LISTA DE EXERCÍCIOS DE PO _ 2012_1_NOVO

Prévia do material em texto

LISTA DE EXERCÍCIOS DE PESQUISA OPERACIONAL
1) EXERCÍCIOS DE MODELAGEM
a) A fazenda ABEP é uma pequena fazenda de criação de animais de pequeno porte e, 
utiliza pelo menos 800 Kg por dia de uma ração. Esta ração é composta de uma mistura 
de milho e soja, onde as composições estão listadas no quadro abaixo.
Kg/Kg de ingrediente
Ingrediente Proteína Fibra Custo ($/Kg.)
Milho 0,09 0,02 0,30
Soja 0,60 0,06 0,90
As necessidades diárias desta ração especial e estipulada em pelo menos 30% de 
proteína e pelo menos 5% de fibra. A Fazenda ABEP deseja determinar uma mistura 
destes ingredientes de tal forma a obter uma ração com o menor custo. Modele este 
problema como um problema de programação linear.
b) A companhia Stratus é especializada na produção de dois tipos básicos de canos 
plásticos, o tipo A e o tipo B. Três recursos são cruciais para a confecção dos tubos: horas 
de prensa, horas de empacotamento e a adição de um tubo especial, que serve para o 
endurecimento da matéria plástica necessária para a construção de cada um dos tubos. 
Na tabela a seguir é representada a situação da próxima semana. Todos os dados 
apresentados na tabela estão expressos em unidades de 100 metros de cano.
Produto
Recurso Tipo A Tipo B Recurso disponível
Prensa 4 hrs 6 hrs 48 hrs
Empacotamento 2 hrs 2 hrs 18 hrs
Mistura do Aditivo 2 kg 1 kg 16 kg
A contribuição para o lucro por 100 metros de cano é de $34 para o cano do tipo A 
e $40 para o cano do tipo B. Pede-se para formular um modelo de programação linear 
para determinar quanto deve ser produzido de cada cano de forma a se maximizar o 
lucro.
c) O dono da fazenda Boi Bandido dispõe de 1.500 litros de leite por dia para fazer doce 
de leite e queijo. Para cada kg de queijo são necessários 12 litros e para cada kg de doce 
são exigidos 10 litros. Além disso, algumas exigências de mercado são impostas:
 A quantidade máxima de doce que pode ser feita por dia é de 100kg;
 A quantidade de queijo deve ser no máximo igual a 1,3 vezes a quantidade de doce de 
leite.
A fazenda dispõe de 12 empregados que trabalham, cada um, 8 horas/dia. O preparo 
de cada kg de queijo requer 40 minutos de mão de obra e cada kg de doce requer 60 
minutos. Sabendo que o kg de queijo dá uma receita de R$ 8,00 e cada kg de doce dá 
uma receita de R$ 5,00, qual a produção diária que maximiza a receita total? Utilize seus 
conhecimentos de Programação Linear para modelar este problema.
d) A empresa Fundo de Quintal S.A. pode fabricar dois produtos (1 e 2). Na fabricação do 
produto 1 a empresa gasta nove horas-homem e três horas-máquina (a tecnologia 
utilizada é intensiva em mão-de-obra). Na fabricação do produto 2 a empresa gasta uma 
hora-homem e uma hora-máquina (a tecnologia é intensiva em capital). Sabendo-se que a 
empresa dispõe de 18 horas-homem e12 horas-máquina e ainda que os lucros dos 
produtos são $4 e $1 respectivamente, quanto deve a empresa fabricar de cada produto 
para obter o maior lucro possível (ou o lucro máximo ou ainda maximizar o lucro)?
2) EXERCÍCIOS DE SOLUÇÃO GRÁFICA:
Encontre uma solução, se houver, para os seguintes modelos de programação linear. 
Utilize o método gráfico para resolver esta questão. Justifique a sua resposta.
a) 
0 x,x 
16 x 2x 
18 2x 2x 
48 6x 4x a sujeito 
40x 34x Max 
21
21
21
21
21
≥
≤+
≤+
≤+
+
b)
0 x, x 
6 x 2x 
4 2x x- 
9 3x xa sujeito 
3x 2x Max 
21
21
21
21
21
≥
≤+
≤+
≤+
+
3) EXERCÍCIOS DO MÉTODO SIMPLEX:
a) Resolva, utilizando o método Simplex na forma de tableau, o seguinte problema de 
programação linear:
0 x, x 
10 2x x 
8 x 2x a sujeito 
3x 2x MAX
21
21
21
21
≥
≤+
≤+
+
b) Resolva o seguinte problema de programação linear:
0 x, x 
15 5x 3x 
 3 x x 
