O que é o problema de atribuição?

O problema de atribuição é um clássico problema de otimização combinatória: dado um conjunto de trabalhadores e tarefas, cada um com um custo associado, encontre o emparelhamento um-para-um que minimize o custo total. Ele aparece naturalmente em agendamento, logística, alocação de recursos e pesquisa operacional — qualquer situação em que você precise corresponder dois grupos da forma mais eficiente possível.

O problema é resolvido com o algoritmo Húngaro (também chamado de algoritmo de Munkres), um método eficiente desenvolvido nos anos 1950. Diferentemente de abordagens de força bruta que devem avaliar cada permutação, o algoritmo Húngaro encontra a solução ótima em tempo polinomial, tornando-o prático mesmo para matrizes moderadamente grandes.

Descrição da ferramenta

Digite uma matriz de custos representando quanto custa atribuir cada trabalhador a cada tarefa, depois clique em Resolver para encontrar instantaneamente a atribuição ótima. A ferramenta destaca quais pares trabalhador-tarefa minimizam o custo total e exibe o resultado em uma tabela clara junto com o custo total ótimo.

Exemplos

Matriz de entrada (3 trabalhadores × 3 tarefas):

Tarefa 1 Tarefa 2 Tarefa 3
Trabalhador 1 400 150 400
Trabalhador 2 400 450 600
Trabalhador 3 300 225 300

Atribuições ótimas:

Trabalhador Tarefa Custo
Trabalhador 1 Tarefa 2 150
Trabalhador 2 Tarefa 1 400
Trabalhador 3 Tarefa 3 300

Custo total: 850

Recursos

  • Matriz editável — clique em qualquer célula ou cabeçalho de coluna para renomear trabalhadores, tarefas e custos diretamente na tabela
  • Tamanho configurável — suporta matrizes de 2×2 até 8×8
  • Resultados instantâneos — o algoritmo Húngaro é executado no navegador sem ida e volta ao servidor

Como funciona

A ferramenta usa o algoritmo de Munkres (Húngaro) para resolver o problema de atribuição de forma ótima. Ela constrói uma matriz de custos a partir de suas entradas, aplica uma série de etapas de redução de linhas e colunas, e iterativamente encontra um emparelhamento máximo de zeros até que uma atribuição ótima completa seja identificada. A complexidade de tempo é $O(n^3)$, onde $n$ é a dimensão da matriz.

Para matrizes não-quadradas (mais trabalhadores que tarefas ou vice-versa), o algoritmo preenche a matriz com zeros para que cada trabalhador e cada tarefa seja emparelhado.

Opções explicadas

  • Número de trabalhadores / linhas — controla quantas linhas aparecem na matriz de custos (2–8)
  • Número de tarefas / colunas — controla quantas colunas aparecem na matriz de custos (2–8)
  • Células da matriz de custos — digite o custo de atribuir um trabalhador específico a uma tarefa específica; qualquer valor numérico é aceito

Limitações

  • O tamanho da matriz é limitado a 8×8 (64 células)
  • O algoritmo minimiza o custo total; para maximizar (por exemplo, para matrizes de lucro), negue os valores antes de inseri-los
  • Valores de célula não-numéricos são tratados como zero