EAD350 II 2017 Aula2

Prévia do material em texto

EAD 350 
 Pesquisa Operacional 
Aula 2 
Prof. Hiroo Takaoka 
 
takaoka@usp.br 
FEA/USP 
Exemplo 1 - Wyndor Glass Co. 
(Hillier e Lieberman, 2010) 
Modelo Matemático 
 
Função Objetivo 
 
Max Z (lucro)= 3X1 + 5X2 
 
 
Sujeito a (restrições): 
 
1X1 + 0X2 < 04 (Fab. 1) 
0X1 + 2X2 < 12 (Fab. 2) 
3X1 + 2X2 < 18 (Fab. 3) 
X1, X2 > 0 
 
Fábrica 
Tempo de Produção por Lote 
(horas) 
Tempo de 
Produção 
Disponível por 
Semana Produto 1 Produto 2 
1 1 0 4 
2 0 2 12 
3 3 2 18 
Lucro por 
Lote 
(US$1.000) 
3 5 
Variáveis de Decisão 
X1- Quantidade de Produto 1 
X2- Quantidade de Produto 2 
         










 
 
X2 
Exemplo 1 - Wyndor Glass Co. 
X1 
Representação gráfica da inequação X1 < 4 
• Construir a reta correspondente à 
equação: X1 = 4 
Como o valor de X1 é sempre 4 para 
qualquer valor de X2, a reta vai ser 
paralela ao eixo X2. 
41 X
(Fabrica 1) 
• Testar a inequação: X1 < 4 
Tomar um ponto qualquer de uma das 
regiões limitadas pela reta, por 
exemplo o ponto (X1= 2, X2 = 2) 
Como 2 < 4, a região das soluções da 
inequação é aquela que contém o 
ponto testado. (2; 2) 
41 X
Exemplo 1 - Wyndor Glass Co. 
Representação gráfica da inequação 2X2 < 12 
X2 
X1 
          
 
 
 
 
 
 
 
 
 
 
 
 
122 2 X
(Fábrica 2) 
• Construir a reta correspondente à 
equação: 2X2 = 12 X2 = 6 
Como o valor de X2 é sempre 6 para 
qualquer valor de X1, a reta vai ser 
paralela ao eixo X1. 
• Testar a inequação: 2X2 < 12 
Tomar um ponto qualquer de uma das 
regiões limitadas pela reta, por 
exemplo o ponto (X1= 2, X2 = 2) 
Como 2(2) < 12 ou 4 < 12, a região 
das soluções da inequação é aquela 
que contém o ponto testado. (2; 2) 
122 2 X
         










 
 
X2 
Exemplo 1 - Wyndor Glass Co. 
X1 
• Construir a reta correspondente à equação: 
 3X1 + 2X2 = 18 
Precisamos de dois pontos: 
fazendo X1 = 0 teremos: 2X2 = 18 X2 = 9 
fazendo X2 = 0 teremos: 3X1 = 18 X1 = 6 
 
 
 
 
Representação gráfica das inequação 3X1 + 2X2 < 18 
X1 X2 
0 9 
6 0 
• Testar a inequação: 3X1 + 2X2 < 18 
Tomar um ponto qualquer de uma das regiões 
limitadas pela reta, por exemplo o ponto: 
 (X1= 2, X2 = 2) 
Como 3(2) + 2(2) < 18 ou 10 < 18, a região das 
soluções da inequação é aquela que contém o 
ponto testado. 
(2; 2) 
1823 21  XX
1823 21  XX
(Fabrica 3) 
(6; 0) 
(0; 9) 
         










 
 
