Dr.

José Antonio Rivera Colmenero

Modelos de Redes
Teoría y
Problemas Resueltos

UNIVERSIDAD NACIONAL AUTÓNOMA DE MÉXICO

Posgrado de la Facultad de Ingeniería
Departamento de Sistemas

JOSÉ ANTONIO RIVERA COLMENERO 1

 Modelos de Redes
con aplicaciones en el
Transporte

JOSÉ ANTONIO RIVERA COLMENERO 2

Contenido del documento

Página

Introducción 4

Capítulo 1. Análisis de Redes 9

Capítulo 2. El Problema de Transporte 26

Capítulo 3. El Problema de Asignación 51

Capítulo 4. El Problema de Transbordo 59

Capítulo 5. El Problema de Flujo Máximo 76

Capítulo 6. El Problema de la Ruta Más Corta 92

Capítulo 7. El Problema del Árbol de Expansión Mínima 104

Capítulo 8. El problema del Agente Viajero 132

Capítulo 9. Redes Sociales. 153

JOSÉ ANTONIO RIVERA COLMENERO 3

 Introducción
Las redes están en todas partes. Hacer una llamada telefónica requiere configurar una
comunicación a través de una red cableada de todos los encuestados posibles mediante el
envío de paquetes de voz entre la persona que llama y la persona que recibe la llamada. El
suministro de agua, gas y electricidad para uso doméstico son redes de distribución
complejas que constan de muchos puntos de origen, intermedios y de destino, donde las
fuentes necesitan producir suficiente oferta para satisfacer la demanda de los puntos de
destino. Los servicios de entrega deben encontrar la ruta óptima para asegurarse de que
todos los paquetes se entreguen en su destino final de la manera más eficiente posible.
Incluso un simple viaje al supermercado implica el procesamiento de muchas redes. ¿Cuál
es la mejor ruta para conducir desde el hogar al supermercado dado el tráfico actual? Dada
una lista de compras, ¿cómo puedo ir al supermercado de manera eficiente para tener todos
los productos de mi lista?

Uno de los talentos de los humanos es exactamente el procesamiento de estas redes.

Subliminalmente, las personas tienen un buen sentido para encontrar una manera eficiente a
través de una red. Teniendo en cuenta su conexión entre el hogar y el trabajo. Dependiendo
de la hora y el día, puede cambiar su ruta para ir del hogar al trabajo sin dibujar
explícitamente la red y ejecutar algún algoritmo de optimización. Contactar a otras
personas, incluso sin los medios de telecomunicación de hoy en día como el teléfono y el
internet, es a menudo una tarea fácil para las personas. Siempre hay un amigo de un amigo
que conoce a la persona que estás buscando.

I.1. Los Sistemas de Transporte

Los sistemas de transporte consisten no solo en los elementos físicos y organizacionales

que interactúan entre sí para generar oportunidades de transporte, sino también en la
demanda que aprovecha esas oportunidades para viajar de un lugar a otro. Esta demanda de
viajes, a su vez, es el resultado de interacciones entre las diversas actividades económicas y
sociales ubicadas en un área determinada. Los modelos matemáticos de los sistemas de
transporte representan, para un sistema de transporte real o hipotético, los flujos de
demanda, el funcionamiento de los elementos físicos y organizativos, las interacciones
entre ellos y sus efectos en el mundo externo. Los modelos matemáticos y los métodos
involucrados en su aplicación a sistemas reales a gran escala son, por lo tanto, herramientas
fundamentales para evaluar y/o diseñar acciones que afectan los elementos físicos (nuevo
programa) de los sistemas de transporte. por ejemplo, una nueva autopista) y/o
componentes organizacionales (por ejemplo, un

Este libro analiza los modelos matemáticos que se utilizan para analizar los sistemas de
transporte, presentándolos como el resultado de un número limitado de supuestos generales
(teoría). También se ocupa de los métodos necesarios para hacer que estos modelos sean

JOSÉ ANTONIO RIVERA COLMENERO 4

operativos, y de su aplicación al diseño y evaluación de proyectos del sistema de transporte.
Este campo de conocimiento es conocido como ingeniería de sistemas de transporte.

El desarrollo de un proyecto de sistema de transporte puede incluir el diseño funcional de

nuevas instalaciones de infraestructura como carreteras, ferrocarriles, aeropuertos y
estacionamientos; evaluación de programas de inversión a largo plazo; evaluación de
esquemas de financiamiento de proyectos; determinación de programas y políticas de
precios para servicios de transporte; definición de esquemas de circulación y regulación de
redes viales urbanas; y diseño de estrategias para nuevos sistemas avanzados de control de
tráfico e información. Los elementos físicos del sistema están diseñados y / o seleccionados
de entre aquellos disponibles para proporcionar las características y el rendimiento que se
requieren de los servicios de transporte que se proporcionarán. Por supuesto, un proyecto
de sistema de transporte debe ser técnicamente viable; pero es igualmente importante que
su definición refleje una evaluación cuantitativa de sus características e impactos en
relación con los objetivos y limitaciones que el proyecto pretende satisfacer.

1.2. Los puentes de Königsberg

La ciudad prusiana de Königsberg (actualmente Kaliningrado en Rusia) fue fundada en el

año 1254 en las riberas del río Pregel con siete puentes que conectan sus cuatro secciones
(designadas A,B, C, y D) como se muestra en la Figura I.1. Surgió una pregunta sobre si
podría construirse un viaje redondo para visitar las cuatro secciones de la ciudad, cruzando
cada puente exactamente una vez. Una sección podría ser visitada varias veces, si fuese
necesario.

A mediados del siglo XVIII, el afamado matemático Leonhard Euler desarrolló un

argumento de “construcción de rutas” para demostrar que sí era posible construir semejante
viaje. Más tarde, a principios del siglo XIX, el mismo problema se resolvió presentando de
nuevo la situación como una red con nodos que representan las secciones y arcos (distintos)
que representan los puentes, como se muestra en la Figura I.2.

La representación en forma de red implica el hallazgo de una respuesta a la pregunta

planteada. El número de arcos incidentes en cada nodo es impar. Esto hace posible entrar y
salir de todas las secciones utilizando puentes distintos. Por consiguiente, el viaje redondo
deseado no puede realizarse1.

1
Solución general: Existe un recorrido que se inicia y termina en un nodo si el número de arcos incidentes en
cada nodo es par. Hay un viaje que se inicia en un nodo y termina en otro si el número de arcos incidentes en
estos dos nodos es impar. De lo contrario, no hay solució[Link] B. Hopkins y [Link],“The Truth about
Königsberg”, College Math Journal,Vol. 35, núm. 3, págs. 198-207, 2004.
JOSÉ ANTONIO RIVERA COLMENERO 5
Figura I.1.
Puentes de Königsberg

Figura I.2.
Representación en forma de red del problema de Königsberg.

1.3. la Matriz de Adyacencia o conectividad

La matriz de adyacencia o conectividad An × n es una matriz de tamaño n × n con n siendo el

número de nodos en la red; y a i , j =1 si existe un enlace entre los nodos i y j, y a i , j =0 en
caso contrario. La Figura 5.10a muestra un ejemplo de una red pequeña. La matriz de
adyacencia correspondiente se muestra en la Figura I.3. Tenga en cuenta que la matriz de
adyacencia es una matriz dispersa, que contiene muchos valores cero. Este es a menudo el
caso en situaciones de la vida real. Las redes sociales tienen millones de miembros, pero las
personas solo están conectadas a una pequeña cantidad de amigos; por ejemplo, Twitter
tiene 500 millones de usuarios, y cada usuario sigue aproximadamente a otros 200 usuarios.

JOSÉ ANTONIO RIVERA COLMENERO 6

Figura I.3.
Representación matemática de (a) una red de muestra: (b) la matriz de adyacencia o
conectividad; (c) la Matriz de Peso; (d) la lista de adyacencia; y (e) la lista de peso

1.4. Redes Sociales

Aunque en el ejemplo de los puentes de Königsberg, las redes son construidas y

desarrolladas por humanos, no son sociales. Una pregunta clave aquí es: “¿Qué hace que
una red sea social?” En general, podríamos decir que una red es social cuando los
actores son personas o grupos de personas. Una conexión entre actores se basa en
cualquier forma de interacción social entre ellos, como una amistad. Al igual que en el
mundo real, las redes sociales también pueden reflejar la intensidad de una relación entre
las personas. ¿Qué tan bien conoces a tus contactos? La relación entre los dos mejores
amigos difiere completamente de la relación entre dos conocidos lejanos. Esas relaciones y
su intensidad son una fuente importante de intercambio de información.

El psicólogo Stanley Milgram midió en 1967 cuán social es el mundo entero. Dirigió un
experimento de Small World en el que distribuyó 100 cartas a personas de todo el mundo.
La tarea en cuestión era devolver la carta a un destino específico, que era uno de los amigos
de Milgram. En lugar de devolver la carta por correo, las personas solo podían pasar la
carta a alguien que conocían. Esta persona, en su turno, tuvo que reenviar la carta a uno de
JOSÉ ANTONIO RIVERA COLMENERO 7
sus contactos, y así sucesivamente ... hasta que la carta llegó a su destino final. Milgram
demostró que, en promedio, cada carta llegó a su destino dentro de seis pasos o caminos. Es
decir, se necesitan menos de seis personas para conectar a dos personas al azar en la red.
Esta es la longitud de ruta promedio de la red. El resultado del experimento es ampliamente
conocido como el teorema de los seis grados de separación. Milgram también encontró
que muchas cartas alcanzaron su destino en tres pasos. Este es el llamado efecto de
canalización. Algunas personas son conocidas y por muchas otras personas, a menudo de
grupos de contactos muy diversos (por ejemplo, trabajo, amigos, pasatiempos). Esas
personas son superestrellas sociométricas, que se conectan a diferentes partes de la red.
Muchos de los caminos en la red pasan a través de estas personas, lo que les otorga una alta
puntuación de intermediación.

Si bien el teorema de los seis grados de separación se basa en los resultados de la vida real,
muchos estudios ya demostraron que una longitud de ruta promedio de seis es una
sobreestimación en las redes sociales en línea. Esos estudios informaron una longitud de
ruta promedio de aproximadamente cuatro pasos o caminos entre dos personas al azar en
una red social en línea (Kwak et al. 2010). Las redes sociales en línea son, por lo tanto, más
densas que las redes de la vida real. Sin embargo, la intensidad entre las relaciones puede
ser muy diferentes.

JOSÉ ANTONIO RIVERA COLMENERO 8

 Capítulo 1
Análisis de Redes

En el mundo real, a menudo nos enfrentamos a una red y deseamos examinar algunas de
sus propiedades con el fin de obtener una idea más clara de lo que realmente estamos
tratando. Esto es particularmente cierto cuando se trata de redes grandes que exhiben
estructuras aparentemente aleatorias. Veremos con más detalle algunas de estas redes, pero
antes de hacerlo, analizaremos algunas de las técnicas básicas que podemos usar para
analizar esas estructuras.

El análisis de redes es un campo de investigación emergente, a menudo basado en el uso de

varias herramientas y métodos matemáticos (ver, por ejemplo, Brandes y Erlebach [2005]),
y también se considera como una subárea de lo que se conoce como minería de datos de
gráficos [Cook and Holder, 2007]. A continuación, consideramos varias métricas utilizadas
en una gran variedad de ciencias para analizar redes. Comenzamos por enfocarnos en los
grados de un nodo, y luego nos acercamos a las estadísticas de distancia. Un concepto
importante que se utiliza para caracterizar muchas redes del mundo real es la agrupación en
clústeres o grupos, que se analiza a continuación. Después de eso, prestamos atención a la
noción de centralidad, que es particularmente importante para redes sociales.

JOSÉ ANTONIO RIVERA COLMENERO 9

Debe quedar claro que puede haber muchas formas diferentes de dibujar una red. En
primer lugar, no hay ninguna razón por la que nos limitemos a los puntos y líneas, aunque
es una práctica común hacerlo. En segundo lugar, no hay, en principio, reglas sobre dónde
colocar los nodos dibujados, ni hay reglas que establezcan que una línea debe dibujarse de
manera recta. Sin embargo, la forma en que dibujamos las redes es a menudo importante
cuando se trata de visualizar ciertos aspectos.

Una propiedad importante de un nodo es la cantidad de arcos que inciden en él. Este
número se llama el grado de un nodo.

1.1 Descripción y características de las redes

En algunos problemas de optimización puede ser útil representar el problema a través
de una red: rutas de vehículos, distribución de productos, programa de actividades en
un proyecto, redes de comunicación, etc.

RED: Es un conjunto de nodos (N) y arcos (A) que conectan los nodos. Se denota
por G = (N, A).

RED G(N, A) es DIRIGIDA si sus arcos tienen una flecha en un lado del arco: Un arco
(i, j) es dirigido si conecta i con j pero no j con i.
Nodo, Arco,
vértice, Arista,
punto. Enlace.

i j
Nodo fuente, Nodo destino,
origen, inicial, final, llegada, etc.
salida, etc.

Los nodos se numeran 1,2 , … , n. Los arcos se denotan por (i , j) indicando que el flujo
va del nodo i al nodo j.

1.2 Grado de un nodo

Quizás uno de los puntos de inicio más simples para el análisis de redes es observar los
grados del nodo. El uso de grados nos permite identificar los actores clave en las redes
sociales: aquellos nodos con un alto grado de nodo.

JOSÉ ANTONIO RIVERA COLMENERO 10

 DEFINICIÓN: Dada una red G = (N, A), compuesto por nodos (N) y arcos (A),
diremos que dos nodos n1 , n2 ∈ N son vecinos si { n 1 , n2 } ∈ A . El grado de un nodo
es el número de vecinos que tiene en la red.

Si el grado de un nodo es 0, diremos que es un nodo aislado.

En la matriz de vecindades [ P ], para determinar el grado de un nodo, basta

sumar los unos que aparezcan en su fila.

Teorema 1.1: Handshaking Lemma. Para toda red G, la suma de todos los grados de los
vértices o nodos es igual al doble del número de arcos, es decir,

∑ gr ( v )=2|A (G)|
n ∈N (G )

Prueba. En cualquier grafo o red, cada arco o arista tiene dos extremos, por lo que
contribuye exactamente con 2 a 1 suma de los grados de vértice.

En este caso, suponemos que la red V (G) está formada por los vértices o nodos v1 , v 2 , … , v n
, la notación, ∑ gr ( v ) se interpreta como:
v ∈V (G)

∑ gr ( v )=gr ( v 1) + gr ( v 2) + …+ gr ( v n )
v ∈V (G)

Ejemplo 1.1. Grado de un nodo

Construya cuatro redes con ocho nodos, todos de grado tres.

FIGURA 1.1.
Redes con nodos de grado tres.

Si consideramos la Figura 1.1, se tienen 8 nodos y cada nodo tiene grado 3. Entonces se
tienen (8)(3) = 24 arcos en la red. Si ahora sumamos los arcos de la red, son 12 arcos en
cada una de las redes de la Figura 1.1. Luego, 2(12) = 24

JOSÉ ANTONIO RIVERA COLMENERO 11

 Ejemplo 1.2. Grado de un nodo
Considere la red G de la siguiente Figura 1.2. En la red G se verifica que:
gr ( a )=3=gr ( c ) , gr ( b )=2=gr ( e) y gr ( d )=4.

FIGURA 1.2.
Grados de los nodos de una red G.

Ejemplo 1.3. Grado de un nodo

Consideremos la Figura 1.3. En este caso, debido a que hay cuatro arcos en el nodo 1
tenemos que gr ( n1 )=4 . Podemos elaborar la Tabla 1.1 considerando cada nodo de
la Figura 1.3

FIGURA 1.3.
Un ejemplo de una red con ocho nodos y 18 arcos.

JOSÉ ANTONIO RIVERA COLMENERO 12

 Nodo Grado Arcos incidentes Vecinos
n1 4 ( n 1 , n2 ) , ( n1 , n5 ) , ( n1 ,n 6 ) , ( n1 , n7 ) n2 , n5 , n6 , n7
n2 4 ( n 1 , n2 ) , ( n2 , n3 ) , ( n2 ,n 5 ) , ( n2 , n 8 ) n1 , n3 , n5 ,n 8
n3 3 ( n 2 , n3 ) , ( n3 , n4 ) , ( n3 , n5 ) n2 , n4 , n5
n4 4 ( n 3 , n 4 ) , ( n4 , n5 ) , ( n4 , n7 ) , ( n4 , n8 ) n3 , n5 , n7 , n8

n5
( n 1 , n5 ) , ( n2 , n5 ) , ( n3 , n5 ) , ( n4 , n5 ) , ( n5 , n6 ) , n1 , n2 , n3 , n 4 , n6 ,n 7 , n 8
7
( n 5 , n7 ) , ( n 5 , n8 )
n6 4 ( n 1 , n6 ) , ( n5 , n6 ) , ( n6 , n7 ) , ( n6 , n8 ) n1 , n5 , n7 ,n 8
n7 5 ( n 1 , n7 ) , ( n 4 ,n 7 ) , ( n5 ,n 7 ) , ( n6 , n7 ) , ( n7 , n8 ) n1 , n4 , n5 , n6 , n8
n8 5 ( n 2 , n8 ) ( n 4 , n8 ) , ( n5 , n8 ) , ( n6 , n8 ) , ( n7 , n8 ) n2 , n4 , n5 , n6 , n7
Suma 36

TABLA 1.1.
Un ejemplo de una red con ocho nodos y 18 aristas.

Cuando sumamos los grados de todos los nodos de G, encontramos que la suma total es 36,
que es exactamente el doble del número de aristas. Esto nos lleva al Teorema 1.1.

1.3. Matriz de vecindades o de adyacencia y número de paseos

o caminos
1.3.1. Grafo o red dirigida y matriz de adyacencia o de vecindades

Considere el siguiente digrafo o red dirigida y su correspondiente matriz de adyacencia:

1 2 3 4

1 0 1 0 1

2 1 0 1 1

3 0 1 0 1

4 1 1 1 0
FIGURA 1.4.
Grafo o red dirigida y su representación en una matriz de adyacencia

En el lado derecho de la Figura 1.4 se tiene la red dirigida con cuatro nodos o vértices, y en
el lado derecho se tiene una matriz con cuatro filas y cuatro columnas, es decir, una matriz

JOSÉ ANTONIO RIVERA COLMENERO 13

de 4  4. Los números que aparecen en la matriz de adyacencia se refieren al número de
arcos que unen los nodos correspondientes en la red. Por ejemplo:
Los nodos 1 y 2 están unidos por 1 arco. Así que se tiene un 1 en el renglon 1 columna 2,
y en el renglón 2 columna 1.
Los nodos 1 y 4 están unidos por un arco. Así que se tiene un 1 en el renglon 1 columna
4, y en el renglón 4 columna 1, y así sucesivamente.

Se generaliza esta idea de la manera siguiente:

Definición
Sea G una red con vvértices o nodos etiquetados 1 ,2 , 3 , … , n.
La matriz de adyacencia A(G) de G es entonces una matriz n × n en la que la entrada en la
fila i y la columna j es el número de arcos que unen los vértices o nodos i y j .

1.3.2. Número de paseos

Definición: Un paseo de una distancia en un grafo o red es una sucesión de k arcos de la
forma:
uv , vw , wx , … , yz .

Esta caminata se denota mediante uvwx ... yz , y se conoce como un paseo entre uy z .

Figura 1.5.
Un paseo entre u y z.

Sean a ij las entradas de la matriz M de vecindades de una red con nodos{ P1 , P 2 , … , Pn } .

Los números a ij son 0 para cada i= j. Si i≠ j, aij será 1 si Pi es vecino de P j y 0 en caso
contrario. Consideremos la red de la Figura 1.6.

FIGURA 1.6

JOSÉ ANTONIO RIVERA COLMENERO 14

Red representativa para determinar el número de paseos y la matriz de vecindad.
La matriz de vecindades y sus primeras potencias, se calculan con Excel:

Primer paso. Se escribe la matriz de vecindad M 1 con base en la red de la Figura 1.6., y se
prepara la matriz M2 para efectuar el cálculo. Se selecciona el rango de la matriz M2 y se
escribe la función =MMULT(D3:H7,D3:H7), seleccionando dos veces el rango de la
matriz M1.

FIGURA 1.7.
Cálculo de la matriz de vecindades de dos paseos.

Segundo paso. Después de haber escrito la función =MMULT(D3:H7,D3:H7), se

presionan al mismo tiemplo las teclas Ctrl+Shift()+Enter. Entonces aparece el cálculo
de la matriz M2.

FIGURA 1.8.
Matriz de vecindades de dos paseos.

JOSÉ ANTONIO RIVERA COLMENERO 15

Tercer paso. Se calcula la matriz M 3, de igual forma que la matriz M 2. Se prepara la
matriz M3, se selecciona le rango de la matriz y se escribe la función:
MMULT(P3:T7,D3:H7).

FIGURA 1.9.
Cálculo de la matriz de vecindades de tres paseos.

Cuarto paso. Se presiona Ctrl+Shift()+Enter, para efectuar el cálculo de la matriz

M3.

FIGURA 1.10.
Matriz de vecindades de tres pasos.

Se observa que en la diagonal de M 2 aparecen los grados de cada nodo. Esto es general:
la entrada a 2ii (donde i= j coincide con el grado del nodo P1), pues el número a 2ii cuenta los
paseos de longitud 2 de Pi a Pi.

De la matriz M 3deducimos, por ejemplo, que hay seis paseos distintos de longitud tres entre
los nodos 1 y 2. Es decir, para ir del nodo 1 al nodo 2, hay seis posibilidades siguiendo
tres caminos o rutas. Los seis caminos sobre la red, son:

JOSÉ ANTONIO RIVERA COLMENERO 16

 Paseo 1. P1 → P5 → P1 → P2 : Paseo 2. P1 → P4 → P 1 → P 2 :

Paseo 3. P1 → P2 → P1 → P2 : Paseo 4. P1 → P2 → P3 → P2 :

Paseo 5. P1 → P2 → P4 → P 2 : Paseo 6. P1 → P4 → P 3 → P 2 :

FIGURA 1.11.
Matriz de vecindades de tres pasos del nodo 1 al nodo 2.

JOSÉ ANTONIO RIVERA COLMENERO 17

 Ejemplo 1.4. Número de paseos y matriz de vecindades
Sea M la matriz nodo – nodo de una gráfica dirigida:

P1 P2 P3 P4

[ ]
P1 0 1 1 1
P 1 0 0 0
M= 2
P3 0 1 0 1
P4 0 1 1 0

a) Dibuje la red dirigida.

b) Determine las conexiones de uno, dos y tres pasos del nodo P1 al nodo P4.
Verifique sus resultados listando la conexión.
c) Repita la parte b. para las conexiones de uno, dos y tres pasos del nodo P3 al nodo
P4.

Las respuestas a las preguntas son:

a) Una representación de la red dirigida asociada a la matriz nodo – nodo es:

b) Las matrices de dos y tres pasos, se obtienen con Excel.

JOSÉ ANTONIO RIVERA COLMENERO 18

 Conexiones de: P1→P4: m114 =1 ; m214 = 1; m314 =2
1 paseo: P1 → P4
2 paseos: P1 → P3 → P4
3 paseos: P1 → P2 → P1 → P4
P1 → P4 → P3 → P4

d) Conexiones de : P3→P4 : m34 =1 ; m234 =0 ; m334 = 2

1 paseo: P3 → P4
2 paseos: No es posible
3 paseos: P3 → P4 → P3 → P4
P3 → P2 → P1 → P4

Ejemplo 1.5. Número de paseos y matriz de vecindades en el

movimiento del caballo en un tablero de ajedrez
Matriz nodo-nodo del movimiento del caballo en un tablero de ajedrez reducido.
Considere el movimiento de un caballo en un tablero de ajedrez reducido como se
muestra a continuación:

Suponga que las posiciones del ajedrez han sido previamente identificadas (9 posiciones)
y lo que se desea es determinar las posiciones finales del caballo después de un
movimiento, dado que conocemos su posición inicial. ¿Qué sucede si tenemos dos
movimientos? Recuerde que un caballo se mueve en forma de L y cambia de un color a
otro color en su posición como se muestra a continuación:

JOSÉ ANTONIO RIVERA COLMENERO 19

 Sugerencia. Construya la matriz nodos-nodos o bien en este caso una matriz posición-
posición, que denotaremos por M.

a) Dibuje la red dirigida.

b) Determine las conexiones de uno, dos y tres pasos de la posición P1 a la posición

P6. Verifique sus resultados listando las distintas conexiones.

c) Repita la parte b. para las conexiones de uno, dos y tres pasos de la posición P3 a
la posición P4.

a) La matriz posición-posición es.

P1 P2 P3 P4 P5 P6 P7 P8 P9 P1 P2 P3 P4 P5 P6 P7 P8 P9
P1 0 0 0 0 0 1 0 1 0 P1 2 0 1 0 0 0 1 0 0
P2 0 0 0 0 0 0 1 0 1 P2 0 2 0 1 0 1 0 0 0
P3 0 0 0 1 0 0 0 1 0 P3 1 0 2 0 0 0 0 0 1
M , M2=
= P4 0 0 1 0 0 0 0 0 1 P4 0 1 0 2 0 0 0 1 0
P5 0 0 0 0 0 0 0 0 0 P5 0 0 0 0 0 0 0 0 0
P6 1 0 0 0 0 0 1 0 0 P6 0 1 0 0 0 2 0 1 0
P7 0 1 0 0 0 1 0 0 0 P7 1 0 0 0 0 0 2 0 1
P8 1 0 1 0 0 0 0 0 0 P8 0 0 0 1 0 1 0 2 0
P9 0 1 0 1 0 0 0 0 0 P9 0 0 1 0 0 0 1 0 2

P1 P2
P1 P2 P3 P4 P5 P6 P7 P8 P9
P1 0 1 0 1 0 3 0 3 0
P4 P3
P2 1 0 1 0 0 0 3 0 3
P3 0 1 0 3 0 1 0 3 0
M3= P4 1 0 3 0 0 0 1 0 3
P5
P5 0 0 0 0 0 0 0 0 0
P6 3 0 1 0 0 0 3 0 1
P7 0 3 0 1 0 3 0 1 0
P8 3 0 3 0 0 0 1 0 1 P6
P7
P9 0 3 0 3 0 1 0 1 0

P8 P9

b) P1→P6 : m16 =1 ; m216 = 0; m316 =3.

1 paso: P1 → P6
2 pasos: No es posible.
JOSÉ ANTONIO RIVERA COLMENERO 20
 3 pasos: P1 → P6 → P1 → P6
P1 → P6 → P7 → P6
P1 → P8 → P1 → P6

c) P3→P4 : m34 =1 ; m234 = 0 ; m334 =3.

1 paso: P3 → P4
2 pasos: No es posible
3 pasos: P3 → P4 → P9 → P4
P3 → P8 → P3 → P4
P3 → P4 → P3 → P4

1.4 Grafo o red completa

Si un grafo o red con v vértices o nodos tiene todos los ( v2) posibles arcos, diremos que
estamos ante el grafo completo con v vértices o nodos, entonces:

v (v −1)
()
K n= v =
v!
2 2 ! ( v −2 ) !
=
2

son los posibles arcos con v vértices o nodos.

1.5 Grafo o red bipartita completa

Una clase de grafos o redes que tienen relevancia en diversos problemas (por ejemplo, en
los problemas de asignación de tareas y en los de transporte), son los llamados grafos o
redes bipartitas. Se trata de aquellos en los que podemos partir el conjunto de nodos en
dos clases (por ejemplo, nodos de origen y nodos de destino), de manera que no haya
arcos entre los nodos de la misma clase.

Un grafo bipartito completo es un grafo bipartito en que cada uno de los nodos de una de
las particiones es adyacente con cada uno de los nodos de la otra partición. Cuando las
particiones tengan n y m nodos, llamaremos K n , m al grafo o red bipartita completa. Un caso
particular es el de los grafos bipartitos completos, que nombraremos como K o , d , los
subíndices indican o = origen, d = destino. En el siguiente dibujo aparece un K 4,6 :

JOSÉ ANTONIO RIVERA COLMENERO 21

