MetodoSimplextabelas

Prévia do material em texto

Pesquisa Operacional
Método Simplex em 
Tabelas
Método simplex em tabelas
� Maneira prática para trabalhar.
� Interessante para compreensão do método
� Esta forma é adequada para resolver problemas com 
dezenas de restrições e variáveis ;
� O método simplex em tabelas utiliza implicitamente a 
inversa da matriz básica e calcula todas as direções 
simplex por iteração, embora apenas uma delas seja 
utilizada pela variável que entra na base. 
Método simplex em tabelas
� Considere o problema na forma padrão.
Minimizar f(x) = cTx 
sujeito a: Ax = b 
 x ≥≥≥≥ 0. 
Método simplex em tabelas
� Considere o exemplo
Minimizar f(x1, x2) = − x1 − 2x2 
sujeito a: x1 + x2 ≤ 6 
 x1 − x2 ≤ 4 
− x1 + x2 ≤ 4 
x1>=0, x2>=0 
Método simplex em tabelas
� Considere o exemplo
x3 = b1 − a11 x1 − a12 x2 = 6 − x1 − x2 
x4 = b2 − a21 x1 − a22 x2 = 4 − x1 + x2 
x5 = b3 − a13 x1 − a32 x2 = 4 + x1 − x2 
x1 = 0, x2 = 0 x3 = 6, x4 = 4, x5 = 4 
Método simplex em tabelas
� Considere o exemplo
Método simplex em tabelas
� Considere o exemplo
x3 = b1 − a12 x2 = 6 − x2 ≥ 0 (a12 > 0) 
x4 = b2 − a22 x2 = 4 + x2 ≥ 0 (a22 < 0) 
x5 = b3 − a32 x2 = 4 − x2 ≥ 0 (a32 > 0) 
Observe que x4 aumenta com 
o crescimento de x2. X4 não é candidata
a deixar a base.
Simplex em tabelas
Método simplex em tabelas
� Voltando ao exemplo
( )
( )
( ) )(
1
404
base)dasainão(06
1
606
5225
424
223
basedasaixbloqueiolinhaxxx
xxx
xxx
≤⇒≥−=
>+=
≤⇒≥−=
Simplex em tabelas
Simplex em tabelas
Simplex em tabelas
Simplex em tabelas
Minimizar f(x1, x2) = − x1 − 2x2 
sujeito a: x1 + x2 ≤ 6 
 x1 − x2 ≤ 4 
− x1 + x2 ≤ 4 
x1>=0, x2>=0 
Algoritmo Simplex em tabelas