Τεχνικές Βελτιστοποίησης

Διδάσκοντες Ορέστης Τελέλης
Κατηγορία μαθήματος Ε/ΣΛΔ
Κωδικός μαθήματος ΨΣ-329
Πιστωτικές μονάδες 5
Ώρες μαθήματος 3 ώρες
Ώρες εργαστηρίων 2 ώρες
Ηλεκτρονικό υλικό Προβολή στον Αρίσταρχο (Open e-Class)

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

Στα πλαίσια του μαθήματος διδάσκεται η αναπαράσταση επιχειρησιακών προβλημάτων μέσω γραμμικού προγραμματισμού, ακέραιου προγραμματισμού και συναφών μοντέλων βελτιστοποίησης. Αναπτύσσεται η θεωρητική θεμελίωση των μοντέλων αυτών και εξετάζονται μέθοδοι επίλυσης για καθολική βελτιστοποίηση, ο σχεδιασμός και η ανάλυση ευριστικών μεθόδων, συμπεριλαμβανομένων ευριστικών τοπικής αναζήτησης και προσεγγιστικών αλγορίθμων.

Ολοκληρώνοντας επιτυχώς το μάθημα οι φοιτητές θα είναι σε θέση:

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

Περιεχόμενα

  • Μοντελοποίηση Προβλημάτων με Γραμμικά Προγράμματα.
  • Θεωρία Γραμμικού Προγραμματισμού, Δυϊκότητα.
  • Αλγόριθμος Simplex.
  • Ακέραιος Γραμμικός Προγραμματισμός.
  • Μέθοδος Διακλάδωσης και Αποτίμησης (Branch and Bound).
  • Προβλήματα Μεταφοράς και Ανάθεσης.
  • Βελτιστοποίηση Δικτύων (Διαδρομές, Δένδρα, Ροές, Ταιριάσματα, Αποκοπές).
  • Υπολογιστικά Δύσκολα Προβλήματα.
  • Εισαγωγή στους Προσεγγιστικούς Αλγορίθμους.
  • Μέθοδοι Τοπικής Αναζήτησης.

Προτεινόμενα Συγγράμματα

  • F. S. Hillier, G. J. Lieberman. Εισαγωγή στην Επιχειρησιακή Έρευνα. Εκδόσεις ΤΖΙΟΛΑ, 2017.
  • Ι. Κολέτσος, Δ. Στογιάννης. Εισαγωγή στην Επιχειρησιακή Έρευνα. Εκδόσεις Συμεών, 2017.
  • J. Kleinberg, E. Tardos. Σχεδιασμός Αλγορίθμων. Εκδόσεις Κλειδάριθμος, 2009.

Πρόσθετη Βιβλιογραφία

Επιπλέον, στον Eύδοξο αναρτώνται σε ηλεκτρονική μορφή άρθρα, οπτικοακουστικό υλικό διαλέξεων και διαδικτυακές διευθύνσεις για χρήσιμες πληροφορίες καθώς και ασκήσεις για την εξάσκηση των φοιτητών/τριών. Παρουσιάζονται μελέτες περίπτωσης, παραδειγματικά προβλήματα και μέθοδοι επίλυσης αυτών.