41 X
X2 
Exemplo 1 - Wyndor Glass Co. 
X1 
1823 21  XX
A 
B C 
D 
E 
(Fábrica 1) 
122 2 X
(Fábrica 2) 
(Fábrica 3) 
Conjunto de 
soluções viáveis: 
Polígono 
ABCDE 
A solução ótima do problema está 
em um dos pontos extremos do 
conjunto de soluções viáveis. 
Conjunto de soluções viáveis 
Exemplo 1 - Wyndor Glass Co. 
• Ponto A (0; 0) 
• Ponto B (0; 6) 
• Ponto C (2; 6) 
Resolução de equações: 
2X2 = 12 
3X1 + 2X2 = 18 
3X1 + 2(12/2) = 18 
3X1 = 18 – 12 
X1 = 2 
 
• Ponto D (4; 3) 
Resolução de equações: 
X1 = 4 
3X1 + 2X2 = 18 
3(4) + 2X2 + 18 
2X2 = 18 – 12 
X2 = 3 
• Ponto E (4; 0) 
Determinação dos valores de X1 e X2 dos pontos ABCDE 
Ponto X1 X2 
A 0 0 
B 0 6 
C 2 6 
D 4 3 
E 4 0 
         










 
 
41 X
122 2 X
X2 
Exemplo 1 - Wyndor Glass Co. 
X1 
1823 21  XX
A 
B C 
D 
E 
(Fábrica 1) 
(Fábrica 2) 
(Fábrica 3) 
Ponto X1 X2 Z 
A 0 0 0 
B 0 6 30 
C 2 6 36 
D 4 3 27 
E 4 0 12 
Conjunto de 
soluções viáveis: 
Polígono 
ABCDE 
Solução Ótima 
Função Objetivo: Max Z = 3X1 + 5X2 
Calcular os 
valores de Z e 
pegar o maior 
valor de Z 
(lembre-se que 
estamos 
maximizando Z) 
Representação gráfica da função objetiva 
X2 
X1 
 
 
Z/C2 
-C1/C2 
1ZZ 
A equação Z = C1X1 + C2X2 pode ser 
reescrita como Função de 1° grau: 
 X2 = -C1/C2X1 + Z/C2 
A constante Z/C2 é chamada de coeficiente 
linear e representa, no gráfico a ordenada 
do ponto de intersecção da reta no eixo X2. 
A constante –C1/C2 é chamada de 
coeficiente angular da reta. 
Função Objetivo: Max Z = C1X1 + C2X2 
3ZZ 
2ZZ 
-C1/C2 
Note que como o coeficiente angular 
independe de Z, à medida que atribuímos 
valores a Z (por exemplo,Z1; Z2; Z3), 
obtemos retas paralelas. 
À medida que o valor de Z aumenta, a reta 
se afasta da origem do sistema de eixos. 
Conjunto de 
soluções viáveis: 
Polígono 
ABCDE 
         










 
 
41 X
122 2 X
X2 
Exemplo 1 - Wyndor Glass Co. 
X1 
1823 21  XX
A 
B C 
D 
E 
(Fábrica 1) 
(Fábrica 2) 
(Fábrica 3) 
Identificação gráfica do ponto ótimo. 
A determinação da solução ótima requer 
identificar a direção na qual a função objetivo Z 
= 3X1 + 5X2 aumenta (lembre-se que estamos 
maximizando Z). Vimos que o valor de Z 
aumenta à medida que a reta se afasta da 
origem de eixos. Assim, vamos designar um 
valor arbitrário a Z para traçar uma das retas 
paralelas e identificar a reta paralela que é mais 
afastada da origem de eixos que ainda contem o 
ponto do conjunto de soluções. 
Função Objetivo: Max Z = 3X1 + 5X2 
Conjunto de 
soluções viáveis: 
Polígono 
ABCDE 
         










 
 
41 X
122 2 X
X2 
Exemplo 1 - Wyndor Glass Co. 
X1 
1823 21  XX
A 
B C 
D 
E 
(Fábrica 1) 
(Fábrica 2) 
(Fábrica 3) 
15Z
21 5315 XX 
Identificação gráfica do ponto ótimo. 
Função Objetivo: Max Z = 3X1 + 5X2 
Vamos atribuir um valor a Z (Por exemplo, 
valor 15 que é MMC de seus coeficientes 
(3; 5)) e traçar a reta. 
(5; 0) 
(3; 0) 
Conjunto de 
soluções viáveis: 
Polígono 
ABCDE 
         










 
 
