Pesquisa Operacional

Prévia do material em texto

PESQUISA 
OPERACIONAL
Aulas B2
segunda-feira, 26 de setembro de 2011
19:04
 Página 1 de Pesquisa Operacional 
Exemplo) Resolva o problema da designação:
O1 10 23 8 9
O2 4 5 6 7
O3 12 10 10 8
O4 6 4 9 7
D1 D2 D3 D4
Passo 2: Subtrair de cada linha o seu menor valor:
2 15 0 1 O menor valor da linha é 8
0 1 2 3 O menor valor da linha é 4
4 2 2 0 O menor valor da linha é 8
2 0 5 3 O menor valor da linha é 4
Passo 3: Subtrair de cada coluna o seu menor valor:
2 15 0 1
0 1 2 3
4 2 2 0
2 0 5 3
O menor 
valor da 
coluna é 0 
(Zero)
O menor 
valor da 
coluna é 0 
(Zero)
O menor 
valor da 
coluna é 0 
(Zero)
O menor 
valor da 
coluna é 0 
(Zero)
Passo 4: Designar para os "0s" (Zeros).
Passo 5: Calcular o Custo total:
 
Caso não esteja, deve-se equilibrar acrescentando uma 
coluna ou linha com todos os elementos iguais a 0 (Zero).
Passo 1: verificar se o sistema está equilibrado => nº de destinos = 
nº de origens.
Aula 01 - Método de Designação (pg1)
quinta-feira, 27 de outubro de 2011
21:48
 Página 2 de Pesquisa Operacional 
Exercício 1) Resolva o problema de designação onde o símbolo X indica a impossibilidade de designação.
O1 6 X 8
O2 4 9 3
O3 5 6 4
O4 8 10 12
D1 D2 D3
Passo 1: O sistema não está equilibrado, necessita o acréscimo de 1 destino (D).
O1 6 X 8 0
O2 4 9 3 0
O3 5 6 4 0
O4 8 10 12 0
D1 D2 D3 D4
Passo 2: Subtrair o menor valor de cada linha.
6 X 8 0 O menor valor da linha é 0 (Zero)
4 9 3 0 O menor valor da linha é 0 (Zero)
5 6 4 0 O menor valor da linha é 0 (Zero)
8 10 12 0 O menor valor da linha é 0 (Zero)
Passo 3: Subtrair o menor valor de cada coluna.
2 X - 6 5 0
0 3 0 0
1 0 1 0
4 4 9 0
O menor 
valor da 
linha é 0 
(Zero)
O menor 
valor da 
linha é 0 
(Zero)
O menor 
valor da 
linha é 0 
(Zero)
O menor 
valor da 
linha é 0 
(Zero)
Passo 4: Designa-se para os "0s" (Zeros). E exclui-se todos os "0s" da linha e coluna correspondentes à designação.
Continua.....---->
Aula 01 - Método de Designação (pg2)
quinta-feira, 27 de outubro de 2011
21:57
 Página 3 de Pesquisa Operacional 
Houve uma designação incompleta, pois somente foram designados 4 elementos, sedo que o necessário eram 4.
Passo 5: Para continuar a solução, deve-se riscar com o menor número de linhas possível a linha ou coluna 
correspondentes aos elementos designados (Zeros).
2 X - 6 5 0
0 3 0 0
1 0 1 0
4 4 9 0
Passo 6: Subtrair o menor valor não riscado de todos os elementos não riscados.
0 X - 8 3 0
0 3 0 0
1 0 1 0
2 2 7 0
Passo 7: Somar esse mesmo valor aos valores que estão no "cruzamento" das retas.
0 X - 8 3 0
0 3 0 2
1 0 1 2
2 2 7 0
Passo 8: Manter os demais valores.
Passo9: Subtrair o menor valor de cada linha dos demais valores.
Passo 10: Subtrair o menor valor de cada coluna dos demais valores.
Passo 11: Fazer uma nova designação:
0 X - 8 3 0
0 3 0 2
1 0 1 2
2 2 7 0
Houve uma completa designação.
Passo 12: Cálculo do Custo total.
 
Aula 01 - Método de Designação (pg3)
quinta-feira, 27 de outubro de 2011
22:11
 Página 4 de Pesquisa Operacional 
