Pesquisa Operacional
na Tomada de Decisões
Programação Não Linear
2ª Edição
Capítulo 7
© Gerson Lachtermacher,2005
Conteúdos do Capítulo
 Programação Não Linear



Aplicações
Solução Gráfica
Resolução no Excel
 Controle de Estoque

Modelo do Lote Econômico
 Problemas de Localização

Caso LCL Telecom S.A.
Capítulo 7
Programação Não Linear
 De forma geral um problema de programação não linear
tem a seguinte forma:
Max ou Min f (x)
st
g i (x)  bi para i  1,2,..., m
x  0 onde x = ( x1 , x2 ,..., xn )
 Nenhum algoritmo resolve todos os problemas que
podem ser incluídos neste formato.
Capítulo 7
Programação Não Linear
Aplicações
 Problemas de Mix de Produtos em que o “lucro” obtido
por produto varia com a quantidade vendida.
 Problemas de Transporte com custos variáveis de
transporte em relação à quantidade enviada.
 Seleção de Portfolio com Risco
Capítulo 7
Programação Não Linear
Solução Gráfica
 Considere o Problema de Programação Linear e sua
solução gráfica
Max Z  3x1 + 5x2
s. r. x1  4
2x2  12
3x1+ 2x2  18
x1  0, x2  0
x2
(0;6)
Solução
Viável
(0;0)
Capítulo 7
(2;6)
1
(4;3)
(4;0)
x1
Programação Não Linear
Solução Gráfica
 Considere o Problema e sua solução gráfica.
x2
Max Z  3x1 + 5 x2
s.t. x1  4
9 x + 5 x  216
2
1
2
2
x1  0, x2  0
Capítulo 7
(2;6)
6
4
Solução
Viável
2
0
0
1
2
3
4 x1
Programação Não Linear
Solução Gráfica
 A solução ótima:




é a mesma do problema
linear.
continua na fronteira do
conjunto de soluções
viáveis.
não é mais um extremo do
conjunto de soluções
viáveis, mas poderia ainda
ocorrer em um ponto
extremo.
Não existe a simplificação
(enumeração)
existente
em Programação Linear
Capítulo 7
x2
(2;6)
6
4
Solução
Viável
2
0
0
1
2
3
4 x1
Programação Não Linear
Solução Gráfica
2
2
+
MaxZ=126x1 9 x1 182x2 13x2
s. r. x1  4
2x2  12
3x1+ 2 x2  18
x2
(0;6)
x1  0, x2  0
Solução
Viável
(0;0)
Capítulo 7
(2;6)
(4;3)
(4;0)
x1
Programação Não Linear
Solução Gráfica
 A função objetivo é uma equação quadrática.
Z=126 x1 - 9 x12 + 182 x2 - 13x22
2
2
2
2
 2  182 
 2  126 
 182  
 126  
 182 
 126 
Z - 9
 
 x2 + 
  - 13 x2 - 
 x1 + 
  -9  x1 - 
 - 13
 







 26 
 18 
26
13
18
9




 
Para Z = 907  171 = 9 x - 7  + 13 x - 7 
Para Z = 857  221 = 9 x - 7  + 13 x - 7 
Para Z = 807  271 = 9 x - 7  + 13 x - 7 

Z - 441 - 637  -9  x1 - 7 - 13  x2 - 7
2
2
2
2
2
1
2
2
2
1
2
2
1
Capítulo 7
2
Programação Não Linear
Solução Gráfica
x2
Max Z = 857=126x1 - 9 x12 + 182 x2 - 13x22
6
4
2
Z = 907
2
Capítulo 7
Z = 857
Solução
Viável
Z = 807
4
x1
Programação Não Linear
Solução Gráfica
2
2
+
Max Z=54 x1 9 x1 78 x2 13x2
s. r. x1  4
2x2  12
3x1+ 2 x2  18
x2
(0;6)
Solução
Viável
x1  0, x2  0
(0;0)
Capítulo 7
(2;6)
(4;3)
(4;0)
x1
Programação Não Linear
Solução Gráfica
 A função objetivo é uma equação quadrática
Z=54 x1 - 9 x12 + 78 x2 - 13x22
2
2
2
2
 2  54 
 2  78
 54 
 78 
 54  
 78  
Z - 9  - 13   -9  x1 -   x1 +    - 13 x2 -   x2 +   
18
26
9
18 
13
26 



  
Para Z = 198  0 = 9x - 3 + 13x - 3 
Para Z = 189  9 = 9x - 3 + 13x - 3 
Para Z = 162  36 = 9x - 3 + 13x - 3 
Z - 81 - 117  -9 x1 - 3 - 13 x2 - 3
2
2
2
2
1
2
2
2
1
2
2
1
Capítulo 7
2
2
Programação Não Linear
Solução Gráfica
Max Z  198=54 x1 - 9 x12 + 78 x2 - 13x22
x2
6
Z = 189
4
Solução no interior do
Z = 198 conjunto de soluções
viáveis e não mais na
fronteira do conjunto
3
2
Solução
Viável
2
Capítulo 7
Z = 162
3
4
x1
Programação Não Linear
 A solução ótima de um problema de programação não
linear(NLP), diferentemente de um problema de LP,
pode ser qualquer ponto do conjunto de soluções
viáveis.
 Isso torna os problemas de NLP muito mais complexos,
