O Metodo Simplex e Analise de Sensibilidade

Prévia do material em texto

O MÉTODO SIMPLEX E 
ANÁLISE DE SENSIBILIDADE
Modelo de PL em forma de equação
 Todas as restrições são equações cujos lados 
direitos são não-negativos
 Todas as variáveis são não-negativas
Conversão de desigualdades em 
equações
 Uma desigualdade do tipo
a1x1 + a2x2 + a3x3 + . . . + aNxN ≤ b
 É equivalente a uma igualdade do tipo
a1x1 + a2x2 + a3x3 + . . . + aNxN + s = b
s ≥ 0
Exemplo (Reddy Micks)
 A desigualdade
 6x1 + 4x2 ≤ 24
 É equivalente à igualdade
 6x1 + 4x2 + s1 = 24
 s1 ≥ 0
 Em
 x1 = 3, x2 = 1
 6.3 + 4.1 = 22 ≤ 24, ou
 s1 = 24 – 22 = 2 ≥ 0
Exemplo (Problema da Dieta)
 A desigualdade
 x1 + x2 ≥ 800
 É equivalente à igualdade
 x1 + x2 – s1 = 800
 s1 ≥ 0
 Em
 x1 = 300, x2 = 600
 300 + 600 = 900 ≥ 800, ou
 s1 = 900 – 800 = 100 ≥ 0
Não negatividade do lado direito
 A restrição
 -x1 + x2 ≤ -3
 É equivalente
 -x1 + x2 + s1 = -3
 s1 ≥ 0
 Mas também a 
 x1 - x2 - s1 = 3
 s1 ≥ 0
Exercícios
 No problema da Reddy Micks, verifique se a 
solução 
x1 = 2, x2 = 3
é viável e determine as variáveis de folga.
Variáveis irrestritas
 Em um problema de alocação de mão de obra, a 
quantidade requerida em um momento i+1 é igual 
à quantidade requerida no momento anterior i mais 
(ou menos) uma variação
 xi+1 = xi + yi+1
 A variável yi+1 deve ser irrestrita para que a 
quantidade de mão de obra possa aumentar ou 
diminuir ao longo do tempo.
Variáveis irrestritas
 Como conciliar essa necessidade com a segunda 
condição?
 yi+1 = y
+
i+1 – y
–
i+1
 y+i+1 ≥ 0
 y–i+1 ≥ 0
 Desta forma, a contratação de um empregado 
seria feita quando
 y+i+1 = 1
 y–i+1 = 0
Variáveis irrestritas
 A demissão seria feita quando
 y+i+1 = 0
 y–i+1 = 1
 A não alteração do quadro resulta em
 y+i+1 = 0
 y–i+1 = 0
 A forma como opera o método Simplex impede 
que as duas variáveis tenham valor positivo 
simultaneamente.
Transitando da forma gráfica para a 
algébrica
 Considere o problema
Maximizar z = 2 x1 + 3 x2
Sujeito a 
2 x1 + x2 ≤ 4
x1 + 2 x2 ≤ 5
x1, x2 ≥ 0
Transitando da forma gráfica para a 
algébrica
As restrições
2 x1 + x2 ≤ 4
x1 + 2 x2 ≤ 5
x1, x2 ≥ 0
Podem ser reescritas
2 x1 + x2 + s1 = 4
x1 + 2 x2 + s2 = 5
x1, x2, s1, s2 ≥ 0
Transitando da forma gráfica para a 
algébrica
0
1
2
3
4
5
0 1 2 3 4 5 6
Ótima (x1 = 1, x2 = 2)
s2 = 0
s1 = 0
Transitando da forma gráfica para a 
algébrica
 Na forma gráfica verificamos que o problema tem 
infinitas soluções porque existe uma área em que 
todas as restrições são atendidas.
 Na forma algébrica, vê-se que o sistema tem
m = 2 equações
n = 4 incógnitas
 É portanto indefinido, tem infinitas soluções
Determinação algébrica de pontos 
extremos
 Se, em um sistema em que
 n ≥ m
 Faz-se com que 
 n – m variáveis assumam o valor 0
 A solução resultante
 Se for única
 É denominada solução básica
 E corresponde a um ponto extremo
