programação linear 3

Prévia do material em texto

CAP. 5 - INTRODUÇÃO A PROGRAMAÇÃO 
LINEAR 
 
1. GENERALIDADES 
Sem dúvida nenhuma a Programação Linear é uma das técnicas da Pesquisa Operacional das mais 
utilizadas em se tratando de problemas de otimização. 
Os problemas de Programação Linear (PL) buscam a distribuição eficiente de recursos limitados 
para atender um determinado objetivo, em geral, maximizar lucros ou minimizar custos. Em se 
tratando de PL, esse objetivo é expresso através de uma função linear, denominada de "Função 
Objetivo". 
É necessário também que se defina quais as atividades que consomem recursos e em que 
proporções os mesmos são consumidos. Essas informações são apresentadas em forma de 
equações as inequações lineares, uma para cada recurso. Ao conjunto dessas equações e/ou 
inequações, denomina-se "Restrições do Modelo". 
Normalmente se tem inúmeras maneiras de distribuir os recursos escassos entre as diversas 
atividades em estudo, 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, isto é, a 
maximização do lucro ou a minimização dos custos. A essa solução dá-se o nome de solução ótima. 
Assim, a Programação linear se incube de achar a solução ótima de um problema, uma vez definida 
o modelo linear, ou seja, a função objetivo e as restrições lineares. 
 
2. PROBLEMAS DE PROGRAMAÇÃO LINEAR 
Como foi dito anteriormente, está-se diante de um problema de PL quando os problemas práticos 
que se pretende resolver pode ser escrito de forma de maximização (ou minimização) de uma função 
objetivo linear, sujeita a um conjunto de restrições que podem ser expressos sob a forma de 
inequações ou equações lineares. 
 
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 2 
 
Exemplos de problemas que podem ser resolvidos por 
programação linear: 
a) Um fabricante está iniciando a última semana de produção de quatro diferentes modelos de 
consoles em madeira para aparelhos de televisão, designados respectivamente, I, II, III e IV. Cada 
um deles deve ser montado e em seguida decorado. Os modelos necessitam, respectivamente de 4, 
5, 3 e 5 horas para montagem e de 2, 1, 5, 3 e 3 horas para decoração. Os lucros sobre as vendas 
dos modelos são respectivamente 7, 7, 6 e 9 reais. O fabricante dispõe de 30.000 horas para a 
montagem destes produtos (750 montadores trabalhando 40 horas por semana) e de 20.000 horas 
para decoração (500 decoradores trabalhando 40 horas por semana). Quanto de cada um dos 
modelos deve ser produzido durante esta última semana a fim de maximizar o lucro? Admita que 
todas as unidades possam ser vendidas. 
 
b) Seja o caso de um investidor que, dispondo de $6000 esteja contemplando a possibilidade de 
compra de dois seguintes tipos de ações: 
? Tipo 1 - preço unitário de compra de $ 5,00 e rentabilidade anual esperada de 30%. 
? Tipo 2 - preço unitário de compra de $ 3,00 e rentabilidade anual estimada em 35%. 
Supondo que o investidor não deseje adquirir mais do que 1750 ações, e que seu corretor só possa 
conseguir 1000 ações do tipo 1 e 1500 ações do tipo 2, que quantidades deve comprar de cada 
tipo de ação, na hipótese de que seja seu objetivo maximizar o total de capital no fim de um ano? 
 
c) Uma empresa esta analisando um conjunto de alternativas de projetos de investimentos 
disponíveis e apresentados na tabela seguir. 
 
Projeto Investimento no 
ano 1 
Investimento no 
ano 2 
Vida útil Economia anual 
nos próximos 3 
anos 
1 12 3 5 anos 9.29 
2 54 7 5 anos 26.85 
3 6 6 5 anos 9.88 
4 6 2 5 anos 7.92 
5 30 35 5 anos 35.33 
6 6 6 5 anos 8.14 
7 48 4 5 anos 22.78 
8 36 3 5 anos 16.91 
9 18 2 5 anos 11.04 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 3 
 
 
O orçamento para investimento é de 50 para o primeiro ano e 20 para o segundo. Sabendo-se que 
a TMA da empresa é de 10% a.a., qual a combinação ótima desses projetos. 
 
3. OBTENDO FUNÇÃO OBJETIVO E AS RESTRIÇÕES 
Antes de discutir as técnicas possíveis para obtenção de resultados, através de um problema será 
discutido como obter a função objetivo e as restrições. 
 
Exemplo para discutir a obtenção da função objetivo e as 
restrições: 
Giapetto fabrica dois tipos de brinquedos de madeira: soldados e trens. Um soldado é vendido por 
$27 e usa $10 de matéria prima. Cada soldado que é fabricado tem um custo adicional de $14 
relativo a mão de obra. Um trem é vendido por $21 e gasta $9 de matéria prima. O custo de mão 
de obra adicional para cada trem é de $10. A fabricação destes brinquedos requer dois tipos de 
mão de obra: carpintaria e acabamento. Um soldado necessita de 2 horas para acabamento e 1 de 
carpintaria. Um trem necessita de 1 hora para acabamento e 1 hora de carpintaria. Cada semana, 
Giapetto pode obter qualquer quantidade de matéria prima, mas tem a disposição até 100 horas de 
acabamento e 80 de carpintaria. A demanda por trens é ilimitada, mas a venda de soldados é de no 
máximo 40 por semana. Giapetto quer maximizar seu lucro diário (receitas-custos). Formular o 
modelo matemático que poderá ser usado por Giapetto para maximizar seu lucro semanal. 
Solução: 
Sabendo que a matéria prima
necessária é obtida sem problemas,
Giapetto tem como objetivo
maximizar o lucro semanal (receitas -
custos).
Vamos então formular
matematicamente a situação de
Giapetto com o objetivo de maximizar
o lucro semanal.
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 4 
 
Primeiro ponto importante:
Variáveis de decisão
Em qualquer modelo de PL, as variáveis
de decisão devem descrever
completamente as decisões a serem
feitas.
Caso de Giapetto: quantos soldados e trens
devem ser feitos na semana.
 
 
Variáveis de decisão
• X1 = número de soldados produzidos
cada semana;
• X2 = número de trens produzidos a cada
semana.
 
 
Segundo ponto importante:
Função objetivo
Em qualquer modelo de PL, o decisor
quer maximizar ou minimizar alguma
função das variáveis de decisão.
Caso de Giapetto: custos fixos (aluguel,
seguro) não depende dos valores de X1
e X2, assim ele pode se concentrar em
maximizar a venda da semana.
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 5 
 
