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

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

Περιγραφή

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

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

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

Ώρες γραφείου: Παρασκευή 1-3

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

E-mail: dimakis@aueb.gr

Βοηθός: Νίκος Νικολαΐδης, email: nnikon95@gmail.com

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

Διαλέξεις: Πέμπτη 3-5 A32, Παρασκευή 3-5 A25.

Φροντιστήριο: Δευτέρα 7-9μμ Α22, μετά από ανακοίνωση στο eclass

 

Περιεχόμενο Μαθήματος
  1. Διατύπωση μαθηματικών υποδειγμάτων και προβλημάτων βελτιστοποίησης
    • Γραμμικά/Μη γραμμικά προβλήματα
    • Κυρτά/Μη κυρτά προβλήματα, ιδιότητες κυρτών συναρτήσεων
    • Συνεχής/Ακέραιος/Μικτός προγραμματισμός
    • Στατικά/Δυναμικά προβλήματα
    • Υπολογιστική επίλυση προβλημάτων στο περιβάλλον AMPL
  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. Εισαγωγή στην Επιχειρησιακή Έρευνα, 10η Έκδοση, Hillier Frederick S., Lieberman
    Gerald J., [κωδ. Ευδόξου:  59386820]

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

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

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

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

 

Ενότητες

Υλικό μαθήματος

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

Διεξάγονται Δευτέρα 7-9μμ στην Α22.

  1. (13/3) Παραδείγματα προβλημάτων βελτιστοποίησης
  2. (27/3) (3/4) Ακέραια γραμμικά προγράμματα, δυναμικός προγραμματισμός (ασκ. 1-4). Ασκ. 2-3 από εδώ.
  3. (24/4) Κυρτότητα (ασκ. 1, 4, 5(υποερώτημα 2, 3), 6, 7 από εδώ και ασκ. 5 από εδώ
  4. (8/5) Βελτιστοποίηση σε ανοιχτά σύνολα & αλγόριθμοι επίλυσης
  5. (15/5) Μέθοδος Langrange (ασκ. 1,2), συνθήκες KKT (ασκ. 1,2)
  6. (12/6) Μέθοδος simplex και γραμμικός προγραμματισμός (ασκ. 3 από εδώ, ασκ. 2 από εδώ, ασκ. 2 & 3 από εδώ)
  7. (19/6) Δυναμικός προγραμματισμός

Διαλέξεις

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

Ημερολόγιο

Προθεσμία
Γεγονός μαθήματος
Γεγονός συστήματος
Προσωπικό γεγονός

Ανακοινώσεις

περισσότερα…