Περιγραφή μαθήματος

Κωδικός μαθήματος: ΜΥΕ009

Εβδομαδιαίες ώρες διδασκαλίας: 3,1,1

Εξάμηνο σπουδών: >=6ο

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 5

Ιστοσελίδα Μαθήματος:

Προσφερόμενο:

Προαπαιτούμενα:

Περιεχόμενο:

Μοντελοποίηση προβλημάτων ως γραμμικά προγράμματα: Μορφές γραμμικών προγραμμάτων και ισοδυναμία τους. Παραδείγματα μοντελοποίησης προβλημάτων συνδυαστικής βελτιστοποίησης ως γραμμικά προγράμματα. Γεωμετρία χώρου εφικτών λύσεων: Γραμμικοί χώροι — υποχώροι, υπερεπίπεδα, πολύεδρα και πολύτοπα, γραμμική ανεξαρτησία και βάση χώρου λύσεων, κορυφές (ακραία σημεία) και βασικές (εφικτές) λύσεις, θεώρημα Καραθεοδωρή. Ο αλγόριθμος Simplex: Λεξικό και ταμπλό. Εναλλαγή στηλών, κριτήριο ελάχιστου λόγου. Εκφυλισμένες λύσεις, αποφυγή κύκλων. Σημείο εκκίνησης, χρήση ψευδομεταβλητών. Μέθοδος δυο φάσεων. Πολυπλοκότητα του Simplex. Αριθμητική αστάθεια και το πρόβλημα της ακεραιότητας. Θεωρία δυϊκότητας: Δυϊκό γραμμικού προγράμματος, συμπληρωματική χαλαρότητα, λήμμα του Farkas. Ανάλυση ευαισθησίας γραμμικών προγραμμάτων. Ακέραιος γραμμικός προγραμματισμός: Πρόβλημα ελάχιστης ποσότητας, πρόβλημα με διαζευκτικούς περιορισμούς, πρόβλημα χωροθέτησης εγκαταστάσεων. Αλγόριθμος διακλάδωσης και οριοθέτησης. Αλγόριθμος επιπέδων αποκοπής. Αλγόριθμοι Εσωτερικών Σημείων: Μέθοδος του Karmakar, πρωτεύων-δυϊκός αλγόριθμος εσωτερικών σημείων. Εφαρμογές γραμμικού προγραμματισμού: Επίλυση παιγνίων μηδενικού αθροίσματος μεταξύ δυο παικτών με χρήση γραμμικού προγραμματισμού. Προβλήματα προσδιορισμού βέλτιστων ροών σε δίκτυα (ροές μέγιστου όγκου / ελαχίστου κόστους, εύρεση ελαχίστων διαδρομών κ.λπ.).

Παρατηρήσεις: