Baixe o app para aproveitar ainda mais
Prévia do material em texto
Programação Linear com o uso do Método Simplex Fabiana Gomes dos Passos Roteiro da aula • Método Simplex – Apresentação e fundamentos do Método Simplex; – Procedimento do Método Simplex para problemas na forma padrão – Maximização; – Exemplo de Aplicação. Apresentação do Método Simplex Resolver um problema de Programação Linear significa basicamente resolver sistemas de equações lineares e calcular o valor da função objetivo; Esse procedimento, apesar de correto, é bastante trabalhoso, podendo ficar impraticável Para resolver um problema real de Programação Linear precisamos de uma sistemática que nos diga: qual o sistema de equações que deve ser resolvido; que o próximo sistema a ser resolvido fornecerá uma solução melhor que os anteriores; Como identificar a solução ótima, uma vez que a tenhamos encontrado Essa sistemática é dada pelo Método Simplex Fundamentos do Método Simplex O método SIMPLEX exige que o problema de otimização apresente todas as restrições em igualdade; Isto não é uma limitação para a aplicação do método, pelo fato que é possível transformar todos os problemas para esta forma; Fundamentos do Método Simplex Caso 1 – Desigualdade do tipo menor ou igual Pode incluir uma variável de folga de tal forma que a nova restrição é: 31 x 03 x 331 xx Fundamentos do Método Simplex Caso 2 – Desigualdade do tipo maior ou igual Pode incluir uma variável de excesso de tal forma que a nova restrição é: 04 x 942 xx 92 x Fundamentos do Método Simplex • Restrição ≤ ⇒ Variável de Folga – Representa, economicamente, à quantidade de recurso não consumido; • Restrição ≥ ⇒ Variável de Excesso - Corresponde, economicamente, à quantidade de recurso consumido além do mínimo requerido; Fundamentos do Método Simplex Caso 3 – Lado direito negativo ( b < 0) Multiplica-se a expressão por (-)1. Procedimento do Método Simplex (problemas na forma padrão - Maximização) Introduzir as variáveis de folga, uma para cada desigualdade Montar um quadro para os cálculos, colocando os coeficientes de todas as variáveis com os respectivos sinais e, na última linha, incluir os coeficientes da função-objetivo transformada. Estabelecer uma solução básica inicial, usualmente atribuindo zero às variáveis originais e achando valores positivos para as variáveis de folga. Como próxima variável a entrar na base, escolher a variável não- básica que fornece, na última linha, a maior contribuição para o aumento da função objetivo (ou seja, tem o maior valor negativo). Se todas as variáveis que estão fora da base tiverem coeficientes nulos ou positivos nessa linha, a solução atual é ótima. Se alguma dessas variáveis tiver valor nulo, temos outra solução ótima, com o mesmo valor da função-objetivo. Passo 1: Passo 2: Passo 3: Passo 4: Procedimentos do Método Simplex (problemas na forma padrão - Maximização) Para escolher a variável que deve deixar a base, deve-se realizar o seguinte procedimento: a) Dividir os elementos da última coluna pelos correspondentes elementos positivos da coluna da variável que vai entrar na base. Se não houver elemento nenhum positivo nessa coluna, o processo deve parar, já que a solução é ilimitada. b)O menor coeficiente indica a equação cuja respectiva variável básica deverá ser anulada, tornando-se variável não-básica. Usando operações com as linhas da matriz, transformar a coluna da nova variável básica num vetor identidade, onde o elemento 1 aparece na linha correspondente à variável que está sendo anulada. Retornar ao PASSO 4 para iniciar nova iteração. Passo 5: Passo 6: Passo 7: Exemplo o A Companhia MAXIMÓVEIS fabrica 2 tipos de produtos: o Cadeiras e Mesas o Margem de Contribuição Unitária: o Cadeira = $ 8,00 o Mesa = $ 6,00 o As cadeiras e mesas são processadas em 2 departamentos: o Montagem o Acabamento Através dos dados contidos na tabela , formule um modelo de programação linear para determinar a produção diária de cada um dos modelos de modo a maximizar o lucro total da companhia. Exemplo o Cada unidade dos produtos consome as seguintes horas na fabricação: Departamento Montagem Acabamento Cadeiras 4 2 Mesas 2 4 Horas totais disponíveis 60 48 Horas por unidade • Variáveis X1 = Quantidade de cadeiras; X2 = Quantidade de mesas; Z = lucro total da companhia. • Restrições a) Limitação de montagem ; b) Limitação de acabamento; c) quantidades não negativas. • Objetivo Maximizar o lucro total da companhia 0, 4842 6024:. 68 21 21 21 21 xx xx xxas xxZMax 1. Qual o mix de produção entre mesas e cadeiras que maximiza o lucro da firma? 2. Qual será o lucro máximo da companhia? Problema Solução Gráfica 4 – Encontrar a solução pela comparação dos pontos extremos Através de todos os pontos extremos da área de soluções viáveis e escolhemos aquele com maior MCT CADEIRA MESA (0,12) Solução ótima (15,0) (0,0) (12,6) MCT = 8x1 + 6x2 (0,0) MCT = 0 (0,12) MCT = 72 (15,0) MCT = 120 (12,6) MCT = 132 Desenvolvimento do Método Simplex Passo1: Introduzir as variáveis de folga Max MCT = 8x1 + 6x2 + 0x3 + 0x4 Sujeito a: 4x1 + 2x2 + 1x3 = 60 2x1 + 4x2 + + 1x4 = 48 x1, x2, x3 e x4 0 Transformar a função-objetivo: de L = 8x1 + 6x2 para L - 8x1 - 6x2 = 0 Desenvolvimento do Método Simplex Passo 2: Montar o quadro Quadro 1: Fazendo as variáveis originais iguais a zero x1 x2 x3 x4 b 4 2 1 0 60 2 4 0 1 48 -8 -6 0 0 0 a) Solução Inicial: Fazendo as variáveis originais do modelo iguais a zero e achando o valor das demais x1= x2 = 0 (variáveis não-básicas) x3 = 60; x4= 48 e L= 0 x3 x4 Variáveis básicas Base Função-objetivo transformada L Desenvolvimento do Método Simplex b) Segunda Solução: O problema é descobrir: Das 2 variáveis não-básicas (nulas) na primeira solução, qual deverá se tornar positiva? Das 2 variáveis básicas (positivas) na primeira solução, qual deverá ser anulada? Qual deverá se tornar positiva? Produzir primeiro o produto que mais contribui para o lucro, como indicado na última linha (maior valor negativo “absoluto”) x1= 8 e x2 = 6 18 Desenvolvimento do Método Simplex Qual variável deverá ser anulada? Se formos produzir apenas o produto que mais contribui para o lucro (x1), qual a quantidade máxima possível? 1ª restrição: 4x1 + 0x2 = 60 Max x1 = 15 2ª restrição: 2x1 + 0x2 = 48 Max x1 = 24 Essa análise pode ser feita diretamente do Quadro 1, dividindo-se os elementos da coluna b pelos correspondentes elementos da coluna x1 O menor quociente indica, pela linha em que ocorreu, qual variável básica deve ser anulada. x1 x2 x3 x4 b 4 2 1 0 60 2 4 0 1 48 -8-6 0 0 0 x3 x4 Base L 1ª linha: 60 / 4 = 15 2ª linha: 48 / 2 = 24 Variável a ser anulada: x3 x2 = 0 X3 = 0 x1 = ? X4= ? Desenvolvimento do Método Simplex Solução: fazendo operações com linhas, a partir do quadro 1, transformar a coluna da nova variável (x1) num vetor identidade, com o elemento 1 na linha correspondente à variável a ser anulada 1ª Operação: Dividir a 1ª linha por 4 Quadro 1A: Base x1 x4 L x1 x2 x3 x4 b 1 1/2 1/4 0 15 2 4 0 1 48 -8 -6 0 0 0 x1 x2 x3 x4 b 4 2 1 0 60 2 4 0 1 48 -8 -6 0 0 0 x3 x4 Base L Quadro 1: Desenvolvimento do Método Simplex 2ª Operação: Multiplicar a 1ª linha por –2 e somar à 2ª linha Quadro 1B: Base x1 x4 L x1 x2 x3 x4 b 1 1/2 1/4 0 15 0 3 -1/2 1 18 -8 -6 0 0 0 Quadro 1A: Base x1 x4 L x1 x2 x3 x4 b 1 1/2 1/4 0 15 2 4 0 1 48 -8 -6 0 0 0 21 Desenvolvimento do Método Simplex 3ª Operação: Multiplicar a 1ª linha por 8 e somar à 3ª linha Quadro 1B: Base x1 x4 L x1 x2 x3 x4 b 1 1/2 1/4 0 15 0 3 -1/2 1 18 -8 -6 0 0 0 Quadro 2: Base x1 x4 L x1 x2 x3 x4 b 1 1/2 1/4 0 15 0 3 -1/2 1 18 0 -2 2 0 120 2ª Solução: X1 = 15; x4 = 18; L = 120 22 Desenvolvimento do Método Simplex c) Terceira solução: Qual deverá se tornar positiva? Produzir primeiro o produto que mais contribui para o lucro, como indicado na última linha (maior valor negativo “absoluto”) x2 Qual variável deverá ser anulada? O menor quociente (b/ x2) indica, pela linha em que ocorreu, qual variável básica deve ser anulada. x1 x2 x3 x4 b 1 1/2 1 /4 0 15 0 3 -1/2 1 18 0 -2 2 0 120 x1 x4 Base L 1ª linha: 15 / 0,5 = 30 2ª linha: 18 / 3 = 6 Variável a ser anulada: x4 x3 = 0 X4 = 0 x1 = ? X2= ? Desenvolvimento do Método Simplex Quadro 2: x1 x2 x3 x4 b 1 1/2 1 /4 0 15 0 3 -1/2 1 18 0 -2 2 0 120 x1 x4 Base L Quadro 2A: Base x1 x2 L x1 x2 x3 x4 b 1 1/2 1/4 0 15 0 1 -1/6 1/3 6 0 -2 2 0 120 Solução: fazendo operações com linhas, a partir do quadro 2, transformar a coluna da nova variável (x2) num vetor identidade, com o elemento 1 na linha correspondente à variável a ser anulada (x4) 4ª Operação: Dividir a 2ª linha por 3 Desenvolvimento do Método Simplex 5ª Operação: Multiplicar a 2ª linha por – ½ e somar à 1ª linha Quadro 2B: Base x1 x2 L x1 x2 x3 x4 b 1 0 1/3 –1/6 12 0 1 -1/6 1/3 6 0 -2 2 0 120 Quadro 2A: Base x1 x2 L x1 x2 x3 x4 b 1 1/2 1/4 0 15 0 1 -1/6 1/3 6 0 -2 2 0 120 Desenvolvimento do Método Simplex 6ª Operação: Multiplicar a 2ª linha por 2 e somar à 3ª linha Quadro 3: Base x1 x2 L x1 x2 x3 x4 b 1 0 1/3 –1/6 12 0 1 -1/6 1/3 6 0 0 5/3 2/3 132 Quadro 2B: Base x1 x2 L x1 x2 x3 x4 b 1 0 1/3 –1/6 12 0 1 -1/6 1/3 6 0 -2 2 0 120 Desenvolvimento do Método Simplex A última linha mostra as contribuições líquidas para o lucro, caso as variáveis x3 e x4 venham a ter seus valores aumentados de 0 para 1. Como essas contribuições têm sinais trocados em relação ao quadro original, concluímos que a solução encontrada: x1=12; x2= 6; x3= 0 e x4=0 é a solução ótima Quadro 3: Base x1 x2 L x1 x2 x3 x4 b 1 0 1/3 –1/6 12 0 1 -1/6 1/3 6 0 0 5/3 2/3 132 Exercício de Fixação 1 A WINDOR GLASS Inc. dispõe de capacidade extra para produzir dois novos produtos. A demanda é muito maior que a capacidade disponível (toda produção poderá ser vendida). Através dos dados contidos na tabela, logo abaixo, qual o mix de produção entre janelas e portas que maximiza o lucro da Inc. E qual será o lucro máximo da companhia? Setor Produtivo Produto Capacidade Disponível Janelas Portas Montagem 1 hora/unid. - 4 horas/mês Laminação - 2 hora/unid. 12 horas/mês Corte 3 hora/unid. 2 hora/unid. 18 horas/mês Lucro Unitário $ 3,00 $ 5,00 • Variáveis X1 = qtde. de janelas, em milhares de unidades; X2 = qtde. de portas, em milhares de unidades; Z = lucro total obtido com novos produtos. • Restrições a) disponibilidade do setor de montagem; b) disponibilidade do setor de laminação; c) disponibilidade do setor de corte; d) quantidades não negativas. • Objetivo Maximizar o lucro total da empresa 0, 1823 122 4:. 53 21 21 2 1 21 xx xx x xas xxZMax Setor Produtivo Produto Capacidade Disponível Janelas Portas Montagem 1 hora/unid. - 4 horas/mês Laminação - 2 hora/unid. 12 horas/mês Corte 3 hora/unid. 2 hora/unid. 18 horas/mês Lucro Unitário $ 3,00 $ 5,00 Exercício de Fixação 1 Solução Gráfica 1 0, 1823 122 4:. 53 21 21 2 1 21 xx xx x xas xxZMax 2 x 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 1 x 12 2 2 x 4 1 x 18 2 3 2 1 x x 0 2 x 0 1 x Neste exemplo, a solução ótima está na interseção entre: a função-objetivo e qualquer uma das restrições, ou as 2 restrições Resolução do problema pelo Método Gráfico Pelo gráfico, na intercessão entre as 2 restrições Laminação 2x2 = 12 (1) Corte 3x1 + 2x2 = 18 (2) Calculando x2 pela 1ª equação: 2x2 = 12 x2 = 6 (3) Substituindo em 2: 3x1 + 2(6) = 18 3x1 + 12 = 18 3x1 = 6 x1 = 2 Solução ótima: 2 janelas e 6 portas Calculando o Lucro Máximo Substitua o ponto ótimo, encontrado anteriormente, na equação da função objetivo Z Solução ótima: 2 janelas e 6 portas Como X1 = 2 e X2 = 6 Substituindo esses valores na função objetivo: 3(2) + 5(6) = 6 + 30 = 36 O lucro máximo da companhia é R$ 36,00 Exercício de Fixação 2 Uma fábrica pretende produzir dois produtos, o produto 1 e o produto 2. Ambos os produtos passampor três fases de desenvolvimento durante o processo de manufatura, cada uma das quais se realiza num departamento diferente. No próximo mês, cada um dos departamentos tem um determinado números disponível de horas por máquina, para ser utilizado na concepção destes dois produtos. Por sua vez, cada um dos produtos requer, por unidade, um dado tempo de utilização de cada máquina. Tempo disponível (h) Tempo requerido por unidade (h) Produto 1 Produto 2 1 0 0 2 2 3 4 12 18 Departamentos 1 2 3 Para manter o problema simples, vamos assumir que os custos de produção de cada produto são constantes, independentemente da quantidade produzida. Supondo que o lucros, por unidade, de cada produto são de R$ 3 para o produto 1 e R$ 5 para o produto 2. Formule um modelo de programação linear para determinar a produção diária de cada um dos modelos de modo a maximizar o lucro total da companhia. • Variáveis X1 = produção diária do produto 1; X2 = produção diária do produto 2; Z = lucro total obtido com os dois produtos. • Restrições a) Tempo disponível para fabricar no departamento 1; b) Tempo disponível para fabricar no departamento 2; c) Tempo disponível para fabricar no departamento 3; d) quantidades não negativas. • Objetivo Maximizar o lucro total da companhia 0, 1823 122 4:. 53 21 21 2 1 21 xx xx x xas xxZMax Exercício de Fixação 2 Tempo disponível (h) Tempo requerido por unidade (h) Produto 1 Produto 2 1 0 0 2 2 3 4 12 18 Departamentos 1 2 3 Representação gráfica do problema x1 x2 2 4 6 8 2 4 6 8 x1 = 4 2x2 = 12 3x1 + 2x2 = 18 0, 1823 122 4:. 53 21 21 2 1 21 xx xx x xas xxZMax x1 x2 2 4 6 8 2 4 6 8 Z = 10 = 3x1 + 5x2 Z = 20 = 3x1 + 5x2 Z = 36 = 3x1 + 5x2 (2, 6) Solução ótima: 2 produtos 1 e 6 produtos 2 Como X1 = 2 e X2 = 6 3(2) + 5(6) = 6 + 30 = 36 Lucro máximo é R$ 36,00 Referências ANDRADE, Eduardo Leopoldino de. Introdução à pesquisa operacional: métodos e modelos para análise de decisões. 3. ed. Rio de Janeiro: LTC, 2004.192 p.
Compartilhar