Stochastic programming — Στοχαστικός προγραμματισμός

Στοχαστικός προγραμματισμός (αγγλ. stochastic programming) — κλάδος του μαθηματικού προγραμματισμού που αναπτύσσει μοντέλα και μεθόδους επίλυσης βελτιστοποιητικών προβλημάτων υπό συνθήκες αβεβαιότητας, όταν ορισμένες παράμετροι του μοντέλου δεν είναι ακριβώς γνωστές, αλλά αναπαρίστανται ως τυχαίες μεταβλητές με γνωστές ή εκτιμώμενες κατανομές πιθανότητας.

Σε αντίθεση με τα ντετερμινιστικά προβλήματα, όπου όλα τα δεδομένα θεωρούνται σταθερές ποσότητες, ο στοχαστικός προγραμματισμός αποσκοπεί στην εύρεση λύσης (ή πολιτικής λήψης αποφάσεων) που είναι βέλτιστη με κάποια στατιστική έννοια. Τις περισσότερες φορές αυτό σημαίνει ελαχιστοποίηση ή μεγιστοποίηση της μαθηματικής προσδοκίας της αντικειμενικής συνάρτησης. Η βασική ιδέα είναι να βρεθεί μια πολιτική λήψης αποφάσεων που να είναι η καλύτερη «κατά μέσο όρο» για όλες τις πιθανές πραγματοποιήσεις των τυχαίων παραμέτρων, κάτι που είναι ιδιαίτερα κρίσιμο για προβλήματα όπου οι αποφάσεις λαμβάνονται επανειλημμένα υπό παρόμοιες συνθήκες (π.χ. στη διαχείριση αποθεμάτων ή ενεργειακών συστημάτων).

Μαθηματική διατύπωση του προβλήματος

Σε γενική μορφή, το πρόβλημα στοχαστικού προγραμματισμού μπορεί να διατυπωθεί ως: $\underset{x\in X}{\min }\mathbb{𝔼}[f(x,\xi )]$ όπου:

• $x$ — διάνυσμα μεταβλητών ελέγχου (αποφάσεων) που πρέπει να προσδιοριστεί.
• $X$ — σύνολο αποδεκτών λύσεων για $x$, ορισμένο από ντετερμινιστικούς περιορισμούς.
• $\xi$ — τυχαίο διάνυσμα που αναπαριστά τις αβέβαιες παραμέτρους του προβλήματος (π.χ. ζήτηση, τιμές, καιρικές συνθήκες).
• $f(x,\xi )$ — αντικειμενική συνάρτηση, η τιμή της οποίας εξαρτάται τόσο από την ληφθείσα απόφαση $x$ όσο και από την πραγματοποίηση του τυχαίου διανύσματος $\xi$.
• $\mathbb{𝔼}[\cdot ]$ — τελεστής μαθηματικής προσδοκίας, υπολογιζόμενος ως προς την κατανομή πιθανότητας του διανύσματος $\xi$.

Ενα θεμελιώδης αρχή που διέπει τα πολυσταδιακά στοχαστικά μοντέλα είναι η αρχή μη-προδρομικότητας (αγγλ. non-anticipativity principle). Αυτή ορίζει ότι οι αποφάσεις που λαμβάνονται σε οποιοδήποτε στάδιο μπορούν να εξαρτώνται μόνο από πληροφορίες διαθέσιμες μέχρι εκείνη τη στιγμή και δεν μπορούν να «κοιτούν στο μέλλον».

Δισταδιακό πρόβλημα με δικαίωμα αντιστάθμισης

Το πλέον διαδεδομένο μοντέλο είναι το δισταδιακό πρόβλημα με δικαίωμα αντιστάθμισης (αγγλ. two-stage stochastic program with recourse). Η διαδικασία λήψης αποφάσεων χωρίζεται σε δύο στάδια:

1. Πρώτο στάδιο: Λαμβάνεται η απόφαση «εδώ και τώρα» (here-and-now) — καθορίζεται το διάνυσμα $x$. Αυτή η απόφαση πρέπει να ληφθεί πριν καταστεί γνωστή η συγκεκριμένη πραγματοποίηση του τυχαίου διανύσματος $\xi$.
2. Δεύτερο στάδιο: Αφού το τυχαίο γεγονός έχει συμβεί, λαμβάνεται μια διορθωτική ή αντισταθμιστική απόφαση (recourse decision) — το διάνυσμα $y(\xi )$, με στόχο την ελαχιστοποίηση των αρνητικών συνεπειών ή την αξιοποίηση ευνοϊκών ευκαιριών που προέκυψαν από τον συνδυασμό της απόφασης του πρώτου σταδίου $x$ και του αποτελέσματος $\xi$.

Μαθηματικά, το δισταδιακό πρόβλημα στοχαστικού γραμμικού προγραμματισμού διατυπώνεται ως εξής: $\underset{x\in {\mathbb{ℝ}}^{n_1}}{\min }\{c^{T}x+{\mathbb{𝔼}}_{\xi }[Q(x,\xi )]\}$ υπό τους περιορισμούς του πρώτου σταδίου: $Ax=b,x\ge 0$. Εδώ $Q(x,\xi )$ — η συνάρτηση αντιστάθμισης (recourse function), που αναπαριστά την βέλτιστη τιμή του προβλήματος δευτέρου σταδίου: $Q(x,\xi )=\underset{y\in {\mathbb{ℝ}}^{n_2}}{\min }\{q(\xi {)}^{T}y\mid T(\xi )x+Wy=h(\xi ),y\ge 0\}$ όπου $\xi$ — τυχαίο διάνυσμα που περιλαμβάνει τις παραμέτρους $q(\xi ),T(\xi )$ και $h(\xi )$· ενώ $c,A,b$ και $W$ — ντετερμινιστικές παράμετροι.

