Programacion dinamica

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 en etapas sucesivas. Las decisiones tomadas en una etapacondicionan 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í, para cada problema será necesario especificar cada unode 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 delproblema, 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 finaliza con la obtención del óptimo del problema.Características:
• Método de optimización para resolver problemas que involucran decisiones secuenciales. Una decisión tomada en una etapa afectará los estados del problema y las posibles decisionesen la etapa siguiente.
• No existe un formato estándar, sino más bien se trata de una forma general de resolver este tipo de problemas.
• Una serie de estados agrupados en etapas, de cadaetapa a la siguiente ocurre una transformación la cual depende de mi decisión.
• Los posibles estados en cada etapa, si son finitos o enumerables, los puedo representar como Nodos.
• Lastransformaciones que me llevan a cada estado posible en la siguiente etapa a partir de cada estado actual los puedo representar como arcos.
• El problema se puede dividir en etapas, con una decisiónxt que se debe tomar en cada etapa.
• Existe un cierto número de estados “s” asociados a cada etapa “t”, y la decisión realizada en una etapa afecta el estado del sistema en la siguiente etapa....