Problema 1:
Joe Cougar vive en Nueva York,
pero proyecta viajar en su automóvil hasta los Ángeles 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, Dallas, San Antonio y Denver. Joe sabe que después de manejar un
día puede llegar a Columbus, Nashville o Louisville. Después de manejar dos
días puede llegar a Kansas City, Omaha o Dalla. 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
la figura siguiente:
Solución:
Joe necesita saber cuál es el
camino más corto entre Nueva York y Los Ángeles.
La determinaremos yendo hacia
atrás.
Clasificamos todas las ciudades en las que Joe puede estar al principio
de n-ésimo día de su viaje como ciudades de la etapa n. por ejemplo, puesto que
Joe solo puede estar en San Antonio o Denver al inicio del cuarto día (el día
1empieza cuando Joe 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á evidentemente 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 ayudara a resolver un problema complejo.
Por lo tanto, empezamos por
determinar la trayectoria más corta a Los Ángeles desde cada ciudad de donde
hay solo 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 solo
quedan 2 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 Ángeles desde cada ciudad que esté
a 3 días de viaje (ciudades de la etapa 2). Encontramos, por último, la
trayectoria más corta a Los Ángeles desde cada ciudad (hay solo 1: Nueva York)
que está a 4 días de viaje.
Con el fin de simplificar la
exposición usamos los números 1, 2,……., 10 dados en la figura anterior para
nombrar las 10 ciudades. Definimos también cij como las millas entre la ciudad i y la ciudad. Por ejemplo,
C35 = 580 son las millas entre Nashville y Kansas City.
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 solo un camino
desde cada ciudad de la etapa 4 hasta
los Ángeles, observamos de inmediato que f4(8)=1030
y la trayectoria 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) de 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. Por ejemplo, para determinar f3 (5) observamos que el camino más corto desde la
ciudad 5 a los Ángeles debe ser uno de los siguientes:
Camino 1:
Ir desde la ciudad 5 a la ciudad 8 y,
luego, tomar el camino más corto desde la ciudad 8 hasta la ciudad 10.
Camino 2:
Ir de la ciudad 5 a la ciudad 9 y, luego, tomar el camino más corto
desde la ciudad 9 hasta la ciudad 10.
La distancia del camino 1 se puede escribir como: C58 +f4 (8) . y la
distancia del camino 2 se podría expresar como C59 +f4 (9). De aquí que la
distancia más corta desde la ciudad 5 hasta la ciudad 10 se podría escribir
como:
El * indica la elección del arco que alcanza a f3 (5)
Por lo tanto, hemos demostrado que el camino más corto desde l ciudad 5 hasta la ciudad 10 es el camino 5-8-10. Obsérvese que para obtenerse este resultado nos apoyamos en lo que sabíamos de f4 (8) y f4(9). De igual modo, para encontrar f3(6) observamos que el camino más corto a Los Ángeles desde la ciudad 6 tiene que empezar por ir a la ciudad 8 o a la 9. Esto da lugar a la ecuación siguiente:
Por lo tanto f3 (5) = 1570 y el camino más
corto desde la ciudad 6 hasta la 10 es el camino 6-8-10.
Para determinar
observamos que:
Por lo
tanto f3 (7) = 1660, y el camino más corto desde la
ciudad 7 a la 10 es la trayectoria 7-9-10.
Cálculos de la etapa 2
Dado que conocemos f3 (5), f3 (6) Y f3(7) es fácil ahora
ir hacia atrás una etapa más y calcular: f2(2), f2(3), f2(4) por lo tanto,
el camino más corto a los Ángeles desde la ciudad 2, ciudad 3 y ciudad 4. Para
ilustrar como se hace este proceso, encontramos el camino más corto (y su
distancia) desde la ciudad 2 hasta la ciudad 10. El camino más corto entre
estas ciudades debe empezar por ir de la ciudad 2 a la ciudad 5, ciudad 6 o
ciudad 7. Una vez que este camino más
corto lleva a la ciudad 5, ciudad 6 o ciudad 7, entonces se debe seguir el
camino más corto desde esa ciudad a los Ángeles. Este razonamiento muestra que
el camino más corto desde la ciudad 2 a la ciudad 10 debe ser uno de los
siguientes:
Camino 1:
Ir desde l ciudad 2
hasta la ciudad 5. Luego seguir el camino más corto desde la ciudad 5 a la
ciudad 10. Una trayectoria de este tipo tiene una distancia total de:
Camino 2:
Ir desde la ciudad 2 a la ciudad 6. Luego
seguir el camino más corto desde la ciudad 6 hasta la ciudad 10. Una
trayectoria de este tipo tiene una
distancia total de:
Camino 3:
Ir desde la ciudad 2 a la ciudad 7. Luego
seguir del camino más corto desde la
ciudad 7 hasta la ciudad 10. Esta trayectoria tiene una distancia total de C27
+ f3(7). Se podría concluir que
Por lo tanto ƒ1 (1)
= 2870, y el camino más corto desde la ciudad 1 hasta la ciudad 10 va desde la
ciudad 1 hasta la ciudad 2 y luego sigue el camino más corto desde la ciudad 2
hasta la ciudad 10. Si verificamos los cálculos de ƒ2 (2) vemos que
la trayectoria más corta desde la ciudad 2 hasta la ciudad 10 es 2 – 5 – 8 –
10. Al trasladar las etiquetas numéricas
A las ciudades reales,
vemos que el camino más corto desde Nueva York
a Los Ángeles pasa por Nueva
York, Columbus, Kansas City, Denver y Los Ángeles. Este camino tiene una nueva
distancia de
f1 (1) =
2870 millas.
CARACTERÍSTICAS DE LAS APLICACIONES DE LA
PROGRAMACIÓN DINÁMICA
Característica 1:
Es posible dividir el
problema en etapas, y se requiere una decisión en cada etapa.
Característica 2:
Cada etapa se relaciona
con una cierta cantidad de etapas.
Característica 3:
La decisión tomada en
cualquier etapa describe el modo en que el estado en la etapa actual se
transforma en el estado en la etapa siguiente.
Característica 4:
Dado el estado actual, la
decisión óptima para cada una de las etapas restantes no tiene que depender de
v los estados ya alcanzados o de las decisiones tomadas previamente.
Característica 5:
Si los estados del
problema se clasifican dentro de uno de T etapas, debe haber una RECURSIÓN que
relacione el costo o la recompensa ganada durante las etapas t, t +1,…..T con
el costo o la recompensa ganada a partir de las etapas t, +1, t +2,…….,T.
La RECURSIÓN formaliza, en esencia, el procedimiento de ir hacia atrás.
Problema 2:
Formulación:
Tablas:
T3:
T2:
T1:
Resultados:
Interpretación:
Finco debe invertir 4000 dolares en la inversión 1, 1000 dolares en la inverrsión 2 y 1000 dolares en la inversión 3
