Método Simplex

Prévia do material em texto

MÉTODO SIMPLEX
UNIVERSIDADE FEDERAL DO RIO GRANDE DO NORTE
DEPARTAMENTO DE ENGENHARIA DE PRODUÇÃO
PRO1801 – PESQUISA OPERACIONAL l
DOCENTE: CLAUDIA APARECIDA CAVALHEIRO FRANCISCO 
MONITOR: ALISSON SAMPAIO DE LIMA
AULA 12
• Algoritmo Simplex – Método das Duas Fases
Passo 0: Achar uma solução viável básica inicial. 
Passo 1: Verificar se a solução atual é ótima. Se for, pare. 
Passo 2: Determinar a variável não-básica que deve entrar na base 
(aquela que apresentar a maior contribuição para a função objetivo).
Passo 3: Determinar a variável básica que deve sair da base (Cálculo do 
Bloqueio: 𝑀𝑖𝑛
𝑏𝑗
𝑎𝑖𝑗
). 
Passo 4: Achar a nova solução viável básica, realizando o pivoteamento
(transformar o sistema em outro equivalente focado no novo vértice) e 
voltar ao Passo 1
Passo 0: Achar uma solução viável básica inicial.
E o que fazer quando não encontramos uma 
solução básica inicial??
Vai acontecer quando tiver restrições do tipo ‘≥’ e/ou ‘=‘
O ponto (0,0) não pertence ao 
conjunto solução do problema
Encontraremos uma solução básica inicial com o uso do 
Método das Duas Fases.
FASE 1:
• Incluiremos variáveis artificiais nas restrições que se façam 
necessário (para obtermos a matriz identidade do quadro do simplex)
• Realizaremos as iterações/pivoteamento do simplex com o objetivo 
de retirar as variáveis artificiais do modelo.
• Modelo sem variáveis artificiais (variáveis artificiais fora da base, com 
valores iguais a zero. Inicia-se a FASE 2.
FASE 2:
• Resolver o simplex normalmente (MAX ou MIN)
s1
s2
5 2 0 0
1 1 0
0 1
3
Max Z=5x1+2x2
s.a.
x1 ≤ 3
x2 ≤ 4
x1+2x2 ≥ 9
x1,x2≥0
Método das Duas Fases
FORMA PADRÃO
Max Z=5x1+2x2
s.a.
x1 + s1 = 3
x2 + s2 = 4
x1+2x2 – s3 = 9
x1,x2,s1,s2,s3 ≥0
b
Z
X
1
X2 s1 s2 s3
0
0 0
0 1 0 4
1 2 0 0 -1 9
Inclusão da Variável Artificial
Max Z=5x1+2x2
s.a.
x1 + s1 = 3
x2 + s2 = 4
x1+2x2 – s3 +a1= 9
x1,x2,s1,s2,s3 ≥0
a1= 9 - x1- 2x2 + s3
W= a1
Novo 
OBJETIVO 
MINIMIZAR W
s1
s2
5 2 0 0
1 1 0
0 1
3
b
Z
X
1
X2 s1 s2 s3
0
0 0
0 1 0 4
1 2 0 0 -1 9a1
a1
0
0
0
1
-9-1 -2 0100W
s1
s
2
5 2 0 0
1 1 0
0 1
3
b
Z
X
1
X2 s1 s2 s3
0
0 0
0 1 0 4
1 2 0 0 -1 9a1
a1
0
0
0
1
-9-1 -2 0100W
Qual a variável entra na base?
Qual a variável sai da base?
Bloqueio = Min {
4
1
; 
9
2
}
Novo OBJETIVO 
MINIMIZAR W
Qual a variável entra na base?
Qual a variável sai da base?
Bloqueio = Min {
3
1
; 
1
1
}
s1
x
2
5 0 0 -2
1 1 0
0 1
3
b
Z
X
1
X2 s1 s2 s3
0
0 0
0 1 0 4
1 0 0 -2 -1 1a1
a1
0
0
0
1
-1-1 0 0120W
-8
s1
x
2
0 0 0 8
0 1 2
0 1
2
b
Z
X
1
X2 s1 s2 s3
5
0 1
0 1 0 4
1 0 0 -2 -1 1X1
a1
-5
-1
0
1
00 0 1000W
-13
INÍCIO DA FASE 2
MAXIMIZAR Z
SOLUÇÃO INICIAL
X1= 1 Z= 13
X2= 4
S1= 2
S2= 0
S3= 0
Método das Duas Fases
s1
x
2
0 0 0 8
0 1 2
0 1
2
b
Z
X
1
X2 s1 s2 s3
5
0 1
0 1 0 4
1 0 0 -2 -1 1X1
-13
FASE 2
MAXIMIZAR Z
Qual a variável entra na base?
Qual a variável sai da base?
Bloqueio = Min {
2
2
; 
4
1
}
s2
x
2
0 0 -4 0
0 1/2 1
0 1
1
b
Z
X
1
X2 s1 s2 s3
1
0 1/
2-1/2 0 -
1/2
3
1 0 1 0 0 3X1
-21
Qual a variável entra na base?
Qual a variável sai da base?
Bloqueio = Min {
1
1/2
}
s3
x
2
0 0 -5 -2
0 1 2
0 1
2
b
Z
X
1
X2 s1 s2 s3
0
0 1
0 1 0 4
1 0 1 0 0 3X1
-23
Chegamos no ótimo!
SOLUÇÃO ÓTIMA
X1= 3
X2= 4
S1= 0
S2= 0
S3= 2
Z= 23
Método das Duas Fases
OBSERVAÇÃO:
• Se W > 0, o problema original seria inviável e o processo de otimização terminaria.
• Se o problema de programação linear é inviável, não há Fase II
• Deveremos procurar excluir a variável artificial da base. 
• Isto pode ser feito através do método das Fase I e Fase II. 
• Na Fase I deve-se tentar excluir as variáveis artificiais da base 
resolvendo o problema de programação linear com uma nova 
função objetivo.
• A função objetivo original Z deverá ser substituída por uma nova 
função formada pela soma das variáveis artificiais. 
OBJETIVO FASE 1: MIN W =σ𝑎𝑟𝑡𝑖𝑓𝑖𝑐𝑖𝑎𝑖𝑠
Max Z=x1+2x2
s.a.
2x1+2x2 = 100
x1+3x2 = 10
x1,x2≥0
Já está na 
FORMA PADRÃO
1 2
2
1 3
100
b
Z
X
1
X2
2
10
Inclusão das Variáveis Artificiais
Problema Inviável / Infactível
Max Z=x1+2x2
s.a.
2x1+2x2 +a1 = 100
x1+3x2 +a2 = 10
x1,x2≥0
a1= 100 - 2x1- 2x2
a2= 10 - x1- 3x2
W= a1+a2= 110 - 3x1- 5x2
Entra x2: Objetivo MIN W
a1
-2
1/
3
0
-1/30
W
2/3 0
4/
3
1/
3
1
80
b
Z
X
1
X2
0
10/
3
a1
a2
-
4/3
0 5/
3
1
0X2
-10/3
-80
a1
0
1
0
00
W
1 2
2
1 3
100
b
Z
X
1
X2
2
10
a1
a2
a2
-3 -5 0
1
0
-
110
a1
-10/3
1
0
-10
W
0 -2
0
1 3
200/
3
b
Z
X
1
X2
-4
10
a1
a2
0 4 3
1
0X1
-10
-200/3