Δυναμικός Προγραμματισμός

(1) ΓΕΝΙΚΑ

(2) ΜΑΘΗΣΙΑΚΑ ΑΠΟΤΕΛΕΣΜΑΤΑ

(3) ΠΕΡΙΕΧΟΜΕΝΟ ΜΑΘΗΜΑΤΟΣ

Εισαγωγή. Συνδυαστικά προβλήματα. Βέλτιστος έλεγχος διακριτού χρόνου. Βέλτιστος έλεγχος συνεχούς χρόνου. Εφαρμογές. Παραλλαγμένοι αλγόριθμοι δυναμικού προγραμματισμού. Στοχαστικός δυναμικός προγραμματισμός. Εφαρμογές στοχαστικού δυναμικού προγραμματισμού. Επιλογές πρακτικής εφαρμογής.

Εργαστήρια: Για την εμπέδωση του μαθήματος, οι φοιτητές καλούνται να εκπονήσουν τρεις εργαστηριακές ασκήσεις σε γλώσσα Προγραμματισμού C ή Matlab σε εφαρμογή των μεθόδων του Δυναμικού Προγραμματισμού.
 

(4) ΔΙΔΑΚΤΙΚΕΣ KAI ΜΑΘΗΣΙΑΚΕΣ ΜΕΘΟΔΟΙ – ΑΞΙΟΛΟΓΗΣΗ

Διδακτέα Ύλη ανά Εβδομάδα (13 εβδομάδες) :

1η Εβδομάδα: Δυναμικά Συστήματα & Βέλτιστος Έλεγχος. Δυναμικά Συστήματα Συνεχούς Χρόνου. Δυναμικά Συστήματα Διακριτού Χρόνου. Ελεγξιμότητα και Παρατηρησιμότητα γραμμικών συστημάτων. Το Πρόβλημα Βέλτιστου Ελέγχου. Ορισμοί, Μέθοδοι και Εφαρμογές. Αρχή Μεγίστου και Δυναμικός Προγραμματισμός

2η Εβδομάδα: Εισαγωγή, Συνδυαστικά Προβλήματα και Παίγνια. Εισαγωγή στο Δυναμικό Προγραμματισμό. Αρχή της Βελτιστοποίησης. Διακριτά προβλήματα αποφάσεων πολλαπλών βαθμίδων. Προβλήματα βραχύτατων μονοπατιών. Παίγνια δύο προσώπων. Συνδυαστικά προβλήματα. Το πρόβλημα του περιπλανώμενου πωλητή.

3η Εβδομάδα: Βέλτιστος Έλεγχος Διακριτού Χρόνου. Το πρόβλημα βέλτιστου ελέγχου διακριτού χρόνου. Ο Αναδρομικός Τύπος του Bellman. Διακριτός Δυναμικός Αλγόριθμος Διακριτού Δυναμικού Προγραμματισμού. Υπολογιστικό Κόστος Διακριτού Δυναμικού Προγραμματισμού. Γραμμική Παρεμβολή

4η Εβδομάδα: Βέλτιστος Έλεγχος Διακριτού Χρόνου (συνέχεια) Αριθμητική επίλυση του προβλήματος βέλτιστου ελέγχου. Η μέθοδος branch-and-bound. Επεκτάσεις του προβλήματος βέλτιστου ελέγχου διακριτού χρόνου. Τα Προβλήματα Ελεύθερου Τελικού Χρόνου. Μη Μεταβλητοί Κανόνες Ελέγχου.

5η Εβδομάδα: Βέλτιστος Έλεγχος Συνεχούς Χρόνου
Το πρόβλημα βέλτιστου ελέγχου συνεχούς χρόνου. Η Εξίσωση Hamilton-Jacobi-Bellman

6η Εβδομάδα: Εφαρμογές. Επιλεγμένες εφαρμογές της μεθοδολογίας του Δυναμικού Προγραμματισμού: Το Πρόβλημα Αποθήκευσης. Το Πρόβλημα Αντικατάστασης. Στατικά Προβλήματα Κατανομής. Το Πρόβλημα Αξιοπιστίας. Το Πρόβλημα Κατανομής Εργασίας

7η Εβδομάδα: Εφαρμογές (συνέχεια). Το πρόβλημα κατανομής φορτίου. Προβλήματα ελαχιστοποίησης κόστους για τον έλεγχο επιδημιών. Γραμμικός-Τετραγωνικός έλεγχος συνεχούς και διακριτού χρόνου.

