Apresentação método - SIMPLEX

Prévia do material em texto

Método simplex
É um procedimento iterativo que permite ir
melhorando a solução de um PPL a cada passo. O
processo termina quando não é possível seguir
melhorando uma determinada solução.
Método simplex
Seja o modelo de Programação linear
Caminha pelos vértices até encontrar uma solução 
que não possua soluções vizinhas melhores que ela
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 4x =3R : 
22 12x =2R : 
1 23 2 18x x+ =1R : 
1x 
2x 
(0,0) 
(0,6) 
(6,0) 
(4,3) 
(2,6) 
(0,9) 
(4,0) 
(4,6) 
𝑴𝑨𝑿𝒁 = 𝟑𝒙𝟏 + 𝟓𝒙𝟐
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎:
3𝑥1 + 2𝑥2 ≤ 18
2𝑥2 ≤ 12
𝑥1 ≤ 4
𝑥1, 𝑥2 ≥ 0
Fundamentos: o modelo de um problema de programação linear 
pode ser resolvido pela solução de um sistema de equações lineares 
equivalentes. 
Para restrições de desigualdade ≤ a conversão é feita adicionando a 
equação uma variável artificial Xfn ≥ 0
FORMA PADRÃO
𝑀𝐴𝑋 𝑍 = 3𝑥1 + 5𝑥2
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎:
𝑥1 + 𝒙𝑓1 = 4
2𝑥2 + 𝒙𝑓2 = 12
3𝑥1 + 2𝑥2 + 𝒙𝑓3 = 18
𝑥1, 𝑥2, 𝒙𝑓1, 𝒙𝑓2, 𝒙𝑓3 ≥ 0
FORMA CANÔNICA
𝑀𝐴𝑋 𝑍 = 3𝑥1 + 5𝑥2
𝑠𝑢𝑗𝑒𝑖𝑡𝑜𝑎:
𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
𝑥1, 𝑥2 ≥ 0
Procedimentos (forma canônica→ forma padrão)
O problema se transformou em
encontrar uma solução de um
sistema de equações que
maximize a função objetivo
Variáveis n = 5
restrições m= 3
n > m
Método de enumeração das soluções básicas
Analisando, podemos dizer que atribuir zero a uma variável significa 
não produzir um dos produtos ou utilizar toda a disponibilidade de 
recursos.
(n-m) variáveis iguais a zero → solução básica
O número de soluções básicas possíveis 
( )
!
C
! !
n
m
n n
m m n m
 
= = 
−  ( )
5
3
5 5!
C 10
3 3! 2 !
 
= = = 
 
Método da enumeração das soluções básicas
• Variáveis não básicas: São as variáveis zeradas, igual a (n-m) 
variáveis.
• Variáveis básicas: São as variáveis cujos valores são calculados pelo 
sistema de equações
1ª combinação
Variáveis não básicas ( x1, x2)= (0,0)
Variáveis básicas (xf1, xf2, xf3)= ( 4, 12, 8)
Solução básica ( x1,x2, xf1, xf2, xf3) = ( 0,0,4,12,8) Z = 0
Método da enumeração das soluções básicas
2ª combinação
Variáveis não básicas ( x1, xf1)= (0,0)
Variáveis básicas (x2, xf2, xf3)= não existe base associada!!!!!!
Solução básica sem solução !!!!!!
3ª combinação
Variáveis não básicas ( x1, xf2)= (0,0)
Variáveis básicas (x2, xf1, xf3)= (6 ,4 ,6 )
Solução básica ( x1,x2, xf1, xf2, xf3) = ( 0,6,4,0,6) Z = 30 solução viável!!
Método da enumeração das soluções básicas
4ª combinação
Variáveis não básicas ( x1, xf3)= (0,0)
Variáveis básicas (x2, xf1, xf2)= (9 ,4 ,-6 )
Solução básica ( x1,x2, xf1, xf2, xf3) = ( 0,9,4,-6,0) solução inviável!!
Porque? Se x1=0 e xf3= 0
X1+ xf1=4 .......... logo se x1=0 xf1=4
3x1+ 2x2+ xf3= 18 ..... logo 3(0)+ 2x2 + 0 = 18 ou x2= 18/2 = 9
2x2+ xf2 = 12 ........ se x2= 9 teremos 2(9) + xf2 = 12.... xf2= 12-18= -6
Método de enumeração das soluções básicas
Solução básica
(x1,x2,xf1,xf2,xf3
)
Z Observação
1 (0,0,4,12,18) 0 Viável
2 ----------- --- Não existe
3 (0,6,4,0,6) 30 Viável 
4 ( 0,9,4,-6,0) ---- Inviável
5 (4,0,0,12,6) 12 viável
6 ------------- ----- Não existe
7 (6,0,-2,12,0) ----- inviável
8 (4,6,0,0,-6) ----- inviável
9 (4,3,0,6,0) 27 viável
10 (2,6,2,0,0) 36 viável
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 4x =3R : 
22 12x =2R : 
1 23 2 18x x+ =1R : 
1x 
2x 
(0,0) 
(0,6) 
(6,0) 
(4,3) 
(2,6) 
(0,9) 
(4,0) 
(4,6) 
Método de enumeração de soluções básicas
• No problema vimos que n=5 (número de variáveis) e m=3 (número de 
restrições) tem
E se n=20 e m= 10 
( )
5
3
5 5!
C 10
3 3! 2 !
 