FIGURA 1.12.
Grafo o red bipartita con orígenes y destinos.

Un grafo o red K o , d consta de o+ d nodos, divididos en dos clases (de origen y de destino);
e incluye los o × d arcos que van de los nodos de un tipo a los del otro.

1.7. Problemas Resueltos

PROBLEMA RESUELTO 1
Problema de los servicios públicos. En este problema, tres vecinos en disputa desean
conectar sus casas a tres empresas de servicios públicos de gas, agua y electricidad de tal
manera que las nueve conexiones no se crucen entre sí en el plano. En el siguiente
diagrama, aparecen ocho conexiones, pero la casa B no está conectada a la red de agua.
¿Se puede insertar la conexión que falta como se requiere?

FIGURA 1.13.
Conexión a los servicios públicos.

JOSÉ ANTONIO RIVERA COLMENERO 22

Observación. En grafos o redes la terminología no es completamente estándar; algunos
autores usan un nodo o punto para lo que llamamos un vértice, y una línea o arco para lo
que llamamos una arista.

El problema de los servicios se puede representar mediante un grafo o red con seis nodos
(o vértices), correspondientes a las tres casas y los tres servicios, y nueve arcos,
correspondientes a las nueve conexiones posibles. (Tenga en cuenta que las tres casas no
están unidas entre sí, y tampoco lo son los tres servicios públicos). El siguiente problema es
el de encontrar otro dibujo que no implique el cruce de arcos.

FIGURA 1.14.
Distribución de los tres servicios públicos: gas, agua y electricidad.

PROBLEMA RESUELTO 2
Considere el siguiente sistema de calles de un solo sentido en una ciudad.

FIGURA 1.15.
Sistema de calles de un solo sentido

JOSÉ ANTONIO RIVERA COLMENERO 23

Debido a que todas las calles son unidireccionales, podemos representar este sistema
mediante un diagrama en el que colocamos flechas en las líneas para indicar las direcciones
de las calles de un solo sentido. Este diagrama se denomina digrafo, una abreviación de
grafo o red dirigida.

Un dígrafo es un diagrama que consta de puntos, llamados vértices o nodos, unidos por
líneas dirigidas, llamados arcos o aristas; cada arco une exactamente dos vértices o
nodos.

FIGURA 1.16.
Digrafo o red dirigida del sistema de calles de un solo sentido

1.8. Problemas Propuestos

1-1. Dibuje la red representada por cada una de las siguientes matrices de adyacencia o de
vecindades (matrices M 1):
1 2 3 4 5 6

[ ]
1 2 3 4 5

[ ]
1 0 1 1 1 0 1
1 0 1 0 1 1
2 1 0 0 1 1 0
2 1 0 1 1 1
3 1 0 0 1 1 1
3 0 1 0 0 1
4 1 1 1 0 1 0
4 1 1 0 0 1
5 0 1 1 1 0 1
5 1 1 1 1 0
6 1 0 1 0 1 0

Nota: La matriz de adyacencia de un grafo o red es simétrica con respecto a la

diagonal principal. También , para una red sin ciclos, cada entrada en la diagonal
principal es 0, y la suma de las entradas en cualquier fila o columna es igual al grado
del vértice o nodo correspondiente a ese renglón o columna.

JOSÉ ANTONIO RIVERA COLMENERO 24

1-2. Considere el siguiente digrafo o red dirigida:

Escriba la matriz de adyacencia o vecindad M 1, calcule las matrices de 2, 3 y 4

paseos o caminos, es decir, M 2 , M 3 y M 4 , y entonces encuentre los números de
paseos o caminos de longitudes 1, 2, 3 y 4 del nodo b al nodo d .

1-2. Dibuje la red representada por cada una de las siguientes matrices de adyacencia o de
vecindades (matrices M 1):

[ ]
1 2 3 4 5 6 7 8 1 2 3 4 5 6

[ ]
1 0 1 1 1 1 0 0 0 1 0 1 0 1 0 1
2 1 0 1 1 0 0 0 1 2 1 0 1 1 1 0
3 0 1 0 0 1 0 0 1 3 1 0 0 1 0 1
4 1 1 0 0 0 1 0 1 4 1 0 1 0 1 0
5 1 1 1 1 0 0 0 0 5 0 1 0 1 0 1
6 0 1 0 0 1 0 0 1 6 0 0 1 0 1 0
7 0 0 1 1 1 0 0 0
8 1 0 1 0 1 0 1 0

1-3. Considere el siguiente digrafo o red dirigida:

Escriba la matriz de adyacencia o vecindad M 1, calcule las matrices de 2, 3 y 4

paseos o caminos, es decir, M 2 , M 3 y M 4 , y entonces encuentre los números de
paseos o caminos de longitudes 1, 2, 3 y 4 del nodo u al nodo w .

JOSÉ ANTONIO RIVERA COLMENERO 25

 Capítulo 2
El Problema de Transporte
(Transportation Problem)

Problema de transporte
Los costos de transporte son un gasto significativo en el costo total del producto que varía
en promedio alrededor del 5% del precio total de los productos manufacturados. Por lo
tanto, es imperativo que el planificador intente mantener estos costos en el nivel más bajo
posible.

2.1 DEFINICIÓN DEL MODELO DE TRANSPORTE

La red que aparece en la Figura 2.1. representa el problema de transporte. Hay m orígenes
y n destinos, cada uno representado por un nodo. Los arcos representan las rutas que unen
los orígenes con los destinos. El arco (i , j) que une el origen i con el destino j transporta
dos piezas de información: el costo de transporte por unidad, c ij y la cantidad transportada,
x ij. La cantidad de la oferta en el origen i es O i y la cantidad de la demanda en el destino j
es D j. El objetivo del modelo es minimizar el costo de transporte total al mismo tiempo
que se satisfacen las restricciones de la oferta y la demanda.

JOSÉ ANTONIO RIVERA COLMENERO 26

FIGURA 2.1.
Representación del modelo de transporte con nodos y arcos (red bipartita).

En este capítulo, nos referiremos al “problema” del transporte como una estructura
específica, mientras que reconocemos que es solo uno de los muchos escenarios de
transporte que pueden aplicarse en cualquier situación. La estructura básica del problema
de transporte es la siguiente. Por un lado, tenemos los Orígenes Oi ,i=1,2 , … , mOi, en los
cuales están disponibles los suministros de un solo producto. Por el otro lado están los
Destinos D j=1,2 , … ,n en los que los clientes demandan bienes en cantidades d j. Los
envíos de productos solo son posibles directamente desde un origen a un destino, no se
permiten desvíos y no se pueden combinar las entregas. El transporte de una sola unidad
desde el origen Oi al destino D j se supone que cuesta c ij Unidades Monetarias (UM). Se
supone que los costos de transporte son lineales. Esta situación se puede visualizar como se
muestra en la Figura 2.1.

Por ahora, asumiremos que el transporte está equilibrado, es decir, que la oferta total es
igual a la demanda total. Más formalmente, requerimos que:
m n

∑ s i= ∑ d j .
i=1 j=1

Con las suposiciones anteriores, ahora deseamos minimizar los costos totales de transporte,
dado que todas las demandas están satisfechas. Para formular el problema, primero
definimos las variables x ij como la cantidad enviada (directamente) desde el origen O i hasta
el destino D j. El problema puede escribirse como:

Modelo de Programación Lineal para Transporte:

JOSÉ ANTONIO RIVERA COLMENERO 27

Función objetivo:
m n
Minimizar z=∑ ∑ cij xij
i=1 j=1
Sujeto a las restricciones:

De oferta o suministro:
n

∑ x ij=si , ∀ i=1,2 , … , m
j=1

De demanda o requerimientos:
m

∑ x ij=d j , ∀ j =1,2, … , n
i=1

Variables de no negatividad:
x ij ≥ 0 , todas las i y j .

Se debe tener en cuenta que el problema del transporte estándar, como se muestra en la
fórmula anterior tiene mn variables y (m+n) restricciones estructurales. Sin embargo, una
restricción es redundante, que se puede ver fácilmente sumando las primeras restricciones
masí como las siguientes n restricciones. Los resultados serán la oferta y la demanda
totales, respectivamente. La suposición de un problema equilibrado requiere que estos dos
sean iguales.

Ejemplo 2.1 MG Auto

MG Auto cuenta con tres plantas en Los Ángeles, Detroit y Nueva Orleáns, y dos
importantes centros de distribución en Denver y Miami. Las capacidades trimestrales de
las tres plantas son 1000, 1500 y 1200 automóviles, y las demandas de los dos centros de
distribución durante el mismo periodo son de 2300 y 1400 automóviles. Las distancias en
millas entre las plantas y los centros de distribución aparecen en la Tabla 2.1.

TABLA 2.1 Distancias en millas de orígenes a destinos

DESTINO
ORIGEN Denver Miami
Los Ángeles 1,000 2,690
Detroit 1,250 1,350
Nueva Orleáns 1,275 850

La compañía transportista cobra 8 centavos por milla por automóvil. En la Tabla 2.2 se dan
los costos de transporte por automóvil en las diferentes rutas, redondeados al dólar más
cercano.

JOSÉ ANTONIO RIVERA COLMENERO 28

 TABLA 2.2 Costo de transporte por automóvil
DESTINO
ORIGEN Denver Miami
Los Ángeles 0.081,000 = $80 0.082,690 = $215
Detroit 0.081,250 = $100 0.081,350 = $108
Nueva Orleáns 0.081,275 = $102 0.08850 = $68

La red asociada con este problema de trabsporte se muestra en la Figura 2.2.

FIGURA 2.2
Representación del modelo de transporte con nodos y arcos

La estructura especial del problema de transporte permite una representación compacta del
problema utilizando el formato tabla de transporte que aparece en la Tabla 1.3.

Denver Miami Oferta

80 215
Los Ángeles x 11 x 12 1,000
100 108
Detroit x 21 x 22 1,500
102 68
Nueva Orleans x 31 x 32 1,200
Demanda 2,300 1,400

TABLA 2.3
Modelo de transporte de MG.

El modelo de Programación Lineal (PL) del problema de transporte es:

JOSÉ ANTONIO RIVERA COLMENERO 29

 1.- El número de arcos nos indican el número de variables de la función objetivo,
en este problema se tienen 6 arcos, por lo tanto se tienen, 6 variables para la
cantidad enviada.
2.- El número de nodos nos indican el número de restricciones. En este problema
se tienen tres nodos de oferta y dos nodos de demanda, por lo tanto, 3 + 2 = 5
restricciones: tres de oferta y dos de demanda.
3.- La función objetivo se formula multiplicando cada variable de la cantidad
enviada por su costo asociado en el arco respectivo y sumando.

Función objetivo

La función objetivo se forma con los valores de Costo unitario-Cantidad enviada sobre los
arcos, se tienen 7 arcos con estas dos variables.

Minimizar Z =80 x11 +215 x 12+100 x 21+108 x 22+102 x31 +68 x 32.

Restricciones

Todas estas restricciones son ecuaciones porque la oferta total desde los tres orígenes
(= 1,000 +1,500 + 1,200 =3,700 automóviles) es igual a la demanda total en los dos
destinos (= 2,300 + 1,400 = 3,700 automóviles). Se tienen cinco nodos, por lo tanto, se
tienen igual número de restricciones.

De oferta:

x 11 +¿ x12 ¿ ¿ ¿ ¿ ¿ 1,000 ( Los Ángeles )

=¿ 1,200(Nueva Orleans)¿
x 21 +¿ x 22 ¿ ¿ ¿ ¿ x 31 ¿

De demanda:

x 11 ¿ + ¿ x 21 ¿ +¿ x31 ¿ ¿ 2,300 ( Denver )

x 12 ¿ + ¿ x 22 ¿ +¿ x32 ¿ ¿ ¿

Restricciones de no negatividad:

x ij ≥ 0 ,i=1,2,3 , j=1,2

Solucion con el software QM para Windows Versión 4

JOSÉ ANTONIO RIVERA COLMENERO 30

Paso 1. Se activa el software QM for Windows desde el escritorio.

FIGURA 2.4
Logo del software QM para Windows versión 4.

Paso 2. Del menú del software “QM para Windows”, se selecciona el Módulo
“Transportation”.

FIGURA 2.5
Selección del menú principal del módulo Transportation (Transporte).

Paso 2. Se selecciona el menú “File” (Archivo) y después “New”.

JOSÉ ANTONIO RIVERA COLMENERO 31

FIGURA 2.6
Creación de un nuevo archivo de transporte.

Paso 3. En la ventana crear el conjunto de datos para el transporte, se indican los nodos de
Oferta (Number of Origins) igual a 3 y lo nodos de Demanda (Number of Destinations)
igual a 2. Se presiona el botón “OK”.

FIGURA 2.7
Ventana para crear un conjunto de datos para transporte

Paso 4. Se ingresan los datos de los costos, de la oferta y de la demanda, se cambian los
nombres de los orígenes, destinos, de oferta y de demanda. Se selecciona el botón de
Minimizar (Minimize)Se presiona el botón “Solve” dentro del menú principal.

JOSÉ ANTONIO RIVERA COLMENERO 32

FIGURA 2.8
Tabla donde se capturan los datos del problema de transporte.

Paso 5. La solución óptima, obtenida con QM para Windows envía 1,000 automóviles de
Los Ángeles a Denver (x 11=1,000), 1300 de Detroit a Denver (x 21=1,300), 200 de Detroit
a Miami ( x 22=200) y 1,200 de Nueva Orleáns a Miami (x 32=1,200). El costo de transporte
mínimo asociado se calcula como:

Función objetivo=1,000 × $ 80+1,300 × $ 100+200 × $ 108+1,200 × $ 68

¿ $ 80,000+ $ 130,000+$ 21,600+ $ 81,600=$ 313,200 .

FIGURA 2.9.
Solución del problema de transporte

La red asociada de costo unitario y la cantidad enviada es:

JOSÉ ANTONIO RIVERA COLMENERO 33

FIGURA 2.10
La red representativa del Costo en cada arco o ruta de la red de transporte.

Valor de la función objetivo: $80,000 + $130,000 + $21,600 + $81,600 = $313,200.

FIGURA 2.11
Red que muestra la solución del problema con los costos asociados a cada arco.

Ejemplo 2.2 POWERCO

Powerco tiene tres centrales eléctricas que cubren las necesidades de cuatro ciudades.
Cada central suministra los números siguientes de kilowatts-hora (kwh) de electricidad:
planta 1 – 35 millones; planta 2 – 50 millones; planta 3 – 40 millones (ver la Tabla 1.4).
Las demandas de potencia pico en estas ciudades, que ocurren al mismo tiempo (2 pm),
son como sigue (en kwh): ciudad 1 – 45 millones; ciudad 2 – 20 millones; ciudad 3 – 30
millones, ciudad 4 – 30 millones (ver la Tabla 1.4). Los costos por enviar un millón de
kwh de electricidad de la planta a la ciudad dependen de la distancia que debe viajar la
electricidad.

JOSÉ ANTONIO RIVERA COLMENERO 34

 TABLA 2.4. Costos de envío, suministros y demanda para POWERCO
A Suministros
De (millones de
Ciudad 1 Ciudad 2 Ciudad 3 Ciudad 4 kwh)
Planta 1 8 UM 6 UM 10 UM 9 UM 35
Planta 2 9 UM 12 UM 13 UM 7 UM 50
Planta 3 14 UM 9 UM 16 UM 5 UM 40
Demanda
(millones de 45 20 30 30 UM
kwh)

Formule un modelo de programación lineal para minimizar el costo de satisfacer la

demanda de potencia pico de cada ciudad.

En forma de red este problema se representaría de la siguiente forma:

Figura 2.12.
Representación de la red de transporte en equilibro: Oferta = Demanda.

Con los costos asociados a los envíos, la red quedaría de la siguiente forma:

JOSÉ ANTONIO RIVERA COLMENERO 35

Figura 2.13.
Red de transporte con los costos unitarios de envío y variables de decisión.

SOLUCIÓN:

Para escribir la función objetivo, en la red anterior se observa que se tienen 12 arcos, por lo
tanto, se tienen 12 variables de decisión x ij.

De la red podemos observar que se tienen 3 nodos de oferta, por lo tanto, se tienen tres
restricciones de oferta, y del lado derecho de la red, se tienen cuatro nodos de demanda,
por consiguiente, se tienen cuatro restricciones de demanda.

Para formular el problema de Powerco como un programa lineal, se comienza por definir
una variable para cada decisión que debe tomar Powerco. Debido a que Powerco debe
determinar cuánta potencia se envía desde cada planta a cada ciudad, se define para los
nodos de oferta: i=1 , 2 ,3 y para los nodos de demanda: j=1 ,2 , 3 , 4 .

x ij =¿ número de (millones) de kwh producidos en la planta i y enviados a la ciudad j.

En términos de estas variables, el costo total de suministrar las demandas de potencia pico a
las ciudades 1 a 4 podrían escribirse como:

Función objetivo (flujo sobre los arcos):

Costo de enviar potencia desde la planta 1: 8 X 11 +6 X 12 +10 X 13 +9 X 14

Costo de enviar potencia desde la planta 2: +9 X 21 +12 X 22 +13 X 23+ 7 X 24

JOSÉ ANTONIO RIVERA COLMENERO 36

 Costo de enviar potencia desde la planta 3: +14 X 31+ 9 X 32+16 X 33+5 X 34
Powerco enfrenta dos tipos de restricciones. Primera, la potencia total suministrada por
cada planta no puede exceder la capacidad de la planta. Por ejemplo, la cantidad total de
potencia enviada desde la planta 1 a las cuatro ciudades no puede pasar de 35 millones de
kwh. Cada variable con subíndice 1 representa un envío de potencia desde la planta 1, de
modo que se podría expresar esta restricción como:

X 11 + X 12 + X 13 + X 14 ≤ 35

De manera similar, se determinan las restricciones que reflejan las capacidades de las
plantas 2 y 3. Debido a que ambas centrales suministran potencia, cada una es un punto de
suministro. De manera análoga, una restricción que asegura que la cantidad total enviada
desde una planta no excede su capacidad es una restricción de suministro o de oferta. La
formulación de programación lineal del problema de Powerco contiene las tres
restricciones de suministro siguientes:

Restricciones de Oferta (todo lo que sale de las plantas 1, 2 y 3):

Restricción de oferta de la planta 1: X 11 + X 12 + X 13 + X 14 ≤ 35

Restricción de oferta de la planta 2: X 21 + X 22 + X 23 + X 24 ≤ 50
Restricción de oferta de la planta 3: X 31 + X 32 + X 33 + X 34 ≤ 40

Segunda, son necesarias restricciones que aseguren que cada ciudad recibirá potencia
suficiente para satisfacer su demanda pico. Cada ciudad demanda potencia, así que cada
una es un punto de demanda. Por ejemplo, la ciudad 1 debe recibir por lo menos 45
millones de kwh. Cada variable con segundo subíndice 1 representa un envío de potencia a
la ciudad 1, así que se obtiene la restricción siguiente:

X 11 + X 21 + X 31 ≥ 45

Del mismo modo, se obtiene una restricción para cada una de las ciudades 2, 3 y 4. Una
restricción que asegura que una ubicación que recibe su demanda es una restricción de
demanda. Powerco debe satisfacer las siguientes cuatro restricciones de demanda:
Restricciones de Demanda (todo lo que envían las plantas a las ciudades 1, 2 y 3):

Restricción de demanda de la ciudad 1: X 11 + X 21 + X 31 ≥ 45

Restricción de demanda de la ciudad 2: X 12 + X 22 + X 32 ≥20
Restricción de demanda de la ciudad 3: X 13 + X 23+ X 33 ≥ 30
Restricción de demanda de la ciudad 4: X 14 + X 24 + X 34 ≥30

x
Debido a que las ij deben ser no negativas, se suman las restricciones:
x ij≥0 , (i = 1, 2, 3 ; j = 1, 2, 3, 4).
Al combinar la función objetivo, las restricciones de suministro, demanda y de no negatividad se
obtiene la formulación del programa lineal siguiente para el problema de Powerco.

JOSÉ ANTONIO RIVERA COLMENERO 37

Función objetivo:

Minimizar Z= 8 X 11 +6 X 12 +10 X 13 +9 X 14 +9 X 21 +12 X 22 +13 X 23 + 7 X 24

+14 X 31+ 9 X 32+16 X 33+5 X 34
Sujeto a:

Restricciones de Oferta:

X 11 + X 12 + X 13 + X 14 ≤ 35
X 21 + X 22 + X 23 + X 24 ≤ 50
X 31 + X 32 + X 33 + X 34 ≤ 40

Restricciones de Demanda:

X 11 + X 21 + X 31 ≥ 45
X 12 + X 22 + X 32 ≥20
X 13 + X 23 + X 33 ≥ 30
X 14 + X 24 + X 34 ≥30

x ij ≥ 0 ,(i=1,2,3 ; j=1,2,3,4)

Cuya solución óptima se muestra es la siguiente:

Valor de la función objetivo: Z = 1,020

Variable Valor
X 11 0
X 12 10
X 13 25
X 14 0
X 21 45
X 22 0
X 23 5
X 24 0
X 31 0
X 32 10
X 33 0
X 34 30
Suma: 1,020 UM

La Figura 2.14 es una representación gráfica del problema de Powerco y su solución

óptima. La variable X ij se representa por una línea o arco, que une el i-ésimo punto de
oferta (planta i) y el j-ésimo punto de demanda (ciudad j).

JOSÉ ANTONIO RIVERA COLMENERO 38

Figura 2.14.
Representación de la red con los costos y flujos sobre los arcos

Por último, se presenta la red de transporte óptima, al eliminar los arcos sin flujo o con
flujo 0(cero).

Figura 2.15.
JOSÉ ANTONIO RIVERA COLMENERO 39
Representación gráfica del problema de Powerco y su solución óptima.
Ejemplo 2.3 Envío de automóviles de las plantas a cuatro regiones
La compañía de automóviles Grand Prix fabrica automóviles en tres plantas y los envía a
cuatro regiones de un país. Las plantas suministran las cantidades listadas en la columna
derecha de la Tabla 2.5. Las demandas de los consumidores por región se listan en la fila
inferior de esta tabla, y los costos unitarios por enviar un automóvil de cada planta a cada
región se listan en la parte media de la tabla. Grand Prix quiere encontrar el plan de
envío a costo mínimo que satisfaga las demandas de las cuatro regiones sin que se
sobrepasen las capacidades de las plantas.

TABLA 2.5. Datos para el ejemplo de Grand Prix

A Suministros
De
Región 1 Región 2 Región 3 Región 4 (unidades)

Planta 1 131 218 266 120 450

Planta 2 250 116 263 278 600
Planta 3 178 132 122 180 500
Demanda(unidades) 450 200 300 300

Objetivo: Desarrolle el modelo de programación lineal de transporte que determine la

forma de enviar los automóviles a costo mínimo de las plantas a las regiones sin que se
excedan las capacidades de producción y se cumpla con las demandas de las regiones.
Sugerencia: Represente el problema de Grand Prix como un modelo de redes

Solución:

Figura 2.16.

JOSÉ ANTONIO RIVERA COLMENERO 40

Representación del problema de Grand Prix como un modelo de redes.
Función objetivo:

Minimizar Z =131 X 11+ 218 X 12+266 X 13+120 X 14 + ¿

250 X 21 +116 X 22 +263 X 23+ 278 X 24 +¿
178 X 31 +132 X 32+122 X 33 +180 X 34

La formulación de programación lineal del problema de Grand Prix contiene las tres
restricciones de suministro u oferta y las cuatro restricciones de demanda, siguientes:

Restricciones de Oferta (todo lo que sale de las plantas 1, 2 y 3):

Restricción de oferta de la planta 1: X 11 + X 12 + X 13 + X 14 ≤ 450

Restricción de oferta de la planta 2: X 21 + X 22 + X 23 + X 24 ≤ 600
Restricción de oferta de la planta 3: X 31 + X 32 + X 33 + X 34 ≤ 500

Restricciones de Demanda (todo lo que llega a cada región proveniente de las

plantas 1, 2, 3 y 4):

X 11 + X 21 + X 31 ≥ 450
X 12 + X 22 + X 32 ≥200
X 13 + X 23 + X 33 ≥ 300
X 14 + X 24 + X 34 ≥300
Debido a que las x ij deben ser no negativas:

x ij ≥ 0 ,(i=1,2,3 ; j=1,2,3,4)

Al combinar la función objetivo, las restricciones de suministro, demanda y de no

negatividad se obtiene la formulación del Programa Lineal siguiente para el problema de
Grand Prix.

Función objetivo:

Minimizar Z = 131 X 11+ 218 X 12+266 X 13+120 X 14 + ¿

250 X 21 +116 X 22 +263 X 23+ 278 X 24 +178 X 31+ 132 X 32 +122 X 33+ 180 X 34

Sujeto a:

Restricciones de Oferta:

X 11 + X 12 + X 13 + X 14 ≤ 450
X 21 + X 22 + X 23 + X 24 ≤ 600
X 31 + X 32 + X 33 + X 34 ≤ 500

Restricciones de Demanda:

JOSÉ ANTONIO RIVERA COLMENERO 41

 X 11 + X 21 + X 31 ≥ 450
X 12 + X 22 + X 32 ≥200
X 13 + X 23 + X 33 ≥ 300
X 14 + X 24 + X 34 ≥300

x ij ≥ 0 ,(i=1,2,3 ; j=1,2,3,4)

Figura 2.17.
Representación gráfica del problema de Grand Prix, solución óptima.

Solución con el software QM para Windows Versión 4

Paso 1. Del menú del software “QM para Windows”, se selecciona el Módulo
“Transportation”.

JOSÉ ANTONIO RIVERA COLMENERO 42

FIGURA 2.18
Módulos de QM para Windows, selección del módulo Transportation (Transporte).

Paso 2. Se selecciona el menú “File” (Archivo) y después “New”.

FIGURA 2.19.
Selección para resolver un nuevo problema de Transporte (Transportation).

Paso 3. En la ventana Crear el conjunto de datos para transporte (Create data set
transportation), se escribe el título del problema que se va a resolver “GRAND PRIX”. Se
indica el número orígenes (Number of Origins), 3. Se indica el número de destinos
(Number of Destinations). Se selecciona minimizar, “Minimize”. En el nombre de los
renglones (Row names) se deja el que tiene, después se podrá cambiar el nombre sobre
escribiendo. Se presiona el botón “OK”.
JOSÉ ANTONIO RIVERA COLMENERO 43
FIGURA 2.20.
Ventana para crear un conjunto de datos para el problema de transporte de Grand Prix.

Paso 4. Se ingresan las variables de costos, las cantidades suministradas y las cantidades
demandadas. Se presione el botón “Solve”:

FIGURA 2.21
Captura de las variables de decisión, función objetivo y restricciones del modelo de transporte.

JOSÉ ANTONIO RIVERA COLMENERO 44

Paso 5. La solución óptima, obtenida con QM para Windows es:

Función objetivo: 176,050 UM.

FIGURA 2.22
Resultados obtenidos con QM para Windows para el problema de Grand Prix.

2.1. Problemas Propuestos

2-1. Los tres bancos de sangre en el Condado de Franklin se coordinan a través de una
oficina central que facilita la entrega de sangre a cuatro hospitales en la región. El
costo de enviar un contenedor estándar de sangre de cada banco a cada hospital se
muestra en la tabla siguiente. También se incluyen el número de contenedores de dos
semanas disponibles en cada banco y el número de contenedores de sangre cada dos
semanas que se necesitan en cada hospital. ¿Cuántos envíos deben hacerse cada dos
semanas de cada banco de sangre a cada hospital para que los costos totales de envío
se minimicen?

Tabla para el problema 2-1.

HASTA
DESDE HOSPITAL HOSPITAL HOSPITAL HOSPITAL
OFERTA
1 2 3 4
BANCO 1 $8 $9 $11 $16 50
BANCO 2 12 7 5 8 80
BANCO 3 14 10 6 7 120
DEMANDA 90 70 40 50

JOSÉ ANTONIO RIVERA COLMENERO 45