41 X
122 2 X
X2 
Exemplo 1 - Wyndor Glass Co. 
X1 
1823 21  XX
A 
B C 
D 
E 
(Fábrica 1) 
(Fábrica 2) 
(Fábrica 3) 
15Z
21 5315 XX 
Identificação gráfica do ponto ótimo. 
Função Objetivo: Max Z = 3X1 + 5X2 
Note que a solução ótima ocorre em 
C, que é o ponto no conjunto de 
soluções além do qual qualquer 
aumento adicional levará Z para fora 
de contornos de ABCDE. 
Z fora do 
Contorno 
ABCDE 
Vamos traçar visualmente as retas 
paralelas cujo valor de Z é 
crescente. 
Conjunto de 
soluções viáveis: 
Polígono 
ABCDE 
         










 
 
41 X
122 2 X
X2 
Exemplo 1 - Wyndor Glass Co. 
X1 
1823 21  XX
A 
B C 
D 
E 
(Fábrica 1) 
(Fábrica 2) 
(Fábrica 3) 
36Z
21 5336 XX 
Identificação gráfica do ponto ótimo. 
Os valores de X1 e X2 
relacionados com o ponto ótimo C 
podem ser obtidos a partir da 
solução do par de equações das 
retas limites das restrições de 
Fábrica 2 e Fábrica 3. 
 2X2 = 12 
 3X1 + 2X2 = 18 
 Z = 3(2) + 5(6) = 36 
C(2; 6) 
Função Objetivo: Max Z = 3X1 + 5X2 
Aplicativo para Gráfico de PL 
• Site do aplicativo 
http://www.zweigmedia.com/utilities/lpg/index.html 
http://www.zweigmedia.com/utilities/lpg/index.html 
• Usar aplicativo para o problema abaixo: 
 
FunçãoObjetivo 
 
Max Z (lucro)= 3X1 + 5X2 
 
 
Sujeito a (restrições): 
 
1X1 + 0X2 < 4 
0X1 + 2X2 < 12 
3X1 + 2X2 <18 
X1, X2 > 0 
Exemplo: 
Wyndor Glass Co. 
Exemplo de Gráfico feito por Aplicativo 
Exercício 2A 
(A) 
Max Z = 2X1 + X2 
sujeito a 
 -X1 + X2 < 1 
 X1 < 3 
 X2 < 2 
 X1 , X2 > 0 
Resolver graficamente, os seguintes problemas: 
(B) 
Max Z = 2X1 + X2 
sujeito a 
 -2X1 + X2 < 2 
 2X1 + X2 < 4 
 X1 , X2 > 0 
(C) 
Max Z = X2 
sujeito a 
 -X1 + X2 < 1 
 X2 > 2 
 X1 , X2 > 0 
(D) 
Min Z = 2X1 + X2 
sujeito a 
 X1 < 1 
 X2 < 2 
 X1 – X2 > 2 
 X1 , X2 > 0 
(E) 
Max Z = 2X1 + X2 
sujeito a 
 X1 < 3 
 X2 < 2 
 X1 - X2 > 1 
 X1 , X2 > 0 
(F) 
Min Z = X1 
sujeito a 
 -X1 + X2 < 2 
 X2 < 5 
 X1 , X2 > 0 
(G) 
Max Z = X1 + 2X2 
sujeito a 
 X1 – X2 < 0 
 3X1 + 3X2 < 6 
 X1 , X2 > 0 
