El problema de la ruta mas corta

1. 1
Lic. Araujo Cajamarca, Raul
El problema de la ruta ma s corta
El modelo de la ruta más corta se refiere a una red en la cual cada arco (,ij ) tiene asociado un
número, ij
c , el cual se interpreta como la distancia (o tal vez el costo o el tiempo) desde el
nodo i hasta el nodo j . Una ruta o camino entre dos nodos es cualquier secuencia de arcos
que los conecte. El objetivo consiste en encontrar las rutas más cortas (o de menor costo o
más rápidas) desde un nodo especifico hasta cada uno de los demás nodos de la red.
Ejemplo01
La administración de seervada park necesita encontrar la ruta más corta desde la entrada del
parque (nodo O) hasta el mirador (nodo T) a través del sistema de caminos que se presenta en
la figura siguiente:
O
A
C
B
D
E
T
2
5
7
4
4
1
4
2
3
7
1
5


Métodos de solución:

Un método sencillo para aprender a enfrentar este problema es el de la fuerza bruta.
Fuerza bruta: consiste en explorar cada uno delos caminos posibles a fin de determinar cuál es
el mejor.
En el grafo anterior resulta bastante sencillo determinar todas las soluciones posibles.
1. Secuencia: O-A-D-T=14u.
O
A D
T
2
7
5

2. 2
Lic. Araujo Cajamarca, Raul

2. Secuencia: O-A-B-D-T=13u.
O
A
B
D
T
2
4
2
5


3. Secuencia: O-B-D-T=14u.
O B
D
T
4
5
5


4. Secuencia: O-B-D-T=14u.
O B
D
E
T
5
3
1
5


Podríamos seguir así enumerando cada una de las rutas, hasta ahora la mínima es de 13u.
Otros métodos mucho más rápidos y eficientes para resolver este tipo de problemas son:
1. Método simplex para redes
2. Algoritmo de Dijkstra
3. Algoritmo de Bellman-Ford

3. 3
Lic. Araujo Cajamarca, Raul
Algoritmo de Dijkstra

Vamos a resolver el Ejemplo 01 para determinar la ruta más corta desde “O” hasta “T”.
Iteración 01: procedemos a etiquetar el nodo origen y lo convertimos en permanente, luego
etiquetamos los nodos adyacentes, directamente conectados que serán denominados nodos
temporales.
O
AA
CC
BB
DD
EE
T
2
5
7
4
4
1
4
2
3
7
1
5
(0)
0, 
(1)
2,O 
(1)
4,O 
(1)
5,O



Iteración 02: de alguno de los nodos temporales elegimos aquel que tenga el menor costo total
asociado y lo convertimos en permanente y actualizamos los nodos temporales.
O
A
C
B
D
E
T
2
5
7
4
4
1
4
2
3
7
1
5
(0)
0, 
(1)
4,O 
(1)
2,O 
(1)
5,O 
(2)
4,A 
(2)
9,A


Iteración 03:

Procedencia:
Nodo anterior
Costo total
asociado
Iteración

4. 4
Lic. Araujo Cajamarca, Raul O
A
C
B
D
E
T
2
5
7
4
4
1
4
2
3
7
1
5
(0)
0, 
(1)
4,O 
(1)
2,O 
(1)
5,O 
(2)
4,A 
(2)
9,A 
(3)
8,C


Iteración 04:
O
A
C
B
D
E
T
2
5
7
4
4
1
4
2
3
7
1
5
(0)
0, 
(1)
4,O 
(1)
2,O 
(1)
5,O 
(2)
4,A 
(2)
9,A 
(3)
8,C 
(4)
7,B 
(4)
8,B

Iteración 05: O
A
C
B
D
E
T
2
5
7
4
4
1
4
2
3
7
1
5
(0)
0, 
(1)
4,O 
(1)
2,O 
(1)
5,O 
(2)
4,A 
(2)
9,A 
(3)
8,C 
(4)
7,B 
(4)
8,B 
(5)
14,E

5. 5
Lic. Araujo Cajamarca, Raul
Iteración 06: O
A
C
B
D
E
T
2
5
7
4
4
1
4
2
3
7
1
5
(0)
0, 
(1)
4,O 
(1)
2,O 
(1)
5,O 
(2)
4,A 
(2)
9,A 
(3)
8,C 
(4)
7,B 
(4)
8,B 
(5)
14,E 
(6)
13,D

