Baixe o app para aproveitar ainda mais
Prévia do material em texto
Capítulo 3. Dualidade e Análise de Sensibilidade Apontamentos de Investigação Operacional 51 Alberto Mulenga Para x1: 1*3 + 1*0 + 7*0 – 5 = -2, logo 1 = -2 Para x2: 2*3 + 1*0 + 4*0 – 6 = 0, logo 2 = 0 O que confere com os resultados obtidos na resolução do problema. Como 1 < 0, isto significa que a solução ainda não é óptima, x1 deve entrar na base e por outro lado a solução do dual não é viável, o que nos leva a concluir que: Enquanto o primal não for óptimo, o dual será inviável; As restrições do dual, correspondentes às variáveis básicas, são satisfeitas como equações, o que significa que a respectiva variável de excesso é nula; O problema primal começa com uma solução viável não óptima que deve ser optimizada, enquanto o dual começa com uma solução inviável com valor superior ao óptimo e continua inviável até que a solução óptima seja atingida. 3.2 MÉTODO SIMPLEX DUAL – SIMPLEX Até agora, nos problemas de programação linear que consideramos era obrigatório que todos os elementos do lado direito da tabela simplex fossem positivos. Isto significa que todas as soluções eram viáveis. Pela propriedade 4, sabemos que as soluções duais são inviáveis até que a solução óptima seja obtida. No entanto é possível que durante o processo de solução, venhamos a ter uma solução dual viável, o que significa inviável no primal. O método Dual – Simplex se destina a resolver esse tipo de problema. As diferenças em relação ao método simplex se resumem nas regras de entrada e saída de variáveis na base. 3.2.1 Regras de entrada e saída de variáveis na base Dado um problema de minimização para resolvé-lo pelo método Dual - Simplex deve-se transformar as inequações do tipo para , em seguida aplicar as regras 1 e 2 para o problema de minimização. Regra 1. Variável que sai: é a variável básica com o menor valor negativo. Se todas as variáveis básicas tiverem valores positivos, a solução é óptima. Regra 2. Variável que entra: é escolhida entre as variáveis fora da base, da seguinte forma: Dividir os coeficientes do lado esquerdo da equação z transformada (coeficientes da função objectivo) pelos correspondentes coeficientes negativos da equação da variável que sai 0a ; a c α ij ij i ij Capítulo 3. Dualidade e Análise de Sensibilidade Apontamentos de Investigação Operacional 52 Alberto Mulenga A variável que entra é a que tem o menor valor entre os quocientes encontrados (para o problema de minimização) ou o menor valor absoluto (para o problema de maximização). Quando, em ambos os casos, não houver coeficientes negativos na linha da variável que sai da base, o problema não tem solução viável. Exemplo 3.5. Resolver o seguinte problema pelo método dual - simplex. Minimizar W = 2x1 + 1x2 Sujeito à 0 321 634 21 21 ix xx xx Resolução Para resolver o problema sem usar o método de duas fazes nem do grande M, vamos escrever o problema na forma padrão e introduzimos depois as variáveis de folga. Minimizar W = 2x1 + 1x2 Min W = 2x1 + 1x2 + 0x3 + 0x4 Sujeito à 0 321 634 21 21 ix xx xx Suj. à 0 3021 6034 4321 4321 ix xxxx xxxx Tabela inicial simplex Base x1 x2 x3 x4 bi x3 x4 -4 -3 1 0 1 2 0 1 -6 3 W -2 -1 0 0 (1/2) (1/3) 0 A variável que sai é x3 porque x3 = -6; e x2 entra na base porque 1/3 < 1/2. 1 a iteração Base x1 x2 x3 x4 bi x2 x4 4/3 1 -1/3 0 -5/3 0 2/3 1 2 l1’=-1/3l1 -1 l2’=l2-2l1 ’ W -2/3 0 -1/3 0 (2/5) 2 l3’=l3+l1 ’ 2 a iteração Base x1 x2 x3 x4 Bi x2 x1 0 1 1/5 4/5 1 0 -2/5 -3/5 6/5 l1’=l1- 4/3l’2 3/5 l2’=-3/5l2 W 0 0 -3/5 -2/5 12/5 l3’=l3+2/3l2 ’ Solução X = {3/5; 6/5; 0; 0} Wmin = 12/5 Para a solução dual temos Y = (3/5; 2/5; 0; 0} Zmax = 12/5 Capítulo 3. Dualidade e Análise de Sensibilidade Apontamentos de Investigação Operacional 53 Alberto Mulenga Exemplo 3.6. Resolver o problema de programação linear. (a) pelo método gráfico (b) pelo método dual - simplex. Minimizar W = 3x1 +2x2 Sujeito à 0 3 634 33 21 21 21 ix xx xx xx 54 3 2 1 , ... ... ... rr r r r a) Resolução pelo método gráfico R1: x1 x2 R2 : x1 x2 R3: x1 x2 recta W: x1 x2 0 3 0 2 0 3 0 0 1 0 3/2 0 3 0 1 -3/2 1 1 432 4 3 2 -1 x1 x2 r1 r2 r3 W Do gráfico o ponto extremo e mínimo é P = r1 r2 Resolvendo o sistema das rectas 634 313 21 21 xx xx teremos a solução X = (3/5; 6/5) com Wmin = 21/5 Capítulo 3. Dualidade e Análise de Sensibilidade Apontamentos de Investigação Operacional 54 Alberto Mulenga b) Resolvendo pelo método dual – simplex, temos: Minimizar W = 3x1 +2x2 + 0x3 +0x4 +0x5 Sujeito à 0 310011 60034 30013 54321 54321 54321 ix xxxxx xxxxx xxxxx Tabela inicial simplex Base x1 x2 x3 x4 x5 bi x3 x4 x5 -3 -1 1 0 0 -4 -3 0 1 0 1 1 0 0 1 -3 -6 3 W -3 -2 0 0 0 (3/4) (2/3) 0 1 a Iteração Base x1 x2 x3 x4 x5 bi x3 x2 x5 -5/3 0 1 -1/3 0 4/3 1 0 -1/3 0 -1/3 0 0 1/3 1 -1 l1’=l1+l2 ’ 2 l2’=-1/3l2 ’ 1 l3’=l3 -l2 ’ W -1/3 0 0 -2/3 0 (1/5) (2) 4 l4’=l4+2l2 ’ 2 a Iteração Base x1 x2 x3 x4 x5 Bi x1 x2 x5 1 0 -3/5 1/5 0 0 1 4/5 -3/5 0 0 0 -1/5 2/5 1 3/5 l1’=-3/5l1 6/5 l2’=l2 -4/3l1 ’ 6/5 l3’=l3 +1/3l1 ’ W 0 0 -1/5 -3/5 0 21/5 l4’=l4+1/3l1 ’ Solução X = (3/5; 6/5; 0;0;6/5) com Wmin = 21/5 3.2.2 EXERCÍCIOS PROPOSTOS Exercício 3.1. Escreva os problemas na forma canónica e transforme – os em duais. a) Minimizar W = 9y1 + 2y2 b) Maximizar Z = 16x1 + 12x2 Sujeito à 0 123 134 21 21 iy yy yy Sujeito à 0 213 9 16 21 21 21 ix xx xx xx Capítulo 3. Dualidade e Análise de Sensibilidade Apontamentos de Investigação Operacional 55 Alberto Mulenga Exercício 3.2. Considere o seguinte problema de programação linear: Minimizar W = 5x1 + 2x2 Sujeito à 0 4 2 1 6 82 21 21 21 ix xx xx xx a) Escreva o problema dual correspondente. b) Obtenha a solução do primal a partir da resolução do dual pelo método simplex. (Resp. X = (0; 8; 0; 2; 4) com Wmin = 16 u.m) Exercício 3.3. Considere o seguinte problema de programação linear. Maximizar Z = 12x1 + 15x2 Sujeito à 0 1052 1234 21 21 ix xx xx Usando o método simplex resolva o problema e apresente as soluções do primal e dual. (Primal: Resp. X = (15/7; 8/7; 0; 0) com Zmax = 300/7) (Dual : Resp: Y = (15/7; 12/7; 0; 0) com Wmin = 300/7) Exercício 3.4. Nos seguintes casos transformar em duais e depois resolver os problemas. a) Min W = 5y1 + 2y2b) Min W = 2y1 + 1y2 + 3y3 Sujeito à 0 712 632 21 21 iy yy yy Sujeito à 0 50012 100111 321 321 iy yyy yyy c) Min W = 7y1 + 5y2 d) Min W = 2y1 + 1y2 Sujeito à 0 82 821 412 21 21 21 iy yy yy yy Sujeito à 0 1012 2012 21 21 iy yy yy a) Resp. Y = (0; 7; 15; 0) com Wmin = 14 b) Resp. Y = (0; 100; 0; 0; 50) com Wmin = 100 c) Resp. Y = (2; 0; 0; 10; 4) com Wmin = 14 d) Resp. Y = (10; 0; 0; 0; 10) com Wmin = 20 Capítulo 3. Dualidade e Análise de Sensibilidade Apontamentos de Investigação Operacional 56 Alberto Mulenga Exercício 3.5. Uma empresa de transporte dispõe de dois tipos de camiões que podem operar em três percursos diferentes. A capacidade semanal de transporte em cada um dos tipos de camiões e a procura semanal mínima de serviços de carga, expressos em toneladas estão indicados no quadro seguinte. Percursos Tipos de camiões Procura mínima Tipo A Tipo B 1 2 3 10 12 10 10 15 10 180 200 220 Sabendo que os custos de operação de cada camião são 50 e 80 u.m por semana respectivamente, quantos veículos de cada tipo deve a empresa utilizar nos percursos indicados, de modo a minimizar os custos. (use o procedimento dual se necessário). (Resp. Y = (22; 0; 40; 64; 0) com Wmin = 1100 u.m.) Exercício 3.6. Resolva o seguinte problema de programação linear, primeiro graficamente e depois pelo algoritmo dual do método simplex. Minimizar W = 4y1 + 5y2 Sujeito à 0 753 802 21 21 iy yy yy (Resp. Y = (14; 33; 0; 0) com Wmin = 221) Exercício 3.7. Resolva os seguintes problemas pelo método dual simplex, se necessário apresente a solução pelo método gráfico. Nota: substituir as equações por duas inequações. a) Min W = 4x1 + 2x2 suj. à 0 23 1 21 21 ix xx xx b) Min W = 2x1+3x2 suj. à 0 211 312 21 21 ix xx xx Respostas: a) X = (3/4; 1/4 ; 0; 0; 0) Wmin = 7/2 b) X = (2; 0; 1; 0; 0) Wmin = 4
Compartilhar