Ch 7 Programacao Nao Linear [Fávero] (2013)

Prévia do material em texto

Capítulo 7
Programação Não Linear
Se chegarmos a descobrir uma teoria completa, com o tempo esta deveria ser compreensível 
para todos e não só para os cientistas. Então, todo mundo poderia discutir sobre a existência do 
ser humano e do Universo. Se encontrarmos a resposta para isso, seria o triunfo final da razão 
humana.
Stephen Hawking
Ao final deste capítulo, você será capaz de:
 � Compreender e diferenciar as características dos problemas de programação não linear, estabelecendo 
as circunstâncias a partir das quais eles devem ser utilizados, em função das características do 
problema e dos objetivos de pesquisa. 
 � Entender a importância da programação não linear para a tomada de decisão.
 � Classificar os problemas de programação não linear (PNL) e conhecer as peculiaridades de cada um 
deles, incluindo PNL irrestrita (com uma única ou mais variáveis) e PNL com restrição (programação 
côncava, convexa, quadrática e separável).
 � Conhecer os métodos de solução para cada classe de problemas de programação não linear.
 � Compreender como os multiplicadores de Lagrange podem ser aplicados para resolver problemas de 
PNL com restrições de igualdade.
 � Compreender como as condições de Karush-Kuhn-Tucker (KKT) podem ser aplicadas para verificar 
se uma determinada solução de um problema de PNL é ou não uma solução ótima local.
 � Conhecer e modelar problemas reais de programação não linear, incluindo o modelo do lote 
econômico de compra, o problema de localização de facilidades e o problema de seleção de carteiras 
de investimentos.
 � Resolver problemas de programação não linear pelo Solver do Excel.
424
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
7.1 Introdução
Conforme visto no Capítulo 1, a formulação geral de um modelo de programação matemática pode 
ser representada como:
 
 
 
 (7.1)
{ }
{ }
{ }
=
≤ = ≥
≤ = ≥
≤ = ≥
M M M
1 2
1 1 2 1
2 1 2 2
1 2
max ou min z ( , ,..., )
sujeito a:
 ( , ,..., ) , , 
 ( , ,..., ) , , 
 
 ( , ,..., ) , ,
n
n
n
m n
f x x x
g x x x b
g x x x b
g x x x
≥K1 2
 
 , , , 0 (restrição de não negatividade)
m
n
b
x x x
onde:
xj são as variáveis de decisão, j=1, 2,...,n
f (x1,x2,...,xn) é a função objetivo, função das variáveis de decisão xj
gi (x1,x2,...,xn) representa a restrição i, i=1, 2,...,m, função das variáveis de decisão xj
bi é o termo independente, constante ou quantidade de recursos disponíveis da i-ésima restrição
Em um problema de programação não linear (PNL), pelo menos a função objetivo f ou uma 
das restrições gi (i=1, 2,...,m) do modelo descrito em (7.1) será representada por uma função não linear 
das variáveis de decisão. Uma função é dita linear quando envolve apenas constantes e termos com 
variáveis de primeira ordem. Caso contrário, a função é dita não linear. Por exemplo, a função objetivo 
2
1 2 3 1 2 3( , , ) 3 4f x x x x x x= + corresponde a uma função não linear. 
Os problemas de PNL são difíceis de serem resolvidos, porém, são muito comuns na prática. Os 
algoritmos de PNL são mais diversos e mais complexos, comparados aos de programação linear ou 
programação binária e/ou inteira (Colin, 2007). Por essa razão, não entraremos no rigor teórico de cada 
algoritmo, mas sim como ele está situado no contexto da PNL. 
Os problemas de programação não linear podem ser classificados como: PNL irrestrita (com uma 
única variável ou com múltiplas variáveis) e PNL com restrição (inclui programação côncava, convexa, 
quadrática e separável). Os problemas de PNL irrestrita serão estudados na Seção 7.4. Já os problemas de 
PNL com restrição serão estudados na Seção 7.5. Para cada problema, discutiremos os principais métodos 
de solução encontrados na literatura.
Ainda na Seção 7.5, estudaremos como os multiplicadores de Lagrange podem ser aplicados para 
resolver problemas de PNL com restrições de igualdade, bem como as condições de Karush-Kuhn-Tucker 
(KKT) podem ser aplicadas para verificar se uma determinada solução de um problema de PNL é ou não 
uma solução ótima local.
Apresentaremos também problemas reais de programação não linear, incluindo o modelo do lote 
econômico de compra, o problema de localização de facilidades e o problema de seleção de carteiras de 
investimentos, assim como a resolução dos mesmos pelo Solver do Excel.
7.2 Solução Gráfica e Complexidade dos Problemas de Programação Não Linear
Um dos teoremas apresentados no Capítulo 3 afirma que a solução ótima de um problema de 
programação linear está sempre associada a um ponto extremo do conjunto de soluções viáveis. Esse 
teorema não é válido para problemas de PNL. Aqui, a solução ótima pode assumir qualquer valor no 
425
Capítulo 7 I Programação Não Linear
conjunto de soluções factíveis, seja na fronteira (mas não necessariamente em um ponto extremo) ou 
no interior da região viável. Essa característica aumenta a complexidade de solução dos problemas de 
programação não linear. Ilustraremos a seguir alguns exemplos com essas características, baseados nos 
trabalhos de Hillier e Lieberman (2005) e Lachtermacher (2009).
7.2.1 Função Objetivo Linear e Restrição(ões) Não Linear(es) 
Exemplo 7.1:
Considere o seguinte problema de PNL:
 
 
 (7.2)
= +
+ ≤
≤
≥
1 2
2 2
1 2
1
1 2
max 4 6
sujeito a:
 10 8 128
 3
 , 0
z x x
x x
x
x x
Determine a solução gráfica de (7.2) e verifique se a solução ótima é um ponto extremo da região factível. 
 � Solução:
A solução gráfica de (7.2) está representada na Figura 7.1. 
Figura 7.1 Solução gráfica do Exemplo 7.1.
Repare que o espaço de soluções factíveis passa a ser representado não apenas por retas, incluindo 
também curvas ou funções não lineares (primeira restrição). A solução ótima, nesse caso, não corresponde 
mais a um ponto extremo da região factível, como ocorria nos problemas de PL, mas encontra-se na sua 
superfície.
7.2.2 Função Objetivo Não Linear e Restrições Lineares (Caso 1)
Exemplo 7.2:
Considere o seguinte problema de PNL:
426
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
 
 
 (7.3)
= − + −
+ ≤
≤
≥
22
1 1 2 2
1 2
1
1 2
max 240 24 240 24
sujeito a:
 2 3 18
 6
 , 0
z x x x x
x x
x
x x
Determine a solução gráfica de (7.3) e verifique se a solução ótima é um ponto extremo da região 
factível. 
 � Solução:
Nesse exemplo, todas as restrições são lineares. Por outro lado, a função objetivo é uma função 
quadrática (circunferência), podendo ser reescrita como:
2 2 2 2
1 224( 5) 24( 5) 24 5 24 5z x x= − − − − + × + ×
O centro dessa circunferência encontra-se no ponto (5, 5) – para maiores detalhes ver Boyer (1996).
A solução gráfica de (7.3) está representada na Figura 7.2. 
Figura 7.2 Solução gráfica do Exemplo 7.2.
Pela Figura 7.2, verifica-se que à medida que o valor de z aumenta, o raio da circunferência diminui 
e converge para a origem. Como a solução ótima deve estar no conjunto de soluções viáveis, ela é obtida 
quando a circunferência tangencia a região viável.
Analogamente ao exemplo anterior, a solução ótima também não corresponde a um ponto extremo 
da região factível, como ocorria nos problemas de PL, mas se encontra na sua superfície.
427
Capítulo 7 I Programação Não Linear
7.2.3 Função Objetivo Não Linear e Restrições Lineares (Caso 2)
Pode ocorrer ainda um segundo caso com as mesmas condições do exemplo anterior (função objetivo 
não linear e restrições lineares) em que a solução ótima encontra-seno interior da região viável e não na 
sua superfície.
Exemplo 7.3:
Considere o seguinte problema de PNL:
 
 (7.4)
= − + −
+ ≤
≤
≥
22
1 1 2 2
1 2
1
1 2
max 180 30 180 45
sujeito a:
 2 3 18
 6
 , 0
z x x x x
x x
x
x x
Determine a solução gráfica de (7.4) e verifique se a solução ótima é um ponto extremo da região factível. 
 � Solução: 