Determinação algébrica de pontos 
extremos
 Há portanto, no máximo
soluções extremas para o problema
)!(!
!
mnm
n
C nm


Determinação algébrica de pontos 
extremos
 No exemplo, 
 m = 2
 n = 4
 Há portanto no máximo 6 pontos extremos
6
1.2
3.4
)!24(!2
!4
)!(!
!





mnm
n
C nm
Transitando da forma gráfica para a 
algébrica
0
1
2
3
4
5
0 1 2 3 4 5 6
Ótima (x1 = 1, x2 = 2)
s2 = 0
s1 = 0
F
B
A
C
D E
Transitando da forma gráfica para a 
algébrica
Variáveis
não básicas
Variáveis 
básicas
Solução 
básica
Ponto 
Extremo
Viável? Valor da 
função obj
x1, x2 s1, s2 4; 5 A S 0
x1, s1 x2, s2 4; -3 F N -
x1, s2 x2, s1 2, 5; 1,5 B S 7,5
x2, s1 x1, s2 2; 3 D S 4
x2, s2 x1, s1 5; -6 E N -
s1, s2 x1, x2 1; 2 C S 8
O Método Simplex
0
1
2
3
4
5
0 1 2 3 4 5 6
Ótima (x1 = 1, x2 = 2)
s2 = 0
s1 = 0
F
B
A
C
D E
Maximizar z = 2 x1 + 3 x2
Ponto 
Extremo
Variáveis 
Básicas
Variáveis
(Zero)
Não Básicas
A s1, s2 x1, x2
B x2, s1 x1, s2 
C x1, x2 s1, s2 
Exercício
 Suponha que apenas a função objetivo do 
problema anterior tenha sido alterada. 
Qual percurso do método simplex?
 Identifique as variáveis básicas e não básicas que 
definem esse caminho.
O Método Simplex
 O problema da Reddy Micks
 Maximizar z = 5 x1 + 4 x2
 Sujeito a
1. 6x1 + 4x2 ≤ 24
2. x1 + 2x2 ≤ 6
3. - x1 + x2 ≤ 1
4. x2 ≤ 2
5. x1 ≥ 0
6. x2 ≥ 0
O Método Simplex
 O problema da Reddy Micks, reescrito na forma de 
equações 
 Maximizar z = 5 x1 + 4 x2 + 0 s1 + 0 s2 + 0 s3 + 0 s4
 Ou z - 5 x1 - 4 x2 = 0
 Sujeito a
1. 6x1 + 4x2 + s1 = 24
2. x1 + 2x2 + s2 = 6
3. - x1 + x2 + s3 = 1
4. x2 + s4 = 2
5. x1, x2, s1, s2, s3, s4 ≥ 0
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 -5 -4 0 0 0 0 0 linha z
s1 0 6 4 1 0 0 0 24 linha s1
s2 0 1 2 0 1 0 0 6 linha s2
s3 0 -1 1 0 0 1 0 1 linha s3
s4 0 0 1 0 0 0 1 2 linha s4
variáveis básicasvariáveis não básicas
coeficiente mais negativo entra na base
O Método Simplex
Base x1 Solução Razão
s1 6 24 24/6 = 4
s2 1 6 6/1 = 6
s3 -1 1 1/(-1) = -1
s4 0 2 2/0 = ∞
mínimo
negativo, ignorar
razão infinita, ignorar
Conclusão: entra x1 e sai s1
A variável de menor razão não 
negativa sai da base
sai da base
A escolha da variável que sai da base é determinada pela primeira restrição encontrada 
quando se aumenta o valor da variável que entra na base.
O Método Simplex
-1
0
1
2
3
4
5
6
7
-1 0 1 2 3 4 5 6 7
s1 = 0
s2 = 0
s3 = 0
24/6 = 41/(-1) = -1
s4 = 0
A B
6/1 = 6
A escolha da variável que sai da base é determinada pela 
primeira restrição encontrada quando se aumenta o valor da 
variável que entra na base.
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 -5 -4 0 0 0 0 0
s1 0 6 4 1 0 0 0 24
s2 0 1 2 0 1 0 0 6
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
sai
entra
linha do pivô
coluna do pivô
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 -5 -4 0 0 0 0 0
x1 0 1 2/3 1/6 0 0 0 4
s2 0 1 2 0 1 0 0 6
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
+5x
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 0 -2/3 5/6 0 0 0 20
s1 0 1 2/3 1/6 0 0 0 4
s2 0 1 2 0 1 0 0 6
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
-1x
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 0 -2/3 5/6 0 0 0 20
s1 0 1 2/3 1/6 0 0 0 4
s2 0 0 4/3 -1/6 1 0 0 2
s3 0 -1 1 0 0 1 0 1
s4 0 0 1 0 0 0 1 2
+1x
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 0 -2/3 5/6 0 0 0 20
s1 0 1 2/3 1/6 0 0 0 4
s2 0 0 4/3 -1/6 1 0 0 2
s3 0 0 5/3 1/6 0 1 0 5
s4 0 0 1 0 0 0 1 2
+0x
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 0 -2/3 5/6 0 0 0 20
x1 0 1 2/3 1/6 0 0 0 4
s2 0 0 4/3 -1/6 1 0 0 2
s3 0 0 5/3 1/6 0 1 0 5
s4 0 0 1 0 0 0 1 2
coeficiente mais negativo entra na base
coluna do pivô
O Método Simplex
Base x2 Solução Razão
x1 2/3 4 4/(2/3) = 6
s2 4/3 2 2/(4/3) = 3/2
s3 5/3 5 5/(5/3) = 3
s4 1 2 2/1 = 2
mínimo
Conclusão: entra x2 e sai s2
A variável de menor razão não 
negativa sai da base
sai da base
O Método Simplex
-1
0
1
2
3
4
5
6
7
-1 0 1 2 3 4 5 6 7
s1 = 0
s2 = 0
s3 = 0
s4 = 0
A
C
B
A escolha da variável que sai da base é determinada pela 
primeira restrição encontrada quandose aumenta o valor da 
variável que entra na base.
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 0 -2/3 5/6 0 0 0 20
x1 0 1 2/3 1/6 0 0 0 4
s2 0 0 4/3 -1/6 1 0 0 2
s3 0 0 5/3 1/6 0 1 0 5
s4 0 0 1 0 0 0 1 2
sai linha do pivô
coluna do pivô
entra na base
O Método Simplex
Base z x1 x2 s1 s2 s3 s4 Solução
z 1 0 0 3/4 1/2 0 0 21
x1 0 1 0 1/4 -1/2 0 0 3
x2 0 0 1 -1/8 3/4 0 0 3/2
s3 0 0 0 3/8 -5/4 1 0 5/2
s4 0 0 0 1/8 -3/4 0 1 1/2
Nenhum dos coeficientes é negativo: a solução é ótima
Resultados
Variável 
de Decisão
Valor 
Ótimo
Recomendação
x1 3 Produzir 3 t diárias de tintas para exteriores
x2 3/2 Produzir 1,5 t diárias de tintas para interiores
z 21 Lucro diário é de $ 21.000
Resultados - Restrições
Recurso Valor da Folga Situação
Matéria-prima M1 s1 = 0 Escasso
Matéria-prima M2 s2 = 0 Escasso
Limite de mercado s3 = 5/2 Abundante
Limite da demanda s4 = 1/2 Abundante
O método Simplex fornece mais que uma solução ótima: permite que se analise o cenário, 
observando por exemplo que restrições influenciaram na fixação do ótimo. Variáveis de 
folga com situação abundante indicam restrições inativas, as que, na situação analisada, 
não influenciaram na solução do problema.
Exercício
 Determine a solução ótima para o problema de 
otimização
Maximizar z = 2 x1 + x2 – 3 x3 + 5 x4
 Sujeito a
 x1 + 2 x2 + 2 x3 + 4 x4 ≤ 40 
 2 x1 – x2 + x3 + 2 x4 ≤ 8
 4 x1 – 2 x2 + x3 – x4 ≤ 10
 x1, x2, x3, x4 ≥ 0
Exercícios
 Repita o exercício anterior com as seguintes funções 
objetivo
Maximizar z = 8 x1 + 6 x2 + 3 x3 – 2 x4
Maximizar z = 3 x1 – x2 + 3 x3 + 4 x4
Minimizar z = 5 x1 – 4 x2 + 6 x3 – 8 x4
Observação: no problema de minimização, a coluna do pivô 
é escolhida pelo maior coeficiente positivo
Solução Inicial Artificial
 Apenas se todas as restrições são do tipo ≤, a 
solução xi = 0 leva a uma solução básica 
envolvendo as variáveis de folga.
 Restrições do tipo = ou ≥ necessitam outros 
mecanismos para gerar uma solução inicial.
O método do M-Grande
O método de duas fases
Método do M-grande (“big M”)
 Variáveis artificiais são adicionadas às restrições 
do tipo = e ≥
 Tais variáveis são incluídas na função objetivo com 
coeficientes punitivos (o grande M), que 
eventualmente as levarão a ficar fora da base.
 O coeficiente será, em problemas de 
Maximização – M
Minimização + M
Método do M-grande (“big M”)
 Min z = 4 x1 + x2
 sujeito a
 3 x1 + x2 = 3
 4 x1 + 3 x2 ≥ 6
 x1 + 2 x2 ≤ 4
 x1, x2 ≥ 0
 Min z = 4 x1 + x2
 sujeito a
 3 x1 + x2 = 3
 4 x1 + 3 x2 - x3 = 6
 x1 + 2 x2 + x4 = 4
 x1, x2 ≥ 0
Método do M-grande (“big M”)
 Min z = 4 x1 + x2
 sujeito a
 3 x1 + x2 = 3
 4 x1 + 3 x2 - x3 = 6
 x1 + 2 x2 + x4 = 4
 x1, x2, x3, x4 ≥ 0
 Min z=4x1+x2+MR1+MR2
 sujeito a
 3 x1 + x2 + R1 = 3
 4 x1 + 3 x2 - x3 + R2 = 6
 x1 + 2 x2 + x4 = 4
 x1, x2, x3, x4, R1, R2 ≥ 0
Quão grande deve ser M?
Tão grande quanto necessário para que não faça parte da base.
Método do M-grande (“big M”)
Base x1 x2 x3 R1 R2 x4 Solução
z -4 -1 0 100 100 0 0
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
x4 1 2 0 0 0 1 4
Método do M-grande (“big M”)
Base x1 x2 x3 R1 R2 x4 Solução
z 696 399 -100 0 0 0 900
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
x4 1 2 0 0 0 1 4
Método do M-grande (“big M”)
Base x1 x2 x3 R1 R2 x4 Solução
z 0 167 -100 -232 0 0 204
x1 1 1/3 0 1/3 0 0 1
R2 0 5/3 -1 -4/3 1 0 2
x4 0 5/3 0 -1/3 0 1 3
Método do M-grande (“big M”)
Base x1 x2 x3 R1 R2 x4 Solução
z 0 0 1/5 -492/5 -501/5 0 18/5
x1 1 0 1/5 3/5 -1/5 0 3/5
x2 0 1 -3/5 -4/5 3/5 3/5 6/5
x4 0 0 1 1 -1 1 1
Método do M-grande (“big M”)
Base x1 x2 x3 R1 R2 x4 Solução
z 0 0 0 -491/5 -100 -1/5 17/5
x1 1 0 0 2/5 0 -1/5 2/5
x2 0 1 0 -11/15 0 0 9/5
x3 0 0 1 1 -1 1 1
Solução: x1= 2/5, x2 = 9/5 e z = 17/5
Método das duas fases
 O big M pode introduzir erros de arredondamento
 No método das duas fases
 Fase I tenta localizar uma solução básica viável
 Fase II resolve o problema original
Fase I
 O problema é expresso na forma de equações
 São introduzidas as variáveis artificiais
 Encontra-se a solução básica que minimiza a soma 
das variáveis artificiais
 Se a função objetivo final 
 tem valor positivo, o problema não tem solução viável
 tem valor menor ou igual a zero, passa-se para a 
segunda fase
Fase I
 Min z = 4 x1 + x2
 sujeito a
 3 x1 + x2 = 3
 4 x1 + 3 x2 ≥ 6
 x1 + 2 x2 ≤ 4
 x1, x2 ≥ 0
 Min z = 4 x1 + x2
 sujeito a
 3 x1 + x2 = 3
 4 x1 + 3 x2 - x3 = 6
 x1 + 2 x2 + x4 = 4
 x1, x2 ≥ 0
Fase I
 Min z = 4 x1 + x2
 sujeito a
 3 x1 + x2 = 3
 4 x1 + 3 x2 - x3 = 6
 x1 + 2 x2 + x4 = 4
 x1, x2, x3, x4 ≥ 0
 Min z = R1 + R2
 sujeito a
 3 x1 + x2 + R1 = 3
 4 x1 + 3 x2 - x3 + R2 = 6
 x1 + 2 x2 + x4 = 4
 x1, x2, x3, x4, R1, R2 ≥ 0
Fase I
Base x1 x2 x3 R1 R2 x4 Solução
r 0 0 0 -1 -1 0 0
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
x4 1 2 0 0 0 1 4
Fase I
Base x1 x2 x3 R1 R2 x4 Solução
r 3 1 0 0 -1 0 3
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
x4 1 2 0 0 0 1 4
Fase I
Base x1 x2 x3 R1 R2 x4 Solução
r 7 4 -1 0 0 0 9
R1 3 1 0 1 0 0 3
R2 4 3 -1 0 1 0 6
x4 1 2 0 0 0 1 4
Fase I
Base x1 x2 x3 R1 R2 x4 Solução
r 7 4 -1 0 0 0 9
R1 1 1/3 0 1/3 0 0 1
R2 4 3 -1 0 1 0 6
x4 1 2 0 0 0 1 4
Fase I
Base x1 x2 x3 R1 R2 x4 Solução
r 0 5/3 -1 -7/3 0 0 2
R1 1 1/3 0 1/3 0 0 1
R2 0 5/3 -1 -4/3 1 0 2
x4 0 5/3 0 -1/3 0 1 3
Fase I
Base x1 x2 x3 R1 R2 x4 Solução
r 0 5/3 -1 -7/3 0 0 2
x1 1 1/3 0 1/3 0 0 1
R2 0 5/3 -1 -4/3 1 0 2
x4 0 5/3 0 -1/3 0 1 3
Fase I
Base x1 x2 x3 R1 R2 x4 Solução
r 0 5/3 -1 -7/3 0 0 2
x1 1 1/3 0 1/3 0 0 1
R2 0 1 -3/5 -4/5 3/5 0 6/5
x4 0 5/3 0 -1/3 0 1 3
Fase I
Base x1 x2 x3 R1 R2 x4 Solução
r 0 0 0 -1 -1 0 0
x1 1 0 1/5 3/5 -1/5 0 3/5
x2 0 1 -3/5 -4/5 3/5 0 6/5
x4 0 0 1 1 -1 1 1
O mínimo igual a zero indica que há uma solução básica viável com
x1 = 3/5, x2 = 6/5 e x4 = 1
Fase II
 Na segunda fase, usa-se a solução viável da 
primeira fase como solução inicial para o problema 
original
Fase I
Base x1 x2 x3 x4 Solução
z -4 -1 0 0 0
x1 1 0 1/5 0 3/5
x2 0 1 -3/5 0 6/5
x4 0 0 1 1 1
Fase I
Base x1 x2 x3 x4 Solução
z 0 -1 4/5 0 12/5
x1 1 0 1/5 0 3/5
x2 0 1 -3/5 0 6/5
x4 0 0 1 1 1
Fase I
Base x1 x2 x3 x4 Solução
z 0 0 1/5 0 18/5
x1 1 0 1/5 0 3/5
x2 0 1 -3/5 0 6/5
x4 0 0 1 1 1
Fase I
Base x1 x2 x3 x4 Solução
z 0 0 0 -1/5 17/5
x1 1 0 0 -1/5 2/5
x2 0 1 0 3/5 9/5
x3 0 0 1 1 1
Solução: x1= 2/5, x2 = 9/5 e z = 17/5
Retirada das variáveis artificiais
 Só podem ser retiradas as colunas das variáveis 
artificiais não básicas
 Se uma ou mais variáveis artificiais permanecer na 
base
 Etapa I
 selecione uma dessas variáveis (artificiais e básicas) para sair da 
base
 selecione uma variável não-artificial não-básica para entrar na 
base
 realize uma iteração do Simplex.
 Etapa II
 remova da tabela a coluna da variável artificial que saiu da 
base