Εισαγωγή: Βελτιστοποίηση, Είδη Προβλημάτων, Μέγεθος Προβλημάτων, Επαναληπτικοί Αλγόριθμοι και Σύγκλιση. Οι Βασικές Ιδιότητες Των Γραμμικών Προγραμμάτων: Εισαγωγή, Παραδείγματα Προβλημάτων Γραμμικού Προγραμματισμού, Βασικές Λύσεις, Το Θεμελιώδες Θεώρημα του Γραμμικού Προγραμματισμού, Σχέσεις με την Κυρτότητα. Μέθοδος Simplex: Οδηγοί, Γειτονικά Ακρότατα Σημεία, Προσδιορισμός Ελάχιστης Εφικτής Λύσης.Υπολογιστικές Διαδικασίες—Μέθοδος Simplex: Τεχνητές Μεταβλητές, Μεταβλητές με Άνω Φράγματα, Η Μέθοδος Simplex σε Μορφή Πινάκων, Η Αναθεωρημένη Μέθοδος Simplex, Δυϊκότητα: Δυϊκά Γραμμικά Προγράμματα, Το Θεώρημα της Δυϊκότητας, Σχέση με τη Διαδικασία Simplex, Ευαισθησία και Συμπληρωματική Χαλαρότητα, Η Δυϊκή Μέθοδος Simplex, Ο Αλγόριθμος Primal-Dual, Αναγωγή Γραμμικών Ανισοτήτων (Περιττές Εξισώσεις, Μηδενικές Μεταβλητές, Μη Ακραίες Μεταβλητές, Εφαρμογές). Προβλήματα Μεταφορών και Δικτύων Ροών: Το Πρόβλημα των Μεταφορών, Εύρευση μιας Βασικής Εφικτής Λύσης, Τριγωνικότητα Βάσης, Η Μέθοδος Simplex για Προβλήματα Μεταφορών, Το Πρόβλημα της Ανάθεσης, Βασικές Έννοιες Δικτύων, Ελάχιστο Κόστος Ροής, Μέγιστη Ροή, Ο Αλγόριθμος Μεταφορών Primal-Dual, Ανασκόπηση. Ο ΑλγόριθμοςτουKarmakar.

Με την ολοκλήρωση των μαθημάτων, ο συμμετέχων θα είναι σε θέση να

• Κατανοεί τις βασικές έννοιες του Γραμμικού Προγραμματισμού
• Μοντελοποιεί πραγματικά πρακτικά προβλήματα βελτιστοποίησης μέτριας πολυπλοκότητας σαν προβλήματα γραμμικού προγραμματισμού
• Επιλύει στην πράξη προβλήματα Γραμμικού Προγραμματισμού που παράγονται από διάφορες εφαρμογές. (Π.χ., την οικονομία, τα δίκτυα)
• Αναλύει της ακρίβειας και τα άλλα χαρακτηριστικά των λύσεων

Γραπτή τελική εξέταση.

• Εισαγωγή: Βελτιστοποίηση, Είδη Προβλημάτων, Μέγεθος Προβλημάτων, Επαναληπτικοί Αλγόριθμοι και Σύγκλιση. – 2 εβδ.
• Οι Βασικές Ιδιότητες Των Γραμμικών Προγραμμάτων: Εισαγωγή, Παραδείγματα Προβλημάτων Γραμμικού
• Προγραμματισμού, Βασικές Λύσεις, Το Θεμελιώδες Θεώρημα του Γραμμικού Προγραμματισμού, Σχέσεις με την Κυρτότητα. – 2 εβδ.
• Μέθοδος Simplex: Οδηγοί, Γειτονικά Ακρότατα Σημεία, Προσδιορισμός Ελάχιστης Εφικτής Λύσης. – 2 εβδ.
• Υπολογιστικές Διαδικασίες—Μέθοδος Simplex: Τεχνητές Μεταβλητές, Μεταβλητές με Άνω Φράγματα, Η
• Μέθοδος Simplex σε Μορφή Πινάκων, Η Αναθεωρημένη Μέθοδος Simplex, Δυϊκότητα: Δυϊκά Γραμμικά Προγράμματα, – 1 εβδ.
• Το Θεώρημα της Δυϊκότητας, Σχέση με τη Διαδικασία Simplex, Ευαισθησία και Συμπληρωματική Χαλαρότητα,
• Η Δυϊκή Μέθοδος Simplex, Ο Αλγόριθμος Primal-Dual, Αναγωγή Γραμμικών Ανισοτήτων (Περιττές Εξισώσεις,
• Μηδενικές Μεταβλητές, Μη Ακραίες Μεταβλητές, Εφαρμογές). – 2 εβδ.
• Προβλήματα Μεταφορών και Δικτύων Ροών: Το Πρόβλημα των Μεταφορών, Εύρευση μιας Βασικής Εφικτής Λύσης, Τριγωνικότητα Βάσης, Η Μέθοδος Simplex για Προβλήματα Μεταφορών, Το Πρόβλημα της Ανάθεσης, Βασικές Έννοιες Δικτύων, Ελάχιστο Κόστος Ροής, Μέγιστη Ροή, Ο Αλγόριθμος Μεταφορών Primal-Dual, Ανασκόπηση. – 2 εβδ.
• Ο ΑλγόριθμοςτουKarmakar. – 2 εβδ.