= = = 
 
( )
20
10
20 20!
C 184.756
10 10! 10 !
 
= = = 
 
Desenvolvimento do método simplex
Problemas Reais
➢Qual o sistema de equações que deve ser
resolvido;
➢Qual é o próximo sistema a ser resolvido
que fornecerá uma solução melhor que
os anteriores;
➢ Como identificar uma solução ótima, uma
vez que tenhamos encontrado.
Método simplex- Passo 1
Transformar o PPL da sua forma Canônica para sua forma Padrão
FORMA CANÔNICA
𝑀𝐴𝑋 𝑍 = 3𝑥1 + 5𝑥2
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎:
𝑥1 ≤ 4
2𝑥2 ≤ 12
3𝑥1 + 2𝑥2 ≤ 18
𝑥1, 𝑥2 ≥ 0
FORMA PADRÃO
𝑀𝐴𝑋 𝑍 = 3𝑥1 + 5𝑥2
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎:
𝑥1 + 𝒙𝑓1 = 4
2𝑥2 + 𝒙𝑓2 = 12
3𝑥1 + 2𝑥2 + 𝒙𝑓3 = 18
𝑥1, 𝑥2, 𝒙𝑓1, 𝒙𝑓2, 𝒙𝑓3 ≥ 0
Método simplex- Passo 2
Montar um quadro para ordenamos as operações, colocando neles apenas os coeficientes das variáveis.
A SOLUÇÃO INICIAL SERÁ SEMPRE OBTIDA FAZENDO AS VARIÁVEIS ORIGINAIS DO MODELO IGUAIS A ZERO E 
ACHANDO O VALOR DAS DEMAIS
FUNÇÃO OBJETIVO MAX Z= 3X1 + 5X2 Z – 3X1 – 5X2 = 0 
Valores na 
solução Z
X1 X2 Xf1 Xf2 Xf3 Valores de 
solução b
1 -3 -5 0 0 0 0
0 1 0 1 0 0 4
0 0 2 0 1 0 12
0 3 2 0 0 1 18
Método simplex- passo 3- cálculo de uma 
nova solução
como a solução inicial testada não é ótima, porque apresenta variáveis 
não básicas com coeficiente negativos, teremos que melhorar esta 
solução. 
Como???
VERIFICANDO:
Que variável que entra na base: entra na base a variável com 
coeficiente negativo de maior valor absoluto.
Método simplex – passo 3
Que variável sai da base: sai da base a variável que primeiro se anula 
com a entrada da variável escolhida. ?????
Esta variável pode ser descoberta dividindo-se os termos da direita( 
valores da solução) , pelo coeficiente da variável que entra. O resultado 
que deverá ser o menor valor positivo, indica a linha da variável que 
deverá sair.
A linha da variável que sai é também chamada LINHA PIVÔ, e o 
elemento intercessão da linha que sai e a coluna que entra, é 
denominado elemento PIVÔ
Método simplex- passo 3
Valores de z x1 x2 xf1 xf2 xf3 Valores b
1 linha 1 -3 -5 0 0 0 0
2 linha 0 1 0 1 0 0 4 4/ 0 = 0
0 0 2 0 1 0 12 12/2=6 linha Pivô
4 linha 0 3 2 0 0 1 18 18/2= 9
Método simplex- cálculo de nova solução
▪ Dividimos a linha PIVÔ pelo elemento pivô , obtendo-se uma nova 
linha com pivô unitário
▪ E vamos reescrever cada uma das outras linhas da seguinte maneira:
multiplicamos os elementos da nova linha pivô pelo coeficiente da 
variável que entra da outa linha com o sinal trocado.
Linha pivô/pivô 
Linha pivô / 2
0 0 2 0 1 0 12
Nova linha Pivô 0 0 1 0 0,5 0 6
Cálculo de uma nova solução
Cálculo da nova 1ª linha
0 0 1 0 0,5 0 6 Nova linha pivô
0 0 5 0 2,5 0 30 nova linha Pivô * ( 5)
1 -3 -5 0 0 0 0 Somar com a primeira linha
1 -3 0 0 2,5 0 30 NOVA 1ª LINHA
Cálculo de uma nova solução
Cálculo da 2ª linha
0 0 1 0 0,5 0 6 Nova linha pivô
0 0 0 0 0 0 0 Nova linha Pivô * ( 0)
0 1 0 1 0 0 4 Somar com a segunda linha
0 1 0 1 0 0 4 NOVA 2ª LINHA
Cálculo de nova solução
Cálculo da 4ª linha
0 0 1 0 0,5 0 6 Nona linha pivô
0 0 -2 0 -1 0 -12 Nova linha Pivô * ( -2)
0 3 2 0 0 1 18 Somar com a quarta linha
0 3 0 0 -1 1 6 NOVA 4ª LINHA
A NOVA SOLUÇÃO É ÓTIMA ? NÃO
Variáveis básicas : x2= 6 , xf1= 4, xf3 = 6
Variáveis não básicas: x1 =0 , xf2 = 0 
Valores na 
solução Z
X1 X2 Xf1 Xf2 Xf3 Valores de 
solução b
1 -3 0 0 2,5 0 30
0 1 0 1 0 0 4
0 0 1 0 0,5 0 6
0 3 0 0 -1 1 6
Temos variáveis negativas 
ainda
Cálculo de uma nova solução
Valores 
de Z
x1 x2 xf1 xf2 xf3 b
1ª linha 1 -3 0 0 2,5 0 30
2ª linha 0 1 0 1 0 0 4 4/1 = 4
3ª linha 0 0 1 0 0,5 0 6 6/0= 0
0 3 0 0 -1 1 6 6/3 = 2
Cálculo nas novas linhas
Cálculo da linha pivô
0 3 0 0 -1 1 6 dividir por (3) = 0 1 0 0 -1/3 1/3 2
Cálculo da 1ª linha
0 1 0 0 -1/3 1/3 2 multiplicar a linha pivô por ( 3)
0 3 0 0 -1 1 6 o resultado somar com a 1ª linha
0 -3 0 0 2,5 0 30
1 0 0 0 1,5 1 36
Cálculo da 2ª linha
0 1 0 0 -1/3 1/3 2 multiplicar a linha pivô por ( -1)
0 -1 0 0 1/3 -1/3 -2 o resultado somar com a 2ªlinha
0 1 0 1 0 0 4
0 0 0 1 1/3 -1/3 2
Nova solução é ótima? Sim
variáveis básicas: x1= 2 , x2= 6 , xf1= 2
varáveis não básicas: xf2 =0 , xf3= 0
Z X1 X2 XF1 XF2 XF3 B
1 0 0 0 1,5 1 36
0 0 0 1 1/3 -1/3 2
0 0 1 0 0,5 0 6
0 1 0 0 -1/3 1/3 2
VERIFICANDO A RESPOSTA NO SISTEMA
𝑀𝐴𝑋 𝑍 = 3𝑥1 + 5𝑥2
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎:
𝑥1 + 𝒙𝑓1 = 4
2𝑥2 + 𝒙𝑓2 = 12
3𝑥1 + 2𝑥2 + 𝒙𝑓3 = 18
𝑥1, 𝑥2, 𝒙𝑓1, 𝒙𝑓2, 𝒙𝑓3 ≥ 0
𝑀𝐴𝑋 𝑍 = 3(2) + 5(6) = 36
𝑠𝑢𝑗𝑒𝑖𝑡𝑜 𝑎:
2 + 2 = 4
2 6 + 0 = 12
3 2 + 2 6 + 0 = 18
𝑥1, 𝑥2, 𝒙𝑓1, 𝒙𝑓2, 𝒙𝑓3 ≥ 0