REDES Y TRAYECTORIA M S CORTA

REDES y TRAYECTORIA
MÁS CORTA

M. en C. Luís Ignacio Martínez Solís

Modelos de Red
• Muchos problemas de
optimización importantes se
analizan mejor por medio de una
representación grafica o de red.

DEFINICIONES BASICAS
• Una grafica, o red, se define mediantes dos
conjuntos de símbolos: nodos y arcos.
Primero, se define un conjunto (llámelo V) de
puntos extremos o vértices. Los vértices deuna grafica o red también se llaman nodos.
También se define un conjunto de arcos A.

DEFINICIONES BASICAS
• Un arco consiste en un par ordenado de
puntos extremos y representa una posible
dirección de movimiento que podría ocurrir
entre puntos extremos(o vértices).
j

k

DEFINICIONES BASICAS
• Para los fines que aquí persiguen, si una red contiene un arco
(j,k) entonces el movimiento es posibledel nodo j al nodo k
.Suponga que los nodos 1,2,3y 4 de la figura representan
ciudades y cada arco representa una carretera(de un solo
sentido)que enlaza dos ciudades.

DEFINICIONES BASICAS
• . Para esta red, V={1,2,3,4} y A={(1,2),(2,3),(3,4),(4,3)
(4,1)}.Para el arco(j,k), el nodo j es el nodo inicial y el
nodo k es el nodo terminal. Se dice que el arco (j,k)va del
nodo j al nodo k. Porconsiguiente, el arco (2,3) tiene el
nodo inicial 2 y el nodo terminal 3, y va del nodo 2 al
nodo 3.El arco (2,3) se podría considerar como una
carretera (unidireccional) en la que se podría viajar de la
ciudad 2 a la ciudad 3 .En la figura , los arcos muestran
que se permite viajar de la ciudad 3 a la ciudad 4 y de la
cuidad 4 a la ciudad 3, pero que el viaje entre las otras
ciudades podría ser en unsolo sentido.

DEFINICIONES BASICAS
• Una secuencia de arcos tal que cada arco tiene
exactamente un vértice en común con el arco previo,
se llama una cadena.
• Una trayectoria es una cadena en la que el nodo
terminal de cada arco es idéntico al nodo inicial del
arco siguiente.
• Por ejemplo, en la figura, (1,2)-(2,3)-(4,3) es una
cadena pero no una trayectoria; (1,2)-(2,3)-(3,4) es una
cadena y unatrayectoria. La trayectoria (1,2)-(2,3)-(3,4)
representa una forma de viajar del nodo 1 al 4.

PROBLEMAS DE TRAYECTORIA MAS CORTA
• Se supone que cada arco de la red tiene una
longitud asociada con él. Suponga que se
empieza en un nodo particular (digamos, el
nodo 1).El problema de encontrar la
trayectoria mas corta (trayectoria de longitud
mínima) del nodo 1 a cualquier otro nodo en
la red sellama problema de trayectoria mas
corta. Los ejemplos 1 y 2 son problemas de
trayectoria más corta.

EJEMPLO 1
• Considere el ejemplo de Powerco (figura ) suponga
que cuando se envía potencia de la planta 1 (nodo 1)
a la ciudad 1 (nodo 6), esta debe pasar por
subestaciones de retransmisión (nodos 2 a 5).

EJEMPLO 1
• Para cualquier par de nodos entre los que se puede
transportar la potencia, lafigura2 da la distancia (en
millas) entre los nodos. Así, las subestaciones 2 y 4
están separadas por tres millas, y la potencia no se
puede enviar entre las subestaciones 4 y 5.Powerco
quiere que la potencia se envié de la planta 1 a la
ciudad 1 para que recorra la distancia mínima
posible, así que debe encontrar la trayectoria más
corta en la figura2 que une el nodo 1 con el nodo 6.

EJEMPLO 2
•Acabo de comprar (en el tiempo 0) un automóvil nuevo por
$12000. El costo de mantener un automóvil durante un año
depende de su edad al comienzo del año, como se da en la
tabla 1. Tabla1
Costos de mantenimiento del automóvil
Edad del automóvil
(años)
0

Costo de mantenimiento
anual
2000

1

4000

2

5000

3

9000

4

12000

EJEMPLO 2
•

Para evitar costos de mantenimiento altos con un automóvilmás antiguo,
podría entregar a cuenta mi automóvil y comprar uno nuevo. El precio que
recibo por dejar a cuenta mi automóvil, depende de la edad del automóvil
al momento de intercambio (véase la tabla 2).
Tabla 2
Precios de intercambio del automóvil
Edad del automóvil
(años)
1

Precio de intercambio
7000

2

6000

3

2000

4

1000

5

0

EJEMPLO 2
• Para simplificar los cálculos, suponga que en...