| Περίληψη: | Στην παρούσα διπλωματική εργασία παρουσιάζεται το Πρόβλημα Μεταφοράς. Το πρόβλημα μεταφοράς αποτελεί ειδική περίπτωση προβλήματος γραμμικού προγραμματισμού, με στόχο την ελαχιστοποίηση του κόστους μεταφοράς των προϊόντων από τους σταθμούς προέλευσης στους σταθμούς προορισμού. Στο πρώτο κεφάλαιο, δίνεται ο ορισμός του προβλήματος. Αποδεικνύεται ότι, η προσφορά των σταθμών προέλευσης και η ζήτηση των σταθμών προορισμού πρέπει να ταυτίζονται για την ύπαρξη εφικτών λύσεων. Επίσης, αποδεικνύεται ότι, ένας από τους περιορισμούς του προβλήματος πλεονάζει και όταν παραλειφθεί οι υπόλοιποι αποτελούν γραμμικά ανεξάρτητο σύστημα εξισώσεων. Τέλος, μέσω του πίνακα μεταφοράς, καταγράφονται οι πληροφορίες
του προβλήματος και παρουσιάζονται οι εφικτές λύσεις του.
Στο δεύτερο κεφάλαιο αναλύεται η μεθοδολογία που χρησιμοποιείται για την εύρεση βέλτιστης λύσης. Αρχικά, προσδιορίζεται μια αρχική βασική εφικτή λύση με τη βοήθεια μιας μεθόδου γι’ αυτό το σκοπό, όπως είναι η μέθοδος του Vogel. Στη συνέχεια, περιγράφεται η διαδικασία ανακατανομής των εκχωρήσεων (MODI) για μετάβαση σε βελτιωμένη βασική εφικτή λύση μέχρι την ικανοποίηση του κριτηρίου αριστότητας. Τέλος, γίνεται αναφορά στην ανάλυση ευαισθησίας μιας άριστης λύσης για το πρόβλημα μεταφοράς.
Στο τρίτο κεφάλαιο, περιγράφεται μια μέθοδος labeling για το πρόβλημα μεταφοράς. Δίνονται βασικές έννοιες της θεωρίας γραφημάτων, όπως ο απλός κύκλος και το ζευγνύον δέντρο και ο τρόπος εφαρμογής τους στο πρόβλημα μεταφοράς. Με χρήση μεθόδου labeling, γίνεται η μετάβαση σε βελτιωμένη βασική εφικτή λύση, χωρίς να χρησιμοποιηθεί ο πίνακας μεταφοράς για τον εντοπισμό του μονοπατιού ανακατανομής των εκχωρήσεων (θ−loop).
|
|---|