obrigando os algoritmos de solução a pesquisar todas as
soluções viáveis.
Capítulo 7
Programação Não Linear
Excel
 O Excel utiliza o algoritmo GRG (generalized reduced
gradient) para chegar à solução para um dado
problema.
 O algoritmo não garante que a solução encontrada é
uma solução global.
 O Solver às vezes tem dificuldades de achar soluções
para problemas que tenham condições iniciais para as
variáveis iguais a zero. Uma boa medida é começar a
otimização com valores diferentes de zero para as
variáveis de decisão.
Capítulo 7
Programação Não Linear
Excel
 Uma maneira prática para tentar minorar o problema de
máximos e mínimos locais é começar a otimização de
diversos pontos iniciais, gerados aleatoriamente.
 Se todas as otimizações gerarem o mesmo resultado,
você pode ter maior confiança, não a certeza, de ter
atingido um ponto global.
Capítulo 7
Programação Não Linear
Controle de Estoque
 Um dos modelos mais simples de controle de estoque é
conhecido como Modelo do Lote Econômico.
 Esse tipo de modelo assume as seguintes hipóteses

A demanda (ou uso) do produto a ser pedido é praticamente
constante durante o ano.

Cada novo pedido do produto deve chegar de uma vez no
exato instante em que este chegar a zero.
Capítulo 7
Programação Não Linear
Controle de Estoque
 Determinar o tamanho do pedido e a sua periodicidade
dado os seguintes custos:



Manutenção de Estoque – Custo por se manter o capital no
estoque e não em outra aplicação, rendendo benefícios
financeiros para a empresa.
Custo do Pedido – Associado a trabalho de efetuar o pedido
de um determinado produto.
Custo de Falta – Associado a perdas que venham a decorrer
da interrupção da produção por falta do produto.
Capítulo 7
Programação Não Linear
Controle de Estoque
50
Demanda Anual =100
Lote=50, Pedidos = 2
Estoque Médio = 25
Demanda Anual =100
Lote=25,Pedido= 4
Estoque Médio = 12,5
25
25
12,5
6
Capítulo 7
12
meses
3
6
9
12
meses
Programação Não Linear
Controle de Estoque
 Variável de Decisão
Constante
Q – Quantidade por Pedido
D
Q
 Função Objetivo = Custo Total  D  C +  S +  C m
Q
2
Onde:
D = Demanda Anual do Produto
C = Custo Unitário do Produto
S= Custo Unitário de Fazer o Pedido
Cm= Custo unitário de manutenção em estoque por ano
Capítulo 7
Caso LCL Computadores
 A LCL Computadores deseja diminuir o seu estoque de
mainboards. Sabendo-se que o custo unitário da
mainboard é de R$50,00, o custo anual unitário de
manutenção de estoque é de R$20,00 e o custo unitário
do pedido é de R$10,00, encontre o lote econômico
para atender a uma demanda anual de 1000 mainboards.
Capítulo 7
Caso LCL Computadores
Capítulo 7
Caso LCL Computadores
Capítulo 7
Caso LCL Computadores
Capítulo 7
Caso LCL Computadores
 Na solução apresentada do lote econômico,
quantidade de pedidos por ano é fracionário, já que
Demanda Anual 1000
nº de lotes 

 31,25
Tamanho do Lote
32
 Isso não representa um problema
Capítulo 7
a
Programação Não Linear
Problemas de Localização
 Um problema muito usual na área de negócios é o de
localização de Fábricas, Armazéns, Centros de
distribuição e torres de transmissão telefônica.
 Nesses problemas devemos Minimizar a distância total
entre os centros consumidores e o centro de
distribuição, reduzindo assim teoricamente o custo de
transporte ou perdas de transmissão.
 O usual é se colocar um eixo cartesiano sobre um mapa
e determinar a posição dos centro consumidores em
relação a uma origem aleatória.
Capítulo 7
Caso LCL Telefonia Celular S.A.
 O Gerente de Projetos da LCL Telefonia Celular S.A., tem que
localizar uma antena de retransmissão para atender a três
localidades na Baixada Fluminense. Por problemas técnicos a
antena não pode estar a mais de 10 km do centro de cada cidade.
Considerando as localizações relativas abaixo, determine o
melhor posicionamento para a torre.
Localidade
X
Y
Nova Iguaçu
-5
10
Queimados
2
1
Duque de Caxias
10
5
Capítulo 7
Caso LCL Telefonia Celular S.A.
Y
Nova Iguaçu
(-5,10)
Queimados
(2,1)
Capítulo 7
Duque de
Caxias
(10,5)
X
Caso LCL Telefonia Celular S.A.
 Variáveis de Decisão


X – Coordenada no eixo X da torre de transmissão
Y – Coordenada no eixo Y da torre de transmissão
 Função-objetivo
3
Min  ( xi - X ) + ( yi - Y )
2
i 1
Capítulo 7
2
Caso LCL Telefonia Celular S.A.
 Restrições de Distância
2
2
+
( x1 X ) ( y1 Y )  10
2
2
+
( x2 X ) ( y2 Y )  10
2
2
+
( x3 X ) ( y3 Y )  10
Capítulo 7
Caso LCL Telefonia Celular S.A.
Modelo no Excel
=SOMA(D2:D4)
Capítulo 7
Caso LCL Telefonia Celular S.A.
Parametrização
Capítulo 7
Caso LCL Telefonia Celular S.A.
Solução
Capítulo 7