Please ensure Javascript is enabled for purposes of website accessibility

Παρουσίαση/Προβολή

Εικόνα επιλογής

Γραμμική και Συνδυαστική Βελτιστοποίηση

(EE916) -  Σ. Δασκαλάκη

Περιγραφή Μαθήματος

Το μάθημα αυτό αποτελεί μια εισαγωγή στο αντικείμενο του Γραμμικού Προγραμματισμού ή Γραμμικής Βελτιστοποίησης, όπως τείνει να ονομάζεται πλέον, αλλά και του Ακέραιου Γραμμικού Προγραμματισμού. Στα δυο αυτά αντικείμενα μελετώνται αρχικά τεχνικές μοντελοποίησης πραγματικών καταστάσεων που οδηγούν  σε προβλήματα επιλύσιμα με τεχνικές Γραμμικού ή ακέραιου προγραμματισμού. Στη συνέχεια καλύπτουμε τις θεωρητικές ανάγκες μας με επανάληψη βασικών εννοιών Γραμμικής Άλγεβρας και  Γεωμετρίας. Στο πλαίσιο αυτό χτίζουμε τη βασική θεωρία του Γραμμικού Προγραμματισμού που οδηγεί στην ανάπτυξη του γνωστότερου αλγορίθμου βελτιστοποίησης, τον Αλγόριθμο Simplex. Ακολουθεί η Δυϊκή θεωρία και η Ανάλυση Ευαισθησίας και οι επακόλουθες παραλλαγές του βασικού αλγορίθμου Simplex. Ο Ακέραιος Προγραμματισμός αποτελεί ένα ξεχωριστό κεφάλαιο του Γραμμικού Προγραμματισμού και μελετάει ένα μεγάλο πλήθος γνωστών από τη βιβλιογραφία προβλημάτων, όπως το πρόβλημα του πλανόδιου πωλητή, το πρόβλημα του σακιδίου, προβλήματα δικτύων π.χ. μεταφοράς και μεταφόρτωσης, καθώς και δικτυακών ροών. Στον Ακέραιο Προγραμματισμό καλύπτεται η μέθοδος Branch & Bound και μπαίνουν τα θεμέλια για τις πιο σύγχρονες επεκτάσεις της.

 

Ημερομηνία δημιουργίας

Παρασκευή, 4 Μαρτίου 2016

Σελίδα μαθήματος
  • Περίγραμμα

    Περιεχόμενο μαθήματος

    Μοντελοποίηση προβλημάτων βελτιστοποίησης με τεχνικές γραμμικού προγραμματισμού. Αλγόριθμος Simplex. Δυϊκή Θεωρία. Συμπληρωματική χαλαρότητα. Αλγόριθμος Dual ? Primal Simplex. Ανάλυση ευαισθησίας. Ακέραιος Προγραμματισμός. Μέθοδος Branch & Bound. Το πρόβλημα του σακιδίου. Το πρόβλημα του πλανόδιου πωλητή. Τετραγωνικός Προγραμματισμός. Τεχνικές μοντελοποίησης με τη βοήθεια ακέραιων μεταβλητών. Ο αλγόριθμος Simplex για δίκτυα. Προβλήματα μεταφοράς και μεταφόρτωσης. Προβλήματα Δικτυακών ροών. Μέθοδος εσωτερικού σημείου.

    Μέθοδοι αξιολόγησης

    Στο μάθημα δεν περιλαμβάνεται εργαστήριο, ωστόσο οι φοιτητές θα πρέπει να μπορούν να προγραμματίζουν στη γλώσσα επιλογής των διδασκόντων (python) και να είναι σε θέση να υλοποιούν διαδικασίες που καλύπτονται στη θεωρία.  Εφ' όσον ο αριθμός των συμμετεχόντων το επιτρέπει θα δοθούν δύο ή τρία σετ ασκήσεων προς επίλυση με συγκεκριμένη ημερομηνία παράδοσης. Τέλος, αντί τελικής εξέτασης θα πρέπει να κάνετε μια τελική εργασία (project) για ένα πρόβλημα δικής σας επιλογής, συνήθως από κάποια δημοσιευμένη εργασία. Η εργασία αυτή θα περιλαμβάνει μοντελοποίηση,  υλοποίηση και επίλυση με κάποιον από τους solvers γραμμικού ή ακέραιου προγραμματισμού.  Η εργασία θα συνοδεύεται με αναφορά 10-15 σελίδων υποστηριζόμενη από σχετική βιβλιογραφία και τον κώδικα υλοποίησης του προβλήματος και θα παρουσιαστεί ενώπιον όλων στο τέλος του εξαμήνου.

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

    Προαπαιτούμενα

    • Γραμμική Άλγεβρα
    • Εισαγωγικές γνώσεις προγραμματισμού με Python

    Ενδεικτική Βιβλιογραφία