2-2. Finnish Furniture fabrica mesas en instalaciones ubicadas en tres ciudades: Reno,
Denver y Pittsburgh. Luego, las mesas se envían a tres tiendas minoristas ubicadas en
Phoenix, Cleveland y Chicago. La gerencia desea desarrollar un programa de
distribución que satisfaga las demandas al menor costo posible. El costo de envío por
unidad de cada una de las fuentes a cada uno de los destinos se muestra en la
siguiente tabla:

Tabla para el problema 2-2

HASTA
DESDE
PHOENIX CLEVELAND CHICAGO
RENO 10 16 19
DENVER 12 14 13
PITTSBURGH 18 12 12

Los suministros u ofertas disponibles son 120 unidades de Reno, 200 de Denver y
160 de Pittsburgh. Phoenix tiene una demanda de 140 unidades, Cleveland tiene una
demanda de 160 unidades y Chicago tiene una demanda de 180 unidades. ¿Cuántas
unidades deben enviarse desde cada instalación de fabricación a cada una de las
tiendas minoristas si se minimiza el costo? ¿Cuál es el costo total?

2-3. Considere el problema de transporte con los siguientes costos unitarios y

capacidades. Encuentre la solución óptima.

Destino
Fuente Suministro
A B C
1 5 1 6 200
2 8 4 3 350
3 7 9 5 170
Demanda 220 300 200

La red asociada al problema de transporte se muestra en la siguiente figura.

Fuentes Destinos
5
1 1 A
(200) 6 (220)

8
2 4 B
3
(350) (300)
7 9
5
3 C
(170) (200)

JOSÉ ANTONIO RIVERA COLMENERO 46

2-4. La Compañía de Petróleo ABC, cuenta con tres puntos para el almacenamiento del
petróleo y debe abastecer cuatro puntos de demanda. La gerencia necesita un
programa para su envío, de tal forma que se minimice el costo total por transporte sin
que se excedan las capacidades de almacenamiento. Se supone que las capacidades y
los costos unitarios por envío son los que se muestran en la tabla siguiente. ¿Cuál es
el programa óptimo para la distribución del petróleo desde los puntos de
almacenamiento hasta los de demanda, que minimice el costo total por transporte?

Tabla para el problema 2-3: Capacidades y costos unitarios de la compañía “ABC”.

PUNTOS DE DEMANDA
CAPACIDAD DE
ALMACENAMIENTO
Dallas Kansas Tampa Miami ABASTECIMIENTO

Boston 5 4 5 6 100
Denver 3 3 6 6 200
Austin 2 5 7 8 400
DEMANDA 200 100 150 250

La tabla anterior la podemos representar en forma gráfica como se muestra en la

siguiente figura.

Abastecimiento Demanda
(Unidades) Costo por unidad enviada (Unidades)
Dallas 200
5
100 Boston
4
5
6
Kansas 100
3 3
200 Denver 6
6

2 5 Tampa 150
7
400 Austin 8

Miami 250

NODOS FUENTE NODOS DE DESTINO

2-5. Considere el problema de distribución, en el cual los costos unitarios por transporte,
las demandas y los abastecimientos; se muestran en la siguiente tabla. Encuentre la
solución óptima.

JOSÉ ANTONIO RIVERA COLMENERO 47

 DESTINO
FUENTE SUMINISTRO
Austin Columbus Dallas Boston Los Ángeles
New York 100 50 90 30 130 30,000
Chicago 90 30 70 50 110 20,000
Pittsburgh 95 30 75 40 120 20,000
DEMANDA 10,000 12,000 15,000 17,000 25,000

2-6. La Compañía Lechera “DIHO” cuenta con dos granjas, las cuales abastecen de leche
a tres supermercados locales. Las demandas para cada uno de los supermercados
Eureka, Casa Matriz y El Rey de las Verduras, durante un período de reparto, son:
6,000, 4,000 y 3,800 litros, respectivamente. Estas granjas tienen una capacidad de
producción de 8500 y 6500 litros de leche, respectivamente; por período de entrega.
Las distancias que hay de las granjas a los supermercados, se listan en la siguiente
tabla. La Compañía Lechera “DIHO” necesita un programa de entrega, de manera
que se minimice el costo total por transporte del producto. Suponiendo, que el costo
unitario por transporte es proporcional a la distancia recorrida.

SUPERMERCADO
GRANJA SUMINISTRO
Eureka Casa Matriz El Rey
Feliz 5 kms 10 kms 7 kms 8,500 litros
Paseo 13 kms 5 kms 11 kms 6,500 litros
DEMANDA 6,000 4,000 3,000

2-7. Localización de una nueva fábrica de Hardgrave Machine [Link] Hardgrave

Machine Company produce componentes de computadora en sus plantas en
Cincinnati, Salt Lake y Pittsburgh. Estas plantas no han sido capaces de satisfacer la
demanda de pedidos de los cuatros almacenes de Hardgrave en Detroit, Dallas,
Nueva York y Los Ángeles. Por consiguiente, la empresa ha decidido construir una
nueva planta para expandir su capacidad productiva. Los nuevos sitios considerados
son Seattle y Birmingham, ambas ciudades atractivas en términos de oferta de mano
de obra, servicios municipales y facilidad de financiamiento para la fábrica.

La Tabla 2.7.1. presenta los costos de producción y requerimientos de oferta de cada

una de las tres plantas existentes, la demanda que debe satisfacer cada uno de los
cuatro almacenes y los costos de producción estimados de las nuevas plantas
propuestas. Los costos de transporte de cada planta a cada almacén se resumen en la
Tabla 2.7.2.

JOSÉ ANTONIO RIVERA COLMENERO 48

 TABLA 2.7.1 DATOS DE DEMANDA Y OFERTA DE HARDGRAVE
DEMANDA COSTO PARA
MENSUAL PLANTA DE OFERTA PRODUCIR UNA
ALMACÉN (UNIDADES) PRODUCCIÓN MENSUAL UNIDAD ($)
Detroit 10,000 Cincinnati 15,000 48
Dallas 12,000 Salt Lake 6,000 50
Nueva York 15,000 Pittsburgh 14,000 52
Los Ángeles 9,000
Total 46,000 35,000
Oferta requerida de la nueva planta = 46,000 – 35,000 = 11,000 unidades por mes

COSTO DE PRODUCCIÓN ESTIMADO POR

UNIDAD EN LAS PLANTAS PROPUESTAS
Seatle $53
Birmingham $49

TABLA 2.7.2 COSTOS DE ENVÍO DE HARDGRAVE

A NUEVA LOS
DETROIT DALLAS
DE YORK ÁNGELES
CINCINNATI $25 $55 $40 $60
SALT LAKE 35 30 50 40
PITTSBURGH 36 45 26 66
SEATTLE 60 38 65 27
BIRMINGHAM 35 30 41 50

La importante pregunta que ahora enfrenta Hardgrave es ésta: ¿cuál de las nuevas
localizaciones redituará el costo más bajo para la empresa en combinación con las plantas y
almacenes existentes? Observe que el costo de cada ruta individual planta a almacén se
encuentra mediante la suma de los costos de envío (de la Tabla 6.2) a los costos de
producción por unidad respectivos (de la Tabla 6.1). Por lo tanto, el costo total de
producción más el costo de envío de un componente de computadora de Cincinnati a
Detroit es de $73 ($25 del costo por el envío más $48 por producir una unidad en
Cincinnati). En las Tablas 2.7.3 y 2.7.4 se muestran los costos totales para Birmingham y
Seattle.

Se deben resolver dos problemas de transporte para encontrar la nueva planta con el
menor costo de producción y envío del sistema.

Para determinar cuál planta nueva (Seattle o Birmingham) ofrece el costo total de
distribución y producción más bajo para todo el sistema, se resuelven dos problemas de

JOSÉ ANTONIO RIVERA COLMENERO 49

 transporte, uno para cada una de las dos posibles combinaciones.
Planta de Birmingham:
TABLA 2.7.3 COSTOS TOTALES DE HARDGRAVE: PRODUCCIÓN MÁS ENVÍO
A NUEVA LOS OFERTA
DETROIT DALLAS
DE YORK ÁNGELES MENSUAL
CINCINNATI 48 + 25 = 73 48 + 55 = 103 48 + 40 = 88 60 + 48 = 108 15,000
SALT LAKE 35 + 50 = 85 30 + 50 = 80 50 + 50 = 100 40 + 50 = 90 6,000
PITTSBURGH 36 + 52 = 88 45 + 52 = 97 26 + 52 = 78 66 + 52 = 118 14,000
BIRMINGHAM 35 + 49 = 84 30 + 49 = 79 41 + 49 = 90 50 + 49 = 99 11,000
DEMANDA
10,000 12,000 15,000 9,000 46,000
MENSUAL

Planta de Seattle:
TABLA 2.7.4 COSTOS TOTALES DE HARDGRAVE: PRODUCCIÓN MÁS ENVÍO
A NUEVA LOS OFERTA
DETROIT DALLAS
DE YORK ÁNGELES MENSUAL
CINCINNATI 48 + 25 = 73 48 + 55 = 103 48 + 40 = 88 60 + 48 = 108 15,000
SALT LAKE 35 + 50 = 85 30 + 50 = 80 50 + 50 = 100 40 + 50 = 90 6,000
PITTSBURGH 36 + 52 = 88 45 + 52 = 97 26 + 52 = 78 66 + 52 = 118 14,000
SEATTLE 60 + 53 = 113 38 + 53 = 91 65 + 53 = 118 27 + 53 = 80 11,000
DEMANDA
10,000 12,000 15,000 9,000 46,000
MENSUAL

Oferta Demanda Oferta Demanda

73 73
Cincinnati Detroit Cinc innati Detroit
103 103
15,000 10,000 15,000 10,000
108 88 108 88

85 85
80 80
Salt Lake Dallas Salt La ke Dallas
100 100
6,000 90 12,000 6,000 12,000
90

88 97 88 97
78 78
Pittsburgh Nueva York Pittsburgh Nueva York
118 118
14,000 15,000 14,000 15,000

84 79 113 91
90 118

Birmingham Los Ángeles Seatle Los Ángeles

99 80
11,000 9,000 11,000 9,000

Birmingham Seattle

JOSÉ ANTONIO RIVERA COLMENERO 50

 Redes de transporte asociadas con las plantas de Seattle y Birmingham

Capítulo 3
El Problema de Asignación
(Assignment Problem)
Un problema de asignación se puede ver como un problema de transporte en el que la
capacidad de cada fuente (o persona a asignar) es 1 y la demanda en cada destino (o trabajo
a realizar) es 1. Este tipo de problema es muy fácil de resolver utilizando el método de
asignación.

Como ilustración del método de asignación, considere el caso de Fix-It Shop, que acaba
de recibir tres nuevos proyectos urgentes para reparar: (1) un radio, (2) un horno
tostador, y (3) una mesa para café rota. Las tres personas que reparan, cada uno con
diferentes talentos y habilidades, están disponibles para hacer los trabajos. El propietario de
Fix-It Shop calcula lo que le costará en salarios asignar a cada uno de los trabajadores a
cada uno de los tres proyectos. Los costos, que se muestran en la Tabla 3.1, difieren porque
el propietario cree que cada trabajador diferirá en velocidad y habilidad en estos trabajos
tan variados.

El problema de asignación: el objetivo es asignar proyectos a personas (un proyecto a

una persona), de manera que se minimice el costo total.

PROYECTO
PERSONA 1 2 3
Arturo $11 $14 $6
Benito 8 10 11
Carlos 9 12 7

TABLA 3.1
Costos de los proyectos de reparación estimados para el problema de asignación de Fix-It
Shop.

El objetivo del dueño es asignar los tres proyectos a los tres trabajadores, de una manera
que resulte en el costo total más bajo para Fixt-It Shop. Tenga en cuenta que la asignación
de personas a proyectos debe ser individualizada, es decir, debe ser una relación uno a uno;
cada proyecto será asignado exclusivamente a un trabajador. Por lo tanto, el número de filas

JOSÉ ANTONIO RIVERA COLMENERO 51

siempre debe ser igual al número de columnas en la tabla de costos de un problema de
asignación.
Una manera de resolver problemas (pequeños) es numerar todos los resultados
posibles.

ASIGNACIÓN DE PROYECTOS COSTOS DE MANO COSTOS

1 2 3 DE OBRA ($) TOTALES ($)
Arturo Benito Carlos 11 + 10 + 7 28
Arturo Carlos Benito 11 + 12 + 11 34
Benito Arturo Carlos 8 + 14 + 7 29
Benito Carlos Arturo 8 + 12 + 6 26
Carlos Arturo Benito 9 + 14 + 11 34
Carlos Benito Arturo 9 + 10 + 6 25

TABLA 3.2
Resumen de las alternativas y los costos de asignación para Fix-It Shop

Debido a que el problema de Fix-It Shop solo consiste en tres trabajadores y tres proyectos,
una manera fácil de encontrar la mejor solución es enumerar todas las asignaciones posibles
y sus costos respectivos. Por ejemplo, si se asigna a Arturo al proyecto 1, Benito al
proyecto 2 y Carlos al proyecto 3, el costo total será $11+ $10 + $7 = $28. La Tabla 3.2
resume las seis opciones de asignación. La tabla también muestra que la solución de
menor costo sería asignar a Carlos al proyecto 1, Benito al proyecto 2 y Arturo al
proyecto 3, a un costo total de $25.

La obtención de soluciones por enumeración funciona bien para problemas pequeños, pero
rápidamente se vuelve ineficiente a medida que los problemas de asignación se hacen más
grandes. Por ejemplo, un problema que involucra la asignación de cuatro trabajadores a
cuatro proyectos requiere que consideremos 4! (= 1  2 × 3  4), o bien, 24 alternativas.
En un problema con ocho trabajadores y ocho tareas, que en realidad no es tan grande en
una situación realista, produce 8! (=1  2  3  4  5  6  7  8), o bien, ¡40,320
soluciones posibles! Es evidente que no sería práctico comparar tantas alternativas, se
necesita un método de solución más eficiente y la mejor manera de resolver el problema es
con QM para Windows versión 4.

3.1. Programa lineal para el ejemplo de asignación

La red en la Figura 3.1 representa un problema que enfrenta Fix-It Shop, que acaba de
recibir tres nuevos proyectos de reparación que deben completarse rápidamente: (1) una
radio, (2) un horno tostador y (3) una mesa de café. Tres personas de reparación, cada
una con diferentes talentos, están disponibles para hacer los trabajos. El propietario de la
tienda calcula el costo en salarios si los trabajadores están asignados a cada uno de los tres
proyectos. Los costos difieren debido a los talentos de cada trabajador en cada uno de los

JOSÉ ANTONIO RIVERA COLMENERO 52

trabajos. El propietario desea asignar los trabajos para minimizar el costo total y cada
trabajo debe tener una persona asignada, y cada persona solo puede asignarse a un trabajo.

FIGURA 3.1.
Ejemplo de un problema de asignación en un formato de red de transporte para Fix-It Shop.

Al formular esto como un programa lineal, se puede usar la forma PL general del problema
de transporte. Al definir las variables, sean:

Las variables especiales 01 se utilizan con el modelo de asignación.

{
x ij = 1 sila persona ies asignadaal proyecto j
0 de otra manera
donde:
i=1,2,3 , con 1= Arturo , 2=Benito , y 3=Carlos
j=1,2,3 , con1=Proyecto 1, 2=Proyecto 2 , y 3=Proyecto 3.
La formulación con programación lineal es:

Minimizar el costo total = 11 x11 +14 x 12+6 x 13 +8 x 21 +10 x 22

+11 x 23 +9 x 31+12 x 32+7 x 33
Sujeto a:

JOSÉ ANTONIO RIVERA COLMENERO 53

 x 11 +¿ x 12 +¿ x13 ≤ 1
x 21 +¿ x 22 +¿ x23 ≤ 1
x 31 +¿ x 32 +¿ x33 ≤ 1
x 11 +¿ x 21 +¿ x31 ¿ 1
x 12 +¿ x 22 +¿ x32 ¿ 1
x 13 +¿ x 23 +¿ x33 ¿ 1

x ij =0 o 1 para toda i y j .
Cuya solución es: x 13=1, por lo que Arturo se asigna al proyecto 3; x 22=1, entonces Benito
se asigna al proyecto 2; y x 31 =1, por lo que Carlos está asignado al proyecto 1. Todas las
demás variables son 0. El costo total es de $ 25.

3.2. Un problema de asignación es equivalente a un problema de

transporte con cada oferta y demanda igual a 1.

Solución con el software QM para Windows Versión 4

Paso 1. Del menú del software “QM para Windows”, se selecciona el Módulo
“Transportation”.

FIGURA 3.2.
Módulos de QM para Windows, selección del Módulo Transportation (Transporte).

JOSÉ ANTONIO RIVERA COLMENERO 54

Paso 2. Se selecciona el menú “File” (Archivo) y después “New”.

FIGURA 3.3.
Selección para crear un nuevo modelo de Transporte (Transportation).

Paso 3. En la ventana Crear el conjunto de datos para Transporte (Create data set
Transportation), se escribe el título del problema que se va a resolver “Fix-It Shop”. Se
indica el número orígenes (Number of Origins), 3. Se indica el número de destinos
(Number of Destinations), 3. Se selecciona Minimizar, “Minimize”. En el nombre de los
renglones (Row names) se deja el que tiene, después se podrá cambiar el nombre sobre
escribiendo. Se presiona el botón “OK”.

FIGURA 3.4.
Ventana para crear el conjunto de datos para el modelo de Transporte de Fix-It Shop.

Paso 4. Se ingresan las variables de costos, las cantidades de Oferta y de Demanda para
Fix-It Shop. Se presione el botón “Solve”:

JOSÉ ANTONIO RIVERA COLMENERO 55

FIGURA 3.5
Captura de los datos de los costos, de la Oferta y de la Demanda para Fix-It Shop.

Paso 5. La solución óptima, obtenida con QM para Windows es:

FIGURA 3.6
Asignación óptima para Fix-It Shop. Arturo-Proyecto 3 (costo $6), Benito-Proyecto 2 (costo $10) y
Carlos-Proyecto 1 (costo $9). Con un Costo óptimo de $25.

3.1. Problemas Propuestos

31. El equipo de astronautas de la NASA actualmente incluye a 10 especialistas en
misiones que tienen un doctorado en astrofísica o astromedicina. Se asignará uno de
estos especialistas a cada uno de los 10 vuelos programados para los próximos nueve
meses. Los especialistas de la misión son responsables de llevar a cabo experimentos
científicos y médicos en el espacio o de lanzar, recuperar o reparar satélites. El jefe
del personal de astronautas, un ex miembro de la tripulación con tres misiones en su
haber, debe decidir quién debe ser asignado y entrenado para cada una de las
JOSÉ ANTONIO RIVERA COLMENERO 56
 diferentes misiones. Claramente, los astronautas con educación médica son más
adecuados para misiones que involucran experimentos biológicos o médicos,
mientras que aquellos con títulos orientados a la ingeniería o la física son los más
adecuados para otros tipos de misiones. El jefe asigna a cada astronauta una
calificación en una escala de 1 a 10 para cada misión posible, con un 10 que es una
combinación perfecta para la tarea en cuestión y un 1 como una falta de coincidencia.
Solo se asigna un especialista a cada vuelo, y ninguno se reasigna hasta que todos los
demás hayan volado al menos una vez.

(a) ¿A quién debe asignarse a qué vuelo?

(b) La NASA acaba de recibir la notificación de que Anderson se va a casar en
febrero y ese mes se le concedió una gira de publicidad muy solicitada en
Europa. (Tiene la intención de llevar a su esposa y dejar que el viaje se duplique
como una luna de miel). ¿Cómo cambia esto el horario final?
(c) Certo se ha quejado de que fue desvalorizado en sus misiones de enero. Ambas
calificaciones deben ser de 10, afirma el jefe, quien acepta y vuelve a calcular el
calendario. ¿Ocurren cambios en el programa establecido en la parte (b)?
(d) ¿Cuáles son las fortalezas y debilidades de este enfoque para la programación?

Datos para el problema 31

MISIÓN
ENE. ENE. FEB. FEB MAR. ABR. MAY. JUN. AGO. SEP.
ASTRONAUTA 12 27 5 26 26 12 1 9 20 19
Vincze 9 7 2 1 10 9 8 9 2 6
Veit 8 8 3 4 7 9 7 7 4 4
Anderson 2 1 10 10 1 4 7 6 6 7
Herbert 4 4 10 9 9 9 1 2 3 4
Schatz 10 10 9 9 8 9 1 1 1 1
Plane 1 3 5 7 9 7 10 10 9 2
Certo 9 9 8 8 9 1 1 2 2 9
Moses 3 2 7 6 4 3 9 7 7 9
Brandon 5 4 5 9 10 10 5 4 9 8
Drtina 10 10 9 7 6 7 5 4 8 8

3-2. La Compañía de Servicios en Computación Austin (CSCA) le proporciona servicio a

cuatro clientes. Los clientes se designan con las letras A, B, C, y D, respectivamente.
CSCA cuenta con cuatro técnicos capacitados para proporcionar este servicio.
Debido a las diferentes especialidades de estos técnicos, su tiempo de servicio varía
de acuerdo con cada cliente específico. Los posibles tiempos de servicio se muestran
en la siguiente tabla. El gerente de CSCA quiere determinar un programa de
asignación que minimice el tiempo total de servicio para sus cuatro clientes.

Tabla para el problema 3-2: Tiempo de servicio en horas.

CLIENTE
TÉCNICO
A B C D
José 3 6 7 10
Pedro 5 6 3 8
Toshi 2 8 4 16

JOSÉ ANTONIO RIVERA COLMENERO 57

 Rudy 8 6 5 9

Analice el problema. Los coeficientes de costos se muestran en la tabla. El objetivo es

minimizar el tiempo total del servicio.

3-3. La siguiente tabla de asignación muestra los costos asociados con la realización de
tres trabajos que efectuarán tres distintos obreros. Se supone que a cada persona se le
asigna un trabajo. Resuelva este problema de asignación.

Obrer Obrero
o 1 2 3
A 10 12 25
B 19 20 22
C 15 26 17

3-4. Resuelva el siguiente problema de asignación no balanceado. M representa una

penalización muy grande por hacer la asignación. (Ayuda: Use un número que sea
mucho mayor que cualquier número de la tabla para representar a M). Todos los
números en la tabla representan costos.

Trabajador
Tarea
A B C D E
1 11 19 M 19 20
2 38 M 15 14 10
3 23 17 21 M M
4 31 37 28 35 46
5 27 43 23 18 M
6 15 21 33 17 28

3-5. Un lunes por la mañana, llegan cinco automóviles al taller mecánico “Super Garage”
para que les den servicio. Cada uno de los cinco mecánicos que trabajan en el taller
pueden dar el servicio requerido a cualquiera de los automóviles. El número de horas
requerido para que cada mecánico le proporcione servicio a cada automóvil se
muestra en la siguiente tabla. ¿Cuál es el tiempo total mínimo, si a cada mecánico se
le asigna un coche para darle servicio?

MECÁNICO
AUTOMOVIL
Hugo Francisco Luis Juan Mario
Ford 6 5 4.5 5.5 6
Chevrolet 4 3.5 5 4.5 3
Toyota 2 3.5 3.5 4 3
VW 5 4.5 3.5 4 5

JOSÉ ANTONIO RIVERA COLMENERO 58

 BMW 4 6 5.5 4.5 6

Capítulo 4
El Problema deTransbordo
(Transshipment Problem)
4.1 DEFINICIÓN DEL MODELO DE TRANSBORDO
En un problema de transporte, si los artículos que se transportan deben pasar por un
punto intermedio (llamado punto de transbordo) antes de llegar a un destino final, el
problema se denomina problema de transbordo. Por ejemplo, una empresa podría estar
fabricando un producto en varias fábricas para enviarlo a un conjunto de centros de
distribución regionales. Desde estos centros, los artículos se envían a los puntos de venta
minoristas que son los destinos finales.

Ejemplo 4.1. Transbordo de manifestantes

Un partido político de México desea transportar 1,500 manifestantes desde dos
municipios M1 y M2. En el municipio M1 se tienen en la lista de manifestantes a 800
personas y en el municipio M2 a 700. Los manifestantes se desplazarán desde el norte de
México y pernoctarán en dos Alcaldías de la Ciudad de México A1 y A2. Al día
siguiente se desplazarán hasta tres destinos D1, D2 y D3, donde pernoctarán y al día
siguiente harán sus manifestaciones. En el lado derecho de la Figura 4.1., se muestra el
número de manifestantes que se requieren para apoyar al partido político. Los costos
asociados en cientos de pesos por transportar cada manifestante de un lugar a otro se
muestran sobre los arcos (flechas).

JOSÉ ANTONIO RIVERA COLMENERO 59

FIGURA 4.1.
Representación del modelo de transbordo para el transporte de manifestantes.
El sistema que se muestra en la Figura 1.2.1. está desbalanceado la Oferta = 800 + 700 =
1,500, es diferente a la Demanda = 450 + 350 + 300 = 1,100, se tiene mayor oferta que
demanda, por eso se tienen restricciones de desigualdad “” en las restricciones de Oferta.

Los costos unitarios asociados con los gastos por transporte y de viáticos de los
manifestantes aparecen sobre los arcos. El partido político desea minimizar los costos de
transporte asociados con el acarreo de personas para satisfacer la demanda de
manifestantes en los tres destinos. En la Tabla 4.1., se presentan los datos de la red en
forma tabular.

Tabla 4.1. Forma tabular del modelo de transbordo

DESDE/HASTA A1 A2 D1 D2 D3 OFERTA
M1 4 7 0 0 0 800
M2 5 7 0 0 0 700
A1 0 0 6 4 5 0
A2 0 0 2 3 4 0
DEMANDA 450 350 300

Minimizar Costo :
4 M 1 A 1+7 M 1 A 2+5 M 2 A 1+7 M 2 A 2+6 A 1 D 1+4 A 1 D 2+ 5 A 1 D 3+2 A 2 D 1+ 3 A 2 D 2+ 4 A 2 D3

Sujeto a las siguientes restricciones:

A) Nodos de oferta (M):

M1: M1A1 + M1A2  800

M2: M2A1 + M2A2  700

B) Nodos de transbordo de oferta-demanda (A):

Aquí se cumple el principio “Todo lo que entra es igual a todo lo que sale”:

FIGURA 4.2.
Lo que entra es igual a lo que sale, si metes un conejo al sombrero, sacas un conejo.

JOSÉ ANTONIO RIVERA COLMENERO 60

A1: M1A1 + M2A1 = A1D1 + A1D2 + A1D3

De donde, tenemos que pasar todas las variables que están en el lado derecho, al lado
izquierdo:

M1A1 + M2A1  A1D1  A1D2  A1D3 = 0

A2: M1A2 + M2A2 = A2D1 + A2D2 + A2D3

De donde, tenemos que pasar todas las variables que están en el lado derecho, al lado
izquierdo

M1A2 + M2A2  A2D1  A2D2  A2D3 = 0

C) Nodos de demanda (D):

D1: A1D1 + A2D1 = 450

D2: A1D2+ A2D2 = 350
D3: A1D3 + A2D3 = 300

Solución con el software QM para Windows Versión 4

Paso 1. Del menú del software “QM para Windows”, se selecciona el Módulo “Linear
Programming”, es decir, Programación Lineal.

JOSÉ ANTONIO RIVERA COLMENERO 61

FIGURA 4.3.
Módulos de QM para Windows, selección de Linear Programming.
Paso 2. Se selecciona el menú “File” (Archivo) y después “New”.

FIGURA 4.4.
Selección para crear un nuevo modelo de Programación Lineal (PL)

Paso 3. En la ventana Crear el conjunto de datos para Programación Lineal, se escribe

el título del problema que se va a resolver “ACARREO DE MANIFESTANTES”. Se
indica el número de restricciones de acuerdo con el número de nodos: 2 de oferta, 2 de
transbordo y 3 de demanda que suman 7 restricciones. El número de variables queda
indicado por el número de arcos que tiene la red y estas se escriben en la función objetivo
con su costo asociado, 11. Se selecciona minimizar, “Minimize”. Se presiona el botón
“OK”.

FIGURA 4.5.
Ventana para crear un modelo de Programación Lineal para el acarreo de manifestantes.

JOSÉ ANTONIO RIVERA COLMENERO 62