Receitas e custos: podem ser expressos em
termos das variáveis X1 e X2. Seria tolice
Giapetto produzir mais soldados que ele possa
vender, assim assumimos que todos
brinquedos produzidos podem ser vendidos.
Assim:
Receita da semana = receita dos soldados +
receita dos trens
Receita da semana = $/soldado * soldado/semana + $/trem * trem/semana
Receita por semana = 27*X1 + 21*X2
 
 
Também podemos escrever:
• Custos de M.P. = 10*X1 + 9*X2
• Custos de M.O. = 14*X1 + 10*X2
Então Giapetto quer maximizar:
(27X1 + 21X2) - (10X1 + 9X2) - (14X1 + 10 X2) = 3X1 + 2X2
Assim o objetivo de Giapetto é escolher X1 e X2 para 
maximizar 3X1 + 2X2
 
Objetivo:
maximizar Z = 3X1 + 2X2
ou
max Z = 3X1 + 2X2
Variável
usualmente
utilizada
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 6 
 
Terceiro ponto importante:
restrições
Se X1 e X2 aumentam, a função objetivo de
Giapetto será sempre maior. Mas infelizmente X1
e X2 são limitados pelas seguintes restrições:
• 1 - cada semana, não mais que 100 horas de
acabamento;
• 2 - cada semana, não mais de 80 horas de
carpintaria;
• 3 - limitação de demanda, não mais de 40
soldados por semana.
 
 
M.P. ilimitada, portanto não há
restrições. Como, próximo
passo, é necessário expressar as
restrições 1, 2 e 3, em termo das
variáveis de decisão: X1 eX2.
 
 
Restrição 1:
não mais de 100 h de acabamento
Total de h de acab./semana = horas de aca./sold. * sold. feitos/semana +horas de acab./trem * trens feitos/semana
Total de h de acab./semana = 2*X1 + 1*X2
Restrição 1 - 2X1 + X2 <= 100
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 7 
 
Restrição 2:
não mais de 80 h de carpintaria
Total de h de carp./semana = horas de carp./sold. * sold. feitos/semana + 
horas de carp./trem * trens feitos/semana
Total de h de carp./semana = 1*X1 + 1*X2
Restrição 2 - 1X1 + X2 <= 80
 
 
Restrição 3:
venda máxima de soldados: 40
Restrição 3 - X1 <= 40
 
 
Restrições:Restrições:
• 1 - 2X1 + X2 <= 100
• 2 - X1 + X2 <= 80
• 3 - X1 <= 40
Restrições para o
problema de PL
de Giapetto
Usualmente
representam a
quantidade de
recursos
disponíveis.
Coeficientes 
tecnológicos:
refletem a quantia
usada para
diferentes produtos.
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 8 
 
Quarto ponto importante:
Restrições adicionais
Para completar a formulação do problema:
• X1 >= 0
• X2 >= 0
 
 
Resumindo
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 <= 100 (2)
• X1 + X2 <= 80 (3)
• X1<= 40 (4)
• X1 >= 0 (5)
• X2 >= 0 (6)
Significa que
X1 e X2 
precisam satisfazer
todas as restrições P.L. - todos os
termos X são de
expoente 1 e as
restrições são
inequações
lineares
O problema de Giapetto
é tipico de muitos outros,
onde precisa-se
maximizar lucros
sujeitos a recursos
limitados
 
 
 
4. SOLUÇÃO DE UM PROBLEMA DE P.L. - MÉTODO 
GRÁFICO 
Um problema de P.L. só pode ser resolvido graficamente desde que o modelo, em estudo, 
apresentar duas variáveis. 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 9 
 
O fato de que a função objetivo
para um PL precisar ser uma
função linear de variáveis tem
2 implicações:
• 1 - A contribuição para a função objetivo
de cada variável de decisão é proporcinal
ao valor da variável de decisão;
• 2 - A contribuição para a função objetivo
para cada variável é independente dos
valores de outras variáveis de decisão.
 
 
Definição: região de solução
- para um problema de PL é
o conjunto de todos os
pontos que satisfazem todas
as restrições do problema.
 
 
Restrições:
• 2X1 + X2 <= 100 (2), ok 2*40+20<=100
• X1 + X2 <= 80 (3), ok 40+20<=80
• X1<= 40 (4), ok 40<=40
• X1 >= 0 (5), ok 40>=0
• X2 >= 0 (6), ok 20>=0
Giapetto: X1 = 40 X2 = 20 região de solução
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 10 
 
Giapetto: X1 = 15 X2 = 70 não é região de solução
Restrições:
• 2X1 + X2 <= 100 (2), ok 2*15+70<=100
• X1 + X2 <= 80 (3), não ok 15+70> 80
• X1<= 40 (4), ok 15<=40
• X1 >= 0 (5), ok 15>=0
• X2 >= 0 (6), ok 70>=0
 
 
região de solução
Pontos que atendem e onde será procurada
a solução ótima
Solução ótima
Ponto da região de solução, que leva ao maior
valor da função objetivo.
 
 
• A maioria dos problemas de PL, tem
somente uma solução ótima;
• Alguns não tem solução ótima;
• Alguns tem infinitas soluções.
Para o problema de Giapetto, solução ótima:
X1=20 e X2 = 60
Z = 3*20 +2*60 = 180
lucro = 180 - 100 = 80/semana
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 11 
 
Solução gráfica para o
problema de 2 variáveis
Um PL com 2 variáveis
pode ser resolvido
graficamente. Nós sempre
nomeamos as variáveis X1
e X2 e os eixos
coordenados por X1 e X2.
 
 
 
Se nós queremos delimitar em
um gráfico o conjunto de
pontos que satisfaça a:
2X1+3X2 <= 6 (1)
3X2 <= 6 - 2X1
X2<=1/3*(6 - 2X1) = 2 - 2/3X1 (2)
 
 
 
O conjunto de pontos que satisfaz (1) e 
(2) cai sobre a reta ou abaixo dela
X2
X11
2
3
4
5
6
1 2 3 4 5 6
X2 = 2 - 2/3X1
Região onde:
2X1+3X2<=6
Região onde:
2X1+3X2>=6
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 12 
 
