| Abstract : | This diploma thesis sets the goal of studying problems which in order to be solved must be divided into other sub-problems, called stages, requiring a policy decision at each stage. These problems can be characterized as dynamic programming problems and for finding an optimal solution a sequence of interrelated decisions is required. At each stage there are a number of states associated with it. The solution procedure is designed in a way that will lead the optimal policy for the overall problem, i.e. a prescription of the optimal policy decision at each stage for each of the possible states. The process begins by finding the optimal policy for the last stage. Then a recursive relationship which starts the solution procedure at the end and moves backward stage by stage until the overall policy is used in order for the optimal solution to be found at the initial stage.Therefore, dynamic programming is a useful mathematical technique which can be used for solving various problems and particular equations must be developed to fit each situation. For this reason, a certain degree of ingenuity and insight into the general structure of dynamic programming problems is required to recognize when a problem can be solved by dynamic programming method. Within the following chapters, a number of examples are listed for this purpose.
Η συγκεκριμένη διπλωματική εργασία θέτει ως στόχο της τη μελέτη προβλημάτων τα οποία προκειμένου να επιλυθούν απαιτείται να διαιρεθούν σε άλλα υπό-προβλήματα, που ονομάζονται στάδια, ενώ σε κάθε στάδιο απαιτείται η λήψη μίας απόφασης. Τα προβλήματα αυτά μπορούν να χαρακτηριστούν και ως προβλήματα δυναμικού προγραμματισμού και για την εξεύρεση της βέλτιστης λύσης τους απαιτείται μια σειρά αποφάσεων αλληλουχίας. Σε κάθε στάδιο υπάρχει ένας αριθμός αποφάσεων ο οποίος σχετίζεται με αυτό. Η διαδικασία επίλυσης σχεδιάζεται με τέτοιο τρόπο που θα οδηγήσει στη βέλτιστη τακτική αποφάσεων για το συνολικό πρόβλημα μέσω της επιλογής της βέλτιστης απόφασης σε κάθε στάδιο για κάθε μία από τις πιθανές ενέργειες. Η διαδικασία αρχίζει με την εύρεση της βέλτιστης απόφασης για το τελευταίο στάδιο. Στη συνέχεια εφαρμόζεται μιας αναδρομική σχέση η οποία ξεκινά την διαδικασία επίλυσης από το τελευταίο στάδιο συνεχίζει να κινείται προς τα πίσω βήμα-βήμα μέχρι ο συνολικός συνδυασμός αποφάσεων να χρησιμοποιηθεί προκειμένου να βρεθεί η βέλτιστη λύση για το αρχικό στάδιο.Συνεπώς, γίνεται αντιληπτό πως ο δυναμικός προγραμματισμός θεωρείται μια χρήσιμη μαθηματική τεχνική η οποία μπορεί να χρησιμοποιηθεί για την επίλυση διαφόρων προβλημάτων ενώ παράλληλα απαιτείται να αναπτυχθούν συγκεκριμένες εξισώσεις προσαρμοσμένες σε κάθε περίσταση. Για το λόγο αυτό, για να αναγνωρισθεί πότε ένα πρόβλημα μπορεί να επιλυθεί με την βοήθεια του δυναμικού προγραμματισμού απαιτείται εφευρετικότητα και διορατικότητα. Στα επόμενα κεφάλαια παρατίθενται για το σκοπό αυτό ορισμένα παραδείγματα.
|
|---|
Copyright © 2013 Library AUEB. All rights reserved.