Programación Dinámica

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Instituto Universitario Politécnico Santiago Mariño
Extensión – San Cristóbal

Elaborado por:
Jorge Lopez
C.I : 20517149

San Cristóbal, Agosto 2012
Programación Dinámica
La programación dinámica es un enfoque general para la solución de problemas en los que es necesario tomar decisiones enetapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará en el futuro (denominadas estados), y a las decisiones que se plantearán en el futuro.
Conviene resaltar que a diferencia de la programación lineal, el modelado de problemas de programación dinámica no sigue una forma estándar. Así, paracada problema será necesario especificar cada uno de los componentes que caracterizan un problema de programación dinámica.
El procedimiento general de resolución de estas situaciones se divide en el análisis recursivo de cada una de las etapas del problema, en orden inverso, es decir comenzando por la última y pasando en cada iteración a la etapa antecesora. El análisis de la primera etapa finalizacon la obtención del óptimo del problema
Modelos de Programación Dinámica
Existen tres modelos diferentes manejados por WINQSB.
* Problema de la diligencia (Stagecoach Problem)
* Problema de la mochila (Snapsack Problem)
* Programación de producción e inventarios (Production and Inventory Scheduling.
Forma
La forma general de las soluciones desarrolladas mediante programacióndinámica requiere de los siguientes pasos:
1. planteamiento de la solución, mediante una serie de decisiones que garanticen que la solución será óptima.
2. Encontrar una solución recursiva de la definición.
3. Calcular la solución teniendo en cuenta una tabla en la que se almacenen soluciones a problemas parciales para su reutilización y así evitar el nuevo cálculo.
4. Encontrar lasolución óptima utilizando la información previamente calculada y almacenada en las tablas.

Características de un Problema de Programación Dinámica
Para que un problema pueda ser resuelto con la técnica de programación dinámica, debe cumplir con ciertas características:
* Naturaleza secuencial de las decisiones: El problema puede ser dividido en etapas.
* Cada etapa tiene un número deestados 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 una etapa determina cual será el estado de la etapa siguiente.
En síntesis, la política óptima desde un estado s de la etapa k a la etapa final está constituida por una decisión que transforma s en un estado s0 de la etapa k +1 y por lapolítica óptima desde el estado s0 hasta la etapa final.

Resolución de un Problema de Programación Dinámica
Para resolver un problema de programación dinámica debemos al menos:
Identificación De Etapas, Estados Y Variable De Decisión: |
  Cada etapa debe tener asociado una o más decisiones (problema de optimización), cuya dependencia de las decisiones anteriores está dada exclusivamente por las variables de estado.   Cada estado debe contener toda la información relevante para la toma de decisión asociada al periodo.

Las variables de decisión son aquellas sobre las cuales debemos definir su valor de modo de optimizar el beneficio acumulado y modificar el estado de la próxima etapa.
|
Descripción De Ecuaciones De Recurrencia: Nos deben indicar como se acumula la función debeneficios a optimizar (función objetivo) y como varían las funciones de estado de una etapa a otra.
RESOLUCIÓN Debemos optimizar cada sub problema por etapas en función de los resultados de la resolución del sub problema siguiente. Notar que las para que las recurrencias estén bien definidas requerimos de condiciones de borde.
Ejercicio:
La familia Simpson va a salir de vacaciones desde su ciudad...