Programação Linear 09

Prévia do material em texto

ENP153 –Programação Linear
Aula 09 – Método Simplex Revisado
SIMPLEX REVISADO
 O método simplex revisado consiste em uma maneira de
aplicarmos o método a um problema de programação linear,
de forma a reduzir a quantidade de operações realizadas
 Se um problema possuir muito mais variáveis do que
restrições (se 𝑛 for muito maior do que 𝑚) os pivôs irão
aparecer em poucas colunas da matriz, como as outras
colunas não são usadas explicitamente, não é necessário
que atualizemos toda a matriz a cada iteração
SIMPLEX REVISADO
 Para entendermos a teoria do método simplex revisado,
precisamos reformular o método simplex, já apresentado
anteriormente na forma matricial
SIMPLEX REVISADO
 Dada uma solução básica inicial para o problema primal,
chamamos de 𝐵 a submatriz da matriz original 𝐴 composta
pelas 𝑚 colunas de 𝐴 correspondentes as variáveis básicas
dessa solução e de 𝐷 a submatriz composta pelas colunas
restantes. Vamos assumir que 𝐵 é composta pelas 𝑚
primeiras colunas de 𝐴. Então, separamos 𝐴, 𝑥 e 𝑐:
SIMPLEX REVISADO
 Deste modo, o problema na forma padrão se torna:
SIMPLEX REVISADO
𝑐𝐵𝐵
−1
𝐵−1
𝑧 = 𝑐𝐵𝐵
−1𝑏
ത𝑏
𝑐𝐵𝐵
−1𝑎𝑘 − 𝑐𝑘
ത𝑦 = 𝐵−1𝑎𝑘
𝑒𝑛𝑡𝑟𝑎 𝑛𝑎 𝑏𝑎𝑠𝑒 → 𝑐𝐵𝐵
−1𝑎𝑘 − 𝑐𝑘
𝑠𝑎𝑖 𝑑𝑎 𝑏𝑎𝑠𝑒 →
ത𝑏
ത𝑦
SIMPLEX REVISADO
 min𝑍 = 2𝑥1 − 3𝑥2 − 4𝑥3
 s.t.
 𝑥1 + 5𝑥2 − 𝑥3 + 𝑥4 = 15
 𝑥1 + 𝑥2 + 𝑥3 + 𝑥5 = 5
 5𝑥1 − 6𝑥2 + 4𝑥3 + 𝑥6 = 10
 𝑥1, 𝑥2, 𝑥3 ≥ 0
SIMPLEX REVISADO
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 1 5 -3 1 0 0 15
𝑳 𝟐 𝒙𝟓 1 1 1 0 1 0 5
𝑳 𝟑 𝒙𝟔 5 -6 4 0 0 1 10
𝑳 𝟒 2 -3 -4 0 0 0 0
SIMPLEX REVISADO
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 1 5 -3 1 0 0 15
𝑳 𝟐 𝒙𝟓 1 1 1 0 1 0 5
𝑳 𝟑 𝒙𝟔 5 -6 4 0 0 1 10
𝑳 𝟒 2 -3 -4 0 0 0 0
SIMPLEX REVISADO
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 4,75 0,50 0 1 0 0,75 22,50
𝑳 𝟐 𝒙𝟓 -0,25 2,50 0 0 1 -0,25 2,50
𝑳 𝟑 𝒙𝟑 1,25 -1,50 1 0 0 0,25 2,50
𝑳 𝟒 7 -9 0 0 0 1 10
SIMPLEX REVISADO
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 4,75 0,50 0 1 0 0,75 22,50
𝑳 𝟐 𝒙𝟓 -0,25 2,50 0 0 1 -0,25 2,50
𝑳 𝟑 𝒙𝟑 1,25 -1,50 1 0 0 0,25 2,50
𝑳 𝟒 7 -9 0 0 0 1 10
SIMPLEX REVISADO
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 4,80 0 0 1 -0,20 0,80 22
𝑳 𝟐 𝒙𝟐 -0,10 1 0 0 0,40 -0,10 1
𝑳 𝟑 𝒙𝟑 1,10 0 1 0 0,60 0,10 4
𝑳 𝟒 6,10 0 0 0 3,60 0,10 19