A solução gráfica para o problema de Giapetto é a seguinte: 
Encontrando a região de solução
do problema de Giapetto:
• 2X1 + X2 <= 100 (2)
• X1 + X2 <= 80 (3)
• X1<= 40 (4)
• X1 >= 0 (5)
• X2 >= 0 (6)
Para um 
ponto (X1, X2)
pertencer a região de
solução é preciso
satisfazer todas
estas inequações.
(5) e (6) indicam o primeiro quadrante
 
 
X2
X120
40
60
80
100
120
20 40 60 80 100 120
(2)
(3)
(4)
A
B
C
D
E
F
G
H
Poligono DGFEH - região de solução
 
 
Encontrando a solução ótima
Após a identificação da região de
solução, nós devemos procurar a
solução ótima, que será o ponto da
região que levar ao maior valor de
Z = 3X1+2X2
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 13 
 
Para encontrar a solução ótima, nós
precisamos desenhar uma linha sobra
a qual todos os pontos levem ao mesmo
valor de Z.
Escolhe-se qualquer ponto da região de
solução:
(20, 0) - Z = 3X1+2X2 = 60
Assim (20, 0) cai sobre a reta:
Z = 3X1 + 2X2 = 60
X2 = 30 - 3/2X1
 
 
3X1 + 2X2 = 60
tem coeficiente angular = -3/2
Assim todas as retas 3X1+2X2 =
constante terão o mesmo coeficiente
angular.
Importante: uma vez desenhada a reta, 
podemos encontrar
todas as outras pelo movimento paralelo da reta
que desenhamos.
 
 
X2
X120
40
60
80
100
120
20 40 60 80 100 120
(4)(2)
(3)
A
B
C
D
E
F
G
H
X2 = 30 - 3/2 X1
Indica o ponto ótimo - G (20, 60)
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 14 
 
Ponto ótimo:
Z = 3*20 + 2*60 = 180
 
 
 
5. PROBLEMAS INTERESSANTES QUE PODEM SER 
FORMULADOS PARA SEREM RESOLVIDOS POR 
PROGRAMAÇÃO LINEAR 
 
O que será visto a seguir é a formulação de vários problemas complicados da Programação Linear. 
O passo mais importante na formulação de um modelo é a escolha apropriada das variáveis de 
decisão. Se as variáveis de decisão forem selecionadas adequadamente, a função objetivo e as 
restrições devem ser obtidas sem muita dificuldade. Problemas na determinação da função objetivo 
e restrições normalmente são devido a uma escolha incorreta das variáveis de decisão. 
 
5.1 Exemplo 1: Problema de orçamento de capital 
Uma empresa de petróleo esta considerando 5 diferentes oportunidades de investimento. O fluxo de 
caixa e valor presente (em milhões de reais) é dado na tabela a seguir. 
A empresa tem no momento $ 40 milhões para investir; e estima-se que no primeiro ano estarão 
disponíveis $ 20 milhões para investimento. A empresa pode comprar qualquer fração de cada 
investimento. Neste caso, o fluxo de caixa e valor presente são ajustados de acordo com a 
proporção do investimento realizado. Por exemplo, se a empresa comprar 1/5 do investimento 3, 
então o pagamento necessário será de 1/5 ($5) = $1 nos tempos 0 e 1. O valor presente do 
investimento 3 será de 1/5 (16) = $3.2 milhões. A empresa quer maximizar o valor presente que 
pode ser obtido pelos investimentos realizados entre as opções 1 a 5. Formular o problema para 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 15 
 
atingir este objetivo. Assumir que qualquer fundo não usado no instante 0 não poderá ser usado no 
primeiro ano (instante 1). 
 
 Inv. 1 Inv. 2 Inv. 3 Inv. 4 Inv. 5 
Desembolso 
instante 0 
11 53 5 5 29 
Desembolso 
instante 1 
3 6 5 1 34 
Valor presente 13 16 16 14 39 
 
 
5.2 Exemplo 2: planejamento financeiro de curto prazo 
Uma empresa eletrônica que fabrica gravadores e rádios têm seus custos de mão de obra, matéria 
prima e preço de venda de cada produto discriminados na tabelaa seguir. 
 
 Gravador Rádio 
Preço de venda 100 90 
Mão de obra 50 35 
Custo matéria prima 30 40 
 
Em primeiro de dezembro de 98, a empresa terá matéria prima que é suficiente para fabricar 100 
gravadores e 100 rádios. Na mesma data, o balancete previsto da empresa é o mostrado a seguir, e 
a razão entre ativo circulante e as suas obrigações (dívida com banco) será 2 (20000/10000). 
 Ativo circulante Obrigações 
Caixa 10000 
Contas a receber 3000 
Estoques 7000 
Dívidas em bancos 10000 
 
A empresa precisa determinar quantos gravadores e rádios deverão produzidos em Dezembro. A 
demanda é alta o suficiente para garantir que todos os produtos fabricados serão vendidos. Todas 
as vendas são feitas a crédito, pagamentos por produtos fabricados em Dezembro não serão 
recebidos até primeiro de Fevereiro de 99. Durante Dezembro, a empresa irá receber $2000 e 
precisará pagar $1000 devido ao empréstimo bancário e $1000 referente ao seu aluguel. Em 
primeiro de janeiro de 99, a empresa receberá um carregamento de matéria prima no valor de 
$2000, que será pago em Fevereiro de 99. A gerência decidiu que em primeiro de janeiro de 99 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 16 
 
precisa ter pelo menos $4000 em caixa. Também o banco exige que a razão entre dinheiro 
disponível e financiamento seja de pelo menos 2. Para maximizar o lucro da produção em 
Dezembro, o que deveria empresa produzir durante este mês? 
 
5.3 Exemplo 3: Modelos de financiamento multi período 
O exemplo a seguir ilustra como a programação linear pode ser usada para problemas de 
gerenciamento de fluxo de caixa. A chave é determinar as relações de dinheiro nas mãos durante 
diferentes períodos. 
 
Uma empresa de investimentos precisa determinar a estratégia de investimento para os próximos 3 
anos. Atualmente a empresa tem $100.000 disponível para investir. Os investimentos A, B, C, D e 
E estão disponíveis. O fluxo de caixa associado com investir $1 em cada opção é dado na tabela a 
seguir. 
 
 0 1 2 3 
A -$1 $0.50 $1 $0 
B $0 -$1 $0.50 $1 
C -$1 $1.2 $0 $0 
D -$1 $0 $0 $1.9 
E $0 $0 -$1 $1.5 
 
