Buscar

Mdulo-4 - Mtodo Simplex [Modo de Compatibilidade]

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 20 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 20 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 20 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

PROGRAMAÇÃO LINEARPROGRAMAÇÃO LINEAR
MÉTODO SIMPLEXMÉTODO SIMPLEX
Módulo 4Módulo 4
Prof. Ms. Antonio dos Santos
Método Simplex :
Seja o Problema de PL:Seja o Problema de PL:
Max Z = 600 x1 + 800 x2
S.a.:S.a.:
x1 +    x2 ≤ 100
3 2 ≤ 2403 x1 + 2 x2 ≤ 240
x1 ≤ 60
x2 ≤ 80
x x ≥ 0x1, x2 ≥ 0
Método Simplex :
Passo 1: Colocar o problema na forma padrão
Max Z = 600 x1 + 800 x2
S.a.:
x1 +    x2 + x3 = 100
3 x + 2 x + x = 2403 x1 + 2 x2 + x4 = 240
x1 + x5 = 60
80x2 + x6 = 80
x1, x2, x3, x4, x5, x6 ≥ 0
Método Simplex 
Passo 2: Montar o tableau Simplex
VARIÁVEIS NÃO BÁSICAS VARIÁVEIS  BÁSICAS
ATIVIDADES VARIÁVEIS DE FOLGA
Z 600 X1 800 X2X1 X2 X3 X4 X5 X6 B
Z ‐600 ‐800 0 0 0 0 0
Z = 600 X1 + 800 X2
Z – 600 X1 – 800 X2 = 0
X3 1 1 1 0 0 0 100
X4 3 2 0 1 0 0 240
X5 1 0 0 0 1 0 60X5 1 0 0 0 1 0 60
X6 0 1 0 0 0 1 80
Método Simplex 
Passo 3: Escolher a variável que deve entrar na base
VARIÁVEIS NÃO BÁSICAS VARIÁVEIS  BÁSICAS
ATIVIDADES VARIÁVEIS DE FOLGA
P bl d i i ãX1 X2 X3 X4 X5 X6 B
Z ‐600 ‐800 0 0 0 0 0
Para um problema de maximização 
deve ser a variável com coeficiente 
negativo de maior valor absoluto.
No exemplo é “ 800”
X3 1 1 1 0 0 0 100
No exemplo é – 800
Portanto “X2” deve entrar na base
X4 3 2 0 1 0 0 240
X5 1 0 0 0 1 0 60X5 1 0 0 0 1 0 60
X6 0 1 0 0 0 1 80
Método Simplex 
Passo 4: Escolher a variável que deve sair da base e determinar o “Pivô” 
VARIÁVEIS NÃO BÁSICAS VARIÁVEIS  BÁSICAS
Á
Determinar o “pivô” que deve ser 
ATIVIDADES VARIÁVEIS DE FOLGA
X1 X2 X3 X4 X5 X6 B
Z ‐600 ‐800 0 0 0 0 0
o menor resultado da relação
“Bi / aij”
X3 1 1 1 0 0 0 100
Linha X3 100/1 <= 100
Linha X4 240/2 <= 120
Linha X5 60/0 = Infactível
X4 3 2 0 1 0 0 240
Linha X6 80/1 <= 80
(ou seja X2 <= 80)
X5 1 0 0 0 1 0 60
X6 0 1 0 0 0 1 80
Portanto X6 deve sair da base por 
ser a condição mais restritiva
Pi ô 1Pivô = 1
Método Simplex 
Passo 5: Multiplicar ou dividir a linha do pivô por um número de 
forma que o valor do pivô fique = a 1
Á S ÃO ÁS C S VARIÁVEIS BÁSICASVARIÁVEIS NÃO BÁSICAS VARIÁVEIS  BÁSICAS
ATIVIDADES VARIÁVEIS DE FOLGA
X1 X2 X3 X4 X5 X6 B
Z ‐600 ‐800 0 0 0 0 0Z 600 800 0 0 0 0 0
X3 1 1 1 0 0 0 100
X4 3 2 0 1 0 0 240
X5 1 0 0 0 1 0 60
X6 0 1 0 0 0 1 80 Neste caso o valor do pivô já é 1 X6 0 1 0 0 0 1 80
portanto a linha fica como está.
Método Simplex 
Passo 6: Colocar a linha do pivô no novo tableau.
Á S ÃO ÁS C S VARIÁVEIS BÁSICASVARIÁVEIS NÃO BÁSICAS VARIÁVEIS  BÁSICAS
ATIVIDADES VARIÁVEIS DE FOLGA
X1 X2 X3 X4 X5 X6 B
ZZ
X3
X4
X5
X6 0 1 0 0 0 1 80X6 0 1 0 0 0 1 80
Método Simplex 
Passo 7: No novo tableau calcular as demais linhas de forma que 
os valores da coluna X2 fique = 0.
Á S ÃO ÁS C S VARIÁVEIS BÁSICASVARIÁVEIS NÃO BÁSICAS VARIÁVEIS  BÁSICAS
ATIVIDADES VARIÁVEIS DE FOLGA
X1 X2 X3 X4 X5 X6 B
Z
ƒPara tanto verifique o valor de 
X2 na linha em análise.
Z
X3
ƒMultiplique a linha do pivô pelo 
negativo do valor encontrado.
X4
ƒSome a nova linha do pivô aos 
valores da linha em análise e 
coloque o resultado no novo
X5
X6 0 1 0 0 0 1 80
coloque o resultado no novo 
quadro. 
X6 0 1 0 0 0 1 80
Método Simplex 
VARIÁVEIS NÃO BÁSICAS         VARIÁVEIS  BÁSICAS
         ATIVIDADES      VARIÁVEIS DE FOLGA