Exercício 2B – Vitamina 
Sabe-se que os alimentos, leite, carne e ovo fornecem 
as quantidades de vitaminas dadas abaixo: 
Vitamina Leite (l) Carne (kg) Ovo (dz) 
Quantidade 
diária mínima 
A 0,25mg 2,00mg 10,00mg 1,00mg 
C 25,00mg 20,00mg 10,00mg 50,00mg 
D 2,50mg 200,00mg 10,00mg 10,00mg 
Custo 
unitário 
R$2,20/l R$17,00/kg R$4,20/dz 
Deseja-se calcular quais as quantidades de leite, carne e 
ovo, a fim de satisfazer as quantidades diárias mínimas de 
vitaminas a um custo mínimo. (não é preciso resolver!) 
Exercício 2B – Vitamina 
Min Z (Custo) = 2,20X1 + 17,00X2 + 4,20X3 
Xi  0 i =1, 2, 3 
Função Objetiva 
Restrições 
Variáveis de Decisão 
X1: quantidade diária de leite 
X2: quantidade diária de carne 
X3: quantidade diária de ovo 
 0,25X1 + 2,00X2 + 10,00X3  1,00 (Vitamina A) 
 25,00X1 + 20,00X2 + 10,00X3  50,00 (Vitamina C) 
 2,50X1 + 200,00X2 + 10,00X3  10,00 (Vitamina D) 
Petróleo 
Quantidade 
máxima 
disponível 
Custo 
unitário 
A 100 6 
B 200 3 
Gasolina 
% mínima 
de petróleo 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 de PL. 
Uma refinaria fabrica dois tipos de gasolina (1 e 2) a partir de dois tipos de 
petróleo bruto (A e B). 
Os custos de petróleo e os preços de venda de gasolina são dados a seguir: 
Exercício 2C - Problema de Refinaria 
Exercício 2C - Problema de Refinaria 
PA 
PB 
G1 
G2 
XA1+XA2 < 100 
XB1+XB2 < 200 
XA1+XB1 
XA2+XB2 
> 60% 
> 30% 
XA1 
XA2 
XB1 
XB2 
(Preço: 8) 
(Preço: 5) 
(Custo: 6) 
(Custo: 3) 
xA1: quantidade de petróleo A (PA) p/ produzir gasolina 1 (G1) 
xA2: quantidade de petróleo A (PA) p/ produzir gasolina 2 (G2) 
xB1: quantidade de petróleo B (PB) p/ produzir gasolina 1 (G1) 
xB2: quantidade de petróleo B (PB) p/ produzir gasolina 2 (G2) 
Variáveis 
de Decisão 
Exercício 2C - Problema de Refinaria 
 Função Objetiva 
 Max L = Receita - Custo 
 Max L= 8(XA1 + XB1) + 5(XA2 + XB2) - 6(XA1 + XA2) - 3(XB1 + XB2) 
 
 
 Max L = 2XA1 – 1XA2 + 5XB1 + 2XB2 
 Restrições 
 Quantidades de petróleo A e B 
 XA1 + XA2 < 100 
 XB1 + XB2 < 200 
 Quantidade mínima % de petróleo A requerida 
 XA1 / (XA1 + XB1) > 0,6 → 0,4XA1- 0,6XB1 > 0 (na gasolina 1) 
 XA2 / (XA2 + XB2) > 0,3 → 0,7XA2 - 0,3XB2 > 0 (na gasolina 2) 
 Xij > 0 
