Programacion dinamica

La programación dinámica es un método para reducir el tiempo de ejecución de un algoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, es decir, es un enfoque general para la solución de problemas en los que es necesario tomar decisiones en etapas sucesivas.

Su inicio y desarrollo básico se debe a Richard Bellman al principio de los cincuenta. La trascendencia de esta metodología no se limita a la Investigación Operativa, sino que es también de gran importancia en la Teoría del Control Óptimo, en estrecha relación con el principio del máximo de Pontryagin. En lo que aquí nos concierne, el desarrollo de la Programación Dinámica se ha visto limitado en su aplicabilidad concreta debido a la complejidad computacional que le acompaña, tanto debido a la cardinalidad del espacio de estado como al número de períodos que intervienen. En este sentido, el trabajo de Larson ha colaborado a su tratamiento, pero muchos autores aún consideran a la Programación Dinámica como un punto de vista conceptual y un bagaje teórico para el análisis de problemas; y no como un método -o conjunto de ellos implantable en algoritmos de tipo general. En esta dirección, los trabajos de Denardo, identificando la estructura de los procesos de decisiones secuenciales, suponen un avance para establecerlos.

Programación dinámica publicada en el año 1957, bellman era un matemático que trabajaba en la RAND corporation, un científico espacial en el sentido literal del término. Había inventado un conjunto de técnicas para optimizar las decisiones cuando había que tomar un gran número sucesivo en medio de circunstancias cambiantes

...