Programacion Dinamica

1 PROGRAMACIÓN DINÁMICA
Es una técnica matemática útil para la toma de decisiones secuenciales 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 del problema de programación dinámica, sino que es un enfoque general para solucionar problemas;las ecuaciones específicas que se usan deben ajustarse a la situación particular. Por tanto, es necesario cierto grado de creatividad y un buen conocimiento de la estructura de los problemas de programación dinámica para reconocer cuándo y cómo un problema puede ser resuelto por medio de estos procedimientos. Ridhard Bellman y G. B. Dantzing fueron los creadores de la programación dinámica en ladécada de 1950.

Ejemplo1 Joe Cougar vive en Nueva York, pero proyecta viajar en su automóvil hasta Los Angeles en busca de fama y fortuna. Los fondos de Joe son limitados, así que decide pasar cada noche de su viaje en la casa de un amigo. Joe tiene amigos en Columbus, Nashville, Louisville, Kansas City, Omaha, Dallas, San Antonio y Denver. Joe sabe que después de manejar un día puede llegar aColumbus, Nashville o Louisville. Después de manejar dos días puede llegar a Kansas City, Omaha o Dallas. Después de tres días de viaje puede llegar a San Antonio o Denver. Luego de cuatro días de manejar puede llegar finalmente a Los Ángeles. Para minimizar la cantidad de millas recorridas, ¿dónde debe Joe pasar cada noche del viaje? Las millas reales por carretera entre las ciudades se dan en lafigura 1.

Solución Joe necesita saber cuál es el camino más corto entre Nueva York y Los Angeles de la figura 1. La determinaremos yendo hacia atrás. Clasificamos todas las ciudades en las que Joe puede estar al principio del n-ésimo día de su viaje como ciudades de la etapa n. Por ejemplo, puesto que Joe sólo puede estar en San Antonio o Denver al inicio del cuarto día (el día 1 empieza cuandoJoe sale de Nueva York), entonces clasificamos San Antonio y Denver como ciudades de la etapa 4. La razón de clasificar las ciudades de acuerdo con etapas será evidente más adelante. La idea de trabajar hacia atrás implica que debemos empezar por resolver un problema fácil que con el tiempo nos ayudará a resolver un problema complejo. Por lo tanto, empezamos por determinar la trayectoria más cortaa Los Ángeles desde cada ciudad de donde

hay sólo un día de viaje en automóvil (ciudades de la etapa 4). Luego usamos esta información para encontrar el camino más corto hasta Los Ángeles desde cada ciudad de donde sólo quedan dos días de manejo (ciudades de la etapa 3). Con esta información ya somos capaces de hallar el camino más corto a Los Angeles desde cada ciudad que esté a tres días deviaje (ciudades de la etapa 2). Encontramos, por último, la trayectoria más corta a Los Angeles desde cada ciudad (hay sólo una: Nueva York) que está a cuatro días de viaje. Con el fin de simplificar la exposición usamos los números 1.2,...,10 dados en la figura 1 para nombrar las 10 ciudades. Definimos también cij como las millas entre la ciudad i y la ciudad j. Por ejemplo, c35 = 580 son lasmillas entre Nashville y Kansas City. Hagamos ft(i) la distancia del camino más corto desde la ciudad i a Los Ángeles, dado que la ciudad i es una ciudad de la etapa t. Cálculos de la etapa 4 Primero determinamos el camino más corto a Los Ángeles desde cada ciudad de la etapa 4. Como hay sólo un camino desde cada ciudad de la etapa 4 hasta Los Ángeles, observamos de inmediato que f4(8) = 1030, y latrayectoria más corta desde Denver hasta Los Ángeles es sencillamente el único camino desde Denver a Los Ángeles. De manera similar, f4(9) = 1390, que es el camino más corto (y el único) desde San Antonio hasta Los Ángeles. Cálculos de la etapa 3 Ahora vamos hacia atrás una etapa (hasta las ciudades de la etapa 3) y encontramos el camino más corto a Los Ángeles desde cada ciudad de la etapa 3....