prog dinamica
Post on 27-Feb-2018
236 Views
Preview:
TRANSCRIPT
-
7/25/2019 Prog Dinamica
1/31
- 1
Elementos de Diseo ptimo
Tcnicas de Optimizacin: Programacin Dinmica
1.Conceptos bsicos de Programacin Dinmica
Como ya quedase dicho, las llamadas programaciones constituyen uno de los grandes
captulos de las Tcnicas de Optimizacin. Su aplicacin se restringe a problemas que se pueden
formular bajo una estructura especfica, para la cual se desarrolla una estrategia de optimizacin
sumamente eficiente.
La ms antigua de estas tcnicas es la Programacin Lineal, cuyos conceptos y algoritmosoperativos bsicos datan de las dcadas del 40 y 50; fundados, principalmente, en los trabajos de
Dantzig y el grupo de la Rand Corp.
En este caso las exigencias se refieren al tipo de ecuaciones que definen el problema: tanto la
funcin objetivo como las relaciones de diseo y restricciones deben ser lineales y las variables
no negativas, esto es
Con este tipo de exigencias se encuentran distintos tipos de programaciones: cuadrtica,
geomtrica,etc.
La que ha de ocupar la atencin de este captulo no pertenece a las tcnicas que requieren
funcionalidades determinadas en la
formulacin del problema.
Programacin Dinmicaes una
tcnica de optimizacin que se
aplica exclusivamente a sistemas
cuyos diagramas de flujo de
informacin son seriados
jx
mibxacon
xc
j
i
nj
j
jij
j
nj
j
j
0
..1
mn
1
1
rN -1
dN -1
dN
d2
d1
S2
S1
S3
SN -1S N
SN +1
rN
r2
r1
Fig. 5.1.1
-
7/25/2019 Prog Dinamica
2/31
- 2
multietapas, entendiendo por seriados aquellos diagramas donde en todaetapa las variables que
ingresan a ella son de decisin o provienen solo de la etapa que la precede de acuerdo al flujo de
informacin, tal como el que se muestra en la figura 5.1.1.
All se ha buscado representar con flecha entera gruesa conjuntos de variables, por ejemplo dNdebe entenderse como un vector de componentes dn1, dn2,...
Las variables individuales, como todas las ri, por ejemplo, se indican con una media flecha
fina. Estas variables ri representan el aporte que realiza en forma individual cada etapa a la
funcin objetivo del sistema. En definitiva, el problema puede ser formulado como sigue
donde fiy gideben tomarse como vectores de funciones de componentes fi1, fi2,...,gi1, gi2,...
Resulta importante aclarar que en todo el captulo, al hacerse referencia a las variables de
estado de una etapa, esto es, que abandonan esa etapa, solo se han de considerar, salvo expresa
mencin en contrario, las que se conectan con otra etapa, lo que de modo alguno quiere decir quesean las nicas que existan. Son las que interesan desde el punto de vista de Programacin
Dinmica, que es algo muy distinto, pero al momento de calcular los aportes a la funcin objetivo
deben tenerse en cuenta, como es obvio, todas las variables, sean o no de interconexin.
Volviendo al diagrama de flujo de la figura 5.1.1, la particular estructura que presenta permite
inferir rpidamente que las consecuencias de cualquier decisin que se tome en cualquier etapa se
pueden proyectar solo hacia adelante en el flujo de informacin, en rigor, en forma directa, a la
etapa siguiente y, a travs de sta, a las restantes.
Esto es tpico, por ejemplo, en todo proceso que se desarrolla a lo largo del tiempo1, donde las
acciones que se toman en el presente solo han de tener consecuencias en el futuro. La situacin
presente, en tanto, es la resultante de las decisiones del pasado, inmodificable, por cierto, ante la
cual, en consecuencia, solo cabe aceptar la realidad y determinar el curso a seguir, en aras de
alcanzar el mejor futuro posible.
1Al menos, mientras no se encuentre el modo de viajar a travs de l.
NidSSrr
dSSg
dSSfcon
rroptFO
iiiii
iii
iii
N
i
i
N
i
iN
..1),,(
0),,(
0),,(
1
1
1
1
*
1
-
7/25/2019 Prog Dinamica
3/31
- 3
Esta dinmicase repite en sistemas seriados multietapas, donde un "presente" en particular es
el valor que toman las variables de interconexin que ingresan a una etapa k cualquiera ("estado"
del sistema a la entrada de la misma2), en tanto que el "futuro" lo constituye el subdiagrama que
comienza en la etapa k y concluye con la final.
Para un determinado estado Sk+1, v.g. Sk+1j, existe un conjunto de decisiones (podra decirse
"en el futuro") dkj,...,dljque logran un valor ptimo para el conjunto de aportes parciales r1,...,rk.
Dado que al fijarse dkjqueda perfectamente determinado Skjy que, con esto, se tiene una
situacin, para las ltimas k-1 etapas, equivalente por completo a lo anterior, se puede poner que
donde ahora Sk+1tiene un valor genrico y las dk,...,d1que logran el ptimo de FOk(y ste mismo)
resultan serfuncionesde ese valor.
Cuando lo anterior es cierto para cualquier valor de k entre 1 y N se tiene el ptimo para el
sistema, segn lo expresa el llamado principio de optimalidad de Bellman3 por el que se
establece que la poltica ptima dN*,...,d1*para un sistema de N etapas debe ser tal que el
subconjunto de decisiones para las k ltimas etapas dk*,...,d1
*resulta ptimo para el estado Sk+1,
para todo k entre 1 y N.
La expresin 5.1.1, asimismo, establece la estructura fundamental de la estrategia deoptimizacin por Programacin Dinmica, como podr verse en seguida.
2.Estrategia bsica. Ejemplos demostrativos
En la exposicin de la estrategia o algoritmo bsico de Programacin Dinmica, para una
mayor claridad en la exposicin, se admitir que en el diagrama de flujo general de la figura 5.1.1
hay solo una variable de interconexin y una de decisin por etapa.
Esto permite que, en la determinacin del estado a la entrada de cada etapa, se logre la mayor
simplicidad de tratamiento pues basta con fijar el valor de una sola variable. Otro tanto ocurre con
la bsqueda de los ptimos parciales (esbozada en 5-1-1), la que se ha de efectuar, tambin, sobre
una variable.
2Ntese que se habla de valores de las variablesy estado del sistema, ya que este ltimo es un valor
singular, quequeda definido por los primeros.
3Richard Bellman fue quien, en la dcada del 50, plantea los fundamentos de Programacin Dinmica.
1.1.5)()( 1..
1
1
kkkd
Ni
ki
idd
kk SFOroptroptSFO
kk
-
7/25/2019 Prog Dinamica
4/31
- 4
De modo alguno esto resta generalidad al tratamiento. Si se incrementase en uno o ms puntos
del diagrama el nmero de variables de interconexin habra de crecer la complejidad en la
determinacin del estado a la entrada de la etapa, o etapas, correspondientes, pero el concepto de
estado ha de seguir siendo singular, con independencia de cuantas variables lo determinan. En
forma anloga, si las modificaciones ocurriesen sobre las variables de decisin, sera cuestin deelegir, en cada caso, la metodologa de optimizacin que mejor se ajuste al nmero de variables y
tipo de problema particular.
Hecha esta aclaracin es posible, ahora, entrar de lleno en el proceso de anlisis que se
desprende del principio de Bellman.
De acuerdo a 5.1.1 se deber comenzar por la ltima etapa, la nmero 1 en el diagrama (la
numeracin elegida obedece a que el proceso de anlisis "transcurre" en sentido inverso al flujo
de informacin), donde deber encontrarse
Si se admite que el paso de
optimizacin indicado solo puede ser
llevado a cabo en forma numrica (de
hecho, la nica va de ataque siempre
posible) habr que determinar el ptimo
de r1para varios valores de S2, de modo
de disponer, en forma tabulada, las
funciones F1(S2) y d1*(S2).
Lo anterior se muestra en la figura
5.2.1, donde, en la parte a de la misma,
se representa la bsqueda de los ptimos
de r1 (mximo, en este caso) para
distintos valores de S2, mientras que en
b y c las relaciones F1(S2) y d1*(S2) (En
ambas figuras se han extrapolado los
resultados para obtener lo indicado con
las curvas gruesas).
En la segunda fase de optimizacin deben considerarse las dos ltimas etapas y encontrar
),,,(),,()( 1121211121211
ddSSSroptdSSroptSFO
kdd
))d,S(S(FO)d),d,S(S,S(ropt
)S(FO)d,S,S(ropt)*rr()S(FO
2321223232d
212232d
1232
2
2
Figura 5.2.1
d*1
r*1
d1
S2
S2
a
b c
r1
S '2
S 22
S 32
-
7/25/2019 Prog Dinamica
5/31
- 5
La cuestin es, en esencia, la misma que antes: debe buscarse el ptimo de r1+ r2para distintos
valores de S3, obteniendo, asimismo, los respectivos d2*.
La nica diferencia radica en que, dado
un valor de S3, para obtener elcorrespondiente a cada d2en la funcin a
optimizar, al resultado del clculo de r2
debe agregarse el valor de FO1 que
corresponda al S3elegido. (Esto se muestra
en la figura 5.2.2.a donde la ordenada est
constituida por dos partes, r2y r1*).
El valor de FO1surge interpolando en la
tabla obtenida en la etapa anterior, para lo
que debe tenerse en cuenta el estado a la
salida (S2) que resulta de la combinacin de
la entrada (S3) y la decisin (d2).Todo esto
se ha de repetir en el anlisis de las etapas 3,4,..,N-1.
Para la ltima etapa, en cambio, lo usual es que el
estado a la entrada de la misma se encuentre
perfectamente determinado (Si no lo estuviera, el
tratamiento que sigue deber efectuarse para cada uno
de los posibles valores). Con esto, la bsqueda de
se reduce a
una nica bsqueda sobre dN para determinar el
ptimo de la funcin objetivo total, tal como seindica en la figura 5.2.3.
A partir del valor encontrado de dN*es posible el clculo de SN*y con sta, a travs de la tabla
respectiva, determinar dN-1*y as, siguiendo ahora el sentido del flujo de informacin, hasta lograr
d1*.
Resumiendo: la estrategia que plantea Programacin Dinmica consta de dos fases, una,
primera, por la cual se han de obtener los ptimos parciales de las k ltimas etapas y las
S31
r2+ r
1*
d2
S32
S33
r2
r1*
a
(r2+ r
1)*
S3
c
d2*
S3
b
Figura 5.2.2
rN+ (r
N-1++r
1)*
Figura 5.2.3
)()( 11 NNNd
NN SFOroptSFO
N
)(()),(( 1 NNNNNNNd
dSFOddSropt
N
-
7/25/2019 Prog Dinamica
6/31
- 6
decisiones ptimas de las mismas en funcin del estado a la entrada al subsistema; la otra fase,
siguiendo el flujo de la informacin, permite obtener los valores de los estados y decisiones
ptimas para todas y cada una de las etapas que componen el sistema.
Tal vez resulte conveniente fijar estos conceptos a travs del anlisis de algunos ejemplossencillos.
En el primero de ellos -la extraccin en tres etapas de un soluto con agregados parciales de
solvente de extraccin presentado en captulos anteriores- es posible encontrar expresiones
funcionales tanto para FOi*(Si+1) como para di*(Si+1); en cambio, en el segundo - una red de
intercambio trmico con divisin de corrientes, similar a la vista en el captulo de ordenamiemto
de clculo - debe acudirse a la solucin numrica planteada como estrategia general.
Problema 5.1 En el problema de
extraccin en tres etapas en equilibrio
que se representa en la figura 5.2.4 se
admitir: a) la inmiscibilidad del
solvente de extraccin y b) una
relacin de equilibrio lineal yi=k xi,
con lo que, adems de sta, la otra
ecuacin para cada etapa es
Se busca maximizar la diferencia venta de soluto extrado y gasto de solvente de extraccin,
siendo C la relacin de costo de este ltimo al precio de venta del primero. Con esto, la funcin
objetivo tendr la forma
mx B = q(x4- x1) - C Wi.
Los datos del problema sern el caudal q y la
fraccin x4.
La figura 5.2.5 muestra el diagrama de flujo
de informacin correspondiente, el que, como
puede apreciarse, rene los requerimientos
exigidos para la aplicacin de Programacin
Dinmica.
En las etapas 2 y 3 se ha aadido una ecuacin (xi = xi ) a fin de clarificar el uso de la tcnica,
al evitar que una misma variable, xi, aparezca, en puntos sucesivos del diagrama, como de
decisin y de estado interconectando etapas (Esto slo por razones didcticas, ya que el
tratamiento podra haberse realizado sin recurrir a este artificio).
3
q
X4
X3
X3
y3
W3
2
q
X2
X2
y2
W2
1
q
X1
y1
W1
Fig. 5.2.5
iii1i yWqxqx
x4
x3
x2
x1
y3 y2 y1
W3
W2
W1q
123
Fig. 5.2.4
-
7/25/2019 Prog Dinamica
7/31
- 7
Para el primer paso de optimizacin se puede considerar
con lo cual
Como se puede apreciar, las relaciones 5-2-1 concluyen por determinar sendas expresiones
analticas para el ptimo parcial y la decisin de la etapa, FO1y x1*, en funcin del estado a la
entrada de la misma x2. Estas expresiones corresponden a las curvas estimadas en la figura 5.2.1
b y c.
Debe hacerse notar que debe verificarse la naturaleza del punto estacionario determinado, lo
que, en este caso, resulta inmediato ya que 0xpx2x/r 31
'21
21
2
Para el segundo paso deben considerarse las dos ltimas etapas buscando
Esto lleva a
(Se deja a cargo del lector el verificar que la derivada segunda es igual a -3/2x3< 0).
Antes de pasar al tercer, y ltimo, paso de optimizacin conviene hacer notar que, hasta ahora,
las funciones objetivos parciales dependan tanto de la decisin en la etapa inicial del respectivo
subdiagrama como del estado a la entrada de la misma.
1
1'2
1
1141x
kx
xx
qW
CW)xx(qrmx1
'24
*1
'21
'2
*1
21
'2
1
1
1
'2
141
2)(
12501
,1
pxpxqrxFO
pxxxpxx
r
k
Cp
x
xpxxqr
2
2
'3
4
2
2'3
12112
22
mx
pxx
xpxq
kx
xxCqFOCWFOFOr
3 '3
2421
'32
3 2'3
*22
22
'3
2
12
xp3p2xq)*rr()x(FO
pxx0x/pxpxx
)FOr(
-
7/25/2019 Prog Dinamica
8/31
- 8
Al tratar el conjunto de las tres etapas la entrada al sistema est fija (x4es un dato), por lo que
x3*no ser ya funcin de la misma sino simplemente un valor nico (Advirtase el abandono de
la utilizacin de la derivada parcial en la determinacin del punto estacionario). Conviene
recordar esto dado que, en la formulacin del problema, se ha omitido el darle valores numricos
a los datos y podra aparecer como que se reiteran las situaciones anteriores. Se trata, entonces, deencontrar
y ahora conocido x3* surgen de inmediato x2* y x1*, en la segunda fase de la estrategia de
Programacin Dinmica, siguiendo el flujo de la informacin:
Problema 5.2 El otro ejemplo al que se hizo referencia es un esquema con una nica divisin de
corrientes para resolver el problema de sntesis de redes de intercambio trmico similar al visto al
considerar el acpite 4 del tema mtodos de optimizacin, esquema que se muestra en la figura
5.2.6.
Figura 5.2.6
W3
W4
W1
W2
V
A500
T3
240
540
T4 280
320
r
1-r T22
T21
200
100180
140T1320
A1
Ac
Ae
A3
A2
4
4
3
41233
4 34
*3
3 23
234
3
23
3
433
243223
x
xp4p3xq)*rrr(FO
pxx0)x/p(xpxx
)FOr(
x
xpxp3p3xqCWFOFOrmx
3
44
3*1
'*24
*2
4 3
4
*3
'*3 xpxxpxxpxxx
-
7/25/2019 Prog Dinamica
9/31
- 9
Las ecuaciones que definan el modelo matemtico del problema eran:
Calentador
)T-500(1013
15=q657,5 3
4v
A200=40
T-54010
13
15c
34
ln
Intercambiador 1
240T)240-T(1013
15=)T-480(102 33
44
4
480T;480T1015
13-
2
1A150=
240-T
T-480ln 34
4-1
4
3
Intercambiador 2
)T-320(109
13=)280-T(102 1
44
4
280T;320T1013
9-
2
1A150=
T-280
320-T14
4-2
1
4
ln
Intercambiador 3
140T)140-T(109
13=)T-320(10
9
15f 11
421
4
140T1013
9
-f15
9
A150=140-T
T-320
214-
321
1
ln
Enfriador
320T)T-320(109
15)f-1(=q80 2222
4a
q
1-
)f-1(15
109A150=
100-T
140
a
4-
e22
ln
Mezclador
1f0200=T
f)-1(+T
f2221
y la funcin objetivo
q0,24+q3,6+A39=FO av0,65
La estrategia de clculo para
este problema determina como
variables de decisin a T1 y al
factor de fraccionamiento f.
El diagrama de flujo
T1
T '1
T21
f
T4
T3
qV
T22
qa
A3
Ae
A1
A2
Ac
Fig. 5.2.7
-
7/25/2019 Prog Dinamica
10/31
- 10
resultante se indica en la figura 5.2.7 (Otra vez se ha recurrido al artificio de introducir una
variable de conexin, T1= T1)
Por las caractersticas del diagrama queda claro que es aplicable Programacin Dinmica,
aunque la naturaleza matemtica de las ecuaciones hace imposible una solucin analtica como enel problema anterior.
Habr que buscar aef
qAAr 24,0)(39mn 65.03
65.01 para distintos valores de T1
, lo que
dar lugar a una tabla donde han de figurar los respectivos FO1, necesarios para el siguiente paso
de optimizacin, y de f*, requeridos para la segunda fase de la tcnica.
Una vez realizado esto habr que proceder a resolver un nico problema:
1v65.0
2
65.0
1
65.0c12
T
FOq6,3)AAA(39FOrmn1
Puede advertirse que ahora se est ,en principio, frente a dos problemas de una variable en
lugar de uno de dos, que fuera la forma como se resolvi anteriormente.
Esta reduccin de la dimensionalidad de los problemas parciales, un aspecto fundamental de
Programacin Dinmica, se logra a costa de resolver reiteradamente cada uno de estos
subproblemas (Recurdense las figuras 5.1.1a y 5.1.2a). De aqu la nota de prevencin en
principioexpresada ms arriba, ya que estas reiteraciones pueden llegar a anular los efectos
derivados del menor nmero de variables de decisin por problema y, an, a resultarperjudiciales, cuestin sobre la cual se ha de volver ms adelante.
Retomando el problema planteado; la generacin de la tabla requiere la adopcin de una serie
de valores de T1. Para ello debe considerarse que existe un lmite superior implcito sobre T1, que
surge del umbral de necesidad de refrigeracin en el enfriador, equipo complementario del
intercambiador 3 .
Estos umbrales se pueden calcular mediante la Tabla del Problema, utilizando una
aproximacin mnima nula. Los consumos de servicios auxiliares que as se determinen
constituirn un mnimo de ndole termodinmica, ya que los intercambios que se propongan sobre
el Pinch deberan realizarse en equipos con rea infinita.
Para el problema, el umbral de refrigeracin es del orden de 63 104, lo que arroja un valor
mximo de 2351, aproximadamente, para T1.
En la construccin de la tabla, se ha tomado como lmite superior 234,5 y 174,5 como el
mnimo, con un total de 7 valores igualmente espaciados. Se estima, a priori, que el valor ptimo
de T1 se ha de ubicar ms cerca del lmite superior que a la inversa, como un modo de ahorrar en
-
7/25/2019 Prog Dinamica
11/31
- 11
el consumo de servicios auxiliares, ms significativos en costo que la amortizacin de los
equipos.
La tabla siguiente muestra los valores encontrados en el primer paso de optimizacin
T1 f* FO1174,5 0,300 5578,46
184,5 0,373 5183,54
194,5 0,445 4786,64
204,5 0,514 4389,10
214,5 0,582 3992,01
224,5 0,649 3596,33
234,5 0,715 3202,98
Como resultado del segundo paso se encuentra el valor ptimo de T1 , 230,501y de la funcin
objetivo global 9015 $/ao, valores totalmente coincidentes con los encontrados en anterioroportunidad. El valor de f*surge por interpolacin en la tabla anterior, resultando ser 0,688, igual
que antes.
3.Programacin Dinmica con variables discretas
Hasta aqu se han considerado problemas cuya formulacin se estructuraba sobre variables
esencialmente continuas (caudales, concentraciones, temperaturas).
Hay otro grupo de problemas, de gran importancia prctica, donde a las variables solo se les
permite adoptar ciertos y determinados valores, esto es, poseen, o tienen definido, un
comportamiento discreto.
En este punto se suele utilizar lo que en la literatura se denomina diagramas de rutas,
aludiendo a la situacin que pude observarse sobre cualquier mapa vial, donde aparecen las
ciudades vinculadas entre s por una red caminera.
En la parte superior de la figura 5.3.1 se esquematiza, en una forma extremadamente simple, lo
que podra ser un mapa de ese tipo4.
All aparecen una serie de nodos (las
ciudades) vinculadas por arcos o lneas de
unin (los tramos carreteros).
4Por razones didcticas se ha adoptado un esquema absolutamente regular, pero esto no es un requisito
necesario para la aplicacin de la tcnica que se ha de exponer, pudiendo el diagrama ser totalmenteirregular.
7 10 9
14 7 2 0
0
03
32
3
7
5
99
813
10
10
9
4
24
2
11
2
2
7
9
510
Fig. 5.3.1
-
7/25/2019 Prog Dinamica
12/31
- 12
Sobre cada uno de estos tramo aparece una cifra que representara la distancia a cubrir.
Se podra plantear como trasladarse de una cualquiera de las localidades del "extremo este" a
otra cualquiera del otro extremo, avanzando siempre en direccin oeste y de modo tal que el viaje
resulte lo ms corto posible.
En adelante se adoptar un sistema de ejes coordenados para ubicar los nodos,
correspondiendo la fila 1, columna 1 al extremo superior izquierdo y la fila 3, columna 4 al
inferior derecho, nodos n1,1y n3,4respectivamente5.
Puede verse que en cada columna hay un nmero finito de nodos, tres en este caso, as como
que, ubicado en un nodo, para avanzar a la columna siguiente, es posible elegir alguno de los,
como mximo tres, arcos que salen del mismo.
En la parte inferior de la figura 5.3.1 se muestra un diagrama de flujo de informacin quepodra asociarse al "mapa" simplificado de arriba. Para ello, bastara admitir que todos los estados
(inicial, intermedios y final) pueden tomar solo tres valores, los que corresponden a las filas 1,2 y
3 respectivamente, y que las decisiones en las etapas han de incrementar en uno la columna,
manteniendo, incrementando o disminuyendo en uno el valor de la fila, siempre que el estado al
que se arribe sea uno permitido.
Esta equivalencia entre un diagrama de rutas y otro de flujo de informacin posee, como se ha
de ver ms adelante, un real inters prctico, que supera a la actual circunstancia de servir como
justificacin terica para el uso de una determinada tcnica.
La aplicacin de la estrategia de Programacin Dinmica -el diagrama lo permite- debe
comenzar analizando el aporte en la ltima etapa, esto en las transiciones que vinculan las
"ciudades" de la columna 3 con las de la 4. El ptimo de este aporte, menor trayecto, depender,
como ya se ha visto, del estado a la entrada de la etapa.
Puesto en los trminos del mapa carretero simplificado, si uno se encontrase en el nodo 1,3
podra trasladarse al 1,4, recorriendo una distancia 9, o al nodo 2,4, ubicado a una distancia 2. La
decisin ptima, en consecuencia, ser esta ltima lo que genera un aporte de 2 a la distancia totala recorrer.
Si la posicin fuese, en cambio, el nodo 2,3 lo mejor sera trasladarse al 1,4 con un aporte de 2.
Para el 3,3 debe el viaje debe concluirse en el nodo 3,4, con un recorrido parcial de 3.
En la figura se han indicado las decisiones ptimas, as como los aportes a la distancia total
5Si el diagrama fuese irregular debera numerarse cada nodo en forma individual.
-
7/25/2019 Prog Dinamica
13/31
- 13
que corresponda, esto dentro de los crculos que marcan los nodos.
Al pasar a considerar las dos ltimas etapas el recorrido hasta el final resulta de la suma del
aporte de la transicin de que se trate y la distancia ptima a recorrer desde la "ciudad" a que se
llega hasta el final.
As, por ejemplo, si se estuviese en el nodo 1,2 y se tomara la decisin de mantenerse en la
fila, habra que cubrir una distancia de 10 para llegar a 1,3 y de all, se sabe, 2 hasta el final, lo
que hace un total de 12. En cambio si uno se trasladara al nodo 2,3 el recorrido sera de 5 + 2 = 7,
obviamente, mejor que lo anterior.
De esta forma se alcanzan los estados iniciales, columna 1, encontrndose que el menor
recorrido total corresponde al nodo 2,1 con un valor de 11 y que las decisiones ptimas -segunda
fase de la tcnica- marcan el camino n2,1- n2,2- n1,3- n2,4.
Hay un caso de optimizacin de diagramas de rutas de gran importancia prctica, pues en l se
basan todas las tcnicas de planificacin de tareas, cronogramas de ejecucin de obras, etc. que se
explicitan en mtodos como PERT o CPM6.
En este tipo de problemas se encuentran fijos tanto el estado inicial, la entrada al sistema,
como el final, a la salida de la ltima etapa.
Un caso como ste se muestra en la figura 5.3.2, donde se ha colocado, junto al diagrama de
rutas, el de flujo de informacin del que podra provenir.
El que exista un nico nodo inicial y slo otro final (la entrada y la salida estn fijas) es
perfectamente entendible si ese diagrama de rutas est representando un conjunto de tareas en las
que se ha subdividido un determinado trabajo
(limpiar el terreno, poner los cimientos,... para
construir una casa), donde, necesariamente, ha de
existir un momento en el que pone en marcha el
programa de trabajo y otro donde todo ha
concluido.
Cada arco en el diagrama debe entenderse
como una tarea, siendo su duracin el valor que se
encuentra sobre el mismo. Cada nodo indica el
momento en que concluye una tarea o est en
condiciones de comenzar otra. De aqu que en el
6PERT: Program Evaluation and Review Technique - CPM: Critical Path Method
10
10
016 9
9
9
9
9
9
7
7
2
2
2
2
3
18
28
14
5
Fig. 5.3.2
-
7/25/2019 Prog Dinamica
14/31
- 14
diagrama se est indicando, tambin, la relacin que existe entre las distintas tareas del programa:
cuales son las que deben estar concluidas antes de poder comenzar con cada una.
Para este caso la funcin objetivo que se plantea es el menor tiempo en el que el programa
puede estar concluido, respetando, claro est, las relaciones entre las tareas que lo componen.
Esto ltimo significa que deber buscarse el camino ms largo, el de mayor duracin, ya que
permitir que las restantes tareas, las que no se encuentran sobre el camino crti co, pueden
concluirse sin inconvenientes.
De la misma forma que antes es posible ir determinando los mximos parciales que
corresponden a cada estado, esto es, cuanto tiempo ha de transcurrir, an, desde ese punto hasta
que el programa se encuentre concluido.
Por ejemplo, resulta inmediato que las tareas que concluyen en el nodo 1,3 debern estarterminadas 2 unidades de tiempo antes que el programa global, as como que las que lo hacen en
el 2,3 lo debern estar 9 unidades antes. Para determinar el valor correspondiente al nodo 1,2 (es
decir, para las tareas que all terminan) ha de tenerse en cuenta que por una va, la que pasa por
n1,3, el lapso sera 12 (10 + 2), mientras que por otro circuito, el que se conecta con n2,3,el valor es
14 (5 + 9) y ser esto ltimo lo que deba considerarse como fecha de terminacin del nodo para
permitir que ambasramas terminen en tiempo.
Al llegar al estado inicial, se tendr el tiempo total y, pasando a la segunda fase de la tcnica,
la posibilidad de determinar el conjunto de tareas que determinan este tiempo, integrando elcamino crtico.
Este concepto de criticidad aparece en virtud de que una demora en la ejecucin de cualquiera
de estas tareas determinar la correspondiente prolongacin del tiempo total de completamiento
del programa.
En la figura 5.3.2 se han indicado, como siempre, en el interior de los nodos, el valor del
mximo parcial, encontrndose que el tiempo mnimo de ejecucin es 28 y el camino crtico est
determinado por la secuencia n2,1- n3,2- n2,3- n2,4.
Adicionalmente a lo anterior pueden determinarse un conjunto de parmetros de suma
importancia en la planificacin de un trabajo.
En la figura 5.3.3 se muestra la resolucin del
mismo problema pero ejecutando las
operaciones en sentido inverso al anterior (Se
estara siguiendo el sentido del flujo de la
10 14
2819
1019
10
9
9
9
77
99
7
0
2
2
3
5
2
Fig. 5.3.3
-
7/25/2019 Prog Dinamica
15/31
- 15
informacin).
Con esto es posible determinar la fecha ms temprana fpen la que puede comenzar una tarea
cualquiera, siendo sta el valor que se encuentra en el nodo donde la tarea comienza.
As, cualquiera de las que lo hacen en el 1,3 no podrn empezar antes de la fecha 19 (max[ 9 +
10;7 + 2] = 19 O tiempo en que se encuentra concluida la tarea que determinan los nodos 2,2 y
1,3).
A partir de haber "fechado" los nodos, calculando el lapso hasta la terminacin, l f(fig. 5.3.2),
as como la fecha temprana o prxima, fp(fig. 5.3.3) se pueden determinar, para cada tarea, lo
que se conoce con el nombre de fecha tarda f t, plazo ltimo para concluirla sin que se retrase el
conjunto y, en relacin con sta, el margen de flotacin m, que representa el mayor lapso de
demora admisible.
Para una tarea t que comienza en ni,jy termina en nk,lser
correspondiendo el subndice t a la tarea y los dobles a los nodos. Con dtse indica la duracin de
la tarea y con DT la del programa total.
En la tabla se muestran los valores de fp, ft y m para cada una de las tareas del ejemplo.
Puede notarse que para las que componen el camino crtico el margen de flotacin es nulo,
indicando que no puede registrarse el menor retraso en las mismas, sin que ello determine una
demora en el tiempo total de ejecucin del programa.
Tarea Duracin Fechaprxima
Fechatarda
Margende a
2,1
1,2 9 0 14 5
2,2 7 0 12 5
2,3 10 0 10 0
1,2 1,3 10 9 26 72,3 5 9 19 5
2,21,3 2 7 26 17
2,3 3 7 19 9
3,3 7 7 19 5
3,22,3 9 10 19 0
3,3 2 10 19 7
1,3
2,4
2 19 28 7
2,3 9 19 28 0
3,3 9 14 28 5
)(;; ,, ttttlktjit dfpftmlfDTftfpfp
-
7/25/2019 Prog Dinamica
16/31
- 16
No se puede terminar este acpite sin advertir que, primero, los casos reales que son abordados
mediante PERT o CPM presentan diagramas (grafos en la terminologa tcnica) totalmente
irregulares lo que, sin embargo, no invalida la aplicacin de todo lo visto7y, segundo, que, si bien
la tcnica bsica es la expuesta, se abordan otras cuestiones tales como costos, asignacin de
recursos, duraciones indeterminadas, etc., cuyo tratamiento escapa a la intencin de esta obra.
4.Tratamiento aproximado: diagrama de rutas equivalente
Del mismo modo en que antes se vinculaba un diagrama de flujo de informacin a uno de rutas
es posible realizar la operacin inversa, generando un diagrama de rutas equivalente, sobre el que
ser factible la aplicacin de las tcnicas ya vistas, resolviendo el problema original en forma
aproximada.
En la figura 5.4.1 se esquematiza una etapa genrica de un diagrama de flujo de informacin.
Uno de rutas con el que estuviese vinculado tendra determinados valores para los estados Si+1y
Si.
Si por un momento se omite la consideracin del estado a la entrada de la etapa -para quien
acta, en todos los casos, como un dato del problema- un diagrama de rutas con el que estuviese
vinculado el de informacin, debera tener fijados un cierto nmero de posibles estados Silos que,
conectados con los correspondientes a Si+1, han de generar las rutas o transiciones posibles.
Para fijar un estado en Sies preciso darle valores a
todas las variables que lo definen, reiterando que en taldefinicin solo se incluyen las que interconectan etapas.
Tales valores pueden ser fijados dentro de ciertos
mrgenes razonables o habrn de surgir por clculos en la
etapa.
En la primera de las alternativas, fijar valores para las
variables de salida, admitiendo siempre que el estado a la
entrada es un dato conocido, ha de ser necesaria una
inversin del flujo de informacin, transformando envariables de estado tantas decisiones como salidas se
pretenda fijar.
Hay, pues, tres casos por analizar:
7De hecho, se podran transformar esos grafos en otros regulares, aunque el hacerlo carece de sentido
prctico.
Fig. 5.4.1
-
7/25/2019 Prog Dinamica
17/31
- 17
a) Si< di b) Si= di c) Si> di
que se muestran en la fig. 5.4.2
Debe aclararse que en los esquemas se ha tomado dicomo el nmero de variables que definen
la decisin diy Sila cantidad de las que determinan el estado S i.
Puede verse que slo en los casos a y b es posible fijar completamente la salida, mientras que
en el caso c algunas de las variables que la determinan surgen por clculo.A su vez, en el caso a,
quedan an variables de decisin por determinar, ya que la modificacin del sentido del flujo de
informacin no alcanza a invertirlas a todas.
En este ltimo caso, para lograr establecer el aporte sobre una transicin cualquiera -desde un
determinado Si+1a un dado Si-, se requiere conocer los valores de las variables de decisin que
han quedado libres, lo que significa un problema de optimizacin para definir tal aporte.Este
problema, obviamente, tiene una dimensionalidad menor que la que le corresponde a la etapa (Se
ha reducido en Sivariables).
El otro caso interesante es el c, donde se puede fijar slo parte del estado a la salida y el resto
debe ser calculado. En este clculo participa el estado a la entrada de la etapa y, en consecuencia,
aunque permanezcan invariables los valores fijados para la salida, al cambiar el estado S i+1,
habrn de generarse diferentes estados Si, por la modificacin de las componentes que surgen por
clculo8.
En la circunstancia descripta el diagrama de rutas aparecer con ramificaciones divergentes,
originadas en cada uno de los valores elegidos para el estado S i+1.
8Podra decirse que se est en condiciones de fijar, por ejemplo, la latitud del punto de destino, pero la
longitud depende de aquella y del cual sea el punto de origen.
i i i
a b c
Si+1
Si+1
Si
Si+1
Si
Si
di- S
id
id
i
di
Si- d
i
ri ri ri
Fig. 5.4.2
-
7/25/2019 Prog Dinamica
18/31
- 18
En la figura 5.4.3 puede apreciarse la
transformacin de un diagrama de flujo de
informacin en otro de rutas equivalente.
Se ha supuesto que se dan dos valores acada una de las variables que participan en la
definicin de los estados interetapas,
variables que aparecen "tachadas" en el
diagrama de flujo de informacin. Los
valores se indican mediante dos dgitos en el
interior de los nodos que representan los
estados. Adems se han marcado con un punto las transiciones sobre las cuales el clculo del
aporte a la funcin objetivo requiere de un proceso de optimizacin.
Puede advertirse que en los tramos que corresponden a la etapa 2 aparecen repetidos los
valores fijados de la variable de salida, un par para cada valor del estado S 3.
Como quedase dicho, esta ramificacin aparece toda vez que resulta imposible fijar la
totalidad de las variables que determinan el estado S2.
Merece un comentario final lo que sucede al aplicar esta metodologa en la ltima etapa. All
las variables de salida no se interconectan con nada y, por consiguiente, no existe un estado, tal
como se ha expuesto para los restantes casos. No se requiere, necesariamente, invertir el flujo de
informacin ni tiene importancia cuntas variables definen el estado y cuntas la decisin.
No obstante, por conveniencia en el clculo, se ha de mantener en la ltima etapa el concepto
de estado a la salida, fijando valores (discretizando) para las variables que se hayan elegido, en el
nmero corresponda, estn stas integradas al estado de salida o a la decisin. Por todo lo dicho
resulta claro que las transiciones en este punto nunca podrn presentarse en un esquema
ramificado.
La precisin que se puede alcanzar por esta va depende, como es obvio, de la cantidad de
estados intermedios que se generan. Si bien cuando el problema est formulado en trminos devariables continuas el nmero posible para los mismos es infinito, no resulta conveniente, en aras
de una mayor exactitud, aplicar la estrategia expuesta sobre un nmero grande de estados
intermedios.
En su lugar, es ms efectivo proceder a una primera bsqueda que permita acotar un mbito
donde reiterar el procedimiento y, as, todas las veces que resulte necesario.
40
31
32
21
22
21
22
12
11
Fig.5.4.3
-
7/25/2019 Prog Dinamica
19/31
- 19
El ejemplo 5.1, ya resuelto mediante el
procedimiento riguroso, puede servir para
fijar las ideas antes expuestas.
En la figura 5.4.4 se esquematiza laestructura bsica del diagrama de rutas
equivalente.
Al igual que antes, para la variable T1
se ha adoptado el rango 169,5-234,5.
En la ltima etapa se ha preferido
utilizar la variable T21en lugar del factor de fraccionamiento f, por ser ms sencillo acotar, en
forma efectiva, los lmites de variacin, elegidos, para el caso, 160 y 260.
La tabla siguiente muestra los resultados obtenidos para 6 valores en cada uno de los estados.
datos
T1
inic
T'1 T21
169.5
234.5
160
260
200
8.96
6.55
5.88
5.79
5.86
3.49
3.21
f
Fig. 5.4.4
-
7/25/2019 Prog Dinamica
20/31
- 20
T1 169.5 182.5 195.5 208.5 221.5 234.5
T21 r2> 8960 8058 7193 6398 5761 6553
160 5879
(0,160)
5397
(0,230)
4912
(0,301)
4429
(0,371)
3954
(0,441)
3489
(0,512)
180 5816
(0,183)
5313
(0,263)
4805
(0,344)
4298
(0,424)
3793
(0,505)
3294
(0,585)
200 5786
(0,213)
5274
(0,307)
4757
(0,401)
4239*
(0,424)
3722*
(0,589)
3209*
(0,682)
220 5775*
(0,256)
5263*
(0,368)
4750*
(0,481)
4242
(0,594)
3755
(0,706)
3445
(0,819)
240 5785
(0,320)
5297
(0,460)
4857
(0,601)
NF NF NF
260 5856(0,426) 5877(0,614) NF NF NF NF
r2+r1* 14735 13321 11943 10637 9483* 9762
En la primera fila y columna de la tabla figuran los valores de los distintos estados. En la
segunda fila los aportes sobre las transiciones entre el nodo inicial y los correspondientes a T1.
De las filas tercera a octava se encuentran los aportes de la ltima etapa y, entre parntesis, el
valor de f*. Con la sigla NF se marca el hecho que la transicin correspondiente no resulta posible
(T22o f exceden los lmites establecidos).
La lectura de una columna, considerando desde la tercera a la octava fila, permite decidir, para
el respectivo valor de T1, cual es la mejor eleccin en la ltima etapa; por ejemplo: para
T1=182,5 resulta lo ms adecuado T21= 220 o, lo que es equivalente, f = 0,368. Puede notarse
que las transiciones ptimas para cada estado se indican con un asterisco.
En la ltima fila se muestra el resultado, r2+ r1*, para las distintas decisiones posibles en la
primera etapa. El menor de todos ellos representa el ptimo global, 9483 $/ao, aproximadamente
un 5% superior al valor encontrado anteriormente.
Las decisiones ptimas seran T1= 221,5 y f = 0,589.
Pero an sera posible ajustar este resultado. De la inspeccin de la tabla surge una zona, a la
que se ha recuadrado, donde, evidentemente, se encuentra el ptimo del problema. Si se ampla la
bsqueda en dicha zona, agregando dos nuevos valores de T '1, 215 y 228, y otros dos de T21, 190
y 2109, se encuentra el ptimo para T1= 228, f=0,693 y un costo de 9076 $/ao, apenas un 0,66%
9Con esto se tendra calculada ms de la tercera parte de la nueva tabla.
-
7/25/2019 Prog Dinamica
21/31
- 21
superior al valor exacto.
5.Programacin Dinmica en sistemas ramificados
Hasta el momento slo se han considerado, para la aplicacin de las tcnicas de Programacin
Dinmica, solo aquellos problemas cuyos diagramas de flujo de informacin cumpliesen
estrictamente las caractersticas de seriados multietapas, tal como fuera definido al iniciar el
tratamiento del tema.
Cabra preguntarse si son ellos los nicos sobre los que puede ser aplicada la tcnica o si
resulta posible adecuar los diagramas, de modo tal que pueda hacrselo.
La respuesta que Programacin Dinmica extiende su aplicacin, en forma directa, a
problemas cuyos diagramas de flujo de informacin son algo ms complejos que lo vistos, as
como resulta posible usarla en otros, adaptando el respectivo diagrama.
Algunos de ellos sern vistos en este captulo; como ser los sistemas ramificados, donde
existen, en algn sector del flujo de informacin, al menos dos ramas o vas independientes, que
surgen de un punto comn (sistemas divergentes) o concurren a uno determinado (sistemas
convergentes). Los diagramas con reciclo de informacin ser otro caso a considerar.
En la figura 5.5.1 se muestra la
estructura bsica de un sistema
ramificado divergente, donde puedeapreciarse la existencia de dos
ramas, A y B, que se separan a
partir de la etapa k. Cada una de
ellas est constituida por un sistema
seriado multietapas como el que se
indicara al principio de este
captulo (Por simplicidad, esto no se ha indicado en el dibujo).
Si se omite por un momento la particular estructura del diagrama, considerando cada una delas ramas por separado, puede plantearse
Luego, evidentemente, es posible plantear
BsubsistoptSFO
AsubsistoptSFO
kBB
kAA
)(
)(
SSk+1
SkA
SkB
kk+1
A
B
N
dk+1
dk
dN
Fig. 5.5.1
-
7/25/2019 Prog Dinamica
22/31
- 22
con lo que, en consecuencia, la metodologa a aplicar es esencialmente la misma que la ya vista,
con la nica particularidad de que deben resolverse la totalidad de las ramas antes del
tratamiento de la etapa donde se produce la divergencia.La figura 5.5.2 presenta otro
caso de sistema ramificado: aqu
hay dos ramas que convergenen
un punto del diagrama y, a partir
de all, este presenta un flujo
unificado.
Comparado con el caso
anterior, el tratamiento reviste unamayor complejidad.
Hasta la etapa k, incluida, no
existe problema alguno porque, de hecho, esa porcin del diagrama no tiene ninguna alteracin.
En ese punto se dispondra de )(),( 111 kkkd
Nkk SFOroptSSFO
k
, donde puede apreciarse
que el ptimo parcial depende de estados sobre los que no se puede actuar en forma simultnea,
ya que la decisin dk+1puede modificar a Sk+1pero no a SN+1y, a la inversa, dN+1.
La solucin a esto es instrumentar un tratamiento secuencial, resolviendo, por ejemplo, las
etapas N, N-1,...k...1 como si fuesen la ltima etapa de la rama M...N+1.
Ello significa que habr que resolver, para distintos valores del estado SN+1
es decir que para lograr transformar el subdiagrama constituido por las etapas N...k...1 en la
ltima de la secuencia M...N+1 habr que optimizar al primero, considerando al estado SN+1como
un dato, tantas veces como valores se establezcan para el mismo.
Una vez que lo anterior ha sido completado -sin duda, el paso computacionalmente ms
engorroso- el procedimiento contina con la obtencin de
)()( 11211
NNNd
NN SFOroptSFO
N
, de acuerdo a lo visto.
)()()( 1 kBBkAAkd
kk SFOSFOroptSFO
k
),()(
),(),(
111
111211
NNNNd
NN
kNkkd
kNk
SSFOroptSFO
SSFOroptSSFO
N
k
dk+1
dk
d1
dN
dN+1
dM
Sk+1
S1
k+1 k 1
N+1
N
M
SN+1
SNe
SMe
Fig. 5.5.2
-
7/25/2019 Prog Dinamica
23/31
- 23
Si se cumple que Si+1+ di> Siy Si+1< Si; i = M...N+1 es posible aplicar otra va de solucin:
invertir por completoel sentido del flujo de informacin en la rama superior, con lo que el
sistema, ahora, ser divergentea partir de la etapa k.
En el caso de querer aplicar esta estrategia para un diagrama donde existen ms de dos ramasque convergen en un punto, la condicin anterior deber verificarse, al menos, para todas ellas
menos una.
Otro de los casos donde es posible aplicar Programacin Dinmica es sobre sistemas que
presentan una derivacin paralela (bypass), como el que se muestra en la figura 5.5.3.
La respuesta general a esta situacin es modificar el diagrama, mediante la creacin de
variables interetapas, de forma que se elimine la rama lateral, como se muestra a la derecha de la
figura. Esto significa el crecimiento de la dimensionalidad en los estados, cuestin que, como se
ver, aumenta la dificultad en la aplicacin de la tcnica.
Sjk
Sjl
Skp
Slp
Slp
SkpSjk
Sjl
k1 km
l1
lnj p
e1 exj p
Fig. 5.5.3
Por esta razn se suele acudir al artificio
de modificar el diagrama, mediante un corte
de la derivacin lateral, de modo de obtener
un sistema divergente. Esto se logra
adoptando el estado Skpcomo una decisin
e invirtiendo el flujo de informacin, con la
salvedad de mantener el carcter divergente
requerido para el nuevo diagrama (Se debe
privilegiar la inversin de las decisiones por sobre los estados, lo que en la figura serepresenta en el cambio de sentido en dkm).
Debe advertirse que la va de solucin expuesta requiere el sostenimiento de Skpa lo largo del
proceso de optimizacin de ambas ramas divergentes generadas; esto es, en la etapa p se tiene
FOp(Slp, Skp) y en ese momento se asigna el subesquema ya tratado a la rama l1...ln, manejando Skp
como un dato (Numricamente, habr que resolver para varios valores de Skp).Al final se tendr
FOl1(Sjl, Skp), punto en el cual se comienza el tratamiento de la rama k, comenzando por la etapa
km, dejando a Skpcomo datohasta obtener FOk1(Sjk,Skp).Es recin en este punto, al tratar la
Sjk
Skp
Sjl
k1
km
Slp
l1
ln
j p
Fig. 5.5.4
-
7/25/2019 Prog Dinamica
24/31
- 24
etapa donde se produce la divergencia,cuando se ha de producir la optimizacin con respecto a
Skp.
El ltimo tipo de diagrama de flujo de informacin anmalo donde se ha de considerar la
aplicacin de Programacin Dinmica sern aquellos donde existen reciclos de informacin,como el que se muestra en la figura 5.5.5
La nica posibilidad que existe de aplicar la tcnica es a travs de la eliminacin del reciclo, lo
que implica una modificacin sustancial del diagrama de flujo.
En la parte derecha de la figura 5.5.5 se esquematiza el procedimiento. El estado S kj se
transforma en decisinsimultneamenteen las etapas j1y kr, lo que obliga a invertir el flujo en la
rama superior.
Sj+1
Skj
k1
k1
kr
kr
j1
j1
jp
jp
Sjk
Sjk
Sj+1
Skj
Fig. 5.5.5
La eleccin de Skjno es arbitraria, ya que se busca que el sistema ramificado resultante sea
divergente (Lo es en la etapa jp), por su mayor simplicidad en el tratamiento posterior. De aqu
que la inversin a la que se hiciese referencia deber privilegiar, otra vez y por la misma razn
que antes, las decisiones por sobre los estados.
El procedimiento a seguir en la optimizacin del esquema modificado presenta la
particularidad de que, por actuar Skjen dos puntos diferentes del mismo, el tratamiento de la rama
k1...krdeber hacerse manteniendo a Skjcomo un dato; ms an, esta caracterizacin se ha de
prolongar hasta el momento de considerar la etapa j1, punto en el cual, recin, se podr tratar a Skjcomo una decisin.
El estudio de las tcnicas de optimizacin es importante no slo por la posibilidad de resolver
problemas que presentan determinadas caractersticas sino -lo que tal vez sea ms importante-
porquesu conocimiento permite estructurar los problemas de forma tal que puedan ser utilizadas
determinadas tcnicas.
En la figura 5.5.6 se muestra la estructura de la red de intercambio analizada en el captulo de
ordenamiento de clculo.
-
7/25/2019 Prog Dinamica
25/31
- 25
Como se vio, en
aquella oportunidad, el
nmero de grados de
libertad para esta red es
3 y una de lasalternativas era
considerar, como
variables de decisin, a
la temperatura T1 y a
los factores de
fraccionamiento f1y f2.
Este problema de tres variables puede ser resuelto mediante Programacin Dinmica, con una
importante reduccin en la complejidad de los clculos (Debe advertirse que se ha omitido, enrazn de tratarse del mismo problema ya visto, el detalle de las ecuaciones que definen el modelo
matemtico del sistema).
En la parte superior de la figura
5.5.7 se muestra el diagrama de
flujo de informacin del
problema. Los bloques E, C, 1, 2 y
3 se corresponden con los equipos
de intercambio trmico, mientrasque m1 y m2 representan los
puntos de mezcla de las corrientes
4 y 2 (La parte superior de la
figura 5.5.7 es equivalente a la
3.2.10).
Puede verse, en este diagrama,
que existen dos grandes segmentos, cada cual con uno de los factores f como variable de decisin
exclusiva y compartiendo ambos a T1.
La circunstancia apuntada conduce a pensar en la posibilidad de reestructurar el flujo de
informacin bajo la forma de un sistema ramificado divergente, como se muestra en la parte
inferior de la figura (Ntese que se ha recurrido al artificio de crear una etapa de interconexin y
dos variables adicionales, T1 y T1, ambas, lgicamente, iguales a T1).
El planteo, ahora, es sencillo: hay que obtener el mnimo de cada una de las ramas, FOc..m1(T1)
y FO3..m2(T1), operando sobre el correspondiente factor de fraccionamiento, para luego
considerar la suma mnima de ambos factores, ya que la etapa de interconexin no efecta aporte
T1
A1
Ac
A2
1 2 3 EC
A3 AE
qV
f1
f2
qE
T22
T21
T42T41
m2m1
T'1
T''1
f1
f2
C-1-2-m1
3-E-m2
Fig. 5.5.7
Fig. 5.5.6
-
7/25/2019 Prog Dinamica
26/31
- 26
alguno a la funcin objetivo, tal como se indica en la tabla siguiente:
T1= T1 f1* FOc..m1 f2* FO3..m2
174,5 0,545 8689,6 0,300 5578,5
184,5 0,575 8009,5 0,373 5183,5
194,5 0,605 7356,7 0,445 4786,6
204,5 0,635 6748,6 0,514 4389,1
214,5 0,665 6224,3 0,582 3992,0
224,5 0,696 5907,3 0,649 3596,3
234,5 0,734 7611,6 0,715 3203,0
El ptimo para el sistema se encuentra para T1=228,7, f1=0,710, f2=0,676, con un costo de
9384 $/ao.
6. Problemas de clculo en Programacin Dinmica
Hasta ahora se han podido apreciar las ventajas de Programacin Dinmica, al reducir la
dimensionalidad de los problemas y, consecuentemente, la complejidad numrica de su
tratamiento.
Pero esto no es gratuito: tal reduccin exige resolver, repetidamente, cada uno de los
subproblemas que genera la estrategia de optimizacin.
Si el nmero de veces que hay que repetir la solucin de los problemas es muy grande, an
cuando el nmero de grados de libertad de cada uno, esto es, su dimensionalidad, sea pequeo,
bien podra suceder que resultase ms sencillo "olvidar" la estructura del diagrama de flujo de
informacin, no aplicar Programacin Dinmica y resolver el caso por bsqueda simultnea,
entendiendo por esto el uso de cualquier tcnica que aborde el tratamiento conjunto de las
variables de decisin.
Para lograr enfocar la cuestin desde un punto de vista analtico se requiere contar con algn
tipo de funcionalidad que vincule la dimensionalidad de un problema con la dificultad de
optimizarlo. Tales expresiones son, en rigor, de dudosa generalidad para los mtodos ms
difundidos.
Resulta posible, en cambio, establecer una cota superior a esta dificultad: basta con tomar un
mtodo ineficiente de optimizacin, para el que sea posible encontrar una funcionalidad del tipo
buscado.
Un mtodo que rene estas caractersticas es el nmero de oro extendido a multivariables,
donde el nmero de clculos a realizar para obtener el ptimo de una funcin de t variables puede
expresarse bajo la forma bt, siendo b una constante que depende de la exactitud deseada.
-
7/25/2019 Prog Dinamica
27/31
- 27
Volviendo al esquema general de
la figura 5.1.1, supngase que todas
las etapas tienen decisiones y
estados de interconexin definidos
por D y S variables,respectivamente, estando fijo el
estado a la entrada al sistema.
Supngase, tambin, que en la bsqueda de FOi(Si+1) se consideran a valores para cada una de
las variables que integran el estado Si+1.Esto dar aSproblemas con D variables de decisin para
cada una de las etapas, salvo para el ltimo paso de optimizacin, donde ha de existir uno solo, en
virtud de estar fijo el estado a la entrada del sistema.
Con esto, la cota superior para las dificultades de clculo inherentes a la estrategia de
optimizacin por Programacin Dinmica PDy bsqueda simultnea BS han de ser
siendo la relacin entre ambos
y la dificultad relativa aumenta (Programacin Dinmica resulta menos atractiva frente a
bsqueda simultnea) con el incremento del nmero de variables de interconexin mientras quedisminuye con el aumento del nmero de variables de decisin por etapas o la cantidad de stas.
Lo anterior puede tomarse como una consideracin de tipo general; la tendencia que se verifica
al aplicar la tcnica. Pero an resulta posible, frente a un caso concreto, moverse dentro de los
extremos que se han examinado; esto es, utilizar Programacin Dinmica sobre un diagrama se
han agrupado etapas, para ser optimizadas en forma conjunta.
Esto puede ser comprendido mejor mediante el anlisis de un ejemplo simple, para el cual se
tomar a=b=8 en la correspondiente expresin de (Esto ltimo implica una reduccin delintervalo de incertidumbre menor al 5% en cada variable en el mtodo del nmero de oro
extendido a n dimensiones).Dichos valores sern utilizados en todo el anlisis que sigue.
En la figura 5.6.1 (a) se muestra un
hipottico diagrama de flujo de
informacin, donde se han indicado slo las
variables que componen las decisiones y
los estados de interconexin, en virtud de
NDBS
SDPD baNb ;1)1(
1)1()1(
SND
BS
PD aNb
rN -1
dN -1
dN
d2
d1
S2
S1
S3
SN -1S N
SN +1
rN
r2
r1
Fig. 5.6.1
-
7/25/2019 Prog Dinamica
28/31
- 28
constituir ellas los nicos elementos a tener en cuenta.
Ntese que aqu no hay constancia en el nmero de variables por etapa, lo que obliga a un
anlisis caso por caso.
Si el problema fuese resuelto por Programacin Dinmica, sin efectuar ninguna modificacin
en el diagrama, la cota superior de la dificultad de clculo sera
1-2-3= 8281+ 8382 + 80 82= 83+ 85+ 82
donde cada uno de los monomios se compone por el producto de 8 Si+1y 8Di
Si la solucin se encara a travs de una bsqueda simultnea, lo que , esquemticamente, se
indica en 5.6.1 (b) como una etapa nica -se ignora, en absoluto, la existencia de subsistemas-, el
grado de dificultad asociado sera [1-2-3]=85
Pero estas dos no son las nicas estructuras posibles. Existe la alternativa de apelar a
estrategias mixtas: agrupar, por ejemplo, solo las dos primeras etapas, o las dos ltimas, como se
indica en 5.6.1 (c) y (d). Para estos casos se tendr
1-[2-3]= 82 81+ 84= 83+ 84
[1-2]-3= 83 83+ 82= 86+ 82
lo que lleva a la conclusin de que la mejor estrategia resulta de considerar en forma conjunta las
etapas 2 y 3, agrupamiento que ha de formar parte de un diagrama seriado co la etapa 1.
Resulta obvia la imposibilidad de efectuar este anlisis en detalle para todos los casos, donde,
con seguridad, habr que vrselas con diagramas de flujo, y alternativas, por ende, de mayor
complejidad.
Sera deseable contar con un criterio simple, que no se viese afectado por las caractersticas
estructurales del flujo de la informacin. Es posible contar con tal criterio, al menos en lo que
concierne al agrupamiento de etapas.
En la figura 5.6.2 (a) se esquematiza un
segmento, etapas i y j, del diagrama de flujo
genrico. All Siy diindican elnmero devariables que componen el estado y la
decisin de la etapa, respectivamente.
Para estas dos etapas solamente, las
estrategias posibles son tratarlas en forma
separada o agruparlas.
Este anlisis focalizado puede efectuarse,
Fig. 5.6.2
-
7/25/2019 Prog Dinamica
29/31
- 29
y sus conclusiones son vlidas para cuando se considera el segmento dentro del sistema total, por
la estructura matemtica (suma de monomios) que posee la expresin que permite el clculo del
grado de dificultad.
Volviendo al esquema, si las etapas se tratan en forma separada o conjunta, se tendr, comodificultad relativa de la primera con respecto a la segunda
y queda claro que esta dificultad relativa es mayor que 1 (conviene el agrupamiento) toda vez
que Si- Si+1 di.
Debe tenerse en cuenta que en la expresin anterior se consideran la totalidad de las variables
que componen el estado a la entrada a la etapa pero solo las variables que integran el estado
que la interconecta con quien se analiza el agrupamiento. Lo anterior es particularmente
importante cuando se consideran los puntos de divergencia en un sistema ramificado.
En la parte b de la figura 5.6.2 se presenta el caso de una etapa sin decisin. Aqu es posible
ensayar cuatro estrategias: el tratamiento del diagrama tal como est, la bsqueda simultnea en
todo el segmento o agrupar la etapa j con la k o la i. Los grados de dificultad para cada alternativasern10
con lo que, como puede verse, siempre resulta conveniente el agrupamiento de j con una etapacontigua, por lo menos para eliminar el estado de interconexin definido por el mayor nmero de
variables, Sio Sj, con independencia de que convenga el tratamiento unificado de las tres etapas,
lo que puede analizarse, luego, con el criterio expuesto anteriormente.
El ltimo caso de agrupamiento a considerar es el de pequeos reciclos.
10En el caso de tratamiento individual de cada etapa se considera una dificultad de clculo para lograr
expresar FOk(Sj) como FOj(Si)
jiii
jii
iiji
ddSSrel
ddSij
dSdSij
88
8
88
1
1
1
..
....
iiki
iikj
jii
iiij
dSdSijk
dSdSijk
ddSijk
dSdSijk
1
1
1
1
88
88
8
88
.
....
-
7/25/2019 Prog Dinamica
30/31
- 30
Ya se ha visto que es posible aplicar Programacin Dinmica a este tipo de diagramas, aunque
resulte bastante engorroso hacerlo.
De aqu que se pudiera pensar en un tratamiento conjunto de las etapas que se encuentran
involucradas en un reciclo de informacin.No resulta posible un tratamiento generalizado como en el caso anterior, por lo que se recurrir
a un enfoque de tipo heurstico.
En la figura 5.6.3 se muestra un sector de un diagrama de flujo donde aparece un reciclo,
donde se supondr que cada estado y decisin, que interesan en el anlisis del reciclo, se
componen de una sola variable.
Como ya qued visto, la solucin por
programacin dinmica exige el manejo de la
variable de reciclo como una decisin en
suspenso, un dato, lo que lleva a invertir el
flujo en la etapa 1, que quedara sin decisin
y, consecuentemente, se agrupar con la 2.
La dificultad relativa del tratamiento por separado de las, ahora, N-1 etapas con respecto al
enfoque simultneo ser
Nrel
N
8
88)2(8 1111
donde se ha tenido en cuenta la bsqueda para un solo valor del estado a la entrada de la etapa
N, en razn de ser algo comn para ambas estrategias.
La expresin anterior resulta ser menor que la unidad para N mayor o igual que 4, por lo que,
extendiendo el criterio a otros diagramas de flujo de informacin, se puede plantear que reciclos
con menos de cuatro variables involucradas en las decisiones deben ser resueltos por
bsqueda simultnea.
Estos criterios de agrupamiento de etapas deben constituir un paso previo a la optimizacin
efectiva del sistema, el que, en definitiva, debera realizarse de acuerdo al siguiente esquema:
1.- Formulacin matemtica del problema
2.- Determinacin de una estrategia de clculo
3.- Construccin del diagrama de flujo de informacin
4.- Anlisis de agrupamiento de etapas en el diagrama.
5.- Optimizacin efectiva del sistema.
En el desarrollo de la estrategia mixta, que presupone el quinto y ltimo paso, est implcita la
Fig. 5.6.3
-
7/25/2019 Prog Dinamica
31/31
31
seleccin del o de los mtodos que resulten ms adecuados para llevar a cabo el proceso de
optimizacin.
Bibliografa
- "Discrete Dynamic Programming" Aris, Blaisdell, 1963.
- "Foundations of Optimization" Wilde & Beightler, Prentice Hall, 1967.
- "Optimization of multistage cyclic and branching systems by serial procedures" Aris,
Nemhauser, Wilde, AIChEJ 10 p.913, 1964
top related