Στοχαστικός δυναμικός προγραμματισμός και έλεγχος συστημάτων ουρών αναμονής

Abstract

Ο στοχαστικός δυναμικός προγραμματισμός αποτελεί ένα σημαντικό πεδίο στον τομέα των Εφαρμοσμένων Μαθηματικών και ειδικότερα στην Επιχειρησιακή Έρευνα, στην Μηχανική και άλλου. Η θεμελίωση του στοχαστικού δυναμικού προγραμματισμού διαδραματίστηκε στα μέσα του 19ου αι., από τον Μαθηματικό Richard Bellman, έχοντας ως στόχο να περιγράψει τον τρόπο με τον οποίο λύνονται τα προβλήματα, που διασπώνται σε μία αλληλουχία διαδοχικών αποφάσεων. Σημαντικό είναι να αναφέρουμε πως θεμέλιό του είναι η αρχή της βελτιστοποίησης. Η λέξη «προγραμματισμός», συμβολίζει την δήλωση της κατάστρωσης ενός σχεδίου. Επίσης, μας μένει να αναλύσουμε την λέξη «δυναμικός». Η έννοια αυτή χρησιμοποιήθηκε για να περιγράψει το γεγονός ότι η φύση της διαδικασίας του προγραμματισμού είναι χρονικά μεταβαλλόμενη και πολυσταδιακή, συμβαίνει δηλαδή σε πολλά διαδοχικά χρονικά στάδια. Η εργασία μας ξεκινάει με μία εισαγωγή στο θέμα και στον καθορισμό των διάφορων κριτηρίων βελτιστοποίησης. Στη συνέχεια ασχολούμαστε με τη θεωρία και με εφαρμογές του κριτηρίου βελτιστοποίησης για τον πεπερασμένο και τον άπειρο ορίζοντα. Περιγράφουμε ένα μοντέλο αποθέματος, στον άπειρο ορίζοντα, με βάση το κριτήριο κόστους, την θεωρία, καθώς και τον υπολογισμό του κριτηρίου βελτιστοποίησης του μέσου κόστους, όταν ο χώρος καταστάσεων της διαδικασίας είναι ένα πεπερασμένο σύνολο. Επίσης, μελετάμε τη θεωρία ύπαρξης των βέλτιστων πολιτικών του μέσου κόστους, όταν ο χώρος καταστάσεων είναι άπειρο σύνολο, αλλά και με τον υπολογισμό αυτών. Τέλος, κάνουμε μια αναφορά σε μοντέλα, στα οποία οι ενέργειες που λαμβάνονται βρίσκονται σε επιλεγόμενες εποχές. Κάποιες λέξεις-κλειδιά της εργασίας μας είναι οι ακόλουθες: Στοχαστικός δυναμικός προγραμματισμός, Συστήματα ουράς, Κριτήριο βελτιστοποίησης, Μοντέλο αποθέματος, Βέλτιστη πολιτική, Ενέργειες, Χώρος καταστάσεων, Πεπερασμένος ή άπειρος χρονικός ορίζοντας, Κριτήριο βελτιστοποίησης του μέσου κόστους

The stochastic dynamic programming is an important part to the sector of applied mathematics. The foundation of stochastic dynamic programming took place at the middle of 19th century and was discovered by the Mathematician Richard Bellman, who had in mind to explain the way of solving problems in sequences of successive decisions. It is important to refer that its foundation is the principle of optimization. The word “programming” symbolizes the notation of coming up a plan. Also, we analyze the word “dynamic”. This aspect was used to describe the fact that the nature of programming process is timely transformed and it is multi-stage i.e., it happens in multiple time successive stages. We begin our work by an introduction and the special definition of the optimization criterion. We proceed with the theory and the computation of the finite-time and infinite-time horizon models by defining the optimization criterion. We describe an inventory model for the infinite-time horizon, the theory and the computation of average cost optimization criterion, when the state space is a finite set. In addition, we refer to the average cost optimal policies existence theory, when the state space is an infinite set. We also refer to models, whose actions are selected at chosen time epochs. Some of keywords of our thesis are given: Stochastic Dynamic Programming, Queueing Systems, Optimization criterion, Inventory model, Optimal policy, Actions, State space, finite-time or infinite-time horizon, average cost optimization criterion