Por exemplo, 1$ investido na opção B requer um pagamento de $1 no ano 1 e retorna $0.50 no 
ano 2 e $1 no ano 3. Para assegurar que o portifólio da empresa seja diversificado, a política da 
empresa é a de aplicar até $ 75.000 em um único investimento. Adicionalmente aos investimentos 
A-E, a empresa pode obter taxas de 8% ao ano mantendo o dinheiro não investido em fundos do 
mercado. Ganhos dos investimentos podem ser imediatamente reinvestidos. Por exemplo, o dinheiro 
recebido no ano 1 do investimento C pode ser imediatamente reinvestido na opção B. A empresa 
tem como diretriz não emprestar dinheiro de fundos, assim o dinheiro disponível para investimento a 
qualquer tempo é limitado ao disponível. Formular a programação linear que maximiza o dinheiro em 
mãos no ano 3. 
 
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 17 
 
 
6. SOLUÇÃO DE PROBLEMAS DE P.L. - MÉTODO SIMPLEX 
Nas formulações anteriores, problemas com mais de 2 variáveis não poderiam ser solucionados com 
o método gráfico. Desta forma é necessário o estudo de outro procedimento para a busca de 
soluções. 
Agora, será apresentado mais um procedimento geral para resolução de problemas de programação 
linear, denominado "Método Simplex" e que foi desenvolvido em1947 por George B. Dantzig. 
O método simplex é um método interativo (algoritmo) utilizado para achar, algebricamente, a 
solução ótima de um problema de P.L.. 
 
6.1 Teoremas Básicos 
Teorema 1 - O conjunto de todas as soluções compatíveis do modelo de programação linear é um 
conjunto convexo cujos vértices (pontos extremos) correspondem a soluções básicas viáveis. 
Teorema 2 - Se a função objetiva possui um máximo (mínimo) finito, então pelo menos uma solução 
ótima é um ponto extremo do conjunto convexo do teorema1. 
 
6.2 Procedimentos do Método Simplex 
Supondo o seguinte problema para maximização: 
Max z = 5X1 + 2X2 
Sujeito a: 
X1 ? 3 
X2 ? 4 
X1 + 2X2 ? 9 
X1, X2 ? 0 
 
A solução gráfica do problema é a seguinte: 
 
 
 
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 18 
 
 
 
 
 
 
 
 
 
 
 
Sabe-se que a solução ótima do modelo é uma solução compatível básica do sistema, ou seja, um 
ponto extremo do polígono A,B,C,D,E. 
O método simplex, para ser iniciado, necessita conhecer uma solução compatível básica (solução 
inicial) do sistema, isto é, um dos pontos A,B,C,D,E do trapézio. Suponha-se que essa solução seja 
o ponto A. 
O método simplex verifica se a presente solução é ótima. Se for o processo está encerrado. Se não 
for ótima, é porque um dos pontos adjacentes fornece um valor maior que o ponto A. 
Neste caso, o método simplex faz então a mudança do ponto A para o ponto extremo adjacente 
que mais aumente o valor da função objetivo. No caso o ponto B. 
Agora, tudo que foi feito para o ponto extremo A é feito para o ponto extremo B. O processo 
finaliza quando se obtém um ponto extremo onde todos os pontos extremos a ele adjacentes, 
fornecem valores menores que a função objetivo. 
Como fazer, algebricamente, a mudança de um ponto extremo para outro, a ele adjacente? 
Achar, portanto, a próxima solução básica (ponto extremo adjacente) exige a escolha de uma 
variável básica para deixar a base atual, tornando-se não básica, e a escolha de uma variável não 
básica para entrar na base em sua substituição. 
 
O método simplex compreenderá, portanto, os seguintes passos: 
 
1. Achar uma solução compatível básica inicial. 
2. Verificar se a solução atual é ótima. Se for, pare. Caso contrário siga para o passo III. 
Pontos extremos 
X2 
X1 
E(0, 4) 
D(1, 4) 
C(3, 3) 
A(0, 0) 
B(3, 0) A B C D E 
Z 
ZB = 15 
ZE = 8 
ZD = 13 
ZB = 15 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 19 
 
3. Determinar a variável não-básica que deve entrar na base. 
4. Determinar a variável básica que deve sair da base. 
5. Achar a nova solução compatível básica, e voltar ao passo II 
 
6.3 O Método Simplex 
A seguir será mostrado passo a passo o método simplex. 
 
Definição Geral de Programação Linear: 
Maximizar ou Minimizar Z = C 1X 1 + C2 X2 + .... + Cn Xn 
sujeito a: 
a11X1 + a12X1 + ..........+ a1nXn (? ou = ou ? ) b1 
a21X1 + a22X1 + ..........+ a2nXn (? ou = ou ? ) b2 
a31X1 + a32X1 + ..........+ a3nXn (? ou = ou ? ) b3 
 
am1X1 + am2X1 + ..........+ amnXn (? ou = ou ? ) bm 
 
X1, X2, X3, Xn ? 0 
 
O Método Simplex é aplicado diretamente quando: 
 
1. todas as restrições são ? bi 
2. todos os bi ? 0 
3. se quer maximizar Z 
 
Quando uma dessas condições não é atendida estamos em presença de um caso particular. 
O Método Simplex será estudado, acompanhando a seguinte formulação: 
 
Maximizar Z = 3x1 + 2x2 + 5x3 
Sujeito a 
x1+ 2x2 + x3 ? 430 
3x1 + 2x3 ? 460 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 20 
 
xl + 4x2 ? 420 
x1, x2, x3 ? 0 
 
Primeiro passo: Transformar o sistema de M desigualdades lineares restritivas em um sistema de M 
equações lineares. 
Para isso adiciona-se a cada uma das desigualdades uma variável não-negativa chamada “Variável 
de Folga". 
Obs: Tem-se tantas variáveis de folga quantos forem as restrições. 
 
Representação das Folgas = xn+1 , xn+2 , ... , xn+m. 
Assim temos: 
x1+ 2x2 + x3 + x4 = 430 
3x1 + 2x3 + x5 = 460 
xl + 4x2 + x6 = 420 
 
Segundo passo: Colocar as equações em forma de tabela 
Z - 3x1 - 2x2 - 5x3 = 0x1+ 2x2 + x3 + x4 = 430 
 3x1 +2x3 + x5 = 460 
 xl + 4x2 + x6 = 420 
 
Terceiro passo: Determinar uma solução inicial viável. 
Pode ser demonstrado que a solução ótima de um problema de programação linear é uma solução 
básica. Una solução básica para um sistema de M equações e N incógnitas. 
Possui M variáveis diferentes de O (zero) e (N - M) variáveis iguais a 0 (zero). As variáveis 
diferentes de 0 (zero) são chamadas "Variáveis Básicas" e aquelas iguais a 0 (zero) são as "Variáveis 
Não Básicas". 
No Método Simplex escolhe-se como variáveis básicas aquelas em cuja coluna aparece um valor 
igual a 1 e os demais iguais a 0 (zero). 
 
