APX3-POI_2022_1

Prévia do material em texto

Centro Federal de Educação Tecnológica Celso Suckow da Fonseca
Curso Superior de Engenharia de Produção
Pesquisa Operacional I
Prof. Coordenador(a): Felipe Pereira do Carmo Data: 25/06/2022
Tutoria à Distância: Georgia Assumpção Pólo: Piraí
Aluno (a): Período: 7º Mat.:
Avaliação Presencial – APX3
● Preencha seu nome no campo de identificação;
● A APX3 é individual: não serão aceitas avaliações onde se perceba o compartilhamento
das resoluções;
● Leia com atenção antes de responder às perguntas;
● A interpretação das questões faz parte da avaliação;
● Sobre o uso de softwares (SageMath, Lindo, Solver) para a resolução das questões: será permitido
o uso com as devidas explicações de cada uma das etapas da resolução, explicitando o raciocínio
seguido. Não consideraremos a simples cópia da resolução, principalmente no que se refere ao uso
do Simplex.
Boa Prova!!!
-----------------------------------------------------------------------------------------------------------------------
Questão 1 (3,0 pontos) Considere o PPL abaixo:
max 3𝑥1 + 5𝑥2
𝑠. 𝑎. − 5𝑥1 + 7𝑥2 ≤ 3
2𝑥1 + 5𝑥2 ≥ 7
5𝑥1 + 6𝑥2 ≤ 20
𝑥1 ≥ 0, 𝑥2 ≥ 0
a) (1,0 ponto) Encontre seu dual.
Partimos do princípio que cada variável técnica gera uma restrição no dual, e tomamos os coeficientes de
cada restrição como o x1, e logo depois fazemos o mesmo com cada restrição de x2 e com os demais. Os
sinais serão então invertidos e logo após os coeficientes será a nossa primal. A função objetivo será então o
oposto, no caso, minimizar. O dual da variável deve ser ≤ 0,
D = min 3𝑥1 + 7𝑥2 + 20x3
-5𝑥1 + 2𝑥2 + 5x3 ≥ 3
6𝑥1 + 5𝑥2 + 7x3 ≥ 5
𝑥1 ≥ 0, 𝑥2 ≥ 0, 𝑥3 ≥ 0
b) (2,0 pontos) Determine o valor ótimo e a solução ótima para o problema dual.
Nós passamos o problema para a forma padrão, adicionando variáveis de excesso, de folga, e artificiais, onde
necessário (mostrar/ocultar detalhes)
● Como a restrição 1 é do tipo '≥' é necessária a variável de excesso X4 e a variável artificial X7.
● Como a restrição 2 é do tipo '≥' é necessária a variável de excesso X5 e a variável artificial X8.
● Como a restrição 3 é do tipo '≤' é necessária a variável de folga X6.
MINIMIZAR: Z = 3 X1 + 7
X2 + 20 X3
MAXIMIZAR: Z = -3 X1 -7 X2 -20 X3 + 0 X4 +
0 X5 + 0 X6 + 0 X7 + 0 X8
sujeito a
-5 X1 + 2 X2 + 5 X3 ≥ 3
6 X1 + 5 X2 + 7 X3 ≥ 5
0 X1 + 0 X2 + 0 X3 ≤ 0
sujeito a
-5 X1 + 2 X2 + 5 X3 -1 X4 + 1 X7 = 3
6 X1 + 5 X2 + 7 X3 -1 X5 + 1 X8 = 5
0 X1 + 1 X6 = 0
X1, X2, X3 ≥ 0 X1, X2, X3, X4, X5, X6, X7, X8 ≥ 0
Nós passamos construir a primeira tabela da Fase I do método das Duas Fases.
Método Simplex das Duas Fases
Tabela 1 0 0 0 0 0 0 -1 -1
Base Cb P0
P
1
P
2 P3
P
4
P
5
P
6
P
7
P
8
P7 -1 3 -5 2 5 -1 0 0 1 0
P8 -1 5 6 5 7 0 -1 0 0 1
P6 0 0 0 0 0 0 0 1 0 0
Z -8 -1 -7 -12 1 1 0 0 0
A variável que vai sair da base é P7 e a que entra P3.
Método Simplex das Duas Fases
Operações intermédias (mostrar/ocultar detalhes)
Tabela 2 0 0 0 0 0 0 -1 -1
Base Cb P0 P1 P2 P3 P4
P
5
P
6 P7
P
8
P3 0 0.6 -1 0.4 1 -0.2 0 0 0.2 0
P8 -1 0.8 13 2.2 0 1.4 -1 0 -1.4 1
P6 0 0 0 0 0 0 0 1 0 0
Z -0.8 -13
-2.
2 0
-1.
4 1 0 2.4 0
A variável que vai sair da base é P8 e a que entra P1.
Método Simplex das Duas Fases
Operações intermédias (mostrar/ocultar detalhes)
Tab
ela
3
 0 0 0 0 0 0 -1 -1
