8116 Μαθηματικός Προγραμματισμός

Μάθημα Επιλογής, Η’ εξάμηνο, 6 μονάδες ECTS

Διδάσκων: Αναπληρωτής Καθηγητής Ιωάννης Μούρτος

URL: https://edu.dmst.aueb.gr/

Περιεχόμενο

Το μάθημα εξετάζει τη θεωρία και τους αλγορίθμους του μαθηματικού προγραμματισμού, καθώς και τη σχέση τους με άλλα πεδία (όπως Θεωρία Παιγνίων). Συγκεκριμένα εξετάζεται η βελτιστοποίηση γραμμικών προβλημάτων, η Δυϊκή Θεωρία, οι βασικοί αλγόριθμοι Γραμμικού Προγραμματισμού, βασικές έννοιες Μη-Γραμμικού Προγραμματισμού και Ακέραιου Προγραμματισμού, η μορφοποίηση προβλημάτων, ο Δυναμικός Προγραμματισμός και η σχέση του Γραμμικού Προγραμματισμού με τη Θεωρία Παιγνίων. Σκοπός είναι η κατανόηση των παραπάνω αλλά και της συνδυασμένης εφαρμογής τους σε προβλήματα βελτιστοποίησης όπως αυτά προκύπτουν από πρακτικές εφαρμογές. Επιμέρους στόχοι είναι η εμβάθυνση ως προς μαθηματικές δομές και ιδιότητες κατηγοριών προβλημάτων, η χρήση αλγορίθμων Μαθηματικού Προγραμματισμού αλλά και ο σχεδιασμός παραλλαγών τους για ειδικές περιπτώσεις προβλημάτων και η μορφοποίηση και επίλυση σχετικών πρακτικών προβλημάτων.

Μαθησιακά Αποτελέσματα

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

  • Να περιγράφουν και να χειρίζονται τις θεμελιώδεις έννοιες, τα βασικά θεωρήματα (Farkas, Karush-Kuhn-Tucker) και τις μεθόδους και αλγορίθμους (simplex, ellipsoid, dynamic programming) του Μαθηματικού Προγραμματισμού.
  • Να εκτελούν τους υπολογισμούς για συγκεκριμένες μεθόδους ή αλγορίθμους Μαθηματικού Προγραμματισμού σε λελογισμένου μεγέθους προβλήματα, π.χ., βήματα αλγορίθμου simplex, βήματα δυναμικού προγραμματισμού, προσδιορισμός δυϊκού προβλήματος, και διατύπωση και έλεγχος αναγκαίας συνθήκης ελαχίστου υπό περιορισμούς.
  • Να μοντελοποιούν πραγματικά προβλήματα από ένα εύρος εφαρμογών (π.χ. παραγωγής, διανομής, σχεδιασμού δικτύων, παιγνίων) ως προβλήματα Μαθηματικού Προγραμματισμού και να προσδιορίζουν την κατάλληλη μέθοδο ή τον κατάλληλο αλγόριθμο βελτιστοποίησής τους.
  • Να αντιλαμβάνονται τις αποδείξεις των σχετικών θεωρημάτων και της γενικότερης μαθηματικής θεμελίωσης του Μαθηματικού Προγραμματισμού, να μπορούν να επικαλούνται συγκεκριμένα θεωρήματα (π.χ. ισχυρού δυισμού) προκειμένου να επιλύσουν αποτελεσματικότερα σχετικά προβλήματα και να μπορούν να διατυπώσουν τις απλούστερες από αυτές τις αποδείξεις.
  • Να μελετούν αυτόνομα και να εμβαθύνουν στην τρέχουσα βιβλιογραφία από επιστημονικά περιοδικά και βιβλία Μαθηματικού Προγραμματισμού, ακόμη και σε γνωστικές περιοχές οι οποίες οριακά εντάσσονται στο περιεχόμενο του μαθήματος.

Προαπαιτούμενα Μαθήματα

Δεν υπάρχουν υποχρεωτικά προαπαιτούμενα μαθήματα. Όμως, συνιστάται ο φοιτητής να έχει εξεταστεί επιτυχώς στα μαθήματα «Μαθηματικά Ι», Διακριτά Μαθηματικά» και «Μαθηματικά ΙΙ» σε προηγούμενο εξάμηνο.

Συνιστώμενη Βιβλιογραφία

  • Εισαγωγή στο Μαθηματικό Προγραμματισμό, Π. Μηλιώτης, Εκδόσεις Σταμούλης, 1994.
  • Γραμμικός Προγραμματισμός, Αλγόριθμοι & Εφαρμογές, Κ. Παπαρρίζος, Εκδόσεις Ζυγός, 1999.

Διδακτικές και Μαθησιακές Μέθοδοι

Διαλέξεις (2 διαλέξεις των 2 ωρών εβδομαδιαίως), φροντιστήρια (1 φροντιστήριο των 2 ωρών εβδομαδιαίως), και προαιρετικές ομάδες γραπτών ασκήσεων (εβδομαδιαίως).

Μέθοδοι Αξιολόγησης/Βαθμολόγησης

Ο τελικός βαθμός ισούται με τον βαθμό της γραπτής τελικής εξέτασης.