Metodo ungherese cosa consiste, esempio

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

Un problema di assegnazione è un tipo speciale di problema di programmazione lineare, in cui l'obiettivo è ridurre al minimo il costo o il tempo di completamento di una quantità di lavoro da parte di più persone.

Fonte: Pixabay.com

Una delle caratteristiche importanti del problema di allocazione è che un solo 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 allocazione. È anche noto come algoritmo di assegnazione Kuhn-Munkres.

Qualsiasi problema di allocazione può essere risolto facilmente applicando questo metodo costituito da due fasi:

- Con la prima fase ci sono riduzioni di righe e riduzioni della colonna.

- Nella seconda fase la soluzione su una base iterativa è ottimizzata.

[TOC]

Qual è il metodo ungherese?

Il metodo ungherese è composto da quattro passi. I primi due passaggi vengono eseguiti una sola volta, mentre i passaggi 3 e 4 vengono ripetuti fino a quando non trovano un incarico ottimale.

È considerato un fatto di ingresso a una matrice quadrata di ordine n per n, che deve contenere solo elementi non negativi.

Per un determinato 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 assegnazione per queste celle fittizie sono sempre assegnati come zero.

Passaggio 1: sottrarre i minimi di ogni riga

Per ogni riga della matrice, l'elemento viene selezionato con il valore più basso e le subtrazioni di ciascun elemento in quella riga.

Può servirti: qual è l'attività attuale? (Con esempi)

Passaggio 2: sottrarre i minimi di ogni colonna

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

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

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

Se sono necessarie linee totali per coprire tutti gli zeri, essendo n uguali alla dimensione n per n della matrice, ci sarà un incarico ottimale tra gli zeri e quindi l'algoritmo si arresta.

Altrimenti, se sono necessarie meno linee per coprire tutti gli zeri nella matrice, continua con il passaggio 4.

Passaggio 4: creare zeri aggiuntivi

È selezionato il minimo elemento della matrice (chiamata k) che non è coperta da una delle linee realizzate nel passaggio 3.

Viene sottratto il valore di k di tutti gli elementi che non sono coperti dalle linee. Successivamente, il valore di K viene aggiunto a tutti gli elementi coperti dall'intersezione di due linee.

Gli elementi che sono coperti da una singola linea sono lasciati come lo sono. Dopo aver eseguito questo passaggio, torni al passaggio 3.

Assegnazione ottimale

Una volta che l'algoritmo viene interrotto nel passaggio 3, viene scelto un set di zeri in modo che ogni riga e ogni colonna abbiano solo uno zero selezionato.

Se in questo processo di selezione non c'è zero singolo in una riga o colonna, uno di questi zeri verrà quindi scelto. Gli zeri rimanenti vengono eliminati in quella colonna o riga, ripetendo lo stesso per gli altri incarichi.

Può servirti: macrolocalizzazione

Se non esiste una singola allocazione di zeri significa che ci sono più soluzioni. Tuttavia, il costo rimarrà lo stesso per i diversi set di allocazioni.

Qualsiasi riga o colonna fittizia che è stata aggiunta viene eliminata. Gli zeri scelti in questa matrice finale corrispondono all'assegnazione ideale richiesta nella matrice originale.

Esempio

Considera una società in cui vi sono quattro attività (A1, A2, A3, A4) che devono essere eseguite 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 perseguito è ridurre al minimo il costo totale dell'attività composta da queste quattro attività.

Passaggio 1: sottrarre i minimi di ogni riga

L'elemento inizia con il valore minimo di ogni riga degli altri elementi di quella riga. Ad esempio, l'elemento più piccolo nella prima riga è 69. Pertanto, 69 di ciascun elemento viene sottratto nella prima riga. La matrice risultante è:

Passaggio 2: sottrarre i minimi di ogni colonna

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

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

Ora verrà determinato il numero minimo di linee (orizzontale o verticale) che sono necessarie per coprire tutti gli zeri nella matrice. Tutti gli zeri possono essere coperti usando 3 righe:

Poiché il numero di linee richieste è tre ed è inferiore alla dimensione della matrice (n = 4), continua con il passaggio 4.

Può servirti: gestione del progetto: cosa è, fasi, obiettivi, esempi

Passaggio 4: creare zeri aggiuntivi

È selezionato l'elemento più basso non coperto dalle linee, il cui valore è 6. Questo valore di tutti gli elementi non coperti viene sottratto 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 numero tre deve essere eseguito di nuovo.

Passaggio 3 (ripetizione)

Ancora una volta viene determinato il numero minimo di linee richieste per coprire tutti gli zeri nella matrice. Questa volta sono richieste quattro righe:

Poiché il numero di linee richieste è 4, pari alla dimensione della matrice (n = 4), esiste un incarico ottimale tra gli zeri nella matrice. Pertanto, l'algoritmo si ferma.

Assegnazione ottimale

Come indicato dal metodo, la selezione effettuata dei seguenti zeri corrisponde a un incarico ottimale:

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

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

Riferimenti

1. Algoritmo Ungheria (2019). L'algoritmo Ungheria. Tratto da: ungherese.com.
2. Studio (2019). Utilizzo dell'algoritmo Ungheria per risolvere i problemi di assegnazione. Preso da: studio.com.
3. Wisdom Jobs (2018). Metodo Ungheria per risolvere il problema dell'assegnazione - Tecniche quantitative per la gestione. Tratto da: Wisdomjobs.com.
4. Geeks for Geeks (2019). Algoritmo Ungheria per il problema dell'assegnazione. Tratto da: geeksforgeeks.org.
5. Karleight Moore, Nathan Landman (2019). Algoritmo di abbinamento massimo in Ungheria. Brillante. Tratto da: brillante.org.