EAD350 Aula06 2014 2sem

Prévia do material em texto

EAD 350
 Pesquisa Operacional
Aula 06
Prof. Cesar Alexandre de Souza
calesou@usp.br
FEA/USP
Essa é uma aula de autoinstrução.
Leia atentamente os slides e realize os exemplos e atividades como solicitado
Boa aula!!
Aviso! - Dia 30/09/14 - Prova
Cai: elaboração do modelo matemático, resolução gráfica, análise de sensibilidade, preço sombra e elaboração e análise dos resultados no Solver do Excel, incluindo relatório de análise de sensibilidade
Prova em sala de Aula, Individual e sem consulta
Próxima aula (23/09) no lab.info e Prova (30/09) na sala de aula
Aula 06 - Objetivos
Apresentar a diferença entre a Programação Linear e a Programação Linear Inteira
Apresentar como modelar a Programação Linear Inteira no Solver do Excel
Apresentar os conceitos da Programação Binária
Apresentar como modelar a Programação Binária no Solver do Excel
Exercitar a Programação Binária no Solver por meio das atividades 6a e 6b
Aula 06 - Agenda
Resolução da atividade 5a (Gasolinas)
Resolução da atividade 5b (escala de atendimento)
Programação Linear Inteira
Conceituação
Como realizar no Excel
Programação Binária
Conceituação
Como realizar no Excel
Atividade 6a e 6B (programação binária)
Aula 06 - Instruções
Essa é uma aula realizada por meio de auto-instrução (ensino à distância), com tempo estimado de 100 minutos para sua realização
Leia atentamente os slides dessa apresentação, bem como analise com cuidados as planilhas de gabarito das atividades
Para o item “Programação Linear Inteira”, use a planilha “Ativ5b-gabarito-2014-2sem.xlxs” para acompanhar o desenvolvimento da solução
Para o item “Programação Linear Inteira”, desenvolva nova planilha para a solução do exemplo apresentado
Desenvolva em duplas as planilhas de solução para as atividades 6a e 6b e envie pelo Erudito até sexta 19/9, 23h59m
Resolução das Atividades 5a e 5b
Petróleo
Máxima
quantidade
disponível 
Custo
unitário
A
100 
6
B
200 
3
Gasolina
Mínima
% A
requerida 
Preço de
venda
unitária
1
60
8
2
30
5
Deseja-se saber a quantidade de cada gasolina que deve ser fabricada de tal maneira que o lucro seja máximo.
Elaborar o Modelo matemático (pode ser na própria planilha)
Elaborar o Modelo no Excel e Resolver com o Solver – Gerar o Relatório de Sensibilidade 
a) Uma refinaria fabrica dois tipos de gasolina (1 e 2) a partir de dois tipos de petróleo bruto (A e B).
Os custos, os preços de venda e matéria-prima
para fabricar as gasolinas são:
Ativ 5a – Resolução
PA
PB
G1
G2
xA1+xA2 < 100
xB1+xB2 < 200
xA1+xB1
xA2+xB2
Mín 60%
Mín 30%
XA1
XA2
XB1
XB2
Total G1:
Total G2:
Total PB:
Total PA:
(Preço: 8)
(Preço: 5)
(Custo: 6)
(Custo: 3)
xA1: quantidade de petróleo A p/ produzir gasolina 1
xA2: quantidade de petróleo A p/ produzir gasolina 2
xB1: quantidade de petróleo B p/ produzir gasolina 1
xB2: quantidade de petróleo B p/ produzir gasolina 2
Variáveis decisórias
Ativ 5a – Resolução
Função Objetiva
Max L= 8(xA1+xB1) + 5(xA2+xB2)
 - 6(xA1+xA2) - 3(xB1+xB2)
 → Max L= 2 xA1 - 1xA2 + 5xB1 + 2xB2
