Upload
fredy-yakuza
View
674
Download
9
Embed Size (px)
Citation preview
Pesquisa Operacional II – Prof. Edilson Machado de Assis
1
Otimização não linear
Disciplina: Pesquisa Operacional em Sistemas II
Professor: Edilson Machado de Assis
Pesquisa Operacional II – Prof. Edilson Machado de Assis
2
Introdução
Problemas de otimização em que a função objetivo ou pelo menos uma das restrições envolvidas não são funções lineares das variáveis de decisão são denominados Problemas de Programação não-linear – PNL.
Um problema de programação não-linear pode ser genericamente representado da seguinte forma:
Otimizar: z =f (x1,x2,...,xn)
Sujeito a: gl (xl, x2,..., xn) ≤ b1
g2 (xl, x2,..., xn) = b2
gm (xl, x2,..., xn) ≥ bm
Pesquisa Operacional II – Prof. Edilson Machado de Assis
3
Convexidade de funções de 1, 2 ou mais variáveis
Quando resolvemos problemas de programação linear através de ferramentas como o Solver do Excel, podemos afirmar que o resultado apresentado pelo software é realmente a solução ótima que procuramos (ou pelo menos uma delas no caso de soluções múltiplas). Resolvendo problemas de programação não-linear, entretanto, o Solver do Excel, bem como qualquer outro software, apresenta dificuldades.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
4
Melhor local e global
Devido às características dos problemas de PNL, não ha condições, a principio, de afirmarmos se o programa encontrou realmente o ponto máximo ou mínimo global da função, ou apenas um ponto de maximo ou mínimo local.
Para que tenhamos condições de assegurar que o resultado encontrado pelo Solver para um problema de programação não-linear é a solução ótima da função-objetivo, precisamos saber identificar as características de concavidade e convexidade das funções que compõem o modelo.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
5
Identificação de concavidade
De uma forma geral, podemos classificar as funções não-lineares em côncavas e convexas. Os métodos para identificar se uma determinada função é côncava ou convexa variam conforme o numero de variáveis da função. Veremos a seguir o procedimento para classificação de funções com uma, duas e mais de duas variáveis.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
6
Funções de uma variável
Funções contínuas de uma variável são as mais simples de serem classificadas. De uma forma genérica, descobrimos se uma função contínua de uma variável é convexa se, ao traçarmos uma linha unindo dois pontos da função, esta linha nunca se encontrar abaixo da curva.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
7
Teste analítico
Uma maneira pratica e rápida de verificarmos a convexidade de uma função de uma variável é por meio da análise da sua segunda derivada. Por este teste, uma função f(x) é:
a) convexa se 2
2
( )d f x
dx ≥ 0 x Domínio ;
b) estritamente convexa se 2
2
( )d f x
dx > 0 x Domínio ;
c) côncava se 2
2
( )d f x
dx ≤ 0 x Domínio ;
d) estritamente côncava se2
2
( )d f x
dx < 0 x Domínio .
Pesquisa Operacional II – Prof. Edilson Machado de Assis
8
Observações
Algumas observações devem ser feitas com relação às
definições:
a) Se a função é linear, 2
2
( )d f x
dx=0 x Domínio a
função é definida como côncava e convexa simultaneamente
b) Se 2
2
( )d f x
dx for positivo para alguns valores do
domínio e negativo para outros, então a função não é nem côncava, nem convexa.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
9
Exemplos Classifique quanto à convexidade:
a) 2( )f x x x ( )
2 1df x
xdx
e 2
2
( )2
d f x
dx (Estritamente convexa)
b) 3( ) 2 8f x x x
2( )3 2
df xx
dx e
2
2
( )6
d f xx
dx (Nem côncava nem convexa)
c) 2( )f x x x ( )
2 1df x
xdx
e 2
2
( )2
d f x
dx (Estritamente côncava)
Pesquisa Operacional II – Prof. Edilson Machado de Assis
10
Funções de 2 variáveis De forma análoga as funções de uma variável, as
derivadas parciais de segunda ordem de funções de duas variáveis podem ser usadas para determinar a convexidade da função.
Seja 1 2( , )f f x x uma função com derivadas parciais de segunda ordem continuas e seja a matriz Hessiana, H, definida pelas segundas derivadas da mesma função e D o determinante da matriz Hessiana.
2 2
1 2 1 22
1 212 2
1 2 1 22
2 1 2
( , ) ( , )
( , ) ( , )
f x x f x x
x xxH
f x x f x x
x x x
Pesquisa Operacional II – Prof. Edilson Machado de Assis
11
Classificação O Determinante é:
22 2 21 2 1 2 1 22 2
1 21 2
( , ) ( , ) ( , ).
f x x f x x f x xD
x xx x
Classificação D 2
1 22
1
( , )f x x
x
21 22
2
( , )f x x
x
Convexa ≥ 0 ≥ 0 ≥ 0 Estritamente
convexa >0 >0 >0
Côncava ≥0 ≤0 ≤0 Estritamente
côncava >0 <0 <0
Válido 1 2 1 2, ( , )x x Domínio f x x
Pesquisa Operacional II – Prof. Edilson Machado de Assis
12
Observações a) se a função é linear do tipo 1 2 0 1 1 2 2( , )f x x x x
então D = 0, 2
1 22
1
( , )f x x
x
=0 e
21 22
2
( , )f x x
x
=0
1 2 1 2, ( , )x x Domínio f x x e a função é definida como côncava e convexa simultaneamente; b) se D < 0, para algum dos possíveis valores 1x e 2x pertencentes ao domínio da função 1 2( , )f x x então a função não é nem côncava, nem convexa.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
13
Exemplos a) 2 2
1 2 1 1 2 2 1( , ) 3 2f x x x x x x x
1 21 2
1
( , )2 3
f x xx x
x
e 1 2
2 12
( , )2
f x xx x
x
2
1 22
1
( , )2
f x x
x
,
21 22
2
( , )2
f x x
x
2 2
1 2 1 2
1 2 2 1
( , ) ( , )1
f x x f x x
x x x x
2 1
1 2H
, logo D=3 e D>0, 2
1 22
1
( , )0
f x x
x
e
21 22
2
( , )0
f x x
x
1 2 1 2, ( , )x x Domínio f x x (Estritamente convexa)
Pesquisa Operacional II – Prof. Edilson Machado de Assis
14
Exemplos continuação
2 21 2 1 1 2 2 1( , ) 3 2f x x x x x x x
Pesquisa Operacional II – Prof. Edilson Machado de Assis
15
Exemplos b) 2 2
1 2 1 2( , )f x x x x
1 21
1
( , )2
f x xx
x
e 1 2
22
( , )2
f x xx
x
2
1 22
1
( , )2
f x x
x
,
21 22
2
( , )2
f x x
x
2 2
1 2 1 2
1 2 2 1
( , ) ( , )0
f x x f x x
x x x x
2 0
0 2H
, logo D=-4 e D<0
1 2 1 2, ( , )x x Domínio f x x (Não é côncava nem convexa)
Pesquisa Operacional II – Prof. Edilson Machado de Assis
16
Exemplos continuação 2 2
1 2 1 2( , )f x x x x
Pesquisa Operacional II – Prof. Edilson Machado de Assis
17
Funções de mais de 2 variáveis O primeiro passo para determinar a convexidade de funções de mais de duas variáveis é montar a matriz Hessiana da função analisamos. Seja 1 2 3( , , ,... )nf x x x x uma função de n variáveis, a matriz Hessiana e uma matriz simétrica n n formada por todas as derivadas parciais de segunda ordem desta função:
2 2 2 2
21 2 1 3 11
2 2 2 2
22 1 2 3 222 2 2 2
23 1 3 2 33
2 2 2 2
21 2 3
n
n
n
n n n n
f f f fx x x x x xx
f f f fx x x x x xx
H f f f fx x x x x xx
f f f fx x x x x x x
Pesquisa Operacional II – Prof. Edilson Machado de Assis
18
Determinantes menores São calculados os determinantes 1 2, ,..., nD D D . Estes são chamados determinantes dos menores principais da matriz hessiana e serão em número igual ao numero de variáveis da função.
2
1 21
fD
x
2 2
21 21
2 2 2
22 1 2
f fx xx
Df f
x x x
2 2 2
21 2 1 31
2 2 2
3 22 1 2 322 2 2
23 1 3 2 3
f f fx x x xx
f f fD
x x x xxf f f
x x x x x
Pesquisa Operacional II – Prof. Edilson Machado de Assis
19
Determinantes menores
Generalizando
2 2
211
2 2
21
n
n
n n
f fx xx
D
f fx x x
Pesquisa Operacional II – Prof. Edilson Machado de Assis
20
Classificação 1D 2D 3D ... nD
Convexa ≥ 0 ≥ 0 ≥ 0 ≥ 0 Estritamente
convexa >0 >0 >0 >0
Côncava ≤0 ≥0 ≤0 ... Estritamente
côncava <0 >0 <0 ...
Côncava e convexa =0 =0 =0 =0
Válido 1 2 1 2, ( , )x x Domínio f x x Se f é linear, é côncava e convexa simultaneamente. Se nenhuma das condições apresentadas for atendida, a função não é nem côncava, nem convexa.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
21
Exemplos a) 2
1 2 3 1 3 2( , , )f x x x x x x
31
fx
x
22
2f
xx
11
fx
x
2 2 2
21 2 1 31
2 2 2
22 1 2 322 2 2
23 1 3 2 3
0 0 1
0 0 1
0 2 0 0 2 0
1 0 0
1 0 0
f f fx x x xx
f f fH
x x x xxf f f
x x x x x
1 0 0D 2
0 00
0 2D
3
0 0 1
0 2 0 2
1 0 0
D
A função é convexa
Pesquisa Operacional II – Prof. Edilson Machado de Assis
22
Exemplos b) 2 2 2
1 2 3 1 2 3 1 2 1 3 2 3( , , ) 2f x x x x x x x x x x x x
1 2 31
2 2f
x x xx
2 1 3
2
2f
x x xx
3 1 2
3
2 2f
x x xx
2 2 2
21 2 1 31
2 2 2
22 1 2 32
2 2 2
23 1 3 2 3
2 1 2
2 1 2
1 2 1 1 2 1
2 1 2
2 1 2
f f fx x x xx
f f fH
x x x xxf f f
x x x x x
1 2 2D 2
2 13
1 2D
3
2 1 2
1 2 1 8
2 1 2
D
A função não é côncava nem convexa
Pesquisa Operacional II – Prof. Edilson Machado de Assis
23
Programação Côncava, Convexa e Quadrática O principal interesse é saber se algoritmos eletrônicos, como o Solver do Excel, o LINGO e outros, encontrarão a solução ótima do problema sem dificuldades. O Solver utiliza um algoritmo chamado GRG (generalized reduced gradient) para chegar a solução do problema. Este algoritmo consiste em, a partir de uma condição inicial, seguir passo a passo, calculando valores para as variáveis do modelo e verificando o comportamento da função objetivo.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
24
Programação Côncava, Convexa e Quadrática No momento em que o valor da função objetivo
inverte de tendência, ou seja, deixa de crescer para diminuir (caso de maximização) ou deixa de diminuir para começar a crescer (caso de minimização), o Solver assume que encontrou um ponto de maximo ou de mínimo da função, que pode ser tanto um extrema local como global. No entanto, com este procedimento, o algoritmo não garante que a solução encontrada seja a solução global, pois a princípio não há certeza se aquela função analisada não irá inverter o seu comportamento novamente.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
25
Programação Côncava, Convexa e Quadrática
Se nos utilizarmos o Solver para encontrarmos o ponto de maximo da função da figura é bastante provável que o algoritmo encontre diversas soluções dependendo dos valores com os quais iniciamos a otimização, o Solver pode indicar o ponto 1 ou o ponto 3 como o ponto que maximiza a função, sendo que, no entanto, apenas o ponto 3 é o maximo global da função e, portanto, o resultado.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
26
Mínimo e máximo global e local Diante da incerteza quanto ao resultado apresentado
pelo Solver, precisamos saber se o tipo do modelo permite que a solução dada pelo algoritmo seja assumida como a solução ótima do problema. Quando o modelo não apresenta restrições, esta análise fica bastante simples. O fato da função-objetivo ser côncava é condição necessária e suficiente para garantirmos que o maximo encontrado peio algoritmo e maximo global. De forma análoga, o fato da função-objetivo de um PNL sem restrições ser convexa é condição necessária e suficiente para garantirmos que o mínimo encontrado também seja global.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
27
Problemas freqüentes Ha três tipos de problemas de programação não-
linear muito freqüentes que atendem a aquelas condições: a programação côncava, a programação convexa e a programação quadrática.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
28
Programação Côncava e Programação Convexa Se a função objetivo do PNL for uma função côncava
(no caso de uma maximização) ou convexa (no caso de uma minimização), o modelo será eficientemente resolvido pelo algoritmo aplicado se o conjunto de soluções viáveis do problema formar um conjunto convexo
Podemos garantir que o conjunto de soluções viáveis de um PNL com restrições (apenas inequações) é um conjunto convexo se todas as restrições respeitarem as regras abaixo
Se a restrição for do tipo ( )i ig x b e ( )ig x for uma função convexa
Se a restrição for do tipo ( )i ig x b e ( )ig x for uma função côncava.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
29
Programação Côncava e Programação Convexa - cont Decorre desta consideração que, se o modelo for uma
maximização, a função objetivo for uma função côncava e o conjunto de soluções viáveis for um conjunto convexo, 0 PNL é dito de Programação Côncava e o maximo encontrado é global.
Similarmente, se o modelo for uma minimização, a função objetivo for uma função convexa e o conjunto de soluções viáveis for um conjunto convexo, o PNL é dito de Programação Convexa e o mínimo encontrado é global.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
30
Programação Quadrática Os problemas que forem classificados como de
Programação Quadrática, independentemente do modelo se tratar de maximização ou de minimização, terão a sua solução ótima encontrada pelos algoritmos de resolução de problemas não-lineares sem dificuldades.
Uma função quadrática de n variáveis (xl,x2,x3,...,xn) é uma função que pode ser escrita da seguinte forma:
12
1 21 1 1 1
( , ,..., )n n n n
n i i ij i j i ii i j i i
f x x x Ax B x x C x D
Pesquisa Operacional II – Prof. Edilson Machado de Assis
31
Programação Quadrática - continuação Em outras palavras, a função quadrática é a soma de
termos envolvendo o quadrado de variáveis 2i iAx ,
produto de variáveis ij i jB x x , funções lineares ijC e constantes D .
Exemplos
21 1 1
2 21 2 1 1 2 2 1 2
( )
( , )
f x ax bx c
f x x ax bx x cx dx ex f
Pesquisa Operacional II – Prof. Edilson Machado de Assis
32
Programação Quadrática - continuação Um problema de programação cujo modelo é uma
maximização ou uma minimização é dito de Programação Quadrática se:
A função objetivo for uma função quadrática. O conjunto de restrições apresentar somente restrições
lineares. Como o conjunto de restrições é formado apenas por
funções lineares da mesma maneira que nos problemas de programação linear, podem garantir que o conjunto de soluções será um conjunto convexo. Portanto, num caso de Programação Quadrática de Maximização em que a função objetivo é uma função côncava o Excel encontrará o maximo global.
Naturalmente num caso de Programação Quadrática de Minimização em que a função objetivo é uma função convexa, o Excel encontrará o mínimo global.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
33
Programação não-linear utilizando o Excel Quando o modelo não se tratar de um problema de programação côncava, convexa ou quadrática, uma maneira pratica para tentar minorar os problemas 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, então podemos ter maior confiança, mas não a certeza de termos atingido um ponto global. Caso contrário, deveremos supor a existência de diversos extremos locais (relativos) e assumir o melhor valor encontrado.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
34
Controle de estoque Um dos modelos mais elementares de controle de estoque chama-se Modelo do Lote Econômico. Este modelo é simples, pois assume que a demanda anual de um produto a ser pedido é constante e que cada novo pedido do produto deve chegar no exato momento em que o estoque chegar a zero. O objetivo do é determinar, por meio do balanceamento dos custos associados ao estoque, o tamanho e a periodicidade do pedido que minimizem o custo total. Os custos mais relevantes que determinam o custo total de estocagem são os seguintes:
Pesquisa Operacional II – Prof. Edilson Machado de Assis
35
Custos envolvidos
a) custo de manutenção do estoque - custo associado ao valor em estoque e que poderia estar aplicado em diversas formas de investimentos, rendendo benefícios financeiros para a empresa, além dos custos de armazenagem;
b) custo do pedido - custo associado ao trabalho de efetuar o pedido de um lote de produtos, engloba custos de mão-de-obra, de transporte do pedido e outros, tais como controle do recebimento do pedido e controle de qualidade do lote recebido;
c) custo de falta - custo relacionado a perdas decorrentes da interrupção da produção devido à falta do produto;
Pesquisa Operacional II – Prof. Edilson Machado de Assis
36
Exemplo Uma empresa que demanda anualmente 100 unidades de um produto. Caso ela decida realizar quatro pedidos trimestrais, os apenas dois semestrais teremos as representações das suas políticas de estoque conforme as figuras:
As políticas de estoque apresentadas acima são apenas duas das diversas formas de atender a demanda anual de 100 unidades que a empresa pode realizar. Porem, como poderemos saber qual e a mais econômica?
Pesquisa Operacional II – Prof. Edilson Machado de Assis
37
Exemplo – continuação Podemos modelar o problema com a função objetivo:
Minimizar .2 m
D QCusto total DC S C
Q
onde: D = demanda anual do produto C = custo unitário do produto Q= quantidade de unidades por pedido (tamanho do lote) S = custo unitário do pedido (custo para fazer o pedido) mC = custo unitário de manutenção do produto em estoque por ano.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
38
Exemplo - continuação Resolvendo problemas deste tipo, dispomos geralmente dos valores da demanda anual, do custo unitário do produto, do custo unitário de pedido e do custo unitário de manutenção, de forma que a variável que vai alterar o valor do custo total anual é a quantidade de unidades por pedido (Q). Considerando-se que a variável Q aparece tanto no numerador quanto no denominador da função objetivo, o modelo é um problema de programação não linear.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
39
Problema prático 1 A LCL Computadores Ltda., empresa montadora de computadores, deseja diminuir o seu estoque de mainboards. Sabendo-se que o custo unitário da mainboard é de R$50, o custo anual unitário de manutenção de estoque é de R$20 e o custo unitário do pedido é de R$10, encontre o lote econômico para atender a uma demanda anual de 1.000 mainboards.
Solução
Se o problema for de programação convexa ou quadrática (não pode ser côncava por se tratar de uma minimização), teremos condições de afirmar que a solução ótima apresentada pelo Solver é o mínimo global da função do custo total anual.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
40
Solução
Minimizar 10001000 50 10 20
2Q
Custo totalQ
Sujeito a: 1 0Q e Q Não se trata de programação quadrática. Verificação de convexidade:
2
23
2 3
10000( ) 50 000 10.
( )10000. 10
20000( )20000.
f Q QQ
df QQ
dQd f Q
QdQ Q
Pesquisa Operacional II – Prof. Edilson Machado de Assis
41
Solução - continuação
Função estritamente convexa 2
2
( )0
d f Q
dQ e temos um
conjunto convexo de restrições e por conseqüência temos um modelo de programação convexa. (Mínimo global, Solver soluciona)
Pesquisa Operacional II – Prof. Edilson Machado de Assis
42
Solução - continuação
Os dados iniciais do problema ficam:
Célula B7: =B3*B4+B3/B7*B5+B7/2*B6
Pesquisa Operacional II – Prof. Edilson Machado de Assis
43
Solução - continuação Aplicando o Solver
Pesquisa Operacional II – Prof. Edilson Machado de Assis
44
Solução - continuação Solução
Solução inteira
Resposta
_ 1000_ 31,25
_ _ _ 32Demanda anual
Núm lotesNúm unidades por lote
Pesquisa Operacional II – Prof. Edilson Machado de Assis
45
Problema prático 2 O Gerente de Projetos da LCL Telefonia Celular S.A. precisa localizar uma antena de transmissão para atender a três localidades da Baixada Fluminense no estado do Rio de Janeiro. Devido a problemas técnicos, a torre não pode estar a mais de 10 km do centro de cada cidade. Considerando as localizações relativas abaixo, o gerente deve tomar a decisão do melhor posicionamento para a antena.
Localidade x y
Nova Iguaçu -5 10
Queimados 2 1
Duque de Caxias 10 5
Pesquisa Operacional II – Prof. Edilson Machado de Assis
46
Continuação problema prático 2
Pesquisa Operacional II – Prof. Edilson Machado de Assis
47
Solução Função objetivo: Minimizar a soma das distâncias entre a torre e as cidades. Restrições: As distancias são menores que 10 Km Função objetivo:
2 2
i ii
Minimizar x X y Y
2 2 2 2
2 2
5 1 0 2 1
10 5
X Y X Y
X Y
Pesquisa Operacional II – Prof. Edilson Machado de Assis
48
Solução Função objetivo:
2 2
i ii
Minimizar x X y Y
2 2 2 2
2 2
5 1 0 2 1
10 5
X Y X Y
X Y
Restrições:
2 2
2 2
2 2
105 10
102 1
1010 5
X Y
X Y
X Y
É difícil comprovar se a função objetivo é convexa ou não. Repete-se o Solver com várias estimativas.
Pesquisa Operacional II – Prof. Edilson Machado de Assis
49
Solver
Célula D2: =RAIZ((B2-B$6)^2+(C2-C$6)^2) Célula B7: =SOMA(D2:D4)
Pesquisa Operacional II – Prof. Edilson Machado de Assis
50
Solver