Quarto passo: verificar se a solução é ótima. 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 21 
 
Examinar os valores dos coeficientes das Variáveis não básicas na la linha (no exemplo, linha de Z) e 
concluir: 
a. Se todos os valores forem positivos a solução é ótima e única. 
b. Se aparecerem valores positivos e alguns nulos a solução é ótima mas não única. 
c. Se aparecer algum valor negativo a solução não é ótima. Deve-se, então executar o 5o passo. 
Como pode se verificar na tabela a seguir, existem números negativos na primeira linha, assim a 
solução não é ótima, e precisa-se continuar os passos do método. 
 
Base z X1 X2 X3 X4 X5 X6 b bi/aie equac. 
Z 1 -3 -2 -5 0 0 0 0 0 
X4 0 1 2 1 1 0 0 430 430 1 
X5 0 3 0 2 0 1 0 460 230 2 
X6 0 1 4 0 0 0 1 420 ind. 3 
 
 
Quinto passo: Determinar a variável que entra (xe ) 
A variável que entra deve satisfazer as seguintes condições: 
- ser igual a 0 (zero) na solução atual (ou seja deve ser não básica) 
- ter coeficiente menor ou igual a 0 (zero) na linha de Z (na la linha) 
- possuir em sua coluna, pelo menos um coeficiente positivo. Escolher para entrar na base aquela 
que apresentar, na linha de Z, o coeficiente negativo de maior valor absoluto. Marcar a coluna na 
tabela. 
 
Sexto passo: Determinar a variável que sai (xs). 
Calcula-se o valor de bi/aie para cada linha da tabela e escolhe-se para sair a variável para a qual o 
quociente tiver o menor valor não negativo. 
Marcar na matriz a linha de xs. O quinto e sexto passos podem ser vistos nesta tabela: 
 
 
 
 
 
Base z X1 X2 X3 X4 X5 X6 b bi/aie equac. 
Z 1 -3 -2 -5 0 0 0 0 0 
X4 0 1 2 1 1 0 0 430 430 1 
entra 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 22 
 
X5 0 3 0 2 0 1 0 460 230 2 
X6 0 1 4 0 0 0 1 420 ind. 3 
 
 
 
Sétimo passo: Calcular a nova matriz de coeficientes, executando as operações convenientes nas 
linhas da matriz. 
Os coeficientes da nova matriz podem ser calculados da seguinte maneira: 
 
10 - Dividir todos os elementos da linha marcada pelo pivô (esta linha não muda mais). 
20 - Multiplicar a linha marcada pelo fator Fi= aie / ase 
Subtrair a linha i da matriz, da linha marcada e multiplicada pelo fator Fi. 
30 - Substituir na coluna base a variável que sai pela variável que entra. 
O resultado destas operações na tabela anterior resulta em: 
 
 
 
Base z X1 X2 X3 X4 X5 X6 b bi/aie equac. 
Z 1 4.5 -2 0 0 2.5 0 1150 0 
X4 0 -0.5 2 0 1 -0.5 0 200 100 1 
X3 0 1.5 0 1 0 0.5 0 230 ind. 2 
X6 0 1 4 0 0 0 1 420 105 3 
 
 
Como na primeira linha da coluna de X2 aparece um número negativo, a solução ainda não é a 
ótima. 
 
Oitavo passo: Repetir todos os passos, do 40 ao 70, tantas vezes quanto forem necessárias, até que 
a solução ótima seja encontrada. O resultado final da tabela anterior aparece na próxima iteração, e 
como não existem mais números negativos na primeira linha a solução é ótima. O resultado é 
mostrado a seguir. 
Base z X1 X2 X3 X4 X5 X6 b bi/aie equac. 
Z 1 4 0 0 1 2 0 1350 0 
X2 0 -0.25 1 0 0.5 -0.25 0 100 1 
X3 0 1.5 0 1 0 0.5 0 230 2 
X6 0 2 0 0 -2 1 1 20 3 
 
O máximo Z é 1350, para X2 = 100, X3 = 230 e X6 = 20. 
sai Pivô 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 23 
 
 
 
 
 
 
 
 
 
6.4 EXEMPLO - Resolver o problema do GIAPETTO pelo 
simplex. 
Resolvendo o problema de
Giapetto pelo simplex
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 <= 100 (2)
• X1 + X2 <= 80 (3)
• X1<= 40 (4)
• X1 >= 0 (5)
• X2 >= 0 (6)
 
 
Primeiro passo importante:
converter o problema de PL na
forma canônica
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 + X3 = 100 (2)
• X1 + X2 + X4 = 80 (3)
• X1 + X5 = 40 (4)
• X1, X2, X3, X4 e X5 >=0
 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 24 
 
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 + X3 = 100 (2)
• X1 + X2 + X4 = 80 (3)
• X1 + X5 = 40 (4)
• X1, X2, X3, X4 e X5 >=0
Variáveis não básicas: X1 = X2 = 0
Variáveis básicas: X3 = 100 X4 = 80 X5 = 40
 
 
O problema pode ser representado assim:
Z X1 X2 X3 X4 X5 b Razão
Base 1 -3 -2 0 0 0 0 (1)
X3 0 2 1 1 0 0 100 (2)
X4 0 1 1 0 1 0 80 (3)
X5 0 1 0 0 0 1 40 (4)
Pivo
100/2=50
80/1=80
40/1=40
Indica que 
X1 entra no
lugar de X5
Solução parcial: (0, 0, 100, 80, 40)
Próximo quadro - Base: X3, X4 e X1
Devem se colocadas na forma canônica 
 
Pivo
Z X1 X2 X3 X4 X5 b Razão
Base 1 0 -2 0 0 3 120 (1)+3(4) (1)
X3 0 0 1 1 0 -2 20 (2)-2(4) (2)
X4 0 0 1 0 1 -1 40 (3)-(4) (3)
X1 0 1 0 0 0 1 40 (4) (4)
Ainda não é a 
solução ótima
20/1=20
40/1=40
40/0
Indica que 
X2 entra no
lugar de X3
Solução parcial: (40, 0, 20, 40, 0)
Próximo quadro - Base: X2, X4 e X1
Devem se colocadas na forma canônica 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 25 
 