Analogamente ao exemplo anterior, a função objetivo é uma função quadrática (nesse caso, uma 
elipse), podendo ser reescrita como:
2 2 2 2
1 230( 3) 45( 2) 30 3 45 2z x x= − − − − + × + × , cujo centro encontra-se no ponto (3, 2).
A solução gráfica de (7.4) está representada na Figura 7.3. Como as restrições não se alteram em 
relação ao exemplo anterior, o conjunto de soluções factíveis é o mesmo.
Figura 7.3 Solução gráfica do Exemplo 7.3.
Analogamente ao exemplo anterior, verifica-se que à medida que o valor de z aumenta, o tamanho da 
elipse diminui e converge para o centro. Porém, nesse caso, como a origem encontra-se dentro da região 
factível, a solução ótima é o próprio centro.
428
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
Portanto, para os três casos analisados, a solução ótima não corresponde a um ponto extremo da 
região factível, sendo um ponto na superfície ou no interior da região factível. Essa característica torna os 
problemas de PNL muito mais complexos, quando comparados aos problemas de PL, já que um conjunto 
infinito de soluções deve ser testado até se encontrar a solução ótima.
7.3 Funções Convexas e Côncavas
Uma função é dita convexa num conjunto convexo S se para 1x S∀ ∈ e 2x S∀ ∈ verifica-se a condição 
1 2 1 2( (1 ) ) ( ) (1 ) ( )f cx c x cf x c f x+ − ≤ + − , em que 0 1c≤ ≤ .
Já uma função é dita côncava num conjunto convexo S se para 1x S∀ ∈ e 2x S∀ ∈ verifica-se a 
condição 1 2 1 2( (1 ) ) ( ) (1 ) ( )f cx c x cf x c f x+ − ≥ + − , em que 0 1c≤ ≤ .
A Figura 7.4 ilustra o exemplo de uma função convexa e côncava, além de uma função que não é nem 
convexa nem côncava. Uma função ( )f x é convexa se um segmento de reta que une dois pontos dessa 
função está na superfície ou acima dela. Analogamente, uma função ( )f x é côncava se um segmento de 
reta que une dois pontos dessa função está na superfície ou abaixo dela. Por outro lado, se um segmento 
de reta une mais do que dois pontos dessa função, ela não é nem convexa nem côncava.
Figura 7.4 Exemplo de uma função convexa, côncava e nem convexa e nem côncava.
Convexa Côncava Nem convexa nem côncava 
As seguintes propriedades são válidas para funções convexas e côncavas:
– Se ( )f x é convexa, então todo mínimo local será sempre o mínimo global
– Se ( )f x é côncava, então todo máximo local será sempre o máximo global
– Se ( )f x é convexa, então ( )f x− é côncava (e vice-versa)
– Funções lineares são tanto convexas quanto côncavas 
– Se ( )f x é convexa, então ( ) 1/ ( )g x f x= é côncava, ( ) 0x f x∀ <
– Se ( )f x é côncava, então ( ) 1/ ( )g x f x= é convexa, ( ) 0x f x∀ >
– Se ( )f x é estritamente convexa, então possui no máximo um ponto de mínimo
– Se ( )f x é estritamente côncava, então possui somente um ponto de máximo
Os métodos para identificar se uma função é convexa ou côncava variam em função do número de 
variáveis no modelo: uma única variável, duas variáveis e mais de duas variáveis.
429
Capítulo 7 I Programação Não Linear
7.3.1 Funções Convexas e Côncavas com uma Única Variável
Por meio do cálculo da segunda derivada de uma função ( )f x , representada por 
2
2
( )d f x
dx
 ou ''( )f x , 
pode-se determinar se esta é uma função convexa ou côncava em um conjunto convexo S.
Caso 1
Se 
2
2
( )
0
d f x
dx
≥ para x S∀ ∈ , ( )f x é uma função convexa em S.
Caso 2
Se 
2
2
( )
0
d f x
dx
> para x S∀ ∈ , ( )f x é uma função estritamente convexa em S.
Caso 3
Se 
2
2
( )
0
d f x
dx
≤ para x S∀ ∈ , ( )f x é uma função côncava em S.
Caso 4
Se 
2
2
( )
0
d f x
dx
< para x S∀ ∈ , ( )f x é uma função estritamente côncava em S.
Cabe listar duas observações em relação às definições listadas anteriormente:
a) Se ( )f x é uma função linear e, consequentemente, 
2
2
( )
0
d f x
dx
= , a função é simultaneamente convexa 
e côncava em S.
b) Se 
2
2
( )d f x
dx
for positivo para alguns valores de x S∈ e negativo para outros, a função não é nem convexa 
nem côncava em S.
Exemplo 7.4:
Determine se as funções a seguir são convexas (ou estritamente convexas), côncavas (ou estritamente 
côncavas), convexas e côncavas simultaneamente ou nenhuma delas, em um conjunto convexo S.
a) 2( ) 2 4f x x x= +
b) 2( ) 6f x x= − +
c) ( ) 8 3f x x= +
d) 3( ) 4 10f x x x= + −
 � Solução:
a) ''( ) 4 0f x = > → função estritamente convexa em S
b) ''( ) 2 0f x = − < → função estritamente côncava em S
c) ''( ) 0f x = → função convexa e côncava em S
d) ''( ) 6f x x= → função nem convexa nem côncava em S
430
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
7.3.2 Funções Convexas e Côncavas com Duas Variáveis
Para uma função f(x1,x2) com 2 variáveis, determina-se se ela é convexa ou côncava em um conjunto 
convexo S por meio da matriz Hessiana H que corresponde a uma matriz quadrada (2×2) das derivadas 
parciais de segunda ordem da função. Pode ser definida como:
⎡ ⎤∂ ∂⎢ ⎥∂ ∂ ∂⎢ ⎥
=⎡ ⎤⎣ ⎦ ⎢ ⎥∂ ∂⎢ ⎥∂ ∂ ∂⎢ ⎥⎣ ⎦
2 2
2
1 1 2
1 2 2 2
2
2 1 2
 
( ,
 
f f
x x x
H f x x
f f
x x x
em que:
2
2
i
f
x
∂
∂ é a derivada parcial de segunda ordem da função f em relação à variável xi, (i � 1, 2))
2
i j
f
x x
∂
∂ ∂ é a derivada de segunda ordem da função f em relação à xi e xj , respectivamente, i,j =1,2 
tal que i j≠ (primeiramente deriva-se a função f em relação à ix , e depois calcula-se a derivada dessa 
derivada em relação à xj).
A classificação, se uma função é convexa (ou estritamente convexa) ou côncava (ou estritamente 
côncava), depende dos elementos da diagonal principal de H, além do cálculo do seu determinante 
[ ]Det ( )H , conforme mostra a Tabela 7.1. 
Tabela 7.1 Classificação das funções com duas variáveis a partir da matriz H para �x
1
, x
2
 � S
Classificação
2
2
1
f
x
∂
∂
2
2
2
f
x
∂
∂ Det (H)
Convexa 0≥ 0≥ 0≥
Estritamente convexa 0> 0> 0>
Côncava 0≤ 0≤ 0≥
Estritamente côncava 0< 0< 0>
Novamente, cabe listar duas observações em relação à classificação listada anteriormente:
a) Se f(x) é uma função linear e, consequentemente, det (H)=0, 
2
2
1
0
f
x
∂
=
∂
 e 
2
2
2
0
f
x
∂
=
∂
, a função é 
simultaneamente convexa e côncava em S.
b) Se Det (H) < 0 para alguns valores de 1 2,x x S∈ , a função não é nem convexa nem côncava em S.
Exemplo 7.5:
Determine se a função 221 2 1 1 2 1 2 2( , ) 2 4 3 5 2f x x x x x x x x= − + + − − é convexa (ou estritamente convexa), 
côncava (ou estritamente côncava), convexa e côncava simultaneamente ou nenhuma delas, em um 
conjunto convexo S.
431
Capítulo 7 I Programação Não Linear
 � Solução:
A matriz Hessiana de f(x1, x2) pode ser calculada como:
⎡ ⎤∂ ∂⎢ ⎥
−∂ ∂ ∂ ⎡ ⎤⎢ ⎥
= =⎡ ⎤ ⎢ ⎥⎣ ⎦ ⎢ ⎥
−∂ ∂ ⎣ ⎦⎢ ⎥∂ ∂ ∂⎢ ⎥⎣ ⎦
2 2
2
1 1 2
1 2 2 2
2
2 1 2
 
4 4
( , )
 4 4
 
f f
x x x
H f x x
f f
x x x
Primeiramente, verifica-se que os elementos pertencentes à diagonal principal da matriz Hessiana 
são todos negativos.
Já o determinante de 1 2( , )H f x x⎡ ⎤⎣ ⎦ é -4(-4) – (4) (4)= 0. 
Conclui-se, portanto, que f(x1, x2) é uma função côncava em S.
Exemplo 7.6:
Idem para a função 2 21 2 1 2 1 2( , ) 3 2 2f x x xx x x= − + + .
 � Solução:
A matriz Hessiana de f(x1, x2) pode ser calculada como:
⎡ ⎤∂ ∂⎢ ⎥
−∂ ∂ ∂ ⎡ ⎤⎢ ⎥
= =⎡ ⎤ ⎢ ⎥⎣ ⎦ ⎢ ⎥∂ ∂ ⎣ ⎦⎢ ⎥∂ ∂ ∂⎢ ⎥⎣ ⎦
2 2
2
1 1 2
1 2 2 2
2
2 1 2
 
6 2
( , )
 2 4
 
f f
x x x
H f x x
f f
x x x
O determinante de 1 2( , )H f x x⎡ ⎤⎣ ⎦ é –6(4) – (2)(2)= – 28.
Conclui-se, portanto, que f(x1, x2) não é nem convexa nem côncava em S.
7.3.3 Funções Convexas e Côncavas com Múltiplas Variáveis
Para uma função f(x1,x2 ,...,xn) com n variáveis, determina-se se ela é convexa ou côncava por meio do 
cálculo dos determinantes dos menores principais da matriz Hessiana (determinantes das submatrizes 
1×1, 2×2 ,..., n×n de H), representados por Det1,Det2,...Detn , respectivamente:
2
1 2
1
Det
f
x
∂
=
∂ , 
2 2
2
1 1 2
2 2 2
2
2 1 2
 
Det
 
f f
x x x
f f
x x x
∂ ∂
∂ ∂ ∂
=
∂ ∂
∂ ∂ ∂
 ,K , 
∂ ∂ ∂
∂ ∂ ∂ ∂ ∂
∂ ∂ ∂
= ∂ ∂ ∂ ∂ ∂
∂ ∂ ∂
∂ ∂ ∂ ∂ ∂
L
L
M M O M
L
222
2
1 1 2 1
222
2
2 1 2 2
222
2
1 2
 
 
Det
 
 
n
n n
nnn
f f f
x x x x x
f f f
x x x x x
f f f
x x x x x
 