Βασικές ιδιότητες και θεωρήματα

• Κυρτότητα: Ένα από τα θεμελιώδη αποτελέσματα της θεωρίας είναι ότι για το δισταδιακό πρόβλημα στοχαστικού γραμμικού προγραμματισμού η αναμενόμενη συνάρτηση αντιστάθμισης $Q(x)={\mathbb{𝔼}}_{\xi }[Q(x,\xi )]$ είναι κυρτή συνάρτηση. Αυτή η ιδιότητα έχει τεράστια σημασία, καθώς εγγυάται ότι το συνολικό πρόβλημα πρώτου σταδίου είναι πρόβλημα κυρτού προγραμματισμού, για το οποίο υπάρχουν αποτελεσματικές μέθοδοι επίλυσης και το ολικό βέλτιστο συμπίπτει με το τοπικό.
• Ντετερμινιστικό ισοδύναμο: Εάν το τυχαίο διάνυσμα $\xi$ έχει πεπερασμένο αριθμό πιθανών πραγματοποιήσεων (σεναρίων) ${\xi }_1,\dots ,{\xi }_K$ με πιθανότητες $p_1,\dots ,p_K$, τότε το πρόβλημα στοχαστικού προγραμματισμού μπορεί να αναδιατυπωθεί ως ένα ενιαίο μεγάλο ντετερμινιστικό πρόβλημα βελτιστοποίησης. Στην περίπτωση αυτή η μαθηματική προσδοκία αντικαθίσταται από σταθμισμένο άθροισμα επί όλων των σεναρίων. Ωστόσο, το μέγεθος αυτού του προβλήματος αυξάνεται γραμμικά με τον αριθμό των σεναρίων, γεγονός που οδηγεί στην «κατάρα της διαστατικότητας» και καθιστά αυτήν την προσέγγιση υπολογιστικά ανεπίλυτη για μεγάλο αριθμό σεναρίων.

Σύγκριση με τη ρωμαλέα βελτιστοποίηση

Ο στοχαστικός προγραμματισμός είναι μία από τις αρκετές προσεγγίσεις βελτιστοποίησης υπό συνθήκες αβεβαιότητας. Η βασική διαφορά του από τη ρωμαλέα βελτιστοποίηση έγκειται στον τρόπο μοντελοποίησης της αβεβαιότητας και στο κριτήριο βελτιστότητας.

Σύγκριση προσεγγίσεων βελτιστοποίησης υπό συνθήκες αβεβαιότητας

Κριτήριο	Στοχαστική βελτιστοποίηση	Ρωμαλέα βελτιστοποίηση
Αναπαράσταση αβεβαιότητας	Οι παράμετροι είναι τυχαίες μεταβλητές με γνωστή κατανομή πιθανότητας	Οι παράμετροι ανήκουν σε ένα δεδομένο σύνολο αβεβαιότητας, κατανομή δεν απαιτείται
Κριτήριο βελτιστότητας	Βελτιστοποίηση της μαθηματικής προσδοκίας της αντικειμενικής συνάρτησης	Βελτιστοποίηση στο χειρότερο σενάριο (minimax)
Χαρακτήρας λύσης	Πολιτική βέλτιστη «κατά μέσο όρο», μπορεί να είναι μη αποδεκτή για σπάνια σενάρια	Λύση εγγυημένα αποδεκτή για όλες τις πραγματοποιήσεις· μπορεί να είναι συντηρητική

Παραδείγματα

• Πρόβλημα εφημεριδοπώλη (αγγλ. newsvendor problem): Κλασικό πρόβλημα διαχείρισης αποθεμάτων, όπου ο πωλητής πρέπει να αποφασίσει πόσες μονάδες εμπορεύματος να αγοράσει, χωρίς να γνωρίζει τη μελλοντική ζήτηση με ακρίβεια. Η λύση εξισορροπεί τον κίνδυνο ζημίας από πλεονάσματα και τον κίνδυνο χαμένων κερδών από ελλείψεις.
• Πρόβλημα αγρότη: Ένας αγρότης αποφασίζει πόσα στρέμματα γης να διαθέσει για διαφορετικές καλλιέργειες στη συνολική έκταση, χωρίς να γνωρίζει τις μελλοντικές καιρικές συνθήκες, οι οποίες επηρεάζουν τις αποδόσεις. Αφού οι καιρικές συνθήκες καταστούν γνωστές, ο αγρότης μπορεί να λάβει διορθωτικές ενέργειες (π.χ. να πουλήσει πλεονάσματα ή να αγοράσει την ελλείπουσα παραγωγή στην αγορά).

Δείτε επίσης

• Μαθηματικός προγραμματισμός
• Επιχειρησιακή έρευνα
• Ρωμαλέα βελτιστοποίηση
• Δυναμικός προγραμματισμός
• Θεωρία ελέγχου

Παραπομπές

</references>