AULA COMPUTACIONAL
- Otimização Paramétrica (Cap. 5)
15 DE SETEMBRO DE 2008
5. OTIMIZAÇÃO PARAMÉTRICA
5.1 Conceito de Otimização
5.2 Elementos Comuns em Problemas de Otimização
5.2.1 Variáveis de Decisão (Manipuladas)
5.2.2 Critério
5.2.3 Função Objetivo
5.2.4 Restrições
5.2.5 Região Viável
5.3 Localização da Solução Ótima
5.4 Problemas e Métodos de Otimização
5.5 Método Analítico: problemas univariáveis e multivariáveis.
5.6 Métodos Numéricos: problemas univariáveis e multivariáveis
5.6. MÉTODOS NUMÉRICOS
São métodos de busca por tentativas.
Os métodos podem ser:
- Diretos: utilizam apenas o valor da Função Objetivo.
- Indiretos: utilizam também o valor da(s) derivada(s) da Função Objetivo
(menor números de tentativas mas o esforço computacional é maior).
Os pesquisadores buscam desenvolver métodos que atendam às
seguintes propriedades:
- Eficiência: resolver o mesmo problema com menor esforço.
- Robustez: resolver uma variedade maior de problemas.
5.6. MÉTODOS NUMÉRICOS
5.6.1 Problemas Univariáveis
Método da Seção Áurea
Utiliza dois pontos posicionados de forma a manter:
(a) simetria em relação aos limites do intervalo
(b) fração eliminada constante
Método da Seção Áurea
Base: Retângulo Áureo (esteticamente perfeito, segundo os gregos)
Propriedade: removendo um quadrado de lado igual ao lado menor,
1- e
e
1
resulta um outro retângulo com as mesmas proporções do retângulo
original

Razão Áurea
1
e

 e 2  e  1  0  e  0,618
e 1 e
Algoritmo da Seção Áurea
ÁUREA
Iniciar
Repetir
Eliminar Região
Atualizar Delta
Se Convergiu Então Finalizar
Colocar Novo Ponto
Convergiu
Delta  Tolerância
Iniciar
Repetir
Eliminar Região
Atualizar Delta
Se Convergiu Então Finalizar
Colocar Novo Ponto
Eliminação de Região
Problema de Mínimo
Fs
Eliminação de Região
Problema de Máximo
Fi
Li
xs
xi
Li
Ls
xs
Fs
Atualiza 
Tolerância ?
Novo Ponto
xi
Atualiza 
Tolerância ?
Novo Ponto
Fi
Fi
Fi
Li
Fs
Li
xs
0,618 
xs
xi
Ls
Fs
Inicialização
xi
Ls
 = L - L
s
i
xi = Li + 0,618
xs = Ls - 0,618
Li
xs
xi
0,618 
Ls
Ls
5.5 MÉTODO ANALÍTICO
5.5.1 Problemas univariáveis
Exemplo:
dimensionamento do extrator
W kg B/h
Q = 10.000 kgA/h
x kgB/kgA
rafinado
xo= 0,02 kg AB/kg A
y kg AB/kg B
extrato
Modelo Matemático:
Balanço de Informação:
1. Q (xo - x) - W y = 0
V = 5, N = 2, C = 2, M = 0
2. y - k x = 0 (k = 4)
G = 1 (otimização)
Avaliação Econômica:
L=R-C
R = pAB W y
C = pB W
pAB = 0,4 $/kgAB : pB = 0,01 $/kgB
Seqüência de Cálculo
x y W
1 * * *
2 * *
x y W