Ainda não é a 
solução ótima Pivo
-10
20
40
Indica que 
X5 entra no
lugar de X4
Solução parcial: (40, 20, 0, 20, 0)
Próximo quadro - Base: X2, X5 e X1
Devem se colocadas na forma canônica
Z X1 X2 X3 X4 X5 b Razão
Base 1 0 0 2 0 -1 160 (1)+2(2) (1)
X2 0 0 1 1 0 -2 20 (2) (2)
X4 0 0 0 -1 1 1 20 (3)-(2) (3)
X1 0 1 0 0 0 1 40 (4) (4)
 
 
solução é ótima
Z X1 X2 X3 X4 X5 b Razão
Base 1 0 0 1 1 0 180 (1)+(3) (1)
X2 0 0 1 -1 2 0 60 (2)+2(3) (2)
X5 0 0 0 -1 1 1 20 (3) (3)
X1 0 1 0 1 -1 0 20 (4)-(3) (4)
Valor máximo possível
para a função objetivo
Solução ótima: (20, 60, 0, 0, 20)
A restrição 4 tem um folga de 20
 
 
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 + X3 = 100 (2)
• X1 + X2 + X4 = 80 (3)
• X1 + X5 = 40 (4)
• X1, X2, X3, X4 e X5 >=0
Solução do problema de
Giapetto pelo simplex
Solução ótima: (20, 60, 0, 0, 20) Z = 3*20 + 2*60 = 180
A restrição 4 tem um folga de 20
 
 
Resolver pelo Simplex a seguinte formulação: 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 26 
 
Max Z = 5X1 +2X2 
Sujeito a: 
X1 ? 3 
X2 ? 4 
X1 + 2X2 ? 9 
X1 ? 0 
X2 ? 0 
 
 
 
 
7. SOFTWARES COMPUTACIONAIS 
 
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. 
Programas adequados existem, virtualmente, para cada sistema computacional comercial 
desenvolvido nos últimos 20 anos. 
Problemas de grande porte requerem sistemas computacionais potentes e, portanto, sistemas 
paralelos têm sido utilizados nos últimos anos. Entretanto, problemas menores podem ser resolvidosem um computador pessoal utilizando um dos softwares desenvolvidos para resolução de problemas 
de programação linear, como por exemplo XPress-MP LINDO e MINOS. 
Para problemas considerados médios, é recomendável a utilização de planilhas eletrônicas com 
recursos para resolução de problemas. Exemplos destas planilhas são o "What's Best?" (LINDO 
Systems) para Lotus 1-2-3, o Microsoft Excel e Borland Quattro e ainda o solver para microsoft 
Excel. Todos eles são ferramentas poderosas, apesar de sua aparência simples. O Solver do Excel 
será utilizado em alguns exemplos apresentados. Outro programa que também será visto é o 
LINDO. 
O instituto de pesquisa operacional e ciências administrativas (INFOR-MS) publica, eventualmente, 
pesquisas sobre os softwares de programação matemática em seu periódico OR/MS Today. O 
relatório de 1995 apresenta softwares que rodam em computadores pessoais e destaca softwares 
capazes de atacar problemas maiores tanto quanto extensões de planilhas eletrônicas. 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 27 
 
 
7.1 Uma introdução ao uso do LINDO 
LINDO (Linear Interactive and Discrete Optimizer) foi desenvolvido por Linus Schrage (1986). Ele 
é um programa de computador que pode ser usado para resolver problemas de programação linear, 
inteira e quadrática. Para ilustrar seu uso, vamos usar o exemplo de Giapetto, discutido 
anteriormente, e que foi sintetizado na seguinte formulação: 
 
 
 
 
O programa executável tem o nome LINDO.EXE, apesar dele ser originalmente desenvolvido para 
o ambiente DOS, pode-se executá-lo pelo WINDOWS. O LINDO assume que todas as variáveis 
são não negativas, e as restrições adicionais não precisam ser fornecidas. 
 
7.1.1 Comandos do LINDO 
São os seguintes os comandos do LINDO: 
MAX – entrada inicial para o problema de maximização; 
MIN – entrada inicial para o problema de minimização; 
END – finalização da formulação, deixando o LINDO pronto para aceitar outros comandos; 
GO – resolve a formulação corrente e apresenta a solução; 
LOOK – mostra seleção estabelecida da atual formulação; 
ALTER – altera um elemento da formulação corrente; 
EXT – soma uma ou mais restrições ao modelo; 
DEL – retira uma ou mais restrições do modelo; 
• max Z = 3X1 + 2X2 (1) 
 sujeito a: 
• 2X1 + X2 <= 100 (2) 
• X1 + X2 <= 80 (3) 
• X1<= 40 (4) 
• X1 >= 0 (5) 
• X2 >= 0 (6) 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 28 
 
DIVERT – saída para um arquivo, de tal forma que possa ser impresso; 
RVRT – finaliza o comando DIVERT; 
SAVE – salva uma formulação, de tal forma que possa ser recuperada para uso futuro; 
RETRIEVE – recupera um arquivo anteriormente salvo; 
EDIT – chama o editor do programa; 
SOLU – mostra a solução da formulação (usar o comando GO antes do SOLU); 
TABLEAU – mostra a tabela da formulação pelo simplex; 
TAKE – habilita o LINDO a trabalhar com arquivos gerados por outros editores. 
 
Uma lista completa dos comandos pode ser obtida através do comando COMMAND. 
 
7.1.2 Usando o LINDO 
O programa assume que todas as variáveis precisam ser não negativas. Assim, usando o programa 
não é necessário digitar as variáveis de não negatividade. Para entrar com ? ou ? , basta digitar > ou 
<. O problema de Giapetto no programa fica da maneira ilustrada na figura abaixo. 
 
Depois de inserida a formulação no programa, pode-se usar qualquer dos comandos mostrados 
anteriormente. Para problemas com muitas variáveis, a função objetivo ou as restrições podem se 
estender por mais de uma linha. Se algum equivoco é cometido durante o processo de entrada da 
formulação, o LINDO acusará o erro e instruções de correção. 
Uma vez a formulação tenha sido programada, é sempre útil verificar se houve algum erro de 
digitação. Para o programa mostrar a formulação, o comando LOOK, pode ser usado. Ele irá 
perguntar qual a linha que se deseja verificar. Responda com um número de uma determinada linha, 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 29 
 
