Το πρόβλημα της εκχώρησης
Αντικείμενο της παρούσας διπλωματικής εργασίας είναι η μαθηματική θεμελίωση του Linear Assignment Problem. Στο πρώτο κεφάλαιο θα συζητήσουμε τους τρόπους με τους οποίους μπορούμε να αναπαραστήσουμε μία ανάθεση. Θα δούμε ότι μπορεί να γίνει με δύο τρόπους: με τους πίνακες ανάθεσης και με τους διμε...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Μορφή: | Thesis |
| Γλώσσα: | Greek |
| Έκδοση: |
2020
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/13010 |
| id |
nemertes-10889-13010 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-130102022-09-05T09:40:16Z Το πρόβλημα της εκχώρησης The assignment problem Μήτρου, Ευανθία Τσάντας, Νικόλαος Τσάντας, Νικόλαος Μακρή, Ευροσύνη Δημητρίου, Ιωάννης Mitrou, Evanthia Πρόβλημα εκχώρησης Ουγγρικός αλγόριθμος The assignment problem Hungarian algorithm Primal-Dual algorithms MatLab Αντικείμενο της παρούσας διπλωματικής εργασίας είναι η μαθηματική θεμελίωση του 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 και θα ερμηνεύσουμε τα αντίστοιχα συμπεράσματα του προβλήματος. Ο κώδικας που θα χρησιμοποιηθεί σημειώνεται στο τέλος της εργασίας. 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. 2020-01-16T21:02:00Z 2020-01-16T21:02:00Z 2019-08 Thesis http://hdl.handle.net/10889/13010 gr 0 application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Πρόβλημα εκχώρησης Ουγγρικός αλγόριθμος The assignment problem Hungarian algorithm Primal-Dual algorithms MatLab |
| spellingShingle |
Πρόβλημα εκχώρησης Ουγγρικός αλγόριθμος The assignment problem Hungarian algorithm Primal-Dual algorithms MatLab Μήτρου, Ευανθία Το πρόβλημα της εκχώρησης |
| description |
Αντικείμενο της παρούσας διπλωματικής εργασίας είναι η μαθηματική θεμελίωση
του 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 και θα ερμηνεύσουμε τα αντίστοιχα
συμπεράσματα του προβλήματος. Ο κώδικας που θα χρησιμοποιηθεί σημειώνεται στο
τέλος της εργασίας. |
| author2 |
Τσάντας, Νικόλαος |
| author_facet |
Τσάντας, Νικόλαος Μήτρου, Ευανθία |
| format |
Thesis |
| author |
Μήτρου, Ευανθία |
| author_sort |
Μήτρου, Ευανθία |
| title |
Το πρόβλημα της εκχώρησης |
| title_short |
Το πρόβλημα της εκχώρησης |
| title_full |
Το πρόβλημα της εκχώρησης |
| title_fullStr |
Το πρόβλημα της εκχώρησης |
| title_full_unstemmed |
Το πρόβλημα της εκχώρησης |
| title_sort |
το πρόβλημα της εκχώρησης |
| publishDate |
2020 |
| url |
http://hdl.handle.net/10889/13010 |
| work_keys_str_mv |
AT mētroueuanthia toproblēmatēsekchōrēsēs AT mētroueuanthia theassignmentproblem |
| _version_ |
1771297193156673536 |
