Συλλογές
Τίτλος Εισαγωγή στον δυναμικό προγραμματισμό
Εναλλακτικός τίτλος Introduction to dynamic programming
Δημιουργός Μαργέτης, Ιωάννης
Συντελεστής Οικονομικό Πανεπιστήμο Αθηνών, Τμήμα Στατιστικής
Δημητράκος, Θεοδόσης
Ψαράκης, Στυλιανός
Κυριακίδης,Επαμεινώνδας
Τύπος Text
Φυσική περιγραφή 71σ.
Γλώσσα el
Αναγνωριστικό http://www.pyxida.aueb.gr/index.php?op=view_object&object_id=8564
Περίληψη Dynamic Programming is a method of optimizing multi-stage problems. It follows the methodology of business research, the stages of which are the collection of relevant and relevant data related to the problem under consideration, the development of a mathematical model, the development of a program based on the mathematical model, the verification of the computational ability of the model and the program; management requirements in relation to the problem under consideration.Solving problems with dynamic programming presupposes their division into stages. These stages should have the Markovian status that politics at one stage does not bind the other stages.In dynamic programming the current stage fully identifies the next stage in terms of deterministic models and largely determines the next stage in terms of stochastic models.Basic concepts of dynamic programming are the state and the policy. By the term state we mean where we are now while by the term politics we mean where we decide to go.A substitute method of dynamic programming is the method of total enumeration which, however, requires large and time consuming calculations.The computational process of the method starts from the division of the problem into stages, the input of the data in its tables or in a network diagram, the development of a retrospective relation for the calculations and the elaboration of the calculations in tables in order to find the optimal valuesSpecifically, we calculate the optimal values of one stage either pre- or retrograde and then add them to the optimal values of the next stages until we successively cover all the stages of the problem and then we will have the total optimal value.In the present work, examples of business content such as receipts, deliveries of goods, advertising and forecasts are solved.Stochastic dynamic programming was applied to the forecasts where future flows are approximated by calculating the expected values if we have the probabilities.In the corresponding example concerning profit forecasts from three investment proposals, we considered each proposal as a separate stage and estimated the optimal price of all proposals.In this example we also combined an approach with decision theory where the problem data was given in a payoff matrix and with the Bayes criterion of maximum returns it was estimated which of the three investment proposals maximizes the expected profits.
Ο Δυναμικός Προγραμματισμός αποτελεί μέθοδο βελτιστοποίησης πολύ-σταδιακών προβλημάτων. Ακολουθεί την μεθοδολογία της επιχειρησιακής έρευνας στάδια της οποίας είναι η συλλογή σχετικών με το υπό εξέταση πρόβλημα και κατάλληλων στοιχείων, η ανάπτυξη μαθηματικού μοντέλου, η ανάπτυξη προγράμματος με βάση το μαθηματικό μοντέλο, η επαλήθευση της υπολογιστικής ικανότητας του μοντέλου και του προγράμματος και η προσαρμογή στις απαιτήσεις της διοίκησης σε σχέση με το υπό εξέταση πρόβλημα.Η επίλυση προβλημάτων με δυναμικό προγραμματισμό προϋποθέτει την διαίρεση τους σε αλληλοεξαρτώμενα στάδια. Τα στάδια θα πρέπει να χαρακτηρίζονται από την Μαρκοβιανή ιδιότητα στο ότι η πολιτική σε ένα στάδιο δεν δεσμεύει την πολιτική στα λοιπά στάδια. Κατά την εφαρμογή του Δυναμικού προγραμματισμού το τρέχων στάδιο προσδιορίζει πλήρως το επόμενο στάδιο σε ότι αφορά τα προσδιοριστικά μοντέλα και προσδιορίζει σε μεγάλο βαθμό το επόμενο στάδιο σε ότι αφορά τα στοχαστικά μοντέλα. Βασικές έννοιες του δυναμικού προγραμματισμού είναι η κατάσταση και η πολιτική. Με το όρο κατάσταση εννοούμε το που βρισκόμαστε τώρα ενώ με τον όρο πολιτική το που αποφασίζουμε να κατευθυνθούμε.Υποκατάστατη μέθοδος του δυναμικού προγραμματισμού είναι η μέθοδος της ολικής απαρίθμησης η οποία όμως απαιτεί μεγάλους και χρονοβόρους υπολογισμούς.Η υπολογιστική διαδικασία της μεθόδου ξεκινά από την διαίρεση του προβλήματος σε στάδια, την εισαγωγή των δεδομένων σε πίνακες των ή σε δικτυακό διάγραμμα, την ανάπτυξη αναδρομικής σχέσης για τους υπολογισμούς και την εκπόνηση των υπολογισμών σε πίνακες προκειμένου να βρεθούν οι βέλτιστες τιμές. Συγκεκριμένα υπολογίζουμε τις βέλτιστες τιμές ενός σταδίου είτε προδρομικά είτε οπισθοδρομικά και στην συνέχεια τις προσθέτουμε στις βέλτιστες τιμές των επόμενων σταδίων μέχρι να καλύψουμε διαδοχικά όλα τα στάδια του προβλήματος και τότε θα έχουμε την συνολική βέλτιστη τιμή. Στην παρούσα εργασία επιλύονται παραδείγματα επιχειρηματικού περιεχομένου όπως εισπράξεις, παραδόσεις εμπορευμάτων, διαφήμισης και προβλέψεων.Για τις προβλέψεις εφαρμόσθηκε στοχαστικός δυναμικός προγραμματισμός όπου οι μελλοντικές ροές προσεγγίζονται με τον υπολογισμό των αναμενόμενων τιμών εφόσον έχουμε τις πιθανότητες. Στο αντίστοιχο παράδειγμα που αφορά προβλέψεις κερδών από τρείς επενδυτικές προτάσεις θεωρήσαμε κάθε πρόταση σαν ένα ξεχωριστό στάδιο και εκτιμήσαμε την βέλτιστη τιμή του συνόλου των προτάσεων. Στο παράδειγμα αυτό συνδυάσαμε και προσέγγιση με θεωρία αποφάσεων όπου τα δεδομένα του προβλήματος δόθηκαν σε payoff matrix και με το κριτήριο μέγιστων αποδόσεων του Bayes εκτιμήθηκε ποια από τις τρείς επενδυτικές προτάσεις μεγιστοποιεί τα αναμενόμενα κέρδη.
Λέξη κλειδί Dynamic programming
Optimization
Multistage decisions
Πολυσταδιακές αποφάσεις
Βελτιστοποίηση
Δυναμικός προγραμματισμός
Διαθέσιμο από 2021-04-20 10:45:41
Ημερομηνία έκδοσης 11/03/2021
Ημερομηνία κατάθεσης 2021-04-20 10:45:41
Δικαιώματα χρήσης Free access
Άδεια χρήσης https://creativecommons.org/licenses/by/4.0/