Embed Size (px)
Citation preview
PROGRAMAÇÃO DINÂMICA
27 de maio de 2014
OTIMIZAÇÃO DE SISTEMAS DISCRETOS
Considere um sistema constituido de N estágios em série.
O dimensionamento deste sistema é um problema de otimização com G = N graus de liberdade tendo x1 ... xN como variáveis de projeto
Uma forma de conduzir a otimização consiste um realizar uma busca multivariável por um dos métodos conhecidos (H&J, por exemplo).
Uma outra forma consiste em realizar N buscas univariáveis.
xox2 xNxN-1xN-2
1 2 Nx1
N -1
PROGRAMAÇÃO DINÂMICA
PROGRAMAÇÃO DINÂMICA
Método criado por Richard Bellman para a otimização de sistemas em estágios.
x*o
1 2 NN -1x1 x2 xNxN-1xN-2
Aplicações na Engenharia Químicabaterias de reatores, extratores, torres de destilação, etc...
Base do Método
PRINCÍPIO DO ÓTIMO“Optimality Principle” (Bellman)
"Para que um sistema em estágios em série seja ótimo é necessário que ele seja ótimo de qualquer
estágio em diante".
x*o
1 2 NN -1
x1o x2
o xNoxN-1
oxN-2o
Todo xi está com o seu valor ótimo
1 2
Q = 10.000 kgA/h
xo = 0,02 kgAB/kgA
W1 W2
X1 kgAB/kgA X2 kgAB/kgA
y1 kgAB/kgA y2 = kgAB/kgA
3
W3
y3 = kgAB/kgA
X3 kgAB/kgA
Exemplo: 3 extratores em série
A solução ótima
A solução ótima pode ser obtida pelo método analítico,
maximizando o Lucro do processo completo.
Incorporando as equações ordenadas ao Lucro:
L (xo, x1, x2, x3) = 4.000 (0,02 – x3) – 25 (0,02 / x1 – x1 / x2 – x2 / x3 – 3)
L / x1 = 0 x2 = 50 x12
L / x2 = 0 x3 = x22 / x1
L / x3 = 0 x1o = 0,01495 x2
o = 0,01118 x3o = 0,008359
W1o = W2
o = W3o = 843,7
Lo (xo, x1, x2, x3) = 21,3 $/h
1 2
Q = 10.000 kgA/h
xo = 0,02 kgAB/kgA
W1o = 843,7 kgB/h W2
o = 843,7 kgB/h
x1o = 0,015
kgAB/kgAx2
o = 0,011 kgAB/kgA
y1 = 0,0598 kgAB/kgA y2 = 0,04472 kgAB/kgA
3
W3o = 843,7 kgB/h
y3 = 0,03344 kgAB/kgA
x3o = 0,0084
kgAB/kgA
1 2
Q = 10.000 kgA/h
xo = 0,02 kgAB/kgA
W1o = 843,7 kgB/h W2
o = 843,7 kgB/h
X1o = 0,015
kgAB/kgAx2
o = 0,011 kgAB/kgA
y1 = 0,0598 kgAB/kgA y2 = 0,04472 kgAB/kgA
3
W3o = 843,7 kgB/h
y3 = 0,03344 kgAB/kgA
x3o = 0,0084
kgAB/kgA
Este sistema é ótimo a partir de qualquer estágio
Outra solução: este sistema não é ótimo a partir de estágio algum !
1 2
Q = 10.000 kgA/h
xo = 0,02 kgAB / kgA
W1 = 1.972 kgB/h W2 = 843,7 kgB/h
x1 = 0,01118 kgAB/kgA
x2 = 0,008359 kgAB/kgA
y1 = 0,04472 kgAB/kgA y2 = 0,03344 kgAB/kgA
3
W2 = 391,2 kgB/h
y3 = 0,02891 kgAB/kgA
x3 = 0,007228
kgAB/kgA
Solução Ótima: cada Estágio abre mão do seu lucro máximo em favor dolucro máximo do sistema
A outra Solução: cada Estágio busca o seu lucro máximo ignorando os Estágios seguintes.
1 2
Q = 10.000 kgA/h
xo = 0,02 kgAB / kgA
W1 = 1.972 kgB/h W2 = 843,7 kgB/h
x1 = 0,01118 kgAB/kgA
x2 = 0,008359 kgAB/kgA
y1 = 0,04472 kgAB/kgA y2 = 0,03344 kgAB/kgA
3
W2 = 391,2 kgB/h
y3 = 0,02891 kgAB/kgA
x3 = 0,007228
kgAB/kgA
Lo' (xo, x1, x2, x3) = L1o' (xo, x1) + L2
o' (x1, x2) + L3o' (x2, x3) = 15,6 + 2,8 + 0,6 = 19 $/h
1 2
Q = 10.000 kgA/h
xo = 0,02 kgAB/kgA
W1o = 843,7 kgB/h W2
o = 843,7 kgB/h
X1o = 0,015
kgAB/kgAx2
o = 0,011 kgAB/kgA
y1 = 0,0598 kgAB/kgA y2 = 0,04472 kgAB/kgA
3
W3o = 843,7 kgB/h
y3 = 0,03344 kgAB/kgA
x3o = 0,0084
kgAB/kgA
Lo (xo, x1, x2, x3) = 4.000 (0,02 – x3o) – 25 (0,02 / x1
o – x1o
/ x2o –x2
o/ x3o – 3) = 21,3 $/h
A forma correta de executar as buscas univariáveis levando em conta os estágios a jusante, é através da
PROGRAMAÇÃO DINÂMICA
De uma forma simplificada, pode-se dizer que a solução por Programação Dinâmica é obtida em duas fases:
Fase de Ida
Fase de Volta
Fase de Ida: o sistema é percorrido no sentido inverso ao do fluxo, do último ao primeiro Estágio.
Nesta fase, cada estágio é “consultado” quanto à sua participação na solução ótima, ficando preparado o caminho de volta.
1 2
Q = 10.000 kgA/h
xo = 0,02 kgAB/kgA
W1 W2
X1 ? kgAB/kgA X2 ? kgAB/kgA
y1 kgAB/kgA y2 = kgAB/kgA
3
W3
y3 = kgAB/kgA
X3 ? kgAB/kgA
Fase de Volta: o sistema é percorrido no sentido do fluxo, do primeiro para o último Estágio.
Nesta fase, a solução ótima vai sendo produzida, de estágio a estágio, utilizando as informações colhidas na Fase de Ida.
1 2
Q = 10.000 kgA/h
xo = 0,02 kgAB/kgA
W1 W2
X1o kgAB/kgA X2
o kgAB/kgA
y1 kgAB/kgA y2 = kgAB/kgA
3
W3
y3 = kgAB/kgA
X3o kgAB/kgA
L (xo, x1, x2, x3) = L1 (xo, x1) + L2 (x1, x2) + L3 (x2, x3)
L1 (xo, x1) = 105 – 4.000 x1 – 0,5 / x1
L2 (x1, x2) = 25 + 4.000 x1 – 4.000 x2 – 25 x1 / x2
L3 (x2, x3) = 25 + 4.000 x2 – 4.000 x3 – 25 x2 / x3
Otimização do Estágio 3 para o valor ótimo de volta ainda desconhecido x2# :
dL3/dx3 = - 4.000 + 25 x2# / x3
2 = 0x3
o = 0,0791 x2#
L3o = 25 + 4.000 x2
# - 632,46 x2#
EXEMPLO: 3 extratores em série
xo*
1x1
W1
y1
2x2
W2
y2
3x3
W3
y3
Assim , fica garantido que o Estágio 3 será ótimo para qualquer valor de x2.
Explicitando o lucro proporcionado por cada estágio:
Otimização dos Estágios 2 + 3 para o valor ótimo de volta ainda desconhecido x1#
(aproveitando L3o ):
dL23/dx2 = 25 x1# / x2
2 – (1/2)(632,46 / x2#) = 0
x2o = 0,1843 x1
# 2/3 L23
o = 50 + 4.000 x1# – 407,2 x1
# 1/3
xo*
1x1
W1
y1
2x2
W2
y2
3x3
W3
y3
Do passo anterior:x3
o = 0,0791 x2 L3
o = 25 + 4.000 x2 - 632,46 x2
L23 = L2 (x1, x2) + L3o = [25 + 4.000 x1
# – 4.000 x2 – 25 x1# / x2] +
[25 + 4.000 x2 - 632,46 x2 ]
L23 = 50 + 4.000 x1# - 25 x1
# / x2 – 632,46 x2
Assim , fica garantido que os Estágios 2 e 3 serão ótimos para qualquer valor de x1.
xo*
1x1
W1
y1
2x2
W2
y2
3x3
W3
y3
Do passo anterior:x2
o = 0,1842 x12/3
L23o = 50 + 4.000 x1 – 407,2 x1
1/3
Otimização dos Estágios 1 + 2 + 3 para a constante xo ( aproveitando L23o ):
L123 = L1 (xo, x1) + L23o = [105 – 4.000 x1 – 0,5 / x1] + [50 + 4.000 x1 – 407,2 x1
1/3 ]
L123 = 155 – 0,5/x1 – 407,2 x11/3
dL123/dx1 = 0,5 / x12 – 135,7 x1
-2/3 = 0
Retornando, no sentido do fluxo:
x1o = 0,015 : W1
o = 843,7 kg/h
L123o = Lo = 21,2 $/a
x2o = 0,01842 x1
2/3 = 0,01118 : W2o = 843,7 kg/h
x3o = 0,07905 x2 = 0,008365 : W3
o = 843,7 kg/h
DESENVOLVIMENTO LITERAL
Primeiro passo: otimiza-se o estágio 3 para um valor hipotético x2
# .
xo*
1x1
W1
y1
2x2
W2
y2
3x3
W3
y3
L (x1, x2, x2) = L1 (xo, x1) + L2 (x1, x2) + L3 (x2, x3)
x2#
ETAPA PREPARATÓRIA
A função objetivo a maximizar é L3 (x2#, x3 ) e a variável de projeto é x3.
Busca univariável em x3. Obtem-se x3
o (x2# ) e L3
o (x2# ) , ambos função de x2
#. L3
o (x2# ) será usado no passo seguinte.
x3o (x2
# ) fica agurdando o resultado x2o a ser determinado na etapa na volta.
xo*
1x1
W1
y1
2x2
W2
y2
3x3
W3
y3
L (x1, x2, x2) = L1 (xo, x1) + L2 (x1, x2) + L3 (x2, x3)
A função objetivo a maximizar é L23 (x1#, x2, x3 ) = L2 (x1
#, x2) + L3 (x2, x3). Porém, para qualquer valor de x2, já se conhece o valor máximo de L3 . Então, a função objetivo fica: L23 (x1
#, x2 ) = L2 (x1#, x2) + L3
o(x2) e a variável de projeto fica sendo x2. Busca univariável em x2 . Obtem-se x2
o (x1# ) e L23
o (x1# ) , ambos função de x1
#. L23
o (x1# ) será usado no passo seguinte.
x2o (x1
# ) fica aguardando x1o (x1
# ) a ser determinado na etapa de na volta.
x1#
ETAPA PREPARATÓRIA
Segundo passo: otimizam-se os estágios 2 e 3, em conjunto, para um valor hipotético x1
#.
A função objetivo a maximizar é L123 (xo , x1 , x2, x3 ) = L1 (xo, x1) + L2 (x1, x2) + L3 (x2, x3). Porém, para qualquer valor de x1, já se conhece o valor máximo de L23 . Então, a função objetivo fica: L123 (xo, x1 ) = L1 (xo, x1) + L23
o (x1) e a
variável de projeto fica sendo x1. Busca univariável em x1 . Obtem-se x1
o e L123o , ambos função de xo.
xo*
1x1
W1
y1
2x2
W2
y2
3x3
W3
y3
L (x1, x2, x2) = L1 (xo, x1) + L2 (x1, x2) + L3 (x2, x3)
Quarto passo: regenera-se a solução final voltando com os valores de x1
o e x2o e x3
o
ETAPA PREPARATÓRIA
Terceiro passo: otimizam-se os estágios 1, 2 e 3, em conjunto, para o valor fixo xo
*.
A solução analítica se torna inviável para problemas de grande porte.
Os resultados intermediários de Lo e xio são lançados em gráficos
ou tabelas.
Procedimento numérico alternativo
A pré-otimização de cada estágio se dá para um conjunto discreto de valores da variável de entrada.
Ver ProgramaçãoDinâmica.xls
Os de Lo são usados durante a pré-otimização
Os de xio são usados no caminho de volta
