Programacion Diamica

Final del formulario
CARACTERISTICAS GENERALES DE LOS PROBLEMAS DE PROGRAMACION DINAMICA.
El problema de la diligencia es un prototipo literal de los problemas de programación dinámica. Por tantouna manera de reconocer una situación que se puede formular como un problema de programación dinámica es poder identificar una estructura análoga a la del problema de la diligencia.
CARACTERISTICASBASICAS:
1.- El problema se puede dividir en etapas que requieren una política de decisión en cada una de ellas.
2.- Cada etapa tiene cierto número de estados asociados con su inicio. Los estados sonlas distintas condiciones posibles en las que se puede encontrar el sistema en cada etapa del problema.
3.- El efecto de la política de decisión en cada etapa es transformar el estado actual en unestado asociado con el inicio de la siguiente etapa.
4.- El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo.
5.- Dado el estado actual, unapolítica óptima para las etapas restantes es independiente de la política adoptada en etapas anteriores. Este es el principio de optimalidad para programación dinámica.
6.- El procedimiento de solución seinicia al encontrar la política óptima para la última etapa.

7.- Se dispone de una relación recursiva que identifica la política óptima para la etapa n, dada la política óptima para la etapa n+1.
Laforma precisa de relación recursiva difiere de un problema a otro de programación dinámica, pero usaremos una notación análoga a la siguiente:
N = número de etapas.
n = etiqueta para la etapaactual ( n = 1,2,…,N)
sn = estado actual para la etapa n
xn = variable de decisión para la etapa n
xn* = valor óptimo de xn (dado sn)
fn(sn,xn) = contribución a la función objetivo de las etapas n,n+1,…,N, si el sistema se encuentra en el estado sn en la etapa n, la decisión inmediata es xn y en adelante se toman decisiones óptimas.
fn*(sn) = fn(sn,xn*)
La relación recursiva siempre tendrá la...