O Método Húngaro é um é um método matemático utilizado para resolver problemas de alocação ou atribuição ótima. Desenvolvido pelo matemático húngaro Harold Kuhn em 1955, o método fornece uma solução eficiente para problemas onde é necessário alocar n tarefas para n agentes (ou recursos) de forma a minimizar o custo total ou maximizar a eficiência. O método é aplicado sobre a matriz custos \(C\).
O método é especialmente útil em situações onde precisamos encontrar a combinação ótima (com o menor custo ou o maior benefício) entre recursos e tarefas, garantindo que cada recurso seja alocado a exatamente uma tarefa e cada tarefa tenha exatamente um recurso alocado.
Vamos tratar aqui apenas do caso de minimização de custos. O caso de maximização quando a matriz custos é \(C\) é modificado para minimizar a matriz custos \(-C\).
Suponha que temos 3 trabalhadores (A, B, C) e 3 tarefas (1, 2, 3). A matriz de custos (em horas) é:
| Tarefa 1 | Tarefa 2 | Tarefa 3 | |
|---|---|---|---|
| Trabalhador A | 10 | 5 | 8 |
| Trabalhador B | 7 | 6 | 9 |
| Trabalhador C | 8 | 7 | 6 |
Matriz de custos original:
\[ C = \begin{bmatrix} 10 & 5 & 8 \\ 7 & 6 & 9 \\ 8 & 7 & 6 \end{bmatrix} \]
Onde cada elemento \(c_{ij}\) representa o custo do trabalhador \(i\) realizar a tarefa \(j\).
Aplicando o Método Húngaro, encontraríamos a atribuição ótima que minimiza o tempo total:
Tempo total: 18 horas (menor possível para esta configuração)
O resultado fundamental do Método Húngaro é apresentado a seguir:
Teorema: Se um número é adicionado ou subtraído de todas as entradas de uma linha ou coluna de uma matriz-custo, então uma alocação ótima para a matriz resultante é também uma alocação ótima para a matriz custo original.
Este teorema justifica o método Húngaro que consiste em transformar uma matriz-custo qualquer em uma matriz com algumas entradas nulas.
Considere uma matriz-custo de dimensão n. Trace retas cobrindo linhas e colunas que contenham entradas zero usando o menor número de retas possível.
Se o número mínimo é n, então uma alocação ótima de zeros é possível e está terminado o processo.
Caso contrário, continue com o processo de ajuste.
Zeros Estrelados representam atribuições candidatas na solução atual:
Diferença para zeros primados (P): Zeros primados são candidatos temporários identificados durante o processo de melhoria da solução.
O Método Húngaro é um algoritmo de ordem polinomial que resolve o Problema de Alocação em tempo O(n³). Foi desenvolvido por Harold Kuhn em 1955 e aperfeiçoado por James Munkres em 1957.
Dada uma matriz de custos n×n, encontrar a alocação ótima (um elemento único por linha e coluna) que minimize o custo total.
O teorema acima garante que podemos subtrair constantes das linhas e colunas sem alterar a solução ótima, permitindo criar zeros para facilitar a atribuição.
O(n³)
n = dimensão da matrizO(n²)
Armazenamento da matrizSempre
Garante solução ótimaClique em um exemplo para carregar a matriz: