Azetatos de Pesquisa Operacional

Prévia do material em texto

Pesquisa Operacional
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 
optimização da operação do sistema.
Fases de um Estudo em P.O.
I. Formulação do problema
II. Construção do modelo do sistema
III. Cálculo da solução através do modelo
IV. Teste do modelo e da solução
V. Estabelecimento de controlos da solução
VI. Implantação e acompanhamento
I. 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.
II. 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 controlo 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 controlo 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.
III. 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.
IV. 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.
V. Estabelecimento de controlos 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.
VI. 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 = 21 32 xx 
Restrições técnicas:
206
1034
21
21


xx
xx
Restrições de não 
negatividade:
0
0
2
1


x
x
As variáveis controladas ou variáveis de decisão são X
1
e X
2
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?
Programação 
de produção
Programação de 
investimento
Quantidades a 
produzir no período
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.
Problema Variáveis de decisão
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 P
1
e P
2
. O lucro unitário do produto P
1
é 
de 1.000 unidades monetárias e o lucro unitário de P
2
é de 1.800 unidades 
monetárias. A empresa precisa de 20 horas para fabricar uma unidade de P
1
e 
de 30 horas para fabricar uma unidade de P
2
. 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 P
1
e 30 unidades anuais para P
2
. 
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
Restrições técnicas:
3040
12003020
2
1
21



x
x
xx
Restrições de não negatividade:
0
0
2
1


x
x
Resumo do modelo: max L = 1000X1 + 1800X2
Sujeito a:
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
Restrições técnicas:
3666
3284
21
21


xx
xx
Restrições de não negatividade:
0
0
2
1


x
x
Resumo do modelo: min C = 3X1 + 2,5 X2
Sujeito a:
FUNÇÃO OBJETIVO:
Problema de
MAXIMIZAÇÃO
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 $80 e cada unidade do
produto B, um lucro de $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
A e B 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 
em M1
Horas gastas 
em M2
Demanda 
máxima
Lucro unitário 
(R$)
A 4 4 ilimitada 80
B 6 2 3 60
Horas disponíveis 24 16
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.
Função objectivo
80x + 60y
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:
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: y ≤ 3
Restrições de não-negatividade
X ≥ 0; Y ≥ 0
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 = $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
EXEMPLO
A Granja Cumbex 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 Cumbex, $0,60 e cada 100g do
alimento 2 custam $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 $0,60 $0,80
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
Função objetivo
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 $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
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 = 2X1 + 5X2 na região de soluções do 
gráfico abaixo.
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
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 $80 e cada unidade do produto B, um lucro de $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
Restrições: horas disponíveis na máquina M1
4x + 6y ≤ 24
4x + 6y = 24
Y=0  x=6
X=0  y=4
Y=0  x=4
X=0  y=8
Restrição: horas disponíveis na máquina M2
4x + 2y ≤ 16
4x + 2y = 16
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
Gráfico das restrições: maximização
As representações gráficas das três restrições 
podem agora ser colocadas em um só gráfico.
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 óptima 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 0 0 0
Q 4 0 320
R 3 2 360
S 3/2 3 300
T 0 3 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 Cumbex 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 Cumbex, $0,60 e cada
100g do Alimento 2 custavam $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 óptima?
O ponto extremo N é, portanto, a solução do nosso 
problema de minimização, com x = 34,5g e y = 83,6g.
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.
Ponto extremo Valor de x Valor de y
Função objetivo
0,006x + 0,008y
M 0 170 1,36
N 34,5 83,6 0,88
L 160 0 0,96
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
$0,88.
Programação Linear
Solução Computacional
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:
Departamento
Consumo de horas pelos
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çõesInterseção das áreas de soluções viáveis
Linhas de isossolução
Ponto de solução óptima do problema
Pontos Função-objetivo MCT
(0,0) (10.0) + (8.0) = 0
(0,10) (10.0) + (8.10) = 80
(8,0) (10.8) + (8.0) = 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 óptima: seis cadeiras e quatro mesas.
Margem de contribuição óptima é 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
óptima 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ção-objetivo 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 óptima.
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
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 óptima 
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 óptima.
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 óptima, 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 óptima, 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 óptima. Desde que se mantenha fixa a quantidade de um dos
produtos na solução óptima, 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 óptima.
As informações fornecidas pelo relatório de limites ganham importância à
medida que aumentamoso 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 óptima. 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 óptima é
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 óptima 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 óptima, 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 óptima 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 óptima. 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
óptima.
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.
Método Simplex
É um procedimento iterativo que permite ir melhorando a
solução de um PPL a cada passo. O processo termina
quando não é possível seguir melhorando uma
determinada solução.
Método Simplex
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 4x 3R : 
22 12x 2R : 
1 23 2 18x x 1R : 
1x 
2x 
(0,0) 
(0,6) 
(6,0) 
(4,3) 
(2,6) 
(0,9) 
(4,0) 
(4,6) 
Parte do valor da F.O. de um 
vértice qualquer que pertença 
a o espaço de soluções 
viáveis.
É um procedimento iterativo que permite ir melhorando a solução de um
PPL a cada passo. O processo termina quando não é possível seguir
melhorando uma determinada solução.
Caminha pelos vértices até 
encontrar uma solução que não 
possua soluções vizinhas melhores 
que ela
Método Simplex
A solução óptima pode não existir:
 Quando não há uma solução viável (restrições incompatíveis);
 Quando não há um valor máximo (ou mínimo) da F.O. (1 ou mais
variáveis tendem ao infinito e as restrições continuarem sendo
satisfeitas).
Fundamentos
O modelo de um PPL pode ser resolvido pela solução de um sistema de equações
lineares
Transformação de um PPL em um sistema de equações equivalentes
1 2
1
2
1 2
1 2
3 5
:
4
2 12
3 2 18
, 0
MAX Z x x
sujeito a
x
x
x x
x x
 


 

