• Author / Uploaded
• Enrique Marquez

Citation preview

Unidad I

Programación dinámica (DP)

Programación dinámica

La técnica de Programación dinámica fue inventada como un método general de optimización de procesos de decisión por etapas. La técnica de programación dinámica es adecuada para resolver problemas cuya solución puede caracterizarse recursivamente (como con la técnica divide y vencerás) y en la que los subproblemas que aparecen en la recursión se solapan de algún modo, lo que significara una repetición de cálculos inaceptable si se programara la solución recursiva de manera directa.

La aplicación de la técnica de programación dinámica evita la repetición de cálculos mediante la memorización de la solución de cada subproblema en una tabla, de manera que no haya que calcularlo mas de una vez.

Fases para la aplicación de la técnica

La aplicación de la técnica de programación dinámica tiene dos fases fundamentales: 1 Definir recursivamente la solución del problema. 2 Definir la estructura de datos para memorizar las soluciones de los subproblemas y escribir el algoritmo que va calculando los valores de esa estructura de datos siguiendo la caracterización de la solución definida en la fase 1, pero sin repetir el calculo de soluciones de subproblemas.

CONCEPTUALIZACIÓN DE PROGRAMACIÓN DINÁMICA

1. En contraste con la programación lineal, no se cuenta con una formulación matemática estándar para “el” problema de Programación dinámica. 2. Se trata de un enfoque de tipo general para la solución de problemas y las ecuaciones específicas que se usan se deben desarrollar para que representen cada situación individual. 3. Se necesita un cierto grado de creatividad y un buen conocimiento de la estructura general de los problemas de Programación Dinámica para reconocer cuándo y cómo se puede resolver un problema por medio de estos procedimientos.

TIPOS DE PROGRAMACIÓN DINÁMICA 1. Programación dinámica determinística. El estado en la siguiente etapa está completamente determinado por el estado y la política de decisión de la etapa actual. 2. Programación dinámica probabilística.

El estado en la siguiente etapa no está completamente determinado por el estado y la política de decisión de la etapa actual, existiendo en su lugar una distribución de probabilidad para determinar cuál será el siguiente estado.

CARACTERÍSTICAS DE PROGRAMACIÓN DINÁMICA 1. Etapas:

El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas. 2. Estados asociados: Cada etapa tiene cierto asociados con su inicio.

número

de

estados

3. Política de decisión: El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con el inicio de la siguiente etapa.

4. Diseño de solución: El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para la política de decisión óptima en cada etapa para cada uno de los estados posibles.

5. Principio de optimalidad:

a. Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. b. La decisión inmediata óptima depende sólo del estado actual y no de cómo se llegó ahí. 6. Inicio de solución: El procedimiento de solución se inicia al encontrar una política óptima para la última etapa.

7. Relación recursiva: Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n + 1.

8. Retroceso: Cuando se use esta relación recursiva, el procedimiento de solución comienza al final y se mueve hacia atrás etapa por etapa – encontrando cada vez la política óptima para esa etapa – hasta que se encuentra la política óptima desde la etapa inicial.

Ejemplo: problema de la ruta más corta Supongamos que se trata de seleccionar la ruta más corta entre dos ciudades. La red de la figura siguiente muestra las rutas posibles entre el inicio del nodo1 y el destino en el nodo 7. Las rutas pasan por ciudades intermedias, representadas por los nodos 2 a 6. Este problema se puede resolver enumerando en forma detallada todas las rutas entre los nodos 1 y 7 (hay 5).

Para resolver el problema con programación dinámica primero se descompone en etapas, delimitadas por las líneas verticales interrumpidas de la figura. A continuación se hacen los cálculos para cada etapa por separado. El concepto general es calcular las distancias (acumuladas) mas cortas a todos los nodos terminales de una etapa, para usarlas a continuación como datos de la etapa inmediata posterior. La etapa 1 tiene 3 nodos finales, 2,3 y 4, y sus cálculos son sencillos.

Resumen de los resultados de la etapa 1. Distancia mas corta al nodo 2= 7 millas (desde el nodo 1) Distancia mas corta al nodo 3 = 8 millas (desde el nodo 1) Distancia mas corta al nodo 4 = 5 millas (desde el nodo 1)

