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 Investimento no
ano 1
ano 2
1
2
3
4
5
6
7
8
9
12
54
6
6
30
6
48
36
18
3
7
6
2
35
6
4
3
2
Vida útil
5 anos
5 anos
5 anos
5 anos
5 anos
5 anos
5 anos
5 anos
5 anos
Economia anual
nos próximos 3
anos
9.29
26.85
9.88
7.92
35.33
8.14
22.78
16.91
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
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.
5. 4
Capítulo 5 - Introdução a Pesquisa Operacional
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
5. 5
Capítulo 5 - Introdução a Pesquisa Operacional
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
5. 6
Capítulo 5 - Introdução a Pesquisa Operacional
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:
• 1 - 2X1 + X2 <= 100
• 2 - X1 + X2 <= 80
• 3 - X1 <= 40
Coeficientes
tecnológicos:
refletem a quantia
usada para
diferentes produtos.
Restrições para o
problema de PL
de Giapetto
Usualmente
representam a
quantidade de
recursos
disponíveis.
5. 7
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
Significa que
X1 e X2
precisam satisfazer
todas as restrições
Resumindo
• max Z = 3X1 + 2X2
sujeito a:
• 2X1 + X2 <= 100
• X1 + X2 <= 80
• X1<= 40
• X1 >= 0
• X2 >= 0
(1)
(2)
(3)
(4)
(5)
(6)
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
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.
Giapetto: X1 = 40 X2 = 20
Restrições:
• 2X1 + X2 <= 100
• X1 + X2 <= 80
• X1<= 40
• X1 >= 0
• X2 >= 0
região de solução
(2), ok 2*40+20<=100
(3), ok 40+20<=80
(4), ok 40<=40
(5), ok 40>=0
(6), ok 20>=0
5. 9
Capítulo 5 - Introdução a Pesquisa Operacional
Giapetto: X1 = 15 X2 = 70
Restrições:
• 2X1 + X2 <= 100
• X1 + X2 <= 80
• X1<= 40
• X1 >= 0
• X2 >= 0
não é região de solução
(2), ok 2*15+70<=100
(3), não ok 15+70> 80
(4), ok 15<=40
(5), ok 15>=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
5. 10
Capítulo 5 - Introdução a Pesquisa Operacional
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
X2 = 2 - 2/3X1
6
5
4
Região onde:
2X1+3X2>=6
3
2
1
Região onde:
2X1+3X2<=6
X1
1
2
3
4
5
6
5. 11
Capítulo 5 - Introdução a Pesquisa Operacional
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
X1 + X2 <= 80
X1<= 40
X1 >= 0
X2 >= 0
(2)
(3)
(4)
(5)
(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
(2)
(4)
120
D
Poligono DGFEH - região de solução
B
100
80
G
60
40
F
20
E
H
20
(3)
A
40
X1
C
60
80
100 120
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
5. 12
Capítulo 5 - Introdução a Pesquisa Operacional
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
(2)
(4)
120
100
D
80
B
G
Indica o ponto ótimo - G (20, 60)
60
40
F
20
A
E
20
H
X2 = 30 - 3/2 X1
(3)
40
X1
C
60
80
100 120
5. 13
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).
Desembolso
instante 0
Desembolso
instante 1
Valor presente
Inv. 1
11
Inv. 2
53
Inv. 3
5
Inv. 4
5
Inv. 5
29
3
6
5
1
34
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 tabela a seguir.
Gravador
100
50
30
Preço de venda
Mão de obra
Custo matéria prima
Rádio
90
35
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
Caixa
Contas a receber
Estoques
Dívidas em bancos
Obrigações
10000
3000
7000
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.
A
B
C
D
E
0
-$1
$0
-$1
-$1
$0
1
$0.50
-$1
$1.2
$0
$0
2
$1
$0.50
$0
$0
-$1
3
$0
$1
$0
$1.9
$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
X2
E(0, 4)
5. 18
Z
ZB = 15
D(1, 4)
ZB = 15
ZD = 13
C(3, 3)
ZE = 8
X1
A(0, 0)
B(3, 0)
A
B
C
D
E
Pontos extremos
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.
Capítulo 5 - Introdução a Pesquisa Operacional
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
?0
X1, X2, X3, Xn
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
5. 19
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
=0
x1+ 2x2 + x3 + x4
3x1
xl + 4x2
+2x3
= 430
+ x5
= 460
+ 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
X4
X5
X6
z
1
0
0
0
X1
-3
1
3
1
X2
-2
2
0
4
X3
-5
1
2
0
X4
0
1
0
0
X5
0
0
1
0
X6
0
0
0
1
b
0
430
460
420
bi/aie
430
230
ind.
equac.
0
1
2
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:
entra
Base
Z
X4
z
1
0
X1
-3
1
X2
-2
2
X3
-5
1
X4
0
1
X5
0
0
X6
0
0
b
0
430
bi/aie
430
equac.
0
1
Capítulo 5 - Introdução a Pesquisa Operacional
X5
X6
0
0
3
1
0
4
2
0
sai
0
0
1
0
0
1
460
420
230
ind.
5. 22
2
3
Pivô
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
X4
X3
X6
z
1
0
0
0
X1
4.5
-0.5
1.5
1
X2
-2
2
0
4
X3
0
0
1
0
X4
0
1
0
0
X5
2.5
-0.5
0.5
0
X6
0
0
0
1
b
1150
200
230
420
bi/aie
100
ind.
105
equac.
0
1
2
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 ilnha a solução é ótima. O resultado é
mostrado a seguir.
Base
Z
X2
X3
X6
z
1
0
0
0
X1
4
-0.25
1.5
2
X2
0
1
0
0
X3
0
0
1
0
X4
1
0.5
0
-2
X5
2
-0.25
0.5
1
O máximo Z é 1350, para X2 = 100, X3 = 230 e X6 = 20.
X6
0
0
0
1
b
1350
100
230
20
bi/aie
equac.
0
1
2
3
Capítulo 5 - Introdução a Pesquisa Operacional
6.4 EXEMPLO - Resolver o problema do GIAPETTO pelo
simplex.
Resolvendo o problema de
Giapetto pelo simplex
• max Z = 3X1 + 2X2
sujeito a:
• 2X1 + X2 <= 100
• X1 + X2 <= 80
• X1<= 40
• X1 >= 0
• X2 >= 0
(1)
(2)
(3)
(4)
(5)
(6)
Primeiro passo importante:
converter o problema de PL na
forma canônica
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 + X3
= 100
• X1 + X2
+ X4
= 80
• X1
+ X5 = 40
• X1, X2, X3, X4 e X5 >=0
(2)
(3)
(4)
5. 23
Capítulo 5 - Introdução a Pesquisa Operacional
• max Z = 3X1 + 2X2 (1)
•
•
•
•
sujeito a:
2X1 + X2 + X3
= 100
X1 + X2
+ X4
= 80
X1
+ X5 = 40
X1, X2, X3, X4 e X5 >=0
(2)
(3)
(4)
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:
Pivo
Base
X3
X4
X5
Z
1
0
0
0
X1
-3
2
1
1
X2
-2
1
1
0
X3
0
1
0
0
X4
0
0
1
0
X5
0
0
0
1
b
0
100
80
40
Razão
(1)
(2)
(3)
(4)
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
Ainda não é a
solução ótima
Pivo
Base
X3
X4
X1
Z
1
0
0
0
X1
0
0
0
1
X2
-2
1
1
0
X3
0
1
0
0
X4
0
0
1
0
X5
3
-2
-1
1
Solução parcial: (40, 0, 20, 40, 0)
Próximo quadro - Base: X2, X4 e X1
Devem se colocadas na forma canônica
b
120
20
40
40
Razão
20/1=20
40/1=40
40/0
(1)+3(4) (1)
(2)-2(4) (2)
(3)-(4) (3)
(4)
(4)
Indica que
X2 entra no
lugar de X3
5. 24
Capítulo 5 - Introdução a Pesquisa Operacional
Ainda não é a
solução ótima
Z
1
0
0
0
Base
X2
X4
X1
X1
0
0
0
1
X2
0
1
0
0
Pivo
X3
2
1
-1
0
X4
0
0
1
0
X5
-1
-2
1
1
b
160
20
20
40
Razão
(1)+2(2) (1)
(2)
(3)-(2)
(4)
-10
20
40
(2)
(3)
(4)
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
Valor máximo possível
para a função objetivo
solução é ótima
Base
X2
X5
X1
Z
1
0
0
0
X1
0
0
0
1
X2
0
1
0
0
X3
1
-1
-1
1
X4
1
2
1
-1
X5
0
0
1
0
b
180
60
20
20
Razão
(1)+(3) (1)
(2)+2(3) (2)
(3)
(3)
(4)-(3) (4)
Solução ótima: (20, 60, 0, 0, 20)
A restrição 4 tem um folga de 20
Solução do problema de
Giapetto pelo simplex
• max Z = 3X1 + 2X2 (1)
sujeito a:
• 2X1 + X2 + X3
= 100
• X1 + X2
+ X4
= 80
• X1
+ X5 = 40
• X1, X2, X3, X4 e X5 >=0
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:
(2)
(3)
(4)
5. 25
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 resolvidos
em 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:
•
•
•
•
•
•
max Z = 3X1 + 2X2
sujeito a:
2X1 + X2 <= 100
X1 + X2 <= 80
X1<= 40
X1 >= 0
X2 >= 0
(1)
(2)
(3)
(4)
(5)
(6)
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;
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 o Solver
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
Função objetivo
Sujeita a:
2X1 + X2 ? 100
Restrição quanto a tempo de acabamento
X1 + X2 ? 80
Restrição quanto a tempo de carpintaria
Capítulo 5 - Introdução a Pesquisa Operacional
X1 ? 40
5. 31
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:
maximizar
Sujeito as restrições
Solução
X1 = número
de soldados
3
X2 = número de
trens
2
2
1
1
1
1
0
0
0
?
?
?
limite
100
80
40
Lucro bruto
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 da pasta 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
Figura 7 - relatório de resposta para o problema
5. 37