Βελτιστοποίηση Δικτύων


Κωδικός 627
Εξάμηνο Χειμερινό
Ώρες Διδασκαλίας - Ώρες Εργαστηρίου 3 - 0
Διδάσκοντες Μιλτιάδης Αναγνώστου
Σύνδεσμοι Ιστοσελίδα Μαθήματος
Πλατφόρμα Διδασκαλίας Τμήμα 1: BigBlueButton

Περιγραφή

Εισαγωγή στη γραφοθεωρία για την περιγραφή δικτύων. Προβλήματα ροής σε δίκτυα, σύνθεση ροών. Ροή ελάχιστου κόστους, ροή πολλών αγαθών, προβλήματα διακριτής βελτιστοποίησης, αλγόριθμοι καθορισμού της ροής. Προβλήματα ελάχιστης διαδρομής, επιγραφές, μέθοδοι καθορισμού/διόρθωσης των επιγραφών, πλειστηριασμοί. Μέγιστης ροή, ελάχιστης τομή, αλγόριθμος Ford-Fulkerson, αλγόριθμοι βασισμένοι σε τιμές. Το πρόβλημα της ροής ελαχίστου κόστους, μετασχηματισμοί του προβλήματος, δυαδική μορφή. Η μέθοδος Simplex, μέθοδοι δυαδικής ανόδου. Πλειστηριασμοί. Μη γραμμική βελτιστοποίηση δικτύων, πολλαπλές ροές, ακέραιοι περιορισμοί, δίκτυα με κέρδη, αλγόριθμοι και προσεγγίσεις. Προβλήματα με ακέραιους περιορισμούς, χαλάρωση Lagrange. Προσεγγιστικοί αλγόριθμοι για NP-δύσκολα προβλήματα. Δένδρο Steiner, πρόβλημα του περιοδεύοντος πωλητή. Γεωμετρικά προβλήματα. Αλγόριθμοι online. Μέθοδοι Μόντε Κάρλο. Αναζήτηση ταμπού, γενετικοί αλγόριθμοι, προσομοιωμένη ανόπτηση.