Είσοδος

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

Γενικά στοιχεία

 

 
Περιγραφή

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

Βλ. επίσης σελίδα του μαθήματος στο courses.cn.ntua.gr

Βιβλιογραφία

Για το πρώτο μέρος του μαθήματος είναι βασικό το βιβλίο του Δημήτρη Μπερτσεκά Network Optimization: Continuous and Discrete Models, Athena Scientific, 1998.

Για το υπόλοιπο δίνεται βιβλιογραφία στις σημειώσεις κάθε κεφαλαίου.

Ώρες και τόπος μαθημάτων

 Κάθε Τετάρτη 5:00-7:00 στην αίθουσα B.2.21 του νέου κτηρίου Ηλεκτρολόγων με πρώτο μάθημα στις 2/11 (και για 13 εβδομάδες).

 



Συγχρηματοδότηση
από την Ε.Ε.