Universidade Federal de Itajubá – UNIFEI
Instituto de Recursos Naturais - IRN
Programação Não-Linear
por
Prof. Benedito C. Silva
Programação Não-Linear
Programação Não-Linear
Programação Não-Linear
Programação Não-Linear
Métodos de solução:
• Substituição
• Gráfico
• Multiplicadores de Lagrange
• Método do Gradiente
• Programação Quadrática
• Condições de Karush-Kuhn Tucker
• Método de Newton
• Método de variações nas Coordenadas
• Linearização de funções separáveis
Programação Não-Linear
Solução Gráfica
Solução Gráfica
Solução Gráfica
Solução Gráfica
MaxZ  54x1  9x12  78x2  13x22
Importante!
Otimização Unidimensional
Busca pela Razão Áurea
Válida para um intervalo que contenha uma única resposta (máximo)
f(x)
Xl é o limite inferior do intervalo
Máximo
XU é o limite superior do intervalo
Xl
X1
X2
XU
X1 e X2 são pontos intermediários usados na busca do máximo
Otimização Unidimensional
Busca pela Razão Áurea
A escolha dos pontos internos pode ser feita de acordo com os
seguintes critérios
f(x)
Máximo
0 = 1 + 2
(a)
1 2
=
0 1
(b)
(a) em (b)
Xl
X2
1
0
X1
XU
2
1
2
=
1 + 2 1
1 + 2 1
=
1
2
Ou,
Otimização Unidimensional
Busca pela Razão Áurea
=
Fazendo
1+ =
1

2
1
chega-se a:
ou,
2 +  − 1 = 0
A raiz positiva será dada por:
−1 + 1 − 4. (−1)
5−1
=
=
= 0,61803 …
2
2
,  …

Razão Áurea
Otimização Unidimensional
Busca pela Razão Áurea
Encontrando o ponto ótimo usando a razão áurea:
1. Escolhe-se os pontos Xl e XU, que definem o intervalo de busca
2. Os pontos interiores são escolhidos usando-se a razão áurea, da
seguinte forma:
5−1
=
( −  )
2
1 =  + )
2 =  − )
3. Calcula-se f(X1) e f(X2)
4. Se f(X1) > f(X2), então:
O domínio a esquerda de X2 deve ser eliminado. Ou seja, X2
passa a ser Xl, X1 passa a ser X2 e
1 =  +
5−1
( −  )
2
Otimização Unidimensional
Busca pela Razão Áurea
Encontrando o ponto ótimo usando a razão áurea:
Se f(X2) > f(X1), então:
O domínio a direita de X1 deve ser eliminado. Ou seja, X1
passa a ser XU, X2 passa a ser X1 e
5−1
2 =  −
( −  )
2
Exemplo:
Usar o método de busca pela seção áurea para encontrar o
máximo da função abaixo, no intervalo de X entre 0 e 4.
  = 2. sen 
2
− 10
Otimização Unidimensional
Interpolação Quadrática
Este método parte do princípio que um polinômio do segundo grau fornece
uma boa aproximação para a forma da função objetivo, f(x), nas
proximidades do ponto ótimo.
Existe apenas uma parábola ligando 3 pontos. Portanto, se existem 3 pontos
que delimitem um ponto ótimo, pode-se ajustar uma parábola aos 3 pontos,
derivá-la e igualar o resultado a zero, para estimar o valor ótimo de X.
f(x)
Ótimo aproximado
Ótimo verdadeiro
Função verdadeira
Função quadrática
X0
X1
X3
X2
Otimização Unidimensional
Interpolação Quadrática
O valor de X3 pode ser obtido pela seguinte equação:
3
=
 0 . 12 −22 + 1 . 22 −02 + 2 . 02 −12
2. 0 . 1 −2 +2. 1 . 2 −0 +2. 2 . 0 −1
Onde, X0, X1 e X2 são aproximações iniciais e X3 é o valor de X que
corresponde ao máximo valor da função quadrática ajustada às
aproximações.
Realizam-se iterações. Em cada uma delas, avaliam os valores da função
para os pontos escolhidos e descarta-se um deles , reduzindo-se o espaço
de busca.
Exemplo:
Usar a interpolação quadrática para encontrar o máximo da função abaixo,
com as aproximações iniciais X0 = 0, X1 = 1 e X2 = 4.
  = 2. sen 
2
− 10
Otimização Unidimensional
Método de Newton
Utiliza a seguinte equação para uma busca iterativa do ótimo da função:
′()
+1 = − "()
Exemplo:
Usar o Método de Newton para encontrar o máximo da função abaixo, com
aproximação inicial X0 = 2,5.
  = 2. sen 
2
− 10
MÉTODOS DE BUSCA DIRETA
Busca Aleatória
Método do tipo “força bruta”
Consiste em calcular repetidamente a função objetivo a partir de valores
das variáveis independentes escolhidos aleatoriamente.
Se um número suficiente de amostras for estudado, o valor ótimo será
eventualmente localizado
Exemplo:
Use a função de geração de números aleatórios do MSExcel (aleatório)
para encontrar o máximo da função abaixo, no domínio limitado por x=-2
a 2 e y=-1 a 1,5
f(x,y) = y – x – 2x2 - 2xy – y2
Método Univariacional
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Estratégia de caminhar “morro acima”
Função objetivo: F(x1,x2)
5
4.5
4
3.5
3
x2
2.5
2
1.5
Máximo local
1
Máximo global
0.5
0
0
0.5
1
1.5
2
x1
2.5
3
3.5
4
4.5
5
Início: ponto coordenadas (parâmetros) aleatórias
5
4.5
X2=valor
aleatório entre
ced
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
X1=valor aleatório entre a e b
Determina direção de busca: exemplo x2=x2+0,3; x1=x1
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Função objetivo melhorou? Não, então tenta no outro sentido.
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Não, então volta para o ponto anterior...
...e muda a direção de busca.
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
F.O melhorou? Sim, então continua no mesmo sentido
E assim segue até encontrar um ponto em que não existe
direção de busca que melhore o valor da FO
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Exemplo:
Use o método univariacional para encontrar o máximo da função abaixo,
a partir do ponto inicial (X1=-10 e X2=-10
f(X1,X2) = X12 + 8.(X1-X2) + X1.X2 + X22
Rosenbrock: Método um pouco mais eficiente
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
0
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
Direção de busca é a que potencialmente dará maior incremento da FO
Muito utilizado para calibração automática de modelos hidrológicos
Download

Programação Linear