Restrições
xA1 + xA2 < 100
xB1 + xB2 < 200
xA1 / (xA1 + xB1) > 0,6 → 0,4 xA1- 0,6 xB1 > 0
xA2 / (xA2 + xB2) > 0,3 → 0,7 xA2 - 0,3 xB2 > 0
xij > 0
Ativ 5a – Resolução : Modelo Matemático
Ativ 5a – Resolução – Planilha Excel (veja arquivo no Erudito)
B) O supervisor do centro de suporte da empresa Alpha precisa elaborar a escala de seu pessoal. O centro de suporte fica aberto das 8 da manhã até meia-noite. O supervisor monitorou as quantidades de chamados por período e determinou que o seguinte número de analistas seriam necessários por período
Podem ser contratados dois tipos de analistas: em tempo integral e estagiários tempo parcial. Os analistas em tempo integral trabalham por oito horas seguidas em três tipos de turno (8h às 16h, 12h às 20h ou 16h às 00h) e recebem $14 por hora. Os estagiários em tempo parcial podem ser contratados para os períodos de 4 horas indicados na tabela anterior e recebem $12 por hora.
Durante qualquer período, deve haver pelo menos dois analistas tempo integral para cada estagiário em tempo parcial.
Como atender a esses requisitos com o custo mínimo? 
Elaborar e escrever o modelo matemático (na própria planilha)
Elaborar a o modelo em Excel e resolver com o Solver – gerar o relatório de análise de sensibilidade
Ativ 5b – Resolução
Período do Dia
Estagiários
Analistas Manhã
Analistas Tarde
Analistas Noite
Número mínimo de Atendentes
8h - meio dia
e1
a1
---
---
4
meio dia - 16h
e2
a2
---
8
16h - 20h
e3
---
a3
10
20h - meia noite
e4
---
---
6
A tabela abaixo indica as variáveis de decisão e1, e2, e3 e e4 referentes aos estagiários (tempo parcial) em cada um dos turnos de 4 horas e as variáveis a1, a2 e a3 referentes aos analistas em cada um dos turnos de 8 horas, bem como as quantidades mínimas para cada turno de 4 horas
O modelo matemático pode então ser assim descrito:
Minimizar o custo: ((e1+e2+e3+4e) x 10 x 4) + ((a1+a2+a3) x 14 x 8)
 
Sujeito a:
e1+a1>=4
e2+a1+a2>=8
e3+a2+a3 >=10
e4+a3>=6
a1 - 2e1 >= 0
a1+a2 - 2e2 >= 0
a2+a3 – 2e3 >=0
a3 – 2e4 >=0
 
Nota importante: as últimas quatro restrições NÃO poderiam ser deixadas escritas como:
a1/e1 >= 2
(a1+a2) / e2 >= 2
(a2+a3) / e3 >= 2
a3 / e4 >= 2
Pois essa formulação infringe as regras da programação linear
 
