Pesquisa Operacional
na Tomada de Decisões
Resolvendo Programação Linear
Em um Microcomputador
Capítulo 3.1_Apendice_A
Conteúdos da Seção
 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_Apendice_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_Apendice_A
Software Lindo
Versão Windows
Capítulo 3.1_Apendice_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_Apendice_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_Apendice_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_Apendice_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_Apendice_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_Apendice_A
Lindo
Solução do Problema
Capítulo 3.1_Apendice_A
Lindo
Solução do Problema
 Valor Ótimo da Função
Objetivo
 Valor das Variáveis Originais
 Valor das Variáveis de Folga
ou Excesso
Capítulo 3.1_Apendice_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_Apendice_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_Apendice_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_Apendice_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_Apendice_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_Apendice_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_Apendice_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_Apendice_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_Apendice_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_Apendice_A
O Caso do Vendedor de Frutas
 Hipóteses

Tudo o que o vendedor levar será vendido.

Nada estragará no caminho
 Função-Objetiva

Maximizar o lucro

Max 20x1 + 10x2 + 30x3
Capítulo 3.1_Apendice_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_Apendice_A
O Caso do Vendedor de Frutas
Max20 x1 + 10 x2 + 30 x3
s.r.
x1 + x2 + x3  800
x1  200
x2  100
x3  200
x1 , x2 , x3  0
 Este problema está visivelmente em forma não
padrão. Resolveremos usando o Lindo.
Capítulo 3.1_Apendice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apendice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apendice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apendice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apendice_A
O Caso do Vendedor de Frutas
Resolvendo Usando o Lindo
Capítulo 3.1_Apendice_A
 Vamos verificar a solução do problema abaixo com a ajuda do
Lindo, como já fizemos com o Excel na seção anterior:
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_Apendice_A
O Problema no Lindo
 Variáveis sem restrições de sinal
Capítulo 3.1_Apendice_A
Solução
Capítulo 3.1_Apendice_A