1 x x o
2 x o
2. y = k x
1. W = Q (xo - x)/y
Restrições de Igualdade !!!
Função Objetivo: L = R - C = pAB W y - pB W
Incorporando a L às Restrições de Igualdade ordenadas :
2. y = k x
1. W = Q (xo - x)/y
L = a - b x - c/x
a = Q ( p AB x o +
pB
k
) = 105
b = p AB Q = 4000
c =
p B Qx o
= 0 ,5
k
L = a - b x - c/x
60
Busca do ponto estacionário:
dL
50
= - b+
dx
R
40
c
b
Solução completa do problema:
o
d2L
dx 2
L = 15,6
L
10
= 0 , 01118
yo = 0,04472 kg AB/kg B;
Wo = 1.972,3 kgB/h;
Ro = 35,3 $/h; Co = 19,7 $/h;
Lo = 15,6 $/h
C
L,R,C 30
$/a
20
c
= 0 || x o =
x2
= -2
xo
c
<0
o 3
(x )
Máximo!
o
x =0, 01118
0
0,006
0,008
0,010
0,012
0,014
0,016
x kgAB/kg A
0,018
0,020
0,022
5.6. MÉTODOS NUMÉRICOS
5.6.2 Problemas Multivariáveis
Alguns métodos diretos:
- Busca Aleatória
- Busca por Malhas
- Busca Secionada
- Simplex (Poliedros Flexíveis)
- Hooke & Jeeves
Procedimento Geral:
(a) seleção de um ponto inicial (base).
(b) exploração da vizinhança da base para inferir uma direção de busca.
(c) progressão na direção de busca até decisão em contrário.
(d) finalização
Os métodos diferem quanto à forma de executar a exploração e a
progressão.
Método de Hooke & Jeeves
ALGORITMO
Estabelecer um incremento e uma tolerância para cada variável
Escolher uma Base
Repetir
Explorar a vizinhança da Base (em busca da direção provável do ótimo)
Se houve Sucesso em alguma direção
Então: Progredir (na direção provável) até haver um Insucesso
Senão (proximidade do ótimo):
Se Chegou ao Ótimo
Então: Finalizar
Senão: reduzir os incrementos
Exploração
Testar a Função Objetivo em cada sentido (incrementos + i e - i) de
cada direção (xi) ao redor da Base.
Do resultado, depreender
a direção provável do
?
ótimo
+ 2
?
- 1
Base
+ 1
?
- 2
?
A Exploração não pode ser interrompida sem que todas as direções
tenham sido testadas.
Exploração
Funções unimodais: o sucesso num sentido dispensa o teste no outro.
S: Sucesso
I: Insucesso
S
+ 2
0,5
0,4
Sucesso
S
0,3
y
Base
desnecessário
0,2
- 2
buscando máximo
0,1
0,0
0,0
- 1
0,2
0,4
x
0,6
0,8
1,0
I
Exploração
O Sucesso numa tentativa justifica a mudança da Base para a nova
posição. A Exploração continua a partir desta melhor posição.
S
+ 2
S
- 2
I
- 1
Base
Método de Hooke & Jeeves : Fase de Progressão
22
Progredir com duplo incremento
até ocorrer um Insucesso
x2
Insucesso!
Permanecer na
Base (25)
+ 2 2
Sucesso!
Mover a Base.
Continuar a Progressão
25
+ 2 1
+ 2 2
Exploração a partir da
Base (25) com 1 e 2 .
18
+ 2 1
+ 2
+1
10
Base
15
Resultado da Exploração
x1
Se Chegou ao Ótimo
Então: Finalizar
Senão: reduzir os incrementos
A Base estará suficientemente próxima para ser declarada como o
ótimo?
Se todos os incrementos estiverem menores do que as tolerâncias,
SIM!: Finalizar
Se algum deles estiver maior, então este deve ser reduzido à metade.
Inicia-se uma nova Exploração à volta da Base com os novos
incrementos
x2
Se Chegou ao Ótimo
Então: Finalizar
Senão: reduzir os incrementos
5
- e1
+ e1
+ 2
+ e2
- 1
+1
7
- e2
10
8
Base
- 2
9
1 > e1 e 2 > e2 : ainda não chegou ao ótimo : 1 = 1 /2 , 2 = 2 /2
x1
x2
- e2
Se Chegou ao Ótimo
Então: Finalizar
+ e1
5
+ e2
+ 2
7
- 1
10
+1
8
Base
- e2
- 2
9
1 < e1 e 2 < e2 : a Base pode ser considerada o Ponto Ótimo
x1
Exemplo: dimensionamento de 2 extratores em série
W kgB/h
1
Q = 10.000 kgA/h
xo = 0,02 kgAB/kgA
x kgAB/kgA
1
1
x kgAB/kgA
2
2
y
Modelo Matemático
1. Q(xo - x1) - W1 y1 = 0
2. y1 - k x1 = 0
3. Q(x1 -x2) - W2 y2 = 0
4. y2 - k x2 = 0
W kgB/h
2
1
kgAB/kgB
y
2
kgAB/kgB
Avaliação Econômica
L=R-C
R = pAB (W1 y1 + W2 y2 )
C = pB (W1 + W2)
pAB = 0,4 $/kgAB : pB = 0,01 $/kgB
Balanço de Informação: V = 8; N = 4; C = 2; G = 2 (otimização)
Exemplo: dimensionamento de 2 extratores em série
Modelo Matemático
1. Q (xo - x1) - W1 y1 = 0
2. y1 - k x1 = 0
3. Q(x1 -x2) - W2 y2 = 0
4. y2 - k x2 = 0
Modelo Matemático
2. y1 = k x1
4. y2 = k x2
3. W2 = Q (x1 – x2)/ y2
1. W1 = Q (xo - x1)/ y1
1
2
3
4
W1 x1 y1 W2 x2 y2
* * *
* *
*
* * *
* *
1
2
3
4
W1 x1 y1 W2 x2 y2
o x x
x o
x
o x x
x o
Incorporando as Restrições de Igualdade à Função Objetivo L
L=R–C
R = pAB (W1 y1 + W2 y2 )
C = pB (W1 + W2)
2. y1 = k x1
4. y2 = k x2
3. W2 = Q (x1 – x2)/ y2
1. W1 = Q (xo - x1)/ y1
L = a – b/x1– cx2 – d x1/x2
a = pAB Q xo + 2 pB Q / k = 130; b = pB Q xo/ k = 0,5; c = pAB Q = 4000; d = pB Q / k = 25
Buscando o ponto estacionário:
L/x1 = b/x12 – d/x2 = 0
x1o = (b2/cd)1/3 = 0,01357
L/x2 = - c + dx1/x22 = 0
x2o = (d/b) x12 = 0,00921
Solução completa:
y1o = 0,05428 kgAB/kgB; W1o = 1.184 kgB/h
y2o = 0,03684 kgAB/kgB; W2o = 1.184 kgB/h
Co = 23,68 $/h; Ro = 43,15 $/h; Lo = 19,47 $/h
Analisando o ponto estacionário:
L/x1 = b/x12 – d/x2 = 0
x1o = (b2/cd)1/3 = 0,01357
L/x2 = - c + dx1/x22 = 0
x2o = (d/b) x12 = 0,00921
  2L

