MODELO DE REDES

Mg. Lord Barrera

Modelo de redes

Escuela de
Ingeniería Industrial

II

1. Redes: conceptos básicos

Definición 1.1. Llamamos red a un par ( N, A) donde N es el conjunto de
nodos y A ⊆ N × N es un conjunto de arcos. Si ( a, b) es un elemento de A, entonces a se llama origen y b se llama extremo. En la figura de
abajo vemos una red cuyos nodos son N = 0, 1, 2, n y cuyos arcos son{(0, 1); (0, 2); (1, 2); (2, 1); (1, n); (2, n)}.

2

n

0

1

Asi mismo, la red también puede expresarse por medio de una matriz de
incidencia.

(0, 1)

(0, 2)

(1, 2)

(2, 1)

(1, n)

(2, n)

0

1

1

0

0

0

0

1

−1
0
0

0

1

1

0

−1
0

−1
0

−1
1
0

0

1

−1

−1

2
n

Cada celda se marca con 1 si el vértice de su filaes el origen del arco de su
columna y con −1 si es el extremo. Se rellenan con ceros el resto de las celdas.
Otro tipo de matriz de incidencia más
simple se construye de la forma siguiente: si existe el arco (i : j) hay 1 en el elemento (i, j) de la matriz. En caso contrario hay un 0.

0
0

1

2

1

1

1
2

n

1
1

1
1

n

Definición 1.2. Llamamos red bilateral a unared que admite ambas orientaciones de los arcos. En este caso los arcos se llaman aristas. Una red sin aristas (que
no admite ambas orientaciones de los arcos) se llama red dirigida.

Una red con aristas puede transformarse en una red dirigida por medio de la
transformación dada en la figura de abajo:

´

A

A

A

B

B

B

´

Un vértice sin arco se llama aislado. Un lazo esun arco cuyo origen y extremo
coinciden. Una cadena es una sucesión de arcos adyacentes (arcos consecutivos
que tienen en común un vértice). Un camino o ruta es una sucesión de arcos
adyacentes del mismo sentido (el extremos de un arco es el origen del siguiente).
Un ciclo, circuito o camino cerrado es un camino en el cual el último extremo
coincide con el primer origen.

2. Modelo de laruta más corta (RCM)

El problema del camino de longitud mínima consiste en seleccionar entre
todos los caminos que unen dos nodos concretos, el camino más corto para ir de
uno de los nodos al otro
Ejemplo 2.1. Suponga que una empresa envía provisiones de la planta 1 (nodo1) a la ciudad 1 (nodo 6), ésta debe pasar por subestaciones de transmisión
(nodos 2 a 5). Para cualquier par de nodosentre los que se puede transportar la
provisión, la figura de abajo da la distancia (en kilómetros) entre los nodos. Así,
las subestaciones 2 y 4 están separadas tres kilómetros, y la provisión no se puede
enviar entre las subestaciones 4 y 5. La empresa quiere que la provisión se envíe
de la planta 1 a la ciudad 1 para que recorra la disnatncia mínima posible. Hallar
la trayectoria más corta dela figura que une el nodo 1 con el nodo 6.
2

3

4
2

4
Planta 1

1

6

2

Ciudad 1

2

3
3

3

5

Subestaciones

Solución. Si el costo de enviar provisiones fuerra proporcional a la distancia

2

que viaja la provisión, entonces conocer la trayectoria más corta entre la planta 1
y la ciudad 1 en la figura de arriba (y la trayectoria más corta entre la planta iy
la ciudad j en diagramas similares) sería necesario determinar los costos de envío
para la versión de transporte del problema mencionado.
Ejemplo 2.2. Acabo de comprar (en el tiempo 0) un automóvil nuevo por
$ 12 000. El costo de mantener un automóvil un automóvil durante un año depende de su edad al comienzo del año, como se da en la tabla 1. Para evitar costos
de mantenimiento altos conun automóvil má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 del intercambio (ver
tabla 2). Para simplificar los cálculos, suponga que en cualquier instante el costo
de un automóvil nuevo son $ 12 000. El objetivo es minimizar el costo neto (costos de compra + costos de...