432
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
em que:
2
2
i
f
x
∂
∂ é a derivada parcial de segunda ordem da função f em relação à variável ix , (i=1,...,n)
2
i j
f
x x
∂
∂ ∂ é a derivada de segunda ordem da função f em relação à ix e jx , respectivamente, i, j=1,...,n 
tal que i j≠ (primeiramente deriva-se a função f em relação à xi , e depois calcula-se a derivada dessa 
derivada em relação à xj).
A Tabela 7.2 mostra a classificação das funções com mais de duas variáveis a partir do cálculo dos 
determinantes dos menores principais da matriz H (Det1,Det2,...,Detn).
Tabela 7.2 Classificação das funções com mais de duas variáveis a partir dos determinantes dos menores 
principais da matriz H para �x
i
, x
j
 � S
Classificação Det1 Det2 Det3 Det4 K Detn
Convexa 0≥ 0≥ 0≥ 0≥ K 0≥
Estritamente convexa 0> 0> 0> 0> K 0>
Côncava 0≤ 0≥ 0≤ 0≥ K K
Estritamente côncava 0< 0> 0< 0> K K
Novamente, cabe listar duas observações em relação à classificação listada anteriormente:
a) Se f(x) é uma função linear e, consequentemente, Det1,Det2,...,Detn = 0, a função é simultaneamente 
convexa e côncava em S.
b) Se nenhuma das condições foi atendida, a função não é nem convexa nem côncava em S.
Exemplo 7.7:
Determine se a função 2 2 21 2 3 1 2 3 1 2 1 3 2 3( , , ) 2 4f x x x x x x x x x x x x= + + − − − é convexa (ou estritamente convexa), 
côncava (ou estritamente côncava), convexa e côncava simultaneamente ou nenhuma delas, em um 
conjunto convexo S.
 � Solução:
A matriz Hessiana de f(x1, x2, x3) pode ser calculada como:
⎤⎡ ∂ ∂ ∂ ⎥⎢ ∂ ∂ ∂ ∂ ∂ ⎥⎢
− −⎥⎢ ∂ ∂ ∂
= = − −⎡ ⎤ ⎥⎢⎣ ⎦ ∂ ∂ ∂ ∂ ∂ ⎥⎢
− −⎥⎢ ∂ ∂ ∂ ⎥⎢
∂ ∂ ∂ ∂ ∂ ⎥⎢ ⎦⎣
2 2 2
2
1 1 2 1 3
2 2 2
1 2 3 2
2 1 2 2 3
2 2 2
2
3 1 3 2 3
 
 4 1 1
( , , ) 1 2 1
1 1 
 
f f f
x x x x x
f f f
H f x x x
x x x x x
f f f
x x x x x
⎡ ⎤⎢ ⎥⎢ ⎥⎢ ⎥⎣ ⎦ 8
434
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
Exemplo 7.8:
Determine a solução ótima para a função 4( ) (10 )f x x= − e identifique se *x é um ponto de máximo ou 
mínimo.
 � Solução:
Para obter a solução ótima, basta calcular a derivada dessa função e igualá-la a zero: 
*
1 * 3( ) ( ) 4(10 ) 0
df x
f x x
dx
= = − − =
Logo, * 10x = .
Para identificar se *x é um ponto de máximo ou mínimo, precisa-se ainda calcular a derivada de 
segunda, terceira e quarta ordem:
2 * 2( ) 12(10 )f x x= −
3 *( ) 24(10 )f x x= − − 
4 *( ) 24f x = 
Como n = 4 e 4 *( 10) 0f x = > , conclui-se que a solução ótima é um ponto de mínimo.
7.4.1.1 Métodos de Solução para PNL Irrestrita com uma Única Variável
Vários métodos de solução têm sido propostos para resolver problemas de PNL irrestrita com uma 
única variável. Dentre eles, destacam-se o método da bisseção e o método de Newton (ou Newton-
Raphson). Descreveremos cada um deles a seguir.
Método da bisseção 
O método da bisseção (bisection method) é um método numérico bastante simples que busca determinar 
a raiz x de uma função f(x) não linear, isto é, determinar a solução analítica da equação f(x) = 0. As raízes 
da função f(x) também podem ser determinadas de forma gráfica, correspondendo aos valores de x em que 
a função intercepta o eixo horizontal do gráfico. 
Como limitação do método da bisseção, a convergência na determinação da raiz da função f(x) é 
muito lenta. 
Método de Newton
O método de Newton (ou método de Newton-Raphson) também é um método numérico cujo 
objetivo é determinar uma função iteração que acelere a convergência na estimação das raízes de uma 
função não linear f(x). É, geralmente, bem mais rápido que o método da bisseção.
Para que a convergência seja satisfatória, o valor inicial estimado deve ser adequado, isto é, 
suficientemente próximo da raiz da função. 
7.4.2 PNL Irrestrita com Múltiplas Variáveis
Analogamente ao exemplo anterior, esse modelo é simplesmente escrito em termos da função 
objetivo (PNL sem restrições), porém, buscando maximizar ou minimizar uma função não linear com n 
variáveis:
435
Capítulo 7 I Programação Não Linear
1 2max ou min ( , ,..., )nf x x x (7.7)
Para encontrar a solução ótima de 1 2( , ,..., )nf x x x , representada pelo vetor x* (x*=
* * *
1 2, ,..., nx x x ), basta 
resolver, de forma analítica, o seguinte sistema de n equações com n incógnitas:
* * *
1 2
1
( , ,..., ) 0nf x x xx
∂
=
∂
* * *
1 2
2
( , ,..., ) 0nf x x xx
∂
=
∂ (7.8)
 M
* * *
1 2( , ,..., ) 0n
n
f x x x
x
∂
=
∂
em que * * *1 2( , ,..., )n
i
f x x x
x
∂
∂ , para 1,...,i n= , representam as derivadas parciais de 
* * *
1 2( , ,..., )nf x x x em relação 
à ix .
Analogamente ao problema de PNL irrestrita com uma única variável, para determinar se a solução 
ótima é um ponto de máximo, mínimo ou inflexão, calculam-se as derivadas parciais de primeira ordem 
(n=1), segunda ordem (n=2) e assim por diante (para cada variável ix ), até que a derivada parcial na 
ordem n *(x )
n
n
i
f
x
⎛ ⎞∂
⎜ ⎟∂⎝ ⎠ seja uma constante com sinal positivo, negativo ou nulo:
Se n é par e *(x ) 0
n
n
i
f
x
∂
>
∂
 para cada ix , os pontos de x* são com certeza de mínimo;
Se n é par e *(x ) 0
n
n
i
f
x
∂
<
∂
 para cada ix , os pontos de x* são com certeza de máximo;
Se n é ímpar para cada ix , os pontos de x* são com certeza de inflexão.
Exemplo 7.9:
Determine a solução ótima para a função 2 21 2 1 2 1 2( , ) 3 4 18 16 10f x x x x x x= + − − + e identifique se x* são 
pontos de máximo, mínimo ou inflexão.
 � Solução:
Primeiramente, calculam-se as derivadas parciais da função f(x1,x2) em relação à x1 e x2, 
respectivamente:
1 2 1
1
( , ) 6 18f x x x
x
∂
= −
∂
 
1 2 2
2
( , ) 8 16f x x x
x
∂
= −
∂
436
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
Para determinar a solução ótima da função f(x1,x2), basta igualar a zero cada uma das equações 
anteriores, obtendo *1x e 
*
2x , respectivamente:
*
16 18 0x − = → 
*
1 3x =
*
28 16 0x − = → 
*
2 2x =
Para identificar se x* são pontos de máximo ou mínimo (n é par), basta calcular a derivada parcial de 
segunda ordem de f (x*) e verificar seu sinal:
2
* *
1 22
1
( 3, 2) 6 0f x x
x
∂
= = = >
∂
2
* *
1 22
2
( 3, 2) 8 0f x x
x
∂
= = = >
∂
Como n= 2 e as derivadas parciais de segunda ordem são positivas, conclui-se que os pontos são de 
mínimo.
7.4.2.1 Métodos de Solução para PNL Irrestrita com Múltiplas Variáveis
Os métodos de solução de problemas de PNL irrestrita com múltiplas variáveis podem ser classificados 
como: métodos de busca direta e métodos de descida ou indiretos.
Métodos de Busca Direta
São métodos que minimizam ou maximizam uma função com múltiplas variáveis sem o uso da 
derivada da função objetivo. Em geral, os métodos que usam derivadas convergem mais rapidamente 
quando comparados aos métodos de busca direta. Dentre os métodos de busca direta, destacam-se: 
método de busca aleatória, método de busca seccionada, método de Hooke e Jeeves com busca linear, 
método de Rosenbrock e método simplex.
Método de Busca Aleatória
É um método que utiliza números aleatórios para encontrar a solução ótima. São menos eficientes 
comparados a outros métodos de busca direta. Não exige chutes iniciais.
Método de Busca Seccionada
O método utiliza várias direções de busca, porém, a cada vez, a busca é feita em uma única direção, 
utilizando métodos univariáveis. 
Método de Hooke e Jeeves com busca linear
É uma adaptação do método original proposto por Hooke e Jeeves utilizando buscas lineares. Esse 
método realiza dois tipos de busca: exploratória e progressiva. A busca exploratória estima a direção 
provável do ponto extremo, a partir de um ponto inicial. Já a busca progressiva percorre essa direção 
enquanto o valor da função objetivo diminuir (minimização) ou aumentar (maximização).
437
Capítulo 7 I Programação Não Linear
Método de Rosenbrock
Segundo Brandão (2010), o método de Rosenbrock não utiliza buscas lineares, mas sim passos 
discretos ao longo das direções de busca. É uma adaptação do método de Hooke e Jeeves, em que, em vez 
da busca ocorrer na direção dos eixos das coordenadas, utilizam-se novas direções ortogonais.
Método Simplex
Avalia a função objetivo para cada um dos pontos extremos do polígono (simplex).
Métodos de Descida ou Métodos Indiretos
São métodos que utilizam a primeira e/ou a segunda derivada da função objetivo para definir as 
direções de busca. Dentre eles, destacam-se: método de Newton, método do Quase-Newton, método do 
gradiente e método do gradiente conjugado.
Método de Newton
Utiliza a segunda derivada da função objetivo para definir a direção de busca. Se a função objetivo é 
quadrática, o mínimo da função é encontrado em apenas uma iteração.
Método do Quase-Newton
É uma variante do método de Newton que calcula apenas a primeira derivada da função objetivo. 
Uma vez que a segunda derivada não é necessária, o método do Quase-Newton é, muitas vezes, mais 
eficiente que o método de Newton.
Método do Gradiente 
Também conhecido como método da inclinação descendente (steepest descent) ou da descida mais 
íngreme (problema de minimização), é um método simples que usa os gradientes para direcionar a busca; 
utiliza apenas a primeira derivada da função objetivo no processo de busca. Porém, muitas vezes, a busca 
estaciona em ótimos locais. 
Método do Gradiente Conjugado
Esse método é adequado para problemas com grande número de variáveis, pois exige um menor 
armazenamento das informações. Utiliza somente a primeira derivada da função objetivo. A direção do 
passo atual é determinada pelo método do gradiente. A nova direção de busca passa a ser determinada 
pela combinação linear das direções de busca dos passos anteriores, associada à direção do passo atual.
7.5 Programação Não Linear com Restrição
Os problemas de PNL com restrição buscam maximizar ou minimizar uma função linear ou não 
linear com múltiplas variáveis, sujeito a uma única restrição (i=1) ou múltiplas restrições (i=1,...,m). Pelo 
menos a função objetivo ou uma das restrições deve ser uma função não linear.
438
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
{ }
1 2
1 2 
1 2
max ou min z ( , ,..., )
sujeito a:
 ( , ,..., ) , , , 1,...,
 , , , 0 
