Características de los problemas de programación dinámica

Índice

1.1 Características de los problemas de programación dinámica 2

1.2. Ejemplos de modelos de programación dinámica 4

1.3. Programación dinámica determinista 7

1.4. Programación dinámica probabilista 11

Programación dinámica probabilística 11

Problema de la diligencia. 12

Bibliografía: 15

1.1 Características de los problemas de programación dinámica

Características generales de los problemas de programación dinámica.

El problema de la diligencia es un prototipo literal de los problemas de programación dinámica. Por tanto una manera de reconocer una situación que se puede formular como un problema de programación dinámica es poder identificar una estructura análoga a la del problema de la diligencia.

Características básicas:

1.- El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas.

2.- Cada etapa tiene cierto número de estados asociados con su inicio. Los estados son las distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema.

3.- 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.- El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo.

5.- Dado el estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. Este es el principio de Optimalidad para programación dinámica.

6.- El procedimiento de solución se inicia al encontrar la política óptima para la última etapa.

7.- 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.

La forma precisa de relación recursiva difiere de un problema a otro de programación dinámica, pero usaremos una notación análoga a la siguiente:

N = número de etapas.

n = etiqueta para la etapa actual ( n = 1,2,…,N)

sn = estado actual para la etapa n

xn = variable de decisión para la etapa n

xn* = valor óptimo de xn (dado sn)

fn(sn,xn) = contribución a la función objetivo de las etapas n, n+1,…,N, si el sistema se encuentra en el estado sn en la etapa n, la decisión inmediata es xn y en adelante se toman decisiones óptimas.

fn*(sn) = fn(sn,xn*)

La relación recursiva siempre tendrá la forma:

fn*(sn) = mín fn(sn,xn) ó fn*(sn) = max fn(sn,xn)

8.- Cuando se usa esta relación recursiva, el procedimiento de solución comienza al final y se mueve hacia atrás etapa por etapa, hasta que encuentra la política óptima desde la etapa inicial.

La programación dinámica (PD) es un procedimiento matemático diseñado principalmente para mejorar la eficiencia de cálculo de problemas de programación matemática seleccionados, descomponiéndolos en subproblemas de menor tamaño y por consiguiente, más fáciles de calcular. La programación dinámica comúnmente resuelve el problema en etapas, en donde en cada etapa interviene exactamente una variable de optimización (u optimizadora). Los cálculos en las diferentes etapas se alcanzan a través de cálculos recursivos de manera que se genere una solución óptima factible a todo el problema.

Los sutiles conceptos que se utilizan en PD junto con las notaciones matemáticas poco conocidas son una fuente de confusión, en especial para un principiante. No obstante nuestra experiencia demuestra que la exposición frecuente a formulaciones y soluciones de PD permitirá a un principiante, con algo de esfuerzo, entender estos conceptos avanzados. Cuando sucede esto, la programación dinámica se vuelve sorprendentemente sencilla y clara.

1.2. Ejemplos de modelos de programación dinámica

1.- Un Ingeniero Forestal, requiere saber: i) Cuál es el costo mínimo, y ii) Cuál es la ruta con ese costo mínimo, para ir desde su oficina hasta el lugar donde está la cosecha. En su camino debe pasar por 3 sectores o ciudades antes de llegar a su destino, y lugares posibles en esos sectores o ciudades. Las posibles rutas, y el costo asociado por Kms. de distancia y otros en $, se ven en el siguiente esquema:

Solución:

Para ir de 1 a 13 hay 48 rutas posibles. Una posibilidad para encontrar la solución es calcular el valor asociado a cada una y ver cuál es la que proporciona el menor costo. ¿Y si fuesen miles de rutas? Por eso se descarta esa alternativa y se usa el método de la programación Dinámica, donde se resuelve desde el final hacia el inicio, y hay etapas y estados. Etapas: Son 4. La etapa 1 es decidir ir del estado inicial 1 al estado 2, 3, 4 o 5 que son los puntos posibles en el sector siguiente. La etapa 2 es decidir ir a 6, 7 u 8.

La etapa 3 es decidir ir a 9, 10, 11 o 12. La etapa 4 es decidir a 13.

Estado: Lugar donde se encuentra. La etapa 1 tiene 1 estado: el 1. La etapa 2 tiene 4 estados: 2, 3, 4, 5. La etapa 3 tiene 3 estados: 6, 7, 8. La etapa 4 tiene4 estados: 9, 10, 11, 12.

Cálculos:

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.

1.3. Programación dinámica determinista

Los problemas de programación dinámica determinística en donde el estado en la siguiente etapa está completamente determinado por el estado y la política de decisión de la etapa actual se puede describir mediante un diagrama como el que se muestra en la siguiente figura.

Estructura básica para la programación dinámica determinística.

En la etapa n el proceso está en algún estado Sn.

Al tomar la decisión Xn se mueve a algún estado Sn+1 en la etapa n+1. La contribución a la función objetivo de ese punto en adelante se calcula como f_n^*+1. La política de decisión también contribuye a la función objetivo. Al combinar estas dos cantidades en la forma apropiada se obtiene fn(Sn, Xn) la contribución de la etapa n en adelante.

La optimización

...