Calculadora do Método Húngaro (Problema de Atribuição)
Resolva problemas de atribuição passo a passo através do algoritmo Húngaro, com redução de linhas/colunas e cobertura ótima de zeros.
| Tarefa 1 | Tarefa 2 | Tarefa 3 | |
|---|---|---|---|
| Trabalhador 1 | |||
| Trabalhador 2 | |||
| Trabalhador 3 |
O Problema de Atribuição e o Algoritmo Húngaro: Guia Acadêmico
Formalização matemática do algoritmo de Kuhn-Munkres (Método Húngaro) para alocação ótima e minimização de custos operacionais.
1. Qual problema o Modelo de Atribuição resolve?
O Problema de Atribuição é um modelo de otimização combinatória em que n recursos (trabalhadores, máquinas) devem ser designados a n tarefas de maneira estritamente bijetiva (um para um). Dada a matriz de custos C onde cᵢⱼ representa o custo de alocar o trabalhador i à tarefa j, busca-se minimizar ∑ cᵢⱼ xᵢⱼ com a restrição de que cada agente e cada tarefa recebam exatamente uma alocação (xᵢⱼ ∈ {0, 1}). O Método Húngaro resolve este problema em tempo fortemente polinomial O(n³).
2. Os 5 Passos do Algoritmo Húngaro (Kuhn-Munkres)
Encontre o menor valor de cada linha e subtraia-o de todos os elementos correspondentes. Isso cria pelo menos um zero em cada linha.
Na matriz resultante, encontre o menor valor de cada coluna e subtraia-o de todos os elementos da respectiva coluna, assegurando zeros em todas as colunas.
Trace o número mínimo de retas horizontais e verticais para cobrir todos os zeros. Se o número de retas for igual a n, a atribuição ótima é possível (vá para o Passo 5). Se for menor que n, avance para o Passo 4.
Identifique o menor elemento não coberto k. Subtraia k de todas as células descobertas e adicione k às interseções de duas retas. Células cobertas por apenas uma reta não se alteram. Retorne ao Passo 3.
Selecione zeros independentes de forma que nenhum agente ou tarefa compartilhe alocação. Consulte a matriz original para somar os custos mínimos.
3. Exemplo Acadêmico Resolvido: 4 Trabalhadores × 4 Tarefas
Acompanhe as reduções da matriz 4×4 e confirme o resultado do motor de cálculo.
| Worker / Machine | Task 1 (T₁) | Task 2 (T₂) | Task 3 (T₃) | Task 4 (T₄) |
|---|---|---|---|---|
| Trabalhador 1 (W₁) | 9 | 2 | 7 | 8 |
| Trabalhador 2 (W₂) | 6 | 4 | 3 | 7 |
| Trabalhador 3 (W₃) | 5 | 8 | 1 | 8 |
| Trabalhador 4 (W₄) | 7 | 6 | 9 | 4 |
A. Redução de Linhas (Subtrair Mínimos de Linha)
Linha 1 mín = 2 → [7, 0, 5, 6] | Linha 2 mín = 3 → [3, 1, 0, 4] | Linha 3 mín = 1 → [4, 7, 0, 7] | Linha 4 mín = 4 → [3, 2, 5, 0]. Cada linha possui ao menos um zero.
B. Redução de Colunas (Subtrair Mínimos de Coluna)
Coluna 1 tem mínimo 3 → [4, 0, 1, 0]. As colunas 2, 3 e 4 já possuem zeros e mantêm-se: Col 2 = [0, 1, 7, 2], Col 3 = [5, 0, 0, 5], Col 4 = [6, 4, 7, 0].
C. Cobertura por Retas e Independência
Os zeros resultantes estão em (W₁, T₂), (W₂, T₁), (W₂, T₃), (W₃, T₃), (W₄, T₁) e (W₄, T₄). O número mínimo de retas para cobrir todos os zeros é exatamente 4 (= n). A solução ótima é imediata.
| Assigned Worker | Matched Task | Original Cost |
|---|---|---|
| Trabalhador 1 (W₁) | Tarefa 2 (T₂) | R$ 2 |
| Trabalhador 2 (W₂) | Tarefa 1 (T₁) | R$ 6 |
| Trabalhador 3 (W₃) | Tarefa 3 (T₃) | R$ 1 |
| Trabalhador 4 (W₄) | Tarefa 4 (T₄) | R$ 4 |
Resultado do Custo Mínimo Ótimo
Custo Total Z* = 2 + 6 + 1 + 4 = R$ 13. (Cada trabalhador recebe uma tarefa exclusiva de forma a minimizar o custo global).
4. Erros Frequentes em Exercícios de Atribuição
Problemas de Maximização sem Inversão
Se o objetivo for maximizar produção ou lucro, converta a matriz subtraindo cada elemento do maior valor da matriz original, ou multiplique todos os termos por -1.
Matrizes Retangulares (m ≠ n)
O algoritmo exige matriz quadrada. Caso existam mais tarefas que trabalhadores (ou vice-versa), insira linhas ou colunas fictícias com custo zero antes de iniciar as reduções.
Aplicação Incorreta do Passo 4
No Passo 4, subtraia k apenas dos elementos não cobertos e adicione k somente às interseções de retas. Elementos cobertos por uma única reta permanecem intocados.