2 2x x a Sujeito
x2x Z Max 
21
21
21
21
21
≥
≤+
≤+
≤+
+= 3
a)Graficamente; b)Pelo Método Simplex.
SOLUÇÃO:
1) EXERCÍCIOS DE MODELAGEM
a) (Handy Taha, page 19)
A ração consiste numa mistura de milho e soja, sendo assim, as variáveis de 
decisão do modelo podem ser definidas como:
x1 = Quantidade (Kg) de milho na mistura diária;
x2 = Quantidade (Kg) de soja na mistura diária.
A função objetivo busca minimizar o custo total diário (em $) da ração e é expressa 
como:
Minimizar Z = 0,3x1 + 0,9x2
As restrições do modelo devem refletir a quantidade diária necessária e as 
necessidades da dieta. Como a Fazenda ABEP necessita de 800 Kg de ração por dia, a 
restrição associada pode ser expressa como:
x1 + x2 ≥ 800
A quantidade de proteína incluída em x1 Kg de milho e x2 Kg de soja é dada pela 
seguinte inequação:
0,9x1 + 0,6x2 ≥ 0,3 (x1 + x2)
De forma análoga, podemos escrever a seguinte restrição para as quantidades de 
fibra:
0,02x1 + 0,06x2 ≥ 0,05 (x1 + x2)
As restrições precedentes são simplificadas agrupando-se todos os coeficientes de 
x1 e x2 no lado esquerdo de cada restrição. Assim, o modelo completo pode ser escrito da 
seguinte forma:
0 x,x 
0 0,01x 0,03x 
0 0,30x 0,21x 
800 x x a sujeito 
0,9x 0,3x Max 
21
21
21
21
21
≥
≤−
≤−
≥+
+
b) (Operations Research 4th edition, Krajewski, Ritzman)
Definindo as Variáveis de Decisão:
As variáveis de decisão podem ser definidas como:
X1 = quantidade de cano do tipo A a ser produzido e vendido na próxima semana.
X2 = quantidade de cano do tipo B a ser produzido e vendido na próxima semana.
Definindo a função objetivo:
A meta é maximizar o lucro total que os dois produtos fornecem quando produzidos. Cada 
unidade do cano do tipo A (X1) rende $34, e cada unidade do cano do tipo B (X2) rende 
$40. Desta forma, a função objetivo torna-se:
21 40x 34x Max +
Por último devemos determinar as restrições do modelo. Cada unidade de X1 e X2 
produzem alguns dos recursos críticos. Do departamento de prensa, uma unidade de X1 
requer 4 horas e uma unidade de X2 requer 6 horas. O total não deve exceder às 48 horas 
da capacidade disponível, então devemos utilizar o sinal de ≤. Desta forma temos a 
primeira restrição.
prensa 48 6x 4x 21 ⇒≤+
De forma análoga, podemos formular restrições para o setor de empacotamento e 
de aditivo. Assim, temos:
aditivo de adição 16 x 2x
ntoempacotame 18 2x 2x
21
21
⇒≤+
⇒≤+
Além disso, devido ao tipo do problema, faz-se necessário que as variáveis de 
decisão sejam valores não negativos, ou seja:
denegativida não 0 x, x 21 ⇒≥
Logo, escrevendo as restrições e a função objetivo, temos o seguinte modelo de 
programação linear:
0 x,x 
16 x 2x 
18 2x 2x 
48 6x 4x a sujeito 
40x 34x Max 
21
21
21
21
21
≥
≤+
≤+
≤+
+
c) A partir do que foi descrito no enunciado do problema temos:
Determinando as variáveis de decisão:
XD = quantidade (kg) de doce de leite
XQ = quantidade (kg) de queijo
Determinando a função objetivo:
CD = receita (R$) de doce de leite = R$ 5,00
CQ = receita (R$) de queijo = R$ 8,00
Maximizar Z = 5 XD + 8 XQ
Determinando as restrições:
Quantidade máxima de doce de leite = 100 kg ⇒ XD ≤ 100
Quantidade máxima de queijo = 1,3 * Qnt máxima de doce de leite = 1,3 * 100 ⇒ XQ ≤ 
130
Quantidade máxima de leite para fazer doce de leite e queijo = 1.500 litros/dia
⇒ 12 XQ + 10 XD ≤ 1.500
Tempo para preparar doce de leite e queijo ⇒ 12 empregados * 8hr * 60 min. = 
5.760 min.
⇒ 40 XQ + 60 XD ≤ 5.760
A partir do descrito temos o modelo completo:
Maximizar Z = 5 XD + 8 XQ
Sujeito a XD ≤ 100
 XQ ≤ 13010 XD + 12 XQ ≤ 1.500
 60 XD + 40 XQ ≤ 5.760
 XD ≥ 0
 XQ ≥ 0
