Solucionador de Problemas de Atribuição

O que é o problema de atribuição?

O problema de atribuição é um problema fundamental de otimização combinatória: dados n agentes e n tarefas com uma matriz de custos C, encontrar uma atribuição um-para-um que minimize o custo total.

O algoritmo húngaro (método Kuhn-Munkres, 1955) resolve em O(n³). Reduz iterativamente a matriz por subtração de linhas e colunas, depois encontra a atribuição ótima por caminhos aumentantes.

Para matrizes retangulares, linhas ou colunas fictícias com custo 0 são adicionadas. Agentes ou tarefas não atribuídos são reportados separadamente.

Formula: Minimizar Σ C[i][σ(i)] para todo i sujeito a σ ser uma permutação (mapeamento um-para-um) Passos do método húngaro: 1. Subtrair os mínimos das linhas 2. Subtrair os mínimos das colunas 3. Cobrir os zeros com o mínimo de linhas 4. Ajustar a matriz e repetir até o ótimo

Exemplo de cálculo

Matriz de custos: [[9,2,7],[6,4,3],[5,8,1]]. Redução por linhas → [[7,0,5],[3,1,0],[4,7,0]]. Redução por colunas → [[4,0,5],[0,1,0],[1,7,0]]. Os zeros permitem uma tarefa por agente: Agente 1→Tarefa 2 (custo 2), Agente 2→Tarefa 1 (custo 6), Agente 3→Tarefa 3 (custo 1). Custo total = 9 — menor que o pareamento tentador Agente 2→Tarefa 3, Agente 3→Tarefa 1 (10).

Quando usar esta calculadora

• Um supervisor de produção atribuindo trabalhadores a máquinas para minimizar o tempo total de processamento ou o custo
• Um gerente de projetos alocando membros da equipe a tarefas com base na correspondência de habilidades e nas estimativas de esforço
• Um coordenador de logística atribuindo veículos de entrega a rotas para minimizar a distância total percorrida
• Um administrador universitário programando salas de exame para disciplinas a fim de minimizar conflitos ou distância de deslocamento

Erros comuns a evitar

• Inserir custos de forma inconsistente — todos os valores da matriz de custos devem usar a mesma unidade (dinheiro, horas, distância); misturar unidades produz atribuições sem sentido
• Esquecer de alternar entre os modos de minimização e maximização — se você está atribuindo por lucro ou preferência (quanto maior, melhor), selecione maximizar; para custo ou tempo (quanto menor, melhor), selecione minimizar
• Usar atribuição para problemas com múltiplas atribuições por agente — o algoritmo húngaro atribui cada agente a exatamente uma tarefa; se os agentes podem assumir várias tarefas, use um modelo diferente
• Não tratar pareamentos inviáveis — se certas combinações agente-tarefa são impossíveis, defina seu custo como um número muito grande em vez de deixá-las como zero

Como interpretar os resultados

• O custo total representa o ótimo global — nenhuma outra atribuição um-para-um pode alcançar um total menor (ou maior, no caso de maximização)
• Se algumas linhas ou colunas aparecem como não atribuídas, há mais agentes do que tarefas (ou vice-versa) — esses agentes/tarefas permanecem livres
• Compare o total ótimo com a atribuição ingênua (p. ex., linha 1 para coluna 1) para ver quanta melhoria o algoritmo proporciona

Normas e referências relacionadas

• Kuhn, H. W. (1955), 'The Hungarian Method for the Assignment Problem', Naval Research Logistics Quarterly — publicação original do algoritmo
• Munkres, J. (1957), 'Algorithms for the Assignment and Transportation Problems', Journal of the SIAM — o refinamento que estabeleceu a execução em tempo polinomial
• Burkard, Dell'Amico & Martello (2009), Assignment Problems (SIAM) — referência moderna abrangente sobre modelos e algoritmos de atribuição

Perguntas frequentes

Pode maximizar?

Sim. Negar todos os custos ou subtrair do máximo, depois resolver a minimização. A atribuição ótima é a mesma.

E se o número de trabalhadores e tarefas for diferente?

O algoritmo preenche a dimensão menor com entradas fictícias (custo 0). Atribuições fictícias indicam trabalhadores ou tarefas não atribuídos.

O problema de atribuição pode lidar com restrições do mundo real, como habilidades ou disponibilidade dos trabalhadores?

Não diretamente na formulação básica. No entanto, você pode codificar atribuições inviáveis definindo seu custo como um número muito grande (p. ex., 999999), impedindo efetivamente que o algoritmo as selecione. Para restrições complexas, considere solvers de programação linear inteira.