Η ουγγρική μέθοδος είναι ένας αλγόριθμος που επιτρέπει την ελαχιστοποίηση του κόστους σε ένα πρόβλημα βελτιστοποίησης που βασίζεται στον γραμμικό προγραμματισμό.
Ο στόχος της ουγγρικής μεθόδου είναι να βρει το ελάχιστο κόστος ενός συνόλου εργασιών που πρέπει να εκτελεστούν από τους πιο κατάλληλους ανθρώπους.
Χρησιμοποιεί γραμμικό προγραμματισμό (PL) για να εκτελέσει μια σειρά βημάτων που μπορούν να αυτοματοποιηθούν. Έτσι, εργαλεία όπως το στατιστικό λογισμικό R (μεταξύ άλλων) έχουν πολλά πολύ χρήσιμα πακέτα για αυτά τα προβλήματα βελτιστοποίησης.
Προέλευση της ουγγρικής μεθόδου
Ο δημιουργός του ήταν ο Ούγγρος μαθηματικός (εξ ου και το όνομά του) Harold W. Kuhn το 1955. Ένας άλλος μαθηματικός, ο James Munkres, το αναθεώρησε το 1957. Με αυτήν την εξέλιξη έχει λάβει άλλα ονόματα όπως ο αλγόριθμος κατανομής Munkres ή Kuhn-Munkres.
Από την άλλη πλευρά, αυτή η μέθοδος έχει προηγούμενο σε δύο συγγραφείς, τους Dénes König και Jenő Egerváry, και τους Εβραίους και τους Ούγγρους. Η πρώτη ανέπτυξε τη θεωρία γραφημάτων στην οποία βασίζεται αυτός ο αλγόριθμος. Το δεύτερο θεώρημα του König γενικεύτηκε και επέτρεψε στον Kuhn να αναπτύξει τη μέθοδο.
Βήματα της ουγγρικής μεθόδου
Τα βήματα που ακολουθούν επιτρέπουν την εφαρμογή της ουγγρικής μεθόδου με απλό τρόπο χρησιμοποιώντας ένα υπολογιστικό φύλλο. Επιπλέον, αυτό το σχήμα που θα δείξουμε θα μας επιτρέψει να δούμε με παγκόσμιο τρόπο τη διαδικασία που θα αναπτύξουμε λεπτομερώς στο τελικό παράδειγμα.
- Ως προκαταρκτικά βήματα, πρέπει να αντιστοιχίσετε άτομα (σειρές) σε μια σειρά έργων (στήλες). Επιπλέον, είναι απαραίτητο να υπολογιστεί το διαφορετικό κόστος κάθε έργου ανάλογα με το ποιος το πραγματοποιεί και να δημιουργήσει έναν πίνακα (C) με αυτές τις πληροφορίες.
- Στον πίνακα (C) αναζητούμε την ελάχιστη τιμή κάθε σειράς. Αφαιρούμε αυτό από όλα τα στοιχεία της σειράς και εκτελούμε την ίδια λειτουργία με τις στήλες. Θα εμφανιστεί ένας νέος πίνακας (C`) με τα αποτελέσματα των προηγούμενων λειτουργιών.
- Στη συνέχεια, δημιουργούμε το «γράφημα των ισοτιμιών», το οποίο μας επιτρέπει να επιλέγουμε τις εργασίες και τα έργα με το χαμηλότερο κόστος. Το βέλτιστο θα ήταν εκείνα τα στοιχεία των οποίων το αποτέλεσμα ήταν μηδέν. Εάν είναι αλήθεια ότι δεν υπάρχει στοιχείο με μηδενική τιμή που αντιστοιχεί σε περισσότερες από μία σειρές, ο αλγόριθμος τελειώνει.
- Διαφορετικά, πρέπει να γίνει μια νέα ανάθεση. Δημιουργείται ένας νέος πίνακας στον οποίο εφαρμόζονται μια σειρά τροποποιήσεων, όπως θα δούμε στο παράδειγμα. Αναδημιουργούμε το γράφημα και συνεχίζουμε μέχρι να έχουμε έναν πίνακα που να έχει τουλάχιστον ένα μηδέν σε κάθε σειρά και σε μη επαναλαμβανόμενες θέσεις.
- Με αυτές τις πληροφορίες έχουμε ήδη ανατεθεί τα άτομα και τα έργα (μηδενικά) που βελτιστοποιούν το πρόβλημα. Εάν μια εργασία έχει ήδη ανατεθεί σε προηγούμενη σειρά, απορρίπτεται στην επόμενη. Για τον υπολογισμό του ελάχιστου κόστους προσθέτουμε το κόστος του αρχικού πίνακα που εμφανίζεται στη θέση αυτών των μηδενικών.
Παράδειγμα μεθόδου της Ουγγαρίας
Ας δούμε ένα απλό παράδειγμα της ουγγρικής μεθόδου του. Ας φανταστούμε ότι έχουμε τρεις εργαζόμενους και πρέπει να ανατεθούν σε τρία έργα. Δημιουργούμε τον αρχικό πίνακα (C) και τις τιμές κόστους σε κάθε κελί. Για αυτό πρέπει να χρησιμοποιήσετε τις διαθέσιμες πληροφορίες στην εταιρεία. Μόλις έχουμε όλα αυτά, ξεκινάμε τη διαδικασία. Ένα υπολογιστικό φύλλο μπορεί να βοηθήσει.
Υπολογίζουμε τα ελάχιστα κάθε σειράς και τα αφαιρούμε από τα στοιχεία αυτής της σειράς και κάνουμε το ίδιο με τις στήλες (βήματα 1 και 2). Στην προκύπτουσα μήτρα (C`) σχεδιάζουμε γραμμές με τέτοιο τρόπο ώστε να καλύπτουν όλα τα μηδενικά και με τη σειρά τους τέμνονται μεταξύ τους (βήμα 3). Βλέπουμε ότι υπάρχουν δύο γραμμές, αλλά η μεγαλύτερη τιμή του αριθμού σειρών ή στηλών είναι τρεις. Πρέπει να συνεχίσουμε.
Τώρα επιλέγουμε τους μικρότερους από τους ακάλυπτους αριθμούς, σε αυτό το παράδειγμα είναι δύο (σκούρο μπλε). Το αφαιρούμε από τα προηγούμενα και το προσθέτουμε σε εκείνα που βρίσκονται όπου οι γραμμές τέμνονται. Στην περίπτωσή μας είναι άλλα δύο (E3, T1). Μας απομένει ένας νέος πίνακας (βήμα 4). Αναδιατυπώνουμε τις γραμμές και μετράμε. Υπάρχουν τρεις γραμμές, όπως ο αριθμός των γραμμών ή στηλών. Ο αλγόριθμος έχει ολοκληρωθεί.
Ξεκινάμε με τη σειρά ή τη στήλη με τα λιγότερα μηδενικά (E1, T1). Εάν μια εργασία έχει ήδη εκχωρηθεί, δεν μπορεί να ανατεθεί εκ νέου, για παράδειγμα, με το E2 δεν μπορείτε να χρησιμοποιήσετε το πρώτο μηδέν του T1, αφού αυτή η εργασία ανατέθηκε στο E1. Το συνολικό κόστος, στην ουγγρική μέθοδο, θα είναι το άθροισμα των δαπανών του αρχικού πίνακα (Βήμα 1) που βρίσκεται στην ίδια θέση με τα επιλεγμένα μηδενικά (βήμα 5).
