Simplex P.L

Prévia do material em texto

Pesquisa Operacional
Instituto de Engenharia de Produção e Gestão 
Universidade Federal de Itajubá
Prof. Dr. José Arnaldo Barra Montevechi
Simplex
Programação Linear (PL)
Solução algébrica - método 
simplex
?Agora será apresentado mais um 
procedimento geral para resolução de 
problemas de PL, denominado “Método 
Simplex” e que foi desenvolvido em 1947 por 
George B. Dantzig.
Método Simplex
?O método simplex é um método interativo 
(algoritmo) utilizado para achar, 
algebricamente, a solução ótima de um 
problema de PL.
Procedimentos do Método 
Simplex
?Sabe-se que a solução ótima do modelo é 
uma solução básica do sistema, ou seja, um 
ponto extremo do polígono gerado pelas 
restrições.
?Para ser iniciado é necessário conhecer uma 
solução compatível básica (solução inicial) 
do sistema, isto é um dos pontos do polígono 
gerado.
Procedimentos do Método 
Simplex
?O método simplex verifica se a presente 
solução é ótima. Se for o processo esta 
encerrado. Se não for ótima, é porque um 
dos pontos adjacentes fornece um valor 
maior que o inicial.
?Neste caso, o método simplex faz então a 
mudança do ponto por um outro que mais 
aumente o valor da função objetivo.
?Agora tudo que foi feito para o primeiro 
ponto é feito para o novo ponto. 
?O processo finaliza quando se obtém um 
ponto extremo onde todos os outros pontos 
extremos, forneçam valores menores para 
a função objetivo.
Procedimentos do Método 
Simplex
?Como fazer, algebricamente, a mudança de 
um ponto extremo para outro?
?Achar portanto a próxima solução básica 
exige a escolha de uma variável básica para 
deixar a base atual, tornando-se não básica, 
e a escolha de uma variável não básica para 
entrar na base em sua substituição.
Procedimentos do Método 
Simplex
Supondo o seguinte problema para 
maximização:
Max Z = 5X1 + 2X2
Sujeito a:
X1 ≤ 3
X2 ≤ 4
X1 + 2X2 ≤ 9
X1, X2 ≥ 0
Procedimentos do Método 
Simplex
A(0, 0)
B(3, 0)
C(3, 3)
D(1, 4)
E(0, 4)
A B C D E
ZB=15
ZC=21
ZD=13
ZE=8
X2
X1
Z
Procedimentos do Método 
Simplex
O Método Simplex é 
aplicado diretamente 
quando:
? todas as restrições são ≤;
? todos os bi ≥ 0;
? se quer maximizar Z.
Passos do simplex
1. Achar uma solução compatível básica inicial;
2. Verificar se a solução é ótima. Se for pare. caso 
contrário, siga para o passo 3;
3. Determinar a variável não básica que deve 
entrar na base;
4. Determinar a variável básica que deve sair da 
base;
5. Achar a nova solução compatível básica e 
voltar ao passo 2.
Seja a formulação
Maximizar z = 3x1 + 2x2 + 5x3
Sujeito a
x1+ 2x2 + x3 ≤ 430
3x1 + 2x3 ≤ 460
xl + 4x2 ≤ 420
x1, x2, x3 ≥ 0
Primeiro passo: Transformar o 
sistema de M desigualdades 
lineares restritivas em um sistema 
de M equações lineares.
Assim temos:
X1 + 2x2 + x3 + x4 = 430
3x1 + 2x3 + x5 = 460
xl + 4x2 + x6 = 420
Segundo passo: Colocar as 
equações em forma de tabela
z - 3x1 - 2x2 - 5x3 = 0 
x1 + 2x2 + x3 + x4 = 430 
3x1 + 2x3 + x5 = 460
xl + 4x2 + x6 = 420
Terceiro passo: Determinar 
uma solução inicial viável.
Base z X1 X2 X3 X4 X5 X6 b bi/aie 
Z 1 -3 -2 -5 0 0 0 0 
X4 0 1 2 1 1 0 0 430 430 
X5 0 3 0 2 0 1 0 460 230 
X6 0 1 4 0 0 0 1 420 ind. 
 
X1 = X2 = X3 = 0
X4 = 430; X5 = 460 e X6 = 420
Quarto passo: verificar se a 
solução é ótima.
Não é ótima!
X1 = X2 = X3 = 0
X4 = 430; X5 = 460 e X6 = 420
Base z X1 X2 X3 X4 X5 X6 b bi/aie 
Z 1 -3 -2 -5 0 0 0 0 
X4 0 1 2 1 1 0 0 430 430 
X5 0 3 0 2 0 1 0 460 230 
X6 0 1 4 0 0 0 1 420 ind. 
 
Quinto passo: Determinar a 
variável que entra (xe)
Sexto passo: Determinar a 
variável que sai (xs).
sai
entra
Pivô
Base z X1 X2 X3 X4 X5 X6 b bi/aie 
Z 1 -3 -2 -5 0 0 0 0 
X4 0 1 2 1 1 0 0 430 430 
X5 0 3 0 2 0 1 0 460 230 
X6 0 1 4 0 0 0 1 420 ind. 
 
