EAD350 II 2017 Aula8

Prévia do material em texto

EAD 350 
 Pesquisa Operacional 
Aula 8 
Prof. Hiroo Takaoka 
 
 
takaoka@usp.br 
FEA/USP 
Aviso! - Dia 10/10/2017 - Prova 
• Matéria 
– Elaboração do modelo matemático 
• Linear, linear inteira e linear binária 
– Resolução gráfica (2 variáveis) 
– Cálculo de preço sombra 
– Análise de sensibilidade 
– Análise do relatório do Solver 
• Prova em sala de aula (E-10), individual e sem consulta 
• Durante a prova os aparelhos eletrônicos devem ser 
desligados. Pode usar calculadora simples. 
Forma de Entrega do Trabalho 
• O trabalho deverá ser entregue via Moodle. 
• Grupo de até 3 alunos. 
• Apenas um aluno do grupo deverá enviar o trabalho. 
• Usar a primeira planilha para colocar as identificações (número 
USP e nome) completas dos membros do grupo inclusive a do 
aluno que vai enviar o trabalho. Chamar esta Planilha de Grupo. 
• Usar uma planilha para cada exercício como mostra a figura 
abaixo. 
 
 
Aula 8 - Objetivos 
• Revisar os conceitos da Programação Binária 
• Exercitar a modelagem de programação Binária 
• Exercitar a Programação Binária no Solver 
Programação Binária 
• A programação binária é um caso especial da programação inteira. 
• Quando algumas ou todas as variáveis de decisão em um problema 
só são permitidas a assumir valores 0 ou 1, tem-se o caso de 
programação binária. 
• O número de aplicações para este tipo de problema é muito grande. 
Sempre que se deseja indicar como solução um conjunto de decisões 
do tipo sim/não interdependentes pode-se aplicar a programação 
binária 
• Uma decisão do tipo sim/não pode ser modelada por uma variável 
binária, fazendo-se 1=sim e 0=não. 
Lembrando.... 
Programação Binária - Conceito 
• De n possibilidades selecionar não mais do que k alternativas. 
• Suponha xi = 0 ou 1 p/ i=1,...,n. 
• A restrição x1 + x2 + ... + xn < k significa que, no máximo, k 
alternativas de n possibilidades podem ser escolhidas. 
• De n possibilidades selecionar pelo menos k alternativas. 
• Suponha xi = 0 ou 1 p/ i=1,...,n. 
• A restrição x1 + x2 + ... + xn > k significa que, no mínimo, k 
alternativas de n possibilidades devem ser escolhidas. 
• De n possibilidades selecionar k alternativas. 
• Suponha xi = 0 ou 1 p/ i=1,...,n. 
• A restrição x1 + x2 + ... + xn = k significa que k alternativas de 
n possibilidades devem ser escolhidas. 
 
Lembrando.... 
Programação Binária - Conceito 
• Pode selecionar a alternativa m se antes a alternativa k tiver 
sido selecionada (Dependência). 
• Suponha xk = 0 ou 1 e xm = 0 ou 1. 
• A restrição xm < xk ou xm - xk < 0 impõe esta condição. 
• Deve selecionar a alternativa m se antes a alternativa k tiver 
sido selecionada (Obrigatoriedade). 
• Suponha xk = 0 ou 1 e xm = 0 ou 1. 
• A restrição xk < xm ou xk- xm < 0 impõe esta condição. 
• Negação. 
• Suponha xk = 0 ou 1 
• A negação de xk é representada como: (1 – xk). 
 