2

x
1
H(x1o ,x o2 )   2
 L

 x1x 2
det(H - I) = 0
b

 2L 

2

 (x o )3
x 2x1 
1

=
 d
 2L 

o 2
2 
x 2  xo  (x 2 )

d 
(xo2 )2   4  105

o
d x1  2,95  105
2 o 3 
(x 2 ) 
1 = -0,258106
Máximo!
e
2,95  105 

8,69  105 
2 = -1,011106
W1 = 1.184
kgB/h
x1 = 0,01357
kgAB/kgA
Q = 10.000 kgA/h
xo = 0,02 kgAB/kgA
W2 = 1.184
kgB/h
1
2
y1 =
0,05428
kgAB/kgA
Estágio
Soluto Recup. kg/h
Solv. Consum. kg/h
Lucro $/a
x2 =
0,00921
kgAB/kgA
y2 =
0,03824
kgAB/kgA
1
2
64,28
1.184
13,87
43,62
1.184
5,61
Total
107,90
2.368
19,48
0,020
0,018
8,0
0,016
10
0,014
16
0,012
X2 0,010
0
4,0 2,0
6,0
19,5
0,00921
14
18
0,008
0,006
12
0,004
0,01357
0,002
0,005
0,010
0,015
0,020
X1
0,025
0,030
0,035
Seguem-se todos os resultados possíveis da Exploração em 2 dimensões
x2
Direção x1
Unimodalidade: dispensa + 1
Direção x2
Unimodalidade: dispensa + 2
Sucesso: deslocar a Base
- 1
15
10
Base
- 2
18 Sucesso: deslocar a Base
Direção provável do ótimo
x1
x2
Direção provável do ótimo
Direção x1
Unimodalidade: dispensa + 1
18 Sucesso:
deslocar a Base Direção x2
+ 2
Sucesso: deslocar a Base
- 1
15
10
Base
- 2
12 Insucesso:
permanece na Base
x1
x2
Direção x1
Unimodalidade: dispensa + 1
Direção x2
13 Insucesso:
permanecer na Base
Direção + 
2
provável
Sucesso: deslocar a Base
do ótimo
- 1
15
10
Base
- 2
12 Insucesso:
permanecer na Base
x1
x2
Direção x1
Direção x2
Unimodalidade: dispensa + 2
Sucesso: deslocar a Base
7
- 1
Insucesso:
permanecer na Base
10
Base
+1
15
- 2
18 Sucesso:
deslocar a Base
Direção provável do ótimo
x1
Direção provável do ótimo
x2
Direção x1
18
Direção x2
Sucesso:
deslocar a Base
+ 2
7
- 1
Insucesso:
permanecer na Base
10
Base
+1
15
Sucesso:
deslocar a Base
- 2
12
Insucesso:
permanecer na Base
x1
x2
Direção x1
Insucesso:
11 permanecer na Base
Direção x2
+ 2
7
- 1
Insucesso:
permanecer na Base
10
Base
+1
- 2
Sucesso:
deslocar a Base
15
Direção provável
do ótimo
Insucesso:
12 permanecer na Base
x1
x2
Direção x1
Direção x2
Unimodalidade: dispensa + 2
7
- 1
Base
10
Insucesso:
permanecer na Base - 
+1
8
Insucesso:
permanecer na Base
2
15
Direção provável
do ótimo
Sucesso:
deslocar a Base
x1
x2
Direção provável
do ótimo
Direção x1
15
Direção x2
Sucesso:
deslocar a Base
+ 2
- 1
Insucesso: 7
permanecer na Base
10
+1
Base
8
Insucesso:
permanecer na Base
- 2
9
Insucesso:
permanecer na Base
x1
x2
Direção x1
5
Direção x2
Insucesso:
permanecer na Base
+ 2
- 1
Insucesso: 7
permanecer na Base
10
+1
Base
8
Insucesso:
permanecer na Base
- 2
9
Insucesso:
permanecer na Base
A Base deve estar próxima do ótimo !
x1
Método de Hooke & Jeeves
ALGORITMO
Estabelecer um incremento e uma tolerância para cada variável
Escolher uma Base
Repetir
Explorar a vizinhança da Base (em busca da direção provável do ótimo)
Se houve Sucesso em alguma direção
Então: Progredir (na direção provável) até haver um Insucesso
Senão: (proximidade do ótimo)
Se Chegou ao Ótimo
Então: Finalizar
Senão: reduzir os incrementos
Funções Unimodais
O método converge sempre para o único extremo independentemente da
base inicial.
Os incrementos iniciais afetam apenas o número de tentativas.
Funções Multimodais
O método pode convergir para extremos locais diferentes dependendo da base inicial e
dos incrementos iniciais selecionados.
(a) partindo de bases iniciais diferentes pode-se alcançar extremos locais diferentes
com os mesmos incrementos iniciais.
(b) partindo de uma mesma base inicial pode-se alcançar extremos locais diferentes
com incrementos iniciais diferentes
f (x) = (x12 + x2 – 11)2 + (x22 + x1 – 7)2
Método dos poliedros flexíveis
É um método de busca multivariável (J.A. Nelder e R. Mead, 1964, também
chamado de Simplex), onde o pior vértice de um poliedro com n + 1 vértices
é substituído por um novo vértice colinear com o vértice antigo e o
centróide.
X2
10
9
7
8
5
12
11
13
6
1
3
4
2
X1
Centróide:
x 0, j

1 n 1
   xi , j  x h , j 
n  i 1

j  1,2, n
onde xh,j é o pior vértice.
Método dos poliedros flexíveis
O algoritmo envolve quatro operações de busca, que para o caso da
minimização da função objetivo têm as seguintes formas:
Expansão
Reflexão
k
k
k
k

 xR  x0   ( x0  xh ) ,   0

k
k
k
onde
f
(
x
)

max
f
(
x
),
,
f
(
x
h
1
n
1 )




 Se f ( xRk )  f ( x k )  min  f ( x1k ), , f ( xnk1 ) ,

então xEk  x0k   ( xRk  x0k ) ,   1

Se f ( xEk )  f ( xRk ), então xhk 1  xEk


k 1
k
sen
ão
x

x
h
R


k  k  1 (ir para 1)

onde
Contração
 Se f ( xRk )  f ( xik )  i  h, então xCk  x0k   ( xhk  x0k )

xhk 1  xCk , 0    1


k  k  1 (ir para 1)

x k
é o melhor vértice.
Redução
1 k

k
k
k 1
k
Se
f
(
x
)

f
(
x
),
então
x

x

( xi  x k )
R
h
i

2

i  1, 2, , n  1


k  k  1 (ir para 1)


Método dos poliedros flexíveis
O critério usado por Nelder e Mead para terminar a busca é o
seguinte:
1
2
2
 1
