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.

3
Tarefa 1Tarefa 2Tarefa 3
Trabalhador 1
Trabalhador 2
Trabalhador 3
Otimização Combinatória e Emparelhamento Bipartido

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)

Passo 1: Redução de Linhas

Encontre o menor valor de cada linha e subtraia-o de todos os elementos correspondentes. Isso cria pelo menos um zero em cada linha.

Passo 2: Redução de Colunas

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.

Passo 3: Cobertura Mínima por Linhas

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.

Passo 4: Modificação da Matriz

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.

Passo 5: Alocação dos Zeros Ótimos

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 / MachineTask 1 (T₁)Task 2 (T₂)Task 3 (T₃)Task 4 (T₄)
Trabalhador 1 (W₁)9278
Trabalhador 2 (W₂)6437
Trabalhador 3 (W₃)5818
Trabalhador 4 (W₄)7694

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 WorkerMatched TaskOriginal 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.