Sétimo passo: Calcular a nova 
matriz de coeficientes, 
executando as operações 
convenientes nas linhas da 
matriz.
 
B ase z X 1 X 2 X 3 X 4 X 5 X 6 b b i/aie 
Z 1 4.5 -2 0 0 2.5 0 1150 
X 4 0 -0.5 2 0 1 -0.5 0 200 100 
X 3 0 1.5 0 1 0 0.5 0 230 ind. 
X 6 0 1 4 0 0 0 1 420 105 
 
 
Oitavo passo: Repetir todos os 
passos, do 4 ao 7, tantas vezes 
quanto forem necessárias, até 
que a solução ótima seja 
encontrada.
Base z X1 X2 X3 X4 X5 X6 b 
Z 1 4 0 0 1 2 0 1350 
X2 0 -0.25 1 0 0.5 -0.25 0 100 
X3 0 1.5 0 1 0 0.5 0 230 
X6 0 2 0 0 -2 1 1 20 
 
O máximo Z é 1350, para X2 = 100, X3 = 230 e X6 = 20. 
Resolvendo o problema de 
Giapetto pelo simplex
Max Z = 3X1 + 2X2 
sujeito a:
2X1 + X2 ≤ 100 
X1 + X2 ≤ 80 
X1 ≤ 40 
X1 ≥ 0 
X2 ≥ 0 
Converter o problema de PL na 
forma canônica
Max Z = 3X1 + 2X2
sujeito a:
2X1 + X2 + X3 = 100
X1 + X2 + X4 = 80
X1 + X5 = 40
X1, X2, X3, X4 e X5 ≥ 0
Max Z = 3X1 + 2X2 
sujeito a:
2X1 + X2 + X3 = 100
X1 + X2 + X4 = 80 
X1 + X5 = 40
X1, X2, X3, X4 e X5 ≥ 0
Variáveis não básicas: X1 = X2 = 0
Variáveis básicas: X3 = 100 X4 = 80 X5 = 40
Solução básica inicial
O problema pode ser 
representado assim:
 Z X1 X2 X3 X4 X5 b Razão 
Base 1 -3 -2 0 0 0 0 
X3 0 2 1 1 0 0 100 
X4 0 1 1 0 1 0 80 
X5 0 1 0 0 0 1 40 
 
100/2=50
80/1=80
40/1=40
Indica que 
X1 entra no
lugar de X5
Solução parcial: (0, 0, 100, 80, 40)
Próximo quadro - Base: X3, X4 e X1
Devem se colocadas na forma canônica
Pivo
X1 entra na base
 Z X1 X2 X3 X4 X5 b Razão 
Base 1 0 -2 0 0 3 120 
X3 0 0 1 1 0 -2 20 
X4 0 0 1 0 1 -1 40 
X1 0 1 0 0 0 1 40 
 
Pivo
Ainda não é a 
solução ótima
20/1=20
40/1=40
40/0
Indica que 
X2 entra no
lugar de X3
Solução parcial: (40, 0, 20, 40, 0)
Próximo quadro - Base: X2, X4 e X1
Devem se colocadas na forma canônica
Segunda iteração
 Z X1 X2 X3 X4 X5 b Razão 
Base 1 0 0 2 0 -1 160 
X2 0 0 1 1 0 -2 20 
X4 0 0 0 -1 1 1 20 
X1 0 1 0 0 0 1 40 
 
Ainda não é a 
solução ótima
Pivo
-10
20
40
Indica que 
X5 entra no
lugar de X4
Solução parcial: (40, 20, 0, 20, 0)
Próximo quadro - Base: X2, X5 e X1
Devem se colocadas na forma canônica
Terceira iteração
solução é ótima
 Z X1 X2 X3 X4 X5 b Razão 
Base 1 0 0 1 1 0 180 
X2 0 0 1 -1 2 0 60 
X5 0 0 0 -1 1 1 20 
X1 0 1 0 1 -1 0 20 
 
Valor máximo possível
para a função objetivo
Solução ótima: (20, 60, 0, 0, 20)
A restrição 4 tem um folga de 20
Quarta iteração
Max Z = 3X1 + 2X2
sujeito a:
2X1 + X2 + X3 = 100
X1 + X2 + X4 = 80
X1 + X5 = 40
X1, X2, X3, X4 e X5 ≥ 0
Solução do problema de 
Giapetto pelo simplex
Solução ótima: (20, 60, 0, 0, 20) Z = 3*20 + 2*60 = 180
A restrição 4 tem um folga de 20
Exercício
?Resolver o problema do final do item 
4.6.4 da apostila;
?Dois participantes por grupo;
?Entregar o resultado para fazer 
parte da avaliação da disciplina.
Resolva o problema 
abaixo pelo simplex
max Z = 5X1 + 2X2 
sujeito a:
X1≤ 3 
X2 ≤ 4 
X1 + 2X2 ≤ 9 
X1 ≥ 0 
X2 ≥ 0 
X2
X11
2
3
4
5
6
1 2 3 4 5 6
Método Gráfico
(Exemplo já realizado anteriormente)
A B
C
D
E
Indicando ponto ótimo - C (3, 3)
Z = 21