Διακριτή Βελτιστοποίηση

Κεντρικό θέμα της διακριτής (ή, αλλοιώς, συνδυαστικής) βελτιστοποίησης είναι η θεωρία ροών σε δίκτυα. Η θεωρία ροών σε δίκτυα έχει εξελιχθεί σε ένα από τους πιο επιτυχημένους κλάδους των Εφαρμοσμένων Μαθηματικών και της Επιχειρησιακής Έρευνας, ενώ παρουσιάζει ισχυρές διασυνδέσεις με τη θεωρία της υπολογιστικής πολυπλοκότητας και τη θεωρία των δομών δεδομένων. Δημιουργήθηκε από ένα ευρύ φάσμα πρακτικών εφαρμογών οι οποίες συνεχώς μέχρι σήμερα πολλαπλασιάζονται. Για την επίλυση των πρακτικών αυτών προβλημάτων αναπτύχθηκε μια αυτόνομη μαθηματική θεωρία που προέκυψε από τις ιδιότητες των μαθηματικών δομών που χρησιμοποιήθηκαν για να προσομοιώσουν τα πραγματικά προβλήματα.

Η εξέλιξη των αλγορίθμων για την επίλυση των προβλημάτων αυτών έδωσε την αφορμή για να αναπτυχθεί σημαντική έρευνα στους τομείς των Διακριτών Μαθηματικών, της Επιχειρησιακής Έρευνας, της Θεωρίας Γραφημάτων, της Θεωρίας Βελτιστοποίησης, και της Θεωρίας της Υπολογιστικής Πολυπλοκότητας. Τέλος, η δυνατότητα των δομών δεδομένων να απεικονίζουν αποτελεσματικά τόσο τα γραφήματα όσο και την πληροφόρηση που απαιτείται κατά τη “λειτουργία” αλγορίθμων γραφημάτων συνέτεινε στο να αναπτυχθούν πολύ επιτυχείς αλγόριθμοι που στηρίζονται τόσο στις μαθηματικές ιδιότητες των προβλημάτων αυτών όσο και στις ιδιότητες των δομών δεδομένων. […]

Η αποτελεσματικότητα των αλγορίθμων δικτύων έχει σαν αποτέλεσμα να λύνονται σήμερα προβλήματα τα οποία εθεωρούντο πολύ μεγάλου μεγέθους για υπολογιστική προσέγγιση.

Στα κεφάλαια που ακολουθούν παρουσιάζονται οι διαφορετικές όψεις του θέματος. Στο Κεφάλαιο 1 αναπτύσσεται η μορφοποίηση των προβλημάτων δικτύων. Στο Κεφάλαιο 2 αναπτύσσονται οι αρχές των βασικών αλγορίθμων για την επίλυση των προβλημάτων αυτών. Στο Κεφάλαιο 3 παρουσιάζονται τα κυριότερα πρακτικά προβλήματα που είναι δυνατό να απεικονιστούν με μαθηματική διατύπωση προβλημάτων δικτύων και να αντιμετωπισθούν με τους αντίστοιχους αλγορίθμους. Στο Κεφάλαιο 4 παρουσιάζονται αλγόριθμοι ταιριασμάτων σε διμερή γραφήματα και θα θέλαμε να ευχαριστήσουμε τον Δρ. Παύλο Ειρηνάκη για τη συνεισφορά του στο υλικό της Παραγράφου 4.3. Στο Κεφάλαιο 5 παρουσιάζονται ορισμένες γενικότερες μέθοδοι συνδυαστικής βελτιστοποίησης που αφορούν ειδικές κατηγορίες προβλημάτων με ακέραιες μεταβλητές. Στο Κεφάλαιο 6 παρουσιάζονται ορισμένα βασικά μοντέλα ακέραιου προγραμματισμού. Κλείνοντας, στο Κεφάλαιο 8 παρουσιάζονται οι βασικοί αλγόριθμοι υπολογισμού ελάχιστων δένδρων.

(από την εισαγωγή του βιβλίου)

ΠΡΟΒΛΗΜΑΤΑ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗΣ ΣΕ ΔΙΚΤΥΑ

Γραφήματα

Ορισμοί

Αναλυτική παράσταση γραφημάτων

Δένδρα

Προβλήματα ροής δικτύων

Το πρόβλημα ροής ελάχιστου κόστους

Ειδικές περιπτώσεις

Γραφήματα και ροές σε δίκτυα

Το πρόβλημα ροής ελάχιστου κόστους: εναλλακτική διατύπωση

απεικόνισης ροής

μετασχηματισμού γραφημάτων

Το θεώρημα της μέγιστης ροής ελάχιστης τομής

Τρία βασικά προβλήματα

Γραμμικός προγραμματισμός και προβλήματα ροής

ροής ελάχιστου κόστους

μέγιστης ροής

συντομότερης διαδρομής

ΚΕΦΑΛΑIΟ 2 : ΑΛΓΟΡIΘΜΟI ΠΡΟΒΛΗΜΑΤΩΝ ΔIΚΤΥΩΝ

Αλγόριθμοι και πολυπλοκότητα

