Pesquisa Operacional
Max Vinicius Bedeschi – CRE 6849
Pesquisa Operacional é um método
científico de tomada de decisões.
Sistema Organizado com o auxílio de
um modelo.
Experimentação modelar com fins de
otimização da operação do sistema.
Fases de um Estudo em P.O.
•
•
•
•
•
•
Formulação do problema
Construção do modelo do sistema
Cálculo da solução através do modelo
Teste do modelo e da solução
Estabelecimento de controles da solução
Implantação e acompanhamento
Formulação do Problema
Nesta fase, o administrador do sistema e o responsável
pelo estudo em P.O. deverão discutir, no sentido de colocar
o problema de maneira clara e coerente, definindo os
objetivos a alcançar e quais os possíveis caminhos
alternativos para que isso ocorra.
Além disso, serão levantadas as limitações técnicas do
sistema e as relações desse sistema com outros da
empresa ou do ambiente externo, com a finalidade de
criticar a validade de possíveis soluções em face destes
obstáculos.
Deverá ainda ser acordada uma medida de eficiência para
o sistema que permita ao administrador ordenar as
soluções encontradas, concluindo o processo decisório.
Construção do Modelo do Sistema
Os modelos que interessam em Pesquisa Operacional são
os modelos matemáticos, isto é, modelos formados por um
conjunto de equações e inequações.
Uma das equações do conjunto serve para medir a
eficiência do sistema para cada solução proposta. É a
função objetivo ou função de eficiência. As outras
equações geralmente descrevem as limitações ou
restrições técnicas do sistema. As variáveis que compõem
as equações são de dois tipos:
-Variáveis controladas ou de decisão.
-Variáveis não controladas.
Variáveis controladas ou de decisão
são variáveis cujo valor está sob controle do administrador.
Decidir, neste caso, é atribuir um particular valor a cada
uma dessas variáveis. Numa programação de produção,
por exemplo, a variável de decisão é a quantidade a ser
produzida num período, o que compete ao administrador
controlar.
Variáveis não controladas
são as variáveis cujos valores são arbitrados por sistemas
fora do controle do administrador. Custos de produção,
demanda de produtos, preço de mercado são variáveis
não controladas.
Um bom modelo é aquele que tem desempenho
suficientemente próximo do desempenho da realidade e
é de fácil experimentação. Essa proximidade desejada é
variável, dependendo do objetivo proposto. Um bom
modelo para um objetivo pode ser péssimo para outro. A
fidelidade de um modelo é aumentada à medida que ele
incorpora características da realidade, com a adição de
novas variáveis. Isso aumenta sua complexidade,
dificultando a experimentação, o que nos leva a
considerar o fator custo-benefício quando pensamos em
melhorar o desempenho de um modelo.
Cálculo da solução através do modelo
É feito através de técnicas matemáticas específicas. A
construção do modelo deve levar em consideração a
disponibilidade de uma técnica para o cálculo da solução.
Teste do modelo e da solução
Esse teste é realizado com dados empíricos do
sistema. Se houver dados históricos, eles serão
aplicados no modelo, gerando um desempenho que
pode ser comparado ao desempenho observado no
sistema. Se o desvio verificado não for aceitável, a
reformulação ou mesmo o abandono do modelo será
inevitável. Caso não haja dados históricos, os dados
empíricos serão anotados com o sistema
funcionando sem interferência, até que o teste possa
ser realizado.
Estabelecimento de controles da solução
A construção e experimentação com o modelo
identificam parâmetros fundamentais para solução do
problema. Qualquer mudança nesses parâmetros
deverá ser controlada para garantir a validade da
solução adotada. Caso alguns desses parâmetros
sofra desvio além do permitido, o cálculo de nova
solução ou mesmo a reformulação do modelo poderá
ser necessária.
Implementação e acompanhamento
Nesta fase, a solução será apresentada ao administrador,
evitando-se o uso da linguagem técnica do modelo. O uso
da linguagem do sistema em estudo facilita a
compreensão e gera boa vontade para a implantação que
está sendo sugerida. Essa implantação deve ser
acompanhada para se observar o comportamento do
sistema com a solução adotada. Algum ajuste pode ser
requerido.
Modelo em Programação Linear
O modelo matemático é composto de uma função
objetiva linear; e de restrições técnicas representadas
por um grupo de inequações também lineares.
Exemplo:
Função objetivo a ser maximizada:
Lucro = 2 x  3 x
1
2
Restrições técnicas:
4 x1  3 x 2  10
6 x1  x 2  20
Restrições de não
negatividade:
x1  0
x2  0
As variáveis controladas ou variáveis de decisão são X1 e X2
A função objetivo ou função eficiência mede o desempenho
do sistema, no caso a capacidade de gerar lucro, para cada
solução apresentada.
O objetivo é maximizar o lucro.
As restrições garantem que essas soluções estão de acordo
com as limitações técnicas impostas pelo sistema.
As duas últimas restrições exigem a não negatividade das
variáveis de decisão, o que deverá acontecer sempre que a
técnica de abordagem for a de programação linear.
Roteirização
• Variáveis de decisão?
• Objetivo?
• Restrições?
Quais as variáveis de decisão?
Problema
Variáveis de decisão
Programação
de produção
Quantidades a
produzir no período
Programação de
investimento
Decisões de
investimento
Nas descrições sumárias de sistemas, isso
fica claro quando lemos a questão proposta,
isto é, a pergunta do problema.
Quais o objetivo?
Identificar o objetivo da tomada de decisão.
Eles aparecem geralmente na forma da
maximização de lucros ou receitas, minimização de
custos, perdas, etc.
A função objetivo é a expressão que calcula o
valor do objetivo (lucro, custo receita, perda, etc.),
em função das variáveis de decisão.
Quais as restrições?
Cada restrição imposta na descrição do sistema
deve ser expressa como uma relação linear
(igualdade ou desigualdade), montadas com as
variáveis de decisão.
Exemplo 1:
Certa empresa fabrica dois produtos P1 e P2. O lucro
unitário do produto P1 é de 1.000 unidades monetárias e o
lucro unitário de P2 é de 1.800 unidades monetárias. A
empresa precisa de 20 horas para fabricar uma unidade
de P1 e de 30 horas para fabricar uma unidade de P2. O
tempo anual de produção disponível para isso é de 1.200
horas. A demanda esperada para cada produto é de 40
unidades anuais para P1 e 30 unidades anuais para P2.
Qual é o plano de produção para que a empresa
maximize seu lucro nesses itens?
Construa o modelo de programação linear para esse
caso.
Solução:
a) Quais as variáveis de decisão?
O que deve ser decidido é o plano de produção, isto
é, quais as quantidades anuais que devem ser
produzidas de P1 e P2.
Portanto, as variáveis de decisão serão X1 e X2
X1  quantidade anual a produzir de P1
X2  quantidade anual a produzir de P2
b) Qual o objetivo?
O objetivo é maximizar o lucro, que pode ser
calculado:
Lucro devido a P1: 1000 . X1 (lucro por unidade de
P1 x quantidade produzida de P1)
Lucro devido a P2: 1800 . X2 (lucro por unidade de
P2 x quantidade produzida de P2)
Lucro total: L = 1000X1 + 1800X2
Objetivo: maximizar L = 1000X1 + 1800X2
c) Quais as restrições?
As restrições impostas pelo sistema são:
Disponibilidade de horas para a produção: 1200 horas.
Horas ocupadas com P1: 20X1 (uso por unidade x
quantidade produzida)
Horas ocupadas com P2: 30X2 (uso por unidade x
quantidade produzida)
Total em horas ocupadas na produção:20X1 + 30X2
Disponibilidade: 1200 horas.
Restrição descritiva da situação: 20X1 + 30X2 ≤ 1200
Disponibilidade de mercado para os produtos (demanda)
Disponibilidade para P1: 40 unidades
Quantidade a produzir de P1: X1
Restrição descritiva da situação X1 ≤ 40
Disponibilidade para P2: 30 unidades
Quantidade a produzir de P2: X2
Restrição descritiva da situação: X2 ≤ 30
Resumo do modelo: max L = 1000X1 + 1800X2
Sujeito a:
Restrições técnicas:
20 x1  30 x 2  1200
x1  40
x 2  30
Restrições de não
negatividade:
x1  0
x2  0
Exemplo 2:
Para uma boa alimentação, o corpo necessita de
vitaminas e proteínas. A necessidade mínima de vitaminas
é de 32 unidades por dia e a de proteínas de 36 unidades
por dia. Uma pessoa tem disponível carne e ovos para se
alimentar. Cada unidade de carne contém 4 unidades de
vitaminas e 6 unidades de proteínas. Cada unidade de
ovo contém 8 unidades de vitaminas e 6 unidades de
proteínas.
Qual a quantidade diária de carne e ovos que deve ser
consumida para suprir as necessidades de vitaminas e
proteínas com o menor custo possível? Cada unidade de
carne custa 3 unidades monetárias e cada unidade de ovo
custa 2,5 unidades monetárias.
Solução:
a. Quais as variáveis de decisão?
Devemos decidir quais as quantidades de carne e ovos
a pessoa deve consumir no dia. As variáveis de decisão
serão, portanto:
X1  quantidade de carne a consumir no dia
X2  quantidade de ovos a consumir no dia
b. Qual o objetivo?
O objetivo é minimizar o custo, que pode ser calculado:
Custo devido à carne: 3 . X1 (custo por unidade x
quantidade a consumir de carne)
Custo devido aos ovos: 2,5 . X2 (custo por unidade x
quantidade a consumir de ovos)
Custo Total: C = 3X1 + 2,5X2
Objetivo:minimiza C = 3X1 + 2,5X2
c. Quais as restrições?
As restrições impostas pelo sistema são:
Necessidade mínima de vitamina: 32 unidades
Vitaminas de carne: 4 . X1 (quantidade por unidade x
unidades de carne a consumir)
Vitamina de ovos: 8 . X2 (quantidade por unidade x
unidades de ovos a consumir)
Total de vitaminas: 4X1 + 8X2
Necessidade mínima: 32
Restrição descritiva da situação: 4X1 + 8X2 ≥ 32
Necessidade mínima de proteína: 36 unidades
Proteína de carne: 6 . X1 (quantidade por unidade x
unidades de carne a consumir)
Proteína de ovos: 6 . X2 (quantidade por unidade x
unidades de ovos a consumir)
Total de proteínas: 6X1 + 6X2
Necessidade mínima: 36
Restrição descritiva da situação: 6X1 + 6X2 ≥ 36
Resumo do modelo: min C = 3X1 + 2,5 X2
Sujeito a:
Restrições técnicas:
4 x1  8 x 2  32
6 x1  6 x 2  36
Restrições de não
negatividade:
x1  0
x2  0
FUNÇÃO OBJETIVO:
Problema de
MAXIMIZAÇÃO
Max Vinicius Bedeschi
CRE 6859
EXEMPLO
Uma fábrica produz dois produtos, A e B. Cada um deles deve
ser processado por duas máquinas, M1 e M2. Devido à
programação de outros produtos, que também utilizam essas
máquinas, a máquina M1 tem 24 horas de tempo disponível
para os produtos A e B, enquanto a máquina M2 tem 16 horas
de tempo disponível. Para produzir uma unidade do produto A,
gastam-se 4 horas em cada uma das máquinas M1e M2. Para
produzir uma unidade do produto B, gastam-se 6 horas na
máquina M1 e 2 horas na máquina Ms. Cada unidade vendida
do produto A gera um lucro de R$80 e cada unidade do
produto B, um lucro de R$60. Existe uma previsão máxima de
demanda para o produto B de 3 unidades, não havendo
restrições quanto à demanda do produto A. Deseja-se saber
quantas unidades de A e de B devem ser produzidas, de forma
a maximizar o lucro e, ao mesmo tempo, obedecer a todas as
restrições desse enunciado.
Variáveis de decisão
AeB
Os dois produtos a serem fabricados
X1 (quantidades do produto A)
X2 (quantidades do produto B)
§ Hipótese: toda a produção será vendida
Produto
Horas gastas Horas gastas
em M1
em M2
Demanda
máxima
Lucro unitário
(R$)
A
4
4
ilimitada
80
B
6
2
3
60
Horas disponíveis
24
16
Função objetivo
Vamos chamar de x e y, respectivamente, às quantidades
dos produtos A e B que devemos fabricar (as quais serão
vendidas integralmente). Portanto, x e y são os valores
procurados, que darão a solução ao nosso problema de
programação linear.
Queremos maximizar o lucro na venda de x unidades de A
e y unidades de B, ou seja, queremos maximizar o
resultado numérico da seguinte expressão:
80x + 60y
Restrições
As restrições dizem respeito à escassez de recursos, por
um lado, e a limites impostos sobre nossas ações na
tentativa de maximiza a função objetivo. Quais são os
nossos recursos escassos?
Horas consumidas na máquina M1 ≤ 24
Horas consumidas na máquina M2 ≤ 16
Horas consumidas na máquina M1 = 4x + 6y
Horas consumidas na máquina M2 = 4x + 2y
Reescrevendo, temos:
4x + 6y ≤ 24
4x + 2y ≤ 16
Restrições
Não se pode fabricar mais de 3 unidades do produto B,
pois sua demanda máxima é essa:
Restrições de não-negatividade
X ≥ 0; Y ≥ 0
y≤3
Formulação completa
Maximizar 80x + 60y
Sujeito a:
4x + 6y ≤ 24
4x + 2y ≤ 16
y≤3
X ≥ 0; Y ≥ 0
A solução do problema nos dá: x=3 e y=2
O valor da função objetivo é máximo e igual a
80(3) + 60(2) = 240 + 120 = R$360,00
Repare o leitor que os recursos disponíveis são totalmente
consumidos, pois:
4(3) + 6(2) = 12 + 12 = 24 (horas consumidas da máquina M1)
4(3) + 2(2) = 12 + 4 = 16 (horas consumidas da máquina M2)
FUNÇÃO OBJETIVO:
Problema de
MINIMIZAÇÃO
Max Vinicius Bedeschi
CRE 6859
EXEMPLO
A Granja Cocoró quer misturar dois tipos de alimentos para criar
um tipo especial de ração para suas galinhas poedeiras. A
primeira característica a ser atingida com a nova raçção e o
menor preço possível por unidade de peso. Cada um dos
alimentos contém os nutrientes necessários à ração final (aqui
chamados de nutrientes X, Y e Z), porém em proporções
variáveis. Cada 100g do alimento 1, por exemplo, possuem 10g
do nutriente X, 50g do nutriente Y e 40g do nutriente Z. O
alimento 2, por sua vez, para cada 100g, possui 20g do nutriente
X, 60g do nutriente Y e 20g do nutriente Z. Cada 100g do
alimento 1 custam, para a Granja Cocoró, R$0,60 e cada 100g do
alimento 2 custam R$0,60. Sabe-se que a ração final deve conter,
no mínimo, 2g do nutriente X, 64g do nutriente Y e 34g do
nutriente Z. É preciso obedecer a essa composição, minimizando
ao mesmo tempo o custo por peso da nova ração.
O objetivo é misturar dois alimentos, Alimento 1 e
Alimento 2, de forma a obter uma nova ração, com
uma certa composição de nutrientes X, Y e Z. Os
nutrientes estão presentes nos dois alimentos.
Nossa ração final será uma mistura dos dois alimentos
– digamos, x gramas do Alimento 1 e y gramas do
Alimento 2.
Portanto: X e Y são nossas variáveis de decisão.
Composição por 100 g
Composição de nutrientes
(mínima em gramas)
Alimento 1
Alimento 2
Nutriente X
10
20
2
Nutriente Y
40
60
64
Nutriente Z
50
20
34
Custo por 100 g
R$0,60
R$0,80
Função objetivo
Nosso problema é de minimização, ou seja, devemos usar
x gramas do Alimento 1 e y gramas do Alimento 2 para
compor (x + y) gramas da nova ração, e x e y devem ser
tais que seu custo total seja mínimo. Ora, cada 100
gramas do Alimento 1 custam R$0,60; um só grama
custaria 0,60/100 e x gramas custariam 0,60x/100, ou
0,006x. Usando o mesmo raciocínio para o Alimento 2, y
gramas custariam 0,008y. Logo, quer-se minimizar
0,006x + 0,008y
Restrições
• A quantidade total do nutriente X, em x gramas
do Alimento 1 e y gramas do Alimento 2, deve
ser pelo menos igual a 2 gramas;
• A quantidade total do nutriente Y, em x gramas
do Alimento 1 e y gramas do Alimento 2, deve
ser pelo menos igual a 64 gramas;
• A quantidade total do nutriente Z, em x gramas
do Alimento 1 e y gramas do Alimento 2, deve
ser pelo menos igual a 34 gramas.
x gramas do Alimento 1 contêm, respectivamente,
10x/100 gramas do nutriente X, ou 0,1x gramas do nutriente X
40x/100 gramas do nutriente Y, ou 0,4x gramas do nutriente Y
50x/100 gramas do nutriente Z, ou 0,5x gramas do nutriente Z
Enquanto y gramas do Alimento 2 contêm
20y/100 gramas do nutriente X, ou 0,2y gramas do nutriente X
60y/100 gramas do nutriente Y, ou 0,6y gramas do nutriente Y
20y/100 gramas do nutriente Z, ou 0,2y gramas do nutriente Z
Reescrevendo, temos:
Quantidade total do nutriente X:
0,1x + 0,2y ≥ 2
Quantidade total do nutriente Y:
0,4x + 0,6y ≥ 64
Quantidade total do nutriente Z:
0,5x + 0,2y ≥ 34
Formulação completa
Maximizar 0,006x + 0,008y
Sujeito a:
0,1x + 0,2y ≥ 2
0,4x + 0,6y ≥ 64
0,5x + 0,2y ≥ 34
X ≥ 0; Y ≥ 0
A solução do problema nos dá:
x=34,5 gramas
y=83,6 gramas
Essas quantidades, correspondem a exatamente 64
gramas do nutriente Y e 34 gramas do nutriente Z e, com
folga, a 20,1 gramas do nutriente X. A soma (x + y) é igual
a 118,1 gramas, formados por 20,1g do nutriente X, 64g
do nutriente Y e 34g do nutriente Z. Corresponde a um
custo de R$0,88. Na verdade, as quantidades de x e de y
correspondem a uma proporção, que pode ser escrita de
inúmeras formas, tais como:
34,5g do alimento 1 para 83,6g do Alimento 2
1g do Alimento 1 para 2,4g do Alimento 2
100g do Alimento 1 para 240g do Alimento 2 etc.
Duas variáveis de Decisão
Técnica de solução numa
Programação Linear
§
Uma revisão gráfica
Max Vinicius Bedeschi
CRE 6859
O desempenho do modelo á avaliado através
da representação gráfica da função objetivo
As soluções são classificadas de acordo com
sua posição no gráfico.
A representação gráfica de uma equação
linear com duas variáveis é uma reta.
Exemplo
Representar graficamente a inequação: X1
+ 2X2 ≥ 10
Exemplo
Representar graficamente a solução do sistema:
X1 + 3X2 ≤ 12
2X1 + X2 ≥ 16
X1 ≥ 0
X2 ≥ 0
Avaliação do objetivo
Maximizar L =
gráfico abaixo.
2X1 + 5X2 na região de soluções do
Verificamos do gráfico que:
1. À medida que atribuirmos valores a L, obtemos retas
paralelas.
2. À medida que o valor de L aumenta, a reta se afasta da
origem do sistema de eixos.
Podemos concluir que pelo ponto P do gráfico teremos a
paralela de maior valor que ainda apresenta um ponto na
região de soluções. Portanto, o ponto P é a solução que
maximiza L na região de soluções dadas.
Como P = (0,6) e L = 2X1 + 5X2, teremos:
L = 2.0 + 5.6 ou Lmáximo = 30
Método Gráfico
Exemplo: Resolver o problema de programação linear:
Minimizar
Z = 2X1 + 3X2
Sujeitos às restrições:
X1 + X2 ≥ 5
5X1 + X2 ≥ 10
X1 ≤ 8
X1 ≥ 0 ;
X2 ≥ 0
Programação Linear:
Formulação e Método Gráfico
com duas variáveis de decisão
Max Vinicius Bedeschi
CRE 6859
Solução Gráfica
Problema de MAXIMIZAÇÃO
Uma fábrica produz dois produtos, A e B, cada qual
processado por duas máquinas M1 e M2. Há restrição
do tempo disponível para a produção em cada uma
das máquinas, e cada um dos produtos consumia um
certo tempo de produção em cada uma das máquinas.
Cada unidade vendida do produto A gerava um lucro
de R$80 e cada unidade do produto B, um lucro de
R$60. Há uma previsão máxima de demanda do
produto B de 3 unidades. O problema está em saber
quantas unidades de A e B devem ser produzidos, de
forma a maximizar o lucro. Na sua formulação final, o
problema havia ficado assim:
Formulação completa
Maximizar 80x + 60y
Sujeito a:
4x + 6y ≤ 24
4x + 2y ≤ 16
0x + 1y ≤ 3
X ≥ 0; Y ≥ 0
4x + 6y ≤ 24
4x + 6y = 24
Y=0  x=6
X=0  y=4
Restrições: horas disponíveis na máquina M1
4x + 2y ≤ 16
4x + 2y = 16
Y=0  x=4
X=0  y=8
Restrição: horas disponíveis na
máquina M2
Temos ainda uma última restrição, que diz respeito à
máxima demanda do produto B, isto é, ao valor
máximo de Y:
0x + 1y ≤ 3
Dessa vez, a região permissível é relativamente simples
de ser encontrada, pois está no espaço abaixo da reta
paralela ao eixo x, passando pelo ponto Y = 3, conforme
o próximo slide.
Restrição: demanda máxima – Produto B
As representações gráficas das três restrições
podem agora ser colocadas em um só gráfico.
Gráfico das restrições: maximização
As três restrições delimitam agora uma região comum,
que é o polígono PQRST; todos os pontos internos a
essa região, ou sobre as retas que a formam, obedecem
simultaneamente a todas as restrições. Os pontos
PQRST são chamados de pontos extremos da região
permissível.
P (x=0; y=0) é o origem dos eixos
Q (x=4; y=0)
T (x=0; y=3)
S (y=3; x=3/2)
R(y=2; x=3)
A solução ótima ao problema está em um dos pontos
extremos da região permissível.
Ponto extremo
Valor de x
Valor de y
Função objetivo
80x + 60y
P
Q
0
4
0
0
0
320
R
S
T
3
3/2
0
2
3
3
360
300
180
O ponto extremo R é, portanto, a solução do nosso
problema de maximização, com x = 3 e y = 2
Movendo a reta paralelamente a si mesma para a direita,
o último ponto a ser encontrado é o p0onto R (ou seja, R é
o ponto extremo mais “extremo”), a nossa solução, com a
reta 80x + 60y assumindo o valor 360.
Retas paralelas à função objetivo:
MAXIMIZAÇÃO
Solução Gráfica
Problema de MINIMIZAÇÃO
A granja Cocoró queria misturar dois tipos de alimentos
(Alimento 1 e Alimento 2) para criar um tipo especial de
ração para suas galinhas poedeiras. Cada 100g do
Alimento 1 possuíam 10g do nutriente X, 50g do
nutriente Y e 40g do nutriente Z. O Alimento 2, por sua
vez, para cada 100g, possuía 20g do nutriente X, 60g
do nutriente Y e 20g do nutriente Z. Cada 100g do
Alimento 1 custavam, para a Granja Cocoró, R$0,60 e
cada 100g do Alimento 2 custavam R$0,80. A ração final
deveria conter, no mínimo, 2 g do nutriente X, 64 g do
nutriente Y e 34 g do nutriente Z. Queríamos obedecer a
essa composição, minimizando ao mesmo tempo o
custo por peso da nova ração.
Formulação completa
Minimizar 0,006x + 0,008y
Sujeito a:
0,1x + 0,2y ≥ 2
0,5x + 0,6y ≥ 64
0,4x + 0,2y ≥ 34
X ≥ 0; Y ≥ 0
Restrição: quantidade mínima do nutriente X na mistura
Restrição: quantidade mínima do nutriente Y na mistura
Restrição: quantidade
mínima do nutriente Y na
mistura
As três restrições delimitam uma região permissível,
aberta à direita, delimitada à esquerda pelos pontos
MNL, pelo eixo y, para valores maiores que M, e pelo
eixo x, para valores maiores que L. Todos os pontos
internos a essa região, ou sobre as retas MN e ML,
obedecem simultaneamente a todas as restrições.
Determinemos as coordenadas dos pontos extremos M,
N e L. Inicialmente, temos, sem dificuldades, as
coordenadas dos pontos M e L:
Gráfico das restrições:
MINIMIZAÇÃO
M (x = 0; y = 170)
L (x = 160; y = 0)
O ponto N é o encontro das retas 0,4x + 0,6y = 64 e
0,5x + 0,2y = 34, que representam os limites mínimos dos
nutrientes Y e Z na mistura. Uma cominação linear entre
as duas equações fornecerá os valor de x e y:
X = 34,5g
Y = 83,6g
Temos três pontos extremos, qual deles dará a
solução ótima?
O ponto extremo N é, portanto, a solução do nosso
problema de minimização, com x = 34,5g e y = 83,6g.
Ponto extremo
Valor de x
M
N
L
0
34,5
160
Função objetivo
Valor de y
0,006x + 0,008y
170
83,6
0
1,36
0,88
0,96
Para identificar graficamente que o ponto N seria o de
melhor solução (mínimo custo da mistura), teria
bastado traçar retas paralelas à função objetivo.
Retas paralelas à função objetivo:
MINIMIZAÇÃO
Movendo a reta paralelamente a si mesma para a
direita, o primeiro ponto a ser encontrado é o ponto N,
com a reta 0,006x + 0,008y assumindo o valor R$0,88.
Programação Linear
Solução Computacional
Max Vinicius Bedeschi
CRE 6859
A Indústria Maximóveis fabrica dois tipos de produtos:
cadeiras e mesas.
Os produtos apresentam as seguintes margens de
contribuição por unidade:
Produto
Margem de Contribuição
por Unidade ($)
Cadeiras
10
Mesas
8
Os produtos são processados por dois departamentos:
montagem e acabamento. Ao passar por esses
departamentos, cada unidade do produto consome
determinado número de horas, conforme indicado na
tabela abaixo:
Consumo de horas pelos
Departamento produtos (em um.)
Cadeiras
Mesas
Montagem
3
3
Acabamento
6
3
Os departamentos apresentam, contudo, limitação em
sua capacidade produtiva, como mostra a tabela abaixo:
Departamento
Capacidade máxima
disponível em horas
Montagem
30
Acabamento
48
Desejamos saber qual é a melhor combinação possível
de cadeiras e mesas a serem produzidas, de forma a
obter a maior margem de contribuição total.
Modelo Completo do problema Indústria Maximóveis
Encontrar os valores para as variáveis de decisão C e M,
de forma a maximizar a função-objetivo:
MCT = 10.C + 8.M
Respeitadas as seguintes
restrições:
3C + 3M ≤ 30
6C + 3M ≤ 48
C ≥ 0; M ≥ 0
Áreas de soluções viáveis definidas pelas restrições
Interseção das áreas de soluções viáveis
Linhas de isossolução
Ponto de solução ótima do problema
Pontos
(0,0)
(0,10)
(8,0)
Função-objetivo
(10.0) + (8.0) =
(10.0) + (8.10) =
(10.8) + (8.0) =
MCT
0
80
80
(6,4)
(10.6) + (8.4) =
92 (melhor solução)
Excel 2003
FERRAMENTAS
SUPLEMENTOS
SOLVER
OK
Excel 2007
Botão do Excel 2007
Opções do Excel
Suplementos
Gerenciar
Suplementos do Excel
Ir para
Suplementos disponíveis  SOLVER
Os dados do problema são informados nas seguintes células:
B5 e C5 – margens de contribuição unitárias dos produtos;
B8 a C9 – tempo gasto pelos produtos em cada departamento;
E8 e E9 – capacidade produtiva dos departamentos.
Parâmetros do Solver
Inclusão das restrições
Representação das restrições do problema
Opções do Solver
Tempo máximo: limita o tempo usado pelo processo de
solução.
Iterações: refere-se ao montante de erro que admitimos entre
o resultado a ser obtido pelo Solver e as metas antes fixadas
nas células de restrição. Quanto maior a precisão exigida
(maior número de casas decimais), maior o tempo gasto pela
ferramenta computacional para solucionar o problema.
Tolerância: essa opção é aplicável apenas aos problemas
com restrições de número inteiro, situação que discutiremos
em um exemplo seguinte deste capítulo.
Convergência: opção aplicável somente nos casos de
problemas não lineares.
Presumir modelo linear: é fundamental que esta opção
seja selecionada nos casos de problemas de Programação
Linear. Indica que todas as relações do modelo do problema
são lineares. Também é selecionada nas situações em que
se deseja uma aproximação linear para um problema não
linear.
Presumir não negativos: a seleção desta opção instrui o
Solver a presumir um limite mínimo de zero para as células
ajustáveis. Esse procedimento dispensa a necessidade de
incluir as restrições do tipo “≥”, uma a uma.
Usar escala automática: esta opção deve ser selecionada,
necessariamente, quando a diferença de grandezas entre os
valores de entradas e os valores de saídas do problema for
muito expressiva. Por exemplo, quando se busca a
maximização da porcentagem da margem de contribuição
(entrada) e o resultado envolve valores de montantes
bastante altos (saídas). Uma sugestão é sempre selecionar
essa alternativa para a solução dos diversos problemas de
PL, procedimento que dispensará a preocupação com um
tipo de situação específica.
Mostrar resultados de iteração: se selecionada, instrui o
Solver a exibir o resultado de cada tentativa de solução do
problema.
Campos “Estimativas”, “Derivadas” e “Pesquisar”:
referem-se a recursos avançados, cuja explicação depende
de conceitos que fogem ao escopo deste livro. No exemplo,
mantivemos para esses campos as definições padrão do
Solver.
Resultados do Solver
Planilha final
As células variáveis indicam a quantidade de itens a
serem produzidos na solução ótima: seis cadeiras e
quatro mesas. Margem de contribuição ótima é de $92.
Relatórios de respostas
Não há sobras
Relatórios de limites
Relatórios de sensibilidade
Análise de sensibilidade. Análise que permite avaliar os
reflexos sobre a solução ótima de eventuais alterações nos
dados e condições do problema, dentro de intervalos
definidos.
Função-objetivo. Expressão matemática por meio da qual se
relacionam as variáveis de decisão e o objetivo a ser atingido.
Linhas de isossolução. Retas nas quais, em todos os seus
pontos, é obtido o mesmo valor para a função-objetivo.
Método Simples. Método matemático que combina conceitos
de álgebra matricial com um conjunto de regras básicas que
levam à solução dos problemas de Programação Linear.
Pesquisa Operacional. Área do conhecimento que fornece um
conjunto de procedimentos voltados para tratar, de forma sistêmica,
problemas que envolvem a utilização de recursos escassos.
Preço sombra (ou sombra preço). Campo do relatório de
sensibilidade do Solver que indica quanto se deixa de ganhar por
não se dispor de mais uma unidade de determinada variável
restritiva.
Programação Linear. Técnica matemática destinada a determinar a
melhor utilização de recursos ilimitados, de forma que uma funçãoobjetivo seja otimizada e sejam satisfeitas determinadas condições
estabelecidas.
Reduzido custo. Informação contida no relatório de sensibilidade
emitido pelo Solver, que pode ser entendida como um “custo de
oportunidade”, indicando quanto se deixa de ganhar (ou perder) por
adotar alternativa diferente da indicada pela solução ótima.
Restrições. Limitações impostas sobre os possíveis valores que
podem ser assumidos pelas variáveis de decisão.
Solver. Ferramenta do software Microsoft Excel que, para
solução dos problemas lineares, utiliza o método simplex com
limites sobre as variáveis e o método de desvio e limite.
Variáveis de decisão. Variáveis que correspondem às decisões
a serem tomadas visando encontrar a solução para o problema
em análise.
Variáveis de folga. Variáveis que representam eventuais folgas
entre limites fixados pelas restrições e o montante efetivamente
definido na solução do problema; introduzidas nas inequações
representativas das restrições, transformam-nas em equações.
Análise dos Relatórios
Max Vinicius Bedeschi
CRE 6859
Relatório de Respostas
Subdividido em três partes:
• Célula de Destino
• Células Ajustáveis
• Restrições
O campo Valor final das células ajustáveis mostra a
solução ótima encontrada pelo Solver: produção de seis
cadeiras e de quatro mesas. O resultado da célula de
destino indica que esse mix de produtos gera uma
margem de contribuição de $92.
O campo Valor original aponta que essas células foram
inicialmente preenchidas com zeros.
O campo Valor da célula aponta o total de horas
utilizadas pelos produtos em cada departamento.
O campo Fórmula contém a expressão representativa de
cada restrição.
O campo Status exibe uma das duas seguintes
mensagens: (1) Agrupar, que significa que não há sobras,
e (2) Não agrupar, indicativa da existência de sobras.
Relatório de Limites
Na primeira parte do relatório, é indicado o valor da
Margem de Contribuição na solução ótima.
Na segunda parte do relatório, destinada às celulas
ajustáveis, mostram-se no campo Valor, as margens
de contribuição unitárias dos produtos. Os campos
Limite inferior e Resultado de destino devem ser
analisados em conjunto.
Considere a linha do relatório correspondente à
Quantidade a produzir de cadeiras. A análise dos campos
correspondentes indica que, mantidas as demais
condições do problema, se reduzirmos a produção de
cadeiras a seu Limite inferior (zero), o Resultado destino
(margem de contribuição) será de $32. Com efeito, na
solução ótima, se deixarmos de produzir cadeiras, a
margem de contribuição total se referirá apenas à
produção de quatro mesas, que têm margem de
contribuição unitária de $8, resultando em $32.
Raciocínio similar deve ser empregado para interpretar a
linha correspondente à Quantidade a produzir de mesas:
quando não são produzidas mesas, a margem de
contribuição total é de $60, relativa à fabricação de seis
cadeiras, com MCU de $10.
A análise do campo Limite superior segue a mesma
lógica. Consideremos, primeiro, a linha referente à
Quantidade a produzir de cadeiras. Os valores dos
campos correspondentes indicam que, na solução ótima,
se produzida a quantidade máxima de 6 unidades de
cadeiras, o Resultado destino será de $92. Ver que esse
é o valor da MCT na solução ótima. Desde que se
mantenha fixa a quantidade de um dos produtos na
solução ótima, não será possível aumentas a quantidade
do outro produto. Verificar que o valor encontrado para a
linha da Quantidade a produzir de mesas também é o
mesmo. Podemos generalizar esses resultados para
todos os problemas de maximização: nos problemas
dessa natureza, o Resultado destino do Limite superior
sempre coincidirá com a solução ótima.
As informações fornecidas pelo relatório de limites
ganham importância à medida que aumentamos o
número de variáveis do problema. Imaginar, por
exemplo, o caso de uma empresa que fabrica 30
diferentes produtos e deseja saber qual seria o valor da
margem de contribuição total caso se decidisse pela
descontinuidade da produção de um desses itens.
Relatório de Sensibilidade
O Relatório de Sensibilidade amplia a solução estática
da programação linear. A análise de sensibilidade
permite incorporar à resposta considerações sobre
eventuais alterações nas condições do problema,
dentro de intervalos definidos.
O Relatório de Sensibilidade é subdividido em duas
partes: uma destinada às celulas ajustáveis e outra, às
restrições.
Análise 1: Quanto às células ajustáveis
O campo Valor final indica as quantidades dos produtos a
serem produzidas na solução ótima. Essa é uma
informação pontual, que, a princípio, depende da
manutenção das condições consideradas na resolução
do problema. Ocorre que os dados do problema estão
sujeitos a alterações em seus valores. No âmbito das
empresas, essas variações ocorrem com certa
freqüência.
A análise de sensibilidade revela que, dentro de
intervalos determinados, a quantidade de produtos a
serem fabricados na solução ótima é mantida, ainda
que se alterem suas MCU. Os intervalos são definidos
com informações dos campos Permissível decréscimo
e Permissível acréscimo. Por exemplo, a MCU das
cadeiras é de $10. É possível afirmar que essa margem
de contribuição unitária pode variar de $8 ($10 –
permissível decréscimo de $2) a $16 ($10 + permissível
acréscimo de $6) que a quantidade de cadeiras
prevista na solução ótima não se altera.
A mesma afirmação pode ser feita quanto à variação da
margem de contribuição das mesas: a quantidade de
quatro mesas a serem produzidas, conforme indicado
na solução ótima, mantém-se desde que a MCU do
produto varie dentro do intervalo de $5 ($8 –
permissível decréscimo de $3) a $10 ($8 + permissível
acréscimo de $2).
A referida análise é válida desde que consideremos
apenas a margem de contribuição de um dos produtos
que varia dentro do intervalo correspondente, enquanto
mantemos constante a margem do outro produto.
Outra situação em que a solução ótima não se altera
refere-se aos casos de aumentos ou diminuições
simultâneas nas margens de contribuição unitárias dos
produtos, desde que essas alterações se verifiquem
dentro dos intervalos antes definidos.
Os valores contidos no campo Reduzido Custo indicam
qual o reflexo provocado no “objetivo coeficiente” (MCT,
em nosso caso) pela opção por alternativas diferentes
da indicada na solução ótima. Pode ser entendido como
um “custo de oportunidade”; mostra quanto se está
deixando de ganhar (ou perder) por desprezar
determinada alternativa.
O “reduzido custo” é zero para as variáveis que fazem
parte da solução ótima.
Análise 2: Quanto às restrições
O campo Sombra preço (ou Preço sombra) indica quanto
se deixa de ganhar por não se dispor de mais uma
unidade de determinada variável restritiva.
Por exempLO, O SOBRE PREÇO DO Departamento de
Montagem é de $2. Isso significa que, caso o
departamento dispusesse de 31 horas, aos invés das 30
atuais, a margem de contribuição da empresa passaria
de $92 para $94. Esse tipo de análise é válido,
logicamente, desde que se mantenham as demais
condições do problema.
O preço sombra indica qual a perda provocada pela diminuição
de uma unidade em uma restrição específica. Por exemplo, a
MCT diminuiria dos atuais $92 para $90, caso a capacidade do
Departamento de Montagem fosse diminuída em uma hora. O
mesmo raciocínio é válido para a análise do Departamento de
Acabamento.
Os valores do preço sombra são válidos para determinados
intervalos. O raciocínio para definição desses intervalos é similar
ao utilizado para o Objetivo coeficiente, considerando-se os
campos Permissível acréscimo e Permissível decréscimo. Assim,
podemos afirmar que o preço-sombra de $2 é mantido nas
variações na quantidade de horas do Departamento de
Montagem que se processarem no intervalo que vai de 24 horas
(30 horas menos permissível decréscimo de 6 horas) a 48 horas
(30 horas + permissível acréscimo de 18 horas)
O preço sombra possui importante conteúdo
informacional, à medida que permite a comparação dos
ganhos que advêm da ampliação da capacidade restritiva
da empresa com os eventuais custos envolvidos. A
Indústria Maximóveis poderia comparar, por exemplo, o
ganho de $40 em sua MCT, proporcionado pelo aumento
de 20 horas na capacidade produtiva do Departamento
de Montagem, com os custos que adviriam dessa
ampliação.