Receita Custo 
Não poderia ser deixadas formuladas assim, pois infringe as regras de PL. 
Exercício 2D – Problema de Escala 
A empresa ABC está envolvida na preparação de medicamentos sofisticados que 
requerem o emprego de técnicos especializados. A empresa trabalha em turnos de 
oito horas cada, mas para haver continuidade no trabalho, a cada quatro horas, os 
técnicos são adicionados para trabalhar com as pessoas que já tenham 
completado quatro horas. Um técnico deve trabalhar continuamente por oito 
horas. Considerando o quadro abaixo, deseja-se formular um modelo de 
programação linear para encontrar o programa que minimiza a mão de obra a ser 
utilizada pela empresa. (não é preciso resolver!) 
Período do dia 
Número mínimo necessário de 
técnicos 
02:00 às 06:00h 10 
06:00 às 10:00h 25 
10:00 às 14:00h 40 
14:00 às 18:00h 50 
18:00 às 22:00h 20 
22:00 às 02:00h 15 
Período 
2h 
(1) 
6h 
(2) 
10h 
(3) 
14h 
(4) 
18h 
(5) 
22h 
(6) 
1 
2 
3 
4 
5 
6 
Numero mínimo 
de técnicos 
10 25 40 50 20 15 
X1 
X2 
X3 
X4 
X5 
X6 X6 
Exercício 2D – Problema de Escala 1 
Variáveis de Decisão 
Xi : número de técnicos adicionados no início do período i (i = 1 a 6) 
Exercício 2D – Problema de Escala 1 
 Função Objetivo 
 Min Z = 1X1 + 1X2 + 1X3 + 1X4 + 1X5 + 1X6 
 Sujeito a 
 X1 + X6 > 10 N° mínimo de técnicos necessário no período 1 
 X1 + X2 > 25 N° mínimo de técnicos necessário no período 2 
 X2 + X3 > 40 N° mínimo de técnicos necessário no período 3 
 X3 + X4 > 50 N° mínimo de técnicos necessário no período 4 
 X4 + X5 > 20 N° mínimo de técnicos necessário no período 5 
 X5 + X6 > 15 N° mínimo de técnicos necessário no período 6 
 Xi > 1 (i = 1 a 6) Pelo menos um técnico deve ser adicionado 
por período 
Xi : número de técnicos adicionados no início do período i (i = 1 a 6) 
Variáveis de Decisão 
Exercício 2E – Fluxo de Caixa 
Um determinado investidor tem três opções de investimento, 
denominados A, B e C, disponíveis no próximo ano. Essas três opções não 
são mutuamente excludentes. Qualquer dinheiro recebido de qualquer 
opção poderá ser reinvestido, imediatamente, em qualquer uma das três 
opções. 
A opção A está disponível no princípio de cada um dos quatro trimestres 
seguintes. Cada real investido em A no princípio de um trimestre lhe 
devolve R$1,10 no final daquele trimestre. 
A opção B está disponível no princípio de cada um dos dois semestres 
seguintes. Cada real investido em B no princípio de um semestre lhe 
devolve R$1,20 no final daquele semestre. 
A opção C só está disponível no princípio do primeiro ano. Cada real 
investido em C lhe devolve R$1,40 um ano mais tarde. 
O capital inicial do investidor é de R$500.000,00. Deseja-se formular um 
modelo de programação linear para fornecer o plano de investimento que 
maximize a quantidade de dinheiro que o investidor pode acumular no 
final do próximo ano. (não é preciso resolver!) 
(Sugestão: usar o modelo de fluxo de caixa) 
Exercício 2E – Fluxo de Caixa 
XA1 XA2 XA3 XA4 
XB1 XB3 
1,1XA1 1,1XA2 1,1XA3 1,1XA4 
1 2 3 4 5 
A 
B 
C 
1 2 3 4 5 
1 2 3 4 5 
1 2 3 4 5 
1,2XB1 1,2XB3 
XC1 
1,4XC1 
R1 R2 R3 R4 
R1 R2 R3 
Xij os valores investidos nas alternativas i (i = A, B, C) no início dos trimestres j (j = 1, 2, 3, 4) 
Rj os valores não investidos no início dos trimestres j (j = 1, 2, 3, 4) 
500.000 
Não 
Investidos 
Saída 
Entrada 
Exercício 2E – Fluxo de Caixa 
Função Objetiva 
Max Z = 1,1XA4 + 1,2XB3 + 1,4XC1 
Sujeito a 
XA1 + XB1 + XC1 + R1 = 500.000 XA1 + XB1 + XC1 + R1 = 500.000 
XA2 + R2 = R1 + 1,1XA1 XA2 + R2 - R1 - 1,1XA1 = 0 
XA3 + xB3 + R3 = R2 + 1,1XA2 + 1,2XB1 XA3 + XB3 +R3 - R2 - 1,1XA2 – 1,2XB1 = 0 
XA4 + R4 = R3 + 1,1XA3 XA4 + R4 - R3 - 1,1XA3 = 0 
Xij > 0 para todo i e j Xij > 0 para todo i e j 
Rj > 0 para todo j Rj > 0 para todo j 
 