X1 X2 X3 X4 X5 X6 BX1 X2 X3 X4 X5 X6 B
(*800) 0 800 0 0 0 800 64000
Z ‐600 0 0 0 0 800 64000 (+) ‐600 ‐800 0 0 0 0 0
= ‐600 0 0 0 0 800 64000
(*‐1) 0 ‐1 0 0 0 ‐1 ‐80
X3 1 0 1 0 0 ‐1 20 (+) 1 1 1 0 0 0 100
= 1 0 1 0 0 ‐1 20
(*‐2) 0 ‐2 0 0 0 ‐2 ‐160( )
X4 3 0 0 1 0 ‐2 80 (+) 3 2 0 1 0 0 240
(=) 3 0 0 1 0 ‐2 80
X5 1 0 0 0 1 0 60 Esta linha já está com o valor de X2 = 0X5 1 0 0 0 1 0 60 Esta linha já está com o valor de X2   0
X6 0 1 0 0 0 1 80 Linha do pivô
Método Simplex 
Passo 8: Escolher a nova variável que deve entrar na base
P bl d i i ã
X1 X2 X3 X4 X5 X6 BX1 X2 X3 X4 X5 X6 B
Para um problema de maximização 
deve ser a variável com coeficiente 
negativo de maior valor absoluto.
Z ‐600 0 0 0 0 800 64000Z ‐600 0 0 0 0 800 64000
“X1” deve entrar na base
X3 1 0 1 0 0 ‐1 20
X4 3 0 0 1 0 ‐2 80
X3 1 0 1 0 0 ‐1 20
X4 3 0 0 1 0 ‐2 80X4 3 0 0 1 0 ‐2 80
X5 1 0 0 0 1 0 60
X4 3 0 0 1 0 ‐2 80
X5 1 0 0 0 1 0 60
X6 0 1 0 0 0 1 80X6 0 1 0 0 0 1 80
Método Simplex 
Passo 9: Escolher a nova variável que deve sair da base e 
determinar o “Pivô” 
Determinar o “pivô” que deve ser 
o menor resultado da relação
“Bi / aij”
X1 X2 X3 X4 X5 X6 B
Z ‐600 0 0 0 0 800 64000
Linha X3 20/1 <= 20
Linha X4 80/3 <= 26,67
Linha X5 60/1 <= 60
X3 1 0 1 0 0 ‐1 20
(ou seja X1 <= 20)
X4 3 0 0 1 0 ‐2 80
X5 1 0 0 0 1 0 60
Portanto X3 deve sair da base por 
ser a condição mais restritiva
Pi ô 1
X5 1 0 0 0 1 0 60
X6 0 1 0 0 0 1 80
Pivô = 1
Método Simplex 
Passo 10: Multiplicar ou dividir a linha do pivô por um número de 
forma que o valor do pivô fique = a 1
X1 X2 X3 X4 X5 X6 B
Z ‐600 0 0 0 0 800 64000
Neste caso o valor do pivô já é 1 
portanto a linha fica como está.X3 1 0 1 0 0 ‐1 20
X4 3 0 0 1 0 ‐2 80
X5 1 0 0 0 1 0 60X5 1 0 0 0 1 0 60
X6 0 1 0 0 0 1 80
Método Simplex 
Passo 11: Colocar a linha do pivô no novo tableau.
Á S ÃO ÁS C S VARIÁVEIS BÁSICASVARIÁVEIS NÃO BÁSICAS VARIÁVEIS  BÁSICAS
ATIVIDADES VARIÁVEIS DE FOLGA
X1 X2 X3 X4 X5 X6 B
ZZ
X3 1 0 1 0 0 ‐1 20
X4
X5
X6X6
Método Simplex 
Passo 12: No novo tableau calcular as demais linhas de forma que 
os valores da coluna X1 fique = 0.
Á S ÃO ÁS C S VARIÁVEIS BÁSICAS ƒPara tanto verifique o valor de 
X1 na linha em análise.
VARIÁVEIS NÃO BÁSICAS VARIÁVEIS  BÁSICAS
ATIVIDADES VARIÁVEIS DE FOLGA
X1 X2 X3 X4 X5 X6 B
Z
ƒMultiplique a linha do pivô pelo 
negativo do valor encontrado.
Z
X3 1 0 1 0 0 ‐1 20
ƒSome a nova linha do pivô aos 
valores da linha em análise e 
coloque o resultado no novo
X4
coloque o resultado no novo 
quadro. 
X5
X6X6
Método Simplex 
X1 X2 X3 X4 X5 X6 B
(*600) 600 0 600 0 0 ‐600 12000
Z 0 0 600 0 0 200 76000 (+) ‐600 0 0 0 0 800 64000Z 0 0 600 0 0 200 76000 (+) 600 0 0 0 0 800 64000
= 0 0 600 0 0 200 76000
X3 1 0 1 0 0 ‐1 20 Linha do pivô
(*‐3) ‐3 0 ‐3 0 0 3 ‐60
X4 0 0 ‐3 1 0 1 20 (+) 3 0 0 1 0 ‐2 80
(=) 0 0 ‐3 1 0 1 20(=) 0 0 ‐3 1 0 1 20
(*‐1) ‐1 0 ‐1 0 0 1 ‐20
X5 0 0 ‐1 0 1 ‐1 40 (+) 1 0 0 0 1 0 60
(=) 0 0 ‐1 0 1 1 40
X6 0 1 0 0 0 1 80 Esta linha já está com o valor de X1 = 0
Método Simplex :
X1 X2 X3 X4 X5 X6 B
Z 0 0 600 0 0 200 76000Z 0 0 600 0 0 200 76000
X3 1 0 1 0 0 ‐1 20
RESULTADO:
X1 = 20
X4 0 0 ‐3 1 0 1 20
X2 = 80
X3 = 0
X4 = 20
X5 40
X5 0 0 ‐1 0 1 ‐1 40
X5 = 40 
X6 = 0
Z = 76 000
X6 0 1 0 0 0 1 80
Z = 76.000
Exercício 1:
Seja o Problema de PL:
Max Z = 30 x1 + 50 x2
S.a.:
2 x1 +    x2 ≤ 16
x + 2 x ≤ 11x1 + 2 x2 ≤ 11
x1 + 3 x2 ≤ 15≥ 0x1, x2 ≥ 0
Exercício 2:
Seja o Problema de PL:
Max Z = 3 x1 + 5 x2
S.a.:
2 x1 +    4x2 ≤ 10
6x + x ≤ 206x1 +  x2 ≤ 20
x1 ‐ x2 ≤ 30≥ 0x1, x2 ≥ 0
Exercício 3: Problema da Dieta
Sabe‐se que os alimentos leite, carne e ovos fornecem  as  quantidades 
de vitaminas dadas na tabela abaixo. Deseja‐se calcular as quantidadesde vitaminas dadas na tabela abaixo. Deseja se calcular as quantidades 
de leite, carne e ovos a fim de satisfazer as quantidades mínimas a um   
mínimo custo.
Vitaminas
Leite 
(litro)
Carne 
(kg)
Ovos 
(dúzia)
Quantidade 
diária 
mínimaVitaminas (litro) (kg) (dúzia) mínima
A 1 mg 3 mg 2 mg 6 mg
C 5 30 20 60
10 0 2 100D 10 50 25 100
CUSTO 
UNITÁRIO $2 00 $12 50 $7 50UNITÁRIO $2,00 $12,50$7,50

Outros materiais

Materiais relacionados

Perguntas relacionadas

Perguntas Recentes