FORMA CANÔNICA
1 2
1 1
2 2
1 2 3
1 2 1 2 3
3 5
:
4
2 12
3 2 18
, , , , 0
MAX Z x x
sujeito a
x f
x f
x x f
x x f f f
 
 
 
  

FORMA PADRÃO
Procedimentos (forma canônicaforma padrão)
1 2
1 2
1 2
1 2
Minimizar Z 3 2
sujeito a:
 5 4 14
3 4 8
, 0
x x
x x
x x
x x
 
 
 

Para restrições de desigualdade “”:
A conversão é feita adicionando à equação uma variável artificial fj0.
1 2Minimizar Z 3 2
sujeito a:
x x 
1 2 23 4 8x x f  
14
1 25 4x x
1f
1 2 1 5 4 14x x f  
8
1 23 4x x
2f
1 2 1 2, , , 0x x f f 
Para restrições de desigualdade “”:
A conversão é feita subtraindo à equação uma variável artificial fj0.
Procedimentos (forma canônicaforma padrão)
FORMA CANÔNICA FORMA PADRÃO
1 2
1
2
1 2
1 2
3 5
:
4
2 12
3 2 18
, 0
MAX Z x x
sujeito a
x
x
x x
x x
 


 

1 2
1 1
2 2
1 2 3
1 2 1 2 3
3 5
:
4
2 12
3 2 18
, , , , 0
MAX Z x x
sujeito a
x f
x f
x x f
x x f f f
 
 
 
  

O problema se transformou em encontrar
uma solução de um sistema de equações
lineares que maximize a F.O.
Variáveis: n=5
Restrições: m=3
n > m
Método de Enumeração das Soluções Básicas
Analisando, podemos dizer que atribuir
zero a uma variável significa não
produzir um dos produtos ou utilizar toda
a disponibilidade de recursos.
O número de 
soluções básicas 
possíveis 
1 2
1 1
2 2
1 2 3
1 2 1 2 3
3 5
:
4
2 12
3 2 18
, , , , 0
MAX Z x x
sujeito a
x f
x f
x x f
x x f f f
 
 
 
  

(n-m) variáveis iguais a zero  solução básica
 
!
C
! !
n
m
n n
m m n m
 
  
   
5
3
5 5!
C 10
3 3! 2 !
 
   
 
soluções 
básicas 
possíveis 
Método de Enumeração das Soluções Básicas
Variáveis não básicas: São as variáveis zeradas,
igual a (n-m) variáveis.
1 2
1 1
2 2
1 2 3
1 2 1 2 3
3 5
:
4
2 12
3 2 18
, , , , 0
MAX Z x x
sujeito a
x f
x f
x x f
x x f f f
 
 
 
  

