Pesquisa Operacional
na Tomada de Decisões
Resolvendo Programação Linear
Em um Microcomputador
2ª Edição
Capítulo 3.1_Apêndice_A
© Gerson Lachtermacher,2005
Conteúdos do Capítulo
 Programação Linear

Software Lindo
 Versão Windows e comandos
 Formulação do problema
 Solução do problema
 Reduced cost
 Sintaxe modelo
 Comandos opcionais
 File | Log output
 O Caso do Vendedor de Frutas
Capítulo 3.1_Apêndice_A
Programação Linear
Software Lindo
 Lindo (Linear Interactive Discrete Optimizer) é um
software interativo para resolução de problemas de
programação



Linear
Quadrática
Inteira
 Utilizado para resolução de problemas reais de mais de
10.000 variáveis, dispõe de características que mostram
os passos e quadros intermediários do método simplex
Capítulo 3.1_Apêndice_A
Software Lindo
Versão Windows
Capítulo 3.1_Apêndice_A
Lindo
Comandos
 Comandos



MAX - Inicia um problema de maximização
MIN - Inicia um problema de minimização
END - Termina a entrada de um problema
 Operadores




Menor
Maior
Menor ou igual
Maior ou igual
<
>
<=
>=
Capítulo 3.1_Apêndice_A
Lindo
Formulação de Problema
 A seguinte entrada é uma formulação válida de uma
problema
Max 2 x + 3 y
Max 2x + 3y
s.t.
4 x + 3 y < 10
s.t.
3x + 5 y < 12
x, y  0
Capítulo 3.1_Apêndice_A
4x + 3y < 10
3x + 5y < 12
END
Lindo
Formulação de Problema
 Solve
 Se a sintaxe não estiver correta, a seguinte mensagem
aparecerá:
 An error occured during compilation on line: n
Capítulo 3.1_Apêndice_A
Lindo
Solução do Problema
 Se nenhum erro
ocorrer durante a
compilação, a tela
ao lado aparecerá.
 Se a análise de
sensibilidade for
desejada responda
sim
Capítulo 3.1_Apêndice_A
Lindo
Solução do Problema
 Quando o problema estiver resolvido, uma janela
denominada Reports Window ou janela de relatórios
aparecerá automaticamente.
 Essa janela de relatórios é o lugar onde todos os
resultados serão lançados.
 Se dois problemas forem resolvidos e houver espaço na
janela, suas resoluções aparecerão uma seguida da outra
 Para se examinar essa janela basta clicar no menu
Windows|Reports Windows (ver slide a seguir)
Capítulo 3.1_Apêndice_A
Lindo
Solução do Problema
Capítulo 3.1_Apêndice_A
Lindo
Solução do Problema
 Valor Ótimo da FunçãoObjetivo
 Valor das Variáveis
Originais
 Valor das Variáveis de
Folga ou Excesso
Capítulo 3.1_Apêndice_A
Solução do Problema
Reduced Cost
 Existem duas interpretações
para o Reduced Cost:
 A quantidade que o
coeficiente da função
objetiva de uma variável
original deve melhorar
antes desta variável se
tornar básica.
 A quantidade de
penalização deverá ser
paga se quisermos tornar
uma variável básica
Capítulo 3.1_Apêndice_A
Solução do Problema
Reduced Cost
 Existem duas interpretações
para os Dual Prices:
 A quantidade pela qual a
função objetiva será
melhorada dado um
incremento de uma
unidade na constante de
uma restrição
 Quanto estaríamos
dispostos a pagar por uma
unidade adicional de um
recurso
Capítulo 3.1_Apêndice_A
Lindo
Sintaxe Modelo
 A função objetivo deve sempre aparecer no começo do
modelo e deve ser iniciada pelo comando MAX ou
MIN.
 O fim da função objetivo é definido através de uma das
seguintes expressões:



SUBJECT TO
S.T.
ST
Capítulo 3.1_Apêndice_A
Lindo
Sintaxe Modelo
 O final das restrições é determinada pelo comando
END.
 O Comando END só é obrigatório se após as restrições