Nro. Mínimo de atendentes
Mínimo de 2 analistas para cada estagiário no turno
Ativ 5b – Resolução – Modelo Matemático
13
Ativ 6b – Resolução – Planilha Excel (veja arquivo no erudito)
Programação Linear Inteira
Programação Linear Inteira
Como pode ser percebido na solução da atividade 5b, a Programação Linear fornece soluções com valores contínuos (isso é, não necessariamente inteiros)
Isso pode ser um problema quando é necessário que os valores sejam inteiros, como é o caso da atividade 5b (não é possível contratar 1,3333 estagiários para o primeiro turno, por exemplo)
Simplesmente “arredondar” os valores para cima ou para baixo não resolve o problema, pois a solução arredondada pode não ser viável (infringir alguma das restrições) ou pode não ser a ótima
Programação Linear Inteira
Por Exemplo, arredondando os valores do exercício 5b para cima ou para baixo (considerando o valor mais próximo) temos a tabela abaixo, com Z (custo) mínimo R$ 1.552:
Esta não é a solução ótima possível com valores inteiros. Vamos realizar novamente o procedimento do Solver, agora impondo a solução inteira e verificar os resultados (descrito nos próximos slides, passo a passo)
Programação Linear Inteira no Excel
No solver, a programação linear inteira é obtida acrescentando-se mais uma restrição, aplicada às células que contêm os valores das variáveis de decisão
1) Abra a planilha “Ativ5b-gabarito-2014-2sem.xlxs”
2) Na aba “Ex5b” está a planilha com os dados do exercício
3) Abra a janela de parâmetros do Solver e clique no adicionar restrições
Programação Linear Inteira no Excel
4) na caixa “referencia de célula” marque a área correspondente às variáveis de decisão (B15 a H15)
5) Na caixa dropdown para o tipo de restrição, note que além do “<=“, “=“ e “>=“ que já conhecemos, há também duas outras opções:
Int – especifica números inteiros
Bin – especifica números binários (0 ou 1)
6) Selecione a opção “Int” e clique no OK
7) Note que uma restrição 
“= número inteiro” é adicionada
OBS – No Excel 2007 ou anteriores, a opção para números inteiros é “núm”, e não “int”
Programação Linear Inteira no Excel
8) Antes de executar o Solver, verifique na janela de opções se a opção “ignorar restrições de números inteiros” está desmarcada (clique no botão opções na janela de parâmetros do solver)
9) Clique no “Resolver”
10) Note que no caso da programação linear inteira, não é gerado relatório de sensibilidade
Ativ 5b – Resposta com Programação Linear Inteira
Veja o resultado
ótimo inteiro
Programação Binária
Programação Binária- Conceito
A programação binária é um caso especial da programação inteira
Quando 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
Programação Binária - Exemplo
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 armazéns, 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 interrelações entre as decisões (somente construir depósito em cidade em que for construída fábrica)?
Programação Binária - Exemplo
Para modelar esse problema com a programação binária utilizaremos 4 variáveis binárias representando a decisão (0=não faz o projeto; 1 = faz o projeto)
A partir daí, elabora-se o modelo matemático:
Função Objetivo: Max Z (VPL) = 9X1+5X2+6X3+4X4
Restrições:
Capital: 
 6X1+3X2+5X3+2X4 <= 10
Depósito somente onde há fábricas: 
X3 <= X1  -X1+X3 <=0
X4 <= X2  -X2+X4 <=0
Variáveis X1, X2, X3 e X4 Binárias	
Programação Binária no Excel
No solver, a programação Binária também é obtida acrescentando-se mais uma restrição, aplicada às células que contêm os valores das variáveis de decisão
Ao invés de selecionar “Int” deve-se selecionar “Bin” para a restrição adicionada
Também dever ser verificado se opção “ignorar restrições de números inteiros” está desmarcada na janela de opções
Atividades da Aula 
(6a e 6b)
Entregar pelo Erudito
Elabore a planilha excel com o modelo matemático e a solução em solver para o problema apresentado como exemplo:
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 armazéns, 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 interrelações entre as decisões (somente construir depósito em cidade em que for construída fábrica)?
Ativ 6 A– Entregar Pelo Erudito, em Grupos de 2 alunos, até o dia 19/09, 23h59m
Leia atentamente a descrição da situação empresarial abaixo, elabore o modelo matemático para o problema e resolva utilizando o solver.
Um agente de compra e venda de terrenos pretende vender três terrenos e recebeu ofertas para cada um deles de quatro incorporadores diferentes. Devido ao capital necessário, essas ofertas foram feitas de maneira que nenhum incorporador compraria mais do que um terreno. Cada terreno só pode ser vendido para um único incorporador (!). As ofertas em R$ mil estão apresentadas na tabela abaixo. 
Dica: pense inicialmente quantas decisões sim/não estão implícitas nessa tabela e como representar as inter-relações entre elas
O problema guarda semelhança ao problemas de transporte da ativ 4b
Ativ 6 B– Entregar Pelo Erudito, em Grupos de 2 alunos, até o dia 19/09, 23h59m