Επιχειρησιακή Έρευνα
Κωνσταντίνα Φούντα
Συμβασιούχος Διδάσκουσα
Μαθησιακά Αποτελέσματα
Με την επιτυχή ολοκλήρωση του μαθήματος ο φοιτητής/τρια θα είναι σε θέση να:
- Γνωρίζει/δηλώνει την μαθηματική θεωρία (έννοιες, θεωρήματα, αποδείξεις) η οποία
σχετίζεται με το εν λόγω μάθημα. - Αναγνωρίζει τους μαθηματικούς τύπους που σχετίζονται με την θεωρία και να
περιγράφει τους τρόπους επίλυσης (π.χ. Μέθοδος M) - Διακρίνει τις διαφορετικές περιπτώσεις των προβλημάτων γραμμικού
προγραμματισμού και να εξηγεί την χρήση τους σε σχέση με το μαθηματικό πρόβλημα
που τίθεται . (πχ Δυϊκή θεωρία, το πρόβλημα μεταφοράς.) - Υπολογίζει βασικά στοιχεία της θεωρίας (π.χ. λύση μέσω της τεχνικής Simplex).
- Κατανοεί, διακρίνει και να επιλύει τις διαφορετικές περιπτώσεις των θεμάτων που
αφορούν τον ακέραιο προγραμματισμό ( Βranch and bound, το πρόβλημα διαμέρισης,
το πρόβλημα της ελάχιστης επικάλυψης συνόλου, δυναμικός προγραμματισμός, το
πρόβλημα του σακιδίου (knapsack problem), γενικευμένο knapsack) - Επιλύει προβλήματα με τη μέθοδο της τοπικής αναζήτησης (πχ Δομή γειτονιάς, μέθοδοι
αναζήτησης γειτονιάς, το πρόβλημα του πλανόδιου πωλητή, διαμέριση γράφων.) - Εξηγεί και επιλύει προβλήματα με χρήση των Ευρετικών αλγορίθμων (Τεχνικές
αποτίμησης απόδοσης, λόγος προσεγγισιμότητας, το πρόβλημα κομβικής επικάλυψης
(vertex covering), μέγιστο ανεξάρτητο υποσύνολο, άνω και κάτω φράγματα, εμπειρική
αποτίμηση ευρετικών μεθόδων). - Συνδυάζει την μαθηματική θεωρία με προβλήματα οικονομικής φύσης που εμπίπτουν
στο μάθημα και να προχωρά επιτυχώς στην υποδειγματοποίησή τους.
Ενδεικτικό Περιεχόμενο Μαθήματος
Μοντέλα επιχειρησιακής έρευνας, πολυπλοκότητα αλγορίθμων, προβλήματα NP-hard. Γραμμικός προγραμματισμός: Αλγόριθμος Simplex, Δυϊκή θεωρία, το πρόβλημα
μεταφοράς. Ακέραιος προγραμματισμός: Βranch and bound, το πρόβλημα διαμέρισης, το πρόβλημα της ελάχιστης επικάλυψης συνόλου, δυναμικός προγραμματισμός, το πρόβλημα του σακκιδίου (knapsack problem), γενικευμένο knapsack. Ευρετικοί αλγόριθμοι: Τεχνικές αποτίμησης απόδοσης, λόγος προσεγγισιμότητας, το πρόβλημα κομβικής επικάλυψης (vertex covering), μέγιστο ανεξάρτητο υποσύνολο, άνω και κάτω φράγματα, εμπειρική αποτίμηση ευρεστικών μεθόδων. Μέθοδοι τοπικής αναζήτησης: Δομή γειτονιάς, μέθοδοι αναζήτησης γειτονιάς, το πρόβλημα του πλανόδιου πωλητή, διαμέριση γράφων. Η προσομοιωμένη ανόπτηση ( simulated annealing): Ο αλγόριθμος του Metropolis, εφαρμογές, το πρόβλημα της μέγιστης τομής.