Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pesquisa Operacional. Simplex (Casos Especiais). 34 PO - PESQUISA OPERACIONAL Continuação Profa. Léa Benatti Exemplo 2: (P. O. –Medeiros da Silva – pg. 46) Maximizar Z = 3X + 5Y Sujeito a: 2X + 4Y ≤ 10 6X + Y ≤ 20 X - Y ≤ 30 X ≥ 0, Y ≥ 0 (condição de não negatividade) Solução: Transformar inequações lineares em equações lineares: Acrescentar “Variáveis de Folga”. Maximizar Z = 3X + 5Y + 0S1 + 0S2 + 0S3 Sujeito a: 2X + 4Y + 1S1 + 0S2 + 0S3 = 10 6X + Y + 0S1 + 1S2 + 0S3 = 20 X - Y + 0S1 + 0S2 + 1S3 = 30 X, Y ≥ 0; S1, S2, S3 ≥ 0 (cond. não negatividade) 1a Tabela: Variáveis de decisão (título da tabela) 3 5 0 0 0 (Linha objetivo) Ci V. na Solução X Y S1 S2 S3 bj bj/aij bj/aij 0 S1 2 4 1 0 0 10 10/4 2,5 0 S2 6 1 0 1 0 20 20/1 20 0 S3 1 -1 0 0 1 30 30/(-1) -30 Z 0 0 0 0 0 0 (C-Z) 3 5 0 0 0 Valores da linha Z: Forma genérica do problema. Exemplo resolvido / para treino dos alunos → três restrições Sai (LP) Linha (C-Z): em termos de variáveis não básicas ( X, Y) → F. obj. entra ( ) ij Cx produtososseSoma restriçõesdasbdireitos ladoseesCoeficient − →→→→ Para cada coluna. 35 −= − = →= )considerarnão(30)1( 30 :linha3 20 1 20 :linha2 valormenor5,2 4 10 :linha1 Y b a a a .corresp j Então: Ci X Y S1 S2 S3 bj 0 2(0) 4(0) 1(0) 0(0) 0(0) 10(0) + 0 6(0) 1(0) 0(0) 1(0) 0(0) 20(0) 0 1(0) -1(0) 0(0) 0(0) 1(0) 30(0) Z 0 0 0 0 0 0 Valores da linha (C-Z): Variável: X Y S1 S2 S3 Coef F. O. 3 5 0 0 0 - Linha Z: 0 0 0 0 0 Linha (C-Z): 3 5 0 0 0 Valores da linha (C-Z) > zero (ou positivos) → melhorar Solução Ótima: encontrada quando os valores da linha (C-Z) são negativos ou nulos. 2a Tabela: Linha (C-Z): maior valor: 5 (referente a Y). - Variável que entra: Y - Variável que sai: ( ) .colunacada/p entecorrespondZValor .)O.F(objetivofunção naiávelvarda.Coefs − Maior valor da linha (C-Z) → variável que entra: Y Z = 0 – 1a tabela: linha Z nula (var. folga somente). X = Y = 0: origem para solução Gráfica. 36 Menor valor de : variável que sai - S1. Linha Principal (LP): 1a linha (referente à variável que sai – S1) Pivô: no de intersecção da coluna da variável que entra com a linha da variável que sai da base → 4. - Determinar a Nova Linha Principal (NLP): Variável X Y S1 S2 S3 bj Antiga LP Nova LP 2 4 1 0 0 10 1/2 1 1/4 0 0 2,5 - Determinar novas linhas restantes: � Valor de intersecção da linha com a coluna da variável que entra (Y): 2a linha → 1 3a linha → -1 � Multiplicar cada valor da nova linha principal (NLP) pelos números acima selecionados. � Subtrair esses resultados das linhas antigas: 2a linha: Nova S2 Variável X Y S1 S2 S3 bj Ant. S2 NLP x no NLP x no Nova S2 6 1 0 1 0 20 1/2(1) 1(1) 1/4(1) 0(1) 0(1) 2,5(1) 1/2 1 1/4 0 0 2,5 11/2 (=5,5) 0 -1/4 1 0 35/2 (=17,5) .corresp j Y b Não se consideram valores menores que zero (ou indeterminados). Implica em valor negativo para a próxima base, o que não é possível. ÷ 4 Pivô Antiga Linha ÷ 37 3a linha: Nova S3 Variável X Y S1 S2 S3 bj Ant. S3 NLP x no NLP x no Nova S3 1 -1 0 0 1 30 1/2(-1) 1(-1) 1/4(-1) 0(-1) 0(-1) 2,5(-1) -1/2 -1 -1/4 0 0 -2,5 (= - 5/2) 3/2 0 1/4 0 1 65/2 (=32,5) - Cálculo da linha Z: Ci 5 0 0 X Y S1 S2 S3 bj 1/2(5) 1(5) 1/4(5) 0(5) 0(5) 5/2(5) + 11/2(0) 0(0) -1/4(0) 1(0) 0(0) 35/2(0) 3/2(0) 0(0) ¼(0) 0(0) 1(0) 65/2(0) Z 5/2 5 5/4 0 0 25/2 - Cálculo da linha (C-Z): Variável Coef. F. O. Linha Z X Y S1 S2 S3 3 5 0 0 0 - 5/2 5 5/4 0 0 (C-Z) 1/2 0 -5/4 0 0 2a Tabela: Variáveis de decisão (título da tabela) 3 5 0 0 0 (Linha objetivo) Ci V. na Solução X Y S1 S2 S3 bj bj/aij bj/aij 5 Y ½ 1 ¼ 0 0 5/2 5/2 ÷ 1/2 5 0 S2 11/2 0 -1/4 1 0 35/2 35/2 ÷ 11/2 3,18 0 S3 3/2 0 ¼ 0 1 65/2 65/2 ÷ 3/2 21,67 Z 5/2 5 5/4 0 0 25/2 (C-Z) ½ 0 -5/4 0 0 3a Tabela: Maior valor positivo em (C-Z) = 1/2 → coeficiente da variável X. � Variável que entra na base: X. ≥≥≥≥ zero - melhorar Sai (LP) Linha (C-Z): em termos de variáveis não básicas ( X, S1) → F. obj. 38 � Variável que sai da base: S2 → Linha Principal (menor valor de bj/aij = 3,18). � Pivô = 11/2 = 5,5 - Determinar novos valores da linha principal (LP): - Determinar novas linhas restantes: � Valor de intersecção da linha com a coluna da variável que entra (X): 1a linha → 1/2 3a linha → 3/2 � Multiplicar cada valor da Nova Linha Principal (NLP) pelos números acima selecionados. � Subtrair esses resultados das linhas antigas: 1a linha: Variável X Y S1 S2 S3 bj Ant. Y NLP x no NLP x no Nova Y 1/2 1 1/4 0 0 5/2 1(1/2) 0(1/2) -1/22(1/2) 2/11(1/2) 0(1/2) 35/11(1/2) 1/2 0 -1/44 1/11 0 35/22 0 1 3/11 -1/11 0 10/11 3a linha: Variável X Y S1 S2 S3 bj Ant. S3 NLP x no NLP x no Nova S3 3/2 0 1/4 0 1 65/21(3/2) 0(3/2) -1/22(3/2) 2/11(3/2) 0(3/2) 35/11(3/2) 3/2 0 -3/44 3/11 0 105/22 0 0 7/22 -3/11 1 305/11=(27,73) Variável X Y S1 S2 S3 bj Antiga LP Nova LP 11/2 0 -1/4 1 0 35/2 1 0 -1/22 2/11 0 70/22 = 35/11 ÷ 11/2 Pivô Antiga Linha ÷ 39 - Cálculo da linha Z: Ci 5 3 0 X Y S1 S2 S3 bj 0(5) 1(5) 3/11(5) -1/11(5) 0(5) 10/11(5) + 1(3) 0(3) -1/22(3) 2/11(3) 0(3) 35/11(3) 0(0) 0(0) 7/22(0) -3/11(0) 1(0) 305/11(0) Z 3 5 297/242=1,23 1/11 0 155/11 - Cálculo da linha (C-Z): Variável Coef. F. O. Linha Z X Y S1 S2 S3 3 5 0 0 0 - 3 5 297/242 1/11 0 (C-Z) 0 0 -297/242 -1/11 0 3a Tabela: Variáveis de decisão (título da tabela) 3 5 0 0 0 (L. objetivo) Ci V. na Solução X Y S1 S2 S3 bj bj/aij 5 Y 0 1 3/11 -1/11 0 10/11 3 X 1 0 -1/22 2/11 0 35/11 0 S3 0 0 7/22 -3/11 1 305/11 Z 3 5 297/242=1,23 1/11=0,09 0 155/11 (C-Z) 0 0 -297/242 -1/11 0 Linha (C-Z): valores menores ou iguais a zero – Solução Ótima Logo: Variáveis básicas: X = 35/11 = 3,18 Z = 155/11 = 14,09 Y = 10/11 = 0,91 S3 = 305/11 = 27,73 Variáveis não básicas: S1 = S2 = 0 Ok - Valores ≤ zero - Solução Ótima. 40 Exercícios Propostos: Exemplo 3: (D. M. – Daniel Moreira – pg. 65) Maximizar Z = 2X + 5Y Sujeito a: 12X + 40Y ≤ 2400 5X + 10Y ≤ 810 X ≥ 0, Y ≥ 0 (condição de não negatividade) Exemplo 4: (P. O. – Medeiros da Silva – pg. 52) Maximizar Z = 2X1 + 3X2 + X3 Sujeito a: X1 + X2 + X3 ≤ 40 2X1 + X2 –X3 ≤ 20 3X1 + 2X2 – X3 ≤ 30 X1 ≥ 0, X2 ≥ 0, X3≥ 0 (condição de não negatividade) Fazer a lista de exercícios propostos no livro P. O. - Medeiros da Silva – pg. 56 – respostas na pg. 58. Puccini – pg. 65. Exercícios na pg. 66: Resolvido item 3.3.2 – Solução algébrica. Resolvido item 3.3.3 – Solução usando quadros (pg. 71). Problemas propostos (pg. 91): resolução na pg. 222. Exercício resolvido no livro P. O. – Medeiros da Silva – pg. 52. Sua forma de montar a solução é um pouco diferente de Daniel Moreira (abordada neste curso), mas leva à mesma resposta. Exercício resolvido no livro P. O. – Medeiros da Silva. Além da forma de montar a solução ser diferente da apresentada aqui, a tabela possui formatação diferente. Neste caso, deve-se ter o cuidado de, antes de iniciar a resolução do modelo, verificar se a variável desejada está na base. Caso não esteja, coloca-la na base através de programação linear. 41 2.5.1 – Casos Especiais (D. M. – Daniel Moreira) a) Problema de Minimização Viu-se até então: Problemas de Maximização; Restrições (≤). Problema de minimização →→→→ Problema de Maximização • Valores finais das variáveis de decisão estarão corretos. • Valor final da “função objetivo”: linha Z, coluna bj, com o “sinal trocado”. OBS.: Restrições →→→→ conservadas como as originais. Ex.: Problema de Minimização: (P. O. (Medeiros)– pág. 58) F. Objetivo: Minimizar L = 3X - 4Y + Z Restrições: X + Y + Z ≤ 10 2X + Y - Z ≤ 20 X, Y, Z ≥ 0 (restrição de não negatividade) Modelo Equivalente: F. Objetivo: Maximizar (-L) = -3X + 4Y - Z Sujeito a: X + Y + Z ≤ 10 2X +Y – Z ≤ 20 X, Y, Z ≥ 0 (restrição de não negatividade) Resolvido o “modelo equivalente”, tem-se a solução do “modelo original” com troca do sinal do valor de L e valores das variáveis básicas sem alteração. b) Problema de variável livre (P. O. – pág. 59) Caso de alguma variável do modelo não possuir a condição de não negatividade Multiplicar todos os coeficientes da “Função Objetivo” por (-1). Substituí-la pela diferença de duas outras variáveis “não negativas”. 42 Ex.: Max. Z = X1 + 2X2 + X3 Sujeito a: X1 + X2 + X 3 ≤ 10 2X1 + 3X2 ≤ 20 X1, X 3 ≥ 0, X2 → livre Modelo Equivalente: Faz-se: X2 = X4 –X5; com X4 ≥ 0 e X5 ≥ 0 Max. Z = X1 + 2X4 – 2X5 + X3 Sujeito a: X1 + X4 – X5 + X3 ≤ 10 2X1 + 3X4 – 3X5 ≤ 20 X1, X4, X5, X3 ≥ 0 A solução deste modelo resolve o anterior. Nomenclaturas de mesmo significado: Variável livre; sem restrição de sinal, variável qualquer. c) Empate na Entrada da Base (Puccini – pág. 77) Caso de empate na entrada (duas ou mais variáveis de mesmo valor positivo na linha (C-Z)): escolher arbitrariamente uma delas para entrar na base. Implicação da escolha: caminho mais longo ou mais curto para chegar à solução ótima. d) Empate na saída da Base (Puccini – pág. 77, P. O. – pág 73) Método Simplex: a linha principal é a restrição que apresenta o menor quociente, não negativo, na divisão dos termos independentes (bj) pelos coeficientes correspondentes da variável que entra na base. Variável que sai da base: variável correspondente à Linha Principal. Caso de empate na saída: escolher arbitrariamente uma das variáveis para sair da base. Ex.: Caso de empate na saída das variáveis X3 e X5. Escolha: X3: sai da base; X5 é nula (variável que fica na base). Se X3 for nula no passo seguinte: solução compatível básica DEGENERADA. (Duas variáveis nulas no passo) Artifício Matemático 2X2 43 Problemas de Degeneração: eventualmente se entra em circuitos fechados intermináveis à procura da solução ótima. e) Caso de Soluções Múltiplas (Puccini – pág. 79, P. O. – pág 73) Na linha (C-Z) do Algoritmo Simplex, os valores dos coeficientes das variáveis não básicas são diferentes de Zero →→→→ para cada solução, inclusive para a solução ótima. Se na solução ótima o coeficiente de uma variável não básica na linha (C-Z) for zero, essa variável poderá entrar na base sem alterar o valor do objetivo, gerando outra solução ótima. Neste caso, qualquer combinação linear dessas duas soluções também será solução ótima. Exercício: (Exemplo de soluções Múltiplas) (Puccini – pg. 79) Maximizar Z = X + 2Y Sujeito a: X ≤ 3 Y ≤ 4 X + 2Y ≤ 9 X ≥ 0, Y ≥ 0 (condição de não negatividade) a) Resolver pelo Método Gráfico. b) Resolver pelo Método Simplex. Solução: a) Solução Gráfica: 3a restrição:X = 0, Y = 9/2 = 4,5 Y = 0, X = 9 Caso raro (existem maneiras para solucionar: nível de exposição sem interesse nessa disciplina). Zona Permissível X + 2Y = 9 (sobre a linha) Y = 4 X = 3 X Y 9,0 B (3, 0) A (0, 0) C (3, 3) D (1, 4) E (0, 4) 4,5 3,0 44 Pontos X Y Z = X + 2Y (Max.) A 0,0 0,0 0,0 B 3,0 0,0 3,0 C 3,0 3,0 9,0 D 1,0 4,0 9,0 E 0,0 4,0 8,0 b) Solução pelo Método Simplex: Solução: Transformar inequações lineares em equações lineares. Acrescentar “Variáveis de Folga”: Maximizar Z = X + 2Y + 0S1 + 0S2 + 0S3 Sujeito a: X + 0Y + 1S1 + 0S2 + 0S3 = 3 0X + Y + 0S1 + 1S2 + 0S3 = 4 X + 2Y + 0S1 + 0S2 + 1S3 = 9 X, Y ≥ 0; S1, S2, S3 ≥ 0 (cond. não negatividade) 1a Tabela: Variáveis de decisão (título da tabela) 1 2 0 0 0 (Linha objetivo) Ci V. na Solução X Y S1 S2 S3 bj bj/aij bj/aij 0 S1 1 0 1 0 0 3 Indet. indet. 0 S2 0 1 0 1 0 4 4/1 4 0 S3 1 2 0 0 1 9 9/2 4,5 Z 0 0 0 0 0 0 (C-Z) 1 2 0 0 0 Onde: Xi: variável de decisão (i = 1, ..., 2) Sj: variável de folga (j = 1, ..., 3) Pivô: número que aparece na intersecção da coluna da variável que entra com a linha da variável que sai da base → 1. Forma genérica do problema Solução ótima (encontra-se no ponto C e D): sobre a reta CD. Variável que entra na base: Y. Sai (LP) Linha (C-Z) é descrita em termos de variáveis não básicas (neste caso: X, Y) → F. obj. 45 Linha Z: inicialmente com valores iguais l à zero (somente variáveis de folga na base) → coeficientes das variáveis de folga na função objetivo inicial. Se, além de usar variáveis de folga, for necessário usar também variável artificial (ai), isto é, quando se tem restrições com sinais (≥), aparecerá na linha Z valores diferentes de zero. Valores da linha Z: Ci X Y S1 S2 S3 bj 0 1(0) 0(0) 1(0) 0(0) 0(0) 3(0) + 0 0(0) 1(0) 0(0) 1(0) 0(0) 4(0) 0 1(0) 2(0) 0(0) 0(0) 1(0) 9(0) Z 0 0 0 0 0 0 Valores da linha (C-Z): )entecorrespondZValor( .)O.F(tivofunçãoobje alniávevarda.Coefs − Variável: X Y S1 S2 S3 Coef F. Obj.: 1 2 0 0 0 - Linha Z: 0 0 0 0 0 Linha (C-Z): 1 2 0 0 0 ( ) ij Cx produtososseSoma restriçõesdasbdireitos ladoseesCoeficient − →→→→ Para cada coluna. Valores > zero → melhorar. Variável que entra: Y. (Para cada coluna) Valor da F. O. associado à 1a tabela (Z = 0,0). X = 0, Y = 0: variáveis não básicas – origem p/ solução Gráfica. 46 Montagem da 2a Tabela: Na linha (C-Z), selecionar o maior valor (coeficiente): 2 (maior contribuição que uma variável isolada pode trazer à F. O.). - Variável que entra na base: Y (var. que corresponde ao maior coeficiente). - Variável que sai da base: 5,4 2 9 :linha3 )S:sai.(varvalormenor:4 1 4 :linha2 )esquecer(adominerdetin 0 3 :linha1 a 2 a a = = = OBS.: Usa-se Ycorrespondente, pois a variável que entra é Y. Linha Principal (LP): Linha da variável que sai (2a linha, referente a S2). - Determinar novos valores da nova linha principal (NLP): Variável X Y S1 S2 S3 bj Antiga LP Nova LP 0 1 0 1 0 4 0 1 0 1 0 4 - Determinar novas linhas restantes: (neste caso a linha de S1 e S3) 1a linha: (no = Zero) Variável X Y S1 S2 S3 bj L. Antiga NLP x no Nova S1 1 0 1 0 0 3 0(0) 1(0) 0(0) 1(0) 0(0) 4(0) - 1 0 1 0 0 3 3a linha: (no = 2) Variável X Y S1 S2 S3 bj L. Antiga NLP x no Nova S3 1 2 0 0 1 9 0(2) 1(2) 0(2) 1(2) 0(2) 4(2) - 1 0 0 -2 1 1 Ycorrespondente bj Pivô Antiga Linha ÷ 1 * Buscar a base para a entrada de Y: (0,1) 47 - Cálculo da linha Z: Ci 0 2 0 X Y S1 S2 S3 bj 1(0) 0(0) 1(0) 0(0) 0(0) 3(0) 0(2) 1(2) 0(2) 1(2) 0(2) 4(2) + 1(0) 0(0) 0(0) -2(0) 1(0) 1(0) Z 0 2 0 2 0 8 - Cálculo da linha (C-Z): Variável Coef. F. O. Linha Z X Y S1 S2 S3 1 2 0 0 0 - 0 2 0 2 0 (C-Z) 1 0 0 -2 0 Linha (C-Z) apresenta coef. > zero (melhorar). 2a Tabela: Variáveis de decisão (título da tabela) 1 2 0 0 0 (Linha objetivo) Ci V. na Solução X Y S1 S2 S3 bj bj/aij bj/aij 0 S1 1 0 1 0 0 3 3/1 3 2 Y 0 1 0 1 0 4 4/0 indet. 0 S3 1 0 0 -2 1 1 1/1 1 Z 0 2 0 2 0 8 (C-Z) 1 0 0 -2 0 Montagem da 3a Tabela: Linha (C-Z), maior valor: 1 (maior contribuição que uma variável isolada pode trazer à F. O.) – coef. da variável X. - Variável que entra na base: X - Variável que sai da base (S3) – menor valor de (LP) Xcorrespondente bj Variável que entra na base: X (maior coef. (+)). Sai (LP) Linha (C-Z) é descrita em termos de variáveis não básicas (neste caso: X, S2) → F. obj. Pivô: 1 48 - Determinar novos valores da nova linha principal (NLP): Variável X Y S1 S2 S3 bj Antiga LP Nova LP 1 0 0 -2 1 1 1 0 0 -2 1 1 - Determinar novas linhas restantes: (neste caso a linha de S1 e Y) 1a linha: (no = 1) Variável X Y S1 S2 S3 bj L. Antiga NLP x no Nova S1 1 0 1 0 0 3 1(1) 0(1) 0(1) -2(1) 1(1) 1(1) - 0 0 1 2 -1 2 2a linha: (no = zero) Variável X Y S1 S2 S3 bj L. Antiga NLP x no Nova Y 0 1 0 1 0 4 1(0) 0(0) 0(0) -2(0) 1(0) 1(0) - 0 1 0 1 0 4 - Cálculo da linha Z: Ci 0 2 1 X Y S1 S2 S3 bj 0(0) 0(0) 1(0) 2(0) -1(0) 2(0) 0(2) 1(2) 0(2) 1(2) 0(2) 4(2) + 1(1) 0(1) 0(1) -2(1) 1(1) 1(1) Z 1 20 0 1 9 - Cálculo da linha (C-Z): Variável Coef. F. O. Linha Z X Y S1 S2 S3 1 2 0 0 0 - 1 2 0 0 1 (C-Z) 0 0 0 0 -1 Linha (C-Z) apresenta coefs. ≤ zero. (Solução Ótima encontrada) Pivô Antiga Linha ÷ 1 * Buscar a base para a entrada de X: (1,0) 49 3a Tabela: Variáveis de decisão (título da tabela) 1 2 0 0 0 (Linha objetivo) Ci V. na Solução X Y S1 S2 S3 bj bj/aij bj/aij 0 S1 0 0 1 2 -1 2 2 Y 0 1 0 1 0 4 1 X 1 0 0 -2 1 1 Z 1 2 0 0 1 9 (C-Z) 0 0 0 0 -1 Variáveis Básicas: Variáveis não básicas: F. Objetivo: X = 1,0 S2 = S3 = 0,0 Z = 9,0 Y = 4,0 S1 = 2,0 Solução Ótima: pto D(1,4) da região permissível. Coeficiente da variável não básica S2 é zero na linha (C-Z). Logo, S2 poderá entrar na base sem alterar o valor do objetivo: gera outra solução ótima. Z = 0S2 –1S3 + 9 (S2 e S3: variáveis não básicas) (Coeficientes da linha (C-Z) (Z modificado) e Valor de Z (da linha Z) correspondente ao termo independente bj). Montagem da 4a Tabela: - Variável que entra na base: S2 (depois de encontrada solução ótima, variável não básica de coeficiente nulo na linha (C-Z)). - Variável que sai da base (S1) – menor valor (LP) Variável que entra na base: S2 (coef. = zero). Sai (LP) Linha (C-Z) é descrita em termos de variáveis não básicas (neste caso: S2, S3) → F. obj. Pto D(1,4) (sol. Graf.) Solução Múltipl a S2 correspondente bj 50 )esquecer( 2 1 2 1 :linha3 4 1 4 :linha2 saique.Var1 2 2 :linha1 a a a −= − = = Linha principal: referente à linha de S1. Pivô: 2 - Determinar novos valores da nova linha principal (NLP): Variável X Y S1 S2 S3 bj Antiga LP Nova LP 0 0 1 2 -1 2 0 0 1/2 1 -1/2 1 - Determinar novas linhas restantes: (neste caso a linha de X e Y) 2a linha: (no = 1) Variável X Y S1 S2 S3 bj L. Antiga NLP x no Nova Y 0 1 0 1 0 4 0(1) 0(1) 1/2(1) 1(1) -1/2(1) 1(1) - 0 1 -1/2 0 1/2 3 3a linha: (no = -2) Variável X Y S1 S2 S3 bj L. Antiga NLP x no Nova X 1 0 0 -2 1 1 0(-2) 0(-2) 1/2(-2) 1(-2) -1/2(-2) 1(-2) - 1 0 1 0 0 3 - Cálculo da linha Z: Ci 0 2 1 X Y S1 S2 S3 bj 0(0) 0(0) 1/2(0) 1(0) -1/2(0) 1(0) 0(2) 1(2) -1/2(2) 0(2) 1/2(2) 3(2) + 1(1) 0(1) 1(1) 0(1) 0(1) 3(1) Z 1 2 0 0 1 9 Pivô Antiga Linha ÷ 2 51 - Cálculo da linha (C-Z): Variável Coef. F. O. Linha Z X Y S1 S2 S3 1 2 0 0 0 - 1 2 0 0 1 (C-Z) 0 0 0 0 -1 Linha (C-Z) apresenta coefs. ≤ zero. (Outra Solução Ótima encontrada) 4a Tabela: Variáveis de decisão (título da tabela) 1 2 0 0 0 (Linha objetivo) Ci V. na Solução X Y S1 S2 S3 bj bj/aij bj/aij 0 S2 0 0 1/2 1 -1/2 1 2 Y 0 1 -1/2 0 1/2 3 1 X 1 0 1 0 0 3 Z 1 2 0 0 1 9 (C-Z) 0 0 0 0 -1 Variáveis básicas: Variáveis não básicas: F. Objetivo: X = 3 S1 = S3 = 0,0 Z = 9,0 Y = 3 S2 = 1 Ponto C(3, 3) da solução gráfica. O coeficiente de S1 (variável não básica) na linha (C-Z) é zero. Se S1 entrar na base retornamos à 3a tabela, ou seja, ao ponto D. Sendo assim, qualquer combinação linear das soluções da tabela 3 e 4, isto é, qualquer ponto de CD, também será uma solução ótima para o modelo em questão. f) Como Trabalhar com Restrições do tipo (=) e (>): (P. O. – Pág. 60, Puccini – Pág. 81) Modelos resolvidos até o presente momento pelo Algoritmo Simplex: - Restrições são do tipo (≤); - Termos da direita bj positivos (bj > 0). Se bj for negativo: multiplicar por (-1) toda a restrição. (O sinal da inequação deve ser invertido). Variável que entra na base: S1 (coef. = zero). Sai (LP) Linha (C-Z): descrita em termos de vars não básicas (neste caso: S1, S3) → F. obj. Pto C(3,3) (sol. Graf.) Solução Múltipla 52 Ex.: Restrição: X – 2Y ≤ - 3 → x (-1) -X + 2Y ≥ 3 → restrição do tipo (≥). � Trabalha-se com problemas de Maximização (caso de problemas de Minimização: transforma-lo em problema de Maximização). f.1) Restrição do tipo (=): (Daniel Moreira – pág. 65) Usa-se variável artificial (ou fictícia, ou fantasma) a. Obs.: Artifício de cálculo: a → variável incluída por meio de obter a solução. Na verdade seu valor é nulo (lado direito = lado esquerdo). Ex.: Restrições: 7X + 3Y = 13 (a1) 2X – Y = 2 (a2) Logo: 7X + 3Y + 1a1 + 0a2 =13 2X – Y + 0a1 + 1a2 = 2 Função objetivo: usar coeficientes negativos de grande valor absoluto: - M (M de grande valor absoluto). Ex.: Maximizar 12X + 5Y Maximizar 12X + 5Y - M1a1 –M2a2 Obs.: a1, a2, ..., → depende do número de restrições tipo (=); Usar: M1 = M2 = .... = M (facilitará os cálculos). f.2) Restrição do tipo (≥≥≥≥): (D. M. – pág. 65) Usam-se variáveis artificiais (ou fictícias, ou fantasmas) a e variáveis de folga S (as últimas com sinais negativos). Ex.: Restrições: 3X + 2Y ≥ 18 3X + 2Y – 1S1 + 1a1 = 18 Este procedimento assegura que as variáveis fictícias não participarão da solução. (D. M. – pág 64) -S: o que falta no lado direito para igualar ao lado esquerdo. Daí o sinal (-). 3X + 2Y + 1a1 = 18 +S1 3X + 2Y – S1 + 1a1 = 18 53 Função objetivo: usam-se variáveis de folga e artificiais (com coeficiente nulo e com coeficiente negativo de grande valor absoluto (-M), respectivamente). Ex.: Minimizar Z = 4X + 3Y Maximizar (-Z) = - 4X - 3Y Maximizar (-Z) = - 4X - 3Y - 0S1 - Ma1 Obs.: a1, a2, ..., S1, S2, ..., Exemplos: (P. O. –pág. 60) Maximizar Z = X + Y + Z Sujeito a: 2X + Y – Z ≤ 10 (variável de folga: S1) X + Y + 2Z ≥ 20 (variável folga (-): -S2 / fict.: a2) 2X + Y + 3Z = 60 (variável fictícia: a3) X, Y, Z ≥ 0 (cond. não negatividade) Problema Equivalente: Maximizar Z = X + Y + Z + 0S1 – 0S2 – M2a2 – M3a3 Sujeito a: 2X + Y – Z + S1 = 10X + Y + 2Z – S2 + a2 = 20 2X + Y + 3Z + a3 = 60 X, Y, Z ≥ 0 (cond. não negatividade) S1, S2, a2, a3 ≥ 0 (cond. não negatividade) À medida que a função Z é maximizada, as variáveis a2 e a3 deixam a base devido ao grande valor de seus coeficiente M2 e M3, respectivamente. Para montagem do quadro do Simplex, tem-se: Maximizar L = X + Y + Z + 0S1 – 0S2 – M2a2 – M3a3 Sujeito a: 2X + Y – Z + S1 + 0S2 + 0a2 + 0a3 = 10 X + Y + 2Z + 0S1 – S2 + a2 + 0a3 = 20 2X + Y + 3Z + 0S1 + 0S2 + 0a2 + a3 = 60 X, Y, Z ≥ 0 (cond. não negatividade) → dependem do número de restrições tipo (≥). Obs.: a2 = a3 = zero, linha (C-L): C - L → -M + kM (-M) (-kM) (kM > M) Variável correspondente a kM entra na base. 54 S1, S2, a2, a3 ≥ 0 (cond. não negatividade) Usar na resolução: M1 = M2 = .... = M (facilitará os cálculos). g) Problema de solução Ilimitada: (P. O. – pág. 73) Ocorre quando a variável que entra na base não possui em sua coluna nenhum coeficiente positivo. Os programas de computadores, neste caso, apresentam a última solução básica antes que a solução se torne ilimitada. Exercícios: resolvidos e propostos, quando se têm problemas abordados nos casos speciais (item 2.5.1). Daniel Moreira: (pág. 65) - exercícios resolvidos; (pág. 71) - exercícios propostos. Medeiros (P. O.) – exercícios resolvidos, principalmente para restrições do tipo (=) e (≥). Bibliografia usada na elaboração do material do curso. BIBLIOGRAFIA PRINCIPAL (BP): (Normas ABNT) /1/ - ‘Pesquisa Operacional na Tomada de Decisões – Modelagem em Excel – Para Cursos de Administração, Economia e Ciências Contábeis’, Gerson Lachtermacher – Editora Campus – Rio de Janeiro, 2002. BIBLIOGRAFIA COMPLEMENTAR (BC): (Normas ABNT) /1/ - ‘Administração da Produção e Operações’, Daniel Augusto Moreira – 3a Edição – Livraria Pioneira Editora – São Paulo, 1998. /2/ - ‘Pesquisa Operacional’, Ermes Medeiros da Silva / Elio Medeiros da Silva / Valter Gonçalves / Afrânio Carlos Murilo – 3a Edição - Editora Atlas S. A. – São Paulo, 1998. /3/ - ‘Introdução à Programação Linear’, Abelardo de Lima Puccini – Livros Técnicos e Científicos Editora S. A. – Rio de Janeiro, 1981 (última reimpressão). /4/ - ‘Introdução à Pesquisa Operacional’, Hillier / Lieberman - Editora Campus Ltda – Editora da Universidade de São Paulo – São Paulo, 1998. /5/ - ‘Pesquisa Operacional’, Richard Bronson – McGraw-Hill do Brasil – São Paulo, 1985. /6/ - ‘Modelos de Programação Linear’, Mário Jorge Braga / Mihail Lermontov / Maria Augusta Machado – Imprensa Naval – Rio de Janeiro, 1985. /7/ - ‘Pesquisa Operacional’, Harvey M. Wagner – Prentice/Hall do Brasil – Rio de Janeiro, 1986. /8/ - ‘Pesquisa Operacional – Técnicas de Otimização Aplicadas a Sistemas Agroindustriais’, José Vicente Caixeta-Filho - Editora Atlas S.A. – São Paulo, 2001. /9/ - ‘Introdução à Pesquisa Operacional – Métodos e Modelos para Análise de Decisões’, Eduardo Leopoldino de Andrade – 3a ed. - Editora LTC – Rio de Janeiro, 2002.
Compartilhar