| Περίληψη: | Αντικείμενο της παρούσας διπλωματικής εργασίας είναι η μαθηματική θεμελίωση
του 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 και θα ερμηνεύσουμε τα αντίστοιχα
συμπεράσματα του προβλήματος. Ο κώδικας που θα χρησιμοποιηθεί σημειώνεται στο
τέλος της εργασίας.
|
|---|
