Baixe Pesquisa Operacional I - Método Simplex e outras Notas de estudo em PDF para Economia Agroindustrial, somente na Docsity! Graduando: Carlos Alberto F. Cruz Engenharia de Produção Elétrica-CESF Aula II 1 Solução para os Modelos de Problemas de Programação Linear Método Gráfico e Método Simplex Método Gráfico 5 Programação Linear Para construir a reta correspondente a equação x1 + 2x2 = 10 precisa- se de dois pontos: fazendo x1 = 0, teremos: 2x2 = 10 x2 = 5 e fazendo x2 = 0, teremos: x1 = 10 0 2 4 6 8 10 12 0 2 4 6 8 10 12 X1 X2 6 Programação Linear Testar a inequação: x1 + 2x2 10 Vamos tomar um ponto qualquer fora da reta, por exemplo o ponto (x1 = 10 e x2 = 5) e testemos na inequação. Substituindo os valores de x1 e x2 na inequação: 10 + 2 * 5 10 ou 20 10, o que é verdadeiro, portanto a região das soluções da inequação é aquela que contém o ponto testado. 7 Programação Linear Exemplo 2: Representar graficamente a solução do modelo: Max L = 2x1 + 5x2 s.a. : x1 + 3x2 12 2x1 + x2 16 x1 0 x2 0 Solução Vamos representar primeiramente cada uma das restrições: 10 Programação Linear Vamos testar para cada reta, qual o semiplano que corresponde à solução das inequações. Para isso vamos escolher um ponto qualquer fora das retas. Por exemplo o ponto (8,16). x1 + 3x2 12; substituindo x1 = 8 e x2 = 16, obtém-se: 8 + 3 * 16 12 ou 56 12; a desigualdade é falsa. Portanto a região das soluções da inequação está do lado oposto ao ponto testado. 2x1 + x2 16; substituindo x1 = 8 e x2 = 16, obtém-se: 2 *8 + 16 16 ou 32 16; a desigualdade é verdadeira. Portanto a região das soluções da inequação está do lado do ponto testado. A combinação dos dois semiplanos resulta na região comum as duas retas, formada pelo triângulo ABC. Observe no gráfico a seguir. 11 Programação Linear Valores Atribuídos a X1 e X2 0 2 4 6 8 10 12 14 16 18 0 2 4 6 8 10 12 14 X1 X2 C B A 12 Programação Linear Os pontos A, B e C são chamados pontos extremos da região permissível, que nesse caso é finita e delimita pelas arestas do triângulo ABC. Não é difícil determinar as coordenadas desses pontos extremos. Os pontos A e B, por sua localização especial, têm coordenadas imediatas: A(x1= 8; x2= 0), B(x1=12; x2=0) O ponto C é a intersecção das duas retas limites das restrições, ou seja, é a intersecção de: x1 + 3x2 = 12 2x1 + x2 = 16 Uma combinação linear adequada entre as duas equações permitirá obter uma das variáveis, cujo o valor poderá ser então substituído em qualquer uma das equações originais para dar o valor da outra variável restante. 15 Programação Linear Exemplo 3: Representar graficamente a solução do modelo: Min Z = 2x1 + 3x2 s.a.: 1x1 + 1x2 5 5x1 + 1x2 10 1x1 8 x1 0 x2 0 16 Programação Linear Exemplo 4: Representar graficamente a solução do modelo: Max L = 2x1 + 3x2 s.a.: 4x1 + 6x2 60 1x1 + 1x2 12 x1 0 x2 0 17 Programação Linear Exemplo 5: Representar graficamente a solução do modelo Max L = 2x1 + 3x s.a.: -1x1 + 2x2 4 1x1 + 2x2 6 1x1 + 3x2 9 x1 0 x2 0 20 Método Simplex UTILIZAÇÃO DE RECURSOS DISPONIBILIDADE Ao introduzirmos o conceito de folga de recurso podemos escrever a relação anterior da seguinte forma: UTILIZAÇÃO + FOLGA = DISPONIBILIDADE Isso implica que: UTILIZAÇÃO DISPONIBILIDADE, então folga 0 UTILIZAÇÃO = DISPONIBILIDADE, então folga = 0 Assim, a folga de cada recurso pode ser representada por uma variável de forma exatamente igual à produção de um produto qualquer. 21 Método Simplex Exemplo: Uma fábrica deseja estabelecer uma programação diária de produção. Atualmente, a fábrica faz apenas dois produtos: mesa e armário, ambos de um só modelo. Para efeito de simplificação, vamos considerar que a fábrica tem limitações em somente dois recursos: madeira e mão-de-obra, cujas disponibilidades diárias são mostradas abaixo. DISPONIBILIDADE RECURSO Madeira 12 m3 Mão-de-obra 8 H.h 22 Método Simplex O processo de produção é tal que, para fazer uma mesa a fábrica gasta 2 m3 de madeira e 2 H.h de mão-de-obra. Para fazer um armário, a fábrica gasta 3 m3 de madeira e 1 H.h de mão-de-obra. Além disso, o fabricante sabe que cada mesa dá uma margem de contribuição para o lucro de R$ 4,00 e cada armário, de R$ 1,00. O problema do fabricante é encontrar o programa de produção que maximize a margem de contribuição total para o lucro. 25 Procedimento do Método Simplex (Problemas de Maximização) Podemos escrever a solução em forma de vetores, então teremos: 8 12 1 0 0 1 43 xx A solução básica inicial seria x1 = 0 , x2 = 0, x3 = 12 e x4 = 8, formada portanto pelas variáveis de folga. 26 Procedimento do Método Simplex (Problemas de Maximização) Vamos montar um quadro para ordenarmos as operações, colocando nele apenas os coeficientes das variáveis. No caso da função objetivo, vamos realizar a seguinte transformação: L = 4x1 + 1x2 para: L - 4x1 - 1x2 = 0 BASE X1 X2 X3 X4 b X3 2 3 1 0 12 X4 2 1 0 1 8 L - 4 - 1 0 0 0 Quadro I 27 Procedimento do Método Simplex (Problemas de Maximização) A última coluna corresponde aos termos independentes das equações, e a última linha contém os coeficientes das variáveis na função objetivo. Na última linha teremos sempre a contribuição que cada variável dá para o lucro total L, por unidade, em cada interação do processo de solução. Como a primeira solução claramente não é a melhor, vamos procurar outra que dê um valor maior para L. Para fazermos isso, vamos nos basear no Quadro I da primeira solução. 30 Procedimento do Método Simplex (Problemas de Maximização) Passo 4: Usar operações válidas com as linhas da matriz e transformar o quadro de cálculos de formar a encontrar a nova solução básica. A coluna da nova variável básica deverá se tornar um vetor identidade, onde o algarismo 1 aparece na linha correspondente à variável que está sendo anulada. Passo 5: Retornar ao passo 2 para iniciar outra iteração. A solução desse exemplo será feita utilizando o Quadro I com as equações completas e usando as operações válidas com as linhas da matriz. 31 Procedimento do Método Simplex (Problemas de Maximização) 1ª Operação: dividir a 2ª linha do Quadro I por 2 Quadro 1A BASE X1 X2 X3 X4 b X3 2 3 1 0 12 X1 1 1/2 0 1/2 4 L - 4 - 1 0 0 0 32 Procedimento do Método Simplex (Problemas de Maximização) 2ª Operação: multiplicar a 2ª linha do Quadro 1A por (- 2) e soma com a 1ª linha do mesmo quadro, colocando o resultado na 1ª linha do Quadro 1B Quadro 1B BASE X1 X2 X3 X4 b X3 0 2 1 -1 4 X1 1 1/2 0 1/2 4 L - 4 - 1 0 0 0