Método Húngaro

Método Húngaro – por Bruno Henrique da Silva

Introdução
Problemas cotidianos de transporte e alocação de tarefas podem ser resolvido por meio da programação linear, mas existe um algoritmo, chamado de Método Húngaro, que torna essa solução mais fácil e viável.

Situação 1 – transporte de produtos
Imagine uma grande rede de produtos esportivos. Ela tem diversos barracões de estoque, situados em m lugares diferentes (origens). Esses produtos devem ser distribuídos em suas n lojas diferentes espalhadas por todo o estado (destino). Sendo conhecido o custo de transporte de cada origem para cada destino, e de que é possível enviar esses produtos de qualquer origem para qualquer destino, deseja-se obter o menor custo possível nessa operação de distribuição de produtos.

Situação 2 – escalação ideal do time de futebol
Tirando-se o goleiro, cada jogador (chamado jogador de linha) pode jogar em cada uma das 10 posições diferentes, tudo dependendo do seu desempenho dentro de campo. Então o técnico é obrigado a escalar cada jogador na sua melhor posição de embate. Para tal, pode realizar vários treinos revezando os jogadores de posição, e dar uma nota de 0 a 15 para cada posição que o jogador ocupa.

O Método Húngaro
Esse método consiste em determinar de um custo de alocação, uma alocação ótima de tarefas. Segue o passo-a-passo:
1 – Subtraia a menor entrada de cada linha de todas as entradas da mesma linha.
2 – Subtraia a menor entrada de cada coluna de todas as entradas da mesma coluna.
3 – Risque, com o menor número possível de traços, as linhas e colunas que contenham zeros, a fim de riscar todos os zeros.
4 – Teste da Otimalidade: se o número de traços for exatamente a ordem da matriz, terminou o procedimento, senão, continue o próximo passo.
5 – Determine a menor entrada que não tenha sido riscada. Subtraia essa entrada de todas as entradas não riscadas e a some a todas as entradas riscadas simultaneamente por traços verticais e horizontais. Volte ao