Ruta más 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.

Edad del Precio de Costos de

Automóvil Reventa Operación

(años) (dólares) (dólares)

1 7 000 300 (año 1)

2 6 000 500 (año 2)

3 4 000 800 (año 3)

4 3 000 1 200 (año 4)

5 2 000 1 600 (año 5)

6 1 000 2 200 ( año 6)

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,

...