La programación dinámica es una técnica matemática que se utiliza para la solución de problemas matemáticos seleccionados, en los cuales se toma una serie de decisiones en forma secuencial. Proporciona un procedimiento sistemático para encontrar la combinación de decisiones que maximice la efectividad total, al descomponer el problema en etapas, las que pueden ser completadas por una o más formas (estados), y enlazando cada etapa a través de cálculos recursivos.
Entendemos por etapa cómo la parte del problema que posee un conjunto de alternativas mutuamente excluyentes, de las cuales se seleccionará la mejor alternativa, y por estado cómo el que refleja la condición o estado de las restricciones que enlazan las etapas. Representa la “liga” entre etapas de tal manera que cuando cada etapa se optimiza por separado la decisión resultante es automáticamente factible para el problema completo.
La programación dinámica no cuenta con una formulación matemática estándar, sino que se trata de un enfoque de tipo general para la solución de problemas, y las ecuaciones específicas que se usan se deben desarrollar para que representen cada situación individual. Comúnmente resuelve el problema por etapas, en donde cada etapa interviene exactamente una variable de optimización (u optimizadora)
La teoría unificadora fundamental de la programación dinámica es el Principio de Optimalidad, que nos indica básicamente como se puede resolver un problema adecuadamente descompuesto en etapas utilizando cálculos recursivos. “Una política óptima tiene la propiedad de que, independientemente de las decisiones tomadas para llegar a un estado particular, en una etapa particular, las decisiones restantes deben constituir una política óptima para abandonar ese estado”.
Para resolver problemas de programación dinámica se necesita un grado de creatividad y un buen conocimiento de la estructura general de los problemas de programación dinámica para reconocer cuando un problema se puede resolver por medio de estos procedimientos y como esto se puede llevar a cabo.
Los problemas de programación dinámica tienen las siguientes características:
-
El problema se puede dividir en etapas que requieren una política de decisión en cada una.
-
Cada etapa tiene cierto número de estados asociados a ella.
-
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.
-
El procedimiento de solución está diseñado para encontrar una política óptima para el problema completo.
-
Dado un estado actual, una política óptima para las etapas restantes es independiente de la política adoptada en las etapas anteriores (principio de optimalidad).
-
El procedimiento de solución se inicia al encontrar la política óptima para la última etapa.
-
Se dispone de una relación recursiva que identifica la política optima par la etapa n dada la política óptima para la etapa (n+1).
La recursividad tiene 2 formas de plantear la fórmula en los problemas de programación dinámica; una es la recursividad de Retroceso dónde el problema se resuelva partiendo de la última etapa hacia la primera, y la otra es la recursividad de Avance dónde el problema se resuelve partiendo de la primera etapa hacia la última.
Las formulaciones de avance y retroceso son en realidad equivalentes en términos de cálculo. Sin embargo, hay situaciones donde habría alguna diferencia, en la eficiencia del cálculo, según la formulación que se utilice. Esto sucede en particular en problemas donde intervine la toma de decisiones conforme transcurre el tiempo. En esto caso las etapas se designan con base en el estricto orden cronológico de los periodos que ellas representan y la eficiencia de los cálculos dependerá de si se utiliza formulación de avance o retroceso.
Un ejemplo muy representativo de la programación dinámica es el del agente viajero:
Un caza fortunas de Missouri decide irse al oeste a unirse a la fiebre del oro en California. Tiene que hacer el viaje en diligencia a través de territorios sin ley donde existían serios peligros de ser atacados por merodeadores. Aun cuando su punto de partida y destino eran fijos, tenía muchas opciones en cuanto a que estados debía elegir como puntos intermedios. Se desea estimar la ruta más segura, como el costo de la póliza para cualquier jornada de la diligencia está basada en una evaluación de seguridad del recorrido, la ruta más segura debe ser aquella que tenga el costo total más barato. ¿Cuál es la ruta que minimiza el costo total de la póliza?
La solución sería que los cálculos se realizan en etapas dividiendo el problema en subproblemas. Después, se considera por separado cada subproblema con el fin de reducir el número de operaciones de cálculo. Se comienza con una pequeña porción del problema original y se encuentra la solución óptima. Luego, se agranda gradualmente el problema y se encuentra la solución óptima actual a partir de la que le precede, hasta resolver el problema original completo. En cada problema aumentado se puede encontrar la solución óptima tomando en cuenta los resultados obtenidos en la interacción anterior.
En el procedimiento de solución para este caso se empleará el desarrollo del problema con un recorrido hacia atrás. Cuando el cazafortunas tiene una sola etapa por recorrer (n=4), su ruta de ahí en adelante esta perfectamente determinada por su estado actual (ya sea H o I) y su destino final, x4 = J, de manera que la ruta para esta última jornada en diligencias es s J La solución al problema es: f * 4 (H) = 3, f * 4 (I) = 4.
Cuando se tienen dos etapas por recorrer (n=3), se analiza de la siguiente manera: Supóngase que se encuentra en el estado F, entonces como se ve en la figura, se debe ir al estado H ó al estado I. a un costo de CF, H = 6 ó CF, I =3. Si se elige el estado H, el costo adicional mínimo al llegar ahí es 3, por tanto, el costo de decisión es 6+3=9, de igual manera si se elige el estado I, el costo total es 3+4=7 que es menor por lo tanto se escogerá el estado I.
Se trabaja de manera similar con los otros dos estados posibles s=E y s=G, cuando quedan dos jornadas por viajar, los resultados son: f * 3 (E) = 4, f * 3 (F) = 7, f * 3 (G) = 6.
La solución para el problema de tres etapas (n=2) se obtiene en forma parecida. Por ejemplo, supóngase que el agente se encuentra en el estado C, como se muestra el diagrama. Ahora deberá ir al estado E, F ó G con un costo inmediato de CC, E =3 ó CC, F =2 ó CC, G =4, respectivamente.
Al llegar aquí el costo adicional mínimo hasta llegar a su destino esta dado de la siguiente manera: x2 = E f2 (C,E) = cC,E + f* 3 (E) = 3 + 4 = 7
x2 = F f2 (C,F) = cC,F + f* 3 (F) = 2 + 7 = 9
x2 = G f2 (C,G) = cC,G + f* 3 (G) = 4 + 6 = 10
El mínimo de estos tres números es 7, por lo que el costo mínimo desde el estado C al final es f * 2 (C) = 7, y el destino inmediato debe ser x * 2 = E. Se realizan cálculos similares cuando se comienza desde el estado B ó D. Los resultados son: f * 2 (B) = 11 f* 2 (C) = 7,
f * 2 (D) = 8
Si se pasa al problema de cuatro etapas (n=1), los cálculos son parecidos a los que se acaban de mostrar para el problema de tres etapas (n=2), excepto que ahora hay solo un inicio posible, s=A , como se muestra el diagrama.
Los resultados se resumen de la siguiente manera:
x1 = B f1(A,B) = cA,B + f* 2 (B) = 2 + 11 = 13
x1 = C f1 (A,C) = cA,C + f* 2 (C) = 4 + 7 = 11
x1 = D f1 (A,D) = cA,D + f* 2 (D) = 3 + 8 = 11
Como el mínimo costo es 11, por tanto, los caminos pueden ser C ó D. En este punto se puede identificar la solución óptima. Los resultados indican los caminos óptimos a seguir: A D E H J ó A D F I J, las dos tienen un costo total de 11
En conclusión, un problema de optimización que se pueda dividir en etapas y que sea dinámico en el tiempo puede resolverse por programación dinámica, las soluciones se pueden ver de manera parcial y si es posible, se validan los resultados usando otros métodos de solución como programación lineal, no lineal, entera o teoría de redes.
Referencias:
-
Bertsekas,D.P., "Dynamic Programming; Deterministic and Stochastic Models"Academic Press, 1987.
-
Dreyfus S.E. y Law A.M., "The Art and Theory of Dynamic Programming", Academic Press, 1977.
-
Hiller, F. S. “Introducción a la Investigación de Operaciones”. 2008.
-
Taha, H. A. “Investigación de Operaciones”. 2005.