Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/13830
Title: Το πρόβλημα μεταφοράς
Other Titles: The transportation problem
Authors: Πάνου, Μαρία
Keywords: Πρόβλημα μεταφοράς
Διαδικασία ανακατανομής των εκχωρήσεων (MODI)
Βάση B
Βασικό σύνολο κελιών B
Ζευγνύον δέντρο
Keywords (translated): Transportation problem
Modified distribution method ­MODI
Basis B
Basic set of cells B
θ−loop
Spanning tree
Abstract: Στην παρούσα διπλωματική εργασία παρουσιάζεται το Πρόβλημα Μεταφοράς. Το πρόβλημα μεταφοράς αποτελεί ειδική περίπτωση προβλήματος γραμμικού προγραμματισμού, με στόχο την ελαχιστοποίηση του κόστους μεταφοράς των προϊόντων από τους σταθμούς προέλευσης στους σταθμούς προορισμού. Στο πρώτο κεφάλαιο, δίνεται ο ορισμός του προβλήματος. Αποδεικνύεται ότι, η προσφορά των σταθμών προέλευσης και η ζήτηση των σταθμών προορισμού πρέπει να ταυτίζονται για την ύπαρξη εφικτών λύσεων. Επίσης, αποδεικνύεται ότι, ένας από τους περιορισμούς του προβλήματος πλεονάζει και όταν παραλειφθεί οι υπόλοιποι αποτελούν γραμμικά ανεξάρτητο σύστημα εξισώσεων. Τέλος, μέσω του πίνακα μεταφοράς, καταγράφονται οι πληροφορίες του προβλήματος και παρουσιάζονται οι εφικτές λύσεις του. Στο δεύτερο κεφάλαιο αναλύεται η μεθοδολογία που χρησιμοποιείται για την εύρεση βέλτιστης λύσης. Αρχικά, προσδιορίζεται μια αρχική βασική εφικτή λύση με τη βοήθεια μιας μεθόδου γι’ αυτό το σκοπό, όπως είναι η μέθοδος του Vogel. Στη συνέχεια, περιγράφεται η διαδικασία ανακατανομής των εκχωρήσεων (MODI) για μετάβαση σε βελτιωμένη βασική εφικτή λύση μέχρι την ικανοποίηση του κριτηρίου αριστότητας. Τέλος, γίνεται αναφορά στην ανάλυση ευαισθησίας μιας άριστης λύσης για το πρόβλημα μεταφοράς. Στο τρίτο κεφάλαιο, περιγράφεται μια μέθοδος labeling για το πρόβλημα μεταφοράς. Δίνονται βασικές έννοιες της θεωρίας γραφημάτων, όπως ο απλός κύκλος και το ζευγνύον δέντρο και ο τρόπος εφαρμογής τους στο πρόβλημα μεταφοράς. Με χρήση μεθόδου labeling, γίνεται η μετάβαση σε βελτιωμένη βασική εφικτή λύση, χωρίς να χρησιμοποιηθεί ο πίνακας μεταφοράς για τον εντοπισμό του μονοπατιού ανακατανομής των εκχωρήσεων (θ−loop).
Abstract (translated): In this dissertation the Transportation Problem is presented. The transportation problem is a special type of linear program in which the objective is to minimize the cost of shipping products from a number of sources to a number of destinations. The definition of the problem is given in the first chapter. It is shown that the total supply and the total demand must be equal for the existence of a feasible solution. It is also shown that there is exactly one redundant equality constraint and that the remaining is a linearly independent system of constraints. Finally, the transportation tableau is used is for displaying information and a feasible solution of the transportation problem. The methodology used to find the optimal solution is analysed in the second chapter. An initial basic feasible solution is determined. This is achieved with the use of a method, such as the Vogel method. Subsequently, the Modified Distribution method (MODI) for transition to a new basic feasible solution is being used, until the optimality criterion is obtained. Finally, a reference to the sensitivity analysis of an optimal solution to the transportation problem is made. In chapter three, a labeling method for the transportation problem is described. Basic concepts of graph theory are given, such as the simple cycle and the spanning tree and their application to the transportation problem is shown. Using the labeling method, a new basic feasible solution is obtained, without the use of the transportation tableau to determine the θ−loop.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Διπλωματική_Πάνου.pdf680.59 kBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.