Algorisme hongarès

L'algorisme hongarès és un algorisme d'optimització el qual resol problemes d'assignació en temps $O(n^{3}\,)$. La primera versió coneguda del mètode Hongarès, va ser inventat i publicat per Harold W. Kuhn el 1955. Va ser revisat per James Munkres el 1957, i ha estat conegut des de llavors com l'algorisme hongarès, l'algorisme de l'assignació de Munkres, o l'algorisme de Kuhn-Munkres. L'algorisme desenvolupat per Kuhn està basat en els primers treballs d'altres dos matemàtics hongaresos: Dénes Kőnig i Jenő Egerváry, d'on prové el seu nom. El gran avantatge del mètode de Kuhn és que és fortament polinòmic, cosa que redueix la seva complexitat computacional. L'algorisme hongarès construeix una solució del problema primal partint d'una solució no admissible (que correspon a una solució admissible del dual) fent-la a poc a poc més admissible.

El 2006 es va descobrir que matemàtic Carl Gustav Jacob Jacobi va solucionar aquest problema en el segle xix, i que la solució es va publicar com a obra pòstuma el 1890 en llatí.

Explicació en termes senzills del problema de l'assignació

Una empresa té tres treballadors: Jaume, Esteve i Ramon. L'empresa necessita que un d'ells netegi el lavabo, un altre escombri el terra i un tercer que netegi els vidres de les finestres, però cadascun demana una paga diferent per fer cada tasca. El problema de l'assignació sorgeix amb la pregunta de quina és la millor manera d'assignar-los les feines tenint en compte que es vol minimitzar el cost total.

Primerament es necessita tenir una matriu de costs dels treballadors realitzant aquests treballs:

	Netejar el lavabo	Escombrar el terra	Netejar els vidres
Jaume	3 €	3 €	3 €
Esteve	3 €	2 €	3 €
Ramon	3 €	3 €	2 €

Tenint en compte aquesta matriu de costs, el resultat de l'algorisme hongarès donarà el menor cost amb el qual aquestes feines es poden realitzar, és a dir, el cost mínim és 7 € quan la distribució de tasques és la següent: en Jaume netejarà el lavabo, n'Esteve escombrarà el terra i en Ramon netejarà els vidres.

Modelat

L'algorisme modela un problema d'assignació com una matriu de costos n×n, on cada element de la fila i, columna j representa el cost d'assignar el treballador i al treball j. L'objectiu és trobar el mínim cost, però si el que es volgués fos el màxim cost, es pot modificar el problema substituint els costos per la diferència entre el cost i el cost màxim. En un problema de cost infinit, tots els elements són restats pel valor màxim de la matriu sencera.

L'algorisme és més fàcil de descriure si formulem el problema amb un graf bipartit. Tenim un graf bipartit complet $G=(S,T;E)$ amb $n$ vèrtexs de treballador ($S$) i $n$ vèrtexs de tasca ($T$), i cada aresta té un cost no negatiu $c(i,j)$. Volem trobar un matching perfecte amb cost mínim.

Anomenem una funció $y:(S\cup T)\to \mathbb {R}$ potencial si $y(i)+y(j)\leq c(i,j)$ per cada $i\in S,j\in T$. El valor de la $y$ potencial és $\sum _{v\in S\cup T}y(v)$. Es pot veure que el cost de cada matching perfecte és com a mínim el valor de cada potencial. El mètode hongarès troba un matching perfecte i un potencial amb cost/valor igual, cosa que demostra l'optimalitat de tots dos. De fet, troba un matching perfecte d'arestes tenses: una aresta $ij$ s'anomena tensa per a una $y$ potencial si $y(i)+y(j)=c(i,j)$. Denotem el subgraf d'arestes tenses com a $G_{y}$. El cost d'un matching perfecte en $G_{y}$ (si n'hi ha) és igual al valor de $y$.

Algorisme

$(1)\,$ Donada la matriu de costos $C\,$, es construeix $C^{\prime }\,$ trobant el valor mínim de cada fila i restant aquest valor a cada element de la fila