Αλγόριθμοι αναζήτησης

Αλγόριθμοι συντομότερης διαδρομής:ο αλγόριθμος του Dijkstra

ο αλγόριθμος του Floyd

Συντομότερη διαδρομή και ανίχνευση αρνητικών κύκλων: ο αλγόριθμος των Bellman-Ford

Αλγόριθμοι μεγίστης ροής

Αλγόριθμος ροής ελαχίστου κόστους

ΚΕΦΑΛΑΙΟ 3: ΕΦΑΡΜΟΓΕΣ

Το πρόβλημα των χρηματικών ροών

Το πρόβλημα της παραγωγής

Το πρόβλημα της τροφοδοσίας

Ανάθεση εργασιών σε μηχανές

Προγραμματισμός εργασιών σε ομοιόμορφες παράλληλες μηχανές

Αντικατάσταση εξοπλισμού

Ελάχιστη συνεκτικότητα δικτύου

Το πρόβλημα των 'χωριστών εκπροσώπων'

Κατανομή εργασιών σε επεξεργαστές

Προβλήματα χρονικού προγραμματισμού και κρίσιμης διαδρομής

Το πρόβλημα του Rhys

Το πρόβλημα της εξόρυξης

Κατασκευή δρόμων

ΚΕΦΑΛΑΙΟ 4: ΑΛΓΟΡΙΘΜΟΙ ΤΑΙΡΙΑΣΜΑΤΩΝ ΣΕ ΔΙΜΕΡΗ ΓΡΑΦΗΜΑΤΑ

Αλγόριθμος ταιριάσματος μέγιστου μεγέθους

Αλγόριθμος ταιριάσματος μέγιστου βάρους

Ευσταθή ταιριάσματα

Βασικές ιδιότητες του Ευσταθούς Ταιριάσματος

Ο αλγόριθμος Extended Gale-Shapley (EGS)

Εναλλακτική αναπαράσταση και επίλυση του προβλήματος

Περιστροφές (Rotations)

Το πρόβλημα της Ευσταθούς Εισαγωγής στο Πανεπιστήμιο

ΚΕΦΑΛΑΙΟ 5:ΜΕΘΟΔΟΙ ΔΙΑΚΡΙΤΗΣ ΒΕΛΤΙΣΤΟΠΟΙΗΣΗΣ

Οπισθοδρόμηση - Έμμεση απαρίθμηση - Μερικές λύσεις

Έμμεση απαρίθμηση - Αλγόριθμος κλάδος και φράγμα

Ο αλγόριθμος κλάδος και φράγμα για το πρόβλημα της αντιστοίχησης

Ο προσθετικός αλγόριθμος του Balas

ΚΕΦΑΛΑΙΟ 6: ΜΟΝΤΕΛΑ ΑΚΕΡΑΙΟΥ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΥ

Ταιριάσματα σε διμερή γραφήματα

Ταιριάσματα σε γενικά γραφήματα

Προβλήματα κυκλωμάτων που καλύπτουν κόμβους

Το πρόβλημα TSP στην ασύμμετρή του μορφή

Το πρόβλημα TSP στη συμμετρική του μορφή

Το πρόβλημα m-πωλητών - Ασύμμετρη μορφή

Το πρόβλημα m-πωλητών - Συμμετρική μορφή

Το πρόβλημα του ελάχιστου πλήρους κυκλώματος κόμβων

Προβλήματα κυκλωμάτων που καλύπτουν κλάδους

Το πρόβλημα του κυκλώματος Euler

Το πρόβλημα του Κινέζου ταχυδρόμου

Το Πρόβλημα της κάλυψης των κόμβων

Προβλήματα συνόλων

Προβλήματα Χρωματισμού

Το Πρόβλημα της Τετραγωνικής Αντιστοίχησης (The Quadratic Assignment Problem)

Προβλήματα δικτύων μεταφοράς

Το πρόβλημα δρομολόγησης ενός στόλου οχημάτων

Το πρόβλημα σχεδιασμού δικτύου μεταφοράς

Προβλήματα χωροθέτησης

Χωροθέτηση εργοστασίων

Χωροθέτηση καθορισμένης κάλυψης

Χωροθέτηση μέγιστης κάλυψης

ΚΕΦΑΛΑΙΟ 7: ΔΕΝΔΡΑ

ο πρόβλημα τους ελάχιστου (συνεκτικού) δένδρου

Δένδρα Steiner

Εφαρμογές

Δένδρα και προβλήματα δικτύων

ΠΑΡΑΡΤΗΜΑ Α: ΑΣΚΗΣΕΙΣ

ΠΑΡΑΡΤΗΜΑ Β: ΜΑΘΗΜΑΤΙΚΟΣ ΠΡΟΓΡΑΜΜΑΤΙΣΜΟΣ

Το Γραμμικό Πρόβλημα Ελαχίστου

Η Μέθοδος Simplex

Δυϊκή Θεωρία

Μη-γραμμικός Προγραμματισμός

Το Πρόβλημα Μεταφοράς

ISBN: 978-960-9443-13-5

Σελίδες: 288

Έτος Έκδοσης: 2012