n
i n i
n
f x x x
g x x x b i m
x x x
=
≤ = ≥ =
≥K
 (7.9)
Dentre os problemas de PNL com restrição, destacam-se: programação côncava, convexa, quadrática 
e separável. 
Inicialmente, apresentaremos como os multiplicadores de Lagrange podem ser aplicados para resolver 
problemas de PNL com restrições de igualdade, e também como as condições de Karush-Kuhn-Tucker 
(KKT) podem ser aplicadas para verificar se uma determinada solução de um problema de PNL é ou não 
uma solução ótima local. Apresentaremos ainda outros métodos de solução para problemas de PNL, 
incluindo métodos de busca direta (método do gradiente reduzido generalizado e métodos de plano de 
corte) e métodos de busca indireta (métodos sequenciais de maximização e minimização sem restrições e 
métodos de transformações de variáveis).
7.5.1 Multiplicadores de Lagrange
Segundo Winston (2004), os multiplicadores de Lagrange podem ser utilizados para resolver 
problemas de PNL em que todas as restrições estão escritas na forma de igualdade. Considere o seguinte 
problema de PNL:
=
=
=
M M M
1 2
1 1 2 1
2 1 2 2
max ou min z ( , ,..., )
sujeito a:
 ( , ,..., ) 
 ( , ,..., ) 
 
 
n
n
n
f x x x
g x x x b
g x x x b
=
≥K
1 2
1 2
 ( , ,..., ) 
 , , , 0 
m n m
n
g x x x b
x x x
 (7.10)
Para resolver o problema (7.10), multiplica-se cada i-ésima restrição 1 2( , ,..., )i n ig x x x b= por uma 
constante iλ denominada multiplicador de Lagrange:
1 2( , ,..., )i i i nb g x x xλ −⎡ ⎤⎣ ⎦
Essas equações são adicionadas à função objetivo formando a chamada Lagrangiana:
1 2 1 2 1 2 1 2
1
( , ,..., , , ,..., ) ( , ,..., ) ( , ,..., )
m
n m n i i i n
i
L x x x f x x x b g x x xλ λ λ λ
=
= + −⎡ ⎤⎣ ⎦∑ (7.11)
Para encontrar os valores de * * *1 2, ,..., nx x x e 1
* * *
2, ,..., mλ λ λ , calculam-se as derivadas parciais da Lagrangiana 
e as mesmas são igualadas a zero:
0 , 1,..., 
0 , 1,..., 
j
i
L
j n
x
L
i mλ
∂
= =
∂
∂
= =
∂
 (7.12)
439
Capítulo 7 I Programação Não Linear
Exemplo 7.10:
Esse exemplo foi baseado em Winston (2004). Uma empresa de pneus quer investir em dois novos 
equipamentos: a prensa plana (x) e a linha de raspa (y). Cada unidade de prensa plana e cada unidade de 
linha de raspa adquirida requer a compra de 2 novos adaptadores. A empresa já decidiu que vai comprar 
12 adaptadores. O lucro obtido a partir dos novos equipamentos pode ser representado pela função 
2 2( , ) 6 2f x y x y xy x y= − − + + + . Determinar a solução ótima e verificar se esta é uma função convexa 
(ou estritamente convexa), côncava (ou estritamente côncava), convexa e côncava simultaneamente ou 
nenhuma delas.
 � Solução:
O modelo pode ser representado matematicamente como:
= = − − + + +
+ =
≥
2 2max ( , ) 6 2
sujeito a: 
 2 2 12
 , 0
z f x y x y xy x y
x y
x y
 (7.13)
A Lagrangiana ( , , )L x y λ de (7.13) pode ser calculada como:
2 2( , , ) 6 2 (12 2 2 )L x y x y xy x y x yλλ = − − + + + + − −
Calculam-se as derivadas parciais em relação à x, y e �, igualando-as a zero:
0 2 6 2 0
L
x y
x
λ∂ = → − + + − =
∂
 (7.14)
0 2 2 2 0
L
y x
y
λ∂ = → − + + − =
∂ (7.15)
0 12 2 2 0
L
x yλ
∂
= → − − =
∂
 (7.16)
Isolando o y na equação (7.14), obtém-se:
2 6 2y x= − + (7.17)
Isolando o x na equação (7.15), obtém-se:
2 2 2x yλ= − + (7.18)
Substituindo (7.18) em (7.17), y pode ser reescrito em função de �:
10
2 6 2(22 2 ) 2
3
y y yλ λ λ= − + − + → = − (7.19)
Substituindo (7.19) em (7.18), x pode ser reescrito em função de �:
440
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
x    





  2 2 2
10
3
2 2λ λ λ 14
3
x (7.20)
Substituindo (7.20) e (7.19) em (7.16), obtém-se o valor de �:
12 2
14
3
2 2
10
3
2 0− −⎛⎝⎜
⎞
⎠⎟ − −
⎛
⎝⎜
⎞
⎠⎟ = → =λ λ λ 
1
2
Finalmente, substituindo o valor de λ = 1
2
 em (7.20) e (7.19), obtêm-se os valores ótimos de x e y 
para (7.13):
x* = − ⎛⎝⎜
⎞
⎠⎟ =
14
3
11
3
2
1
2
 
y* = − ⎛⎝⎜
⎞
⎠⎟ =
10
3
7
3
2
1
2
 com z* =
49
3
Para determinar se a função f(x,y) é côncava ou convexa (veja Seção 7.3.2), calcula-se a matriz 
Hessiana:
 [ ]
⎡ ⎤∂ ∂⎢ ⎥
−∂ ∂ ∂ ⎡ ⎤⎢ ⎥
= = ⎢ ⎥⎢ ⎥
−∂ ∂ ⎣ ⎦⎢ ⎥∂ ∂ ∂⎢ ⎥⎣ ⎦
2 2
2
1 1 2
2 2
2
2 1 2
 
2 1
( , )
 1 2
 
f f
x x x
H f x y
f f
x x x
 
Os elementos da diagonal principal da matriz Hessiana são negativos. Já o determinante de 
1 2( , )H f x x⎡ ⎤⎣ ⎦ é –2(–2) – (1)(1) = 3. 
Conclui-se, portanto, que f(x,y) é uma função estritamente côncava.
7.5.2 Condições de Karush-Kuhn-Tucker
As condições de Karush-Kuhn-Tucker (KKT) podem ser aplicadas para verificar se uma determinada 
solução de um problema de PNL é ou não um ótimo local. De início, o problema de PNL deve estar 
representado matematicamente como:
≤
≤
≤
M M M
1 2
1 1 2 1
2 1 2 2
1 2
max ( , ,..., )
sujeito a:
 ( , ,..., ) 
 ( , ,..., ) 
 
 ( , ,..., ) 
 
m n m
z f x x x
g x x x b
g x x x b
g x x x b
≥1 2, , , 0 x x
 (7.21)
Segundo Colin (2007), a solução * * *1 2( , ,..., )nx x x de (7.21) é um ótimo local se, e somente se, existirem 
as constantes 1 2, ,..., mλ λ λ que satisfaçam as seguintes condições:
Condição 1 de KKT: 
* * * * * *
1 2 1 2
1
( , ,..., ) ( , ,..., )
0
m
n i n
i
i jj
f x x x g x x x
x x
λ
=
∂ ∂
− ≤
∂ ∂∑ , j=1,...,n
441
Capítulo 7 I Programação Não Linear
Condição 2 de KKT: 
* * * * * *
* 1 2 1 2
1
( , ,..., ) ( , ,..., )
0
m
n i n
ij
i jj
f x x x g x x x
x
x x
λ
=
⎞⎛ ∂ ∂
− =⎟⎜ ∂ ∂ ⎠⎝ ∑ , j=1,...,n 
Condição 3 de KKT: * * *1 2( , ,..., ) 0i i i nb g x x xλ ⎡ ⎤− =⎣ ⎦ , i=1,...,m 
Condição 4 de KKT: 0iλ ≥ , i=1,...,m 
Qualquer solução * * *1 2( , ,..., )nx x x que satisfaça as quatro condições de KKT é chamada ponto de KKT.
Exemplo 7.11:
Considere o seguinte problema de PNL:
= + + +
+ ≤
≤
≥
2 2
1 2 1 2
1 2
2
1 2
max 4 2
sujeito a: 
 12
 6
 , 0