Variáveis básicas: São as variáveis cujos valores
são calculados pelo sistema de equações.
1ª Combinação:Variáveis Não Básicas: 1 2( , ) (0,0)x x 
Variáveis Básicas: 1 2 3( , , ) (4,12,18)f f f 
Solução Básica: 1 2 1 2 3( , , , , ) (0,0,4,12,18)x x f f f  Solução Viável !!! 0Z 
Método de Enumeração das Soluções Básicas
2ª Combinação:
Variáveis Não Básicas: 1 1( , ) (0,0)x f 
Variáveis Básicas: 2 2 3( , , )x f f 
Solução Básica: Não existe !!!
Não existe Base Associada !!!!
3ª Combinação:
Variáveis Não Básicas: 1 2( , ) (0,0)x f 
Variáveis Básicas: 2 1 3( , , ) (6,4,6)x f f 
Solução Básica: 1 2 1 2 3( , , , , ) (0,6,4,0,6)x x f f f  Solução Viável !!! 30Z 
4ª Combinação:
Variáveis Não Básicas: 1 3( , ) (0,0)x f 
Variáveis Básicas: 2 1 2( , , ) (9,4, 6)x f f  
Solução Básica: 1 2 1 2 3( , , , , ) (0,9,4, 6,0)x x f f f   Solução Inviável !!!
Continuar .......
Método de Enumeração das Soluções Básicas
Solução Básica
(x1, x2, f1, f2, f3)
F.O. Observação
1 (0,0,4,12,8) 0 Viável
2 ---- ---- Não existe
3 (0,6,4,0,6) 30 Viável
4 (0,9,4,-6,0) ---- Inviável
5 (4,0,0,12,6) 12 Viável
6 ---- ---- Não existe
7 (6,0,-2,12,0) ---- Inviável
8 (4,6,0,0,-6) ---- Inviável
9 (4,3,0,6,0) 27 Viável
10 (2,6,2,0,0) 36 Viável
Método de Enumeração das Soluções Básicas
Solução Básica
(x1, x2, f1, f2, f3)
F.O. Observação
1 (0,0,4,12,8) 0 Viável
2 ---- ---- Não existe
3 (0,6,4,0,6) 30 Viável
4 (0,9,4,-6,0) ---- Inviável
5 (4,0,0,12,6) 12 Viável
6 ---- ---- Não existe
7 (6,0,-2,12,0) ---- Inviável
8 (4,6,0,0,-6) ---- Inviável
9 (4,3,0,6,0) 27 Viável
10 (2,6,2,0,0) 36 Viável
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
1 4x 3R : 
22 12x 2R : 
1 23 2 18x x 1R : 
1x 
2x 
(0,0) 
(0,6) 
(6,0) 
(4,3) 
(2,6) 
(0,9) 
(4,0) 
(4,6) 
Método de Enumeração das Soluções Básicas
No problema vimos que n=5 (número de variáveis) e m=3 (número de restrições)
tem
 
5
3
5 5!
C 10
3 3! 2 !
 
   
 
soluções básicas possíveis 
No caso de n=10 e m=5 teremos:
 
10
5
10 10!
C 252
5 5! 5 !
 
   
 
No caso de n=20 e m=10 teremos:
 
20
10
20 20!
C 184.756
10 10! 10 !
 
   
 
Problemas de grande porte
Simplex!!!
Desenvolvimento do Método Simplex
Problemas Reais
Método gráfico e 
enumeração
Inviável
Sistemática?
 Qual o sistema de equações que deve ser resolvido;
 Qual é o próximo sistema a ser resolvido que
fornecerá uma solução melhor que os anteriores;
 Como identificar uma solução óptima, uma vez que
tenhamos encontrado.
Método Simplex - Passo 1 
Transformar o PPL da sua forma Canônica para sua forma Padrão.
FORMA CANÔNICA
1 2
1
2
1 2
1 2
3 5
:
4
2 12
3 2 18
, 0
MAX Z x x
sujeito a
x
x
x x
x x
 


 

FORMA PADRÃO
1 2
1 1
2 2
1 2 3
1 2 1 2 3
3 5
:
4
2 12
3 2 18
, , , , 0
MAX Z x x
sujeito a
x f
x f
x x f
x x f f f
 
 
 
  

Método Simplex - Passo 2 
Montar um quadro para ordenarmos as operações, colocando
neles apenas os coeficientes das variáveis.
1 23 5 0MAX Z x x  
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
f2 0 2 0 1 0 12
f3 3 2 0 0 1 18
Z -3 -5 0 0 0 0
1 2
1 1
2 2
1 2 3
1 2 1 2 3
3 5
. . 4
2 12
3 2 18
, , , , 0
MAX Z x x
s a x f
x f
x x f
x x f f f
 
 
 
  

