Θεωρία και υποδείγματα βελτιστοποίησης

Αντώνης Δημάκης

Περιγραφή

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

Ανθρώπινο Δυναμικό

Διδάσκων: Αντώνης Δημάκης

Ώρες γραφείου: Δευτέρα 1-3

Γραφείο: γραφείο 506, 5ος όροφος, Τροίας 2 (νέο κτήριο ΟΠΑ) και μέσω MS Teams

E-mail: dimakis@aueb.gr

Βοηθός: Τριαντάφυλλος Παπαδόπουλος

Εκπαιδευτικές Δραστηριότητες

Διαλέξεις: Δευτέρα 11-1 A44, Τρίτη 3-5 Τ106.

Φροντιστήριο: θα ανακοινωθεί

 

Περιεχόμενο Μαθήματος
  1. Διατύπωση μαθηματικών υποδειγμάτων και προβλημάτων βελτιστοποίησης
    • Γραμμικά/Μη γραμμικά προβλήματα
    • Κυρτά/Μη κυρτά προβλήματα, ιδιότητες κυρτών συναρτήσεων
    • Συνεχής/Ακέραιος/Μικτός προγραμματισμός
    • Στατικά/Δυναμικά προβλήματα
    • Επίλυση προβλημάτων με υπολογιστή
  2. Βελτιστοποίηση χωρίς περιορισμούς
    • Κριτήριο της παραγώγου για τοπικά ακρότατα
    • Βελτιστοποίηση τετραγωνικών συναρτήσεων
    • Αλγόριθμοι αναζήτησης ακροτάτων: πιο απότομη κατάβαση, Newton, ιδιότητες σύγκλισης
    • Παράδειγμα: κατηγοριοποίηση με λογιστική παλινδρόμηση
    • Αναζήτηση σε γραμμή (line search), backtracking
  3. Βελτιστοποίηση με περιορισμούς
    • Η μέθοδος Lagrange για ισοτικούς περιορισμούς
    • Συνθήκες Karush-Kuhn-Tucker
    • Παράδειγμα: support vector machines
    • Δυϊκή θεωρία, ανάλυση ευαισθησίας
    • Παράδειγμα: η αγορά
    • Μέθοδος φραγμού (barrier method)
  4. Γραμμικός προγραμματισμός
    • Ο αλγόριθμος simplex, simplex 2 φάσεων, εκφυλισμένα γραμμικά προγράμματα
    • Δυϊσμός γραμμικών προγραμμάτων, ανάλυση ευαισθησίας, κριτήριο βέλτιστης λύσης
  5. Δυναμικός προγραμματισμός
    • Εξίσωση δυναμικού προγραμματισμού
    • Λύση με αναδρομή προς τα πίσω (backward induction)
    • Παραδείγματα: προβλήματα σακιδίου, βελτιστοποίηση στο χρόνο, μέγιστη κοινή υπακολουθία
Μαθησιακοί στόχοι

Μετά την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα είναι σε θέση:

  • Να σχεδιάζουν συστήματα που συμπεριφέρονται με βέλτιστο τρόπο
  • Να αναπτύσσουν μαθηματικά υποδείγματα με σκοπό τη βελτιστοποίηση συστημάτων
  • Να αναγνωρίζουν τους διάφορους τύπους μαθηματικών υποδειγμάτων για προβλήματα βελτιστοποίησης
  • Να προσδιορίζουν τις βέλτιστες λύσεις προβλημάτων βελτιστοποίησης
  • Να κατανοούν τις μαθηματικές ιδιότητες και αλγορίθμους που χρησιμοποιούνται στην επίλυση προβλημάτων βελτιστοποίησης
Προτεινόμενα συγγράμματα

Συγγράμματα:

  1. Εισαγωγή στην Επιχειρησιακή Έρευνα, 10η Έκδοση, Taha A. Hamdy, [κωδ. Ευδόξου: 59415056]
  2. Εισαγωγή στην Επιχειρησιακή Έρευνα, 11η Έκδοση, Hillier Frederick S., Lieberman
    Gerald J., [κωδ. Ευδόξου: 102072205]

Σημειώσεις διαλέξεων

Τρόποι αξιολόγησης / εξέτασης