k
k


f ( xi )  f ( x0 )    e



 n  1 i 1

n 1
DIMENSIONAMENTO POR SIMULAÇÕES SUCESSIVAS
EMPREGADO POR “SOFTWARES” COMERCIAIS
Empregam, para dimensionamento, os módulos ordenados para
simulação.
Mas exige um procedimento de otimização:
- função objetivo (a ser minimizada): diferença, em valor absoluto,
entre os valores obtidos para as variáveis de saída e os valores
estipulados como metas
- variáveis de projeto: as dimensões dos equipamentos
Exemplo: Extrator
W = 3.750 kgB/h
Normal
Q* = 10.000 kgA/h
o
xo*= 0,02 kg AB/kg A Ts C
Q* = 10.000 kgA/h
solvente
x* = 0,008 kgAB/kg A
To oC
T oC
o
T C
rafinado
alimentação
extrato
T oC
W = 3.750 kgB/h
y = 0,032kg AB/kg B
r = 0,60
Simulações Sucessivas
W = ??? kgB/h
Q* = 10.000 kgA/h
oC
T
s
xo*= 0,02 kg AB/kg A
Q* = 10.000 kgA/h
solvente
x = ??? kgAB/kg A
To oC
T oC
o
T C
rafinado
alimentação
extrato
T oC
W = kgB/h
y = kg AB/kg B
FO = |x – 0,008|
Exemplo: Extrator
Simulações Sucessivas
W = ??? kgB/h
Q* = 10.000 kgA/h
oC
T
s
xo*= 0,02 kg AB/kg A
Q* = 10.000 kgA/h
solvente
x = ??? kgAB/kg A
To oC
T oC
o
T C
rafinado
alimentação
extrato
T oC
W = kgB/h
FO = |x – 0,008|
y = kg AB/kg B
1. Q(xo – x) – W y = 0
2. y – k x = 0
x = Q xo / (Q + k W )
Por Seção Áurea, 0 < W < 1.000  W = 3.750
Exemplo: Trocador de Calor
T4* = 30 oC
A = 265,6 T
m2
2
*
1. Q  W1Cp1 (T1  T2 )  0
= 25
oC
W1* = 30.000 kg/h
T1* = 80 oC
Normal
W3 = 44.000 kg/h
2. Q  W3 Cp 3 (T4  T3 )  0
3. Q  UA  0
(T  T4 )  (T2  T3 )
4.   1
0
T  T4
ln 1
T2  T3
T3* = 15 oC
T4* = ???
A
T 2* ???
W1* = 30.000 kg/h
T1* = 80 oC
W3
T3* = 15 oC
Simulações Sucessivas
T2 = T1 – Q/W1Cp1
T4 = T3 + Q/W3Cp3
FO = (T2 – 25)2 + (T4 – 30)2
Por Hooke&Jeeves ...
0 < A < 1.000
0 < W3 < 100.000