programacion dinamica

Universidad de Oriente
Núcleo Anzoátegui
Escuela de Ingeniería y Ciencias Aplicadas
Departamento de Computación y Sistemas
Modelos de Operaciones 1

PROGRAMACION DINAMICA



Barcelona, Marzo del 2014.
PROGRAMACIÓN DINÁMICA
La Programación Dinámica esun método de optimización de extraordinaria versatilidad. Si bien fue desarrollada especialmente para la resolución de problemas en Procesos de Decisión en Múltiples Pasos, diferentes investigaciones han mostrado que las mismas ideas pueden utilizarse en otro tip o de problemas de matemática aplica- da, e incluso pueden ser útiles en el planteo de algunas cuestiones teóricas. Habiendo surgido enlos inicios de la época de las computadoras, la Programación Dinámica fue, además, concebida con un ojo puesto en esta potente herramienta. La Ecuación Funcional que se obtiene, para cada problema, a través del uso del Principio de Optimalidad de Bellman permite, con mayor o menor esfuerzo dependiendo del caso, establecer una recurrencia que es, en sí misma, un algoritmo que resuelve el problema encuestión.
CARACTERISTICAS
Para que el problema sea resuelto con programación dinámica, debe cumplirse con ciertas características:
Naturaleza secuencial de las decisiones: el problema puede ser dividido en etapas.
Cada etapa tiene un número de estados asociados a ella.
La decisión óptima de cada etapa depende solo del estado actual y no de las decisiones anteriores.
La decisión tomada en unaetapa determina cual será el estado de la siguiente etapa.
IMPORTANCIA.
Este algoritmo evita calcular dos veces la misma información, manteniendo una tabla de resultados conocidos, la cual se va llenando a medida que se resuelven los sub-casos.Laprogramación dinámica se aplica no solo por razones de eficiencia, sino porque permite resolver de manera eficiente problemas que no se pueden resolverpor otras metodologías
PRINCIPIO DE OPTIMALIDAD DE BELLMAN
La resolución del modelo en forma óptima mediante programación dinámica está garantizada siempre y cuando las soluciones del problema verifiquen el principio de optimalizad de Bellman que dice:
“Una solución óptima tiene la propiedad de que cualquiera que sea el estado inicial y las decisiones iniciales, las decisiones para las etapasposteriores deben constituir una política optima respecto al estado resultante de la primera decisión.”
En otras palabras, las decisiones involucradas desde una etapa en adelante solo dependen del estado inicial de la etapa y no de las decisiones previas.
ESTRUCTURA BASICA DE PROGRAMACION DINAMICA DETERMINISTICA
Los problemas de programación dinámica se pueden interpretar en términos deredes, donde cada nodo corresponde a un estado, y la red estará formada por columnas de nodos, donde cada columna corresponde a una etapa. El flujo que sale de un nodo solo puede ir a un nodo a su derecha, y que está en la siguiente columna (estado). El valor asignado a cada rama que une dos nodos se puede interpretar como la contribución a la función objetivo que se obtiene al pasar por esos estados.Y el problema es encontrar la ruta con el valor asociado mínimo, o bien con el valor asociado máximo. El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para las decisiones de la política optima en cada etapa para uno de los estados posibles. Las tablas de cálculos de cada etapa son útiles para casos en que se tiene undeterminado estado que no está en la ruta óptima y se desea la ruta óptima desde ese estado donde se está.
Se puede describir un diagrama como la siguiente figura:
SnSn+1EtapanValor: fn(Sn,Xn)XnContribución de XnEtapan+1 fn+1(Sn+1)

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