z x x x x
x x
x
x x
 (7.22)
Verifique as condições de KKT e determine o ótimo local de (7.22).
 � Solução:
A solução desse exemplo foi baseada em Colin (2007). 
A primeira condição de KKT é descrita como:
* * * * * *
1 2 1 1 2 2 1 2
1 2
( , ) ( , ) ( , )
0
jjj
f x x g x x g x x
x x x
λ λ∂ ∂ ∂− − ≤
∂ ∂ ∂
 , j=1, 2
1j = → *1 12 4 0x λ+ − ≤ (7.23)
2j = → *2 1 22 2 0x λ λ+ − − ≤ (7.24)
A segunda condição de KKT é definida como:
* * * * * *
* 1 2 1 1 2 2 1 2
1 2
( , ) ( , ) ( , )
0j
jjj
f x x g x x g x x
x
x x x
λ λ
⎞⎛ ∂ ∂ ∂
− − =⎟⎜ ∂ ∂ ∂ ⎠⎝ , j=1, 2 
1j = → * *1 1 1(2 4 ) 0x x λ+ − = (7.25)
2j = → * *2 2 1 2(2 2 ) 0x x λ λ+ − − = (7.26)
A terceira condição de KKT afirma que:
* *
1 2( , ) 0i i ib g x xλ ⎡ ⎤− =⎣ ⎦ ,i=1, 2 
1i = → * *1 1 2(12 ) 0x xλ − − = (7.27)
2i = → *2 2(6 ) 0xλ − = (7.28)
442
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
Finalmente, as constantes 1λ e 2λ devem ser não negativas (quarta condição de KKT):
1 0λ ≥ e 2 0λ ≥
Os valores de * *1 2 1 2( , , e )x x λ λ podem ser determinados algebricamente a partir das quatro condições 
de KKT estabelecidas anteriormente. Testaremos duas condições. Se nenhuma delas for possível, teremos 
de testar outra alternativa.
Condição 1: x1= 0 
A equação (7.25) afirma que x1= 0, ou 
*
1 12 4 0x λ+ − = , ou ambos valem zero. Testaremos se a 
condição x1= 0 é válida.
Se x1= 0, a inequação (7.23) passa a ser escrita como 1 4λ ≥ . 
A equação (7.27) afirma que 1 0λ = , * *1 212 0x x− − = , ou ambos valem zero. Como estamos assumindo 
que x1= 0 e, consequentemente, 1 4λ ≥ , conclui-se que x2=12. Porém, a segunda restrição do problema 
original (7.22) garante que *2 6x ≤ , de modo que a condição 1 é impossível.
Condição 2: *2 0x = 
A equação (7.26) afirma que *2 0x = , ou 
*
2 1 22 2 0x λ λ+ − − = , ou ambos valem zero. Testaremos se a 
condição *2 0x = é válida.
Se *2 0x = , pela equação (7.28) conclui-se que 2 0λ = . Assim, a inequação (7.24) resume-se a 1 2λ ≥ . 
Pela equação (7.27), como 1 0λ ≠ , a condição * *1 212 0x x− − = deve ser satisfeita, de modo que *1 12x = . 
O valor de 1λ pode ser obtido pela equação (7.25), de modo que 1 2 12 4 28λ = × + = .
Verifica-se que todas as demais condições são atendidas, de modo que a solução 
* *
1 2 1 2( , , e ) (12, 0, 28, 0)x x λ λ = com z=192 é um máximo local. Veremos na próxima seção que essa 
solução também é a ótima global.
7.5.2.1 Condições que Garantem que um Ótimo Local seja um Ótimo Global
Segundo Colin (2007), as condições de KKT são condições necessárias para encontrar o ótimo local 
de um problema de PNL, mas não garantem que o ótimo local seja um ótimo global.
As condições necessárias e suficientes para que um ótimo local seja um ótimo global estão especificadas 
a seguir, tanto para problemas de maximização como minimização, de acordo com Colin (2007).
Para um problema de maximização de PNL, se 1 2( , ,..., )nf x x x é uma função côncava e 1 2( , ,..., )i ng x x x 
para i=1,...,m são funções convexas, então qualquer ponto * * *1 2( , ,..., )nx x x que satisfaça as condições de 
KKT (ótimo local) é também um ótimo global.
Para um problema de minimização de PNL, se 1 2( , ,..., )nf x x x e 1 2( , ,..., )i ng x x x para i=1,...,m são 
funções convexas, então qualquer ponto * * *1 2( , ,..., )nx x x que satisfaça as condições de KKT (ótimo local) é 
também um ótimo global.
443
Capítulo 7 I Programação Não Linear
7.5.3 Outros Métodos de Solução para Problemas de PNL com Restrição 
Vimos que os multiplicadores de Lagrange resolvem apenas problemas com restrições de igualdade, 
de modo que os métodos apresentados nesta seção podem ser aplicados para resolver problemas com 
restrições de desigualdade. Esses métodos são descritos com base no trabalho de Colin (2007) e Rardin 
(1998).
Métodos de Busca Direta
Método do Gradiente Reduzido Generalizado
O método GRG (generalized reduced gradient) é uma extensão do método simplex. O método 
considera, a cada iteração, apenas as variáveis não básicas do problema. O algoritmo utilizado pelo Solver 
para resolver problemas de PNL é uma variante desse método, denominado GRG2. 
Métodos de Plano de Corte
Nesse método, funções não lineares do problema original, seja na função objetivo ou nas restrições, 
são linearizadas de modo que o problema possa ser resolvido por programação linear. Essa solução é usada 
para gerar uma nova aproximação e o processo se repete de modo iterativo.
Métodos de Busca Indireta
Métodos sequenciais de maximização e minimização sem restrições (SUMT)
Pelo SUMT, o problema original de PNL com restrição é transformado em uma sequência de problemas 
sem restrições. Esses métodos podem ser divididos como método da penalidade ou método da barreira. 
No método da penalidade, a sequência de problemas sem restrições está localizada em uma região viável. Já 
no método da barreira, essa sequência está localizadaem uma região de infactibilidade.
Métodos de transformações de variáveis
Nesses problemas, as variáveis originais podem ser transformadas de modo que as restrições possam 
sempre ser satisfeitas.
7.5.4 Programação Côncava
Um modelo geral de PNL na seguinte forma:
{ }
{ }
{ }
1 2
1 1 2 1
2 1 2 2
1 2
max ou min z ( , ,..., )
sujeito a:
 ( , ,..., ) , , 
 ( , ,..., ) , , 
 
 ( , ,..., ) , , 
n
n
n
m n
f x x x
g x x x b
g x x x b
g x x x b
=
≤ = ≥
≤ = ≥
≤ = ≥
M M M
1 2 , , , 0 
m
nx x x ≥K
 (7.29)
é um modelo de programação côncava se satisfizer as seguintes condições:
444
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
– se f é uma função côncava para problemas de maximização;
– se cada restrição 1 2( , ,..., )i ng x x x com sinal ib≥ é uma função côncava;
– se cada restrição 1 2( , ,..., )i ng x x x com sinal ib≤ é uma função convexa;
– e se cada restrição 1 2( , ,..., )i ng x x x com sinal de igualdade é uma função linear.
Se todas as restrições forem de desigualdade e as condições descritas anteriormente forem satisfeitas, 
pode-se garantir que o conjunto de soluções viáveis é um conjunto convexo e, consequentemente, o 
máximo local encontrado é o máximo global.
Pode-se ainda garantir que o conjunto de soluções viáveis é convexo se todas as restrições forem 
lineares. 
Por outro lado, se existirem restrições de igualdade, torna-se difícil afirmar que o conjunto de soluções 
viáveis é convexo. Consequentemente, não podemos afirmar que o máximo local encontrado corresponde 
ao ponto de máximo global.
7.5.5 Programação Convexa
Um modelo geral de PNL é um modelo de programação convexa se satisfizer as seguintes condições:
– se f é uma função convexa para problemas de minimização;
– se cada restrição 1 2( , ,..., )i ng x x x com sinal ib≥ é uma função côncava;
– se cada restrição 1 2( , ,..., )i ng x x x com sinal ib≤ é uma função convexa;
– e se cada restrição 1 2( , ,..., )i ng x x x com sinal de igualdade é uma função linear.
Analogamente ao modelo de programação côncava, se todas as restrições forem de desigualdade e 
as condições descritas anteriormente forem satisfeitas (ou se todas as restrições forem lineares), pode-se 
garantir que o conjunto de soluções viáveis é um conjunto convexo e, consequentemente, o mínimo local 
encontrado é o mínimo global. O mesmo não pode ser afirmado se existirem restrições de igualdade.
7.5.6 Programação Quadrática
Em um problema de programação quadrática, a função objetivo f é quadrática. Já todas as restrições 
1 2( , ,..., )i ng x x x são lineares.
Uma função quadrática de n variáveis pode ser expressa como a soma de termos envolvendo o 
quadrado de uma única variável, o produto de duas variáveis distintas, funções lineares e constantes:
1
2
1 2
1 1 1 1
( , ,..., )
n n n n
n i i ij i j i i
i i j i i
f x x x a x b x x c x d
−
= = = + =
= + + +∑ ∑ ∑ ∑ (7.30)
Assim, uma função quadrática de uma única variável pode ser expressa como 21 1 1( )f x ax bx c= + + . Já uma 
função quadrática de duas variáveis pode ser expressa como: 2 21 2 1 1 2 2 1 2 1 1 2 2( , )f x x a x a x bx x c x c x d= + + + + + , e 
assim, sucessivamente.
Nos problemas de programação quadrática, o conjunto de soluções viáveis será sempre convexo, já que 
todas as restrições são lineares. Desta forma, se f é uma função côncava para problemas de maximização, 
o máximo encontrado será o máximo global. Analogamente, se f é uma função convexa para problemas 
de minimização, o mínimo encontrado será sempre o mínimo global.
Vários problemas reais se enquadram nessa classificação, incluindo o problema de seleção de carteiras 
de investimento.
445
Capítulo 7 I Programação Não Linear
7.5.7 Programação Separável
A programação separável é um caso especial da programação convexa, adicionando-se a hipótese de 
que a função f e todas as restrições 1 2( , ,..., )i ng x x x são funções separáveis.
Uma função é dita separável quando cada variável xj aparece separadamente, seja na função objetivo 
ou em cada restrição. Para Colin (2007), tem-se uma função separável quando cada termo da função 
objetivo ou das restrições, separado por somas ou subtrações, possui uma só variável (não pode haver 
multiplicação ou divisão entre duas variáveis distintas). 
Para Rardin (1998), uma função 1 2( , ,..., )nf x x x é dita separável se puder ser representada como a soma 
de funções de uma única variável:
1 2 1 1 2 2
1
( , ,..., ) ( ) ( ) ( ) ... ( )
n
n j j n n
j
f x x x f x f x f x f x
=
= = + + +∑ (7.31)
Um problema de PNL representado matematicamente na seguinte forma:
{ }
{ }
1 2
1 1 2 1
2 1 2 2
1 2
max ou min z ( , ,..., )
sujeito a:
 ( , ,..., ) , , 
 ( , ,..., ) , , 
 
 ( , ,..., ) ,