$\Rightarrow \;{\mathit {C'}}_{i,j}={\mathit {C}}_{i,j}-\min {\mathit {C}}_{i,j}$

$(2)\,$ Es troba el valor mínim de cada columna i es resta a cada element de la columna.

$\Rightarrow \;{\mathit {C'}}_{i,j}={\mathit {C'}}_{i,j}-\min {\mathit {C}}_{i,j}$

$(3)\,$ A partir de ${\mathit {C'}}\,$ es considera "graf de les igualtats" a $G=(N1,N2,A)\,$ tal que $A\,$ està constituït per totes les còpies $({i,j})\,$ tals que ${\mathit {C'}}_{i,j}=0\,$. En altres paraules, verifiquem si per totes les files existeix una columna amb cost 0 que no ha estat assignada a una altra fila.

Determinar sobre $G\,$ un matching $M\,$ de cardinalitat màxima.

si $|{\mathit {M}}|=|N_{1}|=|N_{2}|\Rightarrow \;STOP$

Si totes les files tenen almenys una intersecció amb cost zero que no ha estat ocupada per una altra fila, estem en l'òptim. Acaba l'algorisme.

$(a)\,$ Considero $C^{\prime }\,$ i s'etiqueten les files que no han estat acoblades o assignades per l'algorisme de matching màxim.

$(b)\,$ S'etiqueten en $C^{\prime }\,$ les columnes que tenen els zeros en correspondència o assignades a les files etiquetades (amb *).

$(c)\,$ Etiquetar les files que no han estat ja etiquetades i acoblades o assignades per l'algorisme de matching màxim amb les columnes ja etiquetades (amb *).

$(d)\,$ Repetir els passos $(b)\,$ i $(c)\,$fins que no hi hagi més files o columnes per etiquetar

$(e)\,$ Esborrar les files NO etiquetades i les columnes etiquetades. Per això es pot traçar una línia recta en les columnes i files esborrades.

$(f)\,$ Sigui $\delta \,$ l'element $C^{\prime }\,$ de valor mínim entre aquells costos no esborrats (o ratllats) en el pas anterior

$(g)\,$ Restar $\delta \,$ a cada element no esborrat i sumar-ho als elements doblement esborrats (o on hi hagi intersecció o creuaments entre les línies marcades en el pas $(e)\,$)

$(h)\,$ Tornar al pas $(3)\,$.

Exemple

En un cert punt de l'algorisme tenim el graf $G\,$ i la matriu $C^{\prime }\,$.

matching màxim del graf de les igualtats.

$C'={\begin{pmatrix}1&2&7&3&0\\3&4&1&0&2\\2&3&6&0&0\\0&6&1&1&0\\2&0&0&4&5\end{pmatrix}}$

En $G\,$ tinc un arc $\Longleftrightarrow \;$ tinc un $0\,$ en$C^{\prime }\,$.

$M=\{(1,5'),(2,4'),(4,1'),(5,3')\}\,$ és matching màxim però no és perfecte, perquè la fila 3 està sense assignar. $\Rightarrow \;$ Tornem al pas $(3)\,$ de l'algorisme

$(a)\,$

${\begin{pmatrix}&&&&&\\&1&2&7&3&0\\&3&4&1&0&2\\\star \;&2&3&6&0&0\\&0&6&1&1&0\\&2&0&0&4&5\end{pmatrix}}$$\Rightarrow \;$

$(b)\,$

${\begin{pmatrix}&&&&\star \;&\star \;\\&1&2&7&3&0\\&3&4&1&0&2\\\star \;&2&3&6&0&0\\&0&6&1&1&0\\&2&0&0&4&5\end{pmatrix}}$$\Rightarrow \;$

$(c)\,$ El matching de les columnes $4'\,$ i $5'\,$ estan acoblades al de les files $1\,$ i $2\Rightarrow \;$

$(d)\,$

${\begin{pmatrix}&&&&\star \;&\star \;\\\star \;&1&2&7&3&0\\\star \;&3&4&1&0&2\\\star \;&2&3&6&0&0\\&0&6&1&1&0\\&2&0&0&4&5\end{pmatrix}}$$\Rightarrow \;$

$(e)\,$

${\begin{pmatrix}&&&&\star \;&\star \;\\\star \;&1&2&7&&\\\star \;&3&4&1&&\\\star \;&2&3&6&&\\&&&&&\\&&&&&\end{pmatrix}}$$\Rightarrow \;$

$(f)\,$

$\delta =min{\begin{pmatrix}1&2&7\\3&4&1\\2&3&5\end{pmatrix}}=1$

$(g)\,$ Resto $\delta \,$ als elements no esborrats de $C^{\prime }\,$ i sumo $\delta \,$ als elements doblement esborrats de $C^{\prime }\,$.

$C'={\begin{pmatrix}0&1&6&3&0\\2&3&0&0&2\\1&2&5&0&0\\0&6&1&2&1\\2&0&0&5&6\end{pmatrix}}$$\Rightarrow \;$

$(h)\,$ Tornem al pas $(1)\,$, per recrear el graf de les igualtats i calcular de nou el matching màxim.

Exemple 2 Problema de minimització

Enunciat del problema: En una empresa existeixen N tasques a realitzar i N persones que poden realitzar-les. Tenim una matriu N×N que conté el cost d'assignar a cada treballador en cada tasca, en el present cas, se suposa que existeixen quatre operaris (a, b, c i d) i quatre tasques a realitzar (1,2,3 i 4). El problema és trobar quina tasca hem d'assignar a cada treballador perquè el cost total sigui mínim. En primer lloc hem de partir d'una matriu com la següent:

${\begin{bmatrix}a1&a2&a3&a4\\b1&b2&b3&b4\\c1&c2&c3&c4\\d1&d2&d3&d4\end{bmatrix}}$

On a, b, c i d són els treballadors que han d'executar les diferents tasques 1, 2, 3 i 4. En la matriu, a1 representa el cost en què s'incorre si el treballador A desenvolupa la tasca 1; a2, a3 i a4 mostra el cost en què s'incorre quan el treballador A executa les tasques 2, 3 i 4 respectivament. De la mateixa forma succeeix per a la resta dels treballadors. La matriu és quadrada de manera que cada treballador pot executar solament una tasca.

Es comença a operar amb la matriu.

• Per fer això, es pren el menor valor de tots els que es troben en la primera fila a_i (i es troba entre 1-4) i és restat dels altres elements d'aquesta fila.
• Es repeteix aquest procediment per a totes les files.
• Això ens porta al fet que en cada fila hi hagi almenys un zero (Poden existir uns quants zeros en una fila, quan hi ha dues caselles que tenen valors iguals i són alhora els valors mínims d'aquestes files).
• Ara disposem d'una matriu on almenys existeix un zero en cada fila.
• Tractem d'assignar als treballadors de manera que cada empleat solament realitzi una tasca i que el cost en cada cas sigui zero.

Això es mostra en la següent matriu, on els zeros són les tasques assignades:

0	a2'	0'	a4'
b1'	b2'	b3'	0'
0'	c2'	c3'	c4'
d1'	0'	d3'	d4'

En alguns casos pot resultar que la matriu anterior no pot ser utilitzada per assignar, com a l'exemple de sota.

0	a2'	a3'	a4'
b1'	b2'	b3'	0'
0	c2'	c3'	c4'
d1'	0	d3'	d4'

Efectivament en el cas de la matriu anterior no es pot realitzar una assignació completa, la tasca 1 és realitzada de manera eficient pels empleats A i C (Existeixen dos zeros en la columna 1). Tots dos no poden ser assignats a la mateixa tasca, també hem d'advertir que ningú pot realitzar la tasca 3 de manera eficient. Per superar això, hem de repetir el procediment anterior per a totes les columnes (és a dir, restar l'element mínim de la columna de tots els elements de la columna) i llavors comprovem si és possible l'assignació.

En la majoria dels casos això ens donarà el resultat, però si encara no és possible l'assignació, llavors s'ha de continuar.

S'han de cobrir tots els zeros de la matriu marcant tan poques columnes com sigui possible. El següent procediment és una manera de fer-ho:

En primer lloc assigna tantes tasques com siguin possible.

• La fila 1 només té un zero, per tant queda assignat. El 0 de la fila 3 queda eliminat perquè és a la mateixa columna

i després s'ha de fer el següent (assignar tasques en les files 2, 3 i 4)

0	a2'	a3'	a4'
b1'	b2'	b3'	0'
0'	c2'	c3'	c4'
d1'	0'	d3'	d4'

• Marca totes les files que no tinguin assignació (fila 1).
• Marca totes les columnes que tinguin zeros en aquesta fila (columna 1).
• Marca totes les files que tinguin assignació en la columna donada (fila 3).
• Marca totes les columnes que tinguin assignacions en la fila donada.
• Repetir aquest procés fins que s'obtingui un circuit tancat.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0'	c2'	c3'	c4'	×
d1'	0'	d3'	d4'

Una vegada realitzat tot això es tracen línies (caselles color gris) sobre totes les columnes marcades i totes les files sense marcar.

×
0	a2'	a3'	a4'	×
b1'	b2'	b3'	0'
0'	c2'	c3'	c4'	×
d1'	0'	d3'	d4'

Dels elements que estan sense ratllar (en blanc), es busca el valor més baix, se'l resta de tots els elements que no estan assenyalats o ratllats i se'l suma als elements que es troben en la intersecció de dues línies. Els altres elements es deixen sense canviar. Ara s'assignen les tasques usant les regles de dalt. Repetiu el procediment fins que sigui possible l'assignació. Bàsicament es troba el segon cost mínim entre dues files. El procediment és repetit fins que siguis capaç de distingir entre els treballadors en termes de menor cost.

Bibliografia

• R.I.Burkard, M.Del'Amico, S.Martello: Assignment Problems. SIAM, Philadelphia PA.) 2009. ISBN 978-0-89871-663-4
• Harold W. Kuhn, "The Hungarian Method for the assignment problem", Naval Research Logistic Quarterly, 2:83-97, 1955. Kuhn's original publication.
• Harold W. Kuhn, "Variants of the Hungarian method for assignment problems", Naval Research Logistic Quarterly, 3: 253-258, 1956.
• J. Munkres, "Algorithms for the Assignment and Transportation Problems", Journal of the Society of Industrial and Applied Mathematics, 5(1):32-38, 1957 March.

Enllaços externs

• R. A. Pilgrim, L'algorisme d'assignació de Munkres. Modificat per a Matrius Rectangulars, apunts del curs, Murray State University. (anglès)