Θα υπάρξουν 3 ή 4 σειρές ασκήσων και τελική εξέταση.

Ο τελικός βαθμός υπολογίζεται με τον τύπο 0.7*T + 0.3*A όπου Τ και Α οι βαθμοί (με άριστα το 10) στην τελική εξέταση και τις ασκήσεις αντίστοιχα, εάν Τ >= 4. Εάν Τ < 4 τότε τελικός βαθμός = T.

 

Ενότητες

Φροντιστήρια

Τα φροντιστήρια γίνονται κάθε Πέμπτη 5-7 στην Δ102.

  1. (6/3) Παραδείγματα προβλημάτων βελτιστοποίησης
  2. (13/3) Γραμμικά, ακέραια προγράμματα. Δυναμικός προγραμματισμός
  3. (20/3) Κυρτά προγράμματα
  4. (3/4) Προβλήματα χωρίς περιορισμούς
  5. (8/5) Προβλήματα με ισοτικούς (ασκ.1 και 2) και ανισοτικούς περιορισμούς (ασκ. 1)
  6. (22/5) Ασκήσεις επανάληψης (3 εως 7
  7. (29/5) Γραμμικός προγραμματισμός (ασκ. 2, ασκ. 3). Δυναμικός προγραμματισμός (ασκ. 2 και 3)

Διαλέξεις

  1. (17/2) Εισαγωγική διάλεξη: πληροφορίες για το μάθημα 
  2. (18/2) Προβλήματα βελτιστοποίησης (1), (2), παραδείγματα [διαφάνειες]
  3. (24/5) Παραδείγματα (συν.) Γενικές ιδιότητες [διαφάνειες]
  4. (25/2) Γραμμικά προγράμματα [διαφάνειες]
  5. (4/3) Ακέραια  & μικτά προγράμματα [διαφάνειες]
  6. (10/3) Ακέραια γραμμικά προγράμματα [διαφάνειες], δυναμικός προγραμματισμός [διαφάνειες]
  7. (11/3) Κυρτά προγράμματα [διαφάνειες]
  8. (17/3) Ιδιότητες κυρτών συναρτήσεων [διαφάνειες]
  9. (18/3) Κριτήρια κυρτότητας [διαφάνειες]
  10. (24/3) Ισοδύναμα κυρτά προγράμματα [διαφάνειες]. Κατά κατεύθυνση παράγωγος [διαφάνειες].
  11. (31/3) Bελτιστοποίηση σε ανοικτά σύνολα: ικανές και αναγκαίες συνθήκες [διαφάνειες]
  12. (1/4) Βελτιστοποίηση σε ανοικτά σύνολα: αλγόριθμος πιο απότομης κατάβασης [διαφάνειες]
  13. (7/4) Βελτιστοποίηση σε ανοικτά σύνολα: παραδείγματα [διαφάνειες]
  14. (8/4) Βελτιστοποίηση σε ανοικτά σύνολα: αναζήτηση γραμμής [διαφάνειες]
  15. (28/4) Βελτιστοποίηση σε ανοικτά σύνολα: τετραγωνικές συναρτήσεις, αλγόριθμος Newton [διαφάνειες]
  16. (29/4) Βελτιστοποίση με περιορισμούς: ισοτικοί περιορισμοί, μέθοδος Lagrange [διαφάνειες]
  17. (5/5) Βελτιστοποίηση με ανισοτικούς περιορισμούς [διαφάνειες]
  18. (6/5) Βελτιστοποίηση με περιορισμούς: KKT συνθήκες [διαφάνειες]
  19. (12/5) Παράδειγμα: support vector machines. Δυϊσμός [διαφάνειες]
  20. (13/5) Δυϊσμός, ευαισθησία, μέθοδος φραγμού [διαφάνειες]
  21. (15/5) Γραμμικός προγραμματισμός [διαφάνειες]
  22. (26/5) Γραμμικός προγραμματισμός [διαφάνειες]
  23. (27/5) Γραμμικός προγραμματισμός [διαφάνειες]
  24. (28/5) Δυναμικός προγραμματισμός [διαφάνειες]
  25. (29/5) Δυναμικός προγραμματισμός [διαφάνειες]

Ημερολόγιο