Al convertir permanente al último nodo nos indica que hemos encontrado la solución óptima,
es decir la ruta más corta que sería la siguiente: O
A
C
B
D
E
T
2
5
7
4
4
1
4
2
3
7
1
5
(0)
0, 
(1)
4,O 
(1)
2,O 
(1)
5,O 
(2)
4,A 
(2)
9,A 
(3)
8,C 
(4)
7,B 
(4)
8,B 
(5)
14,E 
(6)
13,D

La ruta con distancia mínima de “O” hasta “T” es de 13u. Lo determinamos ahora de atrás
hacia adelante, el cual se ha encontrado con 6 iteraciones.
O-A-B-D-T
Ejemplo 02
Una persona tiene que trasladarse a diario del pueblo A al pueblo H. está estudiando cual es el
trayecto más corto usando un mapa de carreteas.
Las carreteras y sus distancias están representadas en la siguiente matriz:

6. 6
Lic. Araujo Cajamarca, Raul
A B C D E F G H
A 12 4
B 5 3
C 2 6
D 8
E 7
F 5
G 3
H

Encuentre la solución a su problema utilizando el algoritmo de Dijkstra
Solución: A
B
C
D
E
F
12
3
4
6
2
5
2
3
G
5
8
H
7
(0)
0, 
(1)
4,A 
(1)
12,A 
(2)
6,C 
(2)
10,C 
(3)
14,D 
(5)
15,B 
(4)
15,F 
(6)
17,G  
(7)
22,E

El camino, ruta mínima o más corta será:
A-C-D-G-H= 17 Km.

Ejercicio 01
Determine la ruta más corta entre los nodos 1 y 8 de la siguiente red.
1
22
33
44
55
66
3
3
4
4
5
2
3
2
2
2
5
8
7
3
2
4

7. 7
Lic. Araujo Cajamarca, Raul
Ejercicio 02 1
22
44
33
55
7
3
2
3
3
2
3
1
2
3
6
1
2


G. D. Eppend
F. J. Gould
C. P. Schmidt
Jeffrey H. Moore
Larry R. Weatherford.
Investigación de Operaciones en la Ciencia Administrativa
5Ta edición Prentice Hall
pp. 244.

Modelo de reemplazo de equipos

Ejercicio 01
Rentcar está desarrollando un plan de reemplazo para su flotilla de automóviles para un
horizonte de planificación de 5 años (1996 a 2000). Al principio de cada año se toma una
decisión acerca de si se debe mantener un automóvil en operación o si se debe reemplazar. Un
automóvil debe estar en servicio por lo menos un año, pero se debe reemplazar después de
tres años. La siguiente tabla proporciona el costo de reemplazo como una función del año en el
cual se adquiere un automóvil y el número de años de operación.

Año que
se adquirió
Costo de reemplazo ($) por determinados
años en operación
1 2 3
1996 4000 5400 9800
1997 4300 6200 8700
1998 4800 7100 -
1999 4900 - --

8. 8
Lic. Araujo Cajamarca, Raul
Ejercicio 02
Los cinco nodos que aparecen en la red siguiente representan puntos en el tiempo, a un año
de distancia, durante un periodo de 4 años. Cada nodo señala el momento en el que se debe
tomar una decisión con respecto a conservar o reemplazar el equipo de computación de la
compañía. Si se toma la decisión de reemplazar el equipo se debe también tomar una decisión
con respecto a cuánto tiempo se utilizará el nuevo equipo. El arco que va del nodo 0 al nodo 1
representa la decisión de conservar el equipo actual durante un año y reemplazarlo al final de
ese año. El arco que va del nodo 0 al nodo 2 representa la decisión de conservar el equipo
actual durante 2 años y remplazarlo al final de esos 2 años. Los números que aparecen por
encima de los arcos señalan los costos totales correspondientes a las decisiones de reemplazo
de equipo; estos costos incluyen el precio de compra descontando, el valor de reventa, los
costos de operación y los costes de mantenimiento.
Determine la política de remplazo de equipo de costo mínimo para el periodo de 4 años. 0 1 2 3 4
600 500 800 700
1000
2800
2000
1400
2100
1600