Paso 4. Se ingresan las variables de decisión, la función objetivo y las restricciones del
modelo de Programación Lineal, se presione el botón “Solve”:

FIGURA 4.6.
Captura de las variables de decisión, función objetivo y restricciones del modelo de PL.

Paso 5. La solución óptima, obtenida con QM para Windows es:

FIGURA 4.7.
Valores de las variables y de la función objetivo proporcionados por QM para Windows del
modelo de Programación Lineal (PL).

Es decir, se envían los manifestantes por las siguientes rutas, con el costo asociado,
Función objetivo=$ 9,550 :

Tabla 1.2.2 Valores de las variables de decisión

Envío por la ruta Costo por transporte sobre el arco
M1A1 = 650 (4)(650) = 2,600
M1A2 = 150 (7)(150) = 1,050
M2A2 = 300 (7)(300) = 2,100
A1D2 = 350 (4)(350) = 1,400
A1D3 = 300 (5)(300) = 1,500
A2D1 = 450 (2)(450) = 900
Función objetivo = Costo total ($) 9,550

JOSÉ ANTONIO RIVERA COLMENERO 63

FIGURA 4.8.
Valores de las variables y costo de envío en cada arco o ruta.

FIGURA 4.9.
Red que minimiza los costos para el transbordo de manifestantes.

Ejemplo 4.2. Transbordo de maíz

Se enviarán 600 toneladas de maíz desde la región S1, y 800 toneladas desde la región S2
por ferrocarril a tres ciudades que tienen las siguientes demandas en toneladas D1 = 500,
D2 = 350 y D3 = 900. Pero antes tienen que abastecer a las regiones T1 y T4 con 200 y
100 toneladas, respectivamente. Asimismo, las zonas de riego T2 y T3 cosecharon 350 y
200 toneladas de maíz, que serán transportadas a las regiones de demanda. El costo por
transportar una tonelada de maíz, se muestra a un lado de los arcos. Se desea determinar
el envío óptimo del maíz que minimice los costos por transporte.

JOSÉ ANTONIO RIVERA COLMENERO 64

FIGURA 4.10.
Red representativa del problema de transbordo de maíz.
En la Figura 4.10, se observa que:

Oferta = 600 + 800 + 350 + 200 = 1,950 toneladas de maíz.

Demanda = 200 + 100 + 500 + 350 + 900 = 2,050 toneladas de maíz.

La red no está en equilibrio y se tendrá una demanda no satisfecha de 100 toneladas de

maíz.

La Tabla 4.2. presenta la forma tabular de la red de transbordo de la Figura 4.10.

Tabla 4.2. Forma tabular del modelo de transbordo de maíz

DESDE/HASTA T1 T2 T3 T4 D1 D2 D3 OFERTA
S1 4 2 3 0 0 0 0 600
S2 0 0 4 8 0 0 0 800
T1 0 3 1 0 0 0 0 0
T2 0 0 3 5 2 4 0 350
T3 0 0 0 2 4 7 1 200
T4 0 0 0 0 0 3 9 0
DEMANDA 200 0 0 100 500 350 900

Número de variables = Número de arcos = 17.

Número de restricciones = Número de nodos = 9.

El modelo de transporte es el siguiente:

Minimizar Costo = 4 S1T1+ 2 S1T2 + 3 S1T3 + 4 S2T3 + 8 S2T4 + 3 T1T2 +

1 T1T3 + 3 T2T3 + 5 T2T4 + 2 T2D1 + 4 T2D2 + 2 T3T4 + 4 T3D1 + 7 T3D2 + 1 T3D3 +
3 T4D2 + 9 T4D3

Sujeto a las restricciones:

A) Nodos de oferta (S):

S1: S1T1 + S1T2 + S1T3 = 600

S2: S2T3 + S2T4 = 800

B) Nodos de transbordo de oferta-demanda (T):

T1: S1T1 – 200 = T1T2 + T1T3

de donde,

JOSÉ ANTONIO RIVERA COLMENERO 65

 S1T1 – T1T2 – T1T3 = 200

T2: S1T2 + T1T2 + 350 = T2T3 + T2T4 +T2D1 + T2D2

de donde,

T2D3 + T2T4 +T2D1 + T2D2 – S1T2 – T1T2 = 350

T3: S1T3 + S2T3 + T1T3 + T2T3 + 200 = T3T4 + T3D1 + T3D2 + T3D3

de donde,

T3T4 + T3D1 + T3D2 + T3D3 – S1T3 – S2T3 – T1T3 – T2T3 = 200

T4: S2T4 + T2T4 + T3T4 –100 = T4D2 + T4D3

de donde,

S2T4 + T2T4 + T3T4 – T4D2 – T4D3 = 100

C) Nodos de demanda (D):

D1: T2D1 + T3D1  500

D2: T2D2 + T3D2 + T4D2  350
D3: T3D3 + T4D3  900

Solución con el software QM para Windows Versión 4

Paso 1. Del menú del software “QM para Windows”, se selecciona el Módulo “Linear
Programming”, es decir, Programación Lineal.

FIGURA 4.11.

JOSÉ ANTONIO RIVERA COLMENERO 66

Módulos de QM para Windows, selección de Linear Programming.
Paso 2. Se selecciona el menú “File” (Archivo) y después “New”.

FIGURA 4.12.
Selección para crear un nuevo modelo de Programación Lineal (PL)

Paso 3. En la ventana Crear el conjunto de datos para Programación Lineal, se escribe

el título del problema que se va a resolver “TRANSBORDO DE MAÍZ”. Se indica el
número de restricciones de acuerdo con el número de nodos: 2 de oferta, 4 de transbordo y
3 de demanda que suman 9 restricciones. El número de variables queda indicado por el
número de arcos que tiene la red y estas se escriben en la función objetivo con su costo
asociado, 17. Se selecciona minimizar, “Minimize”. Se presiona el botón “OK”.

FIGURA 4.13.
Ventana para crear un modelo de Programación Lineal para el transbordo de maíz.

Paso 4. Se ingresan las variables de decisión, la función objetivo y las restricciones del
modelo de Programación Lineal, se presione el botón “Solve”:

JOSÉ ANTONIO RIVERA COLMENERO 67

FIGURA 4.14.
Captura de las variables de decisión, función objetivo y restricciones del modelo de PL.

Paso 5. La solución óptima, obtenida con QM para Windows es:

FIGURA 4.15.
Valores de las variables y de la función objetivo calculados con QM para Windows del
modelo de Programación Lineal (PL)

Es decir, se envían los manifestantes por las siguientes rutas, con sus costos asociados,
Función objetivo=$ 7,900.00 :

Tabla 4.3. Valores de las variables de decisión

Envío por la ruta Costo por transporte sobre el arco
S1T1 = 200 (4)(200) = 800
S1T2 = 400 (2)(400) = 800
S2T3 = 800 (4)(800) = 3,200
T2D1 = 500 (2)(500) = 1,000
T2D2 = 250 (4)(250) = 1,000
T3T4 = 100 (2)(100) = 200
T3D3 = 900 (1)(900) = 900
Función objetivo = Costo total ($) 7,900

JOSÉ ANTONIO RIVERA COLMENERO 68

FIGURA 4.16.
Red que minimiza los costos para el transbordo de maíz.

Las cantidades enviadas son:

S1T1 = 200, S1T2 = 400, S2T3 = 800, T2D1 = 500, T2D2 = 250, T3T4 = 100, T3D3 = 900.

El costo mínimo es:

($4)(200) + ($2)(400) + ($2)(500) + ($4)(250) + ($4)(800) + ($2)(100) + ($1)(900) =
$800 + $800 + $1,000 + $1000 + $3,200 + $200 + $900 = $7,900

Ejemplo 4.3. Problema de transbordo

Resuelva el siguiente problema de transbordo que se muestra en la Figura 4.17., donde
se desea minimizar el costo total del envío de un producto. Los números en cada arco
representan los costos unitarios por envío.

FIGURA 4.17.
Red representativa del problema de transbordo.

JOSÉ ANTONIO RIVERA COLMENERO 69

La Tabla 4.4., muestra la forma tabular de la red de transbordo de la Figura 4.17.

Tabla 4.4. Forma tabular del modelo de transbordo de maíz

DESDE/HASTA T1 T2 T3 D1 D2 D3 OFERTA
S1 3 10 0 0 0 0 500
S2 6 7 15 0 0 0 900
S3 0 10 8 0 0 0 360
T1 0 5 0 15 7 0 200
T2 0 0 0 16 3 7 0
T3 0 2 0 0 18 2 160
DEMANDA 0 100 0 300 1,200 500

El modelo de programación lineal es:

Función objetivo:

Minimizar Costo = 3 S1T1 + 10 S1T2 + 6 S2T1 +7 S2T2 + 15 S2T3 + 10 S3T2 +

8 S3T3 + 5 T1T2 + 15 T1D1 + 7 T1D2 + 16 T2D1 + 3 T2D2 + 7 T2D3 + 2 T3T2 + 18 T3D2
+ 2 T3D3

Sujeto a las restricciones:

A) Nodos de oferta (S):

S1: S1T1 + S1T2 ≤ 500

S2: S2T1 + S2T2 + S2T3 ≤ 900
S3: S3T2 + S3T3 ≤ 360

B) Nodos de transbordo de oferta-demanda (T):

T1: S1T1 + S2T1 + 200 = T1T2 + T1D1 + T1D2

de donde,

T1T2 + T1D1 + T1D2  S1T1 – S2T1 = 200

T2: S1T2 + S2T2 + S3T2 + T1T2 + T3T2  100 = T2D1 + T2D2 + T2D3

de donde,

S1T2 + S2T2 + S3T2 + T1T2 + T3T2  T2D1  T2D2  T2D3 = 100

T3: S2T3 + S3T3 + 160 = T3T2 + T3D2 + T3D3

de donde,

JOSÉ ANTONIO RIVERA COLMENERO 70

 T3T2 + T3D2 + T3D3  S2T3  S3T3 = 160

C) Nodos de demanda (D):

D1: T1D1 + T2D1 = 300

D2: T1D2 + T2D2 + T3D2 = 1200
D3: T2D3 + T3D3 = 500

Solución con el software QM para Windows Versión 4

Paso 1. Del menú del software “QM para Windows”, se selecciona el Módulo “Linear
Programming”, es decir, Programación Lineal.

Paso 2. Se selecciona el menú “File” (Archivo) y después “New”.

Paso 3. En la ventana Crear el conjunto de datos para Programación Lineal, se escribe

el título del problema que se va a resolver “TRANSBORDO DE UN PRODUCTO”. Se
indica el número de restricciones de acuerdo con el número de nodos: 3 de oferta, 3 de
transbordo y 3 de demanda que suman 9 restricciones. El número de variables queda
indicado por el número de arcos que tiene la red y estas se escriben en la función objetivo
con su costo asociado, 16. Se selecciona minimizar, “Minimize”. Se presiona el botón
“OK”.

FIGURA 4.18.
Ventana para crear un modelo de Programación Lineal para el transbordo de un producto.

Paso 4. Se ingresan las variables de decisión, la función objetivo y las restricciones del
modelo de Programación Lineal, se presione el botón “Solve”:

JOSÉ ANTONIO RIVERA COLMENERO 71

FIGURA 4.19.
Captura de las variables de decisión, función objetivo y restricciones del modelo de PL.

Paso 5. La solución óptima, que se obtiene con QM para Windows es:

FIGURA 4.20.
Valores de las variables y de la función objetivo calculados con QM para Windows del
modelo de Programación Lineal (PL).

Es decir, se envían los productos por las siguientes rutas, con sus costos asociados,
Función objetivo=$ 21,220.

Tabla 4.5. Valores de las variables de decisión

Envío por la ruta Costo por transporte sobre el arco
S1T1 = 500 ($3)(500) = $1,500
S2T2 = 900 ($7)(900) = $6,300
S3T3 = 340 ($8)(340) = $2,720
T1D1 = 300 ($15)(300) = $4,500
T1D2 = 400 ($7)(400) = $2,800
T2D2 = 800 ($3)(800) = $2,400
T3D3 = 500 ($2)(500) = $ 1,000
Función objetivo = Costo total ($) $21,220

JOSÉ ANTONIO RIVERA COLMENERO 72

FIGURA 4.21.
Red que minimiza los costos para el transbordo de un producto.

4.1. Problemas Propuestos

41. Resuelva el siguiente problema de transbordo que se muestra en la Figura 4.22.,
donde se desea minimizar el costo total del envío de un producto nuevo. Los números
en cada arco representan los costos unitarios por envío.

FIGURA 4.22.
Red

representativa del problema de transbordo de un producto nuevo.

42. Resuelva el problema de transbordo que aparece en la Figura 4.23, para minimizar el
costo total. Los números en cada arco representan los costos unitarios por envío en
JOSÉ ANTONIO RIVERA COLMENERO 73
 pesos.

FIGURA 4.23.
Red representativa del problema de transbordo.

43. Considérese el gráfico que contempla las rutas posibles para ir desde la ciudad 1 hasta
la ciudad 10. Cada nodo representa una ciudad y los arcos la infraestructura vial
disponible. Las tablas contienen los costos asociados del desplazamiento entre cada
par de nodos para cada una de las etapas. Supondremos que todos los
desplazamientos tienen la misma duración, y que el viaje ha de realizarse en cuatro
etapas. Cada una de ellas se corresponde con un único desplazamiento entre un par de
nodos del grafo, así al finalizar la primera etapa estaremos en una de las ciudades 2, 3
o 4. La segunda etapa finalizará en la ciudad 5, la número 6 o la número7. La tercera
jornada nos llevará a la ciudad 8 o a la número 9. La cuarta etapa permite finalizar el
viaje en la ciudad 10.

JOSÉ ANTONIO RIVERA COLMENERO 74

FIGURA 4.24.
Red representativa del problema de transbordo.

JOSÉ ANTONIO RIVERA COLMENERO 75

 Capítulo 5
El Problema de Flujo Máximo
(Maximal Flow Problem)

En un problema de flujo máximo, el objetivo es maximizar el flujo a través de una

red. Por ejemplo, una red podría representar un sistema de caminos y carreteras, y el
objetivo podría ser maximizar la tasa (velocidad) del flujo de vehículos a través del sistema.
Otros ejemplos de redes de flujo máximo son los sistemas de tuberías que llevan gas natural
(gasoductos), petróleo (oleoductos), o agua, sistemas administrativos, las rutas aéreas,
sistemas de producción, y sistemas de distribución.

Para determinar el flujo máximo de un sistema, es necesario tener en cuenta las

capacidades de flujo de las diferentes ramas de una red. Las capacidades de las ramas
limitan el flujo a través de una rama (arco) de la red. Por lo tanto, el objetivo es determinar
la cantidad de flujo a través de cada rama que logre el máximo flujo posible para el sistema
como un todo.

Se supone que hay un sólo nodo de entrada (llamado fuente) y un sólo nodo de salida
(llamado sumidero). También se supone que hay conservación de flujo (todo lo que entra
a un nodo es igual a todo lo que sale de ese mismo nodo).

Como un ejemplo de una red de flujo máximo, considere la red mostrada en la Figura 5.1.
En dicha figura se ve que el Nodo 1 es el nodo de entrada; por consiguiente, todos los flujos
que entran en el sistema deben pasar por ese nodo. El Nodo 4 es el nodo de salida; por
consiguiente, todos los flujos que dejan el sistema deben pasar por ese nodo. Los números
de las ramas indican la capacidad de flujo de una rama en una dirección dada. Por ejemplo,
el 10 sobre la Rama 12 indica una tasa de flujo máximo posible de 10 saliendo del Nodo
1 y que fluye por esa rama. Ahora algunas ramas permiten el flujo en cualquier dirección.
Sin embargo, este no es el caso para la Rama 12; el 0 en la Rama 12 indica que no es
posible el flujo del Nodo 2 al Nodo 1. Ahora considere la Rama 23, vemos que la tasa de
flujo máximo a lo largo de esta rama es 2, y el flujo puede ser en cualquier dirección. Sin
embargo, es importante reconocer que los flujos en dichas ramas no pueden ocurrir
simultáneamente en ambas direcciones. Por consiguiente, para cualquier rama, el flujo
puede ocurrir sólo en una dirección (es decir, debe ser unidireccional), aunque puede ser
aceptable en ambas direcciones. La determinación de qué dirección, o si debe haber algún
flujo en todo, es una cuestión que se debe resolver.

JOSÉ ANTONIO RIVERA COLMENERO 76

FIGURA 5.1.
Red para el problema del oleoducto.

Algoritmo de flujo máximo

El algoritmo para el problema de flujo máximo es realmente sencillo, y consiste de
relativamente unos cuantos pasos. Éstos son:

1. Encuentre alguna ruta desde el nodo fuente al nodo sumidero que tenga una capacidad
de flujo positiva. (La capacidad de flujo de una ruta se determina por la rama con menor
capacidad a lo largo de la ruta elegida en la dirección del flujo). Si no se encuentra
dicha ruta, la solución actual es óptima. Si no se encuentra dicha ruta al inicio, ningún
flujo es posible (es decir, non existe una solución factible). Si encuentra una ruta con
flujo positivo, continúa el análisis.

2. Ajuste las capacidades de flujo de las ramas en la ruta elegida de la siguiente manera.
Para cada rama, al final donde el flujo entra en la rama, reduzca la capacidad por la
cantidad de flujo; al final de la rama donde sale el flujo, aumente la capacidad por la
cantidad de flujo. Por ejemplo, considere Rama 13:
1 3
3 0

Suponga que decidimos asignar un flujo de 3 a esta rama, fluyendo del Nodo 1 al
Nodo 3. Según la regla anterior, debemos reducir la capacidad izquierda de la rama a 0
y el lado derecho a 3. Por lo tanto, la rama revisada se parecería a:

1 3
3 0
0 3
Para claridad, pudimos haber mostrado la cantidad y dirección del flujo a través de esta
rama:
1 3
3 0
3
0 3
JOSÉ ANTONIO RIVERA COLMENERO 77
 La interpretación de la información en el extremo izquierdo de la rama revisada es que
originalmente era posible un flujo máximo de 3; ahora, ningún flujo adicional es
posible porque el flujo máximo está usándose. Si el valor revisado fuera positivo
(digamos, 2) esto indicaría que sería posible este flujo adicional de izquierda a derecha
en esta rama. En el lado derecho de la Rama 13, vemos que, originalmente, ningún
flujo era posible del Nodo 3 al Nodo 1 a través de esta rama. Esto todavía es verdad,
aunque el valor revisado es un 3. El 3 indica cuánto del flujo actual puede invertirse.
Por ejemplo, en algún punto en el análisis de esta red, podemos asignar un flujo de 3
del Nodo 1 al Nodo 3 a través de esta rama, y termina con los números mostrados. Sin
embargo, esta asignación podría no ser óptima; en un punto posterior del análisis,
podríamos querer deshacer algunos, o todos, de este flujo asignado. El valor revisado
en el extremo derecho de la rama (es decir, 3) indica hasta qué punto puede reducirse el
flujo actual. Si el valor original en el lado derecho hubiera sido diferente de cero,
podríamos haber considerado el flujo en otra dirección. Por lo tanto, es importante que
revisemos siempre los valores en ambos extremos de una rama al mismo tiempo. Note,
también, que la suma de los valores revisados siempre será igual a la suma de los
valores originales.
3. Regrese al paso 1.

EJEMPLO 1

Para demostrar el algoritmo, analizaremos la red mostrada en la Figura 5.1. Podemos

empezar escogiendo cualquier ruta que permita un flujo positivo de la fuente (Nodo 1) al
sumidero (Nodo 4). Obviamente, hay varias rutas, como 124, 1234, 1324, y
134. Se selecciona arbitrariamente la ruta 124.

El flujo del máximo del Nodo 1 al Nodo 2 es 10, mientras que el flujo máximo del Nodo 2
al Nodo 4 es 6. Así, la capacidad limitante a lo largo de esta ruta es de 6 para la Rama 24,
así que podemos asignar un flujo de 6 para cada rama en esta ruta. Esto requiere que las
capacidades al final de cada rama en la ruta se ajusten adecuadamente. De esta forma,
tenemos:

FIGURA 5.2.
Primera revision: La ruta 1-2-4

JOSÉ ANTONIO RIVERA COLMENERO 78

La rama 24 está totalmente cargada; ningún flujo adicional puede enviarse en la dirección
24. Sin embargo, la rama 12 todavía puede aceptar un flujo adicional de 4. En la
selección de nuestra próxima ruta, podríamos querer explorar el flujo adicional a través de
la Rama 12 o podríamos investigar alguna otra ruta. Suponga que elegimos explorar el
flujo a través de la Rama 12, para seguir examinando la Ruta 1234.

La red revisada, como queda ahora, se muestra en la Figura 5.3. Examinando la Ruta
1234, vemos que la Rama 23 es la más restrictiva: su capacidad de flujo del Nodo 2 al
Nodo 3 es 2. Por lo tanto, podemos asignar sólo un flujo de 2 a lo largo de esta ruta. Por la
Rama 12, se agregará 2 al flujo actual y hará un flujo total de 8 para esta rama.

FIGURA 5.3.
Red de flujo actualizada

Para la Rama 23, el flujo será 2, y para la Rama 34, qué ahora no tiene flujo, el flujo
asignado también será 2. La red revisada se muestra en Figura 5.4.

FIGURA 5.4.

JOSÉ ANTONIO RIVERA COLMENERO 79

Segunda revisión de la red
Si no es posible un flujo positivo desde la fuente al sumidero, se ha encontrado una
solución óptima. Sin embargo, ese no es el caso, aquí. La Ruta 134 todavía puede
aceptar un poco de flujo: la Rama 13 puede aceptar un flujo de 3, mientras que la Rama
34 puede aceptar un flujo de 4. Por lo tanto, la rama limitante es 13; por consiguiente,
puede asignarse un flujo de 3 a esta ruta. La red resultante se muestra en la Figura 5.5.

FIGURA 5.5.
Tercera revisión de la red

FIGURA 5.6.
Solución final para el ejemplo de la red de flujo máximo

Hasta aquí, no es posible un flujo adicional porque ninguna ruta tiene una capacidad de
flujo positiva. Por lo tanto, esta solución es óptima; la tasa de flujo máxima es 11 que se
muestra ya sea como la suma de las entradas y como la suma de las salidas. Además, el
flujo a través de las diferentes ramas de la red también lo muestran. Estos valores se
resumen en la Figura 5.6.

Para una red tan pequeña como esta, es posible determinar la tasa de flujo máximo por
inspección. Sin embargo, para redes más grandes, más complicadas, se debe tener un
JOSÉ ANTONIO RIVERA COLMENERO 80
enfoque más prudente. A ese respecto, al intentar determinar si existe una ruta que tenga
una tasa de flujo positiva durante el análisis, note la capacidad total de las ramas que dejan
la fuente así como la capacidad total de las ramas que entran en el sumidero. La capacidad
de flujo de la red no puede exceder a cualquiera de éstos.

Solución con el software QM para Windows Versión 4

Paso 1. Del menú del software “QM para Windows”, se selecciona el Módulo
“Networks”, es decir, Redes.

FIGURA 5.7.
Selección del módulo “Networks” (Redes).

Paso 2. Se selecciona el menú “File” (Archivo)/“New” (Nuevo) y del submenú se activa la

opción Maximal Flow (Flujo Máximo).

FIGURA 5.8.
Selección del menú principal de File (Archivo)/ New (Nuevo)/Maximal Flow (Flujo
Máximo)

Paso 3. En la ventana Crear el conjunto de datos para Red/Flujo Máximo (Create data
set for Networks/Maximal Flow) , se escribe el título del problema que se va a resolver
“OLEODUCTO”. Se indica el Número de Ramas (Number of Branches): 5. Se presiona
el botón “OK”.

JOSÉ ANTONIO RIVERA COLMENERO 81

FIGURA 5.9.
Ventana para crear el conjunto de datos para resolver el problema de Flujo Máximo.

Paso 4. Se ingresa en número del nodo Fuente (Source) y el número del nodo Sumidero
(Sink), en la columna de Nombre de la rama (Branch name) se cambia Branch por Rama
sobre escribiendo en el texto actual, luego se escriben los Nodos iniciales y los Nodos
finales de cada rama (Start node y End node), asimismo, se proporciona la Capacidad
(Capacity) y la Capacidad inversa (Reverse capacity) del flujo sobre las ramas o arcos.
Para obtener la solución de la red con flujo máximo, se presione el botón “Solve”:

FIGURA 5.10.
Captura de los datos asociados con la red de flujo máximo

Paso 5. La solución óptima, que se obtiene con QM para Windows es:

JOSÉ ANTONIO RIVERA COLMENERO 82

FIGURA 5.11
Ventana que muestra los Resultados de la Red (Networks Results)

De donde se observa que el Flujo Máximo en la Red (Maxima Network Flow) que se
puede enviar del nodo fuente (nodo 1) al nodo sumidero (nodo 4), es de 11 unidades de
capacidad.

EJEMPLO 2

Determine el flujo máximo a través del sistema de tuberías desde el nodo 1 hasta el nodo 5.

FIGURA 5.12.
Red para el problema del sistema de tuberías.

Empiece seleccionando cualquier ruta a través de la red que tenga una capacidad de flujo
positiva. Una ruta es 125, donde la Rama 12 tiene una capacidad de 12, y la Rama 25
tiene una capacidad de 7. La capacidad limitante es la capacidad más pequeña a lo largo
de la ruta que es 7. Asigne 7 a cada rama en esta ruta y revise las capacidades de flujo
como corresponde.

JOSÉ ANTONIO RIVERA COLMENERO 83

FIGURA 5.13.
Primera revisión: La ruta 125

Encuentre otra ruta que tenga una capacidad de flujo positiva del Nodo 1 al Nodo 5. Por
simplicidad, suponga que continuamos con la Rama 12 y usamos la Ruta 1235. Las
capacidades de flujo de las ramas en esta ruta son 5 en 12, 4 en 23, y 14 en 35. Por lo
tanto, 4 es la capacidad limitante. Asignando 4 a cada rama en la ruta y ajustando las
capacidades de la rama se obtiene la siguiente red actualizada:

FIGURA 5.14.
Segunda revisión: La ruta 1235.

En este punto, ningún flujo adicional puede pasar por el Nodo 2 porque las dos ramas que
salen de él están cargadas a su capacidad. Sin embargo, la Ruta 135 tiene una
capacidad de flujo positiva de 8 (13 tiene 8 y 35 tiene 10). Asignando un flujo de 8 a
cada rama en 135 se obtiene la siguiente red actualizada:

JOSÉ ANTONIO RIVERA COLMENERO 84

FIGURA 5.15.
Tercera revisión: La ruta 135.

La única rama restante desde el Nodo 1 que tiene una ruta con capacidad de flujo positiva
es 14. La Ruta 145 tiene una capacidad de 6. Asignando 6 a las ramas en esta ruta se
obtiene la siguiente red actualizada.

FIGURA 5.16.
Cuarta revisión: La ruta 145.

Sólo queda una ruta que tiene una capacidad de flujo positiva: 1435, con una
capacidad de 2. Asignando 2 a cada rama en esta ruta se obtiene la red actualizada:

JOSÉ ANTONIO RIVERA COLMENERO 85

FIGURA 5.17.
Quinta revisión: La ruta 1435.

Puesto que ninguna ruta del Nodo 1 al Nodo 5 tiene capacidad de flujo positiva, el análisis
está completo. La tasa de flujo máximo es igual a la suma de los flujos que entran al Nodo
1: 2 + 6 + 8 + 4 + 7 = 27. Esto es igual al flujo que sale del sistema por el Nodo 5.

Los resultados finales se resumen en la red siguiente:

FIGURA 5.18.
Solución final para el ejemplo de la red de flujo máximo del sistema de tuberías

Se muestran los flujos a través de cada rama según la forma como se fueron obteniendo,
simplemente para propósitos de ilustración y claridad. Así que, el flujo a través de Rama
12 es 11, y el flujo a través de Rama 35 es 14. Finalmente, debe observarse que en
muchos casos, las asignaciones de diferentes ramas es posible que produzca el mismo flujo
máximo. Con frecuencia, existen varias soluciones alternativas. Sin embargo, mientras no
se encuentre una ruta con una capacidad de flujo positiva, la solución de flujo máxima se
ha encontrado.

