Programacion dinamica

Programación dinámica

Vamos a considerar problemas para los cuales es posible identificar cierto número de pasos secuencial es que llamaremos “proceso de decisión en n etapas”
Las “decisiones”son las opciones que tenemos para completar las etapas.
Una secuencia de decisiones se denomina “política”.
La condición del proceso en una etapa dada se denomina “estado” en esa etapa.
Cuando setoma una decisión se produce una transición del estado actual a otro estado asociado con la etapa siguiente.
Por ahora nos ocuparemos de la programación dinámica finita si tiene n etapas finitas y silos estados asociados con cada etapa también son finitos. Es determinística si el resultado de cada decisión se conoce exactamente.
El objetivo es determinar una “política óptima”.
Desde el punto devista matemático podemos expresar que:
Se debe optimizar Z = f1(x1) + f2(x2) + ... + fn(xn)
sujeto a x1 + x2 + ... + xn £ b
donde todas las variables son enteras y no negativas.
Las funcionesf1(x1), f2(x2),... son funcionas (no lineales) de una sola variable y b es un entero no negativo. Por ejemplo: la etapa 1 comprende la especificación de la variable x1 con la contribución f1(x1) a ladeterminación del óptimo. La variable x1 se denomina “variable de decisión”.
La programación dinámica parte del principio de optimalidad enunciado por Richard Bellman: “Una política es óptima si, en unperíodo dado, cualesquiera que sean las decisiones precedentes, las decisiones que se tomen en adelante constituyen una política óptima con respecto al resultado de las decisiones precedentes”.
Dichode otro modo: “Toda subpolítica extraída de una política óptima es en sí óptima” o como corolario: Entre el conjunto de políticas que contienen a una subpolítica dada (óptima o no) la mejor es aquellaque se obtiene al completar la subpolítica dada con una subpolítica óptima.
Para aplicar el principio de optimalidad de Bellman comencemos con la última etapa del proceso de n etapas y determinemos...