Pesquisa Operacional SIMPLEX - Exercícios e resolução

Prévia do material em texto

pesquisa operacional i
EXERCÍCIOS DE pORtfólIO
2
ExErcício 1
Resolva graficamente o problema hachurando o espaço 
de soluções viáveis, determinar o ponto ótimo e os valo-
res de x1, x2 e z, responda também se identificou alguma 
restrição redundante:
Min z = 3X1 + 2,5X2
Sujeito a: 
4X1 + 5X2 ≤ 800
X2 ≥ 80
X1 + X2 ≥ 170
4X1 + 6X2 ≥ 170
X1 ≥ 60
Pesquisa Operacional I / Aulas 5–8 Exercícios de Portfólio 2
ExErcício 2
Resolva pelo método simplex o seguinte PPL.
MAX Z = 10X1 + 20X2 + 30X3
s.a.
2X1 + 2X2 + 4X3 ≤ 300
4X2 + 3X3 ≤ 200
X1 ≤ 20
4X1 + 3X2 ≤ 50
X1, X2, X3 ≥ 0
Pesquisa Operacional I / Aulas 5–8 Exercícios de Portfólio 3
gabarito
ExErcício 1
Restrição Redundante: 4x1 + 6x2 ≥ 170, pois a delimitação que faz não di-
minui o espaço de soluções viáveis.
170
160
150
140
130
120
110
100
90
80
70
60
50
40
30
20
10
0
20 40 60 80 100 120 140 160 180 200
I
A
D
K
H
C
G
J BNMO
L
F
Como aparece na Tabela a seguir, o ponto K no gráfico refere-se ao vértice 
ótimo, com X1 = 60, X2 = 110 e Z* = 455.
ponto coordenada x (x1) coordenada y (x2) valor da função objetivo (z)
O 0 0 0
A 0 160 400
B 200 0 600
C 100 80 500
D 50 120 450
E 60 112 460
F 0 80 200
G 90 80 470
H 60 80 380
I 0 170 425
J 170 0 510
K 60 110 455
L 0 85/3 425/6
M 85/2 0 255/2
N 60 0 180
Pesquisa Operacional I / Aulas 5–8 Exercícios de Portfólio 4
ExErcício 2
Forma Padrão do simplex:
MAX Z -10X1 - 20X2 - 30X3
s.a.
2X1 + 2X2 + 4X3 + X4 = 300
4X2 + 3X3 + X5 = 200
X1 + X6 = 20
4X1 + 3X2 + X7 = 50
X1, X2, X3, X4, X5, X6, X7 ≥ 0
Variável que sai da base Variável que entra na base Número Pivô
vB X1 X2 X3 F1 F2 F3 F4 VSM quociente
F1 2 2 4 1 0 0 0 300 300/4
F2 0 4 3 0 1 0 0 200 200/3
F3 1 0 0 0 0 1 0 20 -
F4 4 3 0 0 0 0 1 50 -
Z -10 -20 -30 0 0 0 0 0
vB X1 X2 X3 F1 F2 F3 F4 vsm quociente
F1 2 -10/3 0 1 -4/3 0 0 100/3 33.333/2
X3 0 4/3 1 0 1/3 0 0 200/3 -
F3 1 0 0 0 0 1 0 20 20/1
F4 4 3 0 0 0 0 1 50 50/4
Z -10 20 0 0 10 0 0 2000
Tabela 1.
Tabela 2.
Pesquisa Operacional I / Aulas 5–8 Exercícios de Portfólio 5
vB X1 X2 X3 F1 F2 F3 F4 vsm
F1 0 -29/6 0 1 -4/3 0 -1/2 25/3
X3 0 4/3 1 0 1/3 0 0 200/3
F3 0 -3/4 0 0 0 1 -1/4 15/2
X1 1 3/4 0 0 0 0 1/4 25/2
Z 0 55/2 0 0 10 0 5/2 2125
Operações realizadas na Tabela 2 que gerou a Tabela 3:
linha pivô 
(linha 4) linha 1 linha 2
50
4 = 
25
2
100
3 
- (2 × 252 ) = 
25
3
200
3 - (0 × 
25
2 ) = 
200
3
4
4 = 1 2 - (2 × 1) = 0 0 - (0 × 1) = 0
3
4 = 
3
4 - 
10
3 
- (2 × 34 ) = - 
29
6
4
3 - (0 × 
3
4 ) = 
4
3
0
4 = 0 0 - (2 × 0) = 0 1 - (0 × 0) = 1
0
4 = 0 1 - (2 × 0) = 1 0 - (0 × 0) = 0
0
4 = 0 - 
4
3 - (2 × 0) = - 
4
3
1
3 - (0 × 0) = 
1
3
0
4 = 0 0 - (2 × 0) = 0 0 - (0 × 0) = 0
1
4 = 
1
4 0 - (2 × 
1
4 ) = - 
1
2 0 - (0 × 
1
4 ) = 0
Tabela 3. Encontrada 
a solução ótima 
com z= 2125.
Pesquisa Operacional I / Aulas 5–8 Exercícios de Portfólio 6
linha 3 linha z
20 - (1 × 252 ) = 
15
2 2000 - (-10 × 
25
2 ) = 2125
1 - (1 × 1) = 0 -10 - (-10 × 1) = 0
0 - (1 × 34 ) = - 
3
4 20 - (-10 × 
3
4 ) = 
55
2
0 - (1 × 0) = 0 0 - (-10 × 0) = 0
0 - (1 × 0) = 0 0 - (-10 × 0) = 0
0 - (1 × 0) = 0 10 - (-10 × 0) = 10
1 - (1 × 0) = 1 0 - (-10 × 0) = 0
0 - (1 × 14 ) = - 
1
4 0 - (-10 × 
1
4 ) = 
5
2