Baixe o app para aproveitar ainda mais
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
Compartilhar