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

Περίγραμμα Μαθήματος Αλγοριθμική Επιχειρησιακή Έρευνα

Μοντέλα επιχειρησιακής έρευνας, πολυπλοκότητα αλγορίθμων, προβλήματα 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

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

Γραπτή εξέταση στο τέλος του εξαμήνου και προαιρετικές εργασίες.