Programacion dinamica

*
*
*
*
* Programación dinámica
*
*
*

*
INDICE

1. Introducción 3
2. Características de la programación dinámica 4
3. Políticas en programación dinámica 6
4. El principio de optimización de Bellman 7
5. Clasificación de los modelos dinámicos en cuanto a su resolución 8
5.1. Ejemplo. Diligencia (Programación dinámica) 8
5.2.Programación dinámica determinística 14
5.3. Programación lineal mediante programación dinámica 17
6. Bibliografía 20

*
*
*
*
*
*
*
*
*
*
*

1. Introducción

Como consecuencia de la segunda guerra mundial, y del fuerte desarrollo industrial de la post-guerra, surgieron gran cantidad de fenómenos que necesitaron el control humano, mediantela toma de decisiones, para dirigirlos en el transcurso del tiempo. Cuando estas decisiones debían ser tomadas en distintos tiempos dieron lugar a los fenómenos conocidos con el nombre de procesos de decisión polietápico, caracterizados porque las variables que describen el fenómeno están sujetas a transformaciones en el tiempo, pudiendo modificarse mediante decisiones hechas por el usuario.
Sonprocesos de decisión secuenciales, esto es que tienen una naturaleza dinámica, en los que la decisión que se tome en un instante puede no ser óptima para otro, ya que estos procesos evolucionan con el tiempo.
Si el fenómeno evoluciona de forma determinística, en función de la decisión tomada; si en cada tiempo que se tiene que realizar una decisión se dispone de K de éstas y si el número de vecesque se toma una decisión es N, resulta que el número de trayectorias descritas por el fenómeno es . Si asociada cada trayectoria existe una f.o. se tendrán que comparar los valores asociados para poder decir cuál es la trayectoria óptima
La programación dinámica nació, debido a la dificultad que presenta la resolución de este tipo de problemas. Sin embargo, conviene advertir que no todos losprocesos de decisión secuenciales se resuelven mediante la programación dinámica y que, por otro lado, no todos los problemas que resuelve son procesos de decisión secuencial.
La programación dinámica es una forma de ver los problemas, que se usa tanto en problemas lineales como en los no-lineales. Estos no necesitan caracterizarse por un sistema de ecuaciones. Esto, si bien es una ventaja, es almismo tiempo un inconveniente, ya que no existen algoritmos de tipo general para su resolución, sino que cada problema tiene un tratamiento especial.

* 2. Características de la programación dinámica
1. El problema se puede dividir por etapas, que requieren una política de decisión en cada una de ellas.

2. Cada etapa tiene un cierto número de estados asociados a su inicio. (Estados sonlas diferentes 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 pretende hallar la política óptima para el problema completo. Esto quiere decir, la política a emplear desde cualquierposible estado del problema.

5. Dado el estado actual, la política óptima desde este estado es independiente de las políticas adoptadas en las etapas anteriores. (La solución depende únicamente del estado actual y no de cómo se llegó allí)

6. El procedimiento de la solución termina cuando se obtiene la política óptima de la última etapa (por lo general la solución en esta etapa es trivial)

7.Siempre se dispone de una relación recursiva (esto es lo que permite trabajar las decisiones interrelacionadas).
La relación recursiva será:

fn* (Sn)= Max Xn ( fn (Sn, Xn) ) o también fn* (Sn)= Min Xn ( fn (Sn, Xn))
Sn: Estado actual para la etapa n.
Xn: variable de decisión para la etapa n
N: número de etapas.
n: etiqueta para la etapa actual (1,2,...,N)

8. Cuando se tiene una...