Programação Linear com Lindo, Lingo e Solver

Prévia do material em texto

ENGENHARIA DE PRODUÇÃO
PROGRAMAÇÃO LINEAR
Nome: 
Matrícula: 
Nome: 
Matrícula: 
Nome: 
Matrícula: 
Nome: 
Matrícula: 
Nome: 
Matrícula: 
Universidade do Estado do Rio de Janeiro
FAT – Faculdade de Tecnologia
Professora 
Resende, 12 de dezembro de 2016
Resumo
A otimização de processos é fundamental em qualquer área do conhecimento. Nesse sentido, a programação linear é uma técnica usada com frequência para solucionar problemas tanto do setor público quanto do privado, sendo aplicada a diversos fins como por exemplo: maximizar o rendimento e o lucro e minimizar os gastos em um determinado processo. A programação linear é usada para ajustar as variáveis de modo que melhor se adequem ao processo. Isso pode ser resolvido com ajuda de softwares de modelagem. O modelo SIMPLEX é o mais simples e utiliza da álgebra linear. Para aplicação dessas metodologias, podem ser utilizados softwares como o “LINDO”, o “LINGO” e o “SOLVER”, que são de fácil entendimento e rápida execução, mas necessitam de variáveis de entrada como: funções objetivo, variáveis de decisão e restrições do modelo, para que o programa seja executado e os resultados demonstrados. O uso desses softwares ajuda o usuário na tomada de decisões, facilitando e reduzindo o tempo gasto para a resolução de problemas.
Introdução
Problemas de Programação Linear (PL) visam a distribuição eficiente de recursos para atender um determinado objetivo, em geral, maximizar lucros ou minimizar custos. Se tratando de PL, esse objetivo é expresso através de uma função linear, denominada função objetivo.
É necessário também que se esclareça quais as atividades que consomem recursos e em que proporções. Essas informações são apresentadas em forma de equações ou inequações lineares, uma para cada recurso, denominadas restrições.
Normalmente se tem inúmeras maneiras de distribuir os recursos entre as diversas atividades, bastando para com isso que essas distribuições estejam coerentes com as restrições do modelo. No entanto, o que se busca, num problema PL é a função objetivo. A essa solução dá-se o nome de solução ótima. Assim, a programação linear constitui em achar a solução ótima de um problema, ou seja, a função objetivo e as restrições lineares.
A utilização de programação linear é recomendada para problemas de maior porte, em que muitas variáveis e restrições devem ser consideradas. Por isso, o desenvolvimento de algoritmos computacionais eficientes e precisos têm sido a maior preocupação entre os pesquisadores.
Entretanto, problemas menores podem ser resolvidos em um computador pessoal utilizando um dos softwares desenvolvidos para resolução de problemas de programação linear, como por exemplo LINGO, LINDO e Solver.
Desenvolvimento
Este trabalho abordará dois programas distintos: LINGO e a ferramenta Solver do Microsoft Excel.
Lingo
O LINGO é um software que pode ser utilizado para resolver cálculos de problemas de otimização linear ou não-linear e analisar a solução.
Para que a explicação fique mais clara, tomemos um exemplo o seguinte problema de programação linear:
A partir de dois tipos de matéria-prima, uma empresa pode fabricar dois produtos diferentes X e Y. Cada unidade do produto X consome 2kg da matéria-prima A e 1kg da matéria-prima B. Cada unidade do produto Y consome 1kg de A e 2kg de B. Após fabricados, ambos têm o mesmo preço de venda R$1000,00 por unidade. Considerando que se dispõe de 10kg de A e 8kg de B para a fabricação dos produtos X e Y, determine a receita máxima que a fábrica pode ter com a fabricação e venda desses produtos.
Para começarmos, devemos abrir o LINGO. Assim que for inicializado, ele mostrará uma tela em branco, parecida com a da figura 1. 
Comandos
Menu
Modelo em Branco
Barra de Status
Figura 1:Tela Inicial do LINGO.
Como nosso problema de programação linear é de maximização, usaremos o comando MAX acompanhando a função objetivo. Caso contrário, se nosso problema fosse de minimização, o comando a acompanhar a função objetivo deveria ser o comando MIN.
Nas linhas abaixo são declaradas as restrições do problema. Não há necessidade de digitar END ao final do modelo. Para declarar que as variáveis são do tipo inteiro, devemos usar o comando @GIN(nome da variável). Os tipos de variáveis que podem ser usadas com o LINGO são apresentadas na tabela a seguir.
	COMANDO
	EXPLICAÇÃO
	@GIN(VAR)
	Usado para designar variáveis inteiras
	@BIN(VAR)
	Usado para designar variáveis binárias
	@FREE(VAR)
	Usado para designar que a variável é livre
	@BND(LI,VAR,LS)
	Usado para designar os valores pelos quais a variável VAR é limitada inferiormente e superiormente. Aqui temos que LI é valor mínimo da variável e LS é o valor máximo, ou seja, LI · VAR · LS.