JOSÉ ANTONIO RIVERA COLMENERO 86

 Solución con el software QM para Windows Versión 4

Paso 1. Del menú del software “QM para Windows”, se selecciona el Módulo
“Networks”, es decir, Redes.

FIGURA 5.19.
Selección del módulo “Networks” (Redes).

Paso 2. Se selecciona el menú “File” (Archivo)/“New” (Nuevo) y del submenú se activa la

opción Maximal Flow (Flujo Máximo).

FIGURA 5.20.
Selección del menú principal de File (Archivo)/ New (Nuevo)/Maximal Flow (Flujo
Máximo)

JOSÉ ANTONIO RIVERA COLMENERO 87

Paso 3. En la ventana Crear el conjunto de datos para Red/Flujo Máximo (Create data
set for Networks/Maximal Flow), se escribe el título del problema que se va a resolver
“TUBERÍAS”. Se indica el Número de Ramas (Number of Branches): 8. Se presiona el
botón “OK”.

FIGURA 5.21.
Ventana para crear el conjunto de datos para resolver el problema de Flujo Máximo.

Paso 4. Se ingresa en número del nodo Fuente (Source) y el número del nodo Sumidero
(Sink), en la columna de Nombre de la rama (Branch name) se cambia Branch por Rama
sobre escribiendo en el texto actual, luego se escriben los Nodos iniciales y los Nodos
finales de cada Rama (Start node y End node), asimismo, se proporciona la Capacidad
(Capacity) y la Capacidad inversa (Reverse capacity) del flujo sobre las ramas o arcos.
Para obtener la solución de la red con flujo máximo, se presione el botón “Solve”:

FIGURA 5.22.
JOSÉ ANTONIO RIVERA COLMENERO 88
Captura de los datos asociados con la red de Flujo Máximo
Paso 5. La solución óptima, que se obtiene con QM para Windows es:

FIGURA 5.23.
Ventana que muestra los Resultados de la Red (Networks Results)

De donde se observa que el Flujo Máximo en la Red (Maxima Network Flow) que se
puede enviar del nodo fuente (nodo 1) al nodo sumidero (nodo 5), es de 27 unidades de
capacidad.

5.1. Problemas Propuestos

51. La ciudad de New Berlin está considerando convertir varias de sus calles en un solo
sentido (consulte la red proporcionada). Además, debido al aumento de los impuestos
a la propiedad y al agresivo plan de desarrollo vial, la ciudad de New Berlin ha
estado considerando aumentar la capacidad vial de dos de sus vialidades. Si se hace
esto, el tráfico a lo largo de la carretera 1–2 (desde el nodo 1 al nodo 2) aumentará de
2 a 5, y la capacidad de tráfico a lo largo de la carretera 1–4 aumentará de 1 a 3.
¿Cuál es el número máximo de autos por hora que pueden viajar de este a oeste con el
sistema vial actual? Si se hicieran los aumentos en la capacidad para las carreteras 1–
2 y 2–5, ¿cómo cambiaría la cantidad de autos por hora que pueden viajar de este a
oeste?

Red para el problema 51

JOSÉ ANTONIO RIVERA COLMENERO 89

52. Una red de comunicación que se muestra en la siguiente figura transfiere información
entre diferentes localidades. Los números sobre cada rama representan las
capacidades de flujo de información que entra y que sale por esa rama, por ejemplo,
la capacidad de flujo del nodo 1 al nodo 2 es 10, y del nodo 2 al nodo 1 es 6. ¿Cuál es
el flujo máximo posible de información del nodo 1 al nodo 7? Para resolver este
problema por medio de la red de flujo máximo use QM para Windows.

Red para el problema 52

5-3. Las capacidades de flujo entre los nodos, son los que se muestran en la red de la
siguiente figura, y se desea encontrar el flujo máximo del nodo 1 al nodo 11

Red para el problema 53

JOSÉ ANTONIO RIVERA COLMENERO 90

5-4. South Side Oil and Gas, una nueva empresa de Texas, ha desarrollado una red de
oleoductos para transportar petróleo de los campos de exploración a la refinería y a
otros lugares. Existen 10 oleoductos (ramales) en la red. El flujo de petróleo en
cientos de galones y los datos de la red de oleoductos se presentan en la siguiente
tabla.

Capacidad en
Capacidad
Nodo sentido inverso
Ramal Nodo final (en cientos de
inicial (en cientos de
galones)
galones)
Ramal 1 1 2 10 4
Ramal 2 1 3 8 2
Ramal 3 2 4 12 1
Ramal 4 2 5 6 6
Ramal 5 3 5 8 1
Ramal 6 4 6 10 2
Ramal 7 5 6 10 10
Ramal 8 5 7 5 5
Ramal 9 6 8 10 1
Ramal 10 7 8 10 1

a. Dibuje la red asociada con este problema. ¿Cuál es el máximo flujo que puede
ir a través de la red?

b. South Side Oil and Gas tiene que modificar sus patrones de flujo a través de los
oleoductos. Los nuevos datos se presentan en la siguiente tabla. ¿Qué efecto
tiene esta modificación en el flujo máximo a través de la red?

Ramal Nodo Nodo Capacidad Capacidad en

JOSÉ ANTONIO RIVERA COLMENERO 91

 sentido inverso
(en cientos de
inicial final (en cientos de
galones)
galones)
Ramal 1 1 2 10 4
Ramal 2 1 3 8 2
Ramal 3 2 4 12 1
Ramal 4 2 5 0 0
Ramal 5 3 5 8 1
Ramal 6 4 6 10 2
Ramal 7 5 6 10 10
Ramal 8 5 7 5 5
Ramal 9 6 8 10 1
Ramal 10 7 8 10 1

Capítulo 6
El Problema de la Ruta Más
Corta (Shortest Route Problem)
6.1 Objetivo del problema de la ruta más corta
En la ruta más corta, el objetivo es encontrar la distancia más corta desde un sitio (origen)
a otro sitio (destino) a través de una red. Muy a menudo, la distancia total recorrida es la
medida de efectividad. Los sistemas de entrega y los sistemas de transporte son ejemplos
típicos de donde ocurren tales problemas. Otras medidas de efectividad podrían ser el costo
o el tiempo.

Definiciones de Algoritmo:
 Un algoritmo es un conjunto de instrucciones para resolver un problema.
 Un algoritmo es un método paso por paso para resolver un problema o una tarea.
 Un algoritmo es una secuencia de instrucciones no ambiguas para resolver un
problema, es decir, para obtener una salida requerida para cualquier entrada legítima
en una cantidad de tiempo finita.

El Algoritmo de la ruta más corta

JOSÉ ANTONIO RIVERA COLMENERO 92

El algoritmo que se usa para encontrar la ruta más corta considera que todas las distancias
entre los nodos son no-negativas. El algoritmo encuentra la ruta más corta desde un nodo
especificado (normalmente el Nodo 1) hasta cada nodo en una red. El algoritmo requiere de
n−1 pasos, donde n es el número de nodos en una red.

El análisis usa un procedimiento de etiquetado, en el qué se desarrolla una etiqueta para

cada nodo. Las etiquetas consisten de dos números separados por una coma: El primer
número se refiere a la distancia del Nodo 1 al nodo etiquetado a lo largo de una cierta ruta,
mientras que el segundo número se refiere al nodo que inmediatamente precede a ese nodo
a lo largo de esa ruta. Así, si el Nodo 5, por decir, tiene la etiqueta 18,3, esto nos indica que
hay una ruta desde el Nodo 1 al Nodo 5 que tiene una distancia de 18 y que el nodo
precedente en esa ruta es el Nodo 3. (Para saber cuál es el nodo que precede al Nodo 3,
tendríamos que referirnos a la etiqueta en el Nodo 3. Por lo tanto, una vez que se termina el
análisis, la ruta más corta a cualquier nodo dado desde el Nodo 1 se determina siguiendo
hacia atrás las etiquetas del nodo a través de la red).
El procedimiento de etiquetado inicia con el nodo origen (por ejemplo, el hogar, la oficina
central, la terminal de autobuses, un punto de partida). Normalmente éste es el Nodo l. Su
etiqueta es 0,S. El 0 indica la distancia del Nodo 1 a este nodo; debido a que éste es el Nodo
1, la distancia es 0. La S indican que éste es el nodo inicial (Starting). Este nodo se
considera que está permanentemente etiquetado, un término utilizado para indicar que no
existen rutas más cortas en un nodo. Obviamente, debido a que el Nodo 1 es el punto de
arranque, podemos estar seguros que no hay ninguna “ruta más corta” para este nodo. En
general, una vez que determinamos la distancia más corta a un nodo, le damos a ese nodo
una etiqueta permanente. Esto lo indicamos obscureciendo el nodo.

Inicialmente, ninguno de los nodos están etiquetados. Entonces, conforme avanza el

análisis, se asignan a ciertos nodos etiquetas temporales, que pueden revisarse como parte
del análisis. La etiqueta permanece temporal hasta que se determina que no existe una ruta
más corta a un nodo. En ese momento, la etiqueta se vuelve permanente, y el nodo se
sombrea para reflejar esto. Cuando todos los nodos han recibido etiquetas permanentes, las
rutas más cortas se determinan por inspección de las etiquetas permanentes en los nodos.
La esencia del análisis es determinar las etiquetas permanentes para los nodos, uno a la vez.
Una vez que un nodo recibe su etiqueta permanente, el análisis se enfoca en esa sección de
la red para asignar etiquetas temporales. El ejemplo siguiente ilustrará este procedimiento
sencillo.

Ejemplo 6.1.
Dada esta red que muestra la distancia en kilómetros entre los destinos de entrega,
encuentre la ruta más corta a cada destino desde el Nodo 1. El recorrido entre los nodos
puede ser en cualquier dirección.

JOSÉ ANTONIO RIVERA COLMENERO 93

FIGURA 6.1.
Red representativa del problema de ruta más corta.

Empiece etiquetando el Nodo 1 permanentemente con 0,S. Indique que la etiqueta es

permanente obscureciendo el Nodo 1. Luego, obtenga las etiquetas temporales para cada
nodo que puede alcanzarse directamente desde el Nodo 1 (es decir, Nodos 2, 3, y 4). La
etiqueta debe mostrar la distancia del Nodo 1 y debe indicar que ese Nodo 1 es el nodo
predecesor. Así, la etiqueta temporal para el Nodo 2 es 5,1 porque se tiene una distancia de
5 kilómetros desde el Nodo 1, y Nodo 1 lo precede. De manera semejante, la etiqueta
temporal para el Nodo 3 es 8,1 y la etiqueta temporal para el Nodo 4 es 7,1.

FIGURA 6.2.
Primera etiqueta para la red de ruta más corta

Primera iteración. Determine qué etiqueta temporal tiene la distancia más pequeña
desde el Nodo l. Es la etiqueta para el Nodo 2, con una distancia de 5. Haga esta
etiqueta permanente, y obscurezca el Nodo 2. Ahora determine las etiquetas
temporales para cada nodo que puede alcanzarse directamente desde este último
nodo permanente a menos que un nodo ya tenga una etiqueta permanente (es decir, el
Nodo 1), o a menos que ya exista una etiqueta temporal actual que no pueda

JOSÉ ANTONIO RIVERA COLMENERO 94

mejorarse. Por ejemplo, la etiqueta temporal actual para el Nodo 3 es 8,1; la distancia
desde el Nodo 1 a lo largo de la ruta 123 sería 5 + 6 = 11. Por lo tanto, la etiqueta
actual es más corta, por lo que se debe conservar esa etiqueta. El Nodo 5, sin embargo,
no tiene una etiqueta. Su distancia acumulada desde el Nodo 1 a través del Nodo 2 es
18; entonces, su etiqueta temporal es 18,2 porque el Nodo 2 es su predecesor.

FIGURA 6.3.
Primera iteración para la red de ruta más corta
Segunda iteración. Identifique el nodo que tiene la etiqueta temporal más pequeña. (Las
opciones son: Nodo 3, con una etiqueta de 8,1; el Nodo 4 con una etiqueta de 7,1; y el
Nodo 5 con una etiqueta de 18,2). Debido a que 7 es la distancia más pequeña, el Nodo 4
tiene la etiqueta temporal más pequeña. Haga esta etiqueta permanente (póngale sombra).
Luego, encuentre cada nodo no permanente que puede alcanzarse directamente desde este
nodo permanente más reciente. Éstos son los Nodos 3 y 6. el Nodo 6 no tiene etiqueta
temporal; su etiqueta temporal será ahora 23,4 e indica que su distancia desde el Nodo 1 es
23 kilómetros (la etiqueta del Nodo 4 de 7 más los 16 kilómetros del nodo 4 al nodo 6). El
Nodo 3 ya tiene una etiqueta temporal de 8,1 e indica que puede alcanzarse directamente
desde el Nodo 1 con una distancia de 8 kilómetros. Vemos que también puede alcanzarse
en 8 kilómetros a través de la Ruta 1-4-3. Hay un enlace, así que puede usarse cualquier
etiqueta. Por simplicidad, suponga que retenemos la etiqueta actual.

JOSÉ ANTONIO RIVERA COLMENERO 95

FIGURA 6.4.
Segunda iteración para la red de ruta más corta

Tercera iteración. El nodo con la etiqueta temporal más pequeña es el Nodo 3. Por
consiguiente, ahora su etiqueta se vuelve una etiqueta permanente, y el Nodo 3 se sombrea.
También es útil indicar que existe un empate en este punto y significa que existe una ruta
alterna en este nodo. Luego, encuentre cada nodo no permanente que puede alcanzarse
directamente desde el Nodo 3. Vemos que el Nodo 5 es el único que puede alcanzarse.
Tiene una etiqueta temporal de 18,2. Sin embargo, podemos ver que siguiendo una ruta
directamente desde el Nodo 3 al Nodo 5, la distancia acumulada desde el Nodo 1 será sólo
de 15 (es decir, 8 + 7 = 15). Debido a que la ruta a través del Nodo 3 es más corta,
actualizamos la etiqueta temporal del Nodo 5 para indicar que es la ruta más corta.

FIGURA 6.5.
Tercera iteración para la red de ruta más corta

JOSÉ ANTONIO RIVERA COLMENERO 96

Cuarta iteración. Identifique el Nodo con la etiqueta temporal más pequeña. El Nodo 5
tiene una etiqueta de 15,3 y el Nodo 6 tiene la etiqueta 23,4. Debido a que 15 es más
pequeño que 23, se selecciona el Nodo 5 y se convierte a una etiqueta permanente.

FIGURA 6.6.
Cuarta iteración para la red de ruta más corta

Quinta iteración. El único nodo con una etiqueta no permanente, y el único nodo que
puede alcanzarse directamente desde el nodo permanente mas reciente, es el Nodo 6.
Usando esta ruta, su distancia acumulada desde el Nodo 1 sería 15 + 6 = 21. Debido a que
ésta es menor se debe actualizar su etiqueta, actualizamos etiqueta en 21,5. Y porque éste es
el único nodo sin una etiqueta permanente, podemos etiquetarlo ahora permanentemente,
usando 21,5.

FIGURA 6.7.
Quinta iteración para la red de ruta más corta

Esto completa el análisis de las rutas. Usando la red final, podemos leer las distancias del
Nodo 1 a cualquier nodo con la etiqueta permanente de cada nodo. Por ejemplo, la distancia

JOSÉ ANTONIO RIVERA COLMENERO 97

más corta del Nodo 1 al Nodo 5 es 15 kilómetros, y la distancia más corta del Nodo 1 al
Nodo 6 es 21 kilómetros.

Para identificar la ruta que proporciona la distancia más corta a un nodo particular, es
necesario trabajar de adelante hacia atrás de la red. Esto a veces se le llama volver hacia
atrás o retroceder. Aquí está cómo se hace. Inicie con el nodo en cuestión (es decir, el Nodo
6). La segunda parte de la etiqueta indica el nodo anterior en la ruta más corta. Por lo tanto,
el nodo anterior al Nodo 6 es el Nodo 5. Volviendo nuestra atención al Nodo 5, vemos que
su nodo predecesor es el Nodo 3. Por lo tanto, hasta ahora tenemos 356. En el Nodo 3,
observamos que había un empate y significa que cualquiera de las dos rutas (13 o 143)
tienen la misma distancia. Así, podemos escoger cualquiera de estas como nuestra ruta e
identificar a la otra como una ruta alterna. Así, podemos decir que 1356 es la ruta más
corta, pero que 14356 es una ruta alterna.

FIGURA 6.8.
La ruta más corta.
Solución con el software QM para Windows Versión 4

Ejemplo 6.2.
Todos los días, Ray Design debe transportar camas, sillas y otros muebles de la fábrica al
almacén; necesita pasar por varias ciudades y Ray desea encontrar la ruta con la distancia
más corta. La red de carreteras se muestra en la Figura 6.9. Las distancias están dadas en
kilómetros.

JOSÉ ANTONIO RIVERA COLMENERO 98

FIGURA 6.9.
Carreteras de la planta de Ray al almacén

Primera iteración. Si observa la Figura 6.9, verá que el nodo más cercano a la planta es
el nodo 2, con una distancia de 100 kilómetros. Así conectaremos estos dos nodos.

FIGURA 6.10.
Primera iteración para la red de carreteras de la planta de Ray al almacén

Segunda iteración. Ahora buscamos el siguiente nodo más cercano al origen.

Verificamos los nodos 3, 4 y 5. El nodo 3 es el más cercano, pero hay dos caminos
posibles. La ruta 1–2–3 es la más cercana al origen, con una distancia total de 150
kilómetros.

JOSÉ ANTONIO RIVERA COLMENERO 99

FIGURA 6.11.
Segunda iteración para la red de carreteras de la planta de Ray al almacén

Tercera iteración. El siguiente nodo más cercano es el nodo 4 o el nodo 5. El nodo 4 está
a 200 kilómetros del nodo 2 y el nodo 2 está a 100 kilómetros del nodo 1. Por lo tanto, el
nodo 4 está a 300 kilómetros del origen. Hay dos rutas para el nodo 5, 2–5 y 3–5, hacia el
origen. Tenga en cuenta que no tenemos que volver al origen porque ya conocemos la ruta
más corta desde el nodo 2 y el nodo 3 hasta el origen. Las distancias mínimas se colocadan
arriba o abajo de estos nodos. El camino 2–5 es de 100 kilómetros, y el nodo 2 está a 100
kilómetros del origen. Por lo tanto, la distancia total es de 200 kilómetros. De manera
similar, podemos determinar que la ruta desde el nodo 5 al origen a través del nodo 3 es
190 (40 kilómetros entre los nodos 5 y 3 más 150 millas desde el nodo 3 hasta el origen).
Por lo tanto, seleccionamos el nodo 5 pasando del nodo 3 al origen.

FIGURA 6.12.
Tercera iteración para la red de carreteras de la planta de Ray al almacén.

JOSÉ ANTONIO RIVERA COLMENERO 100

Cuarta iteración. El siguiente nodo más cercano será el nodo 4 o el nodo 6, como los
últimos nodos restantes. El nodo 4 está a 300 kilómetros del origen (del nodo 4 al nodo 2
más 100 del nodo 2 al origen). El nodo 6 está a 290 kilómetros del origen. El nodo 6 tiene
la distancia mínima, y como es el nodo final, hemos terminado.

FIGURA 6.13.
Cuarta iteración para la red de carreteras de la planta de Ray al almacén

La ruta más corta es la ruta 1–2–3–5–6, con una distancia mínima de 290 kilómetros.

FIGURA 6.14.
Red de ruta más corta para Ray de la planta al almacén

JOSÉ ANTONIO RIVERA COLMENERO 101

 Ejemplo 6.3.
Encuentre la ruta más corta de la siguiente red:

SOLUCIÓN:

La ruta más corta es: 1356, con una distancia de 4+3+3 = 10 unidades de longitud.

JOSÉ ANTONIO RIVERA COLMENERO 102

6.2. Problemas propuestos
6-1. Se contrató a Transworld Moving para trasladar mobiliario y equipo de oficina de
Cohen Properties a sus nuevas instalaciones. ¿Qué ruta le recomiendan? La red de
carreteras se muestra en la figura siguiente.

6-2. Encuentre la ruta más corta a través de cada una de las siguientes redes, donde los
números representan distancias reales entre los nodos correspondientes.

(a)

(b)

JOSÉ ANTONIO RIVERA COLMENERO 103

6-3. Encuentre la ruta más corta partiendo del nodo 1 para llegar al nodo 7, en la siguiente
red dirigida.

Capítulo 7
El Problema del Árbol de
Expansión Mínima
(Minimum Spanning Tree
Problem)

JOSÉ ANTONIO RIVERA COLMENERO 104

 ÁRBOLES

INTRODUCCIÓN
Muchos árboles tienen una estructura física que puede ser natural o artificial y estática o
dependiente del tiempo. Dos ejemplos de árboles naturales son la variedad biológica con
tronco, ramas y hojas, y el sistema de drenaje de los ríos tributarios que forman una cuenca
hidrológica. La estructura química de ciertas moléculas orgánicas proporciona ejemplos
menos obvios de estructuras de árboles.

JOSÉ ANTONIO RIVERA COLMENERO 105

 Un árbol joven Cuenca hidrológica Una molécula

FIGURA 7.1.
Ejemplos de árboles naturales.

Un ejemplo de la variedad artificial de árboles es un sistema de distribución de oleoductos

o gasoductos, como una red de oleoductos submarinos; ya que el costo de construir una red
de este tipo puede ser muy grande, una estructura de árbol sin enlaces necesarios puede ser
lo más económico para la red.

FIGURA 7.2.
Ejemplo de un árbol artificial: Un sistema de distribución de ductos.

JOSÉ ANTONIO RIVERA COLMENERO 106

 Teorema 7.1: Definiciones equivalentes de un árbol

Sea G una red con v vértices o nodos. Entonces las siguientes declaraciones son
equivalentes.

 G está conectada y no tiene ciclos.

 G tiene n−1 arcos y no tiene ciclos.
 G está conectada y si se quita cualquiera de los nodos se desconecta G .
 Cualquier par de vértices o nodos de G estarán conectados por exactamente un arco
o ruta.
 G no tiene ciclos, la adición de cualquier nuevo arco crea un ciclo.

7.1 El problema del árbol de expansión mínima

Árbol. Intuitivamente, podemos visualizar como una forma de organizar información de
forma jerárquica, con un único punto de entrada y una serie de caminos que van abriéndose
en cada punto hacia sus sucesores.

Los árboles comenzaron a emplearse en 1857, cuando el matemático inglés Arthur Cayley
los utilizó para contar cierto tipo de componentes químicos. Desde ese momento, los
árboles se han empleado para resolver problemas de gran variedad en diferentes disciplinas.

Los árboles de expansión están relacionados con la interconexión de los nodos de una red
usando lo menos posible de la rama el “material o recurso disponible”. Entre los ejemplos
típicos se encuentran la instalación de una red telefónica en una ciudad, la instalación de
una red de televisión por cable en una colonia, la conexión de motores eléctricos o aparatos
a una red, la construcción de carreteras para comunicar varios municipios, y así
sucesivamente.

Número de arcos del árbol de expansión=Número de nodos−1

El número de arcos o ramas en un árbol de expansión es uno menos

que el número total de nodos. Aún más, cada nodo está conectado en
forma directa por una sola rama con al menos otro nodo.

Se desea determinar el árbol de expansión mínima para construir a costo mínimo una red de
carreteras que una las siete localidades (A, B, C, D, E, F, G). El número cercano a cada
línea punteada proporciona el costo (en millones de pesos) si se elige construir ese tramo
en particular.

JOSÉ ANTONIO RIVERA COLMENERO 107

FIGURA 7.1.
Red de carreteras que une siete localidades.

Un algoritmo notablemente sencillo.

Comenzando sin ligaduras en la red, cada paso del algoritmo selecciona una nueva rama
que insertar de la lista de ramas potenciales. Como se describe en seguida, el algoritmo
continúa hasta que una rama una a cada nodo en cuyo momento los nodos seleccionados
forman un árbol de expansión mínima.

MÉTODO 1

Algoritmo para un problema de árbol de expansión mínima

1. Selección de la primera rama: seleccione la rama potencial menos costosa.

2. Selección de la segunda rama: seleccione la rama potencial menos costosa entre un
nodo que ya esté unido por una rama y un nodo que aún no tenga una rama que lo
una a otro nodo.
3. Repita el paso 2 una y otra vez hasta que cada nodo esté unido por una rama (quizá
más de uno). En ese momento se ha obtenido una solución óptima (un árbol de
expansión mínima).

[Empates: los empates para la rama potencial menos costosa pueden romperse en forma
arbitraria sin afectar la optimalidad de la solución final. No obstante, los empates en el paso
2 señalan que pueden haber (mas no necesariamente hay) otras soluciones óptimas que se
obtendrían al romper el empate de otro modo.]

Entre todas las ramas potenciales (líneas punteadas), la que está entre el nodo C y el nodo
D empata con la que está entre el nodo E y el nodo F como la menos costosa (costo de 1).
Por lo tanto, para el paso 1, se necesita seleccionar una de estas dos ligaduras potenciales
como la primera ligadura insertada en la red. Rompiendo el empate en forma arbitraria, se
selecciona la que está entre el nodo C y el nodo D (la otra se seleccionará después) como
se muestra en seguida.
JOSÉ ANTONIO RIVERA COLMENERO 108
FIGURA 7.2.
Primera iteración para obtener el árbol de expansión mínima.

Ahora se aplica el paso 2 por primera vez. Los dos nodos unidos por una rama son los
nodos C y D, de modo que es necesario comparar los costos de las ramas potenciales entre
cualquiera de estos nodos y un nodo que todavía no tenga ligadura. Estas ligaduras
potenciales y sus costos son:

Como la menos costosa está entre el nodo C y el nodo B, con un costo de 2, se selecciona
como la siguiente rama insertada en la red, como se muestra en seguida.

FIGURA 7.3.
Segunda iteración para obtener el árbol de expansión mínima.

JOSÉ ANTONIO RIVERA COLMENERO 109

Ahora, los nodos B, C y D, están unidos o conectados por una rama (o por dos, como en el
caso del nodo C), de modo que la siguiente ejecución del paso 2 requiere comparar los
costos de las ligaduras potenciales entre uno de estos nodos y uno de los otros.

La ligadura vínculo potencial menos costosa está entre el nodo B y el nodo A, de modo que
se convierte en siguiente rama agregada a la red.

FIGURA 7.4.
Tercera iteración para obtener el árbol de expansión mínima.

Ahora los nodos A, B, C y D están todos unidos, entonces se comparan los costos de las
ligaduras potenciales entre uno de estos nodos y uno de los otros. (En realidad, ninguna de
estas ligaduras potenciales incluye al nodo A, por que no hay ligaduras potenciales que
vayan a un nodo que no esté unido).

La menos costosa es la ligadura potencial entre el nodo C y el nodo F, con un costo de 3, de

modo que se agrega.

JOSÉ ANTONIO RIVERA COLMENERO 110

FIGURA 7.5.
Cuarta iteración para obtener el árbol de expansión mínima.

Ahora todos, salvo los nodos E y G, están unidos por una ligadura. Por lo tanto, las únicas
ramas potenciales que necesitan considerarse están entre uno de los nodos E o G y uno de
los otros nodos.

Por mucho, la menos costosa es la ligadura potencial entre el nodo F y el nodo E, de modo
que por fin se inserta en la red. (Recuerde que esta ligadura potencial estaba empatada
como: la ligadura inicial en el paso l.)

FIGURA 7.6.
Quinta iteración para obtener el árbol de expansión mínima.

Puesto que el nodo G ahora es el único nodo no unido por una ligadura, las únicas ligaduras
potenciales son las que unen este nodo con los otros.

JOSÉ ANTONIO RIVERA COLMENERO 111

La ligadura potencial menos costosa está entre el nodo E y el nodo G, de modo que se
inserta en la red.

FIGURA 7.7.
Sexta iteración para obtener el árbol de expansión mínima.

