Please use this identifier to cite or link to this item: http://hdl.handle.net/10889/13010
Title: Το πρόβλημα της εκχώρησης
Other Titles: The assignment problem
Authors: Μήτρου, Ευανθία
Keywords: Πρόβλημα εκχώρησης
Ουγγρικός αλγόριθμος
Keywords (translated): The assignment problem
Hungarian algorithm
Primal-Dual algorithms
MatLab
Abstract: Αντικείμενο της παρούσας διπλωματικής εργασίας είναι η μαθηματική θεμελίωση του Linear Assignment Problem. Στο πρώτο κεφάλαιο θα συζητήσουμε τους τρόπους με τους οποίους μπορούμε να αναπαραστήσουμε μία ανάθεση. Θα δούμε ότι μπορεί να γίνει με δύο τρόπους: με τους πίνακες ανάθεσης και με τους διμερείς γράφους. Επιπλέον θα δοθούν δύο ειδικές περιπτώσεις του Assignment Problem. Στο δεύτερο κεφάλαιο θα μελετήσουμε εκτενέστερα την θεωρία των γράφων και θα δώσουμε κάποια θεωρήματα τα οποία είναι πολύ σημαντικά ώστε να δείξουμε ότι υπάρχει η τέλεια αντιστοίχιση μεταξύ δύο συνόλων που περιέχουν ίσο αριθμό στοιχείων. Στην συνέχεια, στο τρίτο κεφάλαιο θα μελετήσουμε το Linear Sum Assignment Problem (L.S.A.P.) δίνοντας το μαθηματικό μοντέλο και τη μαθηματική θεμελίωσή του. Επιπλέον θα περιγράψουμε αναλυτικά την διαδικασία του Ουγγρικού αλγόριθμου, όπου είναι ο πιο σημαντικός αλγόριθμος για την επίλυση του L.S.A.P. Στο τέταρτο κεφάλαιο θα μελετηθεί το Multi-Dimensional Assignment Problem, όπου αποτελεί επέκταση του L.S.A.P. και θα δοθεί το μαθηματικό μοντέλο. Και τέλος, στο πέμπτο κεφάλαιο θα επιλύσουμε ένα πρόβλημα εκχώρησης με την βοήθεια της MATLAB και του στατιστικού πακέτου της R και θα ερμηνεύσουμε τα αντίστοιχα συμπεράσματα του προβλήματος. Ο κώδικας που θα χρησιμοποιηθεί σημειώνεται στο τέλος της εργασίας.
Abstract (translated): The purpose of this dissertation is the mathematical foundation of the Linear Assignment Problem. In the first chapter we will discuss about the different ways of presenting a permutation. We will see that it can be achieved with two ways: with permutation matrices and with bipartite graphs. In addition, we will present two special cases of assignment problem. In the second chapter, we will deeply discuss about the graph theory and prove some theories which are very important to show that there is the perfect matching between two sets which have equal number of elements. Subsequently, in the third chapter, we will study the Linear Sum Assignment Problem (L.S.A.P.) focusing on the mathematical model and foundation. Moreover, we will describe analytically the operation of Hungarian algorithm, which is the most important algorithm for solving L.S.A.P.In the fourth chapter, we will analyze the Multi-dimensional Assignment Problem, which is extension of the L.S.A.P. , and we will refer the mathematical model. Finally, in the fifth chapter we will solve an assignment problem in MatLab and with the statistical package R, and we will interpret the results. The MatLab code will be given at the end of this project.
Appears in Collections:Τμήμα Μαθηματικών (ΜΔΕ)

Files in This Item:
File Description SizeFormat 
Διπλωματική_Εργασία_ΠΜΣ.pdf1.92 MBAdobe PDFView/Open


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