Não poderia ser deixadas 
formuladas assim, pois 
infringe as regras de PL. 
Xij os valores investidos nas alternativas i (i= A, B, C) no início dos trimestres j (j = 1, 2, 3, 4) 
Rj os valores não investidos no início dos trimestres j (j = 1, 2, 3, 4)   entradasaída
Exercício 2F – Produção 
Uma fábrica é constituída por quatro centros de processamento S1, S2, S3 e 
S4 e produz três produtos finais F1, F2 e F3, cada um deles tendo apenas um 
processo de fabricação. O centro S1 recebe a matéria-prima, podendo 
processar, no máximo, K1 unidades a um custo unitário C1. Na saída do 
centro S1, é possível enviar o resultado do primeiro processamento, tanto 
para os centros S2 como S3. Os centros S2 e S3 têm custo unitário de 
processamento C2 e C3 e capacidades máximas K2 e K3, respectivamente. A 
saída do centro S2 pode constituir o produto final F1 ou servir de entrada 
para o centro S4. A saída S3 tem que obrigatoriamente, passar por S4. O 
centro S4 pode processar qualquer uma, ou ambas as entradas, com uma 
capacidade total de K4 unidades e um custo unitário de processamento, para 
qualquer entrada, de C4. As saídas de S4 resultarão nos produtos finais F2 e 
F3. Os preços unitários de venda são P1, P2 e P3. 
Utilizando como variáveis de decisão, o quanto fabricar de cada produto, 
formule o problema de maximização do lucro como programação linear. 
P1=8, P2=12, P3=14; C1=4, C2=2, C3=1, C4=3; K1=90, K2=50, K3=30, 
K4=70 
Exercício 2F – Produção 1 
S1 
S2 S3 
S4 
Matéria prima 
K1 = 90, C1 = 4 
K3 = 30, C3 = 1 K2 = 50, C2 = 2 
K4 = 70, C4 = 3 
F1 
P1 = 8 
F2 
P2 = 12 
F3 
P3= 14 
X1, X2 X3 
X3 X1 X2 
X3 X2 
P1=8, P2=12, P3=14 (Preço) 
K1=90, K2=50, K3=30, K4=70 (Capacidade) 
C1=4, C2=2, C3=1, C4=3 (Custo) 
Exercício 2F – Produção 
Variáveis de decisão 
X1 quantidade do produto F1 
X2 quantidade do produto F2 
X3 quantidade do produto F3 
P1=8, P2=12, P3=14 (preço) 
C1=4, C2=2, C3=1, C4=3 (custo) 
K1=90, K2=50, K3=30, K4=70 (capacidade) 
Função objetiva 
Max Lucro = 8X1 + 12X2 + 14X3 – (4X1 + 2X1) - (4X2 + 2X2 + 3X2) - (4X3 + 1X3 + 3X3) 
 
 
 
 = 2X1+ 3X2 + 6X3 
 
Sujeito a 
X1 + X2 + X3 < 90 Centro de processamento S1 
X1 + X2 < 50 Centro de processamento S2 
 X3 < 30 Centro de processamento S3 
 X2 + X3 < 70 Centro de processamento S4 
X1, X2, X3 > 0 
Receita Custo F1 Custo F2 Custo F3