RUTA MAS CORTA

Después de que ya entendimos el algoritmo de DIJKSTRA para resolver problemas de ruta más corta, ahora veamos algunas situaciones tales que de entrada nada que ver con ruta más corta, pero que se pueden modelar mediante una red y darles solución aplicando DIJKSTRA. Para esto, consideremos la siguiente situación:

Ejercicio 1.- Suponga que cuesta 10 000 dólares comprar un automóvil nuevo. En la tabla siguiente se muestra el costo anual de uso y el valor de reventa de un automóvil usado. Determine, suponiendo que se tiene un automóvil nuevo actualmente, una estrategia de reemplazo que minimice los costos netos de tener y de usar un automóvil para los próximos seis años.

Solución:

La red correspondiente constará de siete nodos {1, 2, 3, 4, 5, 6, 7}. El nodo i corresponde al inicio del año i. Para i < j, un arco (i, j) corresponde a la compra de un automóvil nuevo al inicio del año i y conservarlo hasta el inicio del año j. La longitud del arco (i, j) será el costo neto total incurrido por mantener el automóvil desde el inicio del año i hasta el principio del año j, si se compra un automóvil nuevo al inicio del año i y si se da como adelanto este coche al comprar otro automóvil al inicio del año j.

Por ejemplo, calculemos la longitud (costo) del arco (1,2) que corresponde a reemplazar el auto al inicio del año 2 o mantenerlo solo un año.

CT = Costo de mantenerlo un año + Costo del remplazo (Costo del auto – Precio de venta)

CT = 300 + (10000-7000) = 3300

Otro ejemplo, el Costo (peso o longitud del arco (3,6) será:

CT = Costo de mantenimiento de tres años (desde el inicio del año 3 hasta el inicio del año 6 que sería todo el año 3 todo el 4 y todo el 5) + Costo del reemplazo cuando el auto tiene tres años de antigüedad.  

CT = (300+ 500+ 800) + (10000-3000) = 1600+7000 = 7600

Espero que con esto ya no tengan dificultad para determinar el costo de los demás arcos y si todavía tienen dudas, háganmelas saber en el foro, que no necesariamente tiene que ser en la hora de clase.

[pic 1]

Aplicando DIJKSTRA:

Agregando etiquetas temporales tenemos:

[pic 2]

Actualizamos etiquetas temporales:

     Nodo 3 = min {4800, 3300+3300} = 4800

     Nodo 4 = min {7600, 3300+4800} = 7600

     Nodo 5 = min {9800, 3300+7600} = 9800

     Nodo 6 = min {12400, 3300+9800} = 12400

     Nodo 7 = min {15600, 3300+12400} = 15600

Nuevas etiquetas temporales, junto con la nueva etiqueta permanente

[pic 3]

Actualizando etiquetas temporales:

     Nodo 4 = min {7600, 4800+3300} = 7600

     Nodo 5 = min {9800, 4800+4800} = 9600

     Nodo 6 = min {12400, 4800+7600} = 12400

     Nodo 7 = min {15600, 4800+9800} = 14600

Nuevas etiquetas temporales, junto con la nueva etiqueta permanente

[pic 4]

Actualizando etiquetas temporales

     Nodo 5 = {9600, 7600+3300} = 9600

     Nodo 6 = {12400, 7600+4800} = 12400

     Nodo 7 = {14600, 7600+7600} = 14600

Nuevas etiquetas temporales, junto con la nueva etiqueta permanente

[pic 5]

Actualizando etiquetas temporales

     Nodo 6 = min {12400, 9600+3300} = 12400

     Nodo 7 = min {14600, 9600+4800} = 14400

Nuevas etiquetas temporales, junto con la nueva etiqueta permanente

[pic 6]

Actualizando etiquetas temporales

     Nodo 7 = min {14400, 12400+3300} = 14400

Las etiquetas permanentes son

[pic 7]     

Ilustrando las etiquetas permanentes en la red y determinando la ruta más corta tenemos:

[pic 8][pic 9]

Dado que la ruta más corta es 1→ 3 → 5 → 7, entonces la estrategia óptima es reemplazar el automóvil al inicio del año 3 y al inicio del año 5.

Ejercicio 2.- Un club atlético operará sobre la base de ensayar con equipo alquilado durante cuatro años después de los cuales o bien comprará nuevo equipo o se retirará del negocio. En la siguiente tabla se muestran los costos netos totales asociados con el alquiler de equipo nuevo al comienzo del año i y negociarlo al principio del año j. Se quiere saber cuándo alquilar equipo para minimizar el costo total de los 4 años. Formular como problema de redes y resolverlo.

...