d) Sendo x1 e x2 as quantidades fabricadas dos produtos 1 e 2 e
Determinando as variáveis de decisão:
x1 = quantidade a ser produzida do produto 1
x2 = quantidade a ser produzida do produto 2
Determinando a Função Objetivo:
Admitindo que não há economia de escala mas quantidades fabricadas quanto ao 
lucro, a função lucro é uma função linear de x1 e x2 ou seja:
Z = 4 x1 + x2
esse lucro deve ser maximizado por uma escolha de x1 e x2 
 Max Z = 4 x1 + x2 
 x1, x2 
Se o problema parasse aqui o lucro seria ilimitado. Porém, existem recursos limitados.
Determinando as restrições:
O que limita as quantidades fabricadas aqui são as horas-homem e horas-máquina 
disponíveis. Assim, as quantidades fabricadas e as horas utilizadas de cada recursos não 
podem ultrapassar as quantidades de recursos disponíveis ou seja:
H-H 9x1 + x2 ≤ 18 e 
H-M 3 x1 + x2 ≤ 12
Restrições de não negatividade:
x1 ≥ 0 e x2 ≥ 0
Assim, o lucro só poderá crescer até esses limites.
O modelo completo é então:
Max L = 4 x1 + x2 
sujeito a 
9x1 + x2 ≤ 18 horas-homem
3 x1 + x2 ≤ 12 horas-máquina
x1 ≥ 0 e x2 ≥ 0 não-negatividade
Como o problema é de duas variáveis, as restrições e a função objetivo estão 
definidos em duas coordenadas e, podemos obter uma solução fácil graficamente. 
2)
a) 
b) 
FORestrição 1
Restrição 2
Restrição 3
Pto Ótimo
F.O.
Restrição 1
Restrição 2
Restrição 3
Pto Ótimo
3)
a)
Considerando o problema original, tem-se:
0 x, x 
10 2x x 
8 x 2x a sujeito 
3x 2x MAX
21
21
21
21
≥
≤+
≤+
+
Adicionando as variáveis de excesso obtém-se:
0 x, x, x, x 
10 x 2x x 
8 x x 2x a sujeito 
3x 2x MAX
4321
421
321
21
≥
=++
=++
+
Z* = 16, 2=*1x , 4=
*
2x
ENTRA
BASE Z X1 X2 X3 X4 B RAZÃO
MAX 1 -2 -3 0 0 0
X3 0 2 1 1 0 8 8
SAI X4 0 1 2 0 1 10 5
ENTRA
BASE Z X1 X2 X3 X4 B RAZÃO
MAX 1 - 1/2 0 0 1 1/2 15
SAI X3 0 1 1/2 0 1 - 1/2 3 2
X2 0 1/2 1 0 1/2 5 10
ÓTIMO BASE Z X1 X2 X3 X4 B
MAX 1 0 0 1/3 1 1/3 16
X1 0 1 0 2/3 - 1/3 2
X2 0 0 1 - 1/3 2/3 4
b) 
Solução Gráfica:
Método Simplex:
1a restrição
2a restrição
3a restrição
Pto Ótimo
ENTRA
BASE Z X1 X2 X3 X4 X5 RHS RAZÃO
MAX 1 -2 -3 0 0 0 0
X3 0 1 2 1 0 0 2 1 SAI
X4 0 1 1 0 1 0 3 3
X5 0 3 5 0 0 1 15 3
ENTRA RAZÃO
BASE Z X1 X2 X3 X4 X5 RHS
MAX 1 - 1/2 0 1 1/2 0 0 3
X2 0 1/2 1 1/2 0 0 1 2 SAI
X4 0 1/2 0 - 1/2 1 0 2 4
X5 0 1/2 0 -2 1/2 0 1 10 20
BASE Z X1 X2 X3 X4 X5 RHS ÓTIMO
MAX 1 0 1 2 0 0 4
X1 0 1 2 1 0 0 2
X4 0 0 -1 -1 1 0 1
X5 0 0 -1 -3 0 1 9
SOLUÇÃO: X1 = 2 X2 = 0 X3 = 0 X4 = 1 X5 = 9 Z = 4
	Kg/Kg de ingrediente
	Ingrediente
	Milho
	Produto