Simplex_duas_fases (3)

Prévia do material em texto

<p>VARIAÇÕES DO MÉTODO SIMPLEX</p><p> Modelos estudados até o momento se utilizaram de restrições do tipo <=</p><p>com os termos da direita positivos</p><p> Novo Problema :</p><p> 1) Restrição do tipo >=</p><p> Neste caso a variável de folga é subtraída e seu valor é negativo.</p><p> 2) Restrição do tipo =</p><p> Neste caso não introduziremos a variável de folga.</p><p> 3) Para as situações 1 e 2 acrescentaremos variáveis auxiliares ai ,</p><p>formando um novo modelo</p><p>MÉTODO SIMPLEX</p><p> Inicialmente, variáveis artificiais são introduzidas ao modelo, como</p><p>no método anterior.</p><p> Como o nome sugere, há duas fases ou etapas:</p><p> Fase I: consiste em resolver um problema de minimização cuja</p><p>função objetivo é dada pelo somatório das variáveis artificiais.</p><p> Espera-se que o mínimo seja zero (requisito para Fase II).</p><p>MÉTODO DAS DUAS FASES OU FUNÇÃO OBJETIVO</p><p>AUXILIAR</p><p>Caso o valor mínimo da soma seja diferente de zero, o problema</p><p>não tem nenhuma solução viável, o que encerra o processo –</p><p>variável artificial positiva indica que restrição original não foi</p><p>satisfeita.</p><p> Fase II: Usa-se a solução da Fase I como solução básica viável inicial</p><p>para o problema original.</p><p>EXEMPLIFICAÇÃO</p><p>EXEMPLIFICAÇÃO</p><p>Deveremos nesta modelagem eliminar as variáveis auxiliares</p><p>( a2 e a3 )</p><p>Retornar ao modelo original que apresenta solução básica,</p><p>composto pelas variáveis originais.</p><p> Pode ser utilizado o Método do Big M (ou M Grande) ou</p><p>Método da função objetivo Auxiliar</p><p>RETORNO AO MODELO ORIGINAL</p><p>• É construída uma função objetivo auxiliar formada pela soma das</p><p>variáveis auxiliares</p><p>• Quando as variáveis auxiliares e a função auxiliar forem zeradas,</p><p>podemos abandoná-las. O novo objetivo será dado pela função</p><p>objetivo original</p><p>• O modelo original passa a ter a solução básica inicial que não possuía</p><p>antes</p><p>MÉTODO DA FUNÇÃO OBJETIVO</p><p>AUXILIAR</p><p>MÉTODO DA FUNÇÃO OBJETIVO AUXILIAR</p><p>MÉTODO DA FUNÇÃO OBJETIVO AUXILIAR</p><p>EXEMPLO 1 – O QUADRO FICA:</p><p>EXEMPLO 1 – RESOLVENDO:</p><p>Quadro inicial</p><p>1ª. iteração</p><p>Variáveis artificiais e função artificial agora são não básicas</p><p>Podemos abandonar elas do modelo e prosseguir com resolução</p><p>2ª. iteração</p><p>EXEMPLO 1 – RESOLVENDO:</p><p>2ª. iteração</p><p>EXEMPLO 1 – RESOLVENDO:</p><p>VARIAÇÃO DAS APLICAÇÕES DOMÉTODO</p><p>SIMPLEX</p><p>• Lado direito negativo</p><p>➢ Multiplicar a restrição por -1</p><p>• Restrições do tipo ≥</p><p>➢ Inserir variável de excesso subtraindo: -1.xE1</p><p>➢ Inserir variável artificial somando: +1.A1</p><p>• Restrições do tipo =</p><p>➢ Inserir variável artificial somando: +1.A1</p><p>• Problemas de Minimização</p><p>➢ Multiplicar função objetivo por –1</p><p>➢ Tratá-la como maximização</p><p>SIMPLEX DUAS FASES (FUNÇÃO</p><p>OBJETIVO AUXILIAR)</p><p>TREINO = colocar o PPL abaixo na forma padrão do</p><p>Simplex duas fases</p><p>• Max Z = 4x1 + 3x2</p><p>• Sujeito a</p><p>• 2x1 + 1x2 = 15</p><p>• x1 ≥ 4</p><p>• x1 ; x2 ≥ 0</p><p>SIMPLEX DUAS FASES (FUNÇÃO</p><p>OBJETIVO AUXILIAR)</p><p>TREINO = colocar o PPL abaixo na forma padrão do</p><p>Simplex duas fases</p><p>• Max Z = 4x1 + 3x2 + 6x3</p><p>• Sujeito a</p><p>• 3x1 + 1x2 ≤ 10</p><p>• 2x1 – x2 ≥ 4</p><p>• x1 + x2 = -5</p><p>• x1 ; x2 ≥ 0</p><p>17</p><p>Método Simplex – Duas Fases</p><p>O Método Simplex utiliza uma solução inicial viável para</p><p>começar o processo iterativo, trabalhando sempre</p><p>dentro da região viável.</p><p>Nos casos apresentados de maximização até o presente</p><p>momento, a solução para xi = 0, para i = 1, ..., n era</p><p>uma solução viável, já que todas as restrições</p><p>apresentadas foram do tipo (≤).</p><p>Quando as restrições são do tipo (=) ou (≥), esta solução não existe.</p><p>Seja o exemplo abaixo:</p><p>Maximizar L = x1 + 2x2</p><p>Restrições:</p><p>3x1 + 4x2 ≥ 24</p><p>5x1 + 2x2 = 20</p><p>x1 ≥ 0</p><p>x2 ≥ 0</p><p>Como temos uma restrição do tipo () e (=), a variável de</p><p>folga deve ter coeficiente negativo, tendo o significado de</p><p>uma variável de excesso. E incluir as variáveis</p><p>auxiliares.</p><p>O problema transformado é:</p><p>Maximizar L = x1 + 2x2</p><p>3x1 + 4x2 – F1 + A1 = 24</p><p>5x1 + 2x2 + A2 = 20</p><p>x1, x2, f1, a1, a2  0</p><p>onde f1 é uma variável de excesso e A1 e A2 são variáveis auxiliares.</p><p>Percebe-se que o problema com as restrições acima não é o mesmo</p><p>problema, a não ser que todas as variáveis ai sejam iguais a zero.</p><p>Desta forma, podemos resolver o problema em duas fases:</p><p>Na primeira fase, substituímos a função objetivo original</p><p>por uma função objetivo auxiliar da seguinte forma:</p><p>Assim, isolamos as variáveis auxiliares das duas restrições</p><p>para depois soma-las:</p><p>3 x1 + 4 x2 - f1 + A1 = 24</p><p>5 x1 + 2 x2 + A2 = 20</p><p>A1 = -3 x1 - 4 x2 + f1 + 24</p><p>A2 = - 5 x1 - 2 x2 + 20</p><p>_____________________________________________________________________</p><p>W = -8 x1 -6 x2 + f1 + 44</p><p>Minimizar W é = Max (-W)</p><p>Min W = -8 x1 - 6 x2 + f1 + 44 (-1)</p><p>Max -W = 8 x1 + 6 x2 - f1 - 44</p><p>Max - W - 8 x1 - 6 x2 + f1 = - 44 (Nova função Objetivo)</p><p>Como o problema é de minimização e vamos maximizar, é</p><p>necessário multiplicar a função objetivo auxiliar por (-1).</p><p>Nesse momento, aplicamos o método Simplex de forma a</p><p>maximizar a função objetivo auxiliar, com as restrições</p><p>contendo as variáveis auxiliares. A função objetivo auxiliar</p><p>será maximizada quando todas as variáveis ai forem iguais</p><p>a zero, já que não podem conter valores negativos.</p><p>A primeira fase do problema então consiste na</p><p>maximização da função objetivo auxiliar, que fornecerá</p><p>uma solução viável para o problema original.</p><p>A segunda fase consiste em resolver o problema original</p><p>tomando como solução inicial os valores obtidos pela</p><p>primeira fase para as variáveis xi e fi.</p><p>Para resolver o problema, monta-se o quadro de forma</p><p>semelhante à sistemática anterior, colocando-se a função</p><p>objetivo artificial na última linha.</p><p>Base x1 x2 f1 A1 A2 b</p><p>A1 3 4 -1 1 0 24</p><p>A2 5 2 0 0 1 20</p><p>-z -1 -2 0 0 0 0</p><p>-W -8 -6 1 0 0 -44</p><p>Aplica-se Simplex usando como função objetivo a última linha.</p><p>Quando a solução ótima for atingida, dois casos podem ocorrer:</p><p>-W = 0: neste caso foi obtida uma solução básica do problema</p><p>original e o processo de solução deve continuar, desprezando-se</p><p>as variáveis artificiais e os elementos da última linha. É o início</p><p>da segunda fase do processo.</p><p>W  0: neste caso o problema original não tem solução viável,</p><p>o que significa que as restrições devem ser inconsistentes.</p><p>Fase 1 - Primeira iteração</p><p>Variável a entrar na base: x1 (coluna com maior valor negativo na última</p><p>linha)</p><p>Variável a sair da base: A2 (o quociente 20/4 é o menor quociente entre a</p><p>última coluna e a coluna da variável x1, que vai entrar na base)</p><p>Pivô = 5</p><p>Montagem da matriz identidade</p><p>Base x1 x2 f1 A1 A2 b</p><p>A1 3 4 -1 1 0 24</p><p>A2 5 2 0 0 1 20</p><p>-z -1 -2 0 0 0 0</p><p>-W -8 -6 1 0 0 -44</p><p>LP = LP ÷ 5</p><p>L3 = 8 x LP + L3</p><p>L1 = – 3 x LP + L1</p><p>L2 = 1 x LP + L2</p><p>Matriz de cálculo</p><p>anterior</p><p>Base x1 x2 f1 A1 A2 b</p><p>x1 1 0,4 0 0 0,2 4</p><p>A1 0 2,8 -1 1 -0,6 12</p><p>-z 0 -1,6 0 0 0,2 4</p><p>-W 0 -2,8 1 0 1,6 -12</p><p>Base x1 x2 f1 A1 A2 b</p><p>A1 3 4 -1 1 0 24</p><p>A2 5 2 0 0 1 20</p><p>-z -1 -2 0 0 0 0</p><p>-W -8 -6 1 0 0 -44</p><p>Fase 1 – Segunda iteração</p><p>Variável a entrar na base: x2 (coluna com maior valor negativo na última</p><p>linha)</p><p>Variável a sair da base: A1 (o quociente 12/2,8) é o menor quociente</p><p>entre a última coluna e a coluna da variável x2, que vai entrar na base)</p><p>Pivô = 2,8</p><p>Montagem da matriz identidade</p><p>Base x1 x2 f1 A1 A2 b</p><p>x1 1 0,4 0 0 0,2 4</p><p>A1 0 2,8 -1 1 -0,6 12</p><p>-z 0 -1,6 0 0 0,2 4</p><p>-W 0 -2,8 1 0 1,6 -12</p><p>LP = LP ÷ 2,8</p><p>L3 = 2,8 x LP + L3</p><p>L1 = – 0,4 x LP + L1</p><p>L2 = 1,6 x LP + L2</p><p>Matriz de cálculo</p><p>anterior</p><p>Base x1 x2 f1 A1 A2 b</p><p>x1 0 1 -0,35 0,35 -0,21 4,28</p><p>X2 1 0 0,14 -0,14 0,28 2,28</p><p>-z 0 0 -0,56 0,56 -0,13 10,8</p><p>-W 0 0 0 1 1 0</p><p>Como na última linha o valor da função objetivo artificial é zero, a primeira fase terminou</p><p>e a solução encontrada é a solução básica inicial para a segunda fase.</p><p>Base x1 x2 f1 A1 A2 b</p><p>x1 1 0,4 0 0 0,2 4</p><p>A1 0 2,8 -1 1 -0,6 12</p><p>-z 0 -1,6 0 0 0,2 4</p><p>-W 0 -2,8 1 0 1,6 -12</p><p>Removendo a última linha e as colunas referentes às</p><p>variáveis artificiais, o quadro se torna:</p><p>Matriz para</p><p>2ª fase</p><p>Base x1 x2 f1 b</p><p>x1 0 1 -0,35 4,28</p><p>X2 1 0 0,14 2,28</p><p>-z 0 0 -0,56 10,8</p><p>x1 = 0</p><p>x2 = 10</p><p>z = 20</p><p>Realizada as novas iterações, teremos</p><p>como resultado da função objetivo inicial</p><p>(após</p><p>as alterações)</p><p>SIMPLEX DUAS FASES (FUNÇÃO</p><p>OBJETIVO AUXILIAR)</p><p>TREINO</p><p>• Maximizar z = x1 + x2 + x3</p><p>• Sujeito a:</p><p>• x1 + 2x2 + 3x3 ≤ 9</p><p>• x1 + 6x2 + x3 ≥ 3</p><p>• 4x1 + x2 + x3 = 5</p><p>SIMPLEX DUAS FASES (FUNÇÃO</p><p>OBJETIVO AUXILIAR)</p><p>TREINO</p><p>• Minimizar z = 4X1 + 3X2 + 9X3</p><p>• Sujeito a:</p><p>• 2X1 + 4X2 + 6X3 ≤ 15</p><p>• 1X1 + 1X2 + 1X3 = 4,5</p><p>• 6X1 + 1X2 + 6X3 ≥ 12</p><p>SIMPLEX DUAS FASES (FUNÇÃO</p><p>OBJETIVO AUXILIAR)</p><p>TREINO</p><p>• Minimizar z = 3x1 + 2x2 + x3</p><p>• Sujeito a:</p><p>• 3x1 + x2 + 3x3 ≥ 6</p><p>• 3x1 + 2x2 = 6</p><p>• x1 – x2 ≤ 1</p>