Ejercicio 03
Un taller de automotores debe tener siempre un analizador de motor disponible. Un
analizador nuevo cuesta 1000$. El costo i
m por el mantenimiento de un analizador durante su i
ésimo año de funcionamiento es como sigue: 1 2 3
60$, 80$, 120$m m m   . Un
analizador se podrá tener durante 1;2 3ó años y después de usarlo i años (1;2;3i ) se podría
vender y realizar un pago inicial de uno nuevo. Si se compra un analizador nuevo y se vende el
de i años de antigüedad, se obtiene un valor de salvamento (equipo viejo) i
s , donde 1
800$s
, 2
600$s , 3
500$s . Dado que una maquina nueva se debe comprar hoy
(tiempo 0, ver figura), el taller desea determinar una política de reemplazo o reposición y de
valor de equipo viejo para darlo como pago inicial de uno nuevo que minimice:
Los costos netos=(costo de mantenimiento)+(costo de reposición)-(valor de salvamento o de
reventa) durante los siguientes 5 años.
0 1 2 3 4
Año 1 Año 2 Año 3 Año 4
5
Año 5
Tiempo 0 Tiempo 1 Tiempo 2 Tiempo 3 Tiempo 4 Tiempo 5

9. 9
Lic. Araujo Cajamarca, Raul
Costos
años
1 2 3
Mantenimiento i
m 60 80 120
Salvamento i
s 800 600 500

Costo de reposición: 1000$
Costos netos= (costo de mantenimiento)+(costo de reposición)-(valor de salvamento)
0-1: 60+1000-800=260
0-2: 140+1000-600=540
0-3: 260+1000-500=760
1-2:
1-3:
1-4:
Solución óptima: costo mínimo 1280$
Ruta más corta: 1-4-5 y 3-4-5

10. 10
Lic. Araujo Cajamarca, Raul
Solucionario

Ejercicio 01
1. El problema se puede formular como una red en la cual los nodos 1 al 5 representan los
años, 1996 al 2000.
2. Los arcos del nodo 1 (año 1996) pueden llegar solo a los nodos 2; 3 y 4, debido a que un
automóvil debe estar en operación entre uno y tres años.
3. Los arcos de los otros nodos se pueden interpretar de manera similar.
4. El largo de cada arco es igual al costo del reemplazo
5. La solución al problema es equivalente a encontrar la ruta ms corta entre los nodos 1 y 5. 1 2 3 4 5
4000 4300 4800 4900
5400
9800
6200
8700
7100
1996
2000
(0)
0,  
(1)
4000,1  
(1)
5400,1  
(1)
9800,1  
(2)
8300,2  
(2)
10200,2  
(2)
12700,2  
(3)
10200,3  
(3)
12500,3  
(4)
14700,4

Utilizando el algoritmo de Dijkstra la ruta más corta entre el nodo 1 y 5 es: 1-3-5, con un costo
total de 12,500 dolares.
Esta solución significa que: el automóvil adquirido en el año 1996(nodo 1) debe ser
reemplazado después de dos años, en 1998 (nodo 3). Así, el automóvil de reemplazo se
mantendrá en operación hasta finales del año 2000.
El costo total de esta política de reemplazo es de 12,500$ (5400+7100 dolares).
Ejercicio 02 0 1 2 3 4
600 500 800 700
1000
2800
2000
1400
2100
1600
(0)
0, 
(1)
6,o 
(1)
10,o 
(1)
20,o 
(1)
28,o 
(2)
11,1 
(2)
20,1 
(2)
27,1 
(3)
18,2 
(3)
26,2 
(4)
25,3

11. 11
Lic. Araujo Cajamarca, Raul
o La solución al problema es equivalente a encontrar la ruta más corta entre los nodos 0
y 4
o Utilizando el algoritmo de Dijkstra tenemos que la ruta más corta entre el nodo 0 y 4
es: 0-2-3-4 con un costo total mínimo de 2500 dolares.

o Esto quiere decir que el equipo que se adquiere en el nodo 0 se debe conservar 2 años
y luego reemplazarlo, y el equipo que se adquiere en el nodo 2 se conservará un año y
luego se renueva y este último también se conserva solo un año.

o Con esta política el costo total en el que se incurre es de 2500 dolares.