Lembrando.... 
Atividade 8 – Exercício 8A – Resolver em Excel 
HOJE – Entregar pelo Moodle 
Opções 
Retorno 
(VPL) 
A 
Capital Necessário por Ano 
1 2 3 4 5 
400 100 50 200 100 0 
B 700 300 200 100 100 100 
C 800 100 200 270 200 100 
D 1000 200 100 400 200 200 
Capital 
Disponível 
por Ano 
500 450 700 400 300 
Deseja-se selecionar projetos de investimentos que maximizem o 
retorno. Os retornos e as limitações de capital por ano para o 
investimento são dados no quadro abaixo: 
• Resolver com Solver. 
Projeto de Investimento 
A solução ótima do problema requer selecionar três investimentos A, B e C. 
Opções 
Retorno 
(VPL) 
A 
Capital Necessário por Ano 
1 2 3 4 5 
400 100 50 200 100 0 
B 700 300 200 100 100 100 
C 800 100 200 270 200 100 
D 1000 200 100 400 200 200 
Capital 
Disponível 
por Ano 
500 450 700 400 300 
Modifique e resolva o problema de projeto de investimento para levar em 
consideração a seguinte restrição adicional: 
• A diretoria decidiu que a opção D deve ser selecionada se a opção C for 
selecionada. 
 
Exercício 8A – Restrição Adicional 
Projeto de Investimento 
A solução ótima do problema requer selecionar os investimentos C e D. 
Uma empresa está considerando uma expansão por meio de uma nova 
fábrica em Los Angeles ou São Francisco (ou em ambas as cidades). 
Também está considerando construir depósitos, mas, somente na(s) 
cidade(s) em que também houver construído uma fábrica. A empresa pode 
investir até $ 10 milhões nesses projetos. 
A tabela a seguir mostra o VPL (Valor Presente Líquido), ou seja o resultado, 
e o investimento necessário para cada um dos projetos. 
 
 
 
 
 
Quais devem ser os projetos executados, considerando-se a restrição de 
capital e inter-relações entre as decisões (somente construir depósito em 
cidade em que for construída fábrica)? Resolver com Solver. 
 
Atividade 8 – Exercício 8B – Resolver em Excel 
HOJE – Entregar pelo Moodle 
Decisão
VPL (valor presente 
líquido) Investimento
Construir fábrica em Los Angeles $ 9 milhões $ 6 milhões
Construir fábrica em São Francisco $ 5 milhões $ 3 milhões
Construir depósito em Los Angeles $ 6 milhões $ 5 milhões
Construir depósito em São Francisco $ 4 milhões $ 2 milhões
Problema de Expansão 
A solução ótima do problema requer construir fábricas em Los Angeles e 
São Francisco. 
Atividade 8 – Exercício 8C – Resolver em Excel 
HOJE – Entregar pelo Moodle 
Investimentos 
Uma empresa está considerando um conjunto de projetos mostrado no 
quadro que segue. Deseja maximizar o retorno, investindo no máximo 25. 
Cada projeto está sujeito a seguintes condições 
Projeto Condição 
1 Nenhuma 
2 Pode somente se 1 for selecionado 
3 Pode somente se 2 for selecionado 
4 Deve se 2 for selecionado 
5 Pode somente se 1 não for selecionado 
6 Pode somente se 5 não for selecionado 
7 Nenhuma 
Projeto 1 2 3 4 5 6 7 
Investimento 6 2 4 8 5 1 4 
Retorno 15 5 20 2 9 20 3 
Investimento 
Resolver com Solver. Resposta: Investir nos projetos 1, 2, 3, 4, 6 e 7. 
Atividade 8– Exercício 8D – Resolver em Excel 
HOJE – Entregar pelo Moodle 
Rua F 
Rua G 
Rua H 
Rua J 
Rua K 
Rua B 
Rua C 
Rua E Rua D 
Rua A 
Rua I 
c8 c7 
c4 c5 
c1 c2 
c6 
c3 
Instalar o número mínimo de câmeras de segurança, contanto que 
cada uma das ruas seja atendida por no mínimo uma câmera. A figura 
abaixo mostra que o layout das ruas requer um máximo de oito 
localizações de câmera (ci). Quais câmeras devem ser instaladas? 
Câmeras 
Rua F 
Rua G 
Rua H 
Rua J 
Rua K 
Rua B 
Rua C 
Rua E Rua D 
Rua A 
Rua I 
c8 c7 
c4 c5 
c1 c2 
c6 
c3 
A solução ótima do 
problema requer instalar 
as quatro câmeras: 
C1, C2, C5 e C7. 
Câmeras 
Exercício 8D – Resultado