Programación dinámica

1.- La programación Dinámica es una técnica de resolución que encuentra aplicación en numerosos problemas de optimización. Principalmente se abordan aquellos problemas en el que las solucionesfactibles se pueden descomponer en una secuencia de elementos (caminos en un grafo, series de decisiones, etc.), y cuya función objetivo satisface cierta condición de separabilidad y monótona. No obstante,la programación dinámica también encuentra aplicación en la búsqueda de otras estructuras óptima (árboles óptimos) y en la realización eficiente de ciertos cálculos de naturaleza recursiva.

Laprogramación dinámica consiste en una técnica que permite determinar de manera eficiente las decisiones que optimizan el comportamiento de un sistema que evoluciona a lo largo de una serie de etapas. Enotras palabras, trata de encontrar la secuencia de decisiones que optimiza el comportamiento de un proceso de varias etapas.

Los elementos para definir un Problema de Programación Dinámica son:* Etapas (n): Son el periodo de tiempo, lugar, fase o situación en donde se produce un cambio debido a una decisión. Sólo se puede tomar una decisión en cada etapa.
* Estados en: Muestran lasituación actual del sistema cuando nos encontramos en la etapa n
* Variables de decisión xn: Hacen referencia a la toma de decisiones que se produce en una etapa y que provoca un cambio en el estadoactual del sistema.
* Función recurrente fn: Refleja el comportamiento del sistema en función de los estados y las variables de decisión cada etapa tiene su función recurrente, se representa dela sgt forma:
fn(en,xn)


Resolución de un problema de Programación lineal.
1. Identificación de etapas, estados y variable de decisión:
* Cada etapa debe tener asociado una o másdecisiones (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...