Opera sulla matrice dei costi
Operazioni
- Si sottrae ad ogni riga il suo elemento minimo:
(generiamo zeri sulle righe) - Si sottrae ad ogni colonna il suo elemento minimo:
(generiamo zeri su colonne) - Si cerca l’assegnamento di costo minimo, cercando il ricoprimento degli zeri della matrice. Se il numero di righe e colonne che ricoprono gli zeri è minore del numero di righe della matrice, l’assegnamento non è completo e si deve ridurre ancora la matrice. Altrimenti, si è trovato l’assegnamento completo di costo minimo
- Si barrano le righe e le colonne che ricoprono gli zeri. Sia
l’elemento minimo non barrato. Si aggiunge agli elementi barrati 2 volte (cioè l’incrocio tra riga e colonna) e si sottrae agli elementi non barrati.
Si ripetono
Regola generale per trovare il ricoprimento minimo degli zeri
- Si etichettano le righe lasciate fuori dall’assegnamento;
- Si etichettano le colonne che hanno degli zeri in corrispondenza delle righe etichettate;
- Si etichettano le righe abbinate alle colonne etichettate dall’assegnamento ottenuto;
- Si barrano le righe non etichettate e le colonne etichettate.