Designacao Metodo Hungaro .pdf

Prévia do material em texto

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 
3 
 O Problema de designação envolve a determinação de 
n! possíveis soluções. 
 
Exemplo: 
•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 ! 
 
4 
Formulação 
5 



n
j
ijx
1
1
1,0ijx
ni ,...,2,1 , 
nj ,...,2,1 , 
Minimizar 
sujeito a: 
 cada trabalhador é 
designado a uma só 
tarefa 
nj ,...,2,1 , 



n
i
ijx
1
1
cada tarefa é 
executada apenas 
por um trabalhador 
ni ,...,2,1 , 



n
ji
ijijxcC
1,
Método Húngaro 
6 
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 
7 
 1 2 3 4 5 
1 
2 
3 
4 
5 
13 7 0.5 0.5 6.5 
11.5 
7.5 
0 
8.5 
8.5 2 
7.5 6 
0 
1.5 
5.5 
0 
0 
6 
12.5 
7 
5 
0 
7.5 
12 
 1 2 3 4 5 
1 1 
2 
3 
4 
5 
17.5 15 9 5.5 12 
16 
12 
4.5 
13 
16.5 10.5 
15.5 14.5 
8 
9.5 
14 
8.5 
5 
11 
17.5 
12 
10.5 
5.5 
13 
17.5 
1º: Subtrair o menor 
elemento de cada coluna 
de todos os elementos 
dessa coluna 
 17.5 - 4.5 = 13 
 16 - 4.5 = 11.5 
 12 - 4.5 = 7.5 
 4.5 - 4.5 = 0 
 13 - 4.5 = 8.5 
menor elemento da coluna 1 
Início: Redução da Matriz de Custos 
8 
 1 1 2 2 3 3 4 4 5 5 
1 1 
2 2 
3 3 
4 4 
5 5 
12.5 6.5 0 0 6 
11.5 
7.5 
0 
8.5 
8.5 2 
7.5 6 
0 
1.5 
5.5 
0 
0 
6 
12.5 
7 
5 
0 
7.5 
12 
2º: Subtrair o menor 
elemento de cada linha de 
todos os elementos dessa 
linha 
 1 2 3 4 5 
1 
2 
3 
4 
5 
13 7 0.5 0.5 6.5 
11.5 
7.5 
0 
8.5 
8.5 2 
7.5 6 
0 
1.5 
5.5 
0 
0 
6 
12.5 
7 
5 
0 
7.5 
12 
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 
 13 - 0.5 = 12.5 
 7 - 0.5 = 6.5 
 0.5 - 0.5 = 0 
6.5 - 0.5 = 6 
Iteração: Critério de parada
9 
 1 2 3 4 5 
1 1 
2 
3 3 
4 4 
5 5 
12.5 6.5 0 0 6 
11.5 
7.5 
0 
8.5 
8.5 2 
7.5 6 
0 
1.5 
5.5 
0 
0 
6 
12.5 
7 
5 
0 
7.5 
12 
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. 
10 
 1 2 3 4 5 
1 
2 
3 3 
4 4 
5 
12.5 6.5 0 0 6 
11.5 
7.5 
0 
8.5 
8.5 2 
7.5 6 
0 
1.5 
5.5 
0 
0 
6 
12.5 
7 
5 
0 
7.5 
12 
 
3 
4 
12.5 6.5 0 0 6 
11.5 
7.5 
0 
8.5 
8.5 2 
7.5 6 
0 
1.5 
5.5 
0 
0 
6 
12.5 
7 
5 
0 
7.5 
12 
11.5 
7.5 
0 
8.5 
8.5 2 
7.5 6 
0 
1.5 
5.5 
0 
0 
6 
12.5 
7 
5 
0 
7.5 
12 
 1 2 3 4 5 
1 
2 
3 
4 
5 
11 5 0 0 4.5 
10 
7.5 
0 
7 
7 2 
7.5 7.5 
0 
0 
7 
0 
0 
7.5 
14 
7 
3.5 
0 
7.5 
10.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. 
11 
1º. Desenhar o número mínimo de traços que cobrem todos os 
 zeros da matriz. 
 1 2 3 4 5 
1 
2 
3 
4 
5 
11 5 0 0 4.5 
10 
7.5 
0 
7 
7 2 
7.5 7.5 
0 
0 
7 
0 
0 
7.5 
14 
7 
3.5 
0 
7.5 
10.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 
 1 2 3 4 5 
1 
2 
3 
4 
5 
17.5 15 9 5.5 12 
16 
12 
4.5 
13 
16.5 10.5 
15.5 14.5 
8 
9.5 
14 
8.5 
5 
11 
17.5 
12 
10.5 
5.5 
13 
17.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 = 33.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 
 
 
13 
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 custosenvolvidos 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. 
 
 
14 
15 
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 II. 
 
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. 
 
16 
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 II? 
 
17 
2. Uma empresa vende produtos em quatro regiões e possui quatro 
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 $): 
 Região I: 60.000 
 Região II: 50.000 
 Região III: 40.000 
 Região IV: 30.000 
 
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: 
 
18 
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. 
 
19 
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): 
 
20 
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.