Designação - Metodo Hungaro

Designação - Metodo Hungaro

Campus - Mossoró Profª Adricia Fonseca Mendes

Designação

Suponha n trabalhadores a distribuir por n tarefas de forma a que cada trabalhador execute apenas uma tarefa, e que cada tarefa seja executada apenas por um trabalhador.

Conhecendo os custos da realização de cada tarefa por cada trabalhador:

•designar os trabalhadores às tarefas de forma a minimizar os custos

O problema de designação é um problema de dimensão (n x n), em que:

•as variáveis de decisão xij podem tomar valores 0 ou 1; 2

Problema: alocação de recursos disponíveis para atividades de interesse de forma a otimizar alguma medida de efetividade do sistema.

Exemplos de aplicações

O Problema de designação envolve a determinação de n! possíveis soluções.

•para um problema com 5 trabalhadores e 5 tarefas o número de soluções possíveis é igual a 5 ! = 120.

•para um problema com 10 trabalhadores e 10 tarefas o número de soluções é igual a 10 ! = 3 628 800.

Obter a solução ótima por tentativa é DIFÍCIL !

Formulação

j ij x1

Minimizar sujeito a: cada trabalhador é designado a uma só tarefa

i ij x1 cada tarefa é executada apenas por um trabalhador ijij xcC

Método Húngaro

Início: Redução da Matriz de Custos. 1º. Subtrair aos elementos de cada coluna da matriz de custos o mínimo dessa coluna. 2º. Na matriz resultante, subtrair a cada linha o respectivo mínimo.

Iteração: 1º. Desenhar o número mínimo de traços que cobrem todos os zeros da matriz 2º. Critério de parada: o número mínimo de traços é igual a n?.

Sim – enquadrar n zeros, um por linha e um por coluna, a solução é ótima. FIM. Não – passar a 3.

3 º. Redução da matriz de custos.

•Determinar o menor valor não riscado .

•Subtrair a todos os elementos não riscados e somar a todos os elementos duplamente riscados. •Considerar de novo todos os zeros livres e voltar a 1 (Iteração)

Início: Redução da Matriz de Custos

12 3 4 5
12 3 4 5

1º: Subtrair o menor elemento de cada coluna de todos os elementos dessa coluna

13 - 4.5 = 8.5 menor elemento da coluna 1

Início: Redução da Matriz de Custos

1 12 2 3 3 4 4 5 5

2º: Subtrair o menor elemento de cada linha de todos os elementos dessa linha

12 3 4 5

Existe empate na escolha do menor elemento da linha 1 (igual a 0.5). Nas linhas restantes o mínimo é zero, sendo que as linhas restantes não vão ser alteradas

7 - 0.5 = 6.5

Iteração: Critério de parada

12 3 4 5

1º. Desenhar o número mínimo de traços que cobrem todos os zeros da matriz.

2º. Critério de parada: o número mínimo de traços é igual a 5?. Não – passar a 3.

Iteração: Redução da Matriz de Custos.

12 3 4 5
12 3 4 5

1º. min {elementos da submatriz dos elementos não riscados } = 1.5

4º. Os restantes elementos não são alterados.

2º. Subtrair 1.5 a todos os elementos não riscados.

3º. Somar 1.5 aos elementos na intersecção dos traços.

Iteração: Critério de parada.

1º. Desenhar o número mínimo de traços que cobrem todos os zeros da matriz.

34 5

2º. Critério de parada: o número mínimo de traços é igual a 5?.

Sim – enquadrar 5 zeros, um por linha e um por coluna, a solução é ótima. FIM

12 3 4 5

Matriz inicial de custos

solução ótima é : x13 = 1 , x24 = 1, x35 = 1, x41 = 1 , x52 = 1 com um custo total : 9 + 5 + 5.5 + 4.5 + 9.5 = 3.5

Problema de maximização - método húngaro.

Multiplicar todos os elementos da matriz C por (-1)

Identificar o elemento de maior valor em módulo

Somar o elemento de maior módulo a todos os elementos da nova matriz de custos (já multiplicada por (-1))

Resolver como se fosse de minimização

Resolver o problema pelo método húngaro.

O presidente de uma empresa está estudando a transferência de quatro diretores para quatro locais de trabalho diferentes. Foram feitas estimativas dos custos envolvidos na transferência de cada diretor para cada novo local de trabalho. Estes custos são dados a seguir:

Obtenha a designação de diretores para locais de trabalho de menor custo.

1.O Diretor de uma escola deseja inscrever quatro alunos num concurso de matemática que engloba os seguintes assuntos: Álgebra, Cálculo I, Linguagens de Computação e Cálculo I.

Somente um aluno pode ser inscrito em cada assunto e nenhum aluno pode ser inscrito em mais de um assunto porque as provas do concurso ocorrerão simultaneamente. Para isso ele seleciona seus quatro melhores alunos, A, B, C, D e lhes aplica testes cobrindo as quatro áreas do concurso. O quadro abaixo indica o número de pontos que cada aluno obteve em cada uma das áreas no exame simulado.

Qual aluno deve ser selecionado para cada um dos assuntos do concurso, sendo que o Diretor resolveu que o aluno B não deverá fazer a prova de Cálculo I?

2Uma empresa vende produtos em quatro regiões e possui quatro

17 vendedores que devem atender quatro regiões diferentes, sendo um vendedor para cada região. As regiões não são igualmente ricas e apresentam o seguinte potencial de venda (em $):

Os vendedores por outro lado, não são igualmente hábeis e as suas eficiências, que refletem a capacidade de atingir o mercado potencial da região, são dados pelo quadro que se segue:

Pede-se determinar, empregando o modelo da designação e o algoritmo húngaro, como enviar os vendedores às regiões para que o volume de vendas total das quatro regiões seja o maior possível.

3. Uma Empresa necessita desenvolver um plano de produção para iniciar a fabricação de três novos produtos. A Empresa dispõe de cinco máquinas e apenas três destas deverão ser escolhidas para manufaturar os novos itens, sendo um produto por máquina. Os custos de produção e os custos de distribuição para todas as combinações produto-máquina são fornecidos a seguir: Custos de Produção ($/unidade):

Custos de Distribuição ($/unidade):

De acordo com os planos atuais é necessário manter uma determinada produção anual por item para haver demanda pelos preços unitários planejados, estes dados são fornecidos adiante:

Formule um modelo da designação para tratar este problema e resolva-o pelo Algoritmo Húngaro.

Comentários