Αλγοριθμική Επιχειρησιακή Έρευνα (8ΕΠ20)
Διδάσκων :
ΕίδοςΕπιλογής (υποχρεωτικό)
Εξάμηνο8
ΠερίοδοςΕΕ
ECTS5
Ώρες Θεωρίας3
Ώρες Εργαστηρίου
Περιγραφή
Μοντέλα επιχειρησιακής έρευνας, πολυπλοκότητα αλγορίθμων, προβλήματα NP-hard. Γραμμικός προγραμματισμός: Αλγόριθμος simplex, δυϊκή θεωρία, το πρόβλημα μεταφοράς. Ακέραιος προγραμματισμός: Βranch and bound, το πρόβλημα διαμέρισης, το πρόβλημα της ελάχιστης επικάλυψης συνόλου, δυναμικός προγραμματισμός, το πρόβλημα του σακκιδίου (knapsack problem), γενικευμένο knapsack. Ευρετικοί αλγόριθμοι: Τεχνικές αποτίμησης απόδοσης, λόγος προσεγγισιμότητας, το πρόβλημα κομβικής επικάλυψης (vertex covering), μέγιστο ανεξάρτητο υποσύνολο, άνω και κάτω φράγματα, εμπειρική αποτίμηση ευρεστικών μεθόδων. Μέθοδοι τοπικής αναζήτησης: Δομή γειτονιάς, μέθοδοι αναζήτησης γειτονιάς, το πρόβλημα του πλανόδιου πωλητή, διαμέριση γράφων. Η προσομοιωμένη ανόπτηση (simulated annealing): Ο αλγόριθμος του Metropolis, εφαρμογές, το πρόβλημα της μέγιστης τομής.
Συγγράμματα/Βιβλιογραφία
  • SCHAUM'S ΕΠΙΧΕΙΡΗΣΙΑΚΗ ΕΡΕΥΝΑ, RICHARD BRONSON, GOVINDASAMI NAADIMUTHU, ΕΚΔΟΣΕΙΣ - Επιχειρησιακή έρευνα, Μπότσαρης Χαράλαμπος Ε., ΕΚΔΟΣΕΙΣ ΠΑΠΑΖΗΣΗ ΑΕΒΕ, 2η/2011, ΑΘΗΝΑ
  • Μέθοδοι και Προβλήματα Προγραμματισμού, Δρακάτος Κωνσταντίνος Γ.,Δονάτος Γεώργιος Σ.,Χόμπας Βασίλης Χ., ΕΚΔΟΣΕΙΣ ΠΑΠΑΖΗΣΗ ΑΕΒΕ, 1η έκδ./1981, ΑΘΗΝΑ
  • Μέθοδοι και Εφαρμογές Επιχειρησιακής Έρευνας, Γιάννης Σμυρλής, Γιώργος Καϊμακάμης, Μαρία Πάντα, ΙΩΑΝΝΗΣ ΣΜΥΡΛΗΣ, 1η/2010, ΑΘΗΝΑ
Τρόπος Εξέτασης
Γραπτή εξέταση στο τέλος του εξαμήνου και προαιρετικές εργασίες.