Quadro Inicial
A solução inicial será
sempre obtida fazendo
as variáveis originais do
modelo iguais a zero e
achando o valor das
demais.
Método Simplex - Passo 3 
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
f2 0 2 0 1 0 12
f3 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Quadro Inicial
 Das variáveis não básicas na primeira solução, qual deve-se tornar positiva ?
 Das 3 variáveis básicas na primeira solução, qual deverá ser anulado?
Deve ser a variável que MAIS CONTRIBUI para o lucro, o
maior modulo.
Entra: x2
4/0=
12/2=6
18/2=9
Será aquela associada à linha que tiver o menor quociente entre o
elemento da última coluna e o correspondente elemento da coluna de
entrada ou Pivot.
Sai: f2
Método Simplex - Passo 3 
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
f2 0 2 0 1 0 12
f3 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Quadro Inicial
Pivot
Equação Pivot
Para a mudança da base (na busca por outra solução) emprega-se 2 operações de cálculo:
1. Na equação do Pivot:
2. Nas demais equações incluindo Z:
Gera uma nova 
solução básica𝑁𝑜𝑣𝑎 𝐸𝑞𝑢𝑎ção Pivot=
𝐴𝑛𝑡𝑖𝑔𝑎 𝐸𝑞𝑢𝑎ção Pivot
𝑁𝑢𝑚𝑒𝑟𝑜 𝑃𝑖𝑣𝑜𝑡
𝑁𝑜𝑣𝑎 𝐸𝑞𝑢𝑎ção= 𝐸𝑞𝑢𝑎ção Anterior−
𝐶𝑜𝑒𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑒 𝑑𝑎
𝐶𝑜𝑙𝑢𝑛𝑎 𝑃𝑖𝑣𝑜𝑡
∗
𝑁𝑜𝑣𝑎 𝐸𝑞𝑢𝑎ção
𝑃𝑖𝑣𝑜𝑡
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1
x2 0 1 0 1/2 0 6
f3
Z
Método Simplex - Passo 3 
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
f2 0 2 0 1 0 12
f3 3 2 0 0 1 18
Z -3 -5 0 0 0 0
𝑁𝑜𝑣𝑎 𝐸𝑞𝑢𝑎ção
𝐴𝑛𝑡𝑒𝑟𝑖𝑜𝑟: 0 2 0 1 0 12
𝑁𝑜𝑣𝑎 𝐸𝑞𝑢𝑎ção Pivot: 0 1 0
1
2
0 6
𝐴𝑛𝑡𝑒𝑟𝑖𝑜𝑟 𝐸𝑞𝑢𝑎ção Pivot
𝑁𝑢𝑚𝑒𝑟𝑜 𝑃𝑖𝑣𝑜𝑡 = 2
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
f3
Z
Método Simplex - Passo 3 
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
f2 0 2 0 1 0 12
f3 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
f3 3 0 0 -1 1 6
Z
Método Simplex - Passo 3 
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
f2 0 2 0 1 0 12
f3 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
f3 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
Método Simplex - Passo 3 
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
f2 0 2 0 1 0 12
f3 3 2 0 0 1 18
Z -3 -5 0 0 0 0
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
f3 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
Método Simplex - Passo 3 
Quadro I
Como nos elementos da ÚLTIMA LINHA (Equação do Z) existe ainda um
NÚMERO NEGATIVO, significa que NÃO CHEGAMOS AINDA À
SOLUÇÃO ÓPTIMA do PPL. Temos que REPETIR o processo.
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 1 0 1 0 0 4
x2 0 1 0 1/2 0 6
f3 3 0 0 -1 1 6
Z -3 0 0 5/2 0 30
Método Simplex - Passo 3 
Quadro I
4/1=4
6/0=
6/3=2
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 0 0 1 1/3 -1/3 2
x2 0 1 0 1/2 0 6
x1 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36
Quadro II
Método Simplex - Passo 3 
Variáveis 
na Solução
Variáveis de Decisão Valores da 
Soluçãox1 x2 f1 f2 f3
f1 0 0 1 1/3 -1/3 2
x2 0 1 0 1/2 0 6
x1 1 0 0 -1/3 1/3 2
Z 0 0 0 3/2 1 36
Quadro II
Como todas as VARIÁVEIS NA ÚLTIMA LINHA tem COEFICIENTES
POSITIVOS foi encontrado a SOLUÇÃO óptima.
1 2x 
2 6x 
SOLUÇÃO 
ÓPTIMA
36Z 
Dualidade
• Seja o PPL, doravante chamado de PPL primal:
• ou, na forma expandida:
0
:..
)(min



x
bAxas
xfxct
njx
mibxaas
xc
j
n
j
ijij
n
j
jj
,...,10
,...,1:.
min
1
1





Dualidade
• Associado a este PPL, existe um PPL, chamado PPL dual:
• ou, na forma expandida: 0
:..
)(max



u
cuAas
xfub
tt
D
miu
njcuaas
ub
i
m
i
jiij
m
i
ii
,...,10
,...,1:.
max
1
1





Dualidade:
Regras de transformação
Primal Dual
MIN
Restrição
 
Variável
MAX
= qq.
 
Variável
 
Restriçãoqq. =
 
Dual Primal
Dualidade:
Vantagens
• Em situações na qual a matriz de coeficientes do primal 
tem maior número de linhas do que de colunas:
Dual
A base no DUAL é menor!!!
Dualidade:
Vantagens
• É possível “cercar” a solução óptima. (Considere um 
PPL primal de minimização)
x* = u*
f(x)
fD(x)
(valor do primal)
(valordo dual)
Dualidade:
Interpretação Económica
• Seja o par de PPL’s:
njx
mibxaas
xfxc
j
n
j
ijij
n
j
jj
,...,10
,...,1:.
)(max
1
1







miu
njcuaas
ufub
i
m
i
jiij
m
i
Dii
,...,10
,...,1:.
)(min
1
1







PRIMAL DUAL
Dualidade:
Interpretação Económica
• Sejam x* e u* soluções óptimas desses PPL’s e seja B* a 
base relativa a essas soluções. Então:



m
i
iiD ubbuufxf
1
**** )()(
 Supondo b variável e derivando em relação a b, 
temos:
*
*)(
u
b
xf



 Então u* é a taxa de variação do valor ótimo da 
função objetivo f(x*) com b. Como u*  0, então f(x*) 
cresce à medida que bi cresce
Dualidade:
Interpretação Económica
• Considere o primal um problema de alocação de recursos,
com m recursos disponíveis nas quantidades b1, b2, ..., bm
com os quais desejamos fabricar n produtos nas
quantidades x1, x2, ..., xn a serem determinadas.
• Cada unidade do produto j consome aij unidades do
recurso i trazendo um retorno de cj unidades monetárias.
• Queremos determinar a quantidade a ser fabricada de
cada produto de modo a maximizar o retorno.
Dualidade:
Interpretação Económica
 Suponha, agora, aumentada em uma unidade a
quantidade disponível do recurso k, isto é, temos (bk
+ 1) unidades.
 Suponha que a base associada permaneça a mesma.
 Neste caso, a nova solução óptima u** do dual
permanece a mesma uma vez que:
u** = u* = (cB*)tB*-1.
 A nova solução óptima x** será:
Dualidade:
Interpretação Económica
*
1
*** )1()( kk
m
ki
i
ii ububxf 


 Isto é, f(x**) – f(x*) = uk*, ou seja, uk* é o incremento
no lucro trazido pelo aumento de uma unidade da
matéria disponível k.
 uk* é chamado shadow price, dual, valor incremental,
efficiency price, valor implícito, etc.
***
1
* )( kk
m
i
ii uxfuub 

Análise de Sensibilidade
(Pós-otimização)
• Seja o sistema Ax=b,com uma base B, e uma função objetivo f(x)
• Seja o quadro genérico do Simplex em uma dada iteração colocado na
forma matricial não canónica
(xR)t (xB)t
(L1) x
B R B b
(L2) (c
R)t (cB)t f(x)
Análise de Sensibilidade
(Pós-otimização)
• Para colocar esse quadro na forma canónica devemos efetuar as
seguintes transformações elementares: L1  B
-1L1
(xR)t (xB)t
(L1) x
B B-1R I B-1b
(L2) (c
R)t (cB)t f(x)
L2  -(c
B)t L1+ L2
Análise de Sensibilidade
(Pós-otimização)
(xR)t (xB)t
(L1) x
B B-1R I B-1b
(L2) (c
R)t - (cB)tB-1R (0)t f(x)-(cB)tB-1b
Seja: Y = B-1R yj = B
-1aj
xB = B-1b 
z = (cB)tB-1R zj = (c
B)tB-1aj
Análise de Sensibilidade
(Pós-otimização)
(xR)t (xB)t
(L1) x
B Y I xB
(L2) (c
R)t - z (0)t f(x)-f(x)
Sendo: f(x) = ctx = (cB)txB + (cR)txR = 
= (cB)txB = (cB)tB-1b 
Análise de Sensibilidade:
Ex. 1 – Carteira de Investimentos
• Uma empresa gerencia recursos de terceiros através da escolha de carteiras de investimentos para diversos
clientes, baseados em bonds de diversas empresas. Um de seus clientes exige que:
• Não mais de 25% do total aplicado deve ser investido em um único investimento;
• Um valor superior ou igual a 50% do total aplicado deve ser investido em títulos de maturidade maiores que 10
anos;
• O total aplicado em títulos de alto risco deve ser, no máximo, de 45% do total investido.
• Considerando a tabela abaixo de retorno, risco e maturidade dos diversos títulos, determine a estratégia
óptima para o investidor de forma que a rentabilidade de sua aplicação seja máxima.
Título Retorno anual 
(%)
Maturidade 
(anos)
Risco
1 8,7 15 1 – Muito baixo
2 9,5 12 3 – Regular
3 12,0 8 4 – Alto
4 9,0 7 2 – Baixo
5 13,0 11 4 – Alto
6 20,0 5 5 – Muito alto
Carteira de Investimentos: Modelo de 
Programação Matemática
100/max 








Titulosj
jj xretorno
Titulosjx j  25



Titulosj
jj maturidadeTitulosjx 10|50



Titulosj
jj riscoTitulosjx 4|45
100
Titulosj
jx
Análise de sensibilidade: Carteira de
Investimentos - Questões
1. Qual o melhor retorno que se pode obter? Quanto se deve aplicar em
cada título para que se tenha o retorno ótimo?
2. Em qual percentual aumentaria o retorno se fosse permitido aplicar 1%
a mais no Título 2? De quanto seria o retorno? Essa regra vale até
quanto?
3. A partir de qual percentual a aplicação no título 3 é vantajosa?
4. Se fosse imposto limitar a aplicação em cada título em 24% para um
dentre os títulos 2, 4 e 6, em qual título deveria ser feita a diminuição
de aplicação? Justifique.
5. Quanto está influenciando a restrição de limitação de aplicação em
título de alto risco? Qual seria o retorno se esta limitação fosse de
49%?
Análise de Sensibilidade:
Ex. 2 – Produção de automóveis
• Uma empresa deve produzir 1000 automóveis. Ela tem quatro fábricas, as
quais, devido a diferenças na mão-de-obra e avanços tecnológicos, as plantas
diferem no custo de produção de cada carro. Elas também utilizam
diferentes quantidades de matéria-prima e mão-de-obra. A tabela abaixo
resume essas informações:
Fábrica Custo ($ mil) Mão-de-Obra Mat. Prima
1 15 2 3
2 10 3 4
3 9 4 5
4 7 5 6
Análise de Sensibilidade
Ex. 2 – Produção de automóveis

Fabricasj
jj xcmin



Fabricasj
jj TotMObraxMObra



Fabricasj
jj x aTotMatPrimMatPrima
 Um acordo trabalhista requer que pelo menos 400 carros sejam produzidos
na fábrica 3. Existem 3300 horas de mão-de-obra e 4000 unidades de
material que podem ser alocas às 4 fábricas. O modelo de programação
matemática que otimiza a produção é:



Fabricasj
jx Producao
0|  jjj AcordoFabricasjAcordox
Análise de sensibilidade:
Ex. 2 – Produção de automóveis
1. Quais são as quantias óptimas de produção? Qual o custo da
produção?
2. Quanto custa produzir mais um veículo? Quanto economizamos
produzindo um veículo a menos?
3. Como mudaria a solução se custasse somente R$8.000,00 para
produzir na fábrica 2? Como ficaria o custo?
4. Quanto estamos dispostos a pagar por uma hora de trabalho?
5. Quanto o acordo está custando? Qual seria a variação no custo
se o acordo fosse de 250 carros?
6. Quanto vale a matéria-prima (conseguir mais uma unidade)?
Quantas unidades estamos dispostos a pagar por esse preço?
7. Até que custo ainda é vantajoso produzir na fábrica 2?