Ahora cada nodo está unido por una ligadura, por lo que el algoritmo termina y éste es la
solución óptima. Todas las ligaduras insertadas en la red forman un árbol de expansión
mínima con un costo total de 2 + 2 + 1 + 3 + 1 + 5 = 14 (14 millones de pesos). Se
rechazan todas las ligaduras potenciales restantes (líneas punteadas) porque las ligaduras
insertadas proporcionan una ruta entre cada par de nodos.

FIGURA 7.8.
Solución óptima del árbol de expansión mínima.

A este algoritmo se le conoce como algoritmo codicioso o goloso porque simplemente toma
la opción más favorable (la ligadura potencial menos costosa) en cada paso sin preocuparse
del efecto de esta selección en las decisiones subsecuentes. Es notable que tal
procedimien¬to tan rápido y sencillo garantice encontrar una solución óptima.

JOSÉ ANTONIO RIVERA COLMENERO 112

Ejemplo 7.1

La técnica de árbol de expansión mínima implica conectar todos los puntos de una red al
mismo tiempo que se minimiza la distancia o costo entre ellos. Ha sido aplicada, por
ejemplo, por compañías telefónicas para conectar varios teléfonos entre sí al mismo tiempo
que se minimiza la longitud total del cableado necesario. Una compañía constructora está
desarrollando un lujoso proyecto residencial campestre en la Alcaldía de Tlalpan. El dueño
de la compañía, debe determinar la forma más barata de suministrar los servicios (agua,
teléfono, luz, pavimentación) a cada residencia. La red de casas se muestra en la Figura
7.9.

3
2 5
4
3
5
3 7
7
1
2 2
3
3 8
5 1
2 6
6
4

Cañada

FIGURA 7.9.
Red de residencias campestres

Como se ve en la figura hay ocho casas. La distancia entre cada una de ellas en decenas de
metros se muestra en la red. La distancia entre las casas 1 y 2, por ejemplo, es de 30 metros.
Utilizaremos la técnica del árbol de expansión mínima para determinar la distancia mínima
que puede ser utilizada para conectar todos los nodos. El método se describe como sigue:

Pasos para la técnica del árbol de expansión mínima

1. Seleccionar cualquier nodo de la red.

2. Conectar este nodo al nodo más cercano que minimice la distancia total.
3. Considerando todos los nodos que ahora están conectados, encontrar y conectar el
nodo más cercano que no esté conectado. Si hay un empate para el nodo más
cercano, seleccionar uno arbitrariamente. Un empate sugiere que puede haber más
de una solución óptima.
4. Repetir el tercer paso hasta que todos los nodos estén conectados.

JOSÉ ANTONIO RIVERA COLMENERO 113

Paso 1: Se elige el nodo 1. Ahora, se resuelve la red de la Figura 7.9. Se inicia mediante
la selección arbitraria del nodo 1.

1 2 Distancia = 3

1 3 Distancia = 2

1 4 Distancia = 5

Paso 2: se conecta el nodo 1 con el 3. Como el nodo más cercano es el tercer nodo a una
distancia de 2 (20 metros), se conecta el nodo 1 al 3, lo cual se muestra en la Figura 7.9.
3
2 5
4
3
5
3 7
7
1
2 2
3
3 8
5 1
2 6
6
4

Cañada

FIGURA 7.9.
Primera iteración del árbol de expansión mínima

Considerando el nodo 1 y 3, se busca el siguiente nodo más cercano.

3 2 Distancia = 3

3 4 Distancia = 2
1 2 Distancia = 3
3 5 Distancia = 5
1 4 Distancia = 5
3 6 Distancia = 3

3 7 Distancia = 7

Paso 3: se conecta el nodo 3 con el nodo más cercano. Éste es el 4, el cual es el más
cercano a 3. La distancia es 2 (20 metros). Se conectan estos nodos, vea la Figura 7.10.

JOSÉ ANTONIO RIVERA COLMENERO 114

 3
2 5
4
3
5
3 7
7
1
2 2
3
3 8
5 1
2 6
6
4

Cañada

FIGURA 7.10.
Segunda iteración del árbol de expansión mínima.

Paso 4: Se repite el proceso. Se continúa buscando el nodo no conectado más cercano a

los nodos 1, 3 y 4.
1 2 Distancia = 3 3 6 Distancia = 3
3 2 Distancia = 3 3 7 Distancia = 7
3 5 Distancia = 5 4 6 Distancia = 6

Puede ser el nodo 2 o el nodo 6, ambos se encuentran a una distancia 3 del nodo 3. Se
elegirá el nodo 2 y se conectará con el nodo 3, ver la Figura 7.11. Observe que también
pudo haberse conectado el nodo 1 al 2, por eso cuando hay empates implica que hay más de
una solución.
3
2 5
4
3
5
3 7
7
1
2 2
3
3 8
5 1
2 6
6
4

Cañada

JOSÉ ANTONIO RIVERA COLMENERO 115

FIGURA 7.11.
Tercera iteración del árbol de expansión mínima.
Se continúa con el proceso. Existe otro empate en la siguiente iteración, con una distancia
mínima de 3 (del nodo 2 al nodo 5 y del nodo 3 al nodo 6). Hay que recordar que no se
consideró del nodo 1 al nodo 2 con una distancia 3 puesto que ya están conectados tanto el
nodo 1 como el nodo 2. Se elige de manera arbitraria el nodo 5 y se conecta al 2, ver la
Figura
7.12.

2 5 Distancia = 3 3 5 Distancia = 5

4 6 Distancia = 6 3 6 Distancia = 3

3 7 Distancia = 7

3
2 5
4
3
5
3 7
7
1
2 2
3
3 8
5 1
2 6
6
4

Cañada

FIGURA 7.12.:
Cuarta iteración del árbol de expansión mínima

Se determinan los enlaces de los nodos que todavía no están conectados con los nodos 3, 4
y 5.
3 6 Distancia = 3

3 7 Distancia = 7

4 6 Distancia = 6

5 7 Distancia = 4

El siguiente nodo más cercano es el nodo 6 y se conecta con el nodo 3, ver Figura 7.13.

JOSÉ ANTONIO RIVERA COLMENERO 116

 3
2 5
4
3
5
3 7
7
1
2 2
3
3 8
5 1
2 6
6
4

Cañada

FIGURA 7.13.
Quinta iteración del árbol de expansión mínima

En esta etapa, sólo quedan dos nodos sin conectar, el nodo 7 y el nodo 8:

3 7 Distancia = 7
5 7 Distancia = 4

6 8 Distancia = 1

El nodo 8 es el más cercano al nodo 6 con una distancia 1 y se conectan, ver Figura 7.14.

3
2 5
4
3
5
3 7
7
1
2 2
3
3 8
5 1
2 6
6
4

Cañada

JOSÉ ANTONIO RIVERA COLMENERO 117

FIGURA 7.14.
Sexta iteración del árbol de expansión mínima
A continuación se conecta el restante nodo 7 con el nodo 8, ver Figura 7.15.

3
2 5
4
3
5
3 7
7
1
2 2
3
3 8
5 1
2 6
6
4

Cañada

FIGURA 7.15.
Séptima iteración del árbol de expansión mínima

La solución final aparece en la séptima y final iteración (Figura 7.15). Los nodos 1, 2, 4 y
6 están conectados al nodo 3. El nodo 2 está conectado al 5. El 6 al 8 y el 8 al 7. Ahora
están conectados todos los nodos. La distancia total se encuentra sumando las distancias de
los arcos utilizados en el árbol de expansión. En este ejemplo, la distancia es 2 + 2 + 3 + 3
+ 3 + 1 + 2 = 16 (160 metros).

El problema del árbol de expansión mínima implica conectar todos los puntos de una
red, al tiempo que minimiza la distancia total de estas conexiones. Algunos ejemplos
comunes incluyen compañías telefónicas o de cable. Si bien se puede utilizar un modelo de
programación lineal para este problema, tiene ciertas propiedades que lo hacen bastante
complejo.

La técnica del árbol de expansión mínima conecta los nodos con una
distancia mínima

Afortunadamente, existe otro método para encontrar la solución a este problema. La

técnica de árbol de expansión mínima se presentará utilizando el siguiente ejemplo.

Ejemplo 7.2

JOSÉ ANTONIO RIVERA COLMENERO 118

Considere a la compañía Lauderdale Construction, que está desarrollando un proyecto de
viviendas de lujo en Panama City Beach, Florida, que se muestra en la Figura 7.16.

Melvin Lauderdale, propietario y presidente de Lauderdale Construction, debe determinar

la forma menos costosa de suministrar agua y electricidad a cada vivienda. La red de
viviendas se muestra en la Figura 7.16.

FIGURA 7.16.
Panama City Beach. Fuente: Google Maps

JOSÉ ANTONIO RIVERA COLMENERO 119

FIGURA 7.17.
Red para Lauderdale Construction.
Como se ve en la Figura 7.17, hay ocho casas en Panama City Beach, Florida. La distancia
entre cada casa en cientos de pies se muestra en la red. La distancia entre las casas 1 y 2,
por ejemplo, es de 300 pies. (El número 3 está entre los nodos 1 y 2.) Ahora, la técnica de
árbol de expansión mínima se usa para determinar la distancia mínima que se puede usar
para conectarse a los nodos. El enfoque se describe a continuación:

La solución del problema del árbol de expansión mínima consiste en cuatro pasos.

Pasos para la técnica de árbol de expansión mínima

1. Seleccione cualquier nodo en la red.

2. Conecte este nodo al nodo más cercano que minimice la distancia total.
3. Considere todos los nodos que ahora están conectados, encuentre y conecte el nodo
más cercano que no esta conectado. Si hay un empate para el nodo más cercano,
seleccione uno de manera arbitrariae. Un empate sugiere que existe más de una
solución óptima.
4. Repita el tercer paso hasta que todos los nodos estén conectados.

Ahora, resolvemos la red en la Figura 7.17, para Melvin Lauderdale. Comenzamos

seleccionando arbitrariamente el nodo 1. Como el nodo más cercano es el nodo 3, a una
distancia de 2 (200 pies), conectamos el nodo 1 al nodo 3. Esto se muestra en la Figura
7.18.

Paso 1: Seleccionar arbitrariamente el nodo 1

Paso 2: Conectar el nodo 1 con el nodo 3 (el más cercano)

JOSÉ ANTONIO RIVERA COLMENERO 120

FIGURA 7.18.
Primera iteración para Lauderdale Construction.

FIGURA 7.19.
Segunda iteración para Lauderdale Construction.

Considerando los nodos 1 y 3, buscamos el siguiente nodo más cercano. Este es el nodo 4,
que es el más cercano al nodo 3. La distancia es 2 (200 pies). Nuevamente, conectamos
estos nodos, como se muestra en la Figura 7.19. Continuamos, buscando el nodo más
cercano entre los nodos 1, 3 y 4. Son el nodo 2 o el nodo 6, ambos a una distancia de 3 (300

JOSÉ ANTONIO RIVERA COLMENERO 121

pies) del nodo 3. Seleccionaremos el nodo 2 y lo conectaremos al nodo 3, como se muestra
en la Figura 7.20.

FIGURA 7.20.
Tercera iteración para Lauderdale Construction.
Continuamos el proceso. Hay otro empate para la siguiente iteración con una distancia
mínima de 3 (nodo 2  nodo 5 y nodo 3  nodo 6). Debe tener en cuenta que no
consideramos el enlace nodo 1  nodo 2 con una distancia de 3 porque los nodos 1 y 2 ya
están conectados. Seleccionamos arbitrariamente el nodo 5 y lo conectamos al nodo 2,
como se muestra en la Figura 7.21.

FIGURA 7.21.
Cuarta iteración para Lauderdale Construction.

JOSÉ ANTONIO RIVERA COLMENERO 122

El siguiente nodo más cercano es el nodo 6, y lo conectamos al nodo 3, como se muestra en
la Figura 7.22.

FIGURA 7.22.
Quinta iteración para Lauderdale Construction.
En esta etapa, solo nos quedan dos nodos desconectados, los nodos 7 y 8. El nodo 8 es el
nodo más cercano al nodo 6, con una distancia de 1 (100 pies), y lo conectamos, como se
muestra en la Figura 7.23. Luego, el nodo restante, el nodo 7, se conecta al nodo 8, como
se muestra en la Figura 7.24.

FIGURA 7.23.
Sexta iteración para Lauderdale Construction

JOSÉ ANTONIO RIVERA COLMENERO 123

FIGURA 7.24.
Séptima iteración para Lauderdale Construction.
La solución final se puede ver en la séptima y última iteración. Los nodos 1, 2, 4 y 6 están
todos conectados al nodo 3. El nodo 2 está conectado al nodo 5. El nodo 6 está conectado al
nodo 8, y el nodo 8 está conectado al nodo 7. Se encuentra la distancia total sumando las
distancias para los arcos utilizados en el árbol de expansión. En este ejemplo, la distancia es
2 + 2 + 3 + 3 + 3 + 1 + 2 = 16 (o 1,600 pies). Esto se resume en la Tabla 7.1.

Solución con el software QM para Windows Versión 4

JOSÉ ANTONIO RIVERA COLMENERO 124

Paso 1. Del menú del software “QM para Windows”, se selecciona el Módulo
“Networks”, es decir, Redes.

FIGURA 7.25.
Módulos de QM para Windows, selección de Networks (Redes).

Paso 2. Se selecciona el menú “File” (Archivo)/“New” (Nuevo)/”Minimum Spanning

Tree” (Árbol de Expansión Mínima)

FIGURA 7.26.
Selección para aplicar la técnica del Árbol de Expansión Mínima.

JOSÉ ANTONIO RIVERA COLMENERO 125

Paso 3. En la ventana Crear el conjunto de datos para el Árbol de Expansión mínima,
se escribe el título del problema que se va a resolver “Lauderdale Construction”. Se
indica el número de arcos o ramas (Number of Branches) en la red, 13. Se presiona el
botón “OK”.

FIGURA 7.27.
Ventana para crear el conjunto de datos en la red del árbol de expansión mínima.
Paso 4. Se les da un nombre a cada una de los arcos o ramas de la red (Branch name), se
ingresan los datos de las distancias (Cost, equivalente a costo) entre los nodos. Se
selecciona el nodo inicial para el inicio de las iteraciones (Startintg node for iterations),
se proporciona el nodo 1. Se presione el botón “Solve”.

Paso 5. La solución del árbol de expansión mínima, que se obtiene con QM para Windows
es presionando el botón “Solve”:

JOSÉ ANTONIO RIVERA COLMENERO 126

FIGURA 7.28
Captura de las distancias de los arcos o ramas, se establece el nodo inicial para las
iteraciones.

FIGURA 7.29.
Solución de QM para Windows versión 4.0 para el problema del árbol de expansión
mínima de la Lauderdale Construction.

JOSÉ ANTONIO RIVERA COLMENERO 127

FIGURA 7.30.
Solución simplificada del árbol de expansión mínima.

FIGURA 7.31.
Red que hace mínima la suma de las distancias entre las conexiones de los nodos.

Observe que existen soluciones óptimas múltiples.

JOSÉ ANTONIO RIVERA COLMENERO 128

7.1. Problema Resuelto
PROBLEMA RESUELTO
Un fabricante quiere instalar aire acondicionado en una de sus plantas. Para ello, ha
considerado varias alternativas para la instalación de los conductos hacia las salidas
deseadas. Los lugares de las salidas están representadas por nodos en el siguiente
diagrama de red. Los arcos que conectan a los nodos representan los conductos, y las
cantidades en los arcos muestran el costo de las conexiones particulares. Encuentre el
sistema de conexiones que minimizarán el costo total del sistema.

FIGURA 7.32.
Red que hace mínima la suma de las distancias entre las conexiones de los nodos.

JOSÉ ANTONIO RIVERA COLMENERO 129

SOLUCIÓN:
El costo total del sistema es 146.

Recepción Oficinas administrativas

9 8
1 2 3

8 12 7

10 10
6 5 4

6 14 5 15
11
20
7 8 18
7 9
9 6 10
18 9
11 10 14
17 11

11 10
12 17
7 13
12
14 16
12 11
13 15 10 9

13 18
19 18

15
Inventario Transporte

DEL NODO AL NODO COSTO DEL NODO AL NODO COSTO

1 2 9 10 16 10
2 3 8 10 17 11
3 4 7 12 13 13
5 8 5 12 14 7
1 6 8 14 15 10
6 7 6 15 16 9
7 11 9 16 18 11
8 10 6 COSTO TOTAL 146
8 11 7
9 10 10

JOSÉ ANTONIO RIVERA COLMENERO 130

7.2. Problemas Propuestos
7-1. Una compañía de televisión por cable quiere determinar la forma menos costosa de
conectar las casas que se están construyendo con TV por cable. Ha identificado 11
arcos, ramas o rutas posibles para conectar las casas. El costo en miles de pesos se
muestran sobre las ramas o arcos en la siguiente red.

a) ¿Cuál es la manera menos costosa de cablear las casas?

b) Después de revisar los costos de cable y la instalación, la compañía de televisón

por cable desea alterar los costos de instalación del cableado entre sus casas.
Necesita cambiar las primeras ramas. Los cambios se resumen en la siguiente
red. ¿Cuál es el impacto en los costos totales?

JOSÉ ANTONIO RIVERA COLMENERO 131

7-2. Encuentre el árbol de expansión mínima de la siguiente red.

7-3. Una empresa de televisión por cable quiere conectar varias colonias a su sistema de
cable. La empresa ha identificado varias alternativas para las conexiones y el costo de
cada conexión potencial, como se muestra en la siguiente red. Determine el conjunto
de conexiones que minimizan el costo total por el enlace de estas colonias al sistema
de televisión por cable.

13 15
2 4 7
16
8 10 11 10 11
11 7
14 12
3 6 9
10 13
1 9 10 8
17
15 11
5 8 10
JOSÉ ANTONIO RIVERA COLMENERO 132
7-4. Encuentre el conjunto de arcos que interconecten todos los nodos en esta red
utilizando el menos material posible.

15 5
2 14
16 8
8 11 8
9
8 6
1 9
3 10 9
2
10
3 7 7
9
4 12

7-5. Bechtold Construction está en proceso de instalar líneas eléctricas en un gran

desarrollo de viviendas. Steve Bechtold desea minimizar la longitud total del cable
utilizado, lo cual minimizará sus costos. El desarrollo de la vivienda se muestra como
una red en la siguiente figura. Cada casa ha sido numerada, y las distancias entre las
casas se dan en cientos de pies. ¿Que le recomienda?

JOSÉ ANTONIO RIVERA COLMENERO 133

 Capítulo 8
El Problema del Agente Viajero
(The Traveling Salesman
Problem)
8.1. El Problema del Agente Viajero (The Traveling Salesman
Problem, TSP)
Quizás el problema clásico de optimización combinatoria más famoso es conocido como el
problema del agente viajero. Se le ha dado este nombre pintoresco porque se puede
describir en términos de un agente de ventas que debe visitar varias ciudades en un solo
viaje. A partir de su ciudad de origen, el vendedor desea determinar qué ruta debe seguir
para visitar cada ciudad exactamente una vez antes de regresar a su ciudad de origen para
minimizar la duración o longitud total del viaje.
La Figura 8.1 muestra un ejemplo de un pequeño problema del agente viajero con siete
ciudades. La ciudad 1 es la ciudad natal del vendedor. Por lo tanto, a partir de esta ciudad,
el vendedor debe elegir una ruta para visitar cada una de las otras ciudades exactamente una
vez antes de regresar a la ciudad 1. El número al lado de cada enlace o arco entre cada par
de ciudades representa la distancia (o el costo o el tiempo) entre estas ciudades. Se supone
que la distancia es la misma en cualquier dirección. (Esto se conoce como un problema
simétrico del agente viajero). Aunque comúnmente existe un enlace directo entre cada par
de ciudades, se simplifica este ejemplo suponiendo que los únicos enlaces directos son los
que se muestran en la Figura 8.1. El objetivo es determinar qué ruta minimizará la
distancia total que el agente viajero debe viajar.

JOSÉ ANTONIO RIVERA COLMENERO 134

FIGURA 8.1.
Ejemplo de un problema del agente viajero que se utilizará con fines ilustrativos a lo largo
de esta sección.
Han existido una serie de aplicaciones de problemas de egentes viajeros que no tienen nada
que ver con un agente de ventas. Por ejemplo, cuando un camión sale de un centro de
distribución para entregar mercancías a varios lugares, el problema de determinar la ruta
más corta para hacerlo es un problema del agente viajero.

La dificultad de los problemas de los agentes viajeros se complica rápidamente a medida

que aumenta el número de ciudades. En el caso de un problema con n ciudades y un enlace
entre cada par de ciudades, el número de rutas posibles a considerar es ( n−1 ) ! /2 puesto que
hay (n−1) posibilidades para la primera ciudad después de la ciudad de residencia del
agente viajero, (n−2) posibilidades para la siguiente ciudad, y así sucesivamente. El
denominador de 2 surge porque cada ruta tiene una ruta inversa equivalente con
exactamente la misma distancia. Por lo tanto, mientras que un problema de un agente
viajero con 10 ciudades tiene menos de 200,000 soluciones factibles que deben ser
consideradas, un problema de 20 ciudades tiene aproximadamente 1016 soluciones factibles,
mientras que un problema con 50 ciudades tiene aproximadamente 1062 soluciones.

Algoritmo del subviaje inverso

Paso inicial. Comience con cualquier viaje factible como la solución de prueba inicial.

Iteración. Para la solución de prueba actual, considere todas las formas posibles de
realizar un subviaje inverso (solo excluya el inverso del viaje completo) que proporcionaría
una solución mejorada. Seleccione el que proporciona la mayor disminución en la distancia
viajada para que sea la nueva solución de prueba. (Los empates se rompen de manera
arbitraria).

Regla de detención. Deténgase cuando ninguna inversión de un subviaje mejore la

solución de prueba actual. Acepte esta solución como la solución final.

JOSÉ ANTONIO RIVERA COLMENERO 135

Ahora se aplicará este algoritmo al ejemplo, comenzando con 12345671 como la
solución de prueba inicial. Hay cuatro posibles subviajes que mejorarían esta solución,
como se indica a continuación en el segundo, tercero, cuarto y quinto renglones:

Se inicia con un viaje factible: 12345671 Distancia: 12+8+11+11+6+9+12 = 69

Inverso 23: 13245671 Distancia: 10+8+12+11+6+9+12 = 68
Inverso 34: 12435671 Distancia: 12+12+11+3+6+9+12 = 65
Inverso 45: 12354671 Distancia: 12+8+3+11+10+9+12 = 65
Inverso 56: 12346571 Distancia: 12+8+11+10+6+7+12 = 66

Las dos soluciones con Distancia = 65 empatan, ya que proporcionan la mayor disminución
en la distancia viajada, suponga que se elige de manera arbitraria la primera de estas,
12435671 (como se muestra en el lado derecho de la Figura 8.2), se elige de
manera arbitraria como la siguiente solución de prueba, con lo cual se completa la primera
iteración.

FIGURA 8.2.
Inversión de un subviaje que reemplaza el viaje de la izquierda (la solución de prueba
inicial) por el viaje de la derecha (la nueva solución de prueba) al invertir el orden en
que se visitan las ciudades 3 y 4. Esta reversión del subviaje es el resultado de la
sustitución de las líneas discontinuas de la izquierda por las líneas discontinuas de la
derecha como los enlaces que se invierten en el nuevo viaje.

La segunda iteración comienza con el recorrido en el lado derecho de la Figura 8.3., como
la solución de prueba actual. Para esta solución, solo hay una inversión de un subviaje que
proporciona una mejora, como se indica a continuación en el segundo renglón:

Segunda iteración: 12435671 Distancia: 12+12+11+3+6+9+12 = 65

Inverso 356: 12465371 Distancia: 12+12+10+6+3+9+12 = 64

JOSÉ ANTONIO RIVERA COLMENERO 136

FIGURA 8.3.
Inversión del subviaje 3-5-6 que conduce desde la solución de prueba de la izquierda
hasta una solución de prueba mejorada de la derecha.

La Figura 8.3., muestra este subviaje inverso, donde la subsecuencia completa de las
ciudades 356 de la izquierda ahora se visita en orden inverso (653) a la derecha. Por
lo tanto, en el viaje a la derecha ahora se presenta un enlace 46 en lugar de 43, así como
el enlace 37 en lugar de 67, para usar el orden inverso 653 entre las ciudades 4 y 7.
Esto completa la segunda iteración.

A continuación, intentamos encontrar un subviaje inverso que mejore esta nueva solución
de prueba. Sin embargo, no existe ninguna, por lo que se detiene el algoritmo del subviaje
inverso con esta solución de prueba como la solución final.

¿Es 12465371 la solución óptima? Lamentablemente no. La solución óptima

resulta ser:
12467531 Distancia: 12+12+10+9+7+3+10 = 63

O bien, al invertir la dirección de este viaje completo:

13576421 Distancia: 10+3+7+9+10+12+12 = 63

El algoritmo del subviaje inversos es otro ejemplo de un procedimiento de mejora local.

Mejora la solución de prueba actual en cada iteración. Cuando ya no puede encontrar una
mejor solución, se detiene porque la solución de prueba actual es un óptimo local. En este
caso, 12465371 es de hecho un óptimo local porque no hay una mejor solución
dentro de su vecindad local que pueda ser alcanzada mediante la invesrión de un subviaje.

JOSÉ ANTONIO RIVERA COLMENERO 137

FIGURA 8.4.
Solución óptima del problema del agente viajero.

Solución con el software Launch TSPSG

Se resuelve el problema del agente viajero con el software Launch TSPSG. El software
TSPSG (TSP Solver and Generator) que se caracteriza por una interfaz intuitiva y que a
continuación se detalla la implementación de nuestro problema (recordar que City 1
correspondería a la Ciudad 1, y así sucesivamente).

FIGURA 8.5.
Red para el problema del agente viajero.

JOSÉ ANTONIO RIVERA COLMENERO 138

Paso 1. Se activa el software dan clic con el mouse sobre el ícono:

FIGURA 8.6.
Icono del software Launch TSPSG para resolver el problema del agente viajero..

Paso 2: Ingrese los datos. Escriba los valores sobre los arcos, considerando los números
de los arcos, de atrás hacia adelante. Como se observa es una matriz simétrica.

FIGURA 8.7.
Captura de los datos de la red para el problema del agente viajero.

Paso 3. Una vez ingresados los datos al seleccionar “Solve” en la parte inferior de la
pantalla. Entonces, el programa se ejecuta entregando los resultados, que por cierto
coincide con el que identificamos en la solución del algoritmo del subviaje inverso con 63
unidades de longitud o de tiempo.

JOSÉ ANTONIO RIVERA COLMENERO 139

FIGURA 8.8.
Solución óptima que proporciona la ruta más corta para visitar todas las ciudades.
Solución con el software Launch TSPSG

Ejemplo 1. Se resuelve el problema del agente viajero con el software Launch TSPSG.
El software TSPSG (TSP Solver and Generator) que se caracteriza por una interfaz
intuitiva y que a continuación se detalla la implementación de nuestro problema (recordar
que City 1 correspondería a la Ciudad 1, y así sucesivamente).

JOSÉ ANTONIO RIVERA COLMENERO 140

SOLUCIÓN:
Usando el software Launch TSPSG.

Paso 1. Se activa el software dan clic con el mouse sobre el ícono:

Paso 2: Ingrese los datos. Escriba los valores sobre los arcos, y considerando todos los
nodos de atrás hacia adelante y de adelante hacia atrás. Como se observa es una matriz
simétrica. Una vez ingresados los datos al seleccionar “Solve” en la parte inferior derecha
de la pantalla.

Paso 3: Ver la solución del problema del agente viajero:

JOSÉ ANTONIO RIVERA COLMENERO 141

Paso 4: Trazar en la red, la ruta que debe seguir el agente viajero para hacer mínima la
distancia del recorrido.

Ejemplo 2. Resuelva el siguiente problema del agente viajero, donde se debe determinar
la ruta más corta de ida y regreso el nodo de partida es el nodo 1.

JOSÉ ANTONIO RIVERA COLMENERO 142

Se ingresan los datos al software Launch TSPSG.

JOSÉ ANTONIO RIVERA COLMENERO 143

