Αλγοριθμική Επιχειρησιακή Έρευνα (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η/2010, ΑΘΗΝΑ, 13572
  • Μέθοδοι και Προβλήματα Προγραμματισμού, Δρακάτος Κωνσταντίνος Γ.,Δονάτος Γεώργιος Σ.,Χόμπας Βασίλης Χ., ΕΚΔΟΣΕΙΣ ΠΑΠΑΖΗΣΗ ΑΕΒΕ, 1η έκδ./1981, ΑΘΗΝΑ, 30215
Τρόπος Εξέτασης
Γραπτή εξέταση στο τέλος του εξαμήνου και προαιρετικές εργασίες.