Docsity
Docsity

Prepare-se para as provas
Prepare-se para as provas

Estude fácil! Tem muito documento disponível na Docsity


Ganhe pontos para baixar
Ganhe pontos para baixar

Ganhe pontos ajudando outros esrudantes ou compre um plano Premium


Guias e Dicas
Guias e Dicas

Pesquisa Operacional I - Método Simplex, Notas de estudo de Economia Agroindustrial

Engenharia Produção Elétrica - EPE

Tipologia: Notas de estudo

2012

Compartilhado em 23/10/2012

carlos-cruz-38
carlos-cruz-38 🇧🇷

4.3

(3)

11 documentos

Pré-visualização parcial do texto

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
Docsity logo



Copyright © 2024 Ladybird Srl - Via Leonardo da Vinci 16, 10126, Torino, Italy - VAT 10816460017 - All rights reserved