Bas
e
C
b P0 P1 P2 P3 P4 P5 P6 P7 P8
P3 0 0.66153846153846 0
0.569230
7692307
7
1
-0.092307
69230769
2
-0.0769230
76923077 0
0.092307
6923076
92
0.07692307
6923077
P1 0 0.061538461538462 1
0.169230
7692307
7
0 0.10769230769231
-0.0769230
76923077 0
-0.10769
2307692
31
0.07692307
6923077
P6 0 0 0 0 0 0 0 1 0 0
Z -0 0 -0 0 0 0 0 1 1
Existe alguma solução possível para o problema, assim nós podemos passar para a Fase II para calculá-la.
Método Simplex
Operações intermédias (mostrar/ocultar detalhes)
Tabel
a 1 -3 -7
-2
0 0 0 0
Base Cb P0
P
1 P2
P
3 P4 P5
P
6
P3 -20
0.6615384615384
6 0
0.569230769230
77 1
-0.092307692307
692
-0.076923076923
077 0
P1 -3 0.061538461538462 1
0.169230769230
77 0
0.1076923076923
1
-0.076923076923
077 0
P6 0 0 0 0 0 0 0 1
Z -13.415384615385 0
-4.89230769230
77 0 1.5230769230769 1.7692307692308 0
A variável que vai sair da base é P1 e a que entra P2.
Método Simplex
Operações intermédias (mostrar/ocultar detalhes)
Tabel
a 2 -3 -7
-2
0 0 0 0
Base Cb P0 P1
P
2
P
3 P4 P5
P
6
P3 -20
0.4545454545454
5
-3.36363636363
64 0 1
-0.454545454545
45
0.1818181818181
8 0
P2 -7 0.36363636363636
5.909090909090
9 1 0
0.6363636363636
4
-0.454545454545
45 0
P6 0 0 0 0 0 0 0 1
Z -11.636363636364
28.90909090909
1 0 0 4.6363636363636
-0.454545454545
45 0
A variável que vai sair da base é P3 e a que entra P5.
Método Simplex
Operações intermédias (mostrar/ocultar detalhes)
Tabela 3 -3 -7 -20 0 0 0
Base Cb P0 P1 P2 P3 P4
P
5
P
6
P5 0 2.5 -18.5 0 5.5 -2.5 1 0
P2 -7 1.5 -2.5 1 2.5 -0.5 0 0
P6 0 0 0 0 0 0 0 1
Z -10.5 20.5 0 2.5 3.5 0 0
A solução ótima é Z = 10.5
X1 = 0
X2 = 1.5
X3 = 0
Questão 2 (3,0 pontos) Considere o PPL abaixo:
min 3𝑥1 − 𝑥2
𝑠. 𝑎. 𝑥1 + 2𝑥2 ≥ 10
4𝑥1 − 8𝑥2 ≤ 12
2𝑥1 + 9𝑥2 ≤ 40
2 𝑥1 + 9𝑥2 ≥ 20
𝑥1, 𝑥2 ≥ 0
a) (1,0 ponto) Desenhe a região viável.
b) (1,0 ponto) Determine três soluções básicas e classifique-as como viáveis ou inviáveis.
c) (1,0 ponto) Determine uma solução básica inicial viável a partir do Método das Duas
Fases.
Questão 3 (4,0 pontos) Uma fábrica vende dois produtos P1 e P2, ao preço por tonelada de
R$ 100,00 e R$ 80,00, respectivamente. A produção de P1 e P2 é realizada em toneladas e
consome dois recursos, que serão chamados de R1 e R2. Esses recursos estão disponíveis nas
quantidades de 25 e 30 unidades, respectivamente. A produção de 1 tonelada de P1 consome
9 unidades de R1 e 2 unidades de R2, e a produção de 1 tonelada de P2 consome 6 unidades
de R1 e 7 unidades de R2. Formule um problema de programação linear para determinar
quantas toneladas de cada produto devem ser fabricadas para se obter o maior faturamento
possível.
a) (1,0 ponto) Qual será o faturamento máximo? Quanto de cada produto deve ser
fabricado? Responda resolvendo o problema pelo método Simplex.
b) (1,0 ponto) Como os recursos estão sendo utilizados? Estão sendo subutilizados ou
são suficientes?
c) (1,0 ponto) Ache o problema dual e sua solução ótima.
d) (1,0 ponto) Qual o impacto sobre o lucro se aumentarmos a disponibilidade do
recurso R1 de 30 para 33? Justifique.