Baixe o app para aproveitar ainda mais
Prévia do material em texto
Pesquisa Operacional. Método Fç. Objetiva Artificial W (continuação). Exemplo de Fç Objetivo de Minimização. 73 PO - PESQUISA OPERACIONAL Profa. Léa Benatti b) Método da Função Objetiva Artificial W (P. O. – pág. 67, Puccini – pág. 83) (Continuação) Exercício2 – Método da Função Objetiva Artificial W (Puccini – pág. 83) Maximizar Z = 5x + 2y Sujeito a: x ≤ 3 (var. folga: S1) y ≤ 4 (var. folga: S2) x + 2y ≥ 9 (var. folga (-): -S3 / artificial: a3) x ≥ 0, y ≥ 0 (cond. não negatividade) Solução: Minimizar W = a3 Sujeito a: x + 1S1 = 3 (1a restrição) y + 1S2 = 4 (2a restrição) x + 2y – 1S3 + 1a3 = 9 (3a restrição) x, y ≥ 0; S1, S2, S3 ≥ 0; a3 ≥ 0 (cond. não negatividade) 3a restrição: a3 = 9 – x – 2y + 1S3 Substituindo a3 em W: Minimizar W = 9 - x – 2y + 1S3 Problema de Minimizar Problema de Maximizar Maximizar (-W) = - 9 + x + 2y –1S3 Maximizar (-W + 9) = x + 2y – 1S3 OBS.: Deve-se achar: W = 0 Minimizar W = Maximizar (-W) Como W = 0,W = -W = 0 X (-1) 74 1a Tabela: (Inicialmente, trabalha-se com a função W) Variáveis de decisão(título da tabela) 1 2 0 0 -1 0 9 (L. obj.) Ci Var. Sol. X y S1 S2 S3 a3 bj bj/aij 0 S1 1 0 1 0 0 0 3 3/0=ind 0 S2 0 1 0 1 0 0 4 4/1=4 0 a3 1 2 0 0 -1 1 9 9/2=4,5 W 0 0 0 0 0 0 0 (C-W) 1 2 0 0 -1 0 9 Pivô: 1 Onde:x, y, : variáveis de decisão ai: variável de fictícia (i = 2, 3) Sj:variável de folga (j = 1, 2) Valores da linha W: (ver Tabela 1) Valores da linha (C-W): (ver Tabela 1) Linha (C-W) apresenta valores positivos, portanto melhorar a solução (solução ótima não encontrada). X Ci →→→→ Para cada coluna. Coeficientes e lados direitos (bj) das restrições e F. obj. Soma-se os produtos. - (Valor W correspondente) Para cada coluna. Coefs. da variável na função objetivo (F. O.) Variável que entra na base: y. Linha (C-W): em termos de variáveis não básicas (neste caso: x, y, S3)→→→→ F. obj. Sai (LP) Termo independente (bj): não entra na análise da variável que entra na base. 75 Montagem da 2a Tabela: - Variável que entra na base: y→→→→ maior coeficiente na linha (C-W): (2). -Variável que sai da base: entecorrespond j y b →→→→ S2 Linha Principal (LP): Linha da variável que sai (referente a S2). OBS.: Observar que está presente na base uma variável artificial (ou fictícia) a3. Verificar se a entrada da variável de segundo (ou terceiro, ou quarto, ...) maior coeficiente positivo da linha (C-W) retira a variável artificial da base. Caso nenhum destes valores eliminarem a variável artificial, voltar à situação inicial entrando na base com a variável de maior coeficiente positivo, o que significa que a variável artificial sairá da base em um passo posterior. Esta verificação implica em eliminar passos de cálculo, possibilitando trabalhar com menor número de tabelas e menor exposição a erros. Neste exercício, após verificação abordada acima, conclui-se que a3 será eliminada posteriormente. - Determinar os valores da novalinhaprincipal (NLP): (Linha Antiga) ÷ Pivô (=1) Variável X y S1 S2 S3 a3 bj Antiga LP Nova LP 0 1 0 1 0 0 4 0 1 0 1 0 0 4 -Determinar novas linhas restantes (linhas S1 e a3): 1a linha: (no = 0) Variável X y S1 S2 S3 a3 bj L. Antiga NLP x no Nova S1 1 0 1 0 0 0 3 - 0(0) 1(0) 0(0) 1(0) 0(0) 0(0) 4(0) 1 0 1 0 0 0 3 3a linha: (no = 2) Variável x y S1 S2 S3 a3 bj L. Antiga NLP x no Nova a3 1 2 0 0 -1 1 9 - 0(2) 1(2) 0(2) 1(2) 0(2) 0(2) 4(2) 1 0 0 -2 -1 1 1 76 - Cálculo da linha W:(ver tabela 2) - Cálculo da linha (C-W): (ver tabela 2) Linha (C-W) apresenta coefs. > zero(melhorar). 2a Tabela: Variáveis de decisão(título da tabela) 1 2 0 0 -1 0 9 (L. obj.) Ci Var. Sol. X y S1 S2 S3 a3 bj bj/aij 0 S1 1 0 1 0 0 0 3 3/1=3 2 y 0 1 0 1 0 0 4 4/0=ind 0 a3 1 0 0 -2 -1 1 1 1/1=1 W 0 2 0 2 0 0 8 (C-W) 1 0 0 -2 -1 0 1=W Obs.: Até o presente momento: Variáveis básicas: Variáveis não básicas: S1 = 3 x = S2 = S3 = 0 y= 4 a3 = 1 Função obj. Artificial: W = 1 a3≠ 0 W ≠ 0 Montagem da 3a Tabela: Linha (C-W), maior coeficiente positivo: (1) – coeficiente da variável x (desconsiderar coeficiente do termo independente). -Variável que entra na base: x -Variável que sai da base: entecorrespond j x b →→→→ a3→→→→ L. P. Var. que entra na base: x. Linha (C-W): descrita em termos de variáveis nãobásicas (neste caso: x, S2, S3)→→→→ F. obj. Sai (LP) Pivô:1 Continuar até a função objetivo artificial W e a variável a3 ser zero. 77 -Determinar os valores da nova linha principal (NLP): (Linha Antiga) ÷ Pivô (=1) Variável X y S1 S2 S3 a3 bj Antiga LP Nova LP 1 0 0 -2 -1 1 1 1 0 0 -2 -1 1 1 -Determinar novas linhas restantes (linhas S1 e z): 1a linha: (no = 1) Variável x y S1 S2 S3 a3 bj L. Antiga NLP x no Nova S1 1 0 1 0 0 0 3 - 1(1) 0(1) 0(1) -2(1) -1(1) 1(1) 1(1) 0 0 1 2 1 -1 2 2a linha: (no = 0) Variável X y S1 S2 S3 a3 bj L. Antiga NLP x no Nova z 0 1 0 1 0 0 4 - 1(0) 0(0) 0(0) -2(0) -1(0) 1(0) 1(0) 0 1 0 1 0 0 4 - Cálculo da linha W:(ver tabela 3) (coef., bj x Ci); soma. - Cálculo da linha (C-W): (ver tabela 3) (Ci Fç. Obj. - Wi), i: coluna Linha (C-W) apresenta coef. ≤zero (Solução ótima em W). 3a Tabela: Variáveis de decisão (título da tabela) 1 2 0 0 -1 0 9 (L. obj.) Ci Var. Sol. X y S1 S2 S3 a3 bj bj/aij 0 S1 0 0 1 2 1 -1 2 2 y 0 1 0 1 0 0 4 1 x 1 0 0 -2 -1 1 1 W 1 2 0 0 -1 1 9 (C-W) 0 0 0 0 0 -1 0=W W = 0 Coefs. da linha (C-W) ≤ 0 →→→→ Solução ótima em W. Tem-se uma solução básica formadapelas variáveis originais. (x, y) = (1, 4): Pto extremo 78 Obs.: Até o momento: Variáveis básicas: Variáveis não básicas: S1 = 2 S2 = S3 = a3 = 0 y= 4 x= 1 Função Obj.: W = 0 Abandonar variável artificial a3 e continuar os cálculos com a função objetivo original Z. OBS.: Notar que os coeficientes das variáveis não básicas na linha (C-W) são nulos: S2 = S3 = 0. Como se trata de função objetiva artificial W, não é necessário procurar outras soluções para encontrar seu mínimo. O que se deseja é maximizar Z e somente após encontrar Solução em Z é que há a necessidade de verificar se é caso de Solução Múltipla. 4a Tabela: Variáveis de decisão(título da tabela) 5 2 0 0 0 (L. obj.) Ci Var. Sol. x y S1 S2 S3 bj bj/aij 0 S1 0 0 1 2 1 2 2/2=1 2 y 0 1 0 1 0 4 4/1=4 5 x 1 0 0 -2 -1 1 1/(-2)<0 Z 5 2 0 -8 -5 13 (C-Z) 0 0 0 8 5 Linha Z: (Coef., bj x Ci), Soma (Ver tabela 4) Ci 0 2 5 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(5) 0(5) 0(5) -2(5) -1(5) 1(5) Z 5 2 0 -8 -5 13 Observar que a3 é variável não básica (a3 =0) e W = 0. ↓ Mínimo valor de W é encontrado (zero). Var. que entra na base: S2. Linha (C-Z) é descrita em termos de variáveis não básicas (neste caso: S2, S3)→→→→ F. obj. Sai (LP) Pivô:2 79 OBS.: Neste estágio, Ci das variáveis básicas correspondem aos coeficientes da função objetiva original (Z). Linha (C-Z): Coeficientes da F. obj. original Z. (Ver tabela 4) Variáveis Coef. F. O. Z x y S1 S2 S3 5 2 0 0 0 - 5 2 0 -8 -5 (C-Z) 0 0 0 8 5 S2: Variável de maior coeficiente positivo – entra na base. Obs.:Até o presente momento: (ver Tabela 4) Variáveis básicas: Variáveis não básicas: S1 = 2 S2 = S3 = 0 y= 4 x= 1 Função Obj.: Z = 13 Montagem da 5a Tabela: L. P. →→→→ referente a variável S1 →→→→ Pivô = 2 -Determinar os valores da nova linha principal (NLP): (Linha Antiga) ÷ Pivô (=2) 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 (linhas y e x): 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 80 - Cálculo da linha Z: (ver tabela 5) Linha Z:(Coef., bj x Ci), Soma - Cálculo da linha (C-Z): (ver tabela 5) Linha (C-Z): coeficiente > zero (melhorar). 5a Tabela: Variáveis de decisão(título da tabela) 5 2 0 0 0 (Linha objetivo) Ci V. na Solução x y S1 S2 S3 bj bj/aij 0 S2 0 0 1/2 1 1/2 1 1/(1/2) = 2 2 y 0 1 -1/2 0 -1/2 3 3/(-1/2) < 0 5 x 1 0 1 0 0 3 3/0 = ind. Z 5 2 4 0 -1 21 (C-Z) 0 0 -4 0 1 Obs.:Até o momento: (ver Tabela 5) Variáveis básicas: Variáveis não básicas: S2 = 1 S1 = S3 = 0 x = y= 3 Função Obj.: Z = 21 Montagem da 6a Tabela: Variável que entra na base:S3 Variável que sai da base:S2 →→→→ L. P. - Determinar os valores da nova linha principal (NLP): (Linha Antiga) ÷ Pivô (=1/2) Variável x y S1 S2 S3 bj Antiga LP Nova LP 0 0 1/2 1 1/2 1 0 0 1 2 1 2 Var. que entra na base: S3. Linha (C-Z) é descrita em termos de variáveis não básicas (neste caso: S1, S3)→ F. obj. Sai (LP) Pivô:1/2 81 - Determinar novas linhas restantes (linhas y e x): 2a linha: (no = -1/2) Variável x y S1 S2 S3 bj L. Antiga NLP x no Nova y 0 1 -1/2 0 -1/2 3 - 0(-1/2) 0(-1/2) 1(-1/2) 2(-1/2) 1(-1/2) 2(-1/2) 0 1 0 1 0 4 3a linha: (no = 0) Variável x y S1 S2 S3 bj L. Antiga NLP x no Nova x 1 0 1 0 0 3 - 0(0) 0(0) 1(0) 2(0) 1(0) 2(0) 1 0 1 0 0 3 - Cálculo da linha Z: Linha Z: (Coef., bj x Ci), Soma (ver tabela 6) - Cálculo da linha (C-Z): (ver tabela 6) Linha (C-Z): coeficiente ≤ zero (Solução Ótima). 6a Tabela: Variáveis de decisão(título da tabela) 5 2 0 0 0 (Linha objetivo) Ci V. na Solução x y S1 S2 S3 bj bj/aij 0 S3 0 0 1 2 1 2 2 y 0 1 0 1 0 4 5 x 1 0 1 0 0 3 Z 5 2 5 2 0 23 (C-Z) 0 0 -5 -2 0 � Coeficientes de S1 e S2 (variáveis não básicas)na linha (C-Z) ≠ zero →→→→ Solução não é múltipla. Solução ótima do modelo: Variáveis básicas: Variáveis não básicas: F. Objetivo: S3= 2 S1 = S2 = 0 Z = 23 y= 4 x= 3 Pto (x, y) = (3, 4) Linha (C-Z): descrita em termos de variáveis não básicas (neste caso: S1, S2) →→→→ F. obj. 82 Solução ótima corresponde ao ponto (x, y) = (3, 4) →→→→ ponto extremo (vértice) da zona permissível em caso de se usar método gráfico. Problemas Propostos: Exercício1(Puccini – pág. 86 – exercício resolvido) Achar, pelo processo da função objetiva artificial, todas as Soluções compatíveis básicas do seguinte sistema de equações: 3X1 + 2X2 – 5X3 = 6 (var. artificial) 4X1 +7X2 + 4X3 = 9 (var. artificial) X1 ≥ 0; X2 ≥ 0; X3 ≥ 0 (condições não negativas) Solução: 3X1 + 2X2 – 5X3 + a1 = 6 4X1 +7X2 + 4X3 + a2 = 9 X1 ≥ 0; X2 ≥ 0; X3 ≥ 0 W = a1 + a2 ; a1 = 6 - 3X1 – 2X2 + 5X3 a2 = 9 - 4X1 – 7X2 - 4X3 W = 15 – 7X1 – 9X2 + X3 Minimizar W = 15 – 7X1 – 9X2 + X3 (x (-1) →→→→ maximizar W) Maximizar (-W) = -15 + 7X1 + 9X2 – X3 Maximizar (-W) +15 = 7X1 + 9X2 – X3 1a Tabela: Variáveis de decisão(título da tabela) 7 9 -1 0 0 15 (L. objetivo) Ci V. na Solução X1 X2 X3 a1 a2 bj bj/aij 0 a1 3 2 -5 1 0 6 6/2 = 3 0 a2 4 7 4 0 1 9 9/7 = 1,29 W 0 0 0 0 0 0 (C-W) 7 9 -1 0 0 15 Checar ai: a1 = a2 = 0 W = 0 Var. que entra na base: a2. Linha (C-W): descrita emtermos de variáveis não básicas (neste caso: X1, X2, X3) → F. obj. Sai (LP) Pivô: 7 83 Nova Linha Principal: (L. antiga) ÷ pivô (= 7) Variável X1 X2 X3 a1 a2 bj Antiga LP Nova LP 4 7 4 0 1 9 4/7 1 4/7 0 1/7 9/7 Nova Linha a1:(Linha antiga) – (NLP x no) 1a linha: (no = 2) Variável X1 X2 X3 a1 a2 bj L. Antiga NLP x no Nova a1 3 2 -5 1 0 6 - 4/7(2) 1(2) 4/7(2) 0(2) 1/7(2) 9/7(2) 13/7 0 -43/7 1 -2/7 24/7 -Cálculo da linha W: (ver tabela 2) Linha W:(Coef., bj x Ci), Soma -Cálculo da linha (C-W): (ver tabela 2) Linha (C-W): coeficiente > zero (melhorar). ... Resposta: Solução múltipla: variável não básica X3 apresenta coeficiente nulo na linha (C-W) da tabela que gera a Solução ótima em W. Primeira Solução: Variáveis básicas: Variáveis não básicas: F. obj. artificial: X1 = 24/13 X3 = 0 W = 0 X2 = 3/13 a1 = a2 = 0 Mínimo de W = 0→ indica que se obteve uma solução compatível básica para o sistema Segunda Solução: Variáveis básicas: Variáveis não básicas: F. obj. artificial: X1 = 897/416 X2 = 0 W = 0 X3 = 3/32 a1 = a2 = 0 84 Exercício2: (Puccini – pág. 88 – exercício resolvido) Resolver o modelo de programação linear abaixo, usando o Método da Função Objetiva Artificial. Minimizar Z = 3X1 + 2X2 , sujeito a X1 + X2 ≥ 5 2X1 + X2 ≥ 7 X1, X2 ≥ 0 (condição não negativa) Resposta: Solução ótima: (não é caso de solução múltipla) Variáveis básicas: Variáveis não básicas: F. objetiva: X2 = 3 S1, S2 = 0 Z = 12 X1 = 2 a1 = a2 = 0 Obs.: Caso de minimizar a função objetivo: Valores das variáveis básicas são os encontrados no quadro que gera a solução ótima e o valor da função objetivo Z tem sinal contrário do obtido no mesmo quadro. Exercício3: (Puccini – pág. 88 – exercício resolvido pelo método W) Resolver o exercício anterior usando o método do M grande. Exercício4: (Puccini – pág. 91 – no 3.1 - exercício resolvido) Resolva o seguinte problema de programação linear, utilizando o método Simplex: Maximizar Z = 7X1 + 9X2 , sujeito a X1 - X2 ≥ - 2 3X1 + 5X2 ≤ 15 5X1 + 4X2 ≥ 20 X1, X2 ≥ 0 (condição não negativa) Resposta: Solução ótima: Variáveis básicas: Variáveis não básicas: F. objetiva: X2 = 15/13 S2, S3 = 0 Z = 415/13 X1 = 40/13 a3 = 0 S1 = 51/13 85 Exercício5: (Puccini – pág. 91 – no 3.2 - exercício resolvido) Resolva o seguinte problema de programação linear: Maximizar Z = 3X1 + 2X2 + 5X3, sujeito a 2X1 + 3X2 + 4X3 ≤ 10 5X1 + 6X2 + 2X3 ≤ 12 X1, X2, X3 ≥ 0 (condição não negativa) Resposta: Solução ótima: Variáveis básicas: Variáveis não básicas: F. objetiva: X3 = 13/8 X2 = 0 Z = 107/8 X1 = 7/4 S1 = S2 = 0 Exercício6: (Puccini – pág. 92 – no 3.5 - exercício resolvido) Resolva o seguinte problema de programação linear: Maximizar Z = 4X1 + 2X2 + 2X3, sujeito a X1 + X2 + 2X3 ≤ 4 4X1 - 5X2 + 3X3 ≤ 30 X1, X3 ≥ 0 (condição não negativa) Notar que X2 não tem restrição de sinal. Resposta: X2 = X2’ – X2” Solução ótima: Variáveis básicas: Variáveis não básicas: F. objetiva: X1= 50/9 X3, X2’ = 0 Z = 172/9 X2” = 14/9 S1 = S2 = 0 X2 = 0 – (14/9) = - 14/9 Exercício7: (Puccini – pág. 92 – no 3.8 - exercício resolvido) Achar, pelo processo da Função Objetiva Artificial, todas as soluções compatíveis básicas do sistema: X1 + X2 + X3 = 1/3 X1 + X2 + 3X3 = 1 Resposta: Solução ótima (única solução compatível básica): Variáveis básicas: Variáveis não básicas: F. objetiva: X2 = 0 X1 = 0 W = 0 X3 = 1/3 a1, a2 = 0 86 Exercício8: (P. O. (Medeiros) – pág. 73 – no 1) Resolva pelo Simplex, usando o método do M grande para obter a solução básica inicial. Maximizar Z = 2X1 + 3X2 , sujeito a X1 + X2 ≥ 10 2X1 + X2 ≤ 16 X1, X2 ≥ 0 (condição não negativa) Resposta: X1 = 0,X2 = 16, Z = 48 Exercício9: (P. O. (Medeiros) – pág. 75 – no 7) Minimizar Z = 3X1 + 2X2 + X3, sujeito a 3X1 + X2 + 3X3 ≥ 6 3X1 + 2X2 = 6 X1 - X2 ≤ 1 X1, X2, X3 ≥ 0 (condição não negativa) Resposta: X1 = 1,60; X2 = 0,60; X3 = 0,20; Z = 6,20 Exercício10: (P. O. (Medeiros) – pág. 74) Minimizar Z = 3X1 + 2X2 , sujeito a 2X1 + X2 ≥ 10 X1 + 5X2 ≥ 15 X1, X2 ≥ 0(condição não negativa) Resposta: X1 = 3,89; X2 = 2,22; Z = 16,11 Exercício - Minimização: Exercício1 (P. O. - Medeiros – pág. 74 – exercício de Minimização) Resolver pelo Método Simplex: Min Z = 3X1 + 2 X2 , Sujeito a: 2X1 + X2 ≥10 (var. folga (-) e artificial) X1 + 5X2 ≥ 15 (var. folga (-) e artificial) X1, X2 ≥ 0; (condições não negativas) Resposta: X1 = 3,89 X2 = 2,22 Z = 16,11 87 Solução: Método de M Grande: Max. (-Z) = -3X1 - 2X2 Max.(-Z) = - 3X1- 2X2 -0S1- 0S2- Ma1 - Ma2 S. a. 2X1 + X2 – S1 + a1 = 10 X1 + 5X2 –S2 + a2 = 15 X1, X2, S1 , S2 , a1 , a2 ≥ 0 1a Tabela: Variáveis de decisão (título da tabela) -3 -2 0 0 -M -M (L. obj.) Ci Var. Sol. X1 X2 S1 S2 a1 a2 bj bj/aij -M a1 2 1 -1 0 1 0 10 10/1=10 -M a2 1 5 0 -1 0 1 15 15/5=3 Z -3M -6M M M -M -M -25M (C-Z) (3M-3) (6M- 2) -M -M 0 0 - Determinar NLP: (Linha Antiga) ÷ Pivô (=5) Variável X1 X2 S1 S2 a1 a2 bj Antiga LP Nova LP 1 5 0 -1 0 1 15 1/5 1 0 -1/5 0 1/5 3 -Nova a1: 1a linha: (no = 1) Variável X1 X2 S1 S2 a1 a2 bj L. Antiga NLP x no Nova a1 2 1 -1 0 1 0 10 - 1/5 1 0 -1/5 0 1/5 3 9/5 0 -1 1/5 1 -1/5 7 Variável que entra na base: X2. Linha (C-Z): em termos de variáveis não básicas (neste caso: X1, X2, S1, S2) →→→→ F. obj. Sai (LP) 88 2a Tabela: Variáveis de decisão (título da tabela) -3 -2 0 0 -M -M (L. obj.) Ci Var. Sol. X1 X2 S1 S2 a1 a2 bj bj/aij -M a1 9/5 0 -1 1/5 1 -1/5 7 35/9=3,88 -2 X2 1/5 1 0 -1/5 0 1/5 3 15 Z -(9M/5 +2/5) -2 M (-M/5 +2/5) -M (M/5 - 2/5) -7M-6 (C-Z) (9M/5 -13/5) 0 -M (M/5- 2/5) 0 (-6M/5 +2/5) -Determinar NLP:(Linha Antiga) ÷ Pivô (=9/5)Variável X1 X2 S1 S2 a1 a2 bj Antiga LP Nova LP 9/5 0 -1 1/5 1 -1/5 7 1 0 -5/9 1/9 5/9 -1/9 35/9 -Novo X2: 2a linha: (no = 1/5) Variável X1 X2 S1 S2 a1 a2 bj L. Antiga NLP x no NovoX2 1/5 1 0 -1/5 0 1/5 3 - 1/5 0 -1/9 1/45 1/9 -1/45 35/45 0 1 1/9 -2/9 -1/9 2/9 20/9 3a Tabela: Variáveis de decisão (título da tabela) -3 -2 0 0 -M -M (L. obj.) Ci Var. Sol. X1 X2 S1 S2 a1 a2 bj bj/aij -3 X1 1 0 -5/9 1/9 5/9 -1/9 35/9 -2 X2 0 1 1/9 -2/9 -1/9 2/9 20/9 Z -3 -2 13/9 1/9 -13/9 -1/9 -145/9 (C-Z) 0 0 -13/9 -1/9 (-M+ 13/9) (-M +1/9) Variável que entra na base: X1. Linha (C-Z): em termos de variáveis não básicas (neste caso: X1, S1, S2, a2) →→→→ F. obj. Sai (LP) Solução Ótima Linha (C-Z): em termos de variáveis não básicas (neste caso: S1, S2, a1, a2) →→→→ F. obj. 89 Solução: Variáveis básicas: Variáveis não básicas: F. obj.: X1 = 35/9 = 3,89 S1 =S2 = 0 (-Z) = -145/9 = -16,11 X2 = 20/9 = 2,22 a1 = a2 = 0 (Z) = 16,11 * Coeficientes de S1 e S2 (variáveis não básicas) ≠ Zero → não é caso de solução múltipla. Solução: Método da Função Objetiva Artificial W: Max. (-Z) = -3X1 - 2X2 a1 = 10 – 2X1 – X2 + S1 a2 = 15 – X1 – 5X2 + S2 W = a1 + a2 W = 10 – 2X1 – X2 + S1+ 15 – X1 – 5X2 + S2 W = 25 – 3X1 – 6X2 + S1+ S2 Min. W = 25 – 3X1 – 6X2 + S1+ S2 → x (-1) Min. (-W) = - 25+3X1+6X2 - S1- S2 Min. (-W) + 25 = 3X1 + 6X2 - S1 - S2 1a Tabela: (Inicialmente, trabalha-se com a função W) Variáveis de decisão (título da tabela) 3 6 -1 -1 0 0 25 (L. obj.) Ci Var. Sol. X1 X2 S1 S2 a1 a2 bj bj/aij 0 a1 2 1 -1 0 1 0 10 10/1=10 0 a2 1 5 0 -1 0 1 15 15/5=3 W 0 0 0 0 0 0 0 (C-W) 3 6 -1 -1 0 0 25 - Determinar NLP: (Linha Antiga) ÷ Pivô (=5) Variável X1 X2 S1 S2 a1 a2 bj Antiga LP Nova LP 1 5 0 -1 0 1 15 1/5 1 0 -1/5 0 1/5 3 Entra na base Sai L. P. OBS.: Coeficiente da linha (C-W) e coluna bj não entra na avaliação da variável que entra na base. 90 - Nova a1: 1a linha: (no = 1) Variável X1 X2 S1 S2 a1 a2 bj L. Antiga NLP x no Nova a1 2 1 -1 0 1 0 10 - 1/5 1 0 -1/5 0 1/5 3 9/5 0 -1 1/5 1 -1/5 7 2a Tabela: Variáveis de decisão (título da tabela) 3 6 -1 -1 0 0 25 (L. obj.) Ci Var. Sol. X1 X2 S1 S2 a1 a2 bj bj/aij 0 a1 9/5 0 -1 1/5 1 -1/5 7 35/9=3,89 6 X2 1/5 1 0 -1/5 0 1/5 3 15 W 6/5 6 0 -6/5 0 6/5 18 (C-W) 9/5 0 -1 1/5 0 -6/5 7 -Determinar NLP:(Linha Antiga) ÷ Pivô (=9/5) Variável X1 X2 S1 S2 a1 a2 bj Antiga LP Nova LP 9/5 0 -1 1/5 1 -1/5 7 1 0 -5/9 1/9 5/9 -1/9 35/9 -Novo X2: 2a linha: (no = 1/5) Variável X1 X2 S1 S2 a1 a2 bj L. Antiga NLP x no NovoX2 1/5 1 0 -1/5 0 1/5 3 - 1/5 0 -1/9 1/45 1/9 -1/45 35/45 0 1 1/9 -10/45 -1/9 10/45 20/9 3a Tabela: Variáveis de decisão (título da tabela) 3 6 -1 -1 0 0 25 (L. obj.) Ci Var. Sol. X1 X2 S1 S2 a1 a2 bj bj/aij 3 X1 1 0 -5/9 1/9 5/9 -1/9 35/9 6 X2 0 1 1/9 -2/9 -1/9 2/9 20/9 W 3 6 -1 -1 1 1 25 (C-W) 0 0 0 0 -1 -1 0=W Variável que entra na base: X1. Sai (LP) Solução Ótima em W. 91 W = 0; a1 = a2 = 0 ok 4a Tabela: (F. Obj. Original Z) Variáveis de decisão (título da tabela) -3 -2 0 0 (L. obj.) Ci Var. Sol. X1 X2 S1 S2 bj bj/aij -3 X1 1 0 -5/9 1/9 35/9 -2 X2 0 1 1/9 -2/9 20/9 Z -3 -2 13/9 1/9 -145/9 (C-Z) 0 0 -13/9 -1/9 Solução: Variáveis básicas: Variáveis não básicas: F. obj.: X1 = 35/9 = 3,89 S1 =S2 = 0 (-Z) = -145/9 = -16,11 X2 = 20/9 = 2,22 a1 = a2 = 0 (Z) = 16,11 * Coeficientes de S1 e S2 na linha (C-Z) (variáveis não básicas) ≠ Zero → não é caso de solução múltipla. PRGRAMAÇÃO INTEIRA: Em um modelo de Programação Linear, se alguma ou se todas as variáveis de decisão devem apresentar valores inteiros, deve-se usar um algoritmo de resolução chamado “Método da Ramificação e Limites” (é um algoritmo de Programação Linear Inteira). Obs.: Programação Inteira é considerada restrição do modelo de Programação Linear. ≤≤≤≤ 0: Solução Ótima em Z. 92 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