Τι είναι το πρόβλημα της ανάθεσης;

Το πρόβλημα της ανάθεσης είναι ένα κλασικό πρόβλημα συνδυαστικής βελτιστοποίησης: δεδομένου ενός συνόλου εργαζομένων και εργασιών, καθεμία με ένα σχετικό κόστος, βρείτε την αντιστοίχιση ένα προς ένα που ελαχιστοποιεί το συνολικό κόστος. Εμφανίζεται φυσικά στον προγραμματισμό, τη λογιστική, την κατανομή πόρων και την επιχειρησιακή έρευνα — οποιαδήποτε κατάσταση όπου πρέπει να αντιστοιχίσετε δύο ομάδες με τον πιο αποτελεσματικό τρόπο.

Το πρόβλημα επιλύεται με τον αλγόριθμο Hungarian (γνωστός και ως αλγόριθμος Munkres), μια αποτελεσματική μέθοδος που αναπτύχθηκε τη δεκαετία του 1950. Σε αντίθεση με τις μεθόδους brute-force που πρέπει να αξιολογήσουν κάθε μετάθεση, ο αλγόριθμος Hungarian βρίσκει τη βέλτιστη λύση σε πολυωνυμικό χρόνο, καθιστώντας τον πρακτικό ακόμη και για μεσαίως μεγάλους πίνακες.

Περιγραφή εργαλείου

Εισάγετε έναν πίνακα κόστους που αντιπροσωπεύει το κόστος ανάθεσης κάθε εργαζομένου σε κάθε εργασία, στη συνέχεια κάντε κλικ στο Επίλυση για να βρείτε αμέσως τη βέλτιστη ανάθεση. Το εργαλείο επισημαίνει ποια ζεύγη εργαζομένου-εργασίας ελαχιστοποιούν το συνολικό κόστος και εμφανίζει το αποτέλεσμα σε έναν σαφή πίνακα μαζί με το βέλτιστο συνολικό κόστος.

Παραδείγματα

Πίνακας εισόδου (3 εργαζόμενοι × 3 εργασίες):

Εργασία 1 Εργασία 2 Εργασία 3
Εργαζόμενος 1 400 150 400
Εργαζόμενος 2 400 450 600
Εργαζόμενος 3 300 225 300

Βέλτιστες αναθέσεις:

Εργαζόμενος Εργασία Κόστος
Εργαζόμενος 1 Εργασία 2 150
Εργαζόμενος 2 Εργασία 1 400
Εργαζόμενος 3 Εργασία 3 300

Συνολικό κόστος: 850

Χαρακτηριστικά

  • Επεξεργάσιμος πίνακας — κάντε κλικ σε οποιοδήποτε κελί ή κεφαλίδα στήλης για να μετονομάσετε εργαζομένους, εργασίες και κόστη απευθείας στον πίνακα
  • Ρυθμιζόμενο μέγεθος — υποστηρίζει πίνακες από 2×2 έως 8×8
  • Άμεσα αποτελέσματα — ο αλγόριθμος Hungarian εκτελείται στο πρόγραμμα περιήγησης χωρίς επικοινωνία με διακομιστή

Πώς λειτουργεί

Το εργαλείο χρησιμοποιεί τον αλγόριθμο Munkres (Hungarian) για να επιλύσει το πρόβλημα της ανάθεσης βέλτιστα. Κατασκευάζει έναν πίνακα κόστους από τις εισόδους σας, εφαρμόζει μια σειρά βημάτων μείωσης γραμμών και στηλών, και επαναληπτικά βρίσκει μια μέγιστη αντιστοίχιση μηδενικών έως ότου προσδιοριστεί μια πλήρης βέλτιστη ανάθεση. Η χρονική πολυπλοκότητα είναι $O(n^3)$, όπου $n$ είναι η διάσταση του πίνακα.

Για μη τετραγωνικούς πίνακες (περισσότεροι εργαζόμενοι από εργασίες ή αντίστροφα), ο αλγόριθμος συμπληρώνει τον πίνακα με μηδενικά ώστε κάθε εργαζόμενος και κάθε εργασία να αντιστοιχίζονται.

Επεξήγηση επιλογών

  • Αριθμός εργαζομένων / γραμμών — ελέγχει πόσες γραμμές εμφανίζονται στον πίνακα κόστους (2–8)
  • Αριθμός εργασιών / στηλών — ελέγχει πόσες στήλες εμφανίζονται στον πίνακα κόστους (2–8)
  • Κελιά πίνακα κόστους — εισάγετε το κόστος ανάθεσης ενός συγκεκριμένου εργαζομένου σε μια συγκεκριμένη εργασία· δεκτή είναι οποιαδήποτε αριθμητική τιμή

Περιορισμοί

  • Το μέγεθος του πίνακα περιορίζεται στα 8×8 (64 κελιά)
  • Ο αλγόριθμος ελαχιστοποιεί το συνολικό κόστος· για μεγιστοποίηση (π.χ., για πίνακες κέρδους), αρνηθείτε τις τιμές πριν τις εισάγετε
  • Οι μη αριθμητικές τιμές κελιών αντιμετωπίζονται ως μηδέν