aparecerem comandos do tipo GIN ou INT discutidos
mais tarde
 O nome de uma variável no LINDO pode conter até 8
caracteres


Começar por uma letra
Não conter um dos seguintes caracteres:
 ! )+ - = < >
Capítulo 3.1_Apêndice_A
Lindo
Sintaxe Modelo
 Opcionalmente podemos nomear as restrições de um
modelo. O nome das restrições seguem as mesmas
convenções dos nomes das variáveis
 Para nomear uma restrição, inclua o nome, um
parêntese, e a própria restrição em seguida

Exemplo: NOME) 2x + 4y <= 10
Capítulo 3.1_Apêndice_A
Lindo
Sintaxe Modelo
 O LINDO não aceita parêntesis ( ) como indicadores de
preferência de ordem de precedência. Todas as
operações são executadas da esquerda para a direita.
 Somente constantes (não variáveis) são permitidas do
lado direito das restrições.
 Somente variáveis e seus coeficientes (não constantes)
podem ser colocados do lado esquerdo das restrições.
Capítulo 3.1_Apêndice_A
Lindo
Comandos Opcionais
 Os comandos adicionais abaixo são colocados após o
comando END ao final das restrições.
 FREE <Variável> - Remove os limites de não
negatividade imposta a todas as variáveis por default.
 GIN <Variável> - Faz a <Variável> uma variável
inteira geral.
 INT <Variável> - Faz a <Variável> uma variável
inteira binária.
Capítulo 3.1_Apêndice_A
Lindo
File|Log Output
 Esse comando serve para se criar um arquivo contendo
todos os resultados colocados na tela de resultados.
 O comando é do tipo liga/desliga, isto é, a primeira vez,
abre um arquivo (ativa o comando) e a segunda fecha
este arquivo.
 Um símbolo de check é colocado ao lado do menu do
comando enquanto este estiver ativado
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
 Um vendedor de frutas pode transportar 800 caixas de
frutas para sua região de vendas. Ele necessita
transportar pelo menos 200 caixas de laranja e pelo
menos 100 caixas de pêssegos e no máximo 200 caixas
de tangerinas O vendedor obtêm um lucro por caixa de
20, 10 e 30 reais para laranjas, pêssegos e tangerina,
respectivamente. De que forma ele deverá carregar o
caminhão para obter o lucro máximo?
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
 Hipóteses

Tudo o que o vendedor levar será vendido.

Nada estragará no caminho
 Função-objetivo

Maximizar o lucro

Max 20x1 + 10x2 + 30x3
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
 Restrições de venda



Laranjas: x1 > 200
Pêssegos: x2 > 100
Tangerinas: x3 < 200
 Restrição de Transporte

x1 + x2 + x3 < 800
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
Max 20 x1 + 10 x 2 + 30 x 3
s.r.
x1 + x 2 + x 3  800
x1  200
x 2  100
x 3  200
x1 , x 2 , x 3  0
 Este problema está na forma não padrão.
 Resolveremos usando o Lindo.
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apêndice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apêndice_A
Teorema da Dualidade
Exemplo
 Encontrar a solução do problema abaixo com a ajuda do
Lindo.
Max Z  3 x1 + 2 x2 + x3 + 6 x4 + 5 x5 + 4 x6
s.r. x1 + x2 + x3  10
x4 + x5 + x6  15
3 x1 + 2 x2 + x4 + 3 x5  20
x2 + x3 + 2 x4 + x6  30
x1 , x2 , x3  0
x4 , x5 , x6 sem restrições de sinal
Capítulo 3.1_Apêndice_A
O Problema no Lindo
 As três variáveis não tem restrições de sinal
Capítulo 3.1_Apêndice_A
A Solução do Primal
Capítulo 3.1_Apêndice_A
Vamos Agora usar o Lindo para
Obter a Solução do Dual
 As duas primeiras restrições do Primal são igualdades
Capítulo 3.1_Apêndice_A
Solução do Dual
 A função-objetivo
do Dual assume na
solução ótima o
mesmo valor da
função-objetiva do
Primal
Capítulo 3.1_Apêndice_A