8η Εβδομάδα: Αλγόριθμοι Δυναμικού Προγραμματισμού. Αλγόριθμοι για τη μείωση του υπολογιστικού φόρτου: Διακριτός Διαφορικός Δυναμικός Προγραμματισμός. Αυξάνων Δυναμικός Προγραμματισμός. Διαφορικός Δυναμικός Προγραμματισμός.

9η Εβδομάδα: Στοχαστικός Δυναμικός Προγραμματισμός. Εισαγωγή στο Στοχαστικό Δυναμικό Προγραμματισμό. Το Πρόβλημα Στοχαστικού Βέλτιστου Ελέγχου.

10η Εβδομάδα: Στοχαστικός Δυναμικός Προγραμματισμός (συνέχεια). Μέθοδος Στοχαστικού Δυναμικού Προγραμματισμού. Διακριτός Στοχαστικός Δυναμικός Προγραμματισμός

11η Εβδομάδα: Στοχαστικός Δυναμικός Προγραμματισμός (συνέχεια). Επεκτάσεις του Προβλήματος Στοχαστικού Δυναμικού Προγραμματισμού. Προβλήματα με Νεκρούς Χρόνους. Συσχετιζόμενες Μετρήσιμες Διαταραχές. Χρήση Προγνώσεων.

12η Εβδομάδα: Εφαρμογές Στοχαστικού Δυναμικού Προγραμματισμού. Η έννοια του ρίσκου. Συγκεκριμένα ρεαλιστικά παραδείγματα: Το πρόβλημα του εισοδηματία. Το πρόβλημα του προγραμματισμού επενδύσεων

13η Εβδομάδα: Εφαρμογές Στοχαστικού Δυναμικού Προγραμματισμού (συνέχεια) &
Επιλογές Πρακτικής Εφαρμογής. Το πρόβλημα της βέλτιστης στάσης. Στοχαστικός γραμμικός-τετραγωνικός έλεγχος. To πρόβλημα στοχαστικής γραμμικής-τετραγωνικής βελτιστοποίησης.

Εργαστήρια:
Εβδομάδες 1-3: Εισαγωγή στον προγραμματισμό με C και Matlab.
Εβδομάδες 4-8: Εφαρμογές της μεθοδολογίας του Δυναμικού Προγραμματισμού.
Εβδομάδες 9-12: Αλγόριθμοι επίλυσης προβλημάτων Στοχαστικού Δυναμικού Προγραμματισμού
Εβδομάδα 13: Επαναληπτικό μάθημα.

(5) ΑΞΙΟΛΟΓΗΣΗ ΦΟΙΤΗΤΩΝ

Σχόλια για την Αξιολόγηση των Φοιτητών :

Για την εμπέδωση του μαθήματος, οι φοιτητές καλούνται να εκπονήσουν τρεις εργαστηριακές ασκήσεις σε γλώσσα Προγραμματισμού C ή Matlab με εφαρμογή των μεθόδων του Δυναμικού Προγραμματισμού. Η βαθμολογία των ασκήσεων συμμετέχει κατά 1,5 βαθμό στον βαθμό της γραπτής εξέτασης.

(6) ΣΥΝΙΣΤΩΜΕΝΗ ΒΙΒΛΙΟΓΡΑΦΙΑ

• Παπαγεωργίου Μ. (2021) Δυναμικός Προγραμματισμός, Σημειώσεις Μαθήματος, Πολυτεχνείο Κρήτης, Τμήμα Μηχανικών Παραγωγής και Διοίκησης, Χανιά.
• Bellman, R.E. (1957) Dynamic Programming. Princeton University Press, Princeton.
• Bertsekas, D.P. (2005) Dynamic Programming and Optimal Control - Volume I. 3rd edition, Athena Scientific, Belmont, Massachusetts.
• Chichester. Gill, P.E., Murray, W., Wright, M.H. (1981), Practical Optimization. Academic Press, New York.
• Larson, R.E., Casti, J.L. (1978) Principles of Dynamic Programming - Part I: Basic Analytic and Computational Methods. Dekker, New York.
• Larson, R.E., Casti, J.L. (1982) Principles of Dynamic Programming - Part II: Advanced Theory and Applications. Dekker, New York.
• Fletcher, R. (1987) Practical Methods of Optimization (2nd Edition). John Wiley & Sons.
• Sennott L.I. (1999) Stochastic Dynamic Programming and the Control of Queueing Systems, Wiley, New York.
• Whitle P. (1982 & 1983) Optimization over time Dynamic Programming and Stochastic Control, Vol. 1 & 2, Wiley & Sons, Australia.