METODO UNGHERESE: IN COSA CONSISTE, ESEMPIO - DUDAS - 2026

Il metodo ungherese è un algoritmo utilizzato nei problemi di allocazione quando si desidera ridurre al minimo i costi. Cioè, viene utilizzato per trovare il costo minimo assegnando più persone a varie attività in base al costo minimo. Ogni attività deve essere assegnata a una persona diversa.

Un problema di allocazione è un tipo speciale di problema di programmazione lineare, in cui l'obiettivo è ridurre al minimo il costo o il tempo necessari per completare un numero di lavori da più persone.

Fonte: pixabay.com

Una delle caratteristiche importanti del problema di allocazione è che solo un lavoro (o lavoratore) è assegnato a una macchina (o progetto).

Questo metodo è stato sviluppato dal matematico ungherese D. Konig. Per questo motivo è noto come metodo ungherese per i problemi di assegnazione. È anche noto come algoritmo di allocazione di Kuhn-Munkres.

Qualsiasi problema di allocazione può essere facilmente risolto applicando questo metodo che si compone di due fasi:

- Con la prima fase si effettuano riduzioni di riga e di colonna.

- Nella seconda fase la soluzione viene ottimizzata su base iterativa.

Qual è il metodo ungherese?

Il metodo ungherese consiste di quattro passaggi. I primi due passaggi vengono eseguiti una sola volta, mentre i passaggi 3 e 4 vengono ripetuti fino a trovare un'allocazione ottimale.

Una matrice quadrata di ordine n per n è considerata come dato di input, che deve contenere solo elementi non negativi.

Per un dato problema, se il numero di righe nella matrice non è uguale al numero di colonne, è necessario aggiungere una riga fittizia o una colonna fittizia, a seconda del caso. I costi di allocazione per quelle celle fittizie vengono sempre allocati come zero.

Passaggio 1: sottrarre i minimi di ogni riga

Per ogni riga della matrice, l'elemento con il valore più basso viene selezionato e sottratto da ogni elemento in quella riga.

Passaggio 2: sottrarre i minimi da ciascuna colonna

Allo stesso modo, l'elemento con il valore più basso viene selezionato per ogni colonna e sottratto da ogni elemento in quella colonna.

Passaggio 3: coprire tutti gli zeri con un numero minimo di righe

Tutti gli zeri nella matrice risultante dal passaggio 2 devono essere coperti utilizzando un numero minimo di linee orizzontali e verticali, sia da righe che da colonne.

Se è richiesto un totale di n linee per coprire tutti gli zeri, dove n è uguale alla dimensione n volte n della matrice, ci sarà un'allocazione ottimale tra gli zeri e quindi l'algoritmo si ferma.

In caso contrario, se sono necessarie meno di n righe per coprire tutti gli zeri nella matrice, procedere al passaggio 4.

Passaggio 4: crea zeri aggiuntivi

Viene selezionato l'elemento più piccolo della matrice (chiamato k) che non è coperto da una delle linee eseguite nel passaggio 3.

Il valore di k viene sottratto da tutti gli elementi che non sono coperti da linee. Successivamente, il valore di ka viene aggiunto a tutti gli elementi che sono coperti dall'intersezione di due linee.

Gli elementi coperti da una singola riga vengono lasciati così come sono. Dopo aver eseguito questo passaggio, torni al passaggio 3.

Allocazione ottimale

Dopo che l'algoritmo è stato arrestato nel passaggio 3, viene scelto un insieme di zeri in modo che ogni riga e ogni colonna abbia solo uno zero selezionato.

Se in questo processo di selezione non c'è un singolo zero in una riga o colonna, verrà scelto uno di quegli zeri. Gli zeri rimanenti in quella colonna o riga vengono rimossi, ripetendo lo stesso anche per le altre assegnazioni.

Se non esiste una singola assegnazione zero, esistono più soluzioni. Tuttavia, il costo rimarrà lo stesso per diversi set di incarichi.

Eventuali righe o colonne fittizie aggiunte vengono rimosse. Gli zeri scelti in questa matrice finale corrispondono quindi all'assegnazione ideale richiesta nella matrice originale.

Esempio

Si consideri un'azienda in cui ci sono quattro attività (A1, A2, A3, A4) che devono essere svolte da quattro lavoratori (T1, T2, T3, T4). È necessario assegnare un'attività per lavoratore.

La seguente matrice mostra il costo dell'assegnazione di un determinato lavoratore a una determinata attività. L'obiettivo è ridurre al minimo il costo totale dell'attività composta da queste quattro attività.

Passaggio 1: sottrarre i minimi di ogni riga

Si inizia sottraendo l'elemento con il valore minimo in ogni riga dagli altri elementi in quella riga. Ad esempio, l'elemento più piccolo nella prima riga è 69. Pertanto, 69 viene sottratto da ogni elemento nella prima riga. La matrice risultante è:

Passaggio 2: sottrarre i minimi da ciascuna colonna

Allo stesso modo, l'elemento con il valore minimo di ciascuna colonna viene sottratto dagli altri elementi di quella colonna, ottenendo la seguente matrice:

Passaggio 3: coprire tutti gli zeri con un numero minimo di righe

Ora determineremo il numero minimo di linee (orizzontali o verticali) necessarie per coprire tutti gli zeri nella matrice. Tutti gli zeri possono essere coperti utilizzando 3 linee:

Poiché il numero di righe richiesto è tre ed è inferiore alla dimensione della matrice (n = 4), continuiamo con il passaggio 4.

Passaggio 4: crea zeri aggiuntivi

Viene selezionato l'elemento più piccolo non coperto dalle linee, il cui valore è 6. Questo valore viene sottratto da tutti gli elementi non coperti e questo stesso valore viene aggiunto a tutti gli elementi coperti dall'intersezione di due linee. Ciò si traduce nella seguente matrice:

Come indicato nel metodo ungherese, il passaggio tre deve essere eseguito di nuovo.

Passaggio 3 (ripetere)

Anche in questo caso viene determinato il numero minimo di righe necessarie per coprire tutti gli zeri nella matrice. Questa volta sono necessarie quattro righe:

Poiché il numero di righe richiesto è 4, uguale alla dimensione della matrice (n = 4), abbiamo un'allocazione ottimale tra gli zeri nella matrice. Pertanto, l'algoritmo si ferma.

Allocazione ottimale

Come indica il metodo, la selezione fatta dei seguenti zeri corrisponde a un'assegnazione ottimale:

Questa selezione di zeri corrisponde alla seguente allocazione ottimale nella matrice dei costi originale:

Pertanto, il lavoratore 1 deve eseguire l'attività 3, il lavoratore 2, l'attività 2, il lavoratore 3, l'attività 1 e il lavoratore 4 deve eseguire l'attività 4. Il costo totale di questa assegnazione ottimale è 69 + 37 + 11 + 23 = 140.

Riferimenti

1. Algoritmo ungherese (2019). L'algoritmo ungherese. Tratto da: hungarianalgorithm.com.
2. Studio (2019). Utilizzo dell'algoritmo ungherese per risolvere i problemi di assegnazione. Tratto da: study.com.
3. Wisdom Jobs (2018). Metodo ungherese per la risoluzione dei problemi di assegnazione - Tecniche quantitative per la gestione. Tratto da :isdomjobs.com.
4. Geeks for Geeks (2019). Algoritmo ungherese per problemi di assegnazione. Tratto da: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Algoritmo di corrispondenza massima ungherese. Brillante. Tratto da: bright.org.