Programacion Dinamica

Índice

Reseña Histórica………………………………………………………………………………………………………….
La Programación Dinámica. ……………………………………………………………………………………….
Cuando Aplicar……………………………………………………………………………………………………………
Principio de Optimalidad de la Programación Dinámica o de Bellman ………………….….…
Procesos de Decisión de “n” Etapas. ……………………………………………………………………….…
Relación Recursiva (hacia atrás)…………………………………………………………………………………
DP hacia atrás (backward DP) ………………………………………………………………………………….…
DP hacia adelante (forward DP) ……………………………………………………………………………….…
Programación Dinámica en contraste con la Programación Lineal………………………….….
Ejemplos
* Problema del viajero o de la diligencia…………………………………………….
* Problema de la Mochila……………………………………………………………………
* Programación de Producción e Inventarios………………………………………
Modelo Matemático.…………………………………………………………………………………………………..
La Formulación con Programación Dinámica. ………………………………………………………………
Resolución de un Problema de Programación Dinámica. ………………………………………………
Tipos de programación dinámica…………………………………………………………………………………..
* Programación dinámica homogénea y no homogénea. …………………….
* Programación dinámica determinista y aleatoria……………………………….
Conclusión…………………………………………………………………………………………………………………….Bibliografía…………………………………………………………………………………………………………………...


Historia
La primera gran disciplina que surgió a partir del abordaje matemático de los problemas específicos de la Segunda Guerra Mundial fue, seguramente, la Investigación Operativa1. El término Operations Research fue utilizado por primera vez en Inglaterra, en 1941.

Rápidamente se hizo evidente que las mismas técnicas utilizadas en el ámbito militar podían servir en otras áreas de aplicación. En losaños posteriores a la Guerra se abrieron nuevos temas de investigación y se plantearon nuevos problemas, que fueron abordados desde una perspectiva matemática. Entre estos nuevos temas se encontraba la teoría de los Procesos de Decisión en Múltiples Pasos, que Richard Bellman (1920 - 1984) abordó alrededor de 1952, y para los cuales fue pensada originalmente la Programación Dinámica.
Después dedesarrollar el método en el área específica de los problemas de decisión discretos, Bellman y sus colaboradores se dedicaron a la ardua tarea de formular diferentes problemas en los términos de la Programación Dinámica. Como resultado de esta labor, encontraron que las ideas centrales del método, en particular, el Principio de Optimalidad, podían ser aplicadas satisfactoriamente en muchos de losproblemas abordados. Descubrieron también las limitaciones de esta técnica y hallaron modos de sobreponerse a ellas, para algunos problemas puntuales.
La Programación Dinámica es, hoy en día, un recurso imprescindible de Matemática Aplicada y, también, una importante herramienta teórica.

La Programación Dinámica
La programación dinámica es un enfoque general para la solución de problemas en losque es necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan la evolución futura del sistema.
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 anterior.

¿Cuando Aplicar?
*Existe problemas cuyas soluciones pueden ser expresadas recursivamente. No obstante, el tiempo de ejecución de la solución recursiva, es de orden exponencial y por tanto es muy difícil y costoso implementarlo pero puede mejorarse mediante la Programación Dinámica.
* En el diseño Divide y Vencerás se basa en resolver un problema dividiendo en subproblemas independientes, los cuales seresolvían de manera recursiva para combinar finalmente las soluciones y así resolver el problema original.
* La Programación Dinámica consiste en resolver los subproblemas una sola vez, guardando sus soluciones en una tabla para su futura utilización....