Programación dinámica

Programación dinámica
La programación dinámica es una técnica matemática útil en la toma de una serie de decisiones interrelacionadas. Proporciona un procedimiento sistemático para determinar la combinación óptima de decisiones.
En contraste con la programación lineal, no cuenta con una formulación matemática estándar para el problema de asignación dinámica, si no que se trata de un enfoque detipo general [ara la solución de problemas, y las ecuaciones especificas que se usan se deben desarrollar para que representen cada situación individual. Entonces se necesita cierto grado de creatividad y un buen conocimiento de la estructura general de los problemas de programación dinámica para reconocer cuando y como se puede resolver un problema por medio de estos procedimientos.
Laprogramación dinámica se utiliza tanto en problemas lineales como no lineales.
Problema de la diligencia
Un cazafortunas desea ir de Missouri a California en una diligencia, y quiere viajar de la forma más segura posible. Tiene los puntos de salida y destino conocidos, pero tiene múltiples opciones para viajar a través del territorio. Se entera de la posibilidad de adquirir seguro de vida como pasajerode la diligencia.
Diagrama:

¿Cuál es la ruta que minimiza el costo total de la póliza de seguro?
Las alternativas de solución son:
1.- Enumeración exhaustiva: enumerar todas las rutas posibles, calcular su costo y elegir la de menor valor. En total son 18.
2.- Elegir la ruta más barata en cada etapa. Esta solución no conduce al óptimo global. Un pequeño sacrificio en una etapa puedepermitir mayores ahorros más adelante.
3.- Programación dinámica: La programación dinámica comienza con una pequeña porción del problema original y encuentra la solución óptima para este problema pequeño. Después agranda gradualmente el problema y encuentra la solución óptima actual a partir de la que le precede, hasta resolver el problema original completo. En el problema de la diligencia secomienza con el problema sencillo en el que el agente casi ha llegado casi al final de su viaje y solo tiene una etapa más por recorrer. La solución óptima para este problema es ir del estado actual a su destino final (J).
Formulación: Sea Xn (n = 1, 2, 3,4) las variables que representan el destino inmediato en la etapa n.
Luego la ruta seleccionada será:
A X1 X2 X3 X4
Donde X4= J
Sea ƒn (S, Xn) el costo total de la mejor política global para las etapas restantes, dado que el agente se encuentra en el estado S, listo para iniciar la etapa n y se dirige a Xn como destino inmediato.
Dados S y n , sea Xn* el valor de Xn (no necesariamente único), que minimiza fn (S , Xn) , y sea fn *(S) el valor mínimo correspondiente de fn (S, Xn) entonces:
ƒn (S, Xn) = Costo inmediato(etapa n) + Mínimo costo futuro (etapa n + 1 en adelante)= Cs,xn + ƒn+1* (Xn)
Costo óptimo acumulado
Costos por ir de la ciudad i al destino j

Procedimiento de solución hacia atrás.
Etapa n=4: Como el destino final (estado J) se alcanza al terminar la etapa 4, entonces
f5*(J) = 0
El objetivo es hallar f1*(A) y su ruta correspondiente. Cuando el cazafortunas tiene sólo una etapa porrecorrer (n=4), su ruta de ahí en adelante, estará determinada por el estado actual (H o I) y su destino final X4 = J La ruta será: S J donde S= H o

Como f4*= f4(s,J)= Cs,J la solución inmediata para n= 4 es

Etapa n=3: f3*E=4 y X3 *=3 en general en la etapa 3 se tiene:

La solución para la segunda etapa cuando quedan tres jornadas por recorrer se obtiene en forma parecida. En este caso f2s,x2= cs x2+ f3*(X2) por ejemplo, suponga que el cazafortunas se encuentra en el estado C.

Ahora deberá ir al estado E, F o G con sus respectivos costos. A continuación se presentan los tres resultados del diagrama anterior:
x2=E: f2C,E=3+4=7
x2=F: f2C,F=2+7=9
x2=G: f2C,G=4+6=10
El mínimo de estos tres números es 7 por tanto es el costo total mínimo del estado C, entonces el destino...