Para resolver o problema, basta clicar no menu “LINGO” e logo em seguida em “SOLVE”, ou simplesmente clicar no botão “SOLVE” na barra de ferramentas. Se tudo estiver digitado corretamente, aparecerá uma janela como mostrada na figura 2.
Figura 2: Status da solução.
Clique no botão “Close” para fechar esta janela e aparecerá na tela uma janela com os resultados do problema obtidos pelo LINGO.
Figura 3: Relatório de solução.
Em um relatório de solução do LINGO você encontrará uma parte denominada reduced cost (custo reduzido) para cada variável do problema. Ela pode ser interpretada a quantia de penalidade (positiva ou negativa, dependendo do problema) que você teria que pagar para introduzir uma unidade daquela variável na solução.
Já a coluna slack or surplus, indica o excesso em restrições do tipo ≥ ou a folga em restrições do tipo ≤. 
A coluna dual price pode ser interpretada como a quantia pela qual a função objetivo melhoraria/pioraria quando o lado direito das restrições/constantes é aumentado/diminuído em uma unidade. Ele também pode ser entendido como o que estamos dispostos a pagar por unidades adicionais de um recurso. Por isto ele também é chamado de shadow price.
A coluna value apresenta os valores das variáveis para obter uma solução ótima.
 Excel
O Solver faz parte de um conjunto de programas, que geralmente são chamados de ferramentas de análise hipotética, ou seja, uma ferramenta que possibilita encontrar um valor ideal (otimizado) para uma determinada equação.
Para instalar o Solver siga os seguintes passos: 
1. Com o Excel aberto, clique no menu “Arquivo” e depois em “Opções”. Aparecerá uma tela parecida com a da figura 4.
Figura 4: Opções do Excel
 2. No menu lateral, clique em “Suplementos” e procure o Solver na lista de suplementos disponíveis, selecione-o conforme a figura a seguir e clique em “OK” para confirmar a instalação.
Figura 5: Suplementos
Para facilitar a visualização, tomemos como exemplo o seguinte exercício de programação linear:
A padaria Aurora confecciona biscoitos salgados e doces. O biscoito salgado dá um lucro de 400u.m por caixa e o biscoito doce 300u.m por caixa. Os biscoitos são processados em 3 operações principais: mistura, cozimento e embalagem. O tempo disponível para cada operação é de 7,4h, 13h e 4,5h, respectivamente. Para cada caixa de biscoito, os tempos necessários em cada operação é 15min, 20min e 5min, respectivamente, para o biscoito salgado e 15min, 20min e 3min, respectivamente, para o biscoito doce. A padaria pode fabricar no máximo 200 caixas de biscoitos, independentemente do tipo. Quantas caixas de cada tipo a padaria deve produzir para obter o maior lucro?
A modelagem desse problema fica da seguinte maneira:x: quantidade de biscoitos salgados a ser produzida	
y: quantidade de biscoitos doces a ser produzida
				
x e y ≥ 0
Na figura 6 temos nossa tabela montada no Excel.
Figura 6: Modelagem no Excel.
A montagem de um problema de otimização no Excel tem três partes: a célula de destino (fórmula da função objetivo), as células variáveis e as restrições. 
A célula de destino é a célula que representaa meta ou o objetivo que se deseja atingir. Esta célula deverá conter uma fórmula que represente a função objetivo do modelo proposto. No nosso caso, seria a célula G7. Para montar a função objetivo basta fazermos a multiplicação entre as células que conterão a quantidade de caixas de biscoitos salgados e doces vezes o seu respectivo preço, como mostra a figura 7.
Figura 7: Precedentes da célula G7.
As células variáveis poderão ser alteradas ou ajustadas a fim de atingir a otimização da célula de destino. A determinação destes valores está diretamente relacionada às restrições e/ou limitações do modelo. No nosso modelo, essas células são a E8 e F8.
As restrições representam os valores a que o modelo está limitado. Estes valores estão relacionados à quantidade de recursos disponíveis, por exemplo, matéria-prima e mão 3 de obra, sendo que não podemos produzir mais do que é demandado, portanto a demanda também pode ser um fator limitante do modelo. Nessas células, devemos montar uma fórmula para que ele altere de acordo com as alterações feitas nas células variáveis, como podemos observar nas figuras 8, 9 e 10.
Figura 8: Primeira restrição.
Figura 9: Segunda restrição.
Figura 10: Terceira restrição.
Depois de montar a tabela, deve-se executar o solver. Para isso, basta ir até o menu “Dados” e clicar no “Solver” no canto superior direito. Feito isso vamos inserir os parâmetros do problema para que o solver o resolva.
Primeiramente, define-se a célula objetivo, que é nossa célula G7. E, como o exemplo é um problema de maximização, seleciona-se Máx.
Em seguida, define-se quais são as células variáveis. Como dito anteriormente, essas células são a E8 e F8.
Depois, adiciona-se as restrições do problema. Para fazer isso, basta clicar em “Adicionar” e colocar da mesma forma que temos na modelagem do problema mostrada anteriormente. O valor de cada restrição deverá ser menor ou igual ao limite. Para a primeira restrição, tem-se o seguinte (figura 10):
Figura 11: Acionando as restrições.
Quando todas as restrições forem adicionadas, o quadro ficará assim (figura 12):
Figura 12: Parâmetros do Solver.
Caso as variáveis sejam negativas, basta desmarcar o quadro “Tornar Variáveis Irrestritas Não Negativas”.
Depois de clicar em “Resolver”, uma janela aparecerá. Basta clicar em “Ok” e o problema estará resolvido, como mostra a figura 13.
Figura 13: Problema resolvido.
Aplicações
 Problema de Minimização
