Programacion dinamica

iPropuesta de un Algoritmo para Resolver Problemas de Programación Dinámica Aplicada a los Recursos Hídricos
Pilar, Jorge V.
Dto. de Hidráulica - Facultad de Ingeniería - UNNE Av. Las Heras 727 - (3500) Resistencia - Chaco - Argentina Tel: +54 (03783) 425064 (int. 119) - E-mail: jpilar@bigfoot.com Web: http://www.jorge-pilar.amazonas.net INTRODUCCIÓN Algunos problemas que tienen que ver contomar decisiones poseen una estructura especial: las decisiones deben ser tomadas en forma secuencial, en el tiempo y/o en el espacio. Estos problemas pueden descomponerse en varias etapas, las que pueden ser completadas de una o más formas. A pesar de que las decisiones son tomadas de a una, ellas son altamente interdependientes. Para resolver este tipo de problemas, a mediados de la década del 50,Richard Bellman desarrolló la programación dinámica (PD). El planeamiento y operación de sistemas de recursos hídricos presenta innumerables situaciones caracterizadas por una secuencialidad espacial y/o temporal en la toma de decisiones. Estas situaciones son especialmente adecuadas para ser abordadas a través de la PD. La PD está limitada a problemas donde la función objetivo (FO) es función deuna o más variables de decisión y no proporcional a ellas (Hall y Dracup, 1974). Esta función puede, inclusive, ser discontinua, al punto de estar definida solamente para valores discretos de las variables (Labadie, 1977; Barros, 1997). Sintéticamente, la solución de problemas de PD consiste en buscar la decisión óptima “paso a paso”, teniendo en consideración las futuras consecuencias de cadadecisión: la decisión en una determinada etapa debe ser la mejor, no solamente considerando esa etapa, sino todas las restantes. PROBLEMAS DE PD La figura 1 esquematiza una de las “N” etapas de un proceso secuencial de asignación de recursos. qi xi1 .... xij .... xiJ Siendo: qi variable de estado en la etapa “i”, faltando todavía “N-i” etapas xij uno de los valores que puede adoptar la variable dedecisión de “xi” en la etapa “i” xi
*

etapas

Etapa i

xi

*

resto

decisión “óptima” en la etapa “i”.

Figura 1

Esquema de una etapa de un problema de PD

Para explicar el procedimiento de solución de un problema de PD serán definidos los siguientes términos: Ri (xij) el resultado (costo o beneficio) de la decisión “j” para la variable “xi”, en la etapa “i” fi (qi) elbeneficio “óptimo” de las etapas i, i+1,..., N, para el valor “q”de la variable de estado en la etapa “i”. Por lo tanto, la solución del problema en el paso “i” será:

f i (qi ) = OPTIMO R i ( x ij ) ⊕ f i+1 (qi − x ij )

[

]

(1)

con la condición que:

∑ x ij ≤ qi
i=1

J

(2)

siendo “J” el grado de discretización de la variable de decisión. En otras palabras, esto significa queesta variable puede adoptar un valor entre “J+1” valores posibles (incluída la opción de adoptar el valor “cero”) sin sobrepasar el límite del recurso. Este límite, en la etapa “i”, es definido por el valor de la variable de estado. El símbolo ⊕ indica una operación cualquiera, normalmente una suma o un producto. La ecuación de estado en cada etapa debe ser del tipo: q i+1 = q i − x i
∗

(3)

Laúnica etapa en la cual el problema está totalmente definido es la última, o sea en la etapa “N”. Entonces, resuelto el problema para “i = N”, será fácil resolverlo, sucesivamente, para “i = N-1”, hasta “i = 1”. Esta técnica va generando su propio progreso y por eso a esta forma de resolución se la denomina “algoritmo de recursión” y a las fórmulas, “fórmulas recursivas” (Barros, 1997; Bronson,1996; Cifres, 1993; Hall y Dracup, 1974; Labadie, 1977; Taha, 1995; Ventsel, 1982; Wagner, 1986). El proceso de optimización de las decisiones es bifásico: fase 1, del fin para el inicio, reconociendo las mejores decisiones para cada etapa y fase 2, del inicio hasta el fin, leyendo las recomendaciones óptimas surgidas de la fase anterior. El algoritmo La filosofía del algoritmo que se presenta en...