Transformar o problema em Minimização.
1. Multiplicar a Função Objetivo por (-1);
2. Transformar o quadro num quadro de perdas (valores complementares em relação a um valor fixo).
Existem duas opções:
Exemplo:
O quadro fornecido apresenta as eficiências de 4 vendedores em 4 regiões. Os potenciais de venda nas regiões são 
conhecidas. Designar um vendedor para cada região para maximizar o valor total das vendas.
Capacidade de cada vendedor atingir o potencial das vendas:
R1 R2 R3 R4
V1 70 60 80 90
V2 70 80 70 90
V3 60 90 60 70
V4 70 80 70 80
Resolução:
Multiplica-se os valores correspondentes a capacidade de cada região pelo seu potencial de venda:
R1 R2 R3 R4
V1 70 x 100 60 x 80 80 x 60 90 x 90
V2 70 x 100 80 x 80 70 x 60 90 x 90
V3 60 x 100 90 x 80 60 x 60 70 x 90
V4 70 x 100 80 x 80 70 x 60 80 x 90
Ficando da seguinte forma:
R1 R2 R3 R4
V1 70 48 48 81
V2 70 64 42 81
V3 60 72 36 63
V4 70 64 42 72
Define-se o valor máximo possível dentre as regiões, no caso, correspondente ao valor de 81. E subtrai-se desse 
valor em cada célula da tabela:
R1 R2 R3 R4
V1 81-70=11 81-48=33 81-48=33 81-81=0
V2 81-70=11 81-64=17 81-42=39 81-81=0
V3 81-60=21 81-72=9 81-36=45 81-63=18
V4 81-70=11 81-64=17 81-42=39 81-72=9
Potencial de Vendas (R$ x 10³)
R1 R2 R3 R4
100 80 60 90
Aula 02 - Problema da Designação: O caso da Maximização (pg1)
quinta-feira, 10 de novembro de 2011
21:53
 Página 5 de Pesquisa Operacional 
Continuação Exemplo...>
Passo 1: Com a nova definição, subtrai-se o menor valor de cada linha:
R1 R2 R3 R4
V1 11 33 33 0
V2 11 17 39 0
V3 21 9 45 18
V4 11 17 39 9
Passo 2: Com os valores novos, subtrai-se agora, o menor valor de cada coluna:
R1 R2 R3 R4
V1 11 33 33 0
V2 11 17 39 0
V3 12 0 36 9
V4 2 8 30 0
Passo 3: Designar os vendedores para as regiões onde o valor é 0 (Zero):
R1 R2 R3 R4
V1 9 33 3 0
V2 9 7 9 0
V3 10 0 6 9
V4 0 8 0 0
Passo 4: Cobrir as células escolhidas com o menor número possível de linhas:
R1 R2 R3 R4
V1 9 33 3 0
V2 9 7 9 0
V3 10 0 6 9
V4 0 8 0 0
Passo 5: Subtrair das células livres das linhas o menor valor contido nela (3):
Passo 6: Somar às células dos cruzamentos o mesmo valor (3):
R1 R2 R3 R4
V1 6 30 0 0
V2 6 4 6 0
V3 10 0 6 12
V4 0 8 0 3
R1 R2 R3 R4
V1 11 33 33 0
V2 11 17 39 0
V3 12 0 36 9
V4 2 8 30 0
R1 R2 R3 R4
V1 9 33 3 0
V2 9 7 9 0
V3 10 0 6 9
V4 0 8 0 0
Obs.: ao designar um vendedor para uma determinada 
região, não pode-se mais designar nenhum outro, assim 
também ao contrário, um vendedor não pode atuar em 
mais de uma região.
Aula 02 - Problema da Designação: O caso da Maximização (pg2)
quinta-feira, 10 de novembro de 2011
22:08
 Página 6 de Pesquisa Operacional 
PauloCézar
Highlight
PauloCézar
Highlight
PauloCézar
Highlight
PauloCézar
Sticky Note
17null
PauloCézar
Sticky Note
17
PauloCézar
Sticky Note
14
PauloCézar
Highlight
PauloCézar
Sticky Note
17null
PauloCézar
Sticky Note
Traços vermerlhos estão sobre os zeros, ficaram deslocados no PDF.
Continuação Exemplo...>
Passo 7: Nova escolha de designação:
R1 R2 R3 R4
V1 6 30 0 0
V2 6 4 6 0
V3 10 0 6 12
V4 0 8 0 3
Conclusão:
Vendedor Região Valor
1 3 48.000,00
2 4 81.000,00
3 2 72.000,00
4 1 70.000,00
Houve uma designação completa!
Máximo de Vendas:
 
Aula 02 - Problema da Designação: O caso da Maximização (pg3)
quinta-feira, 10 de novembro de 2011
22:25
 Página 7 de Pesquisa Operacional 
PauloCézar
Sticky Note
faltou multiplicar por 100!!!nullvalor correto é R$27.100.000,00