n
n
n
m n
f x x x
g x x x b
g x x x b
g x x x
=
≤ = ≥
≤ = ≥
≤
M M M
{ }
1 2
, 
 , , , 0 
m
n
b
x x x
= ≥
≥K
 (7.32)
é um problema de programação separável se f e cada restrição gi é uma função separável.
O problema (7.33) de PNL é um exemplo de programação separável:
2 2
1 2 1 2
1 2
2 2
1 2
1 2
max z 30 10
sujeito a:
 3 2 18
 4 2 100
 , 0 
x x x x
x x
x x
x x
= + + −
+ ≤
− ≤
≥
 (7.33)
7.6 Solução de Problemas de PNL pelo Solver do Excel
Vimos no Capítulo 3 que, resolvendo um problema de programação linear pelo Solver do Excel, entre 
outros softwares de otimização, há garantia de que a solução encontrada (quando houver) seja ótima. O 
mesmo já não ocorre em relação aos problemas de PNL. 
Para solução de problemas de PNL, o Solver disponibiliza o algoritmo GRG2 (generalized reduced 
gradient). Por causa da complexidade dos problemas de PNL, não é possível afirmar que a solução 
encontrada pelo Solver seja um ponto de máximo ou mínimo global, podendo ser apenas um ótimo local. 
Essa condição pode ser verificada pelo estudo de convexidade e concavidade das funções. 
Vimos nas Seções 7.5.4 e 7.5.6, que se f é uma função côncava para problemas de maximização e o 
conjunto de soluções viáveis é um conjunto convexo, a solução encontrada (nesse caso pelo Solver do 
Excel) corresponde ao ponto de máximo global.
446
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
Analogamente nas Seções 7.5.5 e 7.5.6, se f é uma função convexa para problemas de minimização 
e o conjunto de soluções viáveis é um conjunto convexo, a solução encontrada pelo Solver do Excel será 
sempre um ponto de mínimo global.
Em resumo, podemos garantir que se o problema estudado for de programação côncava, convexa 
ou quadrática, o ótimo local será sempre o ótimo global. Por outro lado, se o problema não se enquadrar 
em nenhuma dessas categorias, Lachtermacher (2009) propõe, como forma de escapar de ótimos locais, a 
geração de diversas soluções iniciais aleatórias. Para cada solução inicial gerada, o Solver aplica o algoritmo 
GRG2. Por fim, verifica-se se essas soluções foram ou não coincidentes. Em caso afirmativo, aumenta-se 
a probabilidade de termos encontrado a solução ótima global (mas não há garantia). Caso contrário, 
escolheríamos a melhor solução encontrada.
Além disso, o Excel 2010 disponibiliza um novo algoritmo para solução de problemas de PNL (e 
inclusive PL), chamado algoritmo evolucionário (veja Figura 7.5). Conforme descrito no Capítulo 1, 
os algoritmos evolucionários (ou evolutivos) são algoritmos heurísticos baseados no princípio 
darwiniano de evolução naturaldas espécies, incluindo algoritmos genéticos, algoritmos meméticos, 
colônia de formigas, enxame de partículas, entre outros. Esses algoritmos vêm sendo aplicados para 
solução de problemas complexos e utilizam estratégias de intensificação (busca de soluções de qualidade) 
e diversificação (busca por soluções diversas), o que faz que a busca não estacione em ótimos locais e 
encontre soluções de alta qualidade. Apesar de não garantir que a solução ótima seja encontrada, pode-se, 
muitas vezes, chegar à solução ótima ou a uma solução próxima a ela.
Figura 7.5 Gradiente reduzido generalizado e algoritmo evolucionário como métodos 
de solução de problemas de PNL no Excel 2010.
447
Capítulo 7 I Programação Não Linear
7.6.1 Análise de Sensibilidade em Problemas Não Lineares
A análise de sensibilidade para problemas de PL foi estudada no Capítulo 4 e considerava dois casos:
a) Análise de sensibilidade em função de alterações em um dos coeficientes da função objetivo; utilizava o 
conceito de custo reduzido. O custo reduzido de uma determinada variável não básica xj representava 
o valor que seu coeficiente original cj deveria melhorar na função objetivo antes da solução básica atual 
tornar-se subótima e de xj tornar-se uma variável básica.
b) Análise de sensibilidade em função de alterações nos termos independentes das restrições; utilizava 
o conceito de preço-sombra. O preço-sombra representava o acréscimo (ou decréscimo) no valor da 
função objetivo caso fosse adicionada (ou retirada) uma unidade na quantidade atual de recursos 
disponíveis de uma determinada restrição.
Na análise de sensibilidade dos problemas de PNL, em vez do custo reduzido e do preço-sombra, 
utilizam-se os conceitos de gradientes reduzidos e multiplicadores de Lagrange, respectivamente. Apesar 
de terem significados diferentes, a interpretação deles é a mesma.
Assim, os multiplicadores de Lagrange podem ter a mesma interpretação do preço-sombra, 
porém, são mais difíceis de serem estimados em razão da complexidade dos problemas de PNL. Calculam, 
portanto, o impacto aproximado no valor da função objetivo caso haja uma variação de uma unidade de 
recursos.
Analogamente, a interpretação do conceito de gradiente reduzido é a mesma do custo reduzido, 
porém, seu cálculo indica apenas um valor aproximado da quantidade que o coeficiente da função objetivo 
de uma variável deve melhorar antes desta tornar-se uma variável básica.
A Figura 7.6 mostra o relatório de sensibilidade para um problema qualquer de PNL.
Figura 7.6 Exemplo de um relatório de sensibilidade para um problema de PNL.
7.7 O Modelo do Lote Econômico de Compra
O lote econômico de compra (LEC) é um modelo básico de controle de estoques e adota as seguintes 
premissas:
– considera um único item; 
448
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
– a demanda é constante ao longo do tempo;
– o tempo de reposição é fixo;
– o preço e o custo do pedido são constantes.
O comportamento do nível de estoque ao longo do tempo no modelo do lote econômico de compra 
está representado na Figura 7.7. O tamanho do lote é representado por Q.
 Figura 7.7 Nível de estoque de um item ao longo do tempo no modelo de LEC.
O modelo do lote econômico considera os seguintes custos:
– Custos de Manutenção de Estoques: são os custos diretamente proporcionais à quantidade estocada. 
Incluem os custos de armazenagem propriamente dita, os custos de seguro, os custos de transporte 
e manuseio, os custos de obsolescência etc.
– Custos do Pedido: são os custos inversamente proporcionais à quantidade estocada. No caso de 
itens comprados, são chamados custos do pedido. No caso de itens fabricados internamente, são 
chamados custos de preparação.
– Custos de Aquisição ou Custos do Material Comprado: correspondem aos custos de compra de 
materiais que serão estocados. Esses custos independem do tamanho do lote.
O objetivo do modelo do LEC é determinar o tamanho do lote de compra e a periodicidade ou ponto 
do pedido, de forma a minimizar os custos totais de estocagem. A função objetivo pode ser expressa 
como:
min ( )
2 M p
Q D
z f Q c c D P
Q
= = ⋅ + ⋅ + ⋅ (7.34)
em que:
Q – tamanho do lote de compra
D – demanda anual do produto
P – preço de compra unitário
cM – custo unitário de manutenção de estoques (anual)
cp – custo unitário do pedido
A Figura 7.8 mostra o efeito do tamanho do lote nos custos.
449
Capítulo 7 I Programação Não Linear
Figura 7.8 Efeito do tamanho do lote nos custos.
O modelo do lote econômico de compra é, portanto, um problema de programação não linear.
Exemplo 7.12:
A empresa Betazul Telecom atua no mercado de telefonia celular e pretende minimizar seu custo total 
de estocagem. Atualmente, a empresa necessita atender a uma demanda anual de 20.000 celulares. Cada 
unidade comprada custa R$8,00, porém, cada vez que a empresa faz o pedido despende um valor de 
R$5,00. O custo anual de manutenção de estoques é de R$20,00 por unidade. Por razões contratuais com 
o fornecedor, o tamanho do lote deve ser no mínimo de 30 unidades. Assim, deseja-se determinar o lote 
econômico de compra. Modele o problema da empresa Betazul Telecom.
 � Solução:
