Programação Linear (PL) Solução algébrica

Universidade Federal de Itajubá
Instituto de Engenharia de Produção e Gestão
Pesquisa Operacional
Simplex
Prof. Dr. José Arnaldo Barra Montevechi
Programação Linear (PL)
Solução algébrica - método
simplex
9 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
9 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
9 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.
9 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
9 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.
9 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.
Procedimentos do Método
Simplex
9 Agora tudo que foi feito para o primeiro
ponto é feito para o novo ponto.
9 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
9 Como fazer, algebricamente, a mudança de
um ponto extremo para outro?
9 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
X2
Z
ZC=21
ZB=15
D(1, 4)
E(0, 4)
ZD=13
C(3, 3)
ZE=8
A(0, 0)
B(3, 0)
X1
A
B
C
D
O Método Simplex é
aplicado diretamente
quando:
9 todas as restrições são ≤;
9 todos os bi ≥ 0;
9 se quer maximizar Z.
E
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
x1 + 2x2 + x3 + x4
3x1
+ 2x3
xl + 4x2
=0
= 430
+ x5
= 460
+ x6 = 420
Terceiro passo: Determinar
uma solução inicial viável.
Base
Z
X4
X5
X6
z
1
0
0
0
X1
-3
1
3
1
X2
-2
2
0
4
X3
-5
1
2
0
X4
0
1
0
0
X5
0
0
1
0
X6
0
0
0
1
b
0
430
460
420
bi/aie
430
230
ind.
X1 = X2 = X3 = 0
X4 = 430; X5 = 460 e X6 = 420
Quarto passo: verificar se a
solução é ótima.
Não é ótima!
Base
Z
X4
X5
X6
z
1
0
0
0
X1
-3
1
3
1
X2
-2
2
0
4
X3
-5
1
2
0
X4
0
1
0
0
X5
0
0
1
0
X1 = X2 = X3 = 0
X4 = 430; X5 = 460 e X6 = 420
X6
0
0
0
1
b
0
430
460
420
bi/aie
430
230
ind.
Quinto passo: Determinar a
variável que entra (xe)
Sexto passo: Determinar a
variável que sai (xs).
entra
Base
Z
X4
X5
X6
z
1
0
0
0
X1
-3
1
3
1
X2
-2
2
0
4
X3
-5
1
2
0
X4
0
1
0
0
sai
X5
0
0
1
0
X6
0
0
0
1
b
0
430
460
420
bi/aie
430
230
ind.
Pivô
Sétimo passo: Calcular a nova
matriz de coeficientes,
executando as operações
convenientes nas linhas da
matriz.
B ase
Z
X4
X3
X6
z
1
0
0
0
X1
4.5
-0.5
1.5
1
X2
-2
2
0
4
X3
0
0
1
0
X4
0
1
0
0
X5
2.5
-0.5
0.5
0
X6
0
0
0
1
b
1150
200
230
420
b i/aie
100
ind.
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
X2
X3
X6
z
1
0
0
0
X1
4
-0.25
1.5
2
X2
0
1
0
0
X3
0
0
1
0
X4
1
0.5
0
-2
X5
2
-0.25
0.5
1
X6
0
0
0
1
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
b
1350
100
230
20
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
Solução básica inicial
Max Z = 3X1 + 2X2
sujeito a:
2X1 + X2 + X3
X1 + X2
= 100
+ X4
X1
= 80
+ 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
O problema pode ser
representado assim:
X1 entra na base
Z
1
0
0
0
Base
X3
X4
X5
X1
-3
2
1
1
X2
-2
1
1
0
X3
0
1
0
0
X4
0
0
1
0
X5
0
0
0
1
b
0
100
80
40
Razão
100/2=50
80/1=80
40/1=40
Pivo
Solução parcial: (0, 0, 100, 80, 40)
Indica que
X1 entra no
lugar de X5
Próximo quadro - Base: X3, X4 e X1
Devem se colocadas na forma canônica
Segunda iteração
Ainda não é a
solução ótima
Pivo
Base
X3
X4
X1
Z
1
0
0
0
X1
0
0
0
1
X2
-2
1
1
0
X3
0
1
0
0
X4
0
0
1
0
Solução parcial: (40, 0, 20, 40, 0)
Próximo quadro - Base: X2, X4 e X1
Devem se colocadas na forma canônica
X5
3
-2
-1
1
b
120
20
40
40
Razão
20/1=20
40/1=40
40/0
Indica que
X2 entra no
lugar de X3
Terceira iteração
Ainda não é a
solução ótima
Z
1
0
0
0
Base
X2
X4
X1
X1
0
0
0
1
Pivo
X2
0
1
0
0
X3
2
1
-1
0
X4
0
0
1
0
X5
-1
-2
1
1
b
160
20
20
40
Solução parcial: (40, 20, 0, 20, 0)
Razão
-10
20
40
Indica que
X5 entra no
lugar de X4
Próximo quadro - Base: X2, X5 e X1
Devem se colocadas na forma canônica
Quarta iteração
Valor máximo possível
para a função objetivo
solução é ótima
Base
X2
X5
X1
Z
1
0
0
0
X1
0
0
0
1
X2
0
1
0
0
X3
1
-1
-1
1
X4
1
2
1
-1
X5
0
0
1
0
Solução ótima: (20, 60, 0, 0, 20)
A restrição 4 tem um folga de 20
b
180
60
20
20
Razão
Solução do problema de
Giapetto pelo simplex
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 ótima: (20, 60, 0, 0, 20)
Z = 3*20 + 2*60 = 180
A restrição 4 tem um folga de 20
Exercício
9Resolver o problema do final do item
4.6.4 da apostila;
9Dois participantes por grupo;
9Entregar 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
Método Gráfico
(Exemplo já realizado anteriormente)
6
Indicando ponto ótimo - C (3, 3)
5
D
4
E
3
Z = 21
C
2
1
X1
A
1
2
B
3
4
5
6