Baixe o app para aproveitar ainda mais
Prévia do material em texto
3.2.3. Método de M Grande Para um problema de Programação Linear em que todas as restrições são do tipo menor ou igual (≤), com os termos independentes não negativos, as varáveis de folgas introduzidas asseguram uma conveniente solução básica inicial. Entretanto, uma questão natural surge quando se pretende determinar uma solução básica inicial para modelos que envolvem restrições do tipo igualdade (=) e do tipo maior ou igual (≥). Para modelos desta natureza, o procedimento comum é o de introdução de variáveis fictícias, que assumem o papel de variáveis de folga na primeira solução básica. E o método de M Grande é aplicado para resolução de problemas deste tipo. O Método de M Grande começa com a apresentação do problema de PL na forma canónica. Neste processo, todas as restrições do tipo maior ou igual (≥) e as do tipo igualdade (=) recebem variáveis de fictícias RI. Estas variáveis fazem parte da primeira solução básica. Entretanto, dado que as variáveis fictícias são externas ao modelo original de PL elas são penalizadas na Função Objectiva através de um valor M suficientemente grande. E dado que o M é um valor positivo suficientemente grande, toda variável Ri é penalizada na Função Objectivo com: • sinal negativo (–), no caso de maximização; e • sinal positiv0 (+), no caso de minimização. Devida esta penalização, a natureza do processo de optimização logicamente tenderá a anular toda variável Ri ao longo das iterações do Simplex. O exemplo a seguir dá detalhes sobre o Método de M Grande. Exemplo Nº 1: Seja dado o seguinte problema de Programação Linear: 0, 3 1523 234: 6: 21 21 21 21 21 ≥ =− ≥+ ≤+ += xx xx xx xxaSujeito xxzMaximizar Para resolver este problema de PL pelo Método de M Grande é necessário reduzir o problema na forma canónica, transformando todas as restrições em igualdades. Neste caso, em que nem todas as restrições são do tipo menor ou igual, deve-se adicionar uma variável de folga (s1), no primeiro membro da primeira restrição, subtrair uma variável de excesso (S2), na segunda restrição e não alterar a terceira restrição. Além disso, deve-se modificar a função objectiva. Estas operações têm como resultado o problema apresentado na forma canónica, com o seguinte aspecto: 0,,, 3 1523 234: 006: 2121 21 221 121 2121 ≥ =− =−+ =++ +++= Ssxx xx Sxx sxxaSujeito SsxxzMaximizar A segunda e a terceira restrições não possuem variáveis que possam desempenhar o papel da variável de folga na determinação da primeira Solução Básica. Assim, deve ser introduzidas duas varáveis fictícias (R1 e R2) nesta duas restrições e penaliza-las na Função Objectivo. Estas operações têm como resultado o problema com o seguinte aspecto: 0,,,, 3 1523 234: 6: 212121 221 1221 121 2121 ≥ =+− =+−+ =++ +++= RRSsxx Rxx RSxx sxxaSujeito MRMRxxzMaximizar Em seguida, deve-se escolher as variáveis a entrar na primeira Solução Básica, através da determinação do número de graus de liberdade (D). Neste exemplo, após a introdução das variáveis de folga, de excesso e fictícias, o problema passou a ter seis (6) variáveis. Entretanto, o número de restrições mantém-se igual a três (3). Assim, o número de graus de liberdade será: D=6 – 3 = 3 E no presente exemplo, D=3 indica que devem ser anuladas três (3) variáveis. E, segundo as regra, devem ser anuladas inicialmente as variáveis originais do problema e, em seguida, as de excesso. E, após a última transformação do problema as suas restrições ficaram com o seguinte aspecto: 3 1523 234 221 1221 121 =+− =+−+ =++ Rxx RSxx sxx Destas relações, e de acordo com as regras, anulando as variáveis originais do problema (x1 e x2), e a variável de excesso (S2), obtém-se a primeira Solução Básica, que é a seguinte: = = = = === 0 3 15 23 0 2 1 1 221 z R R s Sxx Depois da terminação da primeira Solução Básica construi-se a primeira Tabela do Simplex, procedendo de modo análogo aos casos anteriores. Entretanto, a linha da Função Objectivo (linha do z) deve ser apresentada mostrando os efeitos da penalização decorrente da introdução das variáveis fictícias no modelo original. Deste modo, tem-se a seguinte tabela: x1 x2 s1 S2 R1 R2 s1 1 4 1 0 0 0 23 R1 3 2 0 – 1 1 0 15 R2 1 – 1 0 0 0 1 3 z – 1 – 4M – 6 – M 0 M 0 0 – 18M Nesta tabela, as três linhas intermédias representam as equações das restrições cujos termos independentes estão dados na última coluna. E a linha do z obtém-se passando todas as variáveis da função objectivo para o primeiro membro e penalizando as variáveis fictícias (R1 e R2). Passando todas as variáveis da Função Objectivo, tem-se: Z – x1 – 6x2 = 0. Os elementos da Linha da Função Objectivo foram obtidos associando os coeficientes de x1 e x2 da última expressão associadas aos valores decorrentes da penalização das variáveis fictícias que são obtidos através do produto de +M ou –M, pela soma dos coeficientes constantes nas linhas das variáveis fictícias Ri. Neste caso de Maximização utiliza-se –M, para a penalização e os coeficientes das segunda e terceira linhas, pois é nestas linhas onde figurão as variáveis fictícias R1 e R2. Assim, os elementos da linha da Função Objectivo foram obtidos de seguinte modo: • para a coluna de x1: – 1 + (3 + 1)×(–M) = – 1 – 4M; • para a coluna de x2: – 6 + (2 – 1)×(–M) = – 6 – M; • para a coluna de s1: 0 + (0 + 0)×(–M) = 0; • para a coluna de S2: 0 + (–1 + 0)×(–M) = M; e • para a última coluna: 0 + (15 + 3)×(–M) = – 18M; e • as colunas das variáveis fictícias (R1 e R2) não são penalizadas. x1 x2 s1 S2 R1 R2 s1 1 4 1 0 0 0 23 R1 3 2 0 – 1 1 0 15 R2 1 – 1 0 0 0 1 3 z – 1 – 4M – 6 – M 0 M 0 0 – 18M As transformações iterativas das tabelas de Simplex, até se atingir os valores óptimos do problema, são feitas de modo análogo aos casos anteriores. Neste caso, em que se procura determinar um máximo, de acordo com as regras, escolhe-se a variável que apresenta o coeficiente mais negativo na linha da Função Objectivo (z). Deste modo, será a coluna de – 1 – 4M, pois, M é um valor suficientemente grande. Por isso, (– 1 – 4M) é menor que (– 6 – M). Entretanto, para transformar a última linha (linha de z) é necessário determinar o factor a ser usado nas operações do Pivot para a transformação de todos elementos desta linha. Neste caso, e de acordo com as regras, o elemento da Coluna Pivot é menos três (– 1 – 4M) e o seu simétrico é três (1 + 4M). Dividindo esta última expressão pelo Elemento Pivot (1) obtém-se (1 + 4M). E para obtenção dos novos elementos desta linha é necessário fazer as operações do Pivot. Assim, os novos elementos da última linha serão os seguintes: • para a coluna de x1: 0)41(141 =+×+−− MM ; • para a coluna de x2: MMM 57)41(16 −−=+×−−− ; • para a coluna de s1: 0)41(00 =+×+ M ; • para a coluna de S2: MMM =+×+ )41(0 ; • para a coluna de R1: 0)41(00 =+×+ M ; • para a coluna de R2: MM 41)41(10 +=+×+ ; e • para a coluna das soluções: MMM 63)41(318 −=+×+− . x1 x2 s1 S2 R1 R2 s1 0 5 1 0 0 – 1 20 R1 0 5 0 – 1 1 – 3 6 x1 1 – 1 0 0 0 1 3 z 0 – 7 – 5M 0 M 0 1 + 4M 3 – 6M Toda variável fictícia, após ser anulada deve ser retirada da Tabela de Simplex. Sendo assim, a próxima tabela não apresenta a coluna de R1. x1 x2 s1 S2 R1 s1 0 0 1 1 – 1 14 x2 0 1 0 – 5 1 5 1 5 6 x1 1 0 0 – 5 1 5 1 5 21 z 0 0 0 – 5 7 M+ 5 7 5 57 Desta tabela pode-se observar que ainda existe uma Coluna Pivot, facto que indica que ainda não foi atigida a solução óptima do problema. Sendo assim, fazendo–se a sua transformação de modo análogo aos casos anteriores, obtém-se a seguinte tabela: x1 x2 s1 S2 s2 0 0 1 1 14 x2 0 1 5 1 0 4 x1 1 0 5 1 0 7 z 0 0 5 7 0 31 Desta última tabela, pode-se observar que já não existem mais valores negativos na linha da Função Objectivo. Isto significaque já foram encontrados os valores óptimos. E a solução óptima do problema é extraída directamente da tabela e é a seguinte: = = = = 31 14 4 7 * 2 * 2 * 1 z s x x Exemplo Nº 2: Seja dado o seguinte problema de Programação Linear: 0, 232 10 723: 3: 21 21 21 21 21 ≥ =+− ≤+ ≥− += xx xx xx xxaSujeito xxzMinimizar A resolução deste problema procedesse de modo análogo ao caso anterior. Isto é, no início faz-se a transformação do problema para forma canónica, introduzindo: • uma variável de excesso (S1) e uma variável fictícia (R1), na primeira restrição, por ser do tipo maior ou igual (≥); • uma variável de folga (s2) na segunda restrição, por ser do tipo menor ou igual (≤); • uma variável fictícia (R2) na terceira restrição, por ser do tipo igualdade (=). 0,,,,, 232 10 723: 3: 212121 221 221 1121 2121 ≥ =++− =++ =+−− +++= RRsSxx Rxx sxx RSxxaSujeito MRMRxxzMinimizar Depois da transformação, usam-se as novas restrições para determinar a primeira Solução Básica. Para além disso, é necessário apresentar a Função Objectivo com todas as variáveis no primeiro membro. Assim, tem-se: 232 10 723 221 221 1121 =++− =++ =+−− Rxx sxx RSxx Neste caso, o número de graus de liberdade será D=6 – 3 =3 o que implica que a primeira Solução Básica será: = = = = === 0 2 10 7 0 2 2 1 121 z R s R Sxx Após a transformação a função objectivo fica com o seguinte aspecto: 03 21 =−− xxz Depois da terminação da primeira Solução Básica e da transformação da função objectivo, construi-se a primeira tabela de Simplex, que é a seguinte: x1 x2 S1 s2 R1 R2 R1 3 – 2 – 1 0 1 0 7 s2 1 1 0 1 0 0 10 R2 – 2 3 0 0 0 1 2 z – 1 + M – 3 + M – M 0 0 0 9M Neste caso de Minimização utiliza-se +M, para a penalização e os coeficientes das primeira e terceira restrições, pois é nelas onde figurão as variáveis fictícias R1 e R2. Assim, os elementos da linha da Função Objectivo foram obtidos de seguinte modo: • para a coluna de x1: – 1 + (3 – 2)×M = – 1 + M; • para a coluna de x2: – 3 + (– 2 + 3)×M = – 3 + M; • para a coluna de S1: 0 + ( – 1 + 0)×M = – M; • para a coluna de s2: 0 + (0 + 0)×M = 0; e • para a última coluna: 0 + (7 + 2)×M = 9M; e • as colunas das variáveis fictícias (R1 e R2) não são penalizadas. As transformações iterativas das tabelas de Simplex, até se atingir os valores óptimos do problema, são feitas de modo análogo aos casos anteriores. Neste caso, em que se procura determinar um mínimo, de acordo com as regras, escolhe-se a variável que apresenta o coeficiente mais positivo na linha da Função Objectivo (z). Deste modo, será a coluna de (–1+M), pois, M é um valor suficientemente grande. Por isso, (–1+M) é maior que (–3+M). Entretanto, para transformar a última linha (linha de z) é necessário determinar o factor a ser usado nas operações do Pivot para a transformação de todos elementos desta linha. Neste caso, e de acordo com as regras, o elemento da Coluna Pivot é (– 1+M) e o seu simétrico é três (1–M). Dividindo esta última expressão pelo Elemento Pivot, o três (3), obtém-se ( 3 1 M− ). E para obtenção dos novos elementos desta linha é necessário fazer as operações do Pivot. Assim, os novos elementos da última linha serão os seguintes: • para a coluna de x1: 0) 3 1 (31 =−×++− MM ; • para a coluna de x2: M M M 3 5 3 11 ) 3 1 (23 −−=−×−+− ; • para a coluna de S1: M M M 3 2 3 1 ) 3 1 (1 −−=−×−− ; • para a coluna de s2: 0) 3 1 (00 =−×+ M ; • para a coluna de R1: M M 3 1 3 1 ) 3 1 (10 −=−×+ ; • para a coluna de R2: 0) 3 1 (00 =−×+ M ; e • para a coluna das soluções: M M M 3 20 3 7 ) 3 1 (79 +=−×+ . Assim, após a transformação, usando-se as operações do Pivot, obtém-se a seguinte tabela: x1 x2 S1 s2 R1 R2 x1 1 – 3 2 – 3 1 0 3 1 0 3 7 s2 0 3 5 3 1 1 – 3 1 0 3 23 R2 1 3 5 – 3 2 0 3 2 1 3 20 z 0 M 3 5 3 11 +− M 3 2 3 1 −− 0 M 3 1 3 1 − 0 M 3 20 3 7 + Como se sabe, toda variável fictícia, após ser anulada deve ser retirada da Tabela de Simplex. Sendo assim, a próxima tabela não apresenta a coluna de R1. x1 x2 S1 s2 R2 x1 1 0 – 5 3 0 5 2 5 s2 0 0 1 1 – 1 1 x2 0 1 – 5 2 0 5 3 4 z 0 0 – 5 9 0 M− 5 11 17 Desta última tabela, pode-se observar que já não existem mais valores positivos na linha da Função Objectivo. Isto significa que já foram encontrados os valores óptimos. E a solução óptima do problema é extraída directamente da tabela e é a seguinte: = = = = 17 1 4 5 * 2 * 2 * 1 z s x x 3.2.3.2. Problemas Resolvidos Exercício Nº 1: Resolva o seguinte problema de Programação Linear: 0,, 723 62 2132: 52: 321 321 21 321 321 ≥ ≥+− =− ≤++ +−= xxx xxx xx xxxaSujeito xxxzMaximizar 1º)Transformar o problema na forma canónica; 0,,,,,, 723 62 2132: 52: 2121321 22321 121 1321 21321 ≥ =+−+− =+− =+++ +++−= RRSsxxx RSxxx Rxx sxxxaSujeito MRMRxxxzMaximizar 2º)Determinar a primeira Solução Básica; 723 62 2132 22321 121 1321 =+−+− =+− =+++ RSxxx Rxx sxxx D = 7 – 3 = 4 ⇒: = = = = ==== 0 7 6 21 0 2 1 1 2321 z R R s Sxxx 3º)Modificar a Função Objectivo. 0)(52 21321 =++−+− RRMxxxz 4º)Compor a primeira tabela de Simplex e efectuara as sua transformações iterativas. x1 x2 x3 s1 S2 R1 R2 s1 2 1 3 1 0 0 0 21 R1 1 -2 0 0 0 1 0 6 R2 1 -3 2 0 –1 0 1 7 Z 2–2M 2+5M –5–2M 0 M 0 0 –13M x1 x2 x3 s1 S2 R1 R2 s1 2 1 2 11 0 1 2 3 0 – 2 3 2 21 R1 1 –2 0 0 0 1 0 6 x3 2 1 – 2 3 1 0 – 2 1 0 2 1 2 7 z M− 2 1 M2 2 11 +− 0 0 – 2 5 0 M+ 2 5 M6 2 35 − x1 x2 x3 s1 S2 R1 s1 0 2 13 0 1 2 3 – 2 1 2 15 x1 1 -2 0 0 0 1 6 x3 0 – 2 1 1 0 – 2 1 – 2 1 2 1 z 0 – 2 9 0 0 – 2 5 M+− 2 1 2 29 x1 x2 x3 s1 S2 x2 0 1 0 13 2 13 3 13 15 x1 1 0 0 13 4 13 6 13 108 x3 0 0 1 13 1 13 5− 13 14 z 0 0 0 13 9 13 19− 13 256 x1 x2 x3 s1 S2 S2 0 3 13 0 3 2 1 5 x1 1 -2 0 0 0 6 x3 0 3 5 1 3 1 0 3 z 0 3 19 0 3 5 0 27 5º) Compor a solução óptima do problema: = = = = = 27 5 3 0 6 * 2 * 3 * 2 * 1 z S x x x Exercício Nº 2: Resolva o seguinte problema de Programação Linear: 0,, 725 23 15425: 3: 321 321 32 321 321 ≥ =++ ≤− ≥++ −+= xxx xxx xx xxxaSujeito xxxzMinimizar 1º)Transformar o problema na forma canónica; 0,,,,,, 725 23 15425: 3: 2121321 2321 232 11321 21321 ≥ =+++ =+− =+−++ ++−+= RRSsxxx Rxxx sxx RSxxxaSujeito MRMRxxxzMinimizar 2º)Determinar a primeira Solução Básica; 723 23 15425 2321 232 11321 =++− =+− =+−++ Rxxx sxx RSxxx D = 7 – 3 = 4 ⇒: = = = = ==== 0 7 2 15 0 2 2 1 1321 z R s R Sxxx 3º)Modificar a Função Objectivo. 0)(3 21321 =+++−− RRMxxxz 4º)Compor a primeira tabela de Simplex e efectuara as sua transformações iterativas. x1 x2 x3 S1 s2 R1 R2 R1 5 2 4 –1 0 1 0 15 s2 0 3 –1 0 1 0 0 2 R2 1 5 2 0 0 0 1 7 z –1+6M –3+7M 1+6M –M 0 0 0 22M x1 x2 x3 S1 s2 R1 R2 R1 5 0 3 14 –1 3 2− 1 0 3 41 x2 0 1 3 1− 0 3 1 0 0 3 2 R2 1 0 3 11 0 3 5− 0 1 3 11 z -1+6M 0 M 3 25 –M M 3 7 1 − 0 0 M 3 52 2 + x1 x2 x3 S1 s2 R1 R2 R1 11 41 0 0 –1 11 16 1 11 14− 9 x2 11 1 1 0 0 11 2 0 11 1 1 x3 11 3 0 1 0 11 5− 0 11 3 1 z M 11 41 1+− 0 0 –M M 11 16 1+ 0 M 11 25− 2+9M x1 x2 x3 S1 s2 R1 x1 1 0 0 41 11− 41 16 41 11 41 99 x2 0 1 0 41 1 41 6 41 1− 41 32 x3 0 0 1 41 1 41 23− 41 3− 41 14 z 0 0 0 41 11− 41 57 M− 41 11 41 181 x1 x2 x3 S1 s2 x1 1 3 8− 0 3 1− 0 3 1 s2 0 6 46 0 6 1 1 3 16 x3 0 6 23 1 6 1 0 3 10 z 0 2 19− 0 2 1− 0 –3 5º) Compor a solução óptima do problema: −= = = = = 3 3 16 3 10 0 3 1 * 2 * 3 * 2 * 1 z s x x x 3.2.4. Casos especiais no Método de Simplex Esta secção considera quatro casos especiais que têm surgido na aplicação do Método de Simplex, a saber: • soluções degeneradas;• soluções alternativas; • soluções ilimitadas; e • soluções inexistentes ou inviáveis. Existem duas razões essenciais para o interesse no estudo dos casos especiais no Método de Simplex. Estas são: • a explicação teórica das razões de surgimento destes casos; e • a interpretação prática destes casos em problemas reais. 3.2.4.1. Soluções degeneradas. Na aplicação das condições de viabilidade do Método de Simplex, para a determinação da variável a sair da solução básica, a regra de selecção do mínima razão positiva pode não ser satisfeita. Por exemplo, uma ou mais variáveis básicas podem assumir o valor zero (0) após a conclusão de uma certa iteração. Neste caso, a nova solução obtida é degenerada. Exemplo 1 – Considere o seguinte problema: 0, 42 84: 73: 21 21 21 21 ≥ ≤+ ≤+ += xx xx xxSujeito xxzMaximizar Resolvendo este problema tem-se: 0,,, 42 84: )(073: 2121 221 121 2121 ≥ =++ =++ +++= ssxx sxx sxxSujeito ssxxzMaximizar 42 84 221 121 =++ =++ sxx sxx = = = == ⇒=−= 0 4 8 0 224 2 1 21 z s s xx D 073 21 =−−= xxz 1x 2x 1s 2s 1s 1 4 1 0 8 2s 1 2 0 1 4 z –3 –7 0 0 0 1x 2x 1s 2s 2x 4 1 1 4 1 0 2 2s 2 1 0 2 1 1 0 z 4 5− 0 4 5− 0 14 Nesta iteração inicial, qualquer uma das variáveis de folga s1 e s2 podia sair da solução básica. Por esta razão, ao se escolher a variável s1 a variável s2 assumiu o valor zero (0). Resultando, deste modo, uma solução básica degenerada. E a solução óptima é alcançada após se efectuar uma iteração adicional. 1x 2x 1s 2s 2x 0 1 2 1 2 1− 2 1x 1 0 –1 2 0 z 0 0 2 1 2 5 14 Deste modo obtém-se a solução óptima degenerada é a seguinte: = = = 14 2 0 * * 2 * 1 z x x A implicação prática de degenerescência pode ser explicada através da figura 9 que dá a solução gráfica do modelo. Naquela figura, pode-se observar que três rectas passam pelo ponto optimizado (x1=0; x2=2). Uma vez que se trata de um problema bidimensional, o ponto diz-se que é sobredeterminado, pois necessita-se apenas de duas rectas para o definir. Deste modo, conclui-se que uma das restrições é redundante. Na prática, o simples conhecimento de que alguns dos recursos são supérfluos pode tornar-se muito útil durante a escolha da solução. Esta informação pode, também, levar a identificação de irregularidades no estabelecimento do modelo. Infelizmente, não existem regras para identificar as restrições redundantes a partir do Quadro de Simplex. Por isso, na ausência da resolução gráfica é difícil localizar a redundância. 1 2 3 5 6 7 8-1-2-3-4 -1 -2 1 6 5 4 3 2 0 x1 x2 4 9 • 7 x 1 + 4x2 ≤ 8 (redundante) x 1 + 2x 2 ≤ 4 z = 3x1 + 7x 2 Solução óptima degenerada Figura 3.8. – Solução óptima degenerada Sob o ponto de vista teórico, a degenerescência tem duas implicações, a saber: i. A recirculação – se verificar-se as iterações 1 e 2, dos quadros de Simplex anteriores, observa-se que o valor da função objectivo não muda (z=14). Admite- se assim, em termos genéricos, que o Método de Simplex repetirá a mesma sequência de iterações sem nuca melhorar o valor da função objectivo e sem terminar os cálculos; ii. A identidade das soluções – examinando-se as mesmas iterações 1 e 2, pode-se observar que ambas conduzem a valores idênticos para todas as variáveis e para a função objectivo (x1=0, x2=2, s1=0, s2=0 e z=14), embora sejam diferentes na classificação das varáveis em básicas e não básicas. Deste modo, pode-se admitir a possibilidade de se para os cálculos assim que se revele a degenerescência, apesar de se obter a solução óptima. No entanto, este conceito não é aceitável, pois a solução pode ser temporariamente degenerada, segundo o exemplo abaixo. Exemplo 2 – Considere o seguinte problema: 0, 1234 84 84: 23: 21 21 21 21 21 ≥ ≤+ ≤− ≤+ += xx xx xx xxSujeito xxzMaximizar Resolvendo este problema tem-se: 0,,,, 1234 84 84: )(023: 32121 321 221 121 32121 ≥ =++ =+− =++ ++++= sssxx sxx sxx sxxSujeito sssxxzMaximizar 1234 84 84 321 221 121 =++ =+− =++ sxx sxx sxx = = = = == ⇒=−= 0 12 8 8 0 235 3 2 1 21 z s s s xx D 023 21 =−−= xxz 1x 2x 1s 2s 3s 1s 4 1 1 0 0 8 1s 4 –1 0 1 0 8 3s 4 3 0 0 1 12 z –3 –2 0 0 0 0 1x 2x 1s 2s 3s 1x 1 4 1 4 1 0 0 2 2s 0 –3 –1 1 0 0 3s 0 2 –1 0 1 4 z 0 4 5− 4 3 0 0 6 Observando-se o último quadro, verifica-se a degenerescência aparece nesta iteração 1. Entretanto, efectuando-se a segunda iteração, verifica-se que, diferentemente do caso anterior, a degenerescência desaparece na iteração 2 e o valor da função objectivo melhora de z=6 na iteração 1, para 2 17=z , na iteração 2, conforme se observa no quadro abaixo. 1x 2x 1s 2s 3s 1x 1 0 8 3 0 8 1− 2 3 2s 0 0 2 5− 1 2 3 6 2x 0 1 2 1− 0 2 1 2 z 0 0 8 1 0 8 5 2 17 Neste caso em que a degenerescência ocorre uma iteração intermédia o problema tem solução temporariamente degenerada. Por esta razão, as iterações do Simplex devem ser continuadas até se encontrar a solução óptima. E para este caso, a solução óptima não degenerada do problema é a seguinte: = = = 2 17 2 2 3 * * 2 * 1 z x x 3.2.4.2. Soluções alternativas. Geralmente, quando a função objectivo é paralela a uma das restrições, ela assume um valor optimizado em mais do que um ponto, como soluções. Por isso, estas soluções são chamadas soluções alternativas. Exemplo 1 – Considere seguinte problema: 0, 4 52: 42: 21 21 21 21 ≥ ≤+ ≤+ += xx xx xxSujeito xxzMaximizar Resolvendo este problema tem-se: 0,,, 4 52: )(042: 2121 221 121 2121 ≥ =++ =++ +++= ssxx sxx sxxSujeito ssxxzMaximizar 4 52 221 121 =++ =++ sxx sxx = = = == ⇒=−= 0 4 5 0 224 2 1 21 z s s xx D 042 21 =−− xxz 1x 2x 1s 2s 1s 1 2 1 0 5 2s 1 1 0 1 4 z –2 –4 0 0 0 1x 2x 1s 2s 2x 2 1 1 2 1 0 2 5 2s 2 1 0 2 1− 1 2 3 z 0 0 2 0 10 Este último quadro mostra que a solução optimizada é encontrada logo depois de efectuar-se esta primeira iteração, sendo ( 0*1 =x , 2 5* 2 =x e 10* =z ). Veja-se agora como é que sabe que existe uma solução alternativa a partir do quadro de Simplex. Verificando-se os coeficientes das variáveis não básicas na linha da função objectivo (z) na iteração 1,verifica-se que o coeficiente da variável x1 é nulo (0), sendo esta uma variável não básica. Isto indica que a variável x1 pode entrar na solução básica sem alterar o valor da função objectivo z, mas causando alterações dos valores das variáveis. Assim, a segunda iteração faz com que, entrando o x1 na solução básica, vai forçar a saída do s2. Daqui resulta uma nova solução, que é a seguinte: ( 3*1 =x , 1 * 2 =x e 10* =z ). 1x 2x 1s 2s 2x 0 1 1 –1 1 1x 1 0 –1 2 3 z 0 0 2 0 10 Neste caso, diz-se que o problema tem pelo menos duas soluções óptimas alternativas, conforme acima se apresentam. Na prática, o conhecimento de soluções alternativas é muito útil, porque dá ao gestor a possibilidade de escolher a solução que melhor responde a situação em estudo sem sofrer qualquer alteração da função objectivo. Exemplo 2 – Considere o seguinte problema: 0, 1553 1836 2: 2: 21 21 21 21 21 ≥ ≤+ ≤+ ≤− += xx xx xx xxSujeito xxzMaximizar Resolvendo este problema tem-se: 0,,,, 1553 1836 2: )(02: 32121 321 221 121 32121 ≥ =++ =++ =+− ++++= sssxx sxx sxx sxxSujeito sssxxzMaximizar 1553 1836 2 321 221 121 =++ =++ =+− sxx sxx sxx = = = = == ⇒=−= 0 15 18 2 0 235 3 2 1 21 z s s s xx D 02 21 =−−= xxz 1x 2x 1s 2s 3s 1s 1 –1 1 0 0 2 2s 6 3 0 1 0 18 3s 3 5 0 0 1 15 z –2 –1 0 0 0 0 1x 2x 1s 2s 3s 1x 1 –1 1 0 0 2 2s 0 9 –6 1 0 6 3s 0 8 –3 0 1 9 z 0 –3 2 0 0 4 1x 2x 1s 2s 3s 1x 1 0 3 1 9 1 0 3 8 2x 0 1 3 2− 9 1 0 3 2 3s 0 0 3 7 9 8− 1 311 z 0 0 0 3 1 0 6 Este último quadro mostra que a solução optimizada é encontrada logo depois de efectuar-se esta segunda iteração, sendo ( 3 8* 1 =x , 32 * 2 =x e 6* =z ). Entretanto, verificando- se os coeficientes das variáveis não básicas na linha da função objectivo (z),verifica-se que o coeficiente da variável s1 tornou-se novamente nulo (0), sendo esta uma variável não básica. Similarmente ao caso anterior, isto indica que a variável s1 pode entrar na solução básica sem alterar o valor da função objectivo z, mas causando alterações dos valores das variáveis. Assim, efectuando-se a terceira iteração obtém-se uma nova solução, que é a seguinte ( 7 15* 1 =x , 7 12* 2 =x e 6* =z ). conforme se pode observar no quadro abaixo. 1x 2x 1s 2s 3s 1x 1 0 0 21 2 7 1− 7 15 2x 0 1 1 7 1− 7 2 7 12 3s 0 0 0 21 8 7 3 7 11 z 0 0 0 3 1 0 6 3.2.4.3. Soluções não limitadas Em alguns modelos de Programação Linear os valores das variáveis podem ser aumentados indefinidamente sem se violar nenhuma das restrições, o que significa que o espaço das soluções não é limitado, pelo menos numa das direcções. Daí resulta que o valor da função objectivo pode aumentar (caso de maximização) ou diminuir (caso da minimização) indefinidamente. Neste caso, pode-se dizer que, tanto o espaço das soluções, como o valor optimizado da função objectivo são não limitados. Na prática, a não limitação num modelo indica que esse modelo não foi bem estabelecido. Pois se, por exemplo, um modelo gera uma solução que dá um lucro infinito, ele é completamente desprovido de senso. E, em casos reais, os erros mais usuais que originam a não limitação são os seguintes: • a não consideração de uma ou mais restrições não redundantes; e • a estimação inadequada dos parâmetros, ou seja, dos coeficientes das restrições. Exemplo 1 – Considere seguinte problema: 0, 5 2: 2: 21 1 21 21 ≥ ≤ ≤− += xx x xxSujeito xxzMaximizar Resolvendo este problema tem-se: 0,,, 5 2: )(02: 2121 21 121 2121 ≥ =+ =+− +++= ssxx sx sxxSujeito ssxxzMaximizar 5 2 21 121 =+ =+− sx sxx = = = == ⇒=−= 0 5 2 0 224 2 1 21 z s s xx D 02 21 =−− xxz 1x 2x 1s 2s 1s 1 –1 1 0 2 2s 1 0 0 1 5 z –1 –2 0 0 0 Neste quadro de partida pode ver que, tanto o x1, como o x2 podem entrar para a solução básica. Contudo, uma vez que o x2 tem maior coeficiente negativo na função objectivo é ele que deve ser seleccionado como variável de entrada. Entretanto, todos os coeficientes das restrições relativas a x2 não são positivas. Isto indica que o x2 pode crescer indefinidamente sem comprometer nenhuma das soluções. Dado que cada aumento de x2 aumenta o z, um aumento infinito de x2 causa também um aumento infinito de z. Assim, conclui-se o problema tem solução não limitada. Este facto pode ser verificado na figura abaixo onde se observa que o espaço de soluções é ilimitado na direcção de x2. Figura 3.9. – Solução não limitada Exemplo 2 – Considere o seguinte problema: 0, 623 4 3: 3: 21 21 1 21 21 ≥ ≥+ ≤ ≤− += xx xx x xxSujeito xxzMaximizar Resolvendo este problema tem-se: 1 2 3 5 6 7 8-1-2-3-4 -1 -2 1 6 5 4 3 2 0 x1 x2 4 9 7 z = x 1 + 2x 2 x1 ≤ 5 x 1 - x 2 ≤ 2Espaço de soluções não limitado 0,,,,, 623 4 3: )(03: 132121 1321 21 121 132121 ≥ =+−+ =+ =+− +++++= Rsssxx Rsxx sx sxxSujeito MRsssxxzMaximizar 623 4 3 1321 21 121 =+−+ =+ =+− Rsxx sx sxx = = = = === ⇒=−= 0 6 4 3 0 336 1 2 1 321 z R s s sxx D 03 121 =−−−= MRxxz 1x 2x 1s 2s 3s 1R 1s 1 –1 1 0 0 0 3 2s 1 0 0 1 0 0 4 1R 3 2 0 0 –1 1 6 z –3–3M –1–2M 0 0 M 0 –6M 1x 2x 1s 2s 3s 1R 1s 0 3 5− 1 0 3 1 3 1− 1 2s 0 3 2− 0 1 3 1 3 1− 2 1x 1 3 2 0 0 3 1− 3 1 2 z 0 1 0 0 –1 1+M 6 1x 2x 1s 2s 3s 3s 0 –5 3 0 1 3 2s 0 1 –1 1 0 1 1x 1 –1 1 0 0 3 z 0 –4 3 0 0 9 1x 2x 1s 2s 3s 3s 0 0 –2 5 1 8 2x 0 1 –1 1 0 1 1x 1 0 0 1 0 4 z 0 0 –1 4 0 13 Este último quadro mostra que a solução optimizada ainda não foi alcançada, pois a variável s1 pode entrar na solução básica. Entretanto, verifica-se que todos os coeficientes das restrições relativas a s2 não positivos, isto é, são negativos e nulos, indicando que existe pelo menos uma variável que pode ser aumentada indefinidamente. Deste modo conclui-se que o problema tem solução não limitada. Em regra geral, para se identificar a existência de uma situação de não limitação, verifica-se se em qualquer iteração os coeficientes de uma das variáveis não básicas das restrições são não positivos. Se isso suceder, tem-se um espaço de soluções não básicas. Se, além disso, o coeficiente da tal variável na função objectivo for negativo, no caso de maximização, e positivo, no caso de maximização, então o valor da função objectivo é também não limitado. 3.2.4.4. Soluções inexistentes ou inviáveis Se todas as restrições não poderem ser satisfeitas simultaneamente, diz-se que o modelo não tem uma solução viável. Esta situação nunca pode acontecer se todas as restrições forem do tipo menor ou igual (≤) assumindo constantes não negativas no segundo membro, uma vez que as variáveis de folga fornecem sempre uma solução admissível. No entanto, quando se empregam os outros tipos de restrições, torna-se imperioso que se usem as variáveis fictícias que, por definição, não garantem uma solução viável para o modelo original. Embora se usem medidas para forçar as variáveis fictícias a tomar o valor zero na solução óptima, através da utilização das penalizações, este situação só pode ocorrer se o modelo tiver um espaço viável de soluções. Se não tiver, pelo menos uma variável fictícia será positiva na iteração óptima. Isto indica que o problema não tem solução ou tem solução inviável. Sob o ponto de vista prático, um espaço de soluções não admissível indica a possibilidade de o modelo não estar correctamente formulado, uma vez que as restrições não são mutuamente compatíveis. Exemplo 1 – Considere seguinte problema: 0, 1243 22: 23: 21 21 21 21 ≥ ≥+ ≤+ += xx xx xxSujeito xxzMaximizar Resolvendo este problema tem-se: 0,,,, 1243 22: )(023: 12121 1221 121 12121 ≥ =+++ =++ ++++= Rssxx Rsxx sxxSujeito MRssxxzMaximizar 1243 22 1221 121 =+++ =++ Rsxx sxx = = = === ⇒=−= 0 12 2 0 325 1 1 221 z R s sxx D 023 121 =−−− MRxxz 1x 2x 1s 2s 1R 1s 2 1 1 0 0 2 1R 3 4 0 –1 1 12 z –3–3M –2–4M 0 0 M –12M 1x 2x 1s 2s 1R 2x 2 1 1 0 0 2 1R –5 0 –4 –1 1 4 z 1+5M 0 2+4M M 0 4–4M Esta primeira iteração do Método de Simplex mostra que a variável fictícia R1 é positiva (R1=4) na solução óptima. Isto indica que o espaço das soluções é inviável, isto é, o problema não tem soluções. E a solução obtida é chamada Solução Peseudo-óptima. E a figura abaixo, mostra o espaço de soluções deste problema. 1 2 3 5 6 7 8-1-2-3-4 -1 -2 1 6 5 4 3 2 0 x1 x2 4 9 7 3x 1 +4x 2 ≥12 2x 1 +x 2 ≤2 • Solução pseudo-óptima Figura 3.10. – Espaço de soluções inviáveis Referências seleccionadas Hartley, R. (1985), “Linear and Non-linear Programming”. An Introduction to Linear Methods in Mathematical Programming. Ellis Horwood Limited, West Sussex. Taha, H. (1997), “Operations Reseach”. An Introduction. 6th Edition. Prentice-Hall, Inc. Upper Saddle River. Andrade, Eduardo L. (2000). Introdução à Pesquisa Operacional”, 2ª Edição. Livro Técnicos e Científicos Editora, Rio de Janeiro. Exercícios 1. Resolver por Método de M Grande os seguintes problemas de Programação Linear. 0, 82 1 622: 3:) 21 21 21 21 21 ≥ ≤+ ≤+− ≥+ +−= xx xx xx xxaSujeito xxzMaximizara 0, 6 1232 1: 23:) 21 2 21 21 21 ≥ ≤ ≥+ ≤− +−= xx x xx xxaSujeito xxzMinimizarb 0, 1523 234 3: 6:) 21 21 21 21 21 ≥ ≥+ ≤+ =− += xx xx xx xxaSujeitoxxzMaximizarc 0, 8 1 1232: 64:) 21 2 21 21 21 ≥ ≤ ≤− ≥+ +−= xx x xx xxaSujeito xxzMinimizard 0, 52 1043 2674: 53:) 21 21 21 21 21 ≥ =+ ≥− ≤+ += xx xx xx xxaSujeito xxzMaximizare 0, 232 10 723: 3:) 21 21 21 21 21 ≥ =+− ≤+ ≥− += xx xx xx xxaSujeito xxzMinimizarf 0, 52 1043 2674: 53:) 21 21 21 21 21 ≥ =+ ≥− ≤+ += xx xx xx xxaSujeito xxzMinimizarg 0, 52 1243 2474: 53:) 21 21 21 21 21 ≥ ≥+ ≤− ≤+ += xx xx xx xxaSujeito xxzMaximizarh 0, 1523 234 3: 122:) 21 21 21 21 21 ≥ ≥+ ≤+ =− +−= xx xx xx xxaSujeito xxzMinimizari 0, 962 3575 62: 32:) 21 21 21 21 21 ≥ ≥+ ≤+ ≤+− += xx xx xx xxaSujeito xxzMaximizarj 0, 2 1243 82: 32:) 21 21 21 21 21 ≥ ≤− ≥+ ≤+ +−= xx xx xx xxaSujeito xxzMinimizark 0, 1532 2324 3: 6:) 21 21 21 21 21 ≥ ≥+ ≤+ =+− −= xx xx xx xxaSujeito xxzMaximizarl 0, 3 52 4: 32:) 21 21 21 21 21 ≥ ≤+ ≥+ ≤+− += xx xx xx xxaSujeito xxzMaximizarm 0, 2133 155 2052: 510:) 21 21 21 21 21 ≥ ≥+ ≥+ ≥+ += xx xx xx xxaSujeito xxzMaximizarn 2. Resolver por Método de M Grande os seguintes problemas de Programação Linear. 0,, 22 524 13253: 3:) 321 32 321 321 321 ≥ =+− ≥+− ≤−+ +−= xxx xx xxx xxxaSujeito xxxzMinimizara 0,, 12 324 112: 3:) 321 31 321 321 321 ≥ =+− ≥++− ≤+− ++−= xxx xx xxx xxxaSujeito xxxzMinimizarb 0,, 3463 1332 9: 2:) 321 321 321 321 321 ≥ =−+− =+− ≤++ ++−= xxx xxx xxx xxxaSujeito xxxzMinimizarc 0,, 423 62 2132: 2:) 321 321 21 321 321 ≥ ≥+− =− ≤++ +−= xxx xxx xx xxxaSujeito xxxzMaximizard 0,, 522 10443 25774: 653:) 321 321 321 321 321 ≥ ≥−+ ≥+− ≤−+ −+= xxx xxx xxx xxxaSujeito xxxzMaximizare 0,,, 8232 2 62: 2:) 4321 432 31 4321 4321 ≥ ≤+− ≤+− ≥+−− +++= xxxx xxx xx xxxxaSujeito xxxxzMinimizarf 0,, 232 102 523: 23:) 321 321 321 321 321 ≥ ≥−+− ≥++ ≥+− ++= xxx xxx xxx xxxaSujeito xxxzMinimizarg 0,,, 823 632 22: 2:) 4321 4321 4321 4321 4321 ≥ ≤+++− =+−+ =−+− ++−−= xxxx xxxx xxxx xxxxaSujeito xxxxzMinimizarh 0,, 2448 8426 2132: 242:) 321 31 321 321 321 ≥ =+− ≥++− ≤++ ++−= xxx xx xxx xxxaSujeito xxxzMaxiimizari 0,, 725 23 15425: 3:) 321 321 32 321 321 ≥ =++ ≤− ≥++ −+= xxx xxx xx xxxaSujeito xxxzMinimizarj 0,, 823 62 2132: 462:) 321 321 21 321 321 ≥ ≥+− =− ≤++ +−= xxx xxx xx xxxaSujeito xxxzMaximizark 3. Resolver por Método de M Grande os seguintes problemas de Programação Linear. livrexxx xxx xx xxxaSujeito xxxzMaximizara 231 321 21 321 321 ;0, 423 62 932: 2:) ≥ ≥+− =− ≤++ +−= 0;0, 725 426 15425: 3:) 321 321 32 321 321 ≤≥ =−+ ≤+ ≥−+ ++= xxx xxx xx xxxaSujeito xxxzMinimizarb 0,; 423 62 2132: 2:) 321 321 21 321 321 ≥ ≥+− =− ≤++ +−= xxlivrex xxx xx xxxaSujeito xxxzMaximizarc 0,; 1024 732 846: 242:) 321 21 321 321 321 ≥ =+− ≤++ ≥++− −−= xxlivrex xx xxx xxxaSujeito xxxzMinimizard 0;0, 322 323 1: 752:) 231 321 321 321 321 ≤≥ ≥+− ≥+− ≤++ +−= xxx xxx xxx xxxaSujeito xxxzMaximizare 0,, 42 42 6: 2:) 321 321 21 321 321 ≥ ≤−+− ≤+ ≤++ +−= xxx xxx xx xxxaSujeito xxxzMaximizarf 0, 2 1243 82: 33:) 21 21 21 21 21 ≥ ≤− ≥+ ≤+ +−= xx xx xx xxaSujeito xxzMinimizarg 0, 5 2446 1: 2:) 21 2 21 21 21 ≥ ≤ ≥+ ≤+− += xx x xx xxaSujeito xxzMaximizarh 0, 152 13 54: :) 21 21 21 21 21 ≥ ≥− ≤− ≥− +−= xx xx xx xxaSujeito xxzMaximizari 0, 2325 2953 1523: 726:) 21 21 21 21 21 ≥ ≥+ ≥+ ≥+ += xx xx xx xxaSujeito xxzMaximizarj 0, 4 22 33: 62:) 21 1 21 21 21 ≥ ≤ ≥− ≥+ += xx x xx xxaSujeito xxzMinimizark 0, 22 22 42: 42:) 21 21 21 21 21 ≥ ≥+ ≤+− ≤− +−= xx xx xx xxaSujeito xxzMaximizarl 0, 2 662 2438: 52:) 21 21 21 21 21 ≥ ≤+− ≥+− ≥+ += xx xx xx xxaSujeito xxzMaximizarm 0, 152 13 54: :) 21 21 21 21 21 ≥ ≥− ≤− ≥− +−= xx xx xx xxaSujeito xxzMaximizarn 0, 1243 22: 23:) 21 21 21 21 ≥ ≥+ ≤+ += xx xx xxaSujeito xxzMaximizaro 0, 6034 10024 12043: 1020:) 21 21 21 21 21 ≥ ≤− ≥+ ≤+ += xx xx xx xxaSujeito xxzMaximizarp 0, 2 662 2438: 52:) 21 21 21 21 21 ≥ ≤+− ≥+− ≥+ += xx xx xx xxaSujeito xxzMaximizarm 4. Uma pequena fábrica do ramo alimentar é constituída por três secções e pode produzir três produtos enlatados P1, P2, P3 cujos lúcros líguidos por unidade produzida são de 3, 2 e 4 u.m., respectivamente. As secções I, II e III, têm capacidades de processamento limitadas em 480, 580 e 720 horas, por mês, respectivamente. E as horas necessárias para o processamento de uma caixa do produto P1, P2 ou P3, são dadas na tabela abaixo. SECÇÕES PRODUTOS P1 P2 P3 I 2 0 4 II 2 2 2 III 2 4 2 Sabendo que os produtos os três produtos são vendidos em caixas de 12 latas estabeleça o óptimo programa de produção mensal para a fábrica. 5. Uma pequema empresa de distribuição de produtos alimentares dispõe de 1,2 toneladas de arroz no primeiro dos seus dois armazéns e de mais uma tonelada no segundo armazém. E a empresa recebeu pedido provenientes de dois dos seus principais clientes nas quantidades de 18 e 14 sacos, de 50 quilos cada, respectivamente para os clientes 1 e 2. Sabe-se que a empresa oferece transporte gratuído à todos os clientes que compram dez, ou mais, sacos. E para este caso, os custos unitários de transporte estimados, por saco de arroz, são os seguinte: • do Armazém I para a loja do Cliente 1, 14 contos; • do Armazém I para a loja do Cliente 2, 11 contos; • do Armazém II para a loja do Cliente 1, 14 contos; e • do Armazém II para a loja do Cliente 2, 13 contos; Considere que o arroz existente em ambos os armazéns da empresa está em soacos de 50 quilos e determine o óptimo plano de distribuição do arroz para os dois clientes. 6. Uma pequena fábrica produz 3 produtos, A, B e C, que são vendidos a 160, 300 e 500 unidades monetárias (UM), respectivamente. E devida a procura, as exigências de produção semanal são pelo menos 25 unidades de A, 15 de B e 10 de C. Cada tipo de produto requer um certo tempo para fabricação das partes componentes, para a montagem e para a embalagem. Especificamente, uma unidades de A requer 3 homem-horas para a fabricação, 4 homem-horas para a montagem e 1 homem-hora para a embalagem. Os números correspondentes para uma unidade de B são 3, 5 e 5 homem-horas, e para uma unidade de C são 5, 6 e 3 homem-horas. E a fábrica trabalha num único turno de 8 horas, por dia, durante 5dias por semana. Sabendo que a fábrica emprega 8 operários na Secção de Fabricação, 8 na Secção de Montagem e 4 na Secção de Embalagem, determine a óptima misturs de produção semanal para a fábrica. 3.2.3. Método de M Grande 3.2.3.2. Problemas Resolvidos 3.2.4. Casos especiais no Método de Simplex 3.2.4.1. Soluções degeneradas. 3.2.4.2. Soluções alternativas. 3.2.4.3. Soluções não limitadas 3.2.4.4. Soluções inexistentes ou inviáveis
Compartilhar