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.
| Tasca 1 | Tasca 2 | Tasca 3 | |
|---|---|---|---|
| Treballador 1 | |||
| Treballador 2 | |||
| Treballador 3 |
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)
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.
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.
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.
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.
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 / Machine | Task 1 (T₁) | Task 2 (T₂) | Task 3 (T₃) | Task 4 (T₄) |
|---|---|---|---|---|
| Treballador 1 (W₁) | 9 | 2 | 7 | 8 |
| Treballador 2 (W₂) | 6 | 4 | 3 | 7 |
| Treballador 3 (W₃) | 5 | 8 | 1 | 8 |
| Treballador 4 (W₄) | 7 | 6 | 9 | 4 |
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 Worker | Matched Task | Original 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.