Como se observa en la red, no todos los nodos están conectados y debido a esto la matriz
del software Launch TSPSG, aparece con bastantes ceros. Para que el software considere
que no existe un enlace entre las uniones con valor de cero, se cambia el valor de 0 por un
guión “-“ que hace la función de sin enlace.

JOSÉ ANTONIO RIVERA COLMENERO 144

Se seleccióna con un clic del ratón el botón “Solve”.

JOSÉ ANTONIO RIVERA COLMENERO 145

La red que presenta una solución al problema del agente viajero es:

La ruta que debe seguir el agente viajero partiendo del nodo 1 y regresando al mismo nodo
es:

Distancia mínima de recorrido: 1 3  5  4  6  7  8  9  10  2  1. Cuya

suma de distancias es: 1.5 + 1.5 + 1 + 2 + 1 + 3 + 1 + 5 + 2 + 1 = 19 unidades de longitud

8.2. Problemas resueltos

PROBLEMA RESUELTO 1

Considere el problema del agente viajero que se muestra a continuación, donde la ciudad 1
es la ciudad de origen.

JOSÉ ANTONIO RIVERA COLMENERO 146

(a) Enumere todos los viajes posibles, excluya aquellos que solo inviertan el orden de los
viajes listados anteriormente. Calcule la distancia de cada uno de estos viajes e
identifique la solución óptima.
(b) Comience con 1234561 como la solución de prueba inicial, aplique el
algoritmo de subviaje inverso a este problema.
(c) Aplique el algoritmo de subviaje inverso este problema cuando comience con
1254361 como la solución de prueba inicial.

SOLUCIÓN:
(a) Enumere todos los viajes posibles:

Viaje Distancia
1234561 11 + 10 + 7 + 6 + 5 + 9 = 48
1234651 11 + 10 + 7 + 5 + 5 + 6 = 44
1236451 11 + 10 + 12 + 5+ 6 + 6 = 50
1243651 11 + 7 + 7 + 12 + 5 + 6 = 48
1254361 11 + 5 + 6 + 7 + 12 + 9 = 50
1263451 11 + 10 + 12 + 7 + 6 + 6 = 52
1523461 6 + 5 + 10 + 7 + 5 + 9 = 42
1524361 6 + 5 + 7 + 7 + 12 + 9 = 46
1623451 9 + 10 + 10 + 7 + 6 + 6 = 48
1632451 9 + 12 + 10 + 7 + 6 + 6 = 50

Solución óptima: 1523461 (o al revés 1643251) con una distancia

de 42 unidades de longitud.
(b) Se comienza con la solución de prueba inicial 1234561. Existen dos posibles
subviajes inversos que me mejoran esta solución:

Se inicia con un viaje factible: 1234561 Distancia: 11+10+7+6+5+9 = 48

Inverso 56: 1234651 Distancia: 11+10+7+5+5+6 = 44
Inverso 2345: 1543261 Distancia: 6+6+7+10+10+9 = 48

Seleccione 1234651 como la siguiente solución de prueba. No hay subviajes

inversos que mejoren esta solución.
(c) Si se comienza con la solución de prueba inicial 1 254361. Existen dos
posibles subviajes inversos que mejoran esta solución.
Solución de prueba inicial: 1254361 Distancia: 11+5+6+7+12+9 = 50
Inverso 25: 1524361 Distancia: 6+5+7+7+12+9 = 46
Inverso 543: 1234561 Distancia: 11+10+7+6+5+9 = 48

Seleccione 1524361 como la siguiente solución de prueba. No existen

subviajes inversos que mejoren esta solución.
JOSÉ ANTONIO RIVERA COLMENERO 147
 PROBLEMA RESUELTO 2

Con la siguiente serie de nodos, construya la red K 7.

Dibuje los arcos en el siguiente orden: 01, 12, 23, 34, 45, 56, 60, 02, 24, 46, 61, 13, 35,
50, 03, 36, 62, 25, 51, 14, 40.

Recuerde que el número de arcos se obtiene con la ecuación:

v (v −1)
()
Kv= v =
v!
2 2 ! ( v −2 ) !
=
2

Donde v es el número de vértices o nodos. Para este caso, se tienen:

7 (7−1) 42
K7= = =21 arcos
2 2

SOLUCIÓN:

La red se representa como:

JOSÉ ANTONIO RIVERA COLMENERO 148

 PROBLEMA RESUELTO 3
El problema del agente viajero, consiste en que un
agente de ventas visita n ciudades, sale de una
determinada ciudad, visita sólo una vez cada
ciudad de cierta región, siguiendo una ruta que lo
lleve a la ciudad de donde partió . Él desea
encontrar la ruta que minimice la distancia
recorrida.

Este problema se observa en los siguientes

fenómenos administrativos:

• Entregas.
• Inspecciones.
• Ruta del autobús escolar.
• Ruta del camión recolector de basura, etc.

Veamos el siguiente ejemplo sencillo: ¿cuál es el costo mínimo de la ruta que sigue un
agente viajero que se detiene en las ciudades A, B, C y D sin pasar dos veces por la misma
ciudad. La Figura 3-1 es una red representativa del problema del agente viajero. Las
distancias están dadas en kilómetros. Si el costo del viaje por kilómetro es constante,
entonces la ruta de costo mínimo es la ruta más corta.
B
B

15 13
11 21
12
17
14 21 10

A 12 8
A 25 17 C
C
23 30
23 13
30
D
D
Figura 3-1. Red representativa del problema del agente viajero (red simétrica)
Figura 4 2 2 .1 Figura 4 2 2 .2
De donde es fácil ver que existen tres rutas posibles:

ABCDA: Costo = 12 + 17 + 30 + 23 = 82.

ABDCA: Costo = 12 + 14 + 30 + 25 = 81.
ADBCA: Costo = 23 + 14 + 17 + 25 = 79 ←

JOSÉ ANTONIO RIVERA COLMENERO 149

 B B B

12 12
17
17
14 14

A A 25 A 25
C C C
23 23
30 30 23
D D D

ABCDA: Costo = 12 + 17 + 30 + 23 = 82 ABDCA: Costo = 12 + 14 + 30 + 25 = 81 ADBCA: Costo = 23 + 14 + 17 + 25 = 79 ←

El problema origen-destino de la red original (Figura 1) se presenta en forma de tabla o

matriz, como sigue:

A B C D
A 0 12 25 23
B 12 0 17 14
C 25 17 0 30
D 23 14 30 0

Red simétrica

La ruta ADBCA es la que proporciona el costo mínimo.

B
B

15 13
11 21
12
17
14 21 10

A 12 8
A 25 17 C
C
23 30
23 13
30
D
D
Figura 3-2. Red representativa del problema del agente viajero (red asimétrica)
Figura 4 2 2 .1 Figura 4 2 2 .2
JOSÉ ANTONIO RIVERA COLMENERO 150
En algunos problemas, los costos no son simétricos (Figura 2), en tales casos, existe el
doble de rutas que deberán examinarse (6 en este ejemplo):

ABCDA: Costo = 15 + 21 + 30 + 13 = 79
ABDCA: Costo = 15 + 11 + 23 + 12 = 61
ACBDA: Costo = 8 + 10 + 11 + 13 = 42 ←
ACDBA: Costo = 8 + 30 + 21 + 13 = 72
ADBCA: Costo = 17 + 21 + 21 + 12 = 71
ADCBA: Costo = 17 + 23 + 10 + 13 = 63.

No existe un método analítico para resolver este problema, y es imposible en la práctica

calcular todas las soluciones y determinar la mejor cuando se tiene un número grande de
ciudades. Por ejemplo con 12 ciudades hay 39,916,800 rutas distintas si la tabla de costos
es asimétrica, y 19,958,400 si es simétrica.

El problema origen-destino de la red original (Figura 2) se presenta en forma de tabla o

matriz, como sigue:
A B C D
A 0 15 8 17
B 13 0 21 11
C 12 10 0 30
D 13 21 23 0
Red asimétrica

Nos podemos imaginar la situación donde deben planearse las rutas con una red
incompleta, es decir, donde no existen conexiones entre determinadas ciudades. En este
caso, el problema se vuelve todavía más complicado.

PROBLEMA RESUELTO 4
Encuentre la ruta del agente viajero para partir del nodo1 y regresar al mismo noddo

JOSÉ ANTONIO RIVERA COLMENERO 151

 Solución con el software Launch TSPSG
Paso 1. Se cargan los datos en el software y al terminar se da clic en el botón “Solve”.

Paso 2. Se visualizan los resultados de la ruta del agente viajero.

JOSÉ ANTONIO RIVERA COLMENERO 152

Paso 3. La red representativa óptima de la ruta del agente viajero, con una ruta
154321 recorre una distancia igual a: 3 + 5 + 2 + 3 + 4 = 17 unidades de
longitud.

PROBLEMA RESUELTO 5
Las posibles rutas de ida y vuelta si se parte del nodo V (Alcaldía Venustiano Carranza)
y se visitan las demás alcaldías se muestra en la siguiente figura.

Posibles caminos para el agente viajero considerando cinco Alcaldías de la Ciudad de

México: V, Venustiano Carranza; G, Gustavo A. Madero; L, La Magdalena Contreras;
B, Benito Juárez; M, Miguel Hidalgo.

JOSÉ ANTONIO RIVERA COLMENERO 153

8.3. Problemas propuestos
8-1. Encuentre la ruta más corta del agente viajero, si parte del nodo 1.

8-2. Encuentre la ruta más corta del agente viajero, si parte del nodo 1.

JOSÉ ANTONIO RIVERA COLMENERO 154

8-3. Considere las siguientes Figuras (a) y (b), donde se da la solución de un viaje
visitando todos los nodos partiendo del nodo B y terminando en el mismo nodo.

BCPNMDFKLTSRQZXWVJHGB
BCPNMDFGHXWVJKLTSRQZB

Para las Figuras (a) y (b), encuentre un nuevo recorrido de ida y vuelta iniciando en
cualquiera de los siguientes nodos C, P, N o M y terminando en el mismo nodo.

JOSÉ ANTONIO RIVERA COLMENERO 155

 Capítulo 9
Redes Sociales

Justificación

Este capítulo ofrece una introducción al análisis de redes sociales, lo que implica que cubre
un conjunto limitado de temas y técnicas, que un principiante debe dominar para poder
encontrar su camino en el campo del análisis de redes sociales. Es complicado tomar
decisiones sobre qué incluir y qué excluir por el momento considere los aspectos básicos de
la teoría de redes sociales en este capítulo.

Introducción
Teoría de grafos. Pasando por algunos hitos preliminares de fuerte impacto, como el
famoso “problema de los cuatro colores” propuesto por Francis Guthrie [1831-1899] en
1852, la historia de la teoría de las redes sociales se remonta a los orígenes de la teoría de
grafos en matemáticas, creada hacia 1736 por el suizo Leonhard Euler [1707-1783]. Este
matemático prodigioso, uno de los escritores más prolíficos de la historia, inventó de la
noche a la mañana

JOSÉ ANTONIO RIVERA COLMENERO 156

la teoría de grafos al resolver el famoso problema de los siete puentes sobre el río Pregel en
Königsberg, una ciudad hace tiempo impersonal que en algún momento se renombró
Kaliningrado.

El problema consistía en averiguar si se puede pasar por los siete puentes sin cruzar más de
una vez por cada uno de ellos. Lo que hizo Euler en su planteamiento fue como lo que
acostumbraba hacer el antropólogo Clifford Geertz sólo que al revés: en lugar de ahondar el
problema en sus más ínfimos matices de significado (como imponen los modelos de la
descripción densa y del conocimiento local) lo despojó de todo cuanto fuese inesencial al
razonamiento ulterior; en vez de subrayar su peculiaridad, lo vació de lo contingentemente
específico y lo generalizó. Para ello eliminó de cuajo toda información irrelevante al
cálculo de la solución, dejando sólo las masas de tierra representadas por un punto, vértice
o nodo, y los puentes mismos concebidos como líneas, aristas, bordes o arcos. La
orientación y longitud de los trazos tampoco fueron tomados en consideración. Integrando a
un razonamiento casi algebraico nada más que la paridad o imparidad de los grados, ni
siquiera el número de nodos o de conexiones formó parte del planteo. El grafo abstraído por
él es lo que hoy se conoce como un multigrafo, un grafo que admite más de una arista o
arco por vértice o nodo (Figura 9.1).

FIGURA 9.1.
Serie de abstracciones desde los puentes de Königsberg hasta su grafo. (1) Mapa de
dominio público de Königsberg basado en Aldous y Wilson (2000: 9); (2) Dibujo original de
Euler (1741: 129); (3) Diagrama basado en Barabási (2003: 11); (4) Grafo diseñado por el
autor con JgraphEd.

JOSÉ ANTONIO RIVERA COLMENERO 157

Hasta ahora, hemos considerado las redes de comunicación bastante técnicas. En estas
redes, los nodos generalmente están formados por fábricas, casas, negocios, centros de
distribición u otros componentes. Sin embargo, la teoría de redes también se ha utilizado
ampliamente para analizar estructuras sociales, también conocidas como redes sociales.
En una red social, un nodo representa una entidad social, típicamente una persona, una
organización, etc. Un arco o linea representa una relación específica entre sus nodos
incidentes. En contraste con otras áreas de las ciencias sociales en las que es importante
entender qué caracteriza a las entidades sociales (por ejemplo, al considerar sus atributos),
el análisis de redes sociales se concentra en la estructura de las relaciones y trata de
explicar los fenómenos sociales de aquellas estructuras. No debería sorprender que la teoría
de redes desempeñe un papel importante en el análisis de redes sociales.

La teoría de redes sociales es una de las pocas teorías en ciencias sociales que se puede
aplicar a una variedad de niveles de análisis desde pequeños grupos hasta sistemas globales
completos. Los mismos conceptos poderosos trabajan con grupos pequeños, con
organizaciones, naciones y sistemas internacionales.

¿Qué es una Red?

Para analizar una red, primero debemos tener una. ¿Qué es una red? Aquí, y en otros
lugares, usamos una rama de las matemáticas llamada teoría de grafos para definir
conceptos. La mayoría de las características de las redes que introducimos en este
documento provienen de la teoría de grafos. Aunque este no es un curso en teoría de
grafos, se deben estudiar las definiciones cuidadosamente para comprender lo que se está
haciendo cuando se aplica el análisis de red.

Comenzamos con una definición más precisa de “red”: una red es un conjunto de
relaciones.

Un grafo o red es un conjunto de nodos o vértices y un conjunto de arcos o líneas que

los unen.

Más formalmente, una red contiene un conjunto de objetos (en términos matemáticos,
nodos) y una asignación o descripción de las relaciones entre los objetos o nodos. La red
más simple contiene dos objetos, 1 y 2, y una relación que los vincula. Los nodos 1 y 2, por
ejemplo, pueden ser personas, y la relación que los une puede ser tan simple como estar en
la misma habitación. Si 1 está en la misma habitación que 2, entonces 2 está en la misma
habitación que 1. La relación en la Figura 9.2.(a) no es direccional.

FIGURA 9.2.(a).
Relación simple, se representa con una línea o arco, y va del nodo 1 al nodo 2 y
viceversa (relación mutua).
JOSÉ ANTONIO RIVERA COLMENERO 158
En esta red simple, la relación podría ser simétrica. Los nodos 1 y 2 son similares entre sí, o
su relación es mutua.

FIGURA 9.2.(b).
Relación dirigida, se representa con una línea con una flecha, y va del nodo 1 al nodo 2.

La siguiente red de contactos, Figura 9.2(c), es similar a la primera de estar juntas en la

misma habitación, pero tiene una valencia o un flujo. Sin embargo, la mutualidad es un
asunto delicado, y no es tan fácil de lograr, por lo que las redes mutuas tienden a ser
limitadas. Un empate prevalente entre las díadas2 es antisimétrico. Padre e hijo, jefe y
empleado son ejemplos. La relación es por definición diferente, dependiendo de cómo se
mire.

FIGURA 9.2.(c).
Relación simétrica, se representa con una línea con una flecha en cada extremo, y va
del nodo 1 al nodo 2 y viceversa (relación mutua).

No es necesario que haya una sola relación asignada entre los nodos 1 y 2. Por ejemplo, 1 y
2 pueden estar en la misma habitación y también pueden relacionarse entre sí. Cuando hay
más de una relación, esto se llama una relación múltiplex.

Aparte de su direccionalidad, o falta de ella, las relaciones pueden ser más que compartir un
atributo o estar en el mismo lugar al mismo tiempo. Puede haber un flujo entre los objetos o
los nodos. Tener una amistad, por ejemplo, podría llevar a un intercambio de regalos. Los
flujos y los intercambios son muy importantes en la teoría de redes.

En un nivel, esta lista de conceptos de relaciones entre pares de nodos ahora está
lógicamente completa. Pero considere una red, Figura 9.2.(d) entre pares que opera a
través de un nodo intermedio. Por ejemplo:

FIGURA 9.2.(d).
Relación a través de un intermediario.

2
Pareja formada por dos seres o principios muy estrechamente vinculados entre sí.
JOSÉ ANTONIO RIVERA COLMENERO 159
El nodo 1 está conectado con el nodo 3 a través del nodo 2. Las relaciones mostradas
anteriormente son direccionales y no recíprocas. Pueden ser transitivos o pueden no serlo.
Si la relación es transitiva, significa que si 1 tiene amistad con 2, entonces 2 también tiene
amistad con 3. Posible, pero no es probable. Las relaciones transitivas son más comunes
en una jerarquía oficial. El nodo 1 da un mensaje al nodo 2 que lo reenvía al nodo 3.

Uno puede describir la distancia de la red entre pares de nodos en términos de la cantidad
de pasos o enlaces entre ellos. Obviamente, hay dos pasos entre 1 y 3. Pero si 1 también
tiene amistad con 3, como se muestra a continuación, Figura 9.2.(e), se dice que la red es
transitiva o equilibrada y mutua y, en este caso, los tres nodos están directamente
vinculados .

FIGURA 9.2.(e).
Sociograma de tres nodos, todos mutuamente relacionados.

La red que se muestra en la Figura 9.2.(e) es un “sociograma”, un término inventado por

Jacob Moreno (Moreno 1953), considerado por muchos como un fundador clave de los
estudios de redes modernas. También es lo que los matemáticos llaman un grafo. Hay una
rama de las matemáticas, la teoría de grafos, que permite manipular matemáticamente los
sociogramas (Harary, Norman y Cartwright, 1965). La descripción de las relaciones como
sociogramas les permitió a los observadores una visión casi instantánea de lo que estaba
sucediendo en redes pequeñas y no demasiado complicadas. La adición de la teoría de
grafos a las herramientas para comprender las redes permitió comprender y manipular
redes mucho más grandes y complejas. En esta introducción a la teoría de redes,
prescindiremos de las matemáticas de la teoría de grafos, pero confiaremos en sus ideas y
descubrimientos. La red simple de tres unidades se llama tríada. Esta red simple resulta ser
el componente básico de relaciones más complejas.

Muchos analistas de redes, y gran parte del software para manipular redes, prefieren
trabajar algebraicamente con redes cuando se representan y se expresan como matrices. A
continuación (Tabla 9.1) se encuentra el mismo sociograma pero en forma matricial. En
términos de red, llamamos a esto una matriz de adyacencia porque muestra quién está al
lado de quién.

JOSÉ ANTONIO RIVERA COLMENERO 160

 Matriz de Adyacencia que representa la
Figura I.2.(e).
1 2 3
1 0 1 1
2 1 0 1
3 1 1 0

TABLA 9.1.
La matriz de adyacencia que representa la Figura 9.2.(e).

Los números, 1 ,2 y 3en la línea superior y la primera columna identifican los mismos
nodos que en la Figura 9.2.(e). El número 1 en la segunda línea indica una conexión entre
los nodos. El nodo 1 “elige” los nodos 2 y 3. El nodo 2 “elige” los nodos 1 y 3. El nodo 3
“elige” los nodos 1 y 2. Los ceros (0s) indican que en este grafo o matriz, la propia
elección no está en juego, aunque en algunas redes de libre elección pueden ser una opción.
Por ejemplo, los candidatos en una elección pueden votar por sí mismos.

Aunque todos nuestros ejemplos hasta ahora han sido sociales, en principio, podríamos
haber estado hablando de corrientes eléctricas. Hay una rama de la teoría de redes que trata
estos asuntos, aunque los circuitos eléctricos tienden a ser considerablemente más simples
que las redes sociales. Pero considere en cada nivel de análisis, individual, organización o
estadonación, por ejemplo, ¿cuáles son las condiciones que hacen más o menos probable
que exista una ruta entre dos nodos, que los nodos tendrán los mismos atributos, que ellos
estarán relacionados recíprocamente o mutuamente entre sí?, ¿y que las tríadas estarán
equilibradas? Las respuestas se encuentran en la teoría social. Ahora introducimos algunas
hipótesis elementales sobre estas condiciones.

Los científicos sociales han investigado tres tipos de redes: redes centradas en el ego,
sociocéntricas y de sistemas abiertos. Las redes centradas en el ego son aquellas redes
que están conectadas con un solo nodo o individuo, por ejemplo, mis buenos amigos o
todas las compañías que hacen negocios con Widgets, Inc. (el nombre favorito de las
organizaciones estudiadas en escuelas de negocios). Sin embargo, una lista no es
necesariamente una red. En el discurso popular, especialmente cuando se discute el apoyo
social, cualquier lista se llama “red”. Es una red en un sentido básico porque incluso si
ninguna de las personas de la lista está conectada entre sí, al menos todas las personas están
conectadas con la persona que recibe el apoyo. El apoyo puede incluir ayuda con la
búsqueda de empleo, reconfortar durante una enfermedad o un préstamo de dinero o una
cortadora de césped. Se dice comúnmente que una persona con una gran cantidad de
buenos amigos con los que puede contar tiene una gran “red”. Sin embargo, esta red no se
puede discutir en términos de redes sociales, a menos que sepamos si estas personas están
conectadas entre sí y cómo lo hacen. Obviamente, una cosa es tener una red de apoyo en la
que la mayoría de las personas se conozcan y una cuestión muy diferente si las personas
son desconocidas entre sí.

Las redes sociocéntricas son redes en una “caja”. Las conexiones entre los niños en un
aula o entre ejecutivos o trabajadores en una organización son las redes de sistemas

JOSÉ ANTONIO RIVERA COLMENERO 161

cerrados y las más estudiadas en términos de los puntos finos de la estructura de la red.
Estas fueron con los que Moreno comenzó sus estudios. Las redes de sistemas abiertos
son redes en las que los límites no son necesariamente claros, ya que no están en una caja,
por ejemplo, la élite de México, las conexiones entre corporaciones, la cadena de
influyentes de una decisión en particular o los adoptadores de nuevos practicas. De alguna
manera, estas son las redes más interesantes. Más adelante veremos el “Mundo pequeño” y
la difusión, que exploran estos sistemas abiertos con cierto detalle.

CONEXIONES

Ahora examinamos algunas de las situaciones y fuerzas sociales que hacen las conexiones
entre un nodo (por ejemplo, una persona, una organización, un país) y otro.

Equidad

