Lista Simplex Tabular e método das 2 fases

Prévia do material em texto

LISTA DE EXERC´ICIOS 4 - Programac¸a˜o Linear I
SIMPLEX TABULAR - ME´TODO DAS DUAS FASES
Luziane F. de Mendonc¸a
1. Use o me´todo Simplex para resolver
min −5x1 − 4x2 − 3x3
s.a 2x1 + 3x2 + x3 ≤ 5
4x1 + x2 + 2x3 ≤ 11
x1, x2, x3 ≤ 0
Em seguida, a partir da tabela o´tima dessa problema, escreva as matrizes B, B−1 e N
e os vetores yj, cB, cN . Verifique que a soluc¸a˜o o´tima e´ B
−1b e que z∗ = cTBB
−1b.
2. (Klee-Minty problem) Resolva o seguinte problema usando o algoritmo simplex tabular;
observe que todas as possibilidades para a construc¸a˜o sa soluc¸a˜o ba´sica ocorre durante
as iterac¸o˜es
min −100x1 − 10x2 − x3
s.a x1 x3 ≤ 1
20x1 + x2 ≤ 100
200x1 + 20x2 + x3 ≤ 10000
x1, x2, x3 ≤ 0
3. A tabela a seguir e´ obtida na soluc¸a˜o (tabela o´tima) de um PL:
Basic z x1 x2 x3 x4 x5 x6 x7 Solution
z 1 0 5/3 4/3 1 0 0 -5/3 -12
0 0 4/3 2/3 0 1 0 -1/3 4
0 0 1/3 2/3 1 0 1 -1/3 10
0 1 -1/3 1/6 1/2 0 0 1/6 4
(a) Quais sa˜o as varia´veis ba´sicas? Qual e´ a soluc¸a˜o ba´sica que a tabela representa?
Ela e´ o´tima? Explique esta u´ltima resposta, escrevendo z em func¸a˜o das varia´veis na˜o
ba´sicas.
(b) Comec¸ando com essa tabela, fac¸a os ca´lculos necessa´rios ate´ chegar a` tabela o´tima.
(c) A partir da tabela o´tima, escreva tanto a func¸a˜o objetivo como as varia´veis ba´sicas
em func¸a˜o das varia´veis na˜o ba´sicas.
4. Resolva o seguinte problema usando o me´todo das duas fases:
min −x1 − 2x2
s.a −x1 + x2 ≤ 2
4x1 + x2 ≤ 12
3x1 + 4x2 ≤ 20
x1 + x2 ≥ 4
x1, x2 ≥ 0
5. Considere a tabela a seguir para um problema de minimizac¸a˜o, onde todas as restric¸o˜es
eram do tipo ≤ e x3, x4 e x5 sa˜o varia´veis de folga.
z x1 x2 x3 x4 x5 RHS
z 1 0 A 0 B 0 F
? 0 1 -2 0 1 0 C
? 0 0 -3 1 -2 0 D
? 0 0 0 1 3 1 E
Suponha que A < 0, B ≤ 0, e C, D, E ≥ 0.
(a) Determine B−1.
(b) Determine B.
(c) Essa e´ a tabela o´tima?
(d) Escreva a tabela inicial.
(e) Explicite o valor de cBB
−1.
Agora, suponha que A > 0, B ≤ 0; e C, D, E ≥ 0.
(f) Essa nova tabela e´ o´tima?
(g) Escreva uma das direc¸o˜es extremas
(h) Adote A = 5 e F = −10. Escreva a soluc¸a˜o via´vel cuja imagem vale z = −150.
6. A tabela a seguir foi obtida em uma das iterac¸o˜es do me´todo simplex quando aplicado
para resolver o PL (minizac¸a˜o) cuja func¸a˜o objetivo e´ −2x4 − x5 − 2x6 e x1, x2 e x3
sa˜o as varia´veis de folga.
z x1 x2 x3 x4 x5 x6 RHS
z 1 B C 0 0 H G -12
x6 0 2 0 -14/3 0 1 1 A
x2 0 3 D 2 0 5/2 0 5
x4 0 0 E F 1 2 0 0
(a) Encontre os valores das varia´veis desconhecidas (de A ate´ H);
(b) Encontre B−1;
7. A tabela inicial e a tabela atual (depois de algumas iterac¸o˜es) encontram-se abaixo,
para um problema de minimizac¸a˜o. Encontre os valores das varia´veis A ate´ N .
Tabela Inicial:
z x1 x2 x3 x4 x5 RHS
z 1 A 1 -3 0 0 0
? 0 B C D 1 0 6
? 0 -1 2 E 0 1 1
Tabela Atual:
z x1 x2 x3 x4 x5 RHS
z 1 0 -1/3 J K L N
? 0 G 2/3 2/3 1/3 0 F
? 0 H I -1/3 1/3 1 M