Calculadora del Mètode Hongarès (Problema d'Assignació)

Resol problemes d'assignació pas a pas mitjançant l'algorisme Hongarès, des de reduccions per fila/columna fins al cobriment òptim de zeros.

3
Tasca 1Tasca 2Tasca 3
Treballador 1
Treballador 2
Treballador 3
Optimització Combinatòria i Grafs Bipartits

El Problema d'Assignació i l'Algorisme Hongarès: Guia Acadèmica

Desenvolupament matemàtic formal de l'algorisme de Kuhn-Munkres (Mètode Hongarès) per a l'emparellament ponderat i assignació òptima de recursos.

1. Quin problema resol el Model d'Assignació?

El Problema d'Assignació és un model clàssic d'optimització combinatòria on n agents (treballadors, màquines) s'han d'assignar a n tasques de manera bijectiva (un a un). Donada una matriu de costos C on cᵢⱼ representa el cost d'assignar l'agent i a la tasca j, l'objectiu és minimitzar el cost total ∑ cᵢⱼ xᵢⱼ subjecte al fet que cada agent i cada tasca rebin exactament una assignació, amb xᵢⱼ ∈ {0, 1}. El Mètode Hongarès de Harold Kuhn resol aquest problema en temps fortament polinomial O(n³).

2. Els 5 Passos de l'Algorisme Hongarès (Kuhn-Munkres)

Pas 1: Reducció per Files

Troba el valor mínim de cada fila i resta'l de tots els elements d'aquella mateixa fila. Això genera com a mínim un zero a cada fila sense alterar l'ordenació de solucions òptimes.

Pas 2: Reducció per Columnes

Sobre la matriu reduïda, troba el valor mínim de cada columna i resta'l de tots els elements d'aquella columna, garantint almenys un zero per columna.

Pas 3: Cobertura Mínima amb Línies

Traça el nombre mínim de línies horitzontals i verticals per cobrir tots els zeros. Si el nombre de línies és igual a n, existeix una assignació òptima amb cost zero (anar al Pas 5). Si és menor que n, cal anar al Pas 4.

Pas 4: Modificació de la Matriu

Identifica el menor element no cobert k. Resta'l de tots els elements no coberts i suma'l als elements situats a la intersecció de dues línies. Els elements coberts per una sola línia no varien. Torna al Pas 3.

Pas 5: Selecció de Zeros Òptims

Tria zeros independents a files i columnes de manera que cap agent ni tasca comparteixin assignació. Mapeja les posicions als costos de la matriu original per calcular el cost mínim.

3. Exemple Acadèmic Resol: 4 Treballadors × 4 Tasques

Segueix les reduccions successives d'una matriu 4×4 i comprova el resultat exacte del motor.

Worker / MachineTask 1 (T₁)Task 2 (T₂)Task 3 (T₃)Task 4 (T₄)
Treballador 1 (W₁)9278
Treballador 2 (W₂)6437
Treballador 3 (W₃)5818
Treballador 4 (W₄)7694

A. Reducció per Files (Restar Mínims de Fila)

Fila 1 mín = 2 → [7, 0, 5, 6] | Fila 2 mín = 3 → [3, 1, 0, 4] | Fila 3 mín = 1 → [4, 7, 0, 7] | Fila 4 mín = 4 → [3, 2, 5, 0]. Cada fila compta ja amb almenys un zero.

B. Reducció per Columnes (Restar Mínims de Columna)

Columna 1 té mínim 3 → [4, 0, 1, 0]. Les columnes 2, 3 i 4 ja tenen mínim 0 i queden intactes: Col 2 = [0, 1, 7, 2], Col 3 = [5, 0, 0, 5], Col 4 = [6, 4, 7, 0].

C. Cobertura de Línies i Independència

Els zeros resultants se situen a (W₁, T₂), (W₂, T₁), (W₂, T₃), (W₃, T₃), (W₄, T₁) i (W₄, T₄). El nombre mínim de línies per cobrir-los tots és exactament 4 (= n). Per tant, l'assignació òptima és immediata sense requerir el desplaçament del Pas 4.

Assigned WorkerMatched TaskOriginal Cost
Treballador 1 (W₁)Tasca 2 (T₂)2 €
Treballador 2 (W₂)Tasca 1 (T₁)6 €
Treballador 3 (W₃)Tasca 3 (T₃)1 €
Treballador 4 (W₄)Tasca 4 (T₄)4 €

Resultat del Cost Mínim Òptim

Cost Total Z* = 2 + 6 + 1 + 4 = 13 €. (Cada treballador rep una tasca exclusiva amb cost mínim global, coincidint exactament amb el resultat del calculador).

4. Errors Freqüents en Exercicis d'Assignació

⚠

Problemes de Maximització sense Invertir la Matriu

Si es vol maximitzar rendiment o beneficis, cal transformar la matriu restaurant cada valor de l'element màxim de la matriu original, o multiplicant totes les entrades per -1.

⚠

Matrius Rectangulars No Quadrades (m ≠ n)

El Mètode Hongarès exigeix una matriu quadrada. Si hi ha més tasques que treballadors (o a l'inrevés), cal afegir files o columnes fictícies amb costos 0 abans de reduir.

⚠

Operacions Incorrectes al Pas 4

Al Pas 4, el valor k es resta de les cel·les no cobertes i se suma únicament a les interseccions de dues línies. Les cel·les cobertes per una sola línia no es toquen.