Aplicando a fórmula (7.34), a função objetivo da empresa Betazul Telecom pode ser expressa como:
20.000 100.000
min ( ) 20 5 20.000 8 10 160.000
2
Q
z f Q Q
QQ
= = ⋅ + ⋅ + ⋅ ⇒ ⋅ + + (7.35)
A única restrição do modelo impõe que o tamanho do lote seja no mínimo de 30 unidades:
1. 30Q ≥ 
7.7.1 Solução do Problema da Betazul Telecom pelo Solver do Excel
Antes de resolvermos o problema da empresa Betazul Telecom pelo Solver do Excel, é necessário 
classificá-lo como um modelo de programação quadrática, côncava, convexa, etc., para se verificar se a 
solução obtida será ou não a ótima global.
Como o modelo apresenta apenas restrições lineares, o conjunto de soluções viáveis é um conjunto 
convexo. Mas como a função objetivo não é quadrática, o modelo não é de programação quadrática. 
Verificaremos, agora, se o problema pode ser classificado como programação convexa. Como as restrições 
formam um conjunto convexo, resta apenas verificar se a função objetivo é também convexa. Para 
problemas com uma única variável, a convexidade de uma função pode ser analisada por meio do cálculo 
da segunda derivada da função.
450
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
A derivada de primeira ordem da função objetivo (35) é:
2( ) 10 100.000
df Q
Q
dQ
−
= − ⋅ (7.36)
Já a derivada de segunda ordem é:
2
3
32
( ) 200.000
200.000
d f Q
Q
dQ Q
−
= ⋅ = (7.37)
Como Q só pode assumir valores positivos (nesse caso maior que 30), a derivada de segunda ordem 
será sempre positiva 
2
2
( )
0 para 
d f Q
Q S
dQ
⎞⎛
> ∀ ∈ ⎟⎜ ⎠⎝ . Logo, f (Q) é uma função estritamente convexa em S.
Conclui-se, portanto, que o problema é de programação convexa. Consequentemente, podemos 
garantir que a solução encontrada pela Solver será a solução ótima global.
O Exemplo 12 da empresa Betazul Telecom será então resolvido nesta seção pelo Solver do Excel. A 
representação do problema em uma planilha do Excel está ilustrada na Figura 7.9 (veja arquivo Exemplo 7.12_
BetazulTelecom.xls). Para facilitar a convergência do algoritmo, utilizaremos como solução inicial Q = 30.
Figura 7.9 Representação em Excel do problema da empresa Betazul Telecom.
As fórmulas utilizadas na Figura 7.9 estão especificadas no Quadro 7.1.
Quadro 7.1 Fórmulas utilizadas na Figura 7.9
Célula Fórmula
B8 =B14/2*B6
B9 =B3/B14*B5
B10 =B3*B4
B11 =SOMA(B8:B10)
451
Capítulo 7 I Programação Não Linear
O Quadro 7.2 apresenta os nomes atribuídos às células e intervalos de células da Figura 7.9, que serão 
referenciados no Solver.Quadro 7.2 Nomes atribuídos às células da Figura 7.9
Nome Células
Custo_total_anual B11
LEC B14
A representação do problema da empresa Betazul Telecom na caixa de diálogo Parâmetros do 
Solver está ilustrada na Figura 7.10, com os respectivos nomes atribuídos às células do modelo. Como a 
solução obtida pelo Solver será a ótima global, resolveremos o problema apenas pelo algoritmo GRG2 (o 
método evolucionário não será utilizado), considerando Q = 30 como solução inicial.
Figura 7.10 Parâmetros do Solver referentes ao problema da empresa Betazul Telecom.
Por fim, a Figura 7.11 apresenta a solução ótima obtida pelo Solver. 
452
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
Figura 7.11 Solução ótima obtida pelo Solver para o problema da empresa Betazul Telecom.
A solução ótima é, portanto, Q = 100 com z=162.000.
Outra forma de encontrar diretamente a solução ótima seria pelo cálculo do lote ótimo (Q). A 
fórmula pode ser obtida igualando a zero a derivada de primeira ordem de f (Q) (ponto de mínimo):
* 2 2 20.000 5 100
20
p
M
D c
Q
c
× × × ×
= = = (7.38)
lembrando que * 30Q ≥ .
7.8 O Problema de Localização de Facilidades como um Problema de PNL
No Capítulo 6, estudamos o problema de localização de facilidades como um problema de programação 
binária mista. O mesmo também pode ser modelado como um problema de programação não linear, 
se as facilidades i já instaladas estiverem representadas em um eixo cartesiano, com as respectivas 
coordenadas (xi,yi), e o objetivo for determinar a localização de uma nova facilidade j no plano cartesiano 
(as coordenadas (xj,yj) seriam as novas variáveis de decisão), de forma a minimizar a soma das distâncias 
percorridas da nova facilidade j em relação a cada uma das facilidades i já instaladas.
A distância dij entre cada localidade i e a nova localidade j no plano cartesiano é calculada como:
2 2( ) ( )ij i j i jd x x y y= − + − (7.39)
Exemplo 7.13:
A empresa Sabor & Degust do setor alimentício está planejando abrir uma nova fábrica que irá 
abastecer quatro centros de distribuição. Os centros de distribuição estão localizados em Curitiba, 
Barueri, Cabo Frio e Viçosa e as respectivas coordenadas (x,y) no plano cartesiano estão ilustradas na 
Figura 7.12. Deseja-se determinar o local ótimo no plano cartesiano para a instalação da nova fábrica, de 
modo que a soma das distâncias percorridas da fábrica em relação a cada um dos centros de distribuição 
seja minimizada. Por razões logísticas, a distância da fábrica para cada centro de distribuição não pode 
ser maior do que 10, com exceção de Cabo Frio que é no máximo 3. Modele o problema de localização da 
empresa Sabor & Degust.
453
Capítulo 7 I Programação Não Linear
Figura 7.12 Coordenadas dos centros de distribuição no plano cartesiano.
 � Solução:
A variável de decisão do modelo representa a coordenada da fábrica (xj,yj) a ser determinada no plano 
cartesiano.
A função objetivo busca minimizar a soma das distâncias percorridas da fábrica em relação a cada 
um dos i centros de distribuição:
4
2 2
1
min ( ) ( )obj i j i j
i
F z x x y y
=
= = − + −∑ , ou ainda:
2 2 2 2 2 2
2 2
min (1 ) (1 ) (2 ) (3 ) (5 ) (2 )
 (3 ) (5 )
obj j j j j j j
j j
F z x y x y x y
x y
= = − + − + − + − + − + − +
− + −
As restrições do modelo estão especificadas a seguir:
Distâncias máximas de cada centro de distribuição em relação à nova fábrica:
2 2(1 ) (1 ) 10j jx y− + − ≤
2 2(1 ) (1 ) 10j jx y− + − ≤ (Curitiba)
2 2(2 ) (3 ) 10j jx y− + − ≤ (Barueri) 
2 2(5 ) (2 ) 3j jx y− + − ≤ (Cabo Frio)
2 2(3 ) (5 ) 10j jx y− + − ≤ (Viçosa)
454
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
7.8.1 Solução do Problema da Empresa Sabor & Degust pelo Solver do Excel
Antes de resolvermos o problema da empresa Sabor & Degust pelo Solver do Excel, precisamos 
classificá-lo como um modelo de programação quadrática, côncava, convexa, etc., para verificar se a 
solução obtida será ou não a ótima global. Como as restrições não são lineares e a função objetivo não 
é quadrática, não estamos diante de um modelo de programação quadrática. Adicionalmente, como o 
problema é de minimização e todas as restrições são de desigualdade, se ele for um modelo de programação 
convexa, podemos garantir que a solução encontrada pelo Solver será a ótima global.
Como a verificação da convexidade das funções não é trivial para esse exemplo, uma alternativa 
seria encontrar diversas soluções iniciais e, a partir daí, aplicar o algoritmo GRG2 do Solver para cada 
uma delas, verificando se todas convergem para a mesma solução ótima. Outra alternativa seria aplicar o 
algoritmo evolucionário e comparar com a solução obtida pelo algoritmo GRG2.
O Exemplo 7.13 da empresa Sabor & Degust será então resolvido nesta seção pelo Solver do Excel. 
A representação do problema em uma planilha do Excel está ilustrada na Figura 7.13 (veja arquivo 
Exemplo7.13_Sabor&Degust.xls). Pode-se verificar que a solução inicial considerada foi o ponto (0, 0).
Figura 7.13 Representação em Excel do problema da empresa Sabor & Degust.
As fórmulas utilizadas na Figura 7.13 estão especificadas no Quadro 7.3.
Quadro 7.3 Fórmulas utilizadas na Figura 7.13
Célula Fórmula
E4 = RAIZ((B4-$B$11)^2+(C4-$C$11)^2)
E5 = RAIZ((B5-$B$11)^2+(C5-$C$11)^2)
E6 = RAIZ((B6-$B$11)^2+(C6-$C$11)^2)
E7 = RAIZ((B7-$B$11)^2+(C7-$C$11)^2)
D11 =SOMA(E4:E7)
O Quadro 7.4 apresenta os nomes atribuídos às células e intervalos de células da Figura 7.13 que 
serão referenciados no Solver.
Quadro 7.4 Nomes atribuídos às células da Figura 7.13
Nome Células
Distância_real E4:E7
Distância_máxima G4:G7
Coordenadas_fábrica B11:C11
Distância_mínima D11
455
Capítulo 7 I Programação Não Linear
A representação do problema da empresa Sabor & Degust na caixa de diálogo Parâmetros do 
Solver está ilustrada na Figura 7.14, com os respectivos nomes atribuídos às células do modelo. Ainda 
na Figura 7.14, verifica-se que o problema será resolvido, inicialmente, pelo algoritmo GRG2 do Solver.
Figura 7.14 Parâmetros do Solver referentes ao problema da empresa Sabor & Degust.
Por fim, a Figura 7.15 apresenta a solução ótima do problema, a partir da solução inicial (0, 0) e 
utilizando o algoritmo GRG2 do Solver. Ademais, considerando outras soluções iniciais e aplicando 
novamente o algoritmo GRG2, chegou-se à mesma solução ótima. Por fim, o problema também foi 
resolvido pelo algoritmo evolucionário, chegando à mesma solução ótima.
Esses resultados indicam uma maior probabilidade de a solução ótima obtida pelo Solver ser a solução 
ótima global; porém, não temos essa garantia. 
Figura 7.15 Solução ótima obtida pelo Solver para o problema da empresa Sabor & Degust.
A solução ótima é, portanto, xj = 2,15, yi = 2,95 com z = 7,65.
456
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
7.9 O Problema de Seleção de Carteiras de Investimentos como um Problema 
de PNL
Conforme descrito na Seção 2.5.5 do Capítulo 2, Markowitz (1952) desenvolveu um modelo 
matemático de otimização de carteiras que busca escolher, entre um conjunto de investimentos 
financeiros, a melhor combinação que maximiza o retorno esperado da carteira e minimiza seu risco. 
O modelo recai em um problema de programação quadrática (a função objetivo f é quadrática e todas 
as restrições são lineares) que busca encontrar a fronteira eficiente da carteira. Os riscos da carteira são 
medidos por meio da variância do retorno dos ativos, calculado como a soma das variâncias individuais 
de cada ativo e das covariâncias entre os pares de ativos. 
No Capítulo 2 estudamos simplificações desse modelo que recaíram em problemas de programação 
linear.Descreveremos a seguir a formulação matemática geral do modelo de Markowitz.
Parâmetros do modelo:
VAR( )X = variância da carteira de investimento
2
iσ = variância do ativo i, i = 1,...,n 
ijσ = covariância entre os ativos i e j, i,j = 1,...,n 
iμ = retorno esperado do ativo i, i = 1,...,n 
ρ = nível mínimo requerido pelo investidor em relação ao retorno esperado da carteira 
Variáveis de decisão:
xi percentual do ativo i alocado na carteira, i = 1,...,n 
Formulação geral:
σ σ
μ ρ
−
= = = +
=
=
= +
=
≥
∑ ∑ ∑
∑
∑
1
2 2
1 1 1
1
1
min VAR( ) 2
sujeito a:
 1 (1)
 
