Metodo ungherese - Che cos'è, definizione e concetto

Il metodo ungherese è un algoritmo che permette di minimizzare i costi in un problema di ottimizzazione basato sulla programmazione lineare.

Lo scopo del metodo ungherese è trovare il costo minimo di un insieme di compiti che devono essere svolti dalle persone più adatte.

Utilizza la programmazione lineare (PL) per eseguire una serie di passaggi che possono essere automatizzati. Pertanto, strumenti come il software statistico R (tra gli altri) hanno diversi pacchetti molto utili per questi problemi di ottimizzazione.

Origine del metodo ungherese

Il suo creatore è stato il matematico ungherese (da cui il nome) Harold W. Kuhn nel 1955. Un altro matematico, James Munkres, lo ha rivisto nel 1957. Con questa evoluzione ha ricevuto altri nomi come l'algoritmo di allocazione Munkres o Kuhn-Munkres. .

D'altra parte, questo metodo ha un precedente in due autori, Dénes König e Jenő Egerváry, entrambi ebrei e ungheresi. Il primo ha sviluppato la teoria dei grafi su cui si basa questo algoritmo. Il secondo ha generalizzato il teorema di König e ha permesso a Kuhn di sviluppare il metodo.

Fasi del metodo ungherese

I passaggi da seguire consentono di eseguire il metodo ungherese in modo semplice utilizzando un foglio di calcolo. Inoltre, questo schema che mostriamo ci permetterà di vedere in modo globale il processo che svilupperemo in dettaglio nell'esempio finale.

• Come passaggi preliminari, devi assegnare le persone (righe) a una serie di progetti (colonne). Inoltre, è necessario calcolare i diversi costi di ogni progetto a seconda di chi lo realizza e costruire una matrice (C) con queste informazioni.
• Nella matrice (C) cerchiamo il valore minimo di ogni riga. Lo sottraiamo da tutti gli elementi della riga ed eseguiamo la stessa operazione con le colonne. Apparirà una nuova matrice (C`) con i risultati delle operazioni precedenti.
• Successivamente, creiamo il «grafico delle uguaglianze», che ci consente di scegliere le attività ei progetti con il costo più basso. L'optimum sarebbero quegli elementi il ​​cui risultato fosse zero. Se è vero che non esiste alcun elemento con valore zero assegnato a più di una riga, l'algoritmo termina.
• In caso contrario, deve essere effettuato un nuovo incarico. Viene realizzata una nuova matrice alla quale vengono applicate una serie di modifiche, come vedremo nell'esempio. Ricreiamo il grafico e continuiamo fino ad avere una matrice che ha almeno uno zero in ogni riga e in posizioni non ripetitive.
• Con queste informazioni abbiamo già le persone e i progetti assegnati (gli zeri) che ottimizzano il problema. Se un'attività è già assegnata in una riga precedente, viene eliminata nella successiva. Per calcolare il costo minimo aggiungiamo i costi della matrice iniziale che compaiono nella posizione di questi zeri.

Esempio di metodo ungherese

Diamo un'occhiata a un semplice esempio del metodo ungherese di. Immaginiamo di avere tre lavoratori e che debbano essere assegnati a tre progetti. Creiamo la matrice iniziale (C) e i valori di costo in ogni cella. Per questo è necessario utilizzare le informazioni disponibili in azienda. Una volta che abbiamo tutto questo, iniziamo il processo. Un foglio di calcolo può aiutare.

Calcoliamo i minimi di ogni riga e li sottraiamo dagli elementi di quella riga e facciamo lo stesso con le colonne (passi 1 e 2). Nella matrice risultante (C`) tracciamo linee in modo tale che coprano tutti gli zeri e si intersechino a loro volta (passo 3). Vediamo che ci sono due righe, ma il valore più grande del numero di righe o colonne è tre. Dobbiamo andare avanti.

Ora scegliamo il più piccolo dei numeri scoperti, in questo esempio è due (blu scuro). Lo sottraiamo dai precedenti e lo aggiungiamo a quelli che si trovano dove le linee si intersecano. Nel nostro caso sono altri due (E3, T1). Ci rimane una nuova matrice (passaggio 4). Ridisegniamo le linee e contiamo. Ci sono tre righe, uguali al numero di righe o colonne. L'algoritmo è terminato.

Iniziamo con la riga o colonna con il minor numero di zeri (E1, T1). Se un'attività è già assegnata non può essere riassegnata, ad esempio con E2 non è possibile utilizzare il primo zero di T1, poiché questa attività è stata assegnata a E1. Il costo totale, nel metodo ungherese, sarà la somma dei costi della matrice originale (Fase 1) situata nella stessa posizione degli zeri scelti (Fase 5).