Programación Dinamica

Programación dinámica

Historia: El término Programación Dinámica fue utilizado originalmente en los 1940’s por Richard Bellman para describir el proceso de resolver problemas donde se necesita encontrar las mejores decisiones una tras otra. Para 1953, el refinó esto a su significado moderno, el cual se refiere específicamente a anidar pequeños problemas de decisión dentro de grandesdecisiones, luego de esto el campo fue reconocido por la lEEE como un tópico de análisis de sistemas de ingeniería.
La contribución de Bellman es recordada en el nombre de la ecuación de Bellman, un resultado central de programación dinámica que replantea un problema de optimización en forma recursiva. Originalmente la palabra “programación” en “programación dinámica” no tenía conexión con la programaciónde computadoras y en cambio venía del término “programación matemática”.
Sin embargo, actualmente muchos problemas de optimización son mejor resueltos escribiendo programas de computadoras que implementa un algoritmo de programación dinámica, lo cual resulta mejor que llevar a cabo cientos de cálculos a mano.

Concepto: La programación dinámica es un enfoque general para la solución deproblemas en los que es necesario tomar decisiones en etapas 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óndinámica no sigue una forma estándar. Así, para cada 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 etapaantecesora. El análisis de la primera etapa finaliza con la obtención del óptimo del problema. Los problemas de programación dinámica poseen las siguientes características:
• El problema se puede dividir en etapas, donde cada una de ellas requiere una política de decisión.
• Cada etapa tiene cierto número de estados asociados a su inicio.
• El efecto de cada política es transformar el estadoactual en un estado asociado con el inicio de la segunda etapa.
• El procedimiento de solución está diseñado para encontrar una política óptima para manejar el problema completo.
• Una política óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores.
• El proceso de solución comienza cuando se determina la política óptima para la última etapa.
• Se disponede una política recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n+1.
• Cuando se usa esta etapa recursiva, el procedimiento de solución comienza al final y se mueve etapa por etapa hacia atrás hasta que encuentre la política optima desde la etapa inicial.

Diferencias con la programación lineal: La programación dinámica se diferencia de laprogramación lineal porque en contraste con la programación lineal, no se cuenta con una formulación matemática estándar para dar solución a los problemas de Programación dinámica, en cambio se utiliza un enfoque de tipo general para la solución de problemas y las ecuaciones específicas que se usan se deben desarrollar para que representen cada situación individual, además se necesita un cierto gradode creatividad y un buen conocimiento de la estructura general de los problemas de Programación Dinámica para reconocer cuándo y cómo se puede resolver un problema por medio de estos procedimientos.

Comparación entre Programación Dinámica y Recursiva: La diferencia esencial entre Recursión y Programación dinámica es que la última guarda los resultados intermedios mientras la primera no lo...