Gabarito AD2

Prévia do material em texto

Pesquisa Operacional I - AD2
Questão 1. (5,0) Considere o Problema de Programação Linear (PPL) abaixo e responda aos itens a seguir.
max 3x1 + 9x2
x1 + 4x2  8
x1 + 2x2  4
x1, x2 � 0
a) (1,0) Desenhe a região viável do PPL e determine a solução ótima.
Solução Ótima: x = (1, 1) Valor Ótimo: 5
b) (1,0) Associe a cada vértice da região viável as variáveis básicas e não-básicas (ou seja, defina os conjuntos IB e IR.)
Vértice var. básicas var. não-básicas
(0,0,8,4) x , x x , x
(4,0,4,0) x1, x3 x2, x4
(0,2,0,0) x2, x3 x1, x4
(0,2,0,0) x2, x4 x1, x3
c) (1,0) Indique quais as soluções degeneradas. Justifique.
A solução (0,2,0,0) é degenerada uma vez que tem uma variável básica com valor igual a zero.
d) (2,0) Suponha que a restrição 2x1 + x2 � ↵ seja adicionada ao PPL. Para que valores de ↵ o problema é inviável?
1 de 3
3 4 1 2
gráfico da região viável: 0,5
solução ótima: 0,5
cada vértice correto: 0,25
1,0
Pesquisa Operacional I - AD2
Para valores de ↵ > 8 a região de interseção entre as inequações é vazia.
Questão 2. (5,0) Resolva os PPLs abaixo pelo método Simplex exibindo todos os dicionários.
(a) (2,0)
max 2x1 + 3x2
2x1 + 2x2  4
x1 � 1
x1 + x2 = 2
x1, x2 � 0
x3 = 4 � 2x1 � 2x2
x4 = �1 + x1
x5 = 2 � x1 � x2
x6 = �2 + x1 + x2
z = 0 + 2x1 + 3x2
The initial dictionary is infeasible, solving auxiliary problem.
x3 = 4 + x0 � 2x1 � 2x2
x4 = �1 + x0 + x1
x5 = 2 + x0 � x1 � x2
x6 = �2 + x0 + x1 + x2
w = 0 � x0
Entering: x0. Leaving: x6.
x3 = 6 + x6 � 3x1 � 3x2
x4 = 1 + x6 � x2
x5 = 4 + x6 � 2x1 � 2x2
x0 = 2 + x6 � x1 � x2
w = �2 � x6 + x1 + x2
Entering: x1. Leaving: x0.
x3 = 0 � 2x6 + 3x0
x4 = 1 + x6 � x2
x5 = 0 � x6 + 2x0
x1 = 2 + x6 � x0 � x2
w = 0 � x0
2 de 3
1,0
0,5
0,3
0,3
Pesquisa Operacional I - AD2
Back to the original problem.
x3 = 0 � 2x6
x4 = 1 + x6 � x2
x5 = 0 � x6
x1 = 2 + x6 � x2
z = 4 + 2x6 + x2
Entering: x2. Leaving: x4.
x3 = 0 � 2x6
x2 = 1 + x6 � x4
x5 = 0 � x6
x1 = 1 + x4
z = 5 + 3x6 � x4
Entering: x6. Leaving: x3.
x6 = 0 � 12x3
x2 = 1 � 12x3 � x4
x5 = 0 +
1
2x3
x1 = 1 + x4
z = 5 � 32x3 � x4
The optimal value: 5. An optimal solution: (1, 1) .
(b) (2,0)
max 3x1 + 2x2
2x1 + x2  2
3x1 + 4x2 � 12
x1, x2 � 0
x3 = 2 � 2x1 � x2
x4 = �12 + 3x1 + 4x2
z = 0 + 3x1 + 2x2
The initial dictionary is infeasible, solving auxiliary problem.
x3 = 2 + x0 � 2x1 � x2
x4 = �12 + x0 + 3x1 + 4x2
w = 0 � x0
Entering: x0. Leaving: x4.
x3 = 14 + x4 � 5x1 � 5x2
x0 = 12 + x4 � 3x1 � 4x2
w = �12 � x4 + 3x1 + 4x2
3 de 3
0,3
0,3
0,3
0,5
0,5
Pesquisa Operacional I - AD2
Entering: x1. Leaving: x3.
x1 =
14
5 +
1
5x4 �
1
5x3 � x2
x0 =
18
5 +
2
5x4 +
3
5x3 � x2
w = � 185 �
2
5x4 �
3
5x3 + x2
Entering: x2. Leaving: x1.
x2 =
14
5 +
1
5x4 �
1
5x3 � x1
x0 =
4
5 +
1
5x4 +
4
5x3 + x1
w = � 45 �
1
5x4 �
4
5x3 � x1
The original problem is infeasible.
(c) (1,0)
max x1 + x2
x1 + 4x2 � 4
3x1 + x2 = 1
x1, x2 � 0
x3 = �4 + x1 + 4x2
x4 = 1 � 3x1 � x2
x5 = �1 + 3x1 + x2
z = 0 + x1 + x2
The initial dictionary is infeasible, solving auxiliary problem.
x3 = �4 + x0 + x1 + 4x2
x4 = 1 + x0 � 3x1 � x2
x5 = �1 + x0 + 3x1 + x2
w = 0 � x0
Entering: x0. Leaving: x3.
x0 = 4 + x3 � x1 � 4x2
x4 = 5 + x3 � 4x1 � 5x2
x5 = 3 + x3 + 2x1 � 3x2
w = �4 � x3 + x1 + 4x2
Entering: x1. Leaving: x4.
x0 =
11
4 +
3
4x3 +
1
4x4 �
11
4 x2
x1 =
5
4 +
1
4x3 �
1
4x4 �
5
4x2
x5 =
11
2 +
3
2x3 �
1
2x4 �
11
2 x2
w = � 114 �
3
4x3 �
1
4x4 +
11
4 x2
4 de 3
0,5
0,5
0,3
0,14
0,14
Pesquisa Operacional I - AD2
Entering: x2. Leaving: x0.
x2 = 1 +
3
11x3 +
1
11x4 �
4
11x0
x1 = 0 � 111x3 �
4
11x4 +
5
11x0
x5 = 0 � x4 + 2x0
w = 0 � x0
Back to the original problem.
x2 = 1 +
3
11x3 +
1
11x4
x1 = 0 � 111x3 �
4
11x4
x5 = 0 � x4
z = 1 +
2
11x3 �
3
11x4
Entering: x3. Leaving: x1.
x2 = 1 � 3x1 � x4
x3 = 0 � 11x1 � 4x4
x5 = 0 � x4
z = 1 � 2x1 � x4
The optimal value: 1. An optimal solution: (0, 1).
5 de 3
0,14
0,14
0,14