n n n
i i ij i j
i i j i
n
i
i
n
i i
i
X x x x
x
x
≥ =
 (2)
 0 , 1,..., (3)ix i n
 
 (7.40)
que corresponde a um problema de programação quadrática.
A função objetivo do modelo busca, portanto, minimizar a variância da carteira com n ativos 
financeiros, medido como a soma das variâncias individuais de cada ativo e das covariâncias entre os 
pares de ativos. 
A restrição (1) garante que todo o capital será investido.
A restrição (2) garante que o retorno médio da carteira atingirá o limite mínimo requerido pelo 
investidor no valor de ρ .
457
Capítulo 7 I Programação Não Linear
Por fim, as variáveis de decisão devem atender à condição de não negatividade. 
Exemplo 7.14:
O investidor André Silva opera diariamente no home broker da corretora MDC Pactual e deseja 
selecionar uma nova carteira de investimentos que minimiza seu risco, medido pela variância da carteira. 
Para isso, André selecionou 5 investimentos candidatos e considerou o retorno mensal de cada um deles 
nos últimos 12 meses, conforme mostra a Tabela 7.3. Espera-se um limite mínimo de retorno mensal da 
carteira no valor de 0,95%. Formule o problema do investidor André Silva. 
Tabela 7.3 Retorno mensal de cada ativo nos últimos 12 meses
Ativo 1 Ativo 2 Ativo 3 Ativo 4 Ativo 5
Janeiro 2,13% 2,19% 4,26% 3,56% 1,29%
Fevereiro 3,05% 2,90% 0,89% 2,29% -0,23%
Março -0,62% 4,89% 0,96% 0,16% 1,89%
Abril -0,01% -0,80% -0,27% -0,77% 2,03%
Maio 2,80% -0,92% 1,42% 1,29% -0,14%
Junho 2,60% 1,32% 4,33% 4,02% -0,06%
Julho -1,60% -3,02% 0,79% -0,87% 0,97%
Agosto -3,22% 1,71% -0,61% 0,31% 0,12%
Setembro -2,23% 1,23% -2,42% -2,02% 1,98%
Outubro 1,60% -1,52% 1,29% 2,29% 1,45%
Novembro 6,22% -0,99% 2,94% 2,64% 1,24%
Dezembro -0,08% 3,98% 0,08% -1,14% 1,07%
 � Solução:
As variáveis de decisão do modelo são:
 x1 = porcentagem do capital investido no ativo 1
 x2 = porcentagem do capital investido no ativo 2
 M
 x5 = porcentagem do capital investido no ativo 5
Segundo Ragsdale (2009), a variância da carteira também pode ser expressa em termos matriciais:
Variância da carteira = x' × Cov
onde:
x' = (x1, x2, x3, x4, x5)
Cov = matriz de covariância = 
2
1 12 13 14 15
2
21 2 23 24 25
2
31 32 3 34 35
2
41 42 43 4 45
2
51 52 53 54 5
 
 
 
 
 
σ σ σ σ σ
σ σ σ σ σ
σ σ σ σ σ
σ σ σ σ σ
σ σ σ σ σ
⎤⎡ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎥⎢ ⎦⎣
458
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
O cálculo da matriz de covariância para o problema da empresa MDC Pactual está ilustrado na 
Tabela 7.4. O Quadro 7.5 apresenta as fórmulas utilizadas para o cálculo, a partir da representação do 
problema em Excel na Figura 7.16. 
Tabela 7.4 Matriz de covariância dos ativos
Ativo 1 Ativo 2 Ativo 3 Ativo 4 Ativo 5
Ativo 1 0,000655 -0,000089 0,000368 0,000380 -0,000053
Ativo 2 -0,000089 0,000525 -0,000013 0,000025 -0,000002
Ativo 3 0,000368 -0,000013 0,000384 0,000344 -0,000049
Ativo 4 0,000380 0,000025 0,000344 0,000387 -0,000069
Ativo 5 -0,000053 -0,000002 -0,000049 -0,000069 0,000066
Portanto, a função objetivo pode ser expressa como:
222
521
12 13 15
23 24 25
min VAR( ) 0,000655 0,000525 0,000066
 2( 0,000089 0,000368 0,000053
 0,000013 0,000025 0,000002
 
X x x x
x x x
x x x
= + + + +
+ − + + − +
− + − +
K
K
34 35
45
 0,000344 0,000049
 0,000069 )
x x
x
+ − +
−
As restrições do modelo estão especificadas a seguir:
1. Capital investido:
1 2 3 4 5 1x x x x x+ + + + =
2. Retorno médio esperado da carteira:
5210,0089 0,0091 0,0097 0,0095x x x+ + + ≥K
3. Restrições de não negatividade:
1 2 3 4 5, , , , 0x x x x x ≥
7.9.1 Solução do Problema da Corretora MDC Pactual pelo Solver do Excel
Conforme já especificado, a função objetivo do problema é quadrática e todas as restrições são 
lineares, recaindo em um problema de programação quadrática. Portanto, podemos garantir que a solução 
ótima encontrada pelo Solver será a solução ótima global.
O Exemplo 7.14 da corretora MDC Pactual será então resolvido nesta seção pelo Solver do Excel. 
A representação do problema em uma planilha do Excel está ilustrada na Figura 7.16 (veja arquivo 
Exemplo7.14_MDC_Pactual.xls). 
angelo
Destacar
459
Capítulo 7 I Programação Não Linear
Figura 7.16 Representação em Excel do problema da empresa MDC Pactual.
As fórmulas utilizadas na Figura 7.16 estão especificadas no Quadro 7.5.
Quadro 7.5 Fórmulas utilizadas na Figura 16
Célula Fórmula Copiado para
B17 =MÉDIA(B5:B16) C17:F17
I5 =COVAR($B$5:$B$16,B5:B16) J5:M5
I6 =COVAR($C$5:$C$16,B5:B16) J6:M6
I7 =COVAR($D$5:$D$16,B5:B16) J7:M7
I8 =COVAR($E$5:$E$16,B5:B16) J8:M8
I9 =COVAR($F$5:$F$16,B5:B16) J9:M9
B19 =SOMA(B25:F25)
B21 =SOMARPRODUTO(B17:F17, B25:F25)
G25 =SOMARPRODUTO(MATRIZ.MULT(B25:F25,I5:M9),(B25:F25))
A fórmula da célula G25 é uma fórmula alternativa àquela expressa na função objetivo, a fim de 
minimizar erros. 
O Quadro 7.6 apresenta os nomes atribuídos às células e intervalos de células da Figura 7.16 que 
serão referenciados no Solver.
Quadro 7.6 Nomes atribuídos às células da Figura 7.16
Nome Células
Capital_investido B19
Retorno_real B21
Retorno_esperado D21
Porcentagem_investida B24:F24
Variância_carteira G24
460
ELSEVIERPesquisa Operacional para Cursos de Engenharia I Patrícia Belfiore e Luiz Paulo Fávero
A representação do problema da corretora MDC Pactual na caixa de diálogo Parâmetros do Solver 
está ilustrada na Figura 7.17, com os respectivos nomes atribuídos às células do modelo. Como a solução 
obtida pelo Solver será a ótima global, resolveremos o problema apenas pelo algoritmo GRG2.
Figura 7.17 Parâmetros do Solver referentes ao problema da corretora MDC Pactual.
Por fim, a Figura 7.18 apresenta a solução ótima obtida pelo Solver. 
Figura 7.18 Solução ótima obtida pelo Solver para o problema da corretora MDC Pactual.
A solução ótima é, portanto, x1 � 0, x2 � 5,57%, x3 � 0, x4 � 21,27%, x5 � 73,17% com z � 0,000033.