En todos los niveles de análisis, es más probable que los nodos estén conectados entre sí, y
que otras condiciones sean iguales, si están geográficamente cerca unas de otras. Es más
probable que los individuos sean amigos si están cerca geográficamente (Feld y Carter,
1998). En un estudio pionero del efecto de la equidad, Festinger, Schacter y Back (1950)
demostraron que en un nuevo proyecto de vivienda para veteranos de la Segunda Guerra
Mundial, las personas que vivían cerca unas de otras tenían más probabilidades de
convertirse en amigos. Las personas en unidades de vivienda en una esquina tenían más
probabilidades de estar aisladas socialmente que las personas en unidades que se ubican
entre otras unidades. Además de la importancia de la ubicación, un estudio de redes en los
Estados Unidos de personas que trabajan juntas en diferentes juntas directivas corporativas
(llamadas “direcciones interconectadas”) se encontró que “[los enclavamientos se
concentran en empresas con sede en la misma ubicación”. Ser seleccionado para formar
parte de juntas directivas tiene más que ver con la estructura local de la clase alta, conocer a
las personas porque uno se encuentra con ellos en los mismos clubes, que con una simple
amistad. Aunque algunos de los mismos principios de red (en este caso, la equidad) se
aplican a personas individuales, empresas o países, la forma en que se desarrolla el
principio puede diferir para varios niveles de análisis. El comercio entre países, en igualdad
de condiciones, es más probable si los países tienen fronteras comunes. Pero, por ejemplo,
“promediado en todos los países de Europa, el comercio internacional es aproximadamente
diez veces más alto que el comercio internacional con un país socio de la comunidad
europea de tamaño y distancia similares” (Volker 2000). Los economistas tienden a definir
la propinquidad en términos de costo de transporte en lugar del número real de millas
entre nodos o cruces fronterizos cuando la tarifa no es un problema (Krugman y Obstfeld
2000).

La equidad también puede definirse más ampliamente como estar en el mismo lugar al
mismo tiempo. Hay una distinción entre la ubicación conjunta, que coloca a las personas
simplemente dentro del alcance de las demás, y la presencia conjunta, que implica una
relación social que está dentro del marco de una institución o estructura social (Zhao y
Elesh, 2008). Los intereses comunes (por ejemplo, la música) y las plazas o lugares
comunes para las reuniones (por ejemplo, las madres en el patio de recreo) son otra forma

JOSÉ ANTONIO RIVERA COLMENERO 162

de reunir a las personas (Feld 1981; Feld y Carter 1998; Kadushin 1966). Los estudios de
élites muestran que las personas tienen más probabilidades de tener una conexión, relación
o amistad si van a la misma escuela de preparación al mismo tiempo (Domhoff, 1967). Por
supuesto, estas personas pueden simplemente compartir un empate de “vieja escuela”
(fueron a la misma escuela pero en diferentes años), en cuyo caso estamos hablando de
homofilia, un tipo diferente de equidad.

Homofilia

Homofilia (del griego, “amor por lo mismo”) es un concepto introducido en la teoría social
por Lazarsfeld y Merton (1978 [1955]) que incorpora una proposición popular: “los
pájaros de una bandada que tienen las mismas plumas se parecen”, equivalente al refrán
mexicano: “Dios los cría y ellos se juntan”. Más formalmente, si dos personas tienen
características que coinciden en una proporción mayor de la esperada en la población de la
que provienen o en la red de la que forman parte, entonces es más probable que estén
conectadas (Verbrugge, 1977). Lo contrario también es cierto: si dos personas están
conectadas, entonces es más probable que tengan características o atributos comunes.
También hay una retroalimentación implícita: con el tiempo, las relaciones tienden a
ordenarse de modo que se vuelvan más homófilas. He dicho “gente”, pero el principio de
homofilia, como la equidad, se aplica por igual a grupos, organizaciones, países u otras
unidades sociales.

Homofilia a nivel individual

En el nivel individual, las personas tienen más probabilidades de tener una conexión,
amistad o asociación, si tienen atributos comunes (Lazarsfeld y Merton 1978 [1955]). Si
bien las normas comunes se promueven a través de atributos comunes, también lo son los
atributos comunes cuando la asociación o la amistad se producen como resultado de la
ubicación conjunta y las actividades comúnmente situadas (Feld y Carter, 1998).

Lazarsfeld y Merton distinguieron entre el estatus de homofilia, que puede ser atribuido
(por ejemplo, edad, raza, sexo) o adquirido (por ejemplo, estado civil, educación,
ocupación), y el valor de homofilia (por ejemplo, actitudes, estereotipos), que también
tiene. Ha sido denominado homogeneidad (Hall y Wellman 1985). Las actitudes comunes
pueden basarse en patrones de relaciones (Erickson 1988). Numerosos estudios han
documentado la tendencia a la homofilia en una variedad de redes sociales (McPherson,
Smith-Lovin y Cook 2001). Pero una investigación crítica y una pregunta teórica es qué
características, atributos o actividades se seleccionan en una situación dada para ser
candidatos destacados para la homofilia. Por ejemplo, la medida en que la situación valora
la “raza” o la define en términos del color de la piel afectará si las características comunes
como el color de la piel se relacionarán con la elección de los niños como amigos en una
situación de aula (Hallinan 1982; Hallinan y Williams 1989). Debido al principio de la
homofilia, el análisis de las redes sociales implica casi invariablemente la sociología de la
clase, el género, la etnia y la nacionalidad, así como los valores culturales. Parte de la
clasificación y agrupación de redes es, por supuesto, el resultado de atributos visibles, pero

JOSÉ ANTONIO RIVERA COLMENERO 163

parte es el resultado de atributos menos visibles. Para que los menos visibles sean más
visibles, los servicios de citas y coincidencia ofrecen listas de verificación a través de las
cuales intentan unir a las personas.

Hay dos tipos de causas de la homofilia. Las normas o valores comunes pueden unir los
nodos con atributos comunes, o lo contrario, los atributos y contactos comunes pueden
llevar a normas comunes, y esto es válido tanto para los individuos como para las
colectividades (Burt 1982, 234-238). Por ejemplo, un estudio de mujeres adolescentes
encontró que los estudiantes que pertenecían a la misma pandilla tendían a tener
puntuaciones similares en diversas medidas de comportamiento, como comer en exceso,
consumir alcohol, restringir la dieta, etc. Pero no sabemos si las adolescentes están juntas
porque comparten hábitos similares, o se han vuelto similares entre sí mientras se juntan
entre ellas (Hutchinson y Raspee 2007). En general, la investigación sobre homofilia
investiga las condiciones bajo las cuales es probable que ocurra la homofilia, factores que
en un sistema social fomentan qué tipo de similitudes y conducen a vínculos particulares
(McPherson, Smith-Lovin y Cook 2001). Esto es incluso más complejo de lo que parece
porque la homofilia es un proceso. Para reiterar, si las personas que salen juntas tienden a
tener las mismas actitudes, y si tienen las mismas actitudes, tienden a salir juntas (Erickson
1988). Las situaciones de gallina y huevo siempre crean dificultades, y una gran parte de la
formulación original de Lazarsfeld y Merton se dedicó a los intentos esencialmente
infructuosos de Lazarsfeld para resolver esto.

Una segunda causa para la homofilia es la localización estructural. Dos nodos pueden
tener los mismos atributos porque ambos operan en el mismo lugar y, una y otra vez (Feld y
Carter 1998). Mientras que pares similares tienden a formar una relación, la disponibilidad
de atributos similares es una función de la estructura social. Es más probable que encuentre
personas interesadas en resolver problemas matemáticos en una clase de física que en una
clase de literatura inglesa. Pero las personas atraídas por las matemáticas tienen más
probabilidades de elegir una clase de física que una clase de inglés. Al estudiar las
interacciones por correo electrónico, durante más de un año, de una población de más de
30,000 estudiantes y personal en una universidad, Kossinets y Watts (2009) pudieron
determinar que las preferencias individuales de personas similares y la ubicación social de
la comunidad produjeron homofilia. Pero las modestas preferencias iniciales de símilares a
otros se amplificaron en muchos intercambios de correo electrónico en patrones más fuertes
de homofilia; intereses similares llevaron a ubicaciones parecidas en las que los intereses
semejantes estaban más disponibles. La retroalimentación entre la estructura de la red y la
preferencia individual se hace especialmente notable con el tiempo.

En resumen, si las personas se reúnen, parece que hay cuatro procesos involucrados: (1)
se reunen las mismas clases de personas; (2) las personas se influyen entre sí y en el
proceso se vuelven iguales; (3) las personas pueden terminar en el “mismo lugar”; (4) y
una vez que están en el mismo lugar, el mismo lugar influye sobre ellas para que se
vuelvan iguales.

Homofilia y colectividades

JOSÉ ANTONIO RIVERA COLMENERO 164

Las hipótesis sobre la homofilia son sencillas para las personas individuales, pero algo
más complejas cuando se trata de colectividades. En el nivel organizativo, si la similitud
conduce a una mayor probabilidad de un empate depende del tipo de conexión, así como en
la industria.
Considere que Ford, Chrysler y General Motors tienen características comunes: son
fabricantes de automóviles y están geográficamente adyacentes en Detroit. Pero las
características comunes y la continuidad geográfica no necesariamente conducen a un
empate. Por ejemplo, Ford no vende autos a General Motors. Por otro lado, cuando los
ingenieros y los gerentes se mudan de una compañía a otra, se desarrolla un empate entre
las compañías automotrices. De manera similar, las empresas de software en Silicon Valley
se vinculan entre sí a través de su práctica de otorgar licencias de software regularmente y
también intercambiar personal. La ubicación geográfica está cubierta, por supuesto, bajo el
encabezado de la prioridad, pero a través del principio de “economía externa”. También
conduce a la homofilia a través de la coubicación estructural. Las economías externas,
como su nombre lo indica, son “las economías que una empresa puede obtener mediante el
uso de instalaciones o servicios externos a sí misma” (Hoover y Vernon, 1962). Esto lleva a
la situación clásica de “aves con las mismas plumas se parecen” para aprovechar los
servicios fácilmente disponibles y, por lo tanto, reducir los costos de transacción. Al estar
en el mismo lugar al mismo tiempo, a la vez un factor en la homofilia también establece
relaciones de una manera más fácil. No es casual que las empresas que compiten entre sí
y, por lo tanto, tengan atributos muy similares, también estén cerca geográficamente
(Uzzi, 1996).

Los ejemplos corporativos sugieren que el poder en una relación no es irrelevante. Dado
que existe una diada formada en virtud de la homofilia, y que la conexión de la misma
pareja crea mayor homofilia, ¿cuál es el papel del poder o la mutualidad en la díada? A
menudo observamos que en cualquier relación en cualquier momento uno de los pares tiene
una ventaja sobre el otro. ¿Cuándo son iguales las relaciones? ¿Cuándo hay mutualidad?

9.1. Análisis de redes sociales

Comencemos nuestro análisis con un ejemplo motivador para ilustrar la aplicabilidad del
análisis de redes sociales. También consideramos brevemente algunos antecedentes
históricos antes de profundizar en las métricas específicas que se utilizan para analizar las
redes sociales.

EJEMPLO 9.1

JOSÉ ANTONIO RIVERA COLMENERO 165

 Un ejemplo ilustrativo de cómo se puede usar efectivamente el análisis de redes sociales
se describe en [Michael, 1997]. El ejemplo también se ha utilizado como un estudio de
caso en De Nooy et al. [2005] de donde tomamos los resultados del análisis. El caso es
sobre una pequeña empresa de procesamiento de madera en la que la gerencia propuso un
nuevo paquete de compensación. Esto llevó a una huelga, lo que permitió a la gerencia
creer que la comunicación entre los trabajadores estaba lejos de ser óptima. Decidieron
hacer un análisis de la red social. Con este fin, se pidió a los trabajadores que indicaran
con qué frecuencia y con quién estaban negociando la huelga. La frecuencia se midió en
una escala de 5 puntos, lo que llevó a un gráfico en el que dos personas estaban
vinculadas si hablaban entre sí con frecuencia. Este gráfico se muestra en la Figura 9.3.

FIGURA 9.3.
La relación entre trabajadores en huelga en una empresa procesadora de madera.

Hay una serie de propiedades que se pueden derivar de esta red y que puede explicarse
cuando examinamos más de cerca a los miembros individuales. Primero, aparentemente
hay tres grupos. El más pequeño está formado por cuatro trabajadores, a saber, Eduardo,
Domingo, Carlos y Alejandro. Todos estos trabajadores hablan el español como su primer
idioma. De estos, Alejandro era el más competente en inglés. Además, Bob habló algo de
español, lo que probablemente contribuya al vínculo con Alejandro. Otro grupo está
formado por Frank, Gill, Ike, Mike, Bob, Hal, John, Lanny y Karl (todos representados
como un nodo de color gris). Resultó que estos trabajadores formaban un grupo de personas

JOSÉ ANTONIO RIVERA COLMENERO 166

más jóvenes, que no hablaban tan a menudo con los compañeros de trabajo adultos. Este
último formó el tercer grupo, compuesto por Norm, Ozzie, Paul, Sam, Wendle, Xavier,
Vern, Ted, Ulrich, Russ y Quint.

Esta agrupación refleja lo que se conoce en la sociología como homofilia: la tendencia de

las personas a mantener relaciones más sólidas con aquellos que son similares a ellos
mismos.

HOMOFILIA. En un entorno social hace referencia a la inclinación de ciertos

individuos de relacionarse con otros que poseen mucha similitud con ellos. 

Los dos negociadores sindicales, Sam y Wendle, fueron los responsables iniciales de
proponer y abrir la discusión sobre el nuevo paquete. Sin embargo, al echar un vistazo a la
red, no es difícil ver que ninguno de ellos realmente constituye una fuente ideal para iniciar
la comunicación. Intuitivamente, Bob y Norm, y hasta cierto punto también Alejandro, son
las personas más importantes de esta red. Y, de hecho, cuando la gerencia se acercó a Bob y
Norm directamente para explicar de qué se trataba el nuevo paquete, en poco tiempo todos
los trabajadores entendieron el trato y estaban dispuestos a negociar. La huelga terminó.

EJEMPLO 9.2
Consideremos otro ejemplo, esta vez concentrándonos en la familia Medici. Esta familia
altamente influyente y poderosa se originó en Florencia, donde Giovani di Bicci creó el
Banco Medici, convirtiéndolo en uno de los hombres más ricos de Florencia. Su hijo,
Cosimo di Medici, continuó por el mismo camino que su padre y es considerado como el
fundador de la dinastía Medici, una dinastía que duró aproximadamente 200 años.
Cosimo di Medici entendió lo que se necesita para obtener poder y mantenerse en el
poder: asegurarse de que las personas adecuadas se casen entre sí. Padgett y Ansell
[1993] analizaron la dinastía Medici durante la primera mitad del siglo XV, incluida una
visión general de los matrimonios entre los Medici y otras familias, lo que llevó a la red
social como se muestra en la Figura 9.4.

JOSÉ ANTONIO RIVERA COLMENERO 167

FIGURA 9.4.
La relación entre familias florentinas influyentes a principios del siglo XV.

Siguiendo a Jackson [2008] proporcionamos un análisis simple de esta red. Padgett y

Ansell [1993] dan un análisis serio y profundo de las relaciones sociales reales. Para
nuestro análisis, es interesante observar que la familia Strozzi no solo tenía más dinero, sino
que también estaba mejor representada en la legislatura local. Sin embargo, los Medici
finalmente se hicieron más poderosos. Veamos cuál podría ser una posible razón, viendo la
centralidad de la intermediación. La centralidad de intermediación c B (u) de un nodo u se
define como:

|S( x , u , y)|
c B ( u ) =∑
x ≠ y |S(x , y)|

donde, S( x ,u , y ) es la colección de rutas más cortas ( x , y ) que contienen a u, y a S( x , y)es

el conjunto de rutas más cortas entre los nodos x e y . Si normalizamos c B ( u ) por los
posibles pares de familias que u pueden conectar, es decir, por (n−1)(n−2)/2, se puede
calcular que la centralidad de intermediación para los Medici es igual a 0.522, mientras que
este valor es solo 0.103 para los Strozzi. Fraseando esto de manera diferente, los Medici
estaban en más del 50% de todos los caminos más cortos en la red, mientras que los Strozzi
cubrían solo el 10%. De hecho, cuando se trata de ejercer el poder, los Medici
aparentemente estaban en una posición mucho mejor.

Antecedentes históricos
Aunque el análisis de redes sociales a veces parece ser una disciplina novedosa que
recientemente surgió como otra parte de la ciencia de las redes, de hecho, desde hace
mucho es un área de investigación bien establecida. Ya a principios del siglo anterior, los
psicólogos utilizaban diagramas para representar las relaciones entre entidades sociales.
JOSÉ ANTONIO RIVERA COLMENERO 168
Jacob Moreno, quien introdujo el sociograma en la década de 1930, hizo una importante
contribución. En el sociograma, un individuo está representado por un punto, y las
relaciones entre individuos por líneas, de hecho, una gráfica. La importancia de los
sociogramas de Moreno radica en el hecho de que sugirió que se podrían derivar
características específicas de los sociogramas, como identificar personas influyentes,
identificar flujos de información, etc. Y, de hecho, han demostrado ser una herramienta
poderosa para descubrir estructuras en grupos sociales. Regresaremos a un uso específico a
continuación.

Con los sociogramas de Moreno, la escena fue preparada para un trabajo posterior en lo que
se conoce como sociometría, que se trata de medir cuantitativamente las relaciones
sociales. Un concepto importante que despertó fue el de una tríada. Una tríada es un
subgrafo de un sociograma que consta de tres puntos que podrían estar conectados entre sí.
Obviamente, las tríadas están relacionadas con los triángulos. Formalmente, la distinción
entre una tríada y un triángulo es que en este último los tres vértices se unen entre sí. Para
una tríada, este no tiene por qué ser el caso. Las tríadas se volvieron importantes para
estudiar la presencia y evolución de los subgrupos sociales. Por ejemplo, Cartwright y
Harary [1956] desarrollaron una teoría sobre el equilibrio social en la que consideraron
subgrupos de al menos tres individuos, como se muestra en la Figura 9.5.

FIGURA 9.5.
Una tríada a analizar para el equilibrio social.
En este caso particular, se supone que las relaciones entre individuos eran simétricas: si a
Alice le gusta Bob, entonces a Bob también le gusta Alice. Si representamos “se gustan”
con un “+” y “no se gustan” con un “”, podemos hablar de tríadas equilibradas y
desequilibradas como se refleja en la Figura 9.5. La observación importante aquí es que un
sociograma se utiliza para analizar un grupo social en su conjunto al considerar
simultáneamente las perspectivas de todos sus miembros sobre sus relaciones. En otras
palabras, el enfoque está en descubrir estructuras dentro del grupo social. De esta manera,
uno podría hacer declaraciones sobre, por ejemplo, la estabilidad o el equilibrio de todo un
grupo, y hasta qué punto se podría esperar que las relaciones cambiarían (bajo el supuesto
de que los grupos buscan el equilibrio).

AB BC AC B/D Descripción

+ + + B A todos les gusta el uno al otro

El disgusto entre A y C acentúa la relación que B

+ +  D
tiene con cualquiera de ellos.

JOSÉ ANTONIO RIVERA COLMENERO 169

 El disgusto entre B y C acentúa la relación que A
+  + D
tiene con cualquiera de ellos.

+   B A y B se gustan, y a ambos les disgusta C

El disgusto entre A y B acentúa la relación que C

 + + D
tiene con cualquiera de ellos.

 +  B B y C se gustan, y a ambos les disgusta A

  + B A y C se gustan, y a ambos no les gusta B

   D A nadie le gusta el uno al otro

TABLA 9.2.
Las posibles relaciones balanceadas (B) o desbalanceadas (D) en una tríada basadas
en gustos o disgustos entre sí.

La idea de centrarse en el descubrimiento de estructuras globales a través del análisis de

interacciones a pequeña escala, como ocurrió en las tríadas, condujo a nuevas técnicas de
análisis. En particular, los investigadores se interesaron en poder identificar diferentes
subgrupos. En términos de redes, esto significaba que era necesario desarrollar técnicas que
permitieran la identificación de componentes, pero que a veces los componentes todavía
estuvieran conectados entre sí. Para ilustrar esto, considere el ejemplo de los trabajadores
de la empresa de procesamiento de madera nuevamente. Los sociólogos estaban interesados
en ver qué personas formaban realmente grupos dentro de esa comunidad y podían
identificar a tres de ellos, como se mencionó anteriormente. Estos grupos se pueden
visualizar más fácilmente al considerar la matriz de adyacencia de la red asociada, como se
muestra en la Figura 9.6 (a). Para mayor claridad, omitimos los nombres de los
trabajadores. Una celda (i, j) está coloreada de negro si el trabajador i y j están vinculados
entre sí. Al simplemente reordenar las filas y columnas, obtenemos una matriz equivalente,
que se muestra en la Figura 9.6 (b). Esta última matriz revela con más fuerza que en la
primera hay subgrupos entre los trabajadores.

JOSÉ ANTONIO RIVERA COLMENERO 170

 (a) (b)
FIGURA 9.6.
(a) La matriz de adyacencia de la red de la Figura 9.3, y (b) la misma matriz después de
reordenar filas y columnas. De [de Nooy et al., 2005].

No fue hasta la década de 1950 que los investigadores comenzaron a hablar de manera más
sistemática sobre las redes y comenzarían a utilizar conceptos teóricos de gráficos para
expresar aspectos estructurales de las redes. La relación entre los sociogramas y el enfoque
más riguroso que implica el uso de las matemáticas se introdujo gradualmente. Sin
embargo, tomaría por lo menos una década más hasta que los vínculos entre las redes
sociales y las matemáticas se fortalecieran sustancialmente. De particular influencia fue el
trabajo de Mark Granovetter sobre lo que él llamó lazos débiles: vínculos entre diferentes
grupos sociales que demostraron ser esenciales para la difusión de la información y, por lo
tanto, llegar a otros grupos distintos del propio [Granovetter, 1973]. La comprensión del
trabajo de Granovetter requería un enfoque matemático de las redes sociales.

El análisis de las redes sociales ha evolucionado constantemente desde entonces, y se han

desarrollado muchas técnicas de rigidez. Ahora hemos llegado a un nuevo punto. Como se
mencionó, los sociólogos desarrollaron varios modelos sobre cómo los grupos de personas
se organizan. El problema al que se enfrentaron los investigadores fue cómo validar esos
modelos: establecer experimentos sociológicos con muchos participantes no es tan trivial
como Milgram experimentó a fines de los años 60. Con las comunidades en línea, los
investigadores de repente tienen tremendos conjuntos de datos sociológicos en sus manos.
Podemos aplicar análisis similares a estos conjuntos no solo para validar los modelos de
cómo evolucionan las redes sociales o cómo están estructuradas, sino también para
descubrir nuevas propiedades que están inherentemente ligadas al tamaño de una red.

Sociogramas en práctica: una ayuda del profesor.

Consideremos un ejemplo de un sociograma. Un uso particular de los sociogramas se

encuentra en las aulas, lo que permite al maestro obtener una mejor comprensión de la
estructura social de la clase. En tales casos, se le puede pedir a cada alumno que enumere
JOSÉ ANTONIO RIVERA COLMENERO 171
las tres personas que más le agradan (lo que se conoce como una nominación positiva) o la
menor (es decir, las nominaciones negativas). Un ejemplo se muestra en la Figura 8.6.,
que se basa en el material de Sherman [2000]. Una entrada (i , j) marcada con “ +¿ ” indica
que a un alumno i le cae bien el alumno j , mientras que una “−¿“ indica que no le cae bien
el alumno j .

FIGURA 9.7.
Datos sobre los compañeros de clase que más me agradan o no me agradan.

Al considerar solo las nominaciones positivas, obtenemos la red social que se muestra en la
Figura 9.8 (a). En este caso, los alumnos están representados por vértices de color negro,
mientras que las alumnas se muestran como nodos de color blanco. Vemos
instantáneamente que los dos grupos están más o menos separados: los alumnos y las
alumnas tienden a formar su propio subgrupo, como se ilustra más adelante después de
reordenar la matriz de adyacencia, que se muestra en la Figura 9.8 (b).

JOSÉ ANTONIO RIVERA COLMENERO 172

 (a)

(b)
FIGURA 9.8.
(a) El sociograma para nominaciones positivas representado como un gráfico dirigido. Los
Alumnos están representados por nodos de color negro; las Alumnas por nodos de color
blanco. (b) Después de reordenar la matriz de adyacencia, los dos subgrupos se vuelven
más evidentes.

JOSÉ ANTONIO RIVERA COLMENERO 173

Hay otros temas que hacen de este un caso interesante. Por ejemplo, al considerar
simplemente la distribución de los grados, uno puede tener una impresión de la posición de
ciertos alumnos. En este caso, también deberíamos considerar las nominaciones negativas
como se indica en la Figura 9.7. Vemos que los alumnos #11 y #12 son muy populares
(tienen una suma máxima nominaciones positivas igual a 8), mientras que #10 y #21 son
muy impopulares, tienen una suma de nominaciones positivas igual a 0. Hay mucha
controversia con respecto al alumno #19 (y en menor medida al #20), que recibieron
relativamente igual número de nominaciones positivas y negativas, 7 y 6, respectivamente.
También hay alumnos abandonados, es decir, aquellos que no se mencionan en absoluto
(alumnos #8 y #18).

Concentrémonos un poco más en quién es importante y en quién no, considerando el

componente más fuertemente conectado de nuestra red del salón de clases. Este
componente consta de todos los alumnos excepto # 3, # 6, # 8, # 10, # 18, # 21, # 22 y # 24.
La excentricidad de un miembro se define la distancia máxima de ese miembro a cualquier
otro miembro. Para nuestro subgrupo, obtenemos:

Alumno 1 2 4 5 7 9 11 12
Excentricidad 5 6 6 4 7 7 7 5

Alumno 13 14 15 16 17 19 20 23
Excentricidad 6 3 6 5 6 5 4 6

Curiosamente, la alumna #14 es el más cercano a cualquier otro alumno, mientras que los
populares no se diferencian realmente de los demás. Al reconsiderar la Figura 8.7 (a),
podemos ver que la alumna #14 es uno de los pocos alumnos que nominaron a un alumno
(#7) y dos alumnas (#5) y (#20). Para ver en qué medida un alumno está cerca de todos los
demás miembros del grupo, calculamos los valores de proximidad:

Alumno 1 2 4 5 7 9 11 12
Proximidas 0.023 0.021 0.018 0.025 0.018 0.018 0.018 0.022

Alumno 13 14 15 16 17 19 20 23
Proximidad 0.018 0.030 0.021 0.021 0.021 0.025 0.025 0.021

Sin embargo, como hemos argumentado anteriormente, la cercanía puede no ser siempre un
buen indicador de importancia. Por ejemplo, si la alumna #14 fue dada de baja de la clase,
¿qué tan perjudicial sería para la transmisión de información? De hecho, resulta que debido
a que la alumna #14 realmente no está tan bien conectada, ella tampoco desempeña un
papel crucial en estos asuntos. Los sociólogos han introducido la centralidad de la
intermediación como un indicador de la importancia. Esta métrica tiene en cuenta si un
nodo se encuentra en el camino más corto entre otros dos nodos. Si calculamos la
centralidad de intermediación para cada uno de los miembros de nuestro grupo, obtenemos
los siguientes valores:

Alumno 1 2 4 5 7 9 11 12
Intermediació 0.140 0.153 0.050 0.105 0.083 0.007 0.155 0.220

JOSÉ ANTONIO RIVERA COLMENERO 174

 n

Alumno 13 14 15 16 17 19 20 23
Intermediació
0.016 0.054 0.083 0.140 0.017 0.466 0.469 0.029
n

Los resultados son interesantes: sin lugar a dudas, los alumnos #19 y #20 desempeñan
papeles cruciales cuando se trata de conectar los dos grupos de alumnos y alumnas y, por lo
tanto, de pasar información entre los dos subgrupos. De hecho, si elimináramos uno de los
subgrupos, se desharía en el sentido de que ya no tendríamos un componente fuertemente
conectado.

9.2. Intermediación entre las comunidades

La intermediación es la medida en que un nodo se encuentra en las rutas geodésicas o
directas que conectan cualquiera de los dos nodos en la red. Esto puede interpretarse como
la medida en que la información pasa a través de este nodo. Un nodo con una alta
interrelación posiblemente conecta comunidades (es decir, subgrafos en la red) entre sí.
Esto se representa en la Figura 9.9. En la figura, el nodo sombreado conecta las tres
comunidades entre sí y tiene la mayor interrelación. Si este nodo se relaciona con toda la
comunidad, conoce a cualquiera de las otras comunidades. Si eliminamos este nodo de la
red se perderá el contacto entre las comunidades, pues es un enlace entre ellas.

JOSÉ ANTONIO RIVERA COLMENERO 175

FIGURA 9.9.
Ilustración de la intermediación entre comunidades de nodos.

9.3. Algunos conceptos básicos

Ahora que hemos dado una visión general de las redes sociales y un ejemplo típico de cómo
se pueden aplicar, vamos a dar un paso más y consideremos algunos de los conceptos más
importantes en el análisis de redes sociales y cómo estos conceptos se relacionan con el
marco teórico ofrecido por las graficas. En nuestra discusión, seguimos en gran medida la
estructura presentada por Wasserman y Faust [1994].

Centralidad y prestigio

Como hemos mencionado, la identificación de entidades sociales importantes forma un

tema recurrente en el análisis de redes sociales. Hasta este punto, hemos introducido las
siguientes métricas para ayudar a encontrar esas entidades:

Centralidad del nodo: Una métrica que nos dice hasta qué punto un nodo está en el
centro de una red, considerando su distancia máxima a todos los otros nodos. Por lo

JOSÉ ANTONIO RIVERA COLMENERO 176

general, los nodos “en el borde” de la red generalmente se consideran menos influyentes
que los de su centro.

Cercanía: Esta métrica considera la centralidad medida por la distancia a cada otro nodo
en la red. Cuanto más alto sea el valor, más cercano estará un nodo a cada otro nodo.

Centralidad de intermediación: esta importante métrica define la centralidad de un

nodo uconsiderando la fracción de las rutas más cortas que cruzan u. Cuantas más rutas de
este tipo, más importante se debe considerar u.

Todas estas métricas deben considerarse con cuidado, como ilustramos en la sección
anterior con nuestro ejemplo del aula. Por ejemplo, vimos que una persona popular puede
no ser la más eficiente para difundir información.

Tenga en cuenta además que estas métricas se pueden definir para redes dirigidas y no
dirigidas, ya que todos se basan en una noción de distancia entre nodos. Sin embargo,
cuando se consideran redes dirigidas, es útil hacer una distinción entre la distancia a otros
nodos (como se usaría para medir la centralidad) y la distancia desde otros nodos. En
particular, si queremos indicar el prestigio de un nodo u, contar cuántos otros nodos se
refieren a u como una métrica de prestigio parece tener sentido. En particular, tenemos:

Definición 9.1. Sea D una gráfica dirigida. El grado de prestigio p grado (n) de un nodo
n ∈ N ( D) se define como su indegrado de grado δ ¿ ( n).

EJEMPLO 9.3.
En la Sección 9.1 describimos el uso de grafos o redes con signos para representar las
relaciones simétricas (a x le gusta y , y también a y le gusta x ). Cuando algunas
relaciones no son simétricas (a x le gusta y , pero a y no le gusta x ), usamos un dígrafo
con signos. Este es un dígrafo con + o  asociado con cada arco, que indica una relación
positiva (se gustan, se agradan, se caen bien, se ayudan, se llevan bien, etc.) o una
relación negativa (no se gustan,no se agradan, no se caen bien, no se ayudan, no se llevan
bien, etc.).

Por ejemplo, en el dígrafo con signos que se muestra más abajo, a Juan y Jaime se vevan
bien los dos, a María le cae bien Jimena, pero a Jimena no le cae bien María, a Juan no le
gusta Jimena, pero no tenemos información sobre los sentimientos de Jimena por Juan.

JOSÉ ANTONIO RIVERA COLMENERO 177

Tenga en cuenta que un arco negativo de x a y (a Jimena no le cae bien María) no es lo
mismo que un arco positivo de y a x (a María le cae bien Jimena).

BIBLIOGRAFÍA

 Baesens, Bart; Van Vlasselaer, Véronique; Verbeke, Wouter (2015). Social

Network Techniques. Editorial Wiley and Sons. United States of America.
 Barry, Render; Ralph M. Stair, Jr.; Michael E. Hanna; Trevor S. Hale (2015).
Quantitative Analysis for Management. Editorial Pearson. 12ava. Edición. United
States of America.
 Kadushinn, Charles (2012). Understanding Social Networks, Theories, Concepts,
and Findings. Oxford University Press. USA, New York.
 Reynoso, Carlos ( 2011). Redes sociales y complejidad. [Link]
Buenos Aires, Argentina.
 van Steen, Maarten (2010). Graph Theory and Complex Networks an Introduction.
Publicado por Maarten van Steen.
 Wai-Kai-Shen (2003). Net Theory and its Applications- Flows in Networks. Imperial
College Press. Singapore.

JOSÉ ANTONIO RIVERA COLMENERO 178