Programação Linear 07

Prévia do material em texto

ENP153 –Programação Linear
Aula 07 – Método Simplex
MÉTODO SIMPLEX DE RESOLUÇÃO
 min𝑍 = 2𝑥1 − 3𝑥2 − 4𝑥3
 s.t.
 𝑥1 + 5𝑥2 − 𝑥3 ≤ 15
 𝑥1 + 𝑥2 + 𝑥3 ≤ 5
 5𝑥1 − 6𝑥2 + 4𝑥3 ≤ 10
 𝑥1, 𝑥2, 𝑥3 ≥ 0
1º PASSO – FORMA PADRÃO
 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
2º PASSO –CRIAR TABELA
2º PASSO –CRIAR TABELA
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
2º PASSO –CRIAR TABELA
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒
𝑳 𝟐 𝒙𝟓
𝑳 𝟑 𝒙𝟔
𝑳 𝟒
𝐿 1
𝐿 2
𝐿 3
𝐿 4
2º PASSO –CRIAR TABELA
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 1 5 -3 1 0 0 15
𝑳 𝟐 𝒙𝟓
𝑳 𝟑 𝒙𝟔
𝑳 𝟒
2º PASSO –CRIAR TABELA
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 1 5 -3 1 0 0 15
𝑳 𝟐 𝒙𝟓 1 1 1 0 1 0 5
𝑳 𝟑 𝒙𝟔
𝑳 𝟒
2º PASSO –CRIAR TABELA
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 1 5 -3 1 0 0 15
𝑳 𝟐 𝒙𝟓 1 1 1 0 1 0 5
𝑳 𝟑 𝒙𝟔 5 -6 4 0 0 1 10
𝑳 𝟒
2º PASSO –CRIAR TABELA
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
3º PASSO –ENTRA NA BASE
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
mais negativo
3º PASSO –ENTRA NA BASE
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
4º PASSO –SAI DA BASE
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟔
𝑳 𝟏 𝒙𝟒 1 5 -3 1 0 0 15/-3 = 
-5
𝑳 𝟐 𝒙𝟓 1 1 1 0 1 0 5/1 = 5
𝑳 𝟑 𝒙𝟔 5 -6 4 0 0 1 10/4 = 
2.5
𝑳 𝟒 2 -3 -4 0 0 0 0
menor não negativo
4º PASSO –SAI DA BASE
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
5º PASSO –PERMUTAR VARIÁVEIS
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
𝐿 1 → 𝐿 1 + 3𝐿 3
𝐿 2 → 𝐿 2 − 𝐿 3
𝐿 4 → 𝐿 4 + 4𝐿 3
5º PASSO –PERMUTAR VARIÁVEIS
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
5º PASSO –PERMUTAR VARIÁVEIS
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
o processo iterativo continua até que não se possuam mais 
números negativos em L(4)
5º PASSO –PERMUTAR VARIÁVEIS
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
EXERCÍCIO PARA RESOLUÇÃO
MÉTODO SIMPLEX DE DUAS FASES
 Existem momento em que a solução inicial não pode ser
referenciada pela origem. Para estes casos, o método
simples necessita sofrer alguns ajustes iniciais para sua
resolução
 O procedimento para iniciar a resolução desses tipos de
problemas é utilizar, inicialmente, variáveis artificiais nas
restrições do tipo ≥ e = , para que posteriormente estas
sejam descartadas
MÉTODO SIMPLEX DE DUAS FASES
 m𝑎𝑥 𝑍 = 𝑥1 + 2𝑥2
 s.t.
 𝑥1 ≤ 2
 𝑥2 ≤ 2
 𝑥1 + 𝑥2 ≥ 3
 𝑥1, 𝑥2 ≥ 0
MÉTODO SIMPLEX DE DUAS FASES
 m𝑎𝑥 𝑍 = 𝑥1 + 2𝑥2 + 0𝑥3 + 0𝑥4 + 0𝑥5
 s.t.
 𝑥1 + 𝑥3 = 2
 𝑥2 + 𝑥4 = 2
 𝑥1 + 𝑥2 − 𝑥5 = 3
 𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5 ≥ 0
