Programación Dinámica
Enviado por vivianajo • 6 de Julio de 2015 • 579 Palabras (3 Páginas) • 207 Visitas
Programación Dinámica
La Programación Dinámica fue desarrollada por Richard Belman y G. B. Dantzing. Sus importantes contribuciones sobre esta técnica cuantitativa de toma de decisiones se publicaron en 1957.
Inicialmente a la Programación Dinámica se le denomino Programación Lineal Estocástica o Problema de Programación Lineal con Incertidumbre.
La Programación dinámica determina la solución optima de un problema de n variables descomponiéndola en n etapas, cada etapa incluye un subproblema de una sola variable. La principal contribución de la PD es el principio de optimizad, el cual establece que una política optima consiste de subpolíticas optimas, un marco de referencia para descomponer el problema en etapas.
La PD probabilística se origina en especial en el tratamiento de modelos estocásticos de inventario y en los procesos markovianos de decisión.
La Programación Dinámica obtiene soluciones con un avance en reversa, desde el final de un problema hacia el principio con lo que un problema grande y engorroso se convierte en una seri de problemas mas pequeños y mas tratables.
La Programación Dinámica se puede definir como una técnica matemática útil que resuelve una serie de decisiones secuenciales, a cada una de las cuales afecta las decisiones futuras. Proporciona un procedimiento sistemático para determinar la combinación de decisiones que maximiza la efectividad total.
Las características de la programación dinámica se emplean para formular e identificar la estructura de los problemas de este tipo.
A continuación se presentarán estas características básicas que distinguen a los problemas de programación dinámica.
1. El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas. En muchos problemas de programación dinámica, la etapa es la cantidad de tiempo que pasa desde el inicio del problema, en ciertos casos no se necesitan decisiones en cada etapa.
2. Cada etapa tiene un cierto número de estados asociados a ella. Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.
3. Cada etapa tiene un cierto número de estados asociados a ella. Por estado se entiende la información que se necesita en cualquier etapa para tomar una decisión óptima.
4. El efecto de la política de decisión en cada etapa es transformar el estado actual en un estado asociado con la siguiente etapa (tal vez de acuerdo a una distribución de probabilidad).
5. El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo, es decir, una receta para las decisiones de la política óptima en cada etapa para cada uno de los estados posibles.
6. Dado el estado actual, una política óptima para las etapas restantes es independiente de la política
...