TEORIA DE GRAFOS O REDES

Aunque muchos de los problemas de optimización de redes pueden formularse como programas
lineales o enteros y resolverse con los algoritmos correspondientes, existen métodos específicos que
aprovechan la estructura especial de cada problema y su representación en una red, permitiendo
procedimientos de solución más eficientes.

Existen un gran número de situaciones en investigación de operaciones que se pueden modelar y

resolver adecuadamente como redes (nodos conectados por ramas). A manera de ilustración
considere las siguientes situaciones:

a) El diseño de una red de ductos de gas natural de Camisea, que conectan la fuente con los puntos
de entrega en las principales ciudades del país. El objeto del modelo es minimizar el costo de
construcción del ducto.
b) La determinación de la ruta más corta entre dos ciudades en una red de carreteras existente.
c) La determinación del programa de flujo de costo mínimo de los campos petroleros a las refinerías
a través de una red de ductos.
d) La determinación del programa de tiempo (fechas de inicio y de terminación) para las actividades
de un proyecto de construcción.

La solución de estas situaciones y de otras semejantes se logran por medio de una variedad de
algoritmos de optimización de redes. Algunos de estos algoritmos son:
 Algoritmo de la ruta más corta.
 Árbol de expansión mínima.
 Algoritmo del flujo máximo.
 Algoritmo de redes capacitadas de costo mínimo.
 Algoritmo de la ruta crítica.

PROFESOR ALDO MADRID

I. Problema del Camino Mas Corto
El problema de la ruta más corta involucra una red conexa con costos (tiempos, distancias, etc. no
negativo) asociados a cada arco. Del grafo o diagrama de red, a uno de los nodos se le denomina
fuente o nodo origen y a otro nodo se le denomina nodo destino. El objetivo es determinar una ruta
más corta que una el nodo origen con el nodo destino, esto es, que la suma de los costos asociados
de los arcos sea el menor costo (costo mínimo).

Los problemas de la ruta más barata se resuelven mediante el siguiente algoritmo de etiquetas.
Se han desarrollado dos tipos de algoritmos: el algoritmo de Dijkstra (Físico Holandés, 1930-2002)
y el algoritmo de Floyd (Científico de Nueva York 1936-2001). Los cuales se aplican para redes
cíclicas y acíclicas.
El algoritmo de Dijkstra tiene por objeto determinar las rutas mas cortas entre el nodo fuente y los
demás nodos de la Red o grafo. El algoritmo de Floyd es más genérico, permite determinar las rutas
más corta entre dos nodos cualesquiera que forman parte del grafo o red.

ALGORITMO DE LA RUTA MAS CORTA - El algoritmo de Dijkstra

Sea Uij la distancia más corta del nodo fuente (nodo origen i) al nodo j (más próximo) , sea uij la
longitud del arco (i, j). Entonces el algoritmo define etiquetas Permanentes y Temporales:
Etiqueta permanente: [uj, i] y Etiqueta temporal (uj, i)

Paso 1. Etiquetar el nodo inicial con etiqueta permanente:[0, -].

Paso 2. Etiquetar los nodos conectados con el nodo inicial con etiquetas temporales. El nodo con la
menor distancia: min [uj, i], se le debe asignar como etiqueta permanente.
Paso 3. Etiquetar ahora todo los nodos conectados con el nodo asignado como etiqueta permanente.
Y sumar las distancias dentro de las etiquetas temporales. [ui + dij ; i]. El nodo a elegir como etiqueta
permanente será: min [ui + dij ; i].
Paso 4. Repetir el paso3 hasta que todos los nodos del grafo tengan etiquetas permanentes, FIN.

PROFESOR ALDO MADRID

Problema1. Sea el siguiente Grafo o diagrama de red, donde los números asignados a cada uno de
los arcos representan la distancia en kilómetros de un nodo a otro. Hallar la ruta con la distancia
mínima para ir del nodo 1 al nodo 8.

a) Formular el caso como un MPL

b) Hallar la ruta con la distancia mínima para ir del nodo 1 al nodo 8.

Solución