MÉTODO SIMPLEX DE DUAS FASES
MÉTODO SIMPLEX DE DUAS FASES
 Primeira fase: o procedimento utilizará o simplex para
buscar uma base viável da solução
 Segunda fase: de posse da base calculada na primeira fase,
deve-se aplicar o método simplex tradicional em busca do
ótimo para o problema
MÉTODO SIMPLEX DE DUAS FASES
 Primeira fase (Criar problema auxiliar 𝑃′)
 Introduzir variáveis de folga e variáveis artificiais
 Variáveis de folga ou excesso: introduzidas quando há restrições do
tipo ≥ ou ≤
 Variáveis artificiais: introduzidas quando há restrições do tipo ≥
ou =
 Criar função objetivo artificial
𝑍𝑎 =෍
𝑖
𝑥𝑖
𝑎 ∀𝑖
 Variáveis básicas iniciais: variáveis de folga associadas às restrições
≤ e variáveis artificiais
 Objetivo da primeira fase: minimizar a função objetivo artificial
MÉTODO SIMPLEX DE DUAS FASES
 m𝑎𝑥 𝑍 = 𝑥1 + 2𝑥2 + 0𝑥3 + 0𝑥4 + 0𝑥5 + 0𝑥1
𝑎
 s.t.
 𝑥1 + 𝑥3 = 2
 𝑥2 + 𝑥4 = 2
 𝑥1 + 𝑥2 − 𝑥5 + 𝑥1
𝑎 = 3
 𝑥1, 𝑥2, 𝑥3, 𝑥4, 𝑥5, 𝑥1
