09 - metodo - hungaro

09 - metodo - hungaro

(Parte 1 de 3)

Análise e Técnicas de Algoritmos

Método Húngaro

Rohit Gheyi Tiago Massoni

Exemplo

Obra 1Obra 2Obra 3

Exemplo

Obra 1Obra 2Obra 3

Como alocar 3 tratores a 3 obras de modo que o custo seja minimizado?

Exemplo

Obra 1Obra 2Obra 3 problema de minimização

Como alocar 3 tratores a 3 obras de modo que o custo seja minimizado?

Força Bruta

Obra 1Obra 2Obra 3

Força Bruta

Obra 1Obra 2Obra 3

Problema

Como alocar tarefas de modo a minimizar/maximizar o custo?

Método Húngaro

• Problema de Otimização

• Origem

– H. Kuhn (1955)

• Criador do Algoritmo

– E. Egerváry e D. Konig (1931)

Matriz Custo

Obra 1Obra 2Obra 3

Sempre a matriz de custo deve ser NxN

Alocação de Tarefas

Obra 1Obra 2Obra 3

Podemos alocar só um elemento por cada linha e coluna. Ou seja, um trator por obra.

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.

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.

Ao diminuir as linhas e colunas, estamos comparando-as com valores relativos

Obra 1Obra 2Obra 3

subtraindo a menor entrada de cada linha

Obra 1Obra 2Obra 3

Obra 1Obra 2Obra 3 subtraindo a menor entrada de cada linha

Teorema de Köning

Obra 1Obra 2Obra 3

Se o número mínimo de traços que atravessam todos os zeros for n, não teremos dois zeros em cada linha/coluna

1 Algoritmo

Algoritmo

1.Para cada linha, subtraia a menor entrada de todas as entradas da mesma linha

Algoritmo

1.Para cada linha, subtraia a menor entrada de todas as entradas da mesma linha

2.Para cada coluna, subtraia a menor entrada de todas as entradas da mesma coluna

3.Risque um traço ao longo de linhas e colunas de tal modo que todas as entradas zero da matriz-custo sejam riscadas com um número mínimo de traços j.

(Parte 1 de 3)

Comentários