A continuación, la etapa 2 tiene 2 nodos extremos, el 5 y el 6. si se considera primero el nodo 5, se ve en la figura que hay tres rutas posibles para llegar a el, que son (2,5), (3,5) y (4,5). Esta información, junto con las distancias mas cortas a los nodos 2, 3 y 4 determina la distancia (acumulada) mas corta al nodo 5, como sigue:

De igual manera para el nodo 6 se tiene

Resumen de resultados de la etapa 2: Distancia más corta al nodo 5 = 12 millas (desde el nodo 4) Distancia más corta al nodo 6= 17 millas ( desde el nodo 3) El ultima paso es examinar la etapa 3. El nodo del destino 7 se puede alcanzar ya sea desde el nodo 5 o desde el nodo 6. Usando el resumen de los resultados de la etapa2, y las distancias de los nodos 5 y 6 al nodo 7, se obtiene.

Resumen de resultado de la etapa 3

Distancia más nodo 5).

corta al nodo 7= 21 millas (desde el

Estos cálculos indican que la distancia mas corta entre los nodos 1 y 7 es 21 millas. Las ciudades que definen la ruta optima se determinan como sigue. Según el resumen de la etapa 3, el nodo 7 esta enlazado con el nodo 5. a continuación según el resumen de la etapa 2 el nodo 4 esta vinculado al nodo 5. por ultimo, según el resumen de la etapa 1, el nodo 4 esta enlazado con el nodo 1. así, la ruta más corta se define como: 1---- 4-----5 ----- 7.

Donde F4(X4)= 0 para X4 =7. El orden asociado de cálculos es f3 ---- f2-----f1 Etapa 3.

Como el nodo 7 (X4=7) está conectado con los nodos 5 y 6 (X3=5 y 6) con exactamente una ruta a cada uno, no hay alternativas para elegir, y los resultados de la etapa 3 se pueden resumir como sigue:

X3

d(x3,x4)/x4=7

solución optima/ f3(x3)

x4

5

9

9

7

6

6

6

7

Etapa 2. la ruta (2,6) esta bloqueada, porque no existe. Dada f3(x3) desde la etapa 3, se pueden comparar las alternativas factibles como se ven en el siguiente cuadro: X2 2

12+9=21

---------------

21

5

3

8+9=17

9+6=15

15

6

4

7+9=16

13+6=19

16

5

La solución optima de la etapa 2 se lee como sigue: si usted si usted está en las ciudades 2 o 4, La ruta más corta pasa por la ciudad 5, y si está en la ciudad 3, la ruta más corta pasa por la ciudad 6.

Etapa1. Desde el nodo 1 se tiene tres rutas alternativas: (1,2), (1,3), (1,4). Se usa f2(x2) desde la etapa 2 para calcular el siguiente cuadro

La solución optima en la etapa 1 indica que la ciudad 1 esta enlazada con la ciudad 4. a continuación, la solución optima en la etapa 2 enlaza la ciudad 4 con la ciudad 5. por ultimo, la solución optima en la etapa 3 conecta la ciudad 5 con la ciudad 7. Así la ruta completa es 1 --- 4 ---5 ---- 7.

Ejemplos característicos de DP de sistemas de energía eléctrica 1. Planificación de la expansión de la generación 2. Programación semanal de grupos térmicos

3. Coordinación hidrotérmica

Planificación de la expansión de la generación Minimizar los costes totales (fijos y variables) de expansión del equipo generador para un alcance de varios años.

Decisiones: Potencia a instalar de cada tipo de generación en cada año del alcance del modelo. Restricciones de expansión: · Potencia instalada inicial conocida. · Máxima (mínima) potencia instalable, inversión máxima (mínima), número máximo (mínimo) de generadores instalables en cada año. Restricciones de operación: · Balance generación demanda en cada año. Estados: Número total de generadores instalados al comienzo de cada año.

Respuesta al problema planteado: El Ingeniero Forestal tiene un costo mínimo de $24 para ir desde su oficina al lugar de cosecha, y ese mínimo lo puede lograr yendo desde su oficina al lugar 3 luego al lugar 8 luego al lugar 9 y de ahí al lugar 13, que es donde está la cosecha.

Programación Dinámica Probabilística.

En la programación dinámica probabilística, el estado en la etapa siguiente no queda completamente determinado por el estado y la decisión de la subpolítica en el estado actual, sino que existe una distribución de probabilidad para lo que sería el estado siguiente.

Gráficamente tenemos: