·
Engenharia de Produção ·
Outros
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Prof Felipe Chagas UNIDADE I Programação Linear Origem da Pesquisa Operacional Origem durante o período da Segunda Guerra Mundial Criada por George B Dantzig 19142005 Programação Linear Utiliza equações de 1 grau daí o termo linear para modelos matemáticos que representem um problema específico Pesquisa Operacional e Programação Linear Fonte httpwwwoexploradorcombrexpw pcontentuploads201409George Dantzig622x336jpg Modelo representação simplificada do comportamento da realidade expressa na forma de equações matemáticas ou esquemas que permitem simular a realidade A modelagem é muito utilizada por empresas de grande porte principalmente quando um processo novo vai ser implementado em suas atividades Processo de aprendizado contínuo Princípios de Modelagem Fonte Autor Definição do problema Construção do Modelo Obtenção de solução a partir do Modelo Testar o Modelo e sua solução Implantação Problema satisfeito Sim Não Exemplo de modelagem Uma empresa fabrica peças mecânicas para a montagem de um carro e possui no momento dois tipos de peças para serem confeccionadas Para a fabricação das peças a empresa compra até 200 toneladas de matériaprima e estabeleceu que o tempo de uso de máquinas na confecção das peças é de 10 horas Se para a fabricação do tipo de peça 1 a empresa gasta 5 toneladas de matériaprima e a mesma peça leva 04 hora em sua fabricação e para a fabricação do tipo de peça 2 a empresa gasta 9 toneladas de matériaprima e a mesma peça leva 03 hora em sua fabricação qual deve ser a quantidade fabricada pela empresa de maneira a maximizar seus lucros vendendo a 200 a peça 1 e 280 a peça 2 Princípios de Modelagem Procedimento para modelagem Primeiramente compreenda o problema Defina as variáveis de decisão do problema variáveis de decisão são os parâmetros que podem ser controlados pelo tomador de decisão Nesse exemplo as variáveis de decisão são quantidade da peça 1 a ser fabricada quantidade da peça 2 a ser fabricada Princípios de Modelagem X1 X2 Procedimento para modelagem Primeiramente compreenda o problema Defina a funçãoobjetivo A funçãoobjetivo é uma função matemática que representa o principal objetivo do tomador de decisão No nosso exemplo o objetivo é maximizar o lucro da empresa que é obtido pela venda das peças nos valores mencionados FO Maximizar Z 200x1 280 x2 Princípios de Modelagem Procedimento para modelagem Primeiramente compreenda o problema Defina as restrições do problema Os recursos da empresa são finitos para fabricar ambas as peças a empresa dispõe apenas de 200 toneladas de matériaprima e opera apenas durante 10 horas como tempo útil para a fabricação das peças Portanto Princípios de Modelagem Assim concluímos a elaboração do modelo para o exemplo apresentado De maneira geral a representação do modelo é dada da seguinte forma Não existe um algoritmo geral para realizar a modelagem de um problema real No entanto é importante seguir algumas dicas para resolver problemas de PPL Identifique as variáveis de decisão do problema Estabeleça qual é o objetivo do problema Defina as restrições do problema Princípios de Modelagem Suponha que uma empresa deseje maximizar seus lucros O lucro obtido pela venda do produto 1 é 3 e o produto 2 é 2 a unidade Para a fabricação dos produtos a empresa dispõe de 6 kg de matériaprima por dia e 6 horas de máquina por dia e produto 1 consome 2 kg de matériaprima e 1 hora para fabricação enquanto que o produto 2 consome 1 kg de matériaprima e leva 2 horas para fabricação O Modelo que representa corretamente o problema citado é Interatividade a b Interatividade Suponha que uma empresa deseje maximizar seus lucros O lucro obtido pela venda do produto 1 é 3 e o produto 2 é 2 a unidade Para a fabricação dos produtos a empresa dispõe de 6 kg de matériaprima por dia e 6 horas de máquina por dia e produto 1 consome 2 kg de matériaprima e 1 hora para fabricação enquanto que o produto 2 consome 1 kg de matériaprima e leva 2 horas para fabricação O Modelo que representa corretamente o problema citado é Resposta c Umas das formas mais elementares para a resolução de Problemas de Programação Linear é por meio do método gráfico Pelo método gráfico inserimos inicialmente as funções de duas variáveis num plano cartesiano onde nos eixos x e y são colocadas as variáveis de decisão para posteriormente serem inseridas as funções lineares do problema Soluções de problemas de Programação Linear Método gráfico 15 10 5 0 5 10 15 15 10 5 0 5 10 15 Variável x2 Variável x1 Fonte Autor Exemplo considere o problema de programação Linear do exemplo anterior de fabricação de peças Primeiro passo analisar as restrições do problema reescrevendo uma variável em função da outra Soluções de problemas de Programação Linear Método gráfico O passo seguinte é reescrever as restrições como funções de primeiro grau onde o valor de x2 depende do valor de x1 Observe que as setas indicam o sinal das inequações A região onde as funções convergem é chamada região viável Soluções de problemas de Programação Linear Método gráfico Fonte Autor Após determinar a região viável estabelecemos as curvas de nível que representam a funçãoobjetivo Para fazermos isso primeiramente precisamos identificar pontos em que a curva de nível da FO tem o mesmo valor Soluções de problemas de Programação Linear Método gráfico Funçãoobjetivo Substituindo os pontos x1 x2010 Encontrar a curva de nível em Z2800 usando x1 x2 x10 Ou seja tendo os dois pontos x1 x2 010 e 140 podemos traçar uma reta para qual o valor de Z é 2800 Veja a curva de nível Z2800 passando por x1x2 010 e 140 Soluções de problemas de Programação Linear Método gráfico Fonte Autor Se repetirmos o processo agora para o ponto x1 x2015 teremos Para esse novo ponto repetimos o processo anterior calculando no ponto x10 Veja a curva de nível Z4200 passando por x1 x2 015 e 210 Soluções de problemas de Programação Linear Método gráfico Veja a curva de nível Z4200 passando por x1 x2 015 e 210 Observe na figura abaixo que a reta para 4200 é paralela à reta para 2800 e obviamente z4200 é uma resposta viável Soluções de problemas de Programação Linear Método gráfico Fonte Autor Então se fizéssemos esse processo repetidas vezes chegaria um momento em que a curva de nível de Z se aproximaria a um dos extremos da região viável Quando isso ocorre dizemos que esta é uma solução ótima para o problema Para encontrar esse ponto ótimo para Z basta encontrarmos o ponto x1 x2ab para o qual temos o vértice superior que define o ponto ótimo para o problema O ponto em questão ocorre quando x2 assume o mesmo valor nas restrições 1 e 2 Soluções de problemas de Programação Linear Método gráfico Obtemos agora a resposta para x1 e x2 Ou seja o valor ótimo para o exemplo se encontra onde x1x21414 Assim 𝑍 200 𝑥1 280 𝑥2 𝑍 200 14 28014 6720 Soluções de problemas de Programação Linear Método gráfico 60 15𝑥1 90 36𝑥1 𝑥1 90 60 36 15 14285 14 𝑥2 200 5𝑥1 9 200 5 14 9 1444 14 O valor Z6720 é o máximo lucro que a empresa pode alcançar aplicandose as produções especificadas para x1 e x2 através do método gráfico Observe o ponto ótimo Soluções de problemas de Programação Linear Método gráfico Fonte Autor Z6720 Observe o problema abaixo A figura que representa corretamente a região viável delimitada pelo método gráfico é Interatividade Interatividade a b Variável x2 Variável x2 Variável x1 Variável x1 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 Região viável 0 5 10 15 0 2 4 6 8 10 Região viável Restrição 1 Restrição 2 x10 x20 Restrição 1 Restrição 2 x10 x20 Interatividade c e Restrição 1 Restrição 2 x10 x20 Variável x1 Variável x1 Restrição 1 Restrição 2 x10 x20 Série 1 Série 2 x10 x20 45 4 35 3 25 2 15 1 05 0 Variável x2 45 4 35 3 25 2 15 1 05 0 d Variável x2 45 4 35 3 25 2 15 1 05 0 Variável x2 0 2 4 6 8 10 Variável x1 0 2 4 6 8 10 0 5 10 15 Resposta c Restrição 1 Restrição 2 x10 x20 45 4 35 3 25 2 15 1 05 0 Variável x2 0 2 4 6 8 10 Variável x1 O algoritmo simplex é um procedimento algébrico para solucionar problemas de Programação Linear A solução pelo método gráfico como visto anteriormente quando aplicado para mais de duas variáveis é impraticável O simplex permite resolver o problema de forma ordenada seguindo uma metodologia bem simples O método Simplex A forma padrão de um problema de Programação Linear é uma maneira de estabelecer que as entradas para o algoritmo simplex sejam do mesmo formato para qualquer problema Considerando um algoritmo de maximização a forma padrão é a seguinte Problemas de Programação linear na forma padrão Max Z C1x1 C2x2 C3x3 Cnxn 1 a11x1a12x2a13x3 b1 Sujeito a 2 a21x1a22x2a23x3 b2 3 a31x1a32x2a33x3 b3 Podemse observar os seguintes aspectos na forma padrão apresentada A função objetivo é do tipo maximização Todos os lados direitos das restrições são positivos Todas as restrições são do tipo igualdade Todas as variáveis de decisão são positivas Problemas de Programação linear na forma padrão Max Z C1x1 C2x2 C3x3 Cnxn 1 a11x1a12x2a13x3 b1 Sujeito a 2 a21x1a22x2a23x3 b2 3 a31x1a32x2a33x3 b3 Agora veremos como resolver um problema de programação linear a partir do simplex já aplicando a um exemplo básico Considere o seguinte caso Algoritmo do método Simplex Max Z x115x2 1 2x1 2x2 160 Sujeito a 2 x1 2x2 120 3 4x12x2 280 X1x2 0 Passo 1 Verificar se o problema está escrito na forma padrão Observe que o problema apresenta sinais de desigualdade nas restrições e a função objetivo não está escrita na forma padrão Algoritmo do método Simplex Max Z x115x2 1 2x1 2x2 160 Sujeito a 2 x1 2x2 120 3 4x12x2 280 x1x2 0 Passo 2 Reescrever a função objetivo igualandoa a zero Passo 3 Inserir as variáveis de folga nas restrições Observe que colocamos uma variável de folga para cada restrição Algoritmo do método Simplex Z x115x2 0 2x1 2x2 f1 160 x1 2x2 f2 120 4x12x2 f3 280 x1x2 0 Passo 4 Construir o quadro do simplex A tabela simplex apresenta um local em que identificamos cada uma das variáveis Os valores do quadro indicam os coeficientes dos termos para cada equação A coluna LD indica os valores que estão do lado direito da igualdade e LE indica os coeficientes do lado esquerdo da igualdade Algoritmo do método Simplex Z X1 X2 F1 F2 F3 B EqZ 1 1 15 0 0 0 0 Rest1 0 2 2 1 0 0 160 Rest2 0 1 2 0 1 0 120 Rest3 0 4 2 0 0 1 280 LE LD Passo 5 Início do processo de repetição A partir desse passo iremos recalcular o tableau do Simplex otimizandoo até obtermos a melhor resposta possível Primeiramente substitua variável básica linha que entra por outra variável básica linha que sai A primeira é definida pelo menor número negativo na primeira linha linha da função objetivo e a segunda é o menor número positivo linha pivô Algoritmo do método Simplex Passo 6 Identificar o elemento pivô e dividir toda linha pelo elemento pivô Veja que toda a tabela do simplex se manteve igual exceto a linha pivô que agora possui todos os valores divididos pelo elemento pivô Algoritmo do método Simplex Toda linha pivô foi dividida pelo elemento pivô 2 Passo 7 calcular as novas linhas fazendo com que os coeficientes das variáveis básicas sejam iguais a 1 e os coeficientes das variáveis não básicas sejam iguais a 0 No cálculo da Nova linha 1 fizemos o seguinte cálculo Algoritmo do método Simplex NL1 L1 Termo da coluna que entra da L1 Termo da linha pivô E assim obtemos a tabela do simplex atualizada com os novos valores da Linha 1 Algoritmo do método Simplex E assim obtemos a tabela do simplex atualizada com os novos valores da Linha 1 Algoritmo do método Simplex 1ª coluna 11501 2ª coluna 11505025 3ª coluna 15 1510 4ª coluna 01500 5ª coluna 01505075 6ª coluna 01500 7ª coluna 0156090 Repetimos o mesmo procedimento para as demais linhas recalculando os termos da mesma forma que foi feito pra linha 1 para as linhas 2 e 4 não fazemos para a linha 3 pois ela é a linha pivô Algoritmo do método Simplex NL2 L2 Termo da coluna que entra da L2 Termo da linha pivô NL4 L4 Termo da coluna que entra da L4 Termo da linha pivô A nova tabela do simplex ao final dos cálculos da primeira tentativa fica assim Algoritmo do método Simplex Z X1 X2 F1 F2 F3 B L1 EqZ 1 025 0 0 075 0 90 L2 Rest1 0 1 0 1 1 0 40 L3 Rest2 0 05 1 0 05 0 60 L4 Rest3 0 3 0 0 1 1 160 Veja que ainda existem valores negativos na primeira linha linha do Z Isso quer dizer que a solução não é ótima e precisamos voltar ao passo 5 e repetir o processo até que todos os valores sejam 0 Fazemos o processo de substituição novamente e aplicamos os cálculos para cada uma das novas linhas nessa segunda tentativa Ao final do processo obteremos a seguinte tabela otimizada Algoritmo do método Simplex Z X1 X2 F1 F2 F3 B L1 EqZ 1 0 0 025 05 0 100 L2 Rest1 0 1 0 1 1 0 40 L3 Rest2 0 0 1 05 1 0 40 L4 Rest3 0 0 0 3 2 1 40 Veja que agora todos os termos da primeira linha linha do Z são positivos Isso quer dizer que essa é a resposta ótima do problema Então de todas as soluções possíveis a melhor será Chegamos aqui ao fim do algoritmo do simplex Algoritmo do método Simplex x1 40 x2 40 f3 40 Max Z 40 1540 100 Dado o problema de programação linear abaixo A tabela inicial do simplex é dada pela alternativa Interatividade Max Z 25x1x2 2x1 x2 100 Sujeito a 2x1 99x2 200 2x13x2 50 x1x2 0 A Interatividade Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 B Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 Interatividade C D Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 200 1 0 0 Rest3 0 2 3 0 0 1 50 Interatividade E Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 A Resposta Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 Problemas de Programação Linear apresentam uma propriedade muito particular a dualidade que é a relação de um problema associado denominado dual a um problema original denominado primal Ambos estão interrelacionados de forma que é possível estabelecer uma relação entre a solução ótima de um problema e a do outro O primeiro passo para compreender a dualidade de um problema de Programação Linear é saber que iremos transformar um problema original primal em um problema associado dual mantendo porém a mesma solução ótima em ambos os casos Dualidade Para trabalhar a dualidade transformando um problema de programação linear aplicamos os seguintes passos 1 Se o problema primal é de minimização o dual é de maximização e viceversa ou seja Dualidade Máx Z Min D Min D Máx Z Para trabalhar a dualidade transformando um problema de programação linear aplicamos os seguintes passos 2 Se o problema primal tem n variáveis e m restrições o problema dual tem m variáveis e n restrições ou seja Se um problema apresenta 3 variáveis e 4 restrições O Dual desse mesmo problema apresentará 4 variáveis de decisão e 3 restrições Dualidade Para trabalhar a dualidade transformando um problema de programação linear aplicamos os seguintes passos 3 Os elementos do lado direito das restrições no primal são os coeficientes da função objetivo no dual 4 O problema de maximização deve ter restrições do tipo e o de minimização deve ter restrições do tipo Se isso não ocorrer multiplicamos a restrição por 1 trocando o sinal de toda a restrição 5 As variáveis do problema devem ser não negativas Dualidade Vejamos um exemplo de aplicação Primeiramente vamos escrever a tabela inicial do simplex Dualidade Exemplo Max Z 4x15x29x3 x1 x2 2x3 16 Sujeito a 7x1 5x2 3x3 25 x1x2x3 0 X1 X2 X3 Sinal Lado Direito da Restrição Restrição 1 1 1 3 16 Restrição 2 7 5 3 25 Restrição 3 4 5 9 Veja que o problema tem 2 restrições e 3 incógnitas Na transformação para o Dual ele terá 3 restrições e 2 incógnitas Dualidade Exemplo x1 x2 x3 Sinal Lado Direito da Restrição y1 1 1 3 16 y2 7 5 3 25 Z 4 5 9 Antes Veja que o problema tem 2 restrições e 3 incógnitas Na transformação para o Dual ele terá 3 restrições e 2 incógnitas Dualidade Exemplo x1 x2 x3 Sinal Lado Direito da Restrição Primal y1 1 1 3 16 y2 7 5 3 25 Sinal Lado Direito da restrição Dual 4 5 9 Depois Agora vamos obter a função objetivo do problema Dual Obtemos assim o problema Dual Dualidade Exemplo Min D 16y125y2 y1 7y2 4 Sujeito a y1 5y2 5 3y1 3y2 9 y1y2 0 Restrição 1 Restrição 2 Restrição3 Sinal Lado Direito da Restrição Primal y1 1 1 3 16 y2 7 5 3 25 Sinal Lado Direito da restrição Dual 4 5 9 A resposta obtida pelo Simplex no problema Dual é a mesma obtida pelo problema Primal Nesse caso em ambos os casos pode ser aplicado o método simplex Mas afinal qual é a interpretação que podemos fazer da solução do problema Dual Existe uma interpretação econômica após a resolução de um problema em sua forma dual pelo simplex podendo indicar o quanto o aumento de uma variável afeta a maximização do problema ou minimização em relação ao aumento de outra variável Interpretação da Dualidade Por exemplo considerando o problema Interpretação da Dualidade Max Z 4x1 5x2 3x3 x1 x2 2x3 100 Sujeito a 6x1 6x2 42x3 360 8x1 4x2 4x3 400 x1x2x3 0 Teremos a seguinte tabela otimizada pelo simplex nos dois problemas Interpretação da Dualidade SIMPLEX PRIMAL FINAL Z X1 X2 X3 F1 F2 F3 B EqZ 1 0 0 1 1 05 0 280 Rest1 0 0 1 133 1 017 0 40 Rest2 0 1 0 067 1 033 0 20 Rest3 0 0 0 4 4 2 1 80 Teremos a seguinte tabela otimizada pelo simplex nos dois problemas Interpretação da Dualidade SIMPLEX DUAL FINAL D Y1 Y2 Y3 G1 G2 G3 C EqD 1 0 0 80 20 40 0 280 Rest1 0 0 1 0 1 0 0 1 Rest2 0 1 0 0 0 0 0 1 Rest3 0 0 1 0 0 0 0 05 Perceba que as soluções para os problemas primal e dual são respectivamente Agora imagine que está sendo oferecida uma unidade adicional de matériaprima para confecção dos produtos ou seja em vez de 100 kg de matériaprima teríamos 101 kg A equação do Dual ficaria assim Interpretação da Dualidade Z 4x1 5x2 3x3 420 540 30 280 D 100y1 360y2 400y3 1001 36005 4000 280 D 101y1 360y2 400y3 D 1011 36005 4000 281 Ou seja em tese 1 kg a mais indicaria 1 de lucro Mas se para adquirir 1 kg de matériaprima o custo é 3 na verdade estaríamos tendo um prejuízo de 2 Interpretação da Dualidade Daí extraímos uma importante informação o valor ótimo de uma variável do modelo dual é o limite que devemos pagar pelo acréscimo de uma unidade adicional do recurso associado à variável Isso é chamado de preçosombra Ou seja não podemos simplesmente aumentar a quantidade produzida visando aumentar o lucro num determinado problema sem levar em conta o fator econômico que esse aumento pode acarretar Ou seja pode ser que no final haja um prejuízo Interpretação da Dualidade Dado o problema primal Sua versão Dual apresentará a 2 variáveis de decisão e 3 restrições b 3 variáveis de decisão e 2 restrições c 2 variáveis de folga e 4 variáveis de decisão d 2 variáveis de decisão e 2 restrições e NDA Interatividade Max Z 4x1 5x2 9x3 x1 x2 2x3 16 Sujeito a 7x1 5x2 3x3 25 x1x2x3 0 Dado o problema primal Sua versão Dual apresentará a 2 variáveis de decisão e 3 restrições b 3 variáveis de decisão e 2 restrições c 2 variáveis de folga e 4 variáveis de decisão d 2 variáveis de decisão e 2 restrições e NDA Resposta Max Z 4x1 5x2 9x3 x1 x2 2x3 16 Sujeito a 7x1 5x2 3x3 25 x1x2x3 0 ATÉ A PRÓXIMA
Envie sua pergunta para a IA e receba a resposta na hora
Texto de pré-visualização
Prof Felipe Chagas UNIDADE I Programação Linear Origem da Pesquisa Operacional Origem durante o período da Segunda Guerra Mundial Criada por George B Dantzig 19142005 Programação Linear Utiliza equações de 1 grau daí o termo linear para modelos matemáticos que representem um problema específico Pesquisa Operacional e Programação Linear Fonte httpwwwoexploradorcombrexpw pcontentuploads201409George Dantzig622x336jpg Modelo representação simplificada do comportamento da realidade expressa na forma de equações matemáticas ou esquemas que permitem simular a realidade A modelagem é muito utilizada por empresas de grande porte principalmente quando um processo novo vai ser implementado em suas atividades Processo de aprendizado contínuo Princípios de Modelagem Fonte Autor Definição do problema Construção do Modelo Obtenção de solução a partir do Modelo Testar o Modelo e sua solução Implantação Problema satisfeito Sim Não Exemplo de modelagem Uma empresa fabrica peças mecânicas para a montagem de um carro e possui no momento dois tipos de peças para serem confeccionadas Para a fabricação das peças a empresa compra até 200 toneladas de matériaprima e estabeleceu que o tempo de uso de máquinas na confecção das peças é de 10 horas Se para a fabricação do tipo de peça 1 a empresa gasta 5 toneladas de matériaprima e a mesma peça leva 04 hora em sua fabricação e para a fabricação do tipo de peça 2 a empresa gasta 9 toneladas de matériaprima e a mesma peça leva 03 hora em sua fabricação qual deve ser a quantidade fabricada pela empresa de maneira a maximizar seus lucros vendendo a 200 a peça 1 e 280 a peça 2 Princípios de Modelagem Procedimento para modelagem Primeiramente compreenda o problema Defina as variáveis de decisão do problema variáveis de decisão são os parâmetros que podem ser controlados pelo tomador de decisão Nesse exemplo as variáveis de decisão são quantidade da peça 1 a ser fabricada quantidade da peça 2 a ser fabricada Princípios de Modelagem X1 X2 Procedimento para modelagem Primeiramente compreenda o problema Defina a funçãoobjetivo A funçãoobjetivo é uma função matemática que representa o principal objetivo do tomador de decisão No nosso exemplo o objetivo é maximizar o lucro da empresa que é obtido pela venda das peças nos valores mencionados FO Maximizar Z 200x1 280 x2 Princípios de Modelagem Procedimento para modelagem Primeiramente compreenda o problema Defina as restrições do problema Os recursos da empresa são finitos para fabricar ambas as peças a empresa dispõe apenas de 200 toneladas de matériaprima e opera apenas durante 10 horas como tempo útil para a fabricação das peças Portanto Princípios de Modelagem Assim concluímos a elaboração do modelo para o exemplo apresentado De maneira geral a representação do modelo é dada da seguinte forma Não existe um algoritmo geral para realizar a modelagem de um problema real No entanto é importante seguir algumas dicas para resolver problemas de PPL Identifique as variáveis de decisão do problema Estabeleça qual é o objetivo do problema Defina as restrições do problema Princípios de Modelagem Suponha que uma empresa deseje maximizar seus lucros O lucro obtido pela venda do produto 1 é 3 e o produto 2 é 2 a unidade Para a fabricação dos produtos a empresa dispõe de 6 kg de matériaprima por dia e 6 horas de máquina por dia e produto 1 consome 2 kg de matériaprima e 1 hora para fabricação enquanto que o produto 2 consome 1 kg de matériaprima e leva 2 horas para fabricação O Modelo que representa corretamente o problema citado é Interatividade a b Interatividade Suponha que uma empresa deseje maximizar seus lucros O lucro obtido pela venda do produto 1 é 3 e o produto 2 é 2 a unidade Para a fabricação dos produtos a empresa dispõe de 6 kg de matériaprima por dia e 6 horas de máquina por dia e produto 1 consome 2 kg de matériaprima e 1 hora para fabricação enquanto que o produto 2 consome 1 kg de matériaprima e leva 2 horas para fabricação O Modelo que representa corretamente o problema citado é Resposta c Umas das formas mais elementares para a resolução de Problemas de Programação Linear é por meio do método gráfico Pelo método gráfico inserimos inicialmente as funções de duas variáveis num plano cartesiano onde nos eixos x e y são colocadas as variáveis de decisão para posteriormente serem inseridas as funções lineares do problema Soluções de problemas de Programação Linear Método gráfico 15 10 5 0 5 10 15 15 10 5 0 5 10 15 Variável x2 Variável x1 Fonte Autor Exemplo considere o problema de programação Linear do exemplo anterior de fabricação de peças Primeiro passo analisar as restrições do problema reescrevendo uma variável em função da outra Soluções de problemas de Programação Linear Método gráfico O passo seguinte é reescrever as restrições como funções de primeiro grau onde o valor de x2 depende do valor de x1 Observe que as setas indicam o sinal das inequações A região onde as funções convergem é chamada região viável Soluções de problemas de Programação Linear Método gráfico Fonte Autor Após determinar a região viável estabelecemos as curvas de nível que representam a funçãoobjetivo Para fazermos isso primeiramente precisamos identificar pontos em que a curva de nível da FO tem o mesmo valor Soluções de problemas de Programação Linear Método gráfico Funçãoobjetivo Substituindo os pontos x1 x2010 Encontrar a curva de nível em Z2800 usando x1 x2 x10 Ou seja tendo os dois pontos x1 x2 010 e 140 podemos traçar uma reta para qual o valor de Z é 2800 Veja a curva de nível Z2800 passando por x1x2 010 e 140 Soluções de problemas de Programação Linear Método gráfico Fonte Autor Se repetirmos o processo agora para o ponto x1 x2015 teremos Para esse novo ponto repetimos o processo anterior calculando no ponto x10 Veja a curva de nível Z4200 passando por x1 x2 015 e 210 Soluções de problemas de Programação Linear Método gráfico Veja a curva de nível Z4200 passando por x1 x2 015 e 210 Observe na figura abaixo que a reta para 4200 é paralela à reta para 2800 e obviamente z4200 é uma resposta viável Soluções de problemas de Programação Linear Método gráfico Fonte Autor Então se fizéssemos esse processo repetidas vezes chegaria um momento em que a curva de nível de Z se aproximaria a um dos extremos da região viável Quando isso ocorre dizemos que esta é uma solução ótima para o problema Para encontrar esse ponto ótimo para Z basta encontrarmos o ponto x1 x2ab para o qual temos o vértice superior que define o ponto ótimo para o problema O ponto em questão ocorre quando x2 assume o mesmo valor nas restrições 1 e 2 Soluções de problemas de Programação Linear Método gráfico Obtemos agora a resposta para x1 e x2 Ou seja o valor ótimo para o exemplo se encontra onde x1x21414 Assim 𝑍 200 𝑥1 280 𝑥2 𝑍 200 14 28014 6720 Soluções de problemas de Programação Linear Método gráfico 60 15𝑥1 90 36𝑥1 𝑥1 90 60 36 15 14285 14 𝑥2 200 5𝑥1 9 200 5 14 9 1444 14 O valor Z6720 é o máximo lucro que a empresa pode alcançar aplicandose as produções especificadas para x1 e x2 através do método gráfico Observe o ponto ótimo Soluções de problemas de Programação Linear Método gráfico Fonte Autor Z6720 Observe o problema abaixo A figura que representa corretamente a região viável delimitada pelo método gráfico é Interatividade Interatividade a b Variável x2 Variável x2 Variável x1 Variável x1 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 Região viável 0 5 10 15 0 2 4 6 8 10 Região viável Restrição 1 Restrição 2 x10 x20 Restrição 1 Restrição 2 x10 x20 Interatividade c e Restrição 1 Restrição 2 x10 x20 Variável x1 Variável x1 Restrição 1 Restrição 2 x10 x20 Série 1 Série 2 x10 x20 45 4 35 3 25 2 15 1 05 0 Variável x2 45 4 35 3 25 2 15 1 05 0 d Variável x2 45 4 35 3 25 2 15 1 05 0 Variável x2 0 2 4 6 8 10 Variável x1 0 2 4 6 8 10 0 5 10 15 Resposta c Restrição 1 Restrição 2 x10 x20 45 4 35 3 25 2 15 1 05 0 Variável x2 0 2 4 6 8 10 Variável x1 O algoritmo simplex é um procedimento algébrico para solucionar problemas de Programação Linear A solução pelo método gráfico como visto anteriormente quando aplicado para mais de duas variáveis é impraticável O simplex permite resolver o problema de forma ordenada seguindo uma metodologia bem simples O método Simplex A forma padrão de um problema de Programação Linear é uma maneira de estabelecer que as entradas para o algoritmo simplex sejam do mesmo formato para qualquer problema Considerando um algoritmo de maximização a forma padrão é a seguinte Problemas de Programação linear na forma padrão Max Z C1x1 C2x2 C3x3 Cnxn 1 a11x1a12x2a13x3 b1 Sujeito a 2 a21x1a22x2a23x3 b2 3 a31x1a32x2a33x3 b3 Podemse observar os seguintes aspectos na forma padrão apresentada A função objetivo é do tipo maximização Todos os lados direitos das restrições são positivos Todas as restrições são do tipo igualdade Todas as variáveis de decisão são positivas Problemas de Programação linear na forma padrão Max Z C1x1 C2x2 C3x3 Cnxn 1 a11x1a12x2a13x3 b1 Sujeito a 2 a21x1a22x2a23x3 b2 3 a31x1a32x2a33x3 b3 Agora veremos como resolver um problema de programação linear a partir do simplex já aplicando a um exemplo básico Considere o seguinte caso Algoritmo do método Simplex Max Z x115x2 1 2x1 2x2 160 Sujeito a 2 x1 2x2 120 3 4x12x2 280 X1x2 0 Passo 1 Verificar se o problema está escrito na forma padrão Observe que o problema apresenta sinais de desigualdade nas restrições e a função objetivo não está escrita na forma padrão Algoritmo do método Simplex Max Z x115x2 1 2x1 2x2 160 Sujeito a 2 x1 2x2 120 3 4x12x2 280 x1x2 0 Passo 2 Reescrever a função objetivo igualandoa a zero Passo 3 Inserir as variáveis de folga nas restrições Observe que colocamos uma variável de folga para cada restrição Algoritmo do método Simplex Z x115x2 0 2x1 2x2 f1 160 x1 2x2 f2 120 4x12x2 f3 280 x1x2 0 Passo 4 Construir o quadro do simplex A tabela simplex apresenta um local em que identificamos cada uma das variáveis Os valores do quadro indicam os coeficientes dos termos para cada equação A coluna LD indica os valores que estão do lado direito da igualdade e LE indica os coeficientes do lado esquerdo da igualdade Algoritmo do método Simplex Z X1 X2 F1 F2 F3 B EqZ 1 1 15 0 0 0 0 Rest1 0 2 2 1 0 0 160 Rest2 0 1 2 0 1 0 120 Rest3 0 4 2 0 0 1 280 LE LD Passo 5 Início do processo de repetição A partir desse passo iremos recalcular o tableau do Simplex otimizandoo até obtermos a melhor resposta possível Primeiramente substitua variável básica linha que entra por outra variável básica linha que sai A primeira é definida pelo menor número negativo na primeira linha linha da função objetivo e a segunda é o menor número positivo linha pivô Algoritmo do método Simplex Passo 6 Identificar o elemento pivô e dividir toda linha pelo elemento pivô Veja que toda a tabela do simplex se manteve igual exceto a linha pivô que agora possui todos os valores divididos pelo elemento pivô Algoritmo do método Simplex Toda linha pivô foi dividida pelo elemento pivô 2 Passo 7 calcular as novas linhas fazendo com que os coeficientes das variáveis básicas sejam iguais a 1 e os coeficientes das variáveis não básicas sejam iguais a 0 No cálculo da Nova linha 1 fizemos o seguinte cálculo Algoritmo do método Simplex NL1 L1 Termo da coluna que entra da L1 Termo da linha pivô E assim obtemos a tabela do simplex atualizada com os novos valores da Linha 1 Algoritmo do método Simplex E assim obtemos a tabela do simplex atualizada com os novos valores da Linha 1 Algoritmo do método Simplex 1ª coluna 11501 2ª coluna 11505025 3ª coluna 15 1510 4ª coluna 01500 5ª coluna 01505075 6ª coluna 01500 7ª coluna 0156090 Repetimos o mesmo procedimento para as demais linhas recalculando os termos da mesma forma que foi feito pra linha 1 para as linhas 2 e 4 não fazemos para a linha 3 pois ela é a linha pivô Algoritmo do método Simplex NL2 L2 Termo da coluna que entra da L2 Termo da linha pivô NL4 L4 Termo da coluna que entra da L4 Termo da linha pivô A nova tabela do simplex ao final dos cálculos da primeira tentativa fica assim Algoritmo do método Simplex Z X1 X2 F1 F2 F3 B L1 EqZ 1 025 0 0 075 0 90 L2 Rest1 0 1 0 1 1 0 40 L3 Rest2 0 05 1 0 05 0 60 L4 Rest3 0 3 0 0 1 1 160 Veja que ainda existem valores negativos na primeira linha linha do Z Isso quer dizer que a solução não é ótima e precisamos voltar ao passo 5 e repetir o processo até que todos os valores sejam 0 Fazemos o processo de substituição novamente e aplicamos os cálculos para cada uma das novas linhas nessa segunda tentativa Ao final do processo obteremos a seguinte tabela otimizada Algoritmo do método Simplex Z X1 X2 F1 F2 F3 B L1 EqZ 1 0 0 025 05 0 100 L2 Rest1 0 1 0 1 1 0 40 L3 Rest2 0 0 1 05 1 0 40 L4 Rest3 0 0 0 3 2 1 40 Veja que agora todos os termos da primeira linha linha do Z são positivos Isso quer dizer que essa é a resposta ótima do problema Então de todas as soluções possíveis a melhor será Chegamos aqui ao fim do algoritmo do simplex Algoritmo do método Simplex x1 40 x2 40 f3 40 Max Z 40 1540 100 Dado o problema de programação linear abaixo A tabela inicial do simplex é dada pela alternativa Interatividade Max Z 25x1x2 2x1 x2 100 Sujeito a 2x1 99x2 200 2x13x2 50 x1x2 0 A Interatividade Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 B Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 Interatividade C D Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 200 1 0 0 Rest3 0 2 3 0 0 1 50 Interatividade E Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 A Resposta Z X1 X2 F1 F2 F3 B EqZ 1 25 1 0 0 0 0 Rest1 0 2 1 1 0 0 100 Rest2 0 2 99 0 1 0 200 Rest3 0 2 3 0 0 1 50 Problemas de Programação Linear apresentam uma propriedade muito particular a dualidade que é a relação de um problema associado denominado dual a um problema original denominado primal Ambos estão interrelacionados de forma que é possível estabelecer uma relação entre a solução ótima de um problema e a do outro O primeiro passo para compreender a dualidade de um problema de Programação Linear é saber que iremos transformar um problema original primal em um problema associado dual mantendo porém a mesma solução ótima em ambos os casos Dualidade Para trabalhar a dualidade transformando um problema de programação linear aplicamos os seguintes passos 1 Se o problema primal é de minimização o dual é de maximização e viceversa ou seja Dualidade Máx Z Min D Min D Máx Z Para trabalhar a dualidade transformando um problema de programação linear aplicamos os seguintes passos 2 Se o problema primal tem n variáveis e m restrições o problema dual tem m variáveis e n restrições ou seja Se um problema apresenta 3 variáveis e 4 restrições O Dual desse mesmo problema apresentará 4 variáveis de decisão e 3 restrições Dualidade Para trabalhar a dualidade transformando um problema de programação linear aplicamos os seguintes passos 3 Os elementos do lado direito das restrições no primal são os coeficientes da função objetivo no dual 4 O problema de maximização deve ter restrições do tipo e o de minimização deve ter restrições do tipo Se isso não ocorrer multiplicamos a restrição por 1 trocando o sinal de toda a restrição 5 As variáveis do problema devem ser não negativas Dualidade Vejamos um exemplo de aplicação Primeiramente vamos escrever a tabela inicial do simplex Dualidade Exemplo Max Z 4x15x29x3 x1 x2 2x3 16 Sujeito a 7x1 5x2 3x3 25 x1x2x3 0 X1 X2 X3 Sinal Lado Direito da Restrição Restrição 1 1 1 3 16 Restrição 2 7 5 3 25 Restrição 3 4 5 9 Veja que o problema tem 2 restrições e 3 incógnitas Na transformação para o Dual ele terá 3 restrições e 2 incógnitas Dualidade Exemplo x1 x2 x3 Sinal Lado Direito da Restrição y1 1 1 3 16 y2 7 5 3 25 Z 4 5 9 Antes Veja que o problema tem 2 restrições e 3 incógnitas Na transformação para o Dual ele terá 3 restrições e 2 incógnitas Dualidade Exemplo x1 x2 x3 Sinal Lado Direito da Restrição Primal y1 1 1 3 16 y2 7 5 3 25 Sinal Lado Direito da restrição Dual 4 5 9 Depois Agora vamos obter a função objetivo do problema Dual Obtemos assim o problema Dual Dualidade Exemplo Min D 16y125y2 y1 7y2 4 Sujeito a y1 5y2 5 3y1 3y2 9 y1y2 0 Restrição 1 Restrição 2 Restrição3 Sinal Lado Direito da Restrição Primal y1 1 1 3 16 y2 7 5 3 25 Sinal Lado Direito da restrição Dual 4 5 9 A resposta obtida pelo Simplex no problema Dual é a mesma obtida pelo problema Primal Nesse caso em ambos os casos pode ser aplicado o método simplex Mas afinal qual é a interpretação que podemos fazer da solução do problema Dual Existe uma interpretação econômica após a resolução de um problema em sua forma dual pelo simplex podendo indicar o quanto o aumento de uma variável afeta a maximização do problema ou minimização em relação ao aumento de outra variável Interpretação da Dualidade Por exemplo considerando o problema Interpretação da Dualidade Max Z 4x1 5x2 3x3 x1 x2 2x3 100 Sujeito a 6x1 6x2 42x3 360 8x1 4x2 4x3 400 x1x2x3 0 Teremos a seguinte tabela otimizada pelo simplex nos dois problemas Interpretação da Dualidade SIMPLEX PRIMAL FINAL Z X1 X2 X3 F1 F2 F3 B EqZ 1 0 0 1 1 05 0 280 Rest1 0 0 1 133 1 017 0 40 Rest2 0 1 0 067 1 033 0 20 Rest3 0 0 0 4 4 2 1 80 Teremos a seguinte tabela otimizada pelo simplex nos dois problemas Interpretação da Dualidade SIMPLEX DUAL FINAL D Y1 Y2 Y3 G1 G2 G3 C EqD 1 0 0 80 20 40 0 280 Rest1 0 0 1 0 1 0 0 1 Rest2 0 1 0 0 0 0 0 1 Rest3 0 0 1 0 0 0 0 05 Perceba que as soluções para os problemas primal e dual são respectivamente Agora imagine que está sendo oferecida uma unidade adicional de matériaprima para confecção dos produtos ou seja em vez de 100 kg de matériaprima teríamos 101 kg A equação do Dual ficaria assim Interpretação da Dualidade Z 4x1 5x2 3x3 420 540 30 280 D 100y1 360y2 400y3 1001 36005 4000 280 D 101y1 360y2 400y3 D 1011 36005 4000 281 Ou seja em tese 1 kg a mais indicaria 1 de lucro Mas se para adquirir 1 kg de matériaprima o custo é 3 na verdade estaríamos tendo um prejuízo de 2 Interpretação da Dualidade Daí extraímos uma importante informação o valor ótimo de uma variável do modelo dual é o limite que devemos pagar pelo acréscimo de uma unidade adicional do recurso associado à variável Isso é chamado de preçosombra Ou seja não podemos simplesmente aumentar a quantidade produzida visando aumentar o lucro num determinado problema sem levar em conta o fator econômico que esse aumento pode acarretar Ou seja pode ser que no final haja um prejuízo Interpretação da Dualidade Dado o problema primal Sua versão Dual apresentará a 2 variáveis de decisão e 3 restrições b 3 variáveis de decisão e 2 restrições c 2 variáveis de folga e 4 variáveis de decisão d 2 variáveis de decisão e 2 restrições e NDA Interatividade Max Z 4x1 5x2 9x3 x1 x2 2x3 16 Sujeito a 7x1 5x2 3x3 25 x1x2x3 0 Dado o problema primal Sua versão Dual apresentará a 2 variáveis de decisão e 3 restrições b 3 variáveis de decisão e 2 restrições c 2 variáveis de folga e 4 variáveis de decisão d 2 variáveis de decisão e 2 restrições e NDA Resposta Max Z 4x1 5x2 9x3 x1 x2 2x3 16 Sujeito a 7x1 5x2 3x3 25 x1x2x3 0 ATÉ A PRÓXIMA