Suponhamos que 8, 12 e 9 unidades de proteínas, carboidratos e gorduras, respectivamente, sejam as necessidades semanais mínimas para cada pessoa. O alimento A contém, por kg, 2, 6 e 1 unidade de proteínas, carboidratos e gorduras e o alimento B contém, por kg, 1, 1 e 3 unidades, respectivamente. Se A custa 3 unidades monetárias e B 2 unidades monetárias, quantos kg de cada um se deve adquirir por semana para se ter a dieta de menor custo? 
O modelo de decisão do problema é dado a seguir.
x: quantidade em kg de alimento A a ser adquirida
y: quantidade em kg de alimento B a ser adquirida
			
x ≥ 0 e y ≥ 0
Resolvendo com o LINGO, obtém-se:
Com o solver obtém-se:
 Problema de Maximização
Um fazendeiro dispõe de 200L de leite, 160h de mão de obra e 10L de coalho para produzir diariamente queijos do tipo A e B. Cada kg do queijo do tipo A necessita 10L de leite, 5h de mão de obra e 1L de coalho. Cada kg do queijo do tipo B requer 0,5L de coalho, 10h de mão de obra e 13L de leite. A demanda de área do queijo do tipo B nunca excede a do queijo do tipo A por mais de 2kg. Se o fazendeiro lucra R$0,20 com cada kg do queijo tipo A e R$0,50 com cada kg do queijo tipo B, otimize a produção de queijos do fazendeiro.
O modelo de decisão do problema é dado a seguir.
x: quantidade em kg de queijo do tipo A a ser produzida
y: quantidade em kg de queijo do tipo B a ser produzida
			
x ≥ 0 e y ≥ 0
Resolvendo com o LINGO obtém-se:
Com o solver obtém-se:
Conclusão
Os softwares de modelagem são ferramentas elaboradas com o intuito de reduzir o tempo gasto na resolução de problemas em diversas áreas, principalmente nas que dizem respeito à tomada de decisões com vistas à maximização de rendimento ou lucro e/ou à minimização de alguma variável envolvida no processo, como as perdas. No entanto, é preciso entender bem qual o problema a ser resolvido, qual o objetivo a ser alcançado, e quais as variáveis que interferem nesse processo. De posse dessas informações, basta o uso do software correto para obtenções de resultados.
Referências
JESUS, J.B.; FAVONI, C. I. O Uso Da Ferramenta Solver Do Excel Na Resolução De Problemas De Programação Linear. Disponível em: <http://www.pucrs.br/famat/viali/graduacao/producao/po_2/material/apostilas/Arigo_Solver.pdf>. Acesso em 8 de novembro de 2016.
Introdução à Programação Linear. Disponível em: <http://www.iepg.unifei.edu.br/edson/download/Engecon2/CAP5EE2PLapost.pdf>. Acesso em 8 de novembro de 2016.
JÚNIOR, A. C. G.; SOUZA, M. J. F. Lindo: Manual de Referência. Disponível em: <http://www.decom.ufop.br/marcone/Disciplinas/OtimizacaoCombinatoria/lindo_p.pdf>. Acesso em 8 de novembro de 2016.
SANTOS, M. P. Programação Linear. Disponível em: < http://mpsantos.com.br/plinear.pdf>. Acesso em 8 de novembro de 2016.