por exemplo, 3; ou por uma faica de linhas, 1-3; ou todas (ALL). Lembre que o LINDO considera 
a função objetivo como a linha 1. 
Para alterar algum aspecto da formulação, usar o comando ALTER. O programa irá perguntar qual 
o número da linha, nome da variável, e o novo coeficiente, nesta seqüência. Para trocar o lado 
direito de uma restrição, digitar RHS quando o programa perguntar pela variável. Para trocar o sinal 
da restrição (por exemplo ? para ? ), digitar DIR quando o programa perguntar pela variável. 
Mudanças adicionais podem ser feitas usando EXT (para adicionar novas linhas), DEL (apagar 
uma linha) e APPC (para somar uma variável a uma ou mais linhas). 
Uma vez que o programa esta digitado, para salvar basta digitar SAVE e dar um nome para o 
problema. Para recuperar o arquivo basta usar RETRIEVE. 
Para verificar o resultado do problema, basta digitar GO. Para obter uma impressão é preciso criar 
um arquivo e imprimir este arquivo. Isto é realizado com o comando DIVERT. 
Para resolver o problema, basta usar GO. Apenas a solução ótima é mostrada na tela, mas a 
solução inteira pode ser vista no arquivo de saída para impressão. Em seguida o programa pergunta 
se é desejo fazer uma análise de sensibilidade. Digitar NO ou YES. Para sair do programa é 
necessário digitar QUIT. 
Qualquer problema no uso do programa, o comando HELP fornece algumas informações. 
Finalmente, o LINDO não aceita parênteses e virgulas. Assim 400(X1+X2) precisa ser digitado 
como 400X1+400X2. 
 
7.1.3 O editor do LINDO 
Em versões mais novas do LINDO usando o comando EDIT, um editor para corrigir e verificar a 
formulação inteira é uma ferramenta bastante interessante. Neste editor as teclas tem as seguintes 
funções: 
 
Home – manda o cursor para o inicio da formulação; 
End – manda o cursor para o fim da formulação; 
PgUp – movimenta uma página a frente; 
PgDn– movimenta uma página a trás; 
Setas – movimenta o cursor de uma posição; 
Esc – sai do editor; 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 30 
 
Del – apaga caracter; 
Backspace – apaga o caracter a esquerda do cursor; 
Enter – muda o texto a direita para a próxima linha; 
Crtl – seta direita – manda o cursor para o fim da próxima palavra; 
Crtl – seta esquerda – manda o cursor para o fim da palavra anterior; 
Crtl-S – move o cursor para o início da linha; 
Crtl-E – move o cursor para o fim da linha; 
 
7.2 UTILIZANDO O SOLVER DO EXCEL 
Como foi dito anteriormente, a aplicação de programação linear não é mais limitada pela 
necessidade de um software especialista. Planilhas eletrônicas geralmente possuem ferramentas que 
podem ser utilizados para atacar problemas de programação linear de tamanho considerável. Talvez 
as duas planilhas mais utilizadas sejam o Excel, que contém um opcional conhecido como solver, e o 
Lotus 1-2-3, que possui o módulo What's best?. Ambos os sistemas são muito simples de serem 
utilizados e, embora sejam um pouco mais lentos que os softwares especialistas, podem resolver 
problemas de tamanho razoável. Existem, é claro, alguns perigos na sua facilidade de uso, assim 
como existem armadilhas que devem ser evitadas quando modelos de programação linear são 
construídos e rodados, as quais podem ser encobertas neste software amigável. Entretanto, a 
disponibilidade deste software é algo passível de ser elogiada. 
A discussão apresentada a seguir é baseada no Microsoft Excel v7. Versões mais recentes ou mais 
antigas deste software poderão apresentar pequenas diferenças na estrutura, mas as idéias básicas 
são as mesmas. 
 
7.2.1 Formulação para oSolver 
Na base de qualquer modelo de programação linear existe um conjunto de restrições às quais uma 
função objetivo a ser otimizada está submetida. O exemplo simples de Giapetto foi formulado 
anteriormente, neste capítulo, através das equações algébricas representadas a seguir: 
Max Z = 3X1+ 2X2 
Sujeita a: 
2X1 + X2 ? 100 
X1 + X2 ? 80 
Função objetivo 
 
Restrição quanto a tempo de acabamento 
Restrição quanto a tempo de carpintaria 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 31 
 
X1 ? 40 Restrição de venda máxima de soldados 
 
Estas equações podem ser representadas de maneira diferente, através da utilização de matrizes. 
Esta representação está exposta a seguir: 
 
 X1 = número 
de soldados 
X2 = número de 
trens 
 
maximizar 3 2 
Sujeito as restrições limite 
 2 1 ? 100 
 1 1 ? 80 
 1 0 ? 40 
 Lucro bruto 
Solução 0 0 0 
 
Com exceção da última linha, denominada solução, as demais restrições expostas nas matrizes já 
eram conhecidas. A linha de solução representa os valores atribuídos a X1 e X2 antes de qualquer 
otimização. No estado atual, ambos X1 e X2 são definidos como zero, o que resulta em um lucro 
bruto de zero unidades. 
O primeiro estágio de uso Solver é escrever esta matriz na planilha, como apresentado na Figura 1. 
Como em qualquer planilha, é muito importante observar que algumas células contêm valores 
constantes, mas outras contêm fórmulas as quais assumem os valores que são exibidos nas mesmas. 
Neste exemplo, as células D4, D5, D6 e E8 contêm fórmulas. As demais contêm textos, que são 
utilizados para deixar o exemplo mais claro, ou contêm valores. 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 32 
 
 
Figura 1 - formulação básica do problema. 
Uma rápida explicação da Figura 1 é dada abaixo: 
 
1. Neste exemplo, as colunas B e C possuem os valores dos coeficientes das expressões utilizadas 
na formulação algébrica e na tabela anteriormente. 
2. A linha 2 contém os valores dos coeficientes da função objetivo (2 e 1). 
3. As linhas 4 a 6 apresentam os valores dos coeficientes das restrições descritas anteriormente. 
4. A linha 8 contém os valores dados inicialmente para X1 e X2 antes de qualquer otimização. 
5. A coluna D possui suas linhas com valor zero, porém suas células representam a utilização das 
três restrições. Assim, a célula D4 contém a fórmula: 
 
= $B$8*$B4 + $C$8*$C4 
 
Observe que as referências às células B10 e C10 são ambas absolutas. Assim, esta fórmula 
estendida da célula D4 a à D6 é dada por: 
 D4 = $B$8*$B4 + $C$8*$C4 
 D5 = $B$8*$B5 + $C$8*$C5 
 D6 = $B$8*$B6 + $C$8*$C6 
 
A coluna E foi utilizada para que os limites máximos e mínimos das restrições fossem observados, a 
qual é freqüentemente conhecida como right-hand-sides (abreviada como RHS por muitas pessoas). 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 33 
 
Assim, existe um limite de 100 horas para acabamento, de 80 horas para carpintaria e venda 
máxima de 40 soldados. A coluna D, como mencionado anteriormente, é usada para armazenar a 
utilização atual dos recursos. Assim, a célula D4 representa a quantidade da restrição horas de 
acabamento que foi utilizada e seu valor é zero, uma vez que as células B8 e C8 contêm valor zero 
antes de qualquer otimização. 
 Finalmente, uma célula da planilha deve ser utilizada para armazenar o resultado da otimização 
