MÉTODO HUNGARO
1227 palavras
5 páginas
Análise e Técnicas de AlgoritmosMétodo Húngaro
Rohit Gheyi
Tiago Massoni
Exemplo
Obra 1
Obra 2
Obra 3
Trator 1
900
750
750
Trator 2
350
850
550
Trator 3
1250
950
900
2
Exemplo
Obra 1
Obra 2
Obra 3
Trator 1
900
750
750
Trator 2
350
850
550
Trator 3
1250
950
900
Como alocar 3 tratores a 3 obras de modo que o custo seja minimizado?
2
Exemplo
Obra 1
Obra 2
Obra 3
Trator 1
900
750
750
Trator 2
350
850
550
Trator 3
1250
950
900
Como alocar 3 tratores a 3 obras de modo que o custo seja minimizado? problema de minimização
2
Força Bruta
Obra 1
Obra 2
Obra 3
Trator 1
900
750
750
Trator 2
350
850
550
Trator 3
1250
950
900
3
Força Bruta
Obra 1
Obra 2
Obra 3
Trator 1
900
750
750
Trator 2
350
850
550
Trator 3
1250
950
900
n.(n-1)....1 = n!
3
Problema
Como alocar tarefas de modo a minimizar/maximizar o custo?
4
Método Húngaro
• Problema de Otimização
• Origem
– H. Kuhn (1955)
• Criador do Algoritmo
– E. Egerváry e D. Konig (1931)
– Teorema da alocação ótima
– Teorema de Köning
5
Matriz Custo
Obra 1
Obra 2
Obra 3
Trator 1
900
750
750
Trator 2
350
850
550
Trator 3
1250
950
900
Sempre a matriz de custo deve ser NxN
6
Alocação de Tarefas
Obra 1
Obra 2
Obra 3
Trator 1
900
750
750
Trator 2
350
850
550
Trator 3
1250
950
900
Podemos alocar só um elemento por cada linha e coluna. Ou seja, um trator por obra.
7
Teorema da Alocação
Ótima
Se um número real é somado ou subtraído de todas as entradas de uma linha ou coluna, então uma alocação ótima para a matriz resultante é também uma alocação ótima para a matriz original.
8
Teorema da Alocação
Ótima
Se um número real é somado ou