Variables de Decisión:
1 , 𝑠𝑖 𝑒𝑙 𝑛𝑜𝑑𝑜 𝑗 𝑒𝑠 𝑣𝑖𝑠𝑖𝑡𝑎𝑑𝑜 𝑖𝑛𝑚𝑒𝑑𝑖𝑎𝑡𝑎𝑚𝑒𝑛𝑡𝑒 𝑑𝑒𝑠𝑝𝑒𝑢é𝑠 𝑑𝑒𝑙 𝑛𝑜𝑑𝑜 𝑖
𝑋𝑖𝑗 = {
0 , 𝑐𝑎𝑠𝑜 𝑐𝑜𝑛𝑡𝑟𝑎𝑟𝑖𝑜 … … … … … … … … … … … … … … … … … … … … … …
Restricciones:
X12 + X13 = 1
X12 - X25 = 0
X13 – X34 – X36 = 0
X25 – X57 = 0
X34 – X47 – X48 – X46 = 0
X36 + X46 – X68 = 0
X57 + X47 – X78 = 0
X78 + X48 + X68 = 1
XIJ ≥0
Función Objetivo:
Min Z =4X12+3X13+8X25+12X34+4X36+17X57+20X47+2X46+15X48+X68+9X78

PROFESOR ALDO MADRID

MPL general del Camino más Corto

𝑚 𝑚

𝑀𝑖𝑛 𝑍 = ∑ ∑ 𝑐𝑖𝑗 𝑥𝑖𝑗

𝑖=1 𝑗=1
Sujeto a:
𝑚 𝑚 1, 𝑠𝑖 𝑖 = 1
∑ 𝑥𝑖𝑗 − ∑ 𝑥𝑘𝑖 = { 0; 𝑠𝑖 2 ≤ 𝑖 ≤ 𝑚 − 1
𝑗=1 𝑘=1 −1; 𝑠𝑖 𝑖 = 𝑚

xij ≥ 0

Problema 2. En el derrumbe de una mina, un minero ha quedado atrapado; la entrada de la mina

se encuentra ubicada en el nodo 1, se sabe que el minero está atrapado en el nodo 7, para llegar a
dicho nodo hay que atravesar una red de túneles que van conectados entre sí. El tiempo de vida
que le queda al minero sin recibir auxilio es cada vez menor y se hace indispensable hallar la ruta
de acceso al nodo 7.
El grafo, muestra las distancias entre nodos de la mina en cientos de metros.

a. Determine la ruta más corta que permita auxiliar al minero.

b. Formule el caso como un MPL.

PROFESOR ALDO MADRID

Problema3. Se adquiere (tiempo 0) un vehículo nuevo por un valor de $12000. El costo de mantener
un automóvil durante un ano depende de la antigüedad del vehículo a comienzo del año (Ver
cuadro). Para evitar incurrir en elevados costos de mantención, es posible vender el vehículo usado
y adquirir uno nuevo. El precio de venta del automóvil usado depende de los años de uso que tenga
(Ver cuadro). Para simplificar los cálculos, se puede asumir que el costo de un vehículo nuevo es
siempre US$12000, independiente del ano de compra. El
Años de Mantención Precio
objetivo es determinar el programa de renovación del Antigüedad Costo anual ($) Venta ($)
automóvil de forma de minimizar los costos netos 0 2000 7000
durante los próximos cinco años, considerando que al 1 4000 6000
final del periodo se vende el vehículo. Formule y 2 5000 2000
3 9000 1000
resuelva el modelo como un problema de ruta más corta.
4 12000 0

Solución
Sea cij la longitud del arco (i, j) definida como el costo neto de comprar, mantener y vender el
vehículo desde el inicio del año i al inicio del año j.
Dónde:
cij = (costos de mantención durante los años i. i+1, …) + (costo de compra al inicio del ano i) –
(Precio de venta al inicio del ano j)

Costo de Mantenimiento por Año

Año 1 2 3 4 5 6
1 7 12 21 31 41
2 7 12 21 31
3 7 12 21
4 7 12
5 7

44
31
21
12

7 7 7 7 7
1 2 3 4 5 6

12 12 12
21 21
31

Problema4. La Ruta Más Confiable

PROFESOR ALDO MADRID

Una Ejecutiva debe conducir todos los días de su casa hacia su trabajo. Como ella sabe Teoría de
Grafos, ha determinado la ruta más corta para llegar a su trabajo. Desafortunadamente, la ruta más
corta que ella ha determinado, tiene un control policial muy estricto (sobre todo en las horas punta),
que le ha ocasionado fuertes pagos de multas por sobrepasarse los límites de velocidad. Debido a
ello, es obvio que la ruta más corta no es una buena opción para ella. La ejecutiva ha decidido buscar
una nueva ruta que maximice la probabilidad de no ser detenida por la policía, para ello analiza el
grafo (la red) con las posibles rutas factibles en función de las estimaciones de probabilidad que ella
asigno para cada ruta, tal como muestra el siguiente grafo. Cuál será la ruta más confiable desde su
casa hasta su trabajo (nodo7).
0.8 0.35
1 3 5

0.2 0.5
0.6
0.1 0.4
Casa 7

2 0.3 4

Solución: El algoritmo del camino más corto no se puede aplicar de modo directo, pues las
cantidades asignadas a los arcos del grafo son probabilidades; por lo que se debe aplicar un artificio.
Tomar logaritmos y luego aplicar el algoritmo y al resultado final aplica el antilogaritmo.

Problema 5. Una Cía. Dedicada al alquiler o renta de autos está evaluando un reemplazo de su flota
de autos para los próximos cinco años. Un automóvil debe estar en servicio como mínimo un año,
para luego considerar su reemplazo. La siguiente tabla muestra el resumen de los costos de reemplazo
(en miles de dólares) en función del número de años en operación. Los costos incluyen el monto de
compra, el seguro, operación y mantenimiento.
1 2 3 4 5
1 4 5,4 9,8 13,7
2 4,3 6,2 8,1
3 4,8 7,1
4 4,9
Con esta información cada cuantos años deben ser reemplazados y el año máximo de su vigencia
de su flota de automóviles
Solución: El grafo que representa el caso dado es.
13.7

9.8

5.4
4.8 4.9
1 2 3 4 5
4 4.3
6.2

8.1 7.1

Caso: CAMINO MAS CORTO

PROFESOR ALDO MADRID

Un estudiante de ingeniería de la URP desea saber cuál es la ruta más corta desde su casa a la
universidad, para ello utiliza “Google Maps” para determinar las distancias de todas las posibles
rutas desde su casa hasta la universidad. ¿Cuál debe ser la ruta que debe elegir?

PROFESOR ALDO MADRID

II. El Problema del Arbol de Expansion Mínima
Suponga que cada uno de los arcos (i, j) de un grafo tiene asociado cierta longitud. Donde cada arco
(i,j) representa una forma que conecta el nodo i con el nodo j (en ambos sentidos). Existen muchas
aplicaciones donde se desea determinar que todos los arcos de un grafo estén conectados, donde se
busca minimizar la longitud total de los arcos que une todos los nodos (sin formar ciclos - loops).

En un grafo o red de n nodos, un árbol es un grupo de n − 1 arcos que conecta todos los nodos de la
red y que puede contener caminos abiertos (no loop). Luego, el árbol de expansión mínima, es el
árbol cuyos arcos tienen la menor longitud total posible.

Algoritmo del problema del árbol de expansión mínima

Paso1. Construir una tabla representando en filas y columnas los nodos de la red. Cada celda i − j se
completa con la distancia entre los nodos i y j. Si la conexión no es posible, se agrega una M. Se
agrega una columna auxiliar para indicar los nodos ya conectados.
Paso2. Se inicia en cualquier nodo i. Se indica como conectado en la columna auxiliar. Se tacha la
columna del nodo i y se busca el menor coeficiente no tachado de la fila i, se identifica dicho nodo
como j.
Paso3. Se marca como conectado el nodo j en la columna auxiliar. Se tacha la columna j. Se busca
el menor coeficiente no tachado entre las filas de los nodos ya conectados y se marca el nuevo nodo.
Se repite el paso hasta completar la conexión de todos los nodos.

Ejemplo. Una pequeña escuela dispone de 5 computadoras. La distancia

entre cada equipo es en decenas de metros de fibra óptica, tal como muestra
en la Figura. ¿Cuál es la mínima longitud de cable que se requiere para
conectar todas las computadoras?

Solución
Taba matricial del grafo:

PROFESOR ALDO MADRID

Árbol de expansión mínima de conexión de las 5 PC´s:

Rpta. Total 90 metros de fibra óptica

Problema1. Determinar el árbol de expansión mínima del grafo

que se presenta.

Solución:
Se adjunta la tabla final

PROFESOR ALDO MADRID

Problema2. El gobierno Regional de Huancavelica debe suministrar de agua potable a 7 localidades
(distritos de la zona), la troncal está ubicada en el nodo A. Se desea determinar cuál será la distancia
más corta para dotar de agua a las siete localidades a fin de poder determinar el número de tuberías
a utilizar en el tendido de red de agua potable. Las distancias están en kilómetros, cada tubo de PVC
“flexibles” mide 5metros. ¿Cuánto tubos conformaran el lote a utilizar en el tendido de la red de
agua?

Problema3. Determinen la mínima longitud de cable de fibra óptica que se debe utilizar para
interconectar las 12 áreas de una empresa (las distancias están en cientos de metros).

Problema4 Una compañía de reforestación debe sembrar árboles en ocho zonas de una misma área.
Para esto debe desarrollar un sistema de caminos de tierra para tener acceso a cualquier zona desde
cualquier otra. La distancia entre cada par de zonas viene dada en la siguiente tabla:

¿Cuál será la longitud mínima del camino a

construir que una entre pares de las zonas
donde serán sembradas los arboles?

PROFESOR ALDO MADRID

EL PROBLEMA DEL FLUJO MAXIMO

En un grafo cuando los arcos representas flujos de: líquidos, gases, vehículos, etc. lo que se busca es
obtener el máximo flujo que puede brindar el grafo (red).
En un grafo se puede representar el flujo que se da en una red de una fábrica hacia sus clientes (se
busca maximizar el flujo). O el caso de representar la red de suministros de proveedores a una
fábrica. O el flujo de un fluido (petróleo, gas, agua, desagüe, etc.) a través del tendido de tuberías
y/o acueductos. O el flujo de tránsito (de vehículos, partes de una pieza en un proceso de fabricación,
etc.) en una red de transporte. En todas ellas se tendrá presente que el flujo debe discurrir desde un
Origen hacia un Destino (sumidero).
Algoritmo
1. Identifica una trayectoria de aumento con la Cij mayor de todos los flujos menores Cij
del grafo.
2. Enviar el flujo con la cantidad de Cij. Disminuir el Cij enviando a todos los Cij de los
arcos del grafo.
3. Repetir el proceso hasta que todas las trayectorias sus capacidades mínimas de envío
sean cero. Caso contrario ir al paso 1. su todas las trayectoria tienen al menos un Cij = 0
entonces Fin.

Planteamiento del Problema de Flujo Máximo como un MPL

Maximizar F
 F si j  s,

s.a.  x jk   x ij  0 si j  s, e,
kD(j) iA(j)  F si j  e,

0  xij  qij i, j  1, 2,..., n

Ejemplo: Formular como un MPL el siguiente grafo (red) para

hallar el flujo máximo:

Solución: Maximizar x13  x12

s.a. x24  x23  x32  x12  0,
x34  x32  x23  x13  0,
0  x12  4,
0  x13  3,
0  x 23  3,
0  x 32  1,
0  x 34  5,
0  x 24  1.

PROFESOR ALDO MADRID

Ejemplo 1. Determine el flujo máximo desde el nodo 1 (nodo fuente) hacia el nodo 7 (sumidero)
del siguiente grafo.

Problema1. El siguiente grafo muestra el proceso de

producción que indica las diferentes rutas que puede
seguir un producto en una planta, en sus diferentes
caminos de ensamblaje. El número de cada cuadro
representa el máximo límite de artículos por hora que
se pueden procesar en cada estación.

a. Cuál es el número máximo de partes por

hora que puede procesar la planta.
b. Que operaciones generan cuellos de botella y como deben mejorarse.

PROFESOR ALDO MADRID