ΘΠ09 Αλγοριθμική Επιχειρησιακή Έρευνα

• Κ09 - Διακριτά Μαθηματικά

Μοντέλα επιχειρησιακής έρευνας, πολυπλοκότητα αλγορίθμων, προβλήματα NP-hard. Γραμμικός προγραμματισμός: αλγόριθμος simplex, δυϊκή θεωρία, το πρόβλημα μεταφοράς. Ακέραιος προγραμματισμός: branch and bound, το πρόβλημα διαμέρισης, το πρόβλημα της ελάχιστης επικάλυψης συνόλου (set covering), δυναμικός προγραμματισμός, το πρόβλημα του σακιδίου (knapsack problem), γενικευμένο knapsack. Ευρεστικοί αλγόριθμοι: τεχνικές αποτίμησης απόδοσης, λόγος προσεγγισιμότητας, το πρόβλημα κομβικής επικάλυψης (vertex covering), μέγιστο ανεξάρτητο υποσύνολο, άνω και κάτω φράγματα, εμπειρική αποτίμηση ευρεστικών μεθόδων. Mέθοδοι τοπικής αναζήτησης: δομή γειτονιάς, μέθοδοι αναζήτησης γειτονιάς, το πρόβλημα του πλανόδιου πωλητή, διαμέριση γράφων. Η προσομοιωμένη ανόπτηση (simulated annealing): ο αλγόριθμος του Metropolis, εφαρμογές, το πρόβλημα της μέγιστης τομής (max cut).