𝑎 ≥ 0
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟑 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 1 1 0 0 -1 1 3
𝑳 𝟒 𝒁𝒂 0 0 0 0 0 1 0
𝑳 𝟓 𝒁 1 2 0 0 0 0 0
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟑 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 1 1 0 0 -1 1 3
𝑳 𝟒 𝒁𝒂 0 0 0 0 0 1 0
𝑳 𝟓 𝒁 1 2 0 0 0 0 0
Como 𝑥1
𝑎 esta na base, deve-se anular seu coeficiente na função 
objetivo artificial, de forma a colocar o PPL na forma adequada
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟑 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 1 1 0 0 -1 1 3
𝑳 𝟒 𝒁𝒂 0 0 0 0 0 1 0
𝑳 𝟓 𝒁 1 2 0 0 0 0 0
𝐿 4 → −𝐿 3 + 𝐿 4
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟑 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 1 1 0 0 -1 1 3
𝑳 𝟒 𝒁𝒂 -1 -1 0 0 1 0 -3
𝑳 𝟓 𝒁 1 2 0 0 0 0 0
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟑 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 1 1 0 0 -1 1 3
𝑳 𝟒 𝒁𝒂 -1 -1 0 0 1 0 -3
𝑳 𝟓 𝒁 1 2 0 0 0 0 0
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟑 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 1 1 0 0 -1 1 3
𝑳 𝟒 𝒁𝒂 -1 -1 0 0 1 0 -3
𝑳 𝟓 𝒁 1 2 0 0 0 0 0
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟑 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 1 1 0 0 -1 1 3
𝑳 𝟒 𝒁𝒂 -1 -1 0 0 1 0 -3
𝑳 𝟓 𝒁 1 2 0 0 0 0 0
𝐿 4 → 𝐿 1 + 𝐿 4𝐿 3 → −𝐿 1 + 𝐿 3 𝐿 5 → −𝐿 1 + 𝐿 5
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 0 1 -1 0 -1 1 1
𝑳 𝟒 𝒁𝒂 0 -1 1 0 1 0 -1
𝑳 𝟓 𝒁 0 2 -1 0 0 0 -2
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 0 1 -1 0 -1 1 1
𝑳 𝟒 𝒁𝒂 0 -1 1 0 1 0 -1
𝑳 𝟓 𝒁 0 2 -1 0 0 0 -2
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 0 1 -1 0 -1 1 1
𝑳 𝟒 𝒁𝒂 0 -1 1 0 1 0 -1
𝑳 𝟓 𝒁 0 2 -1 0 0 0 -2
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 1 0 1 0 0 2
𝑳 𝟑 𝒙𝟏
𝒂 0 1 -1 0 -1 1 1
𝑳 𝟒 𝒁𝒂 0 -1 1 0 1 0 -1
𝑳 𝟓 𝒁 0 2 -1 0 0 0 -2
𝐿 4 → 𝐿 3 + 𝐿 4𝐿 2 → −𝐿 3 + 𝐿 2 𝐿 5 → −2𝐿 2 + 𝐿 5
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 0 1 1 1 -1 1
𝑳 𝟑 𝒙𝟐 0 1 -1 0 -1 1 1
𝑳 𝟒 𝒁𝒂 0 0 0 0 0 1 0
𝑳 𝟓 𝒁 0 0 1 0 2 -2 -4
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓 𝒙𝟏
𝒂
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 0 2
𝑳 𝟐 𝒙𝟒 0 0 1 1 1 -1 1
𝑳 𝟑 𝒙𝟐 0 1 -1 0 -11 1
𝑳 𝟒 𝒁𝒂 0 0 0 0 0 1 0
𝑳 𝟓 𝒁 0 0 1 0 2 -2 -4
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 2
𝑳 𝟐 𝒙𝟒 0 0 1 1 1 1
𝑳 𝟑 𝒙𝟐 0 1 -1 0 -1 1
𝑳 𝟒 𝒁 0 0 1 0 2 -4
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 2
𝑳 𝟐 𝒙𝟒 0 0 1 1 1 1
𝑳 𝟑 𝒙𝟐 0 1 -1 0 -1 1
𝑳 𝟒 𝒁 0 0 1 0 2 -4
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 2
𝑳 𝟐 𝒙𝟒 0 0 1 1 1 1
𝑳 𝟑 𝒙𝟐 0 1 -1 0 -1 1
𝑳 𝟒 𝒁 0 0 1 0 2 -4
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 2
𝑳 𝟐 𝒙𝟒 0 0 1 1 1 1
𝑳 𝟑 𝒙𝟐 0 1 -1 0 -1 1
𝑳 𝟒 𝒁 0 0 1 0 2 -4
𝐿 3 → 𝐿 2 + 𝐿 3 𝐿 4 → −2𝐿 2 + 𝐿 4
MÉTODO SIMPLEX DE DUAS FASES
VB 𝒙𝟏 𝒙𝟐 𝒙𝟑 𝒙𝟒 𝒙𝟓
𝑳 𝟏 𝒙𝟏 1 0 1 0 0 2
𝑳 𝟐 𝒙𝟓 0 0 1 1 1 1
𝑳 𝟑 𝒙𝟐 0 1 0 1 0 2
𝑳 𝟒 𝒁 0 0 -1 -2 0 -6
𝑆𝑜𝑙𝑢çã𝑜 ó𝑡𝑖𝑚𝑎 → 𝑥∗ = 2,2 → 𝑍∗ = 6
INTERPRETAÇÃO GEOMÉTRICA – 1º FASE
INTERPRETAÇÃO GEOMÉTRICA – 1º FASE
𝟎, 𝟎 → 𝒔𝒐𝒍𝒖çã𝒐 𝒊𝒏𝒊𝒄𝒊𝒂𝒍
INTERPRETAÇÃO GEOMÉTRICA – 1º FASE
INTERPRETAÇÃO GEOMÉTRICA – 1º FASE
INTERPRETAÇÃO GEOMÉTRICA – 2º FASE
INTERPRETAÇÃO GEOMÉTRICA – 2º FASE
𝒙∗ → 𝒔𝒐𝒍𝒖çã𝒐 ó𝒕𝒊𝒎𝒂