(neste caso, o valor do lucro semanal obtido); nesta planilha, este valor está contido na célula E8. 
 
7.2.2 Janela de Parâmetros do Solver 
Utilizando os botões do mouse ou o teclado, devemos selecionar o Solver a partir do menu de 
ferramentas do Microsoft Excel. A Figura 2 apresenta a janela que irá aparecer na tela. Esta janela 
de parâmetros do Solver é utilizada quando o usuário fornece ao Solver as informações necessárias 
para que o mesmo busque a solução otimizada. 
Figura 2 - Janela de parâmetros do Solver. 
 
Para chegarmos à solução ótima do exemplo, o Solver precisa das seguintes informações: 
 
1. Onde o valor da função objetivo será armazenado? Este valor representa o resultado da 
otimização dado pela combinação de valores de X1 e X2 determinada. Neste caso, o resultado 
será armazenada na célula E8. Isto significa que a célula E8 deve conter a fórmula apropriada 
para a otimização, a qual, neste caso, é dada por: = $B$2*$B$8 + $C$2*$C$8. Observe que 
as células de referência são absolutas - o que é recomendável, porém não é necessário. 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 34 
 
2. Quais são as restrições e que forma as mesmas possuem? Para fornecer estas informações para 
o Solver, clique no botão adicionar da subjanela de restrições da janela dos parâmetros do 
Solver. Uma caixa de diálogo, como a apresentada na Figura 3, irá aparecer. Neste caso, a 
caixa de diálogo corresponde à primeira restrição, a restrição das horas de acabamento, a qual 
possui seus coeficientes nas células B4 e C4 e sua expressão está contida na célula D4. Assim, a 
célula $D$4 deve ser digitada na caixa referência de célula, uma vez que a mesma contém a 
expressão da restrição. Esta restrição é do tipo menor ou igual a, assim devemos selecionar este 
símbolo da caixa central da janela. Finalmente, o valor máximo para esta restrição encontra-se 
na célula $E$4 e esta célula deve ser indicada na caixa à esquerda da janela. Aperte o botão 
OK e a caixa de diálogo irá fechar-se retornando à janela de parâmetros do Solver. Cada uma 
das restrições deve ser descrita do mesmo modo como a anterior. 
 
Figura 3 - janela para entrada das restrições. 
 
3. Quais células irão conter os valores de X1 e X2, os quais serão modificados até que se otimize 
a função objetivo, e qual tipo de otimização deve-se procurar? Esta informação deve ser 
fornecida pelo usuário através da janela de parâmetros do Solver. As células cujos valores serão 
variados são a B8 e a C8 e, como mostra a Figura 4, devem ser descritas como células de 
referência na caixa células variáveis. Como se busca a maximização destas variáveis, a opção 
Máx deve ser selecionada. 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 35 
 
 
Figura 4 - entrada das células que irão variar para que a solução ótima seja encontrada (células 
variáveis). 
 
Antes de executar a otimização, é interessante informar ao Solver que todas as restrições são 
expressões lineares, assim como a função objetivo. Estas informações devem ser fornecidas, pois 
estamos tratando de um problema de programação linear. Para entrar com esta informação, clique o 
botão opções da janela dos parâmetros do Solver. Uma nova janela irá aparecer onde a opção 
presume modelo linear deve ser selecionada. Isto irá aumentar a velocidade da otimização e, 
também, fará com que os relatórios fornecidos sejam adaptados para o formato de problemas de 
programação linear (veja a seguir). 
Para executar a otimização, retorne à janela de parâmetros do Solver e aperte o botão resolver. A 
Figura 5 apresenta o resultado da otimização. 
 
 
Figura 5 - solução do problema 
 
É importante observar que muitas outras informações, além do valor ótimo das variáveis estudadas, 
podem ser obtidas a partir da solução fornecida para um problema de programação linear. Um bom 
pacote computacional como o Solver fornece relatórios que ajudam o usuário a entender muito mais 
sobre a solução apresentada. O Solver fornece três relatórios padrão e permite que sua solução seja 
exportada para outro pacote se uma análise mais detalhada for necessária. 
 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 36 
 
7.2.3 O Relatório de Resultados do Solver 
O relatório resume os resultados dapasta de trabalho e também fornece algumas informações a 
mais. Estas informações extras podem ser calculadas pelo usuário, mas é importante guardá-las em 
algum lugar. O relatório da otimização para o problema apresentado é mostrado na Figura 6 e 
possui três partes, como descrito abaixo: 
 
? 1.Célula de destino (Máximo): apresenta o máximo lucro obtido pelo Solver. Se este fosse um 
problema de minimização, esta seção iria conter o valor mínimo. 
? Células ajustáveis: mostram as variáveis de entrada, seus valores após a solução ótima e seus 
valores iniciais (zero, neste caso). 
Restrições: indicam a utilização de cada um dos recursos ao final da otimização. A coluna de status 
classifica as restrições como obrigatória (restrição com utilização máxima) ou não-obrigatória, estas 
últimas são as que apresentam algum recurso que não foi utilizado - indicado pelo valor diferente de 
zero na coluna diferencial (slacks - folgas). 
Os outros dois relatórios fornecem mais informações sobre a sensibilidade da solução ótima, 
informações que podem ser importantes por várias razões. Primeiro, porque são raros os casos de 
programação matemática em ciências administrativas nos quais todos os coeficientes ou valores do 
modelo são conhecidos com precisão. Geralmente, alguns coeficientes são conhecidos e vários 
serão aproximações, estimativas ou até mesmo hipóteses. O que fazer, se os valores tomados forem 
errados? Qual será o efeito destes erros na solução? Assim, uma solução alternativa não tão ótima 
pode ser, algumas vezes, melhor que uma solução ótima que se toma sensível aos valores atribuídos 
aos coeficientes. A segunda razão que torna importante a análise de sensibilidade está relacionada à 
idéia de que o mundo é dinâmico e, por isso, as coisas estão mudando constantemente. Por 
exemplo, pode ser verdade que esta semana a matéria-prima tenha um certo custo, porém, se o 
período observado for um mês, este custo pode ser diferente. Assim, é importante conhecer quais 
são os efeitos que as mudanças nos coeficientes podem gerar na solução ótima. 
Capítulo 5 - Introdução a Pesquisa Operacional 5. 37 
 
Figura 7 - relatório de resposta para o problema