Unidad 6

Modelo de redes

Objetivos:

Al nalizar la unidad, el alumno:

  •  Resolverá problemas utilizando el algoritmo de la ruta más corta.
  •  Resolverá problemas de flujo máximo.
  •  Resolverá problemas de flujo restringido de costo mínimo.
  •  Resolverá problemas de aplicación al entorno de los negocios.
  •  Resolverá problemas utilizando el algoritmo PERT.
Matemáticas para negocios 215

Introducción

La  representación  gráca  de  las  vías  de  comunicación  de  cualquier  región 
geográca es un claro ejemplo de una red, lo cual le conere relevancia natural 
por tener la capacidad de proporcionarnos información acerca de los diferentes
caminos que podemos utilizar para trasladarnos de un origen hasta un destino
preestablecido pero, en general, es necesario obtener aún más información de un
diagrama de redes, como encontrar cuál de todas las posibles rutas es la que tiene
un recorrido total menor a cualquier otra, es decir, la ruta más corta de todas o,
por ejemplo, cuál es la ruta con mayor auencia o ujo máximo, así como el ujo
de costo mínimo. Se puede observar que el denominador común de los términos
recién presentados como: “más corta” y “mínimo o máximo”, tiene una relación
directa con la optimización. Es en este sentido que se presenta tanto la denición 
de los modelos de redes, su terminología y construcción, así como casos prácticos
para resolver con la metodología presentada a lo largo de este capítulo.

En las diferentes secciones del capítulo se estudiarán los problemas mencionados a

través de la solución de casos de aplicación, por lo que se sugiere que el lector resuelva de
nueva cuenta tales ejemplos, así como la sección de ejercicios y la autoevaluación.

6.1.  Denición del modelo

En general, una red es la representación gráca de un proceso, serie de actividades 
interconectadas o la distribución de puntos geográcos especícos, por ejemplo, 
un mapa carretero o la distribución de una red de computadoras representada en
un diagrama, aunque existen muchos más contextos donde se aplican las redes.

Por  mostrar  una  representación  de  la  realidad,  las  redes  se  clasican  como  un 
modelo. Es así como se dene el modelo de redes, el cual cuenta con terminología 
propia, necesaria para su desarrollo. A continuación se presenta la notación y
terminología empleada.
216 Unidad 6 ▪ Modelo de redes

Notación y terminología

Red. Conjunto de puntos llamados nodos (o vértices) y líneas que los unen
llamadas arcos (o ligaduras, aristas o ramas).

Los arcos se etiquetan con los nombres de los nodos en sus puntos terminales, por
ejemplo, AB es el arco entre los nodos A y B.

Arcos dirigidos. Un arco es dirigido cuando tiene ujo en una sola dirección y 
ésta se indica con una cabeza de echa al nal del arco o línea en la dirección del 
ujo.

Arcos no dirigidos. Un arco donde se permite el ujo en ambas direcciones.

Trayectoria. Sucesión de arcos distintos que conectan dos nodos.

Trayectoria dirigida. Una trayectoria dirigida del nodo i al nodo j, es una sucesión
de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el ujo del 
nodo i al nodo j, a través de esta trayectoria, es factible.

Trayectoria no dirigida. Una trayectoria no dirigida del nodo i al nodo j es una

sucesión de arcos cuya dirección (si la tienen) puede ser hacia o desde el nodo j.

Red dirigida. Es una red que tiene sólo arcos dirigidos.

Red no dirigida. Es una red donde todos sus arcos son no dirigidos.

Red conexa. Una red conexa es una red en la que cada par de nodos está conectado.
Se dice que dos nodos están conectados si la red contiene al menos una trayectoria
no dirigida entre ellos aparte.

Se debe resaltar que no es necesario que la trayectoria sea dirigida aun cuando la
red sea dirigida.

Capacidad de arco. Es la cantidad máxima de ujo (quizás innito) que puede 
circular en un arco dirigido.

Nodo fuente (o nodo de origen). Tiene la propiedad de que el ujo que sale del 

nodo excede al ujo que entra a él. 

Nodo demanda (o nodo destino). Es el caso contrario al nodo fuente, donde el

ujo que llega excede al que sale de él. 
Matemáticas para negocios 217

Nodo de trasbordo  (o  nodo  intermedio).  Satisface  la  conservación  del  ujo,  es 
decir, el ujo que entra es igual al que sale.

Esta terminología se utilizará en el desarrollo del algoritmo y ejemplos. Conforme se

requiera, se recuperará alguno de los conceptos, ya sea para aplicar algún paso de un
algoritmo o explicar alguna consideración particular de una operación o tipo de red.

Ejemplo 1 El siguiente diagrama representa una red:

Los nodos 0 y F representan el origen y destino de la red, mientras que los nodos
A, B, C, D y E, son nodos de trasbordo, el número en los arcos o líneas puede
indicar distancia en kilómetros, por ejemplo, entre nodos adyacentes.

Como se mencionó en un principio, los diagramas de redes, además de representar

vías de comunicación, también se utilizan para obtener información adicional,
por ejemplo, para obtener la ruta más corta entre el nodo origen y el nodo destino.
A continuación se presenta el algoritmo de La ruta más corta.

6.2. Problema de la ruta más corta

El problema de la ruta más corta tiene por objetivo determinar la ruta mínima
entre un origen y un destino determinados utilizando la información disponible
en  una  red  y  cumpliendo  con  las  especicaciones  de  distancia,  conexiones 
existentes, etcétera.

El algoritmo analiza la red a partir del origen, identicando en orden ascendente 
la ruta más corta hasta cada uno de los nodos desde el origen hasta alcanzar el
nodo destino.
218 Unidad 6 ▪ Modelo de redes

Esto es partir de una red establecida, conexa y no dirigida con nodos origen y
destino. A cada arco no dirigido se asocia una distancia no negativa. El objetivo
es determinar la ruta más corta, es decir, la trayectoria con la mínima distancia
total, desde el origen hasta el destino.

Algoritmo de la ruta más corta:

Objetivo de la n-ésima iteración. Encontrar el n-ésimo nodo más cercano al

origen (este paso se repetirá para n=1,2,… hasta que el n-ésimo nodo más cercano
sea el nodo destino).

Datos para la n-ésima iteración. Son los n-1 nodos más cercanos al origen (encontrados
en las iteraciones previas), incluida su ruta más corta y la distancia desde el origen
(estos nodos y el origen se llaman nodos resueltos, el resto son nodos no resueltos).

Candidatos para el n-ésimo nodo más cercano. Cada nodo resuelto que tiene
conexión directa por una ligadura con uno o más nodos no resueltos, proporciona
un candidato y éste es el nodo no resuelto que tiene la ligadura más corta (los
empates proporcionan candidatos adicionales).

Cálculo del n-ésimo nodo más cercano. Para cada nodo resuelto y sus candidatos,
se suma la distancia entre ellos y la distancia de la ruta más corta desde el
origen a este nodo resuelto. El candidato con la distancia total más pequeña
es el n-ésimo nodo más cercano (los empates proporcionan nodos resueltos
adicionales) y su ruta más corta es la que genera esta distancia.

El algoritmo es muy sencillo y su aplicación se facilita aún más si se utiliza una

tabla que registra el resultado de las iteraciones y permite la identicación de las 
conexiones que forman la ruta más corta de la red.

La tabla contiene la siguiente información:

Tabla 6.1. Tabla para aplicar el algoritmo de la ruta más corta.

Nodos resueltos Nodo no resuelto Distancia n-ésimo

Distancia Última
n conectados directamente más cercano total nodo más
mínima conexión
a nodos no resueltos conectado involucrada cercano
1
...
n
Matemáticas para negocios 219

La primera columna indica el número de la iteración.

La segunda columna: registra los nodos resueltos (nodos ya utilizados en la

trayectoria) para iniciar la iteración actual, después de no considerar los nodos
que no se utilizan.

La tercera columna: candidatos (nodos no resueltos con la ligadura más corta al

nodo resuelto) para el n-ésimo nodo más cercano.

La cuarta columna: distancia de la ruta más corta desde el origen a cada uno de
estos candidatos.

La quinta columna: candidato con la menor distancia al origen.

La sexta columna: distancia de la ruta más corta desde el origen al último nodo
resuelto.

La séptima columna: último tramo en esta ruta más corta.

En la última columna se puede determinar la ruta más corta desde el nodo origen
al destino.

El siguiente ejemplo muestra la aplicación de la tabla a la red del ejemplo anterior.

Ejemplo 2 Aplicar el algoritmo de la ruta más corta a la red del ejemplo 1.

Se comienza por generar una tabla con los siguientes encabezados:

220 Unidad 6 ▪ Modelo de redes

Nodos resueltos Nodo no resuelto Distancia n-ésimo

Distancia Última
n conectados directamente más cercano total nodo más
mínima conexión
a nodos no resueltos conectado involucrada cercano
1
...
n

La primera iteración se registra en la la correspondiente a  n = 1

La primera iteración se realiza comparando la distancia existente entre el nodo

0 y los nodos A y B respectivamente, seleccionando el nodo B como el “nodo no
resuelto más cercano conectado” con una “distancia total involucrada” de 4 km.
Ahora, el “n-ésimo nodo más cercano” aplica cuando se deba comparar más de
un nodo, en este caso el mismo nodo B es el más cercano con una “distancia
mínima” de 4 km, por lo que se establece la “última conexión” como 0B.

Nodos resueltos Nodo no resuelto Distancia n-ésimo

Distancia Última
n conectados directamente más cercano total nodo más
mínima conexión
a nodos no resueltos conectado involucrada cercano
1 0 B 4 B 4 0B

Ahora toca el turno de la segunda iteración:

En esta iteración, el nodo 0 y el nodo B son nodos resueltos, es decir, ya se pasó por
ellos, pero están conectados a nodos no resueltos y, por esta razón, se consideran
en la segunda iteración.

El nodo no resuelto más cercano a 0 y B respectivamente es A y C, el primero con

una distancia total de 5 unidades, mientras que la distancia para llegar a C es la
suma de las distancias de 0 a B y luego de B a C; siendo mínima la primera, se
selecciona como última conexión.

Nodos resueltos Nodo no resuelto Distancia n-ésimo

Distancia Última
n conectados directamente más cercano total nodo más
mínima conexión
a nodos no resueltos conectado involucrada cercano
1 0 B 4 B 4 0B
0 A 5 A 5
2 0A
B C 4+6=10 C 10
Matemáticas para negocios 221

La tabla completa, considerando la misma explicación que se presentó para la

primera y segunda iteración, está dada por:

Nodos resueltos Nodo no resuelto Distancia n-ésimo

Distancia Última
n conectados directamente más cercano total nodo más
mínima conexión
a nodos no resueltos conectado involucrada cercano
1 0 B 4 B 4 0B
0 A 5 A
2 5 0A
B C 4+6=10 C
3 A D 5+4=9 C 9 AB
E 9+2=11 E
4 B 11 BE
D 9+3=12 D
D F 12+7=19 F 19
5 ET
E F 11+5=16 F 16

De la última columna se extrae la información para resolver el problema:

La ruta más corta desde el nodo destino hacia el nodo origen se determina desde el
nal hacia el principio de la última columna, es decir, desde el destino T→ E→B→
A→0, con una distancia total de 16 kilómetros.

Si representamos la ruta más corta sobre el diagrama de la red, queda como:

En algunas ocasiones, este algoritmo de solución puede generar más de una ruta
más corta y será decisión del responsable del proyecto considerar, de las posibles
rutas más cortas, la que mejores benecios reporte para los involucrados.
222 Unidad 6 ▪ Modelo de redes

6.3. Flujo máximo

Cuando se pretende maximizar el ujo a través de una red, considerando como 
inicio de la red un nodo llamado fuente y como nodo nal un nodo llamado destino
y tomando en cuenta que el ujo en los arcos es sólo en la dirección que en el 
diagrama de la red se indica, se tiene un problema de ujo máximo, en el cual el
objetivo es maximizar la cantidad total de ujo de la fuente al destino.

Este tipo de problema tiene una amplia gama de aplicaciones dentro de las cuales
se pueden mencionar:

Maximizar el ujo de cualquier uido a través de una tubería.
•
• Maximizar el ujo de vehículos por un sistema carretero.
• Maximizar el ujo de insumos o productos desde los proveedores hacia los 
clientes de cualquier tipo de empresa.

Para resolver este problema, se requiere una red conexa dirigida, identicar los 
nodos fuente y destino, así como conocer, por lo general, los límites máximos
permisibles de ujo en cada uno de los arcos dirigidos de la red. Con el diagrama 
de la red y los datos mencionados se utiliza un algoritmo para obtener la
solución.

A manera de introducción al algoritmo de solución, se presentan algunos términos

necesarios en la aplicación del mismo.

Red residual. Una vez asignados ujos a los arcos de la red original, la red residual

es aquella que muestra las capacidades restantes (capacidades residuales) para
asignar ujos adicionales. Para indicar la capacidad de ujo se coloca un número 
en la base del arco.
Matemáticas para negocios 223

Ejemplo 3 Suponer que entre un nodo adyacente y un nodo fuente se tiene una capacidad
máxima de ujo de 9 unidades de algún producto, lo cual está representado por 
la siguiente gura:

Observa que la capacidad residual de la derecha vale cero, pues no se ha realizado

asignación de ujo. Entonces si se asigna, por ejemplo, un ujo de 6 unidades al 
arco 0A, el diagrama de la red cambia a:

Este cambio en el diagrama indica que el nodo “0” tiene una capacidad residual
de tres unidades y que la capacidad residual del nodo “A” es de seis unidades.

Trayectoria aumentada. Es la trayectoria dirigida desde el nodo fuente hacia el

destino en la red residual, donde todos los arcos comprendidos en esta trayectoria
tienen capacidad residual estrictamente positiva.

Algoritmo de la trayectoria de aumento:

  1.  Se  identica  una  trayectoria  de  aumento  encontrando  alguna  trayectoria 
dirigida del origen al destino en la red residual, tal que cada arco sobre esta
trayectoria tiene capacidad residual estrictamente positiva (si no existe una,
los ujos netos asignados constituyen un patrón del ujo óptimo). 

  2.  Se  identica  la  capacidad  residual  c*  de  esta  trayectoria  de  aumento 
encontrando el mínimo de las capacidades residuales de los arcos sobre esta
trayectoria. Se aumenta en c* el ujo de esta trayectoria. 

  3.  Se disminuye en c* la capacidad residual de cada arco en esta trayectoria de 
aumento. Se aumenta en c* la capacidad residual de cada arco en la dirección 
opuesta en esta trayectoria. Se regresa al paso 1.

A continuación se aplica este algoritmo a la siguiente red, que es la misma del

ejemplo 1, pero sobre la red se escribieron los límites máximos permisibles, como
las capacidades residuales de los arcos de la red.
224 Unidad 6 ▪ Modelo de redes

Ejemplo 4 Considera  los  ujos  de  la  siguiente  red  y  determina  la  trayectoria  de  aumento 
para el problema de ujo máximo.

Iteración 1. Primero se determina una trayectoria de aumento desde el nodo

fuente hacia el destino de la red residual, para este caso la trayectoria de aumento

min (9,12,7,9 ) = 7 , que corresponde a las capacidades residuales de cada arco.

está dada por 0→B→C→D→F, que tiene una capacidad residual igual al

Asignamos el ujo de 7 a esta trayectoria para obtener:

Iteración 2. Otra trayectoria de aumento desde el nodo fuente hacia el destino de

B→C→E→F, la cual tiene una capacidad residual igual al min (2,5,6,6 ) = 2 , que
la red residual para esta segunda iteración es la trayectoria de aumento por 0→

corresponde a las capacidades residuales de cada arco. Asignamos el ujo de 2 a 
esta trayectoria para obtener:
Matemáticas para negocios 225

Iteración 3. Una trayectoria más será 0→A→C→E→F mín (7, 7, 4, 4) = 4.

Asignamos el flujo de 4 a esta trayectoria para obtener:

Como ya no existen trayectorias de aumento, el patrón de ujo actual es óptimo. 
Entonces la solución óptima de este problema de ujo máximo está dada por la 
siguiente red:

Esto quiere decir que el ujo máximo para esta red es de 13 unidades.

6.4. Flujo restringido de costo mínimo

En ocasiones, lo que se busca determinar acerca de una red es la manera en la

cual distribuir algún tipo de material por los conductos de la misma (arcos) al
menor costo posible, calculado éste con el costo unitario de transporte de cada
conducto y respetando los límites máximos permisibles de ujo en toda la red. 
Para el transporte del material por los conductos de la red, desde los puntos de
producción hasta los de consumo, se denotan nodos fuentes, nodos de trasbordo
–donde concurren varias rutas– y nodos destino.

Para plantear el modelo de ujo de costo mínimo, se considera una red conexa 
dirigida, en donde al menos se incluyen un nodo de producción ( fuente) y uno de
consumo (destino). La producción total de la red debe ser igual a la demanda total de
ésta; esto es un problema balanceado, en caso contrario, se utilizan nodos cticios 
para lograr el balance. En adelante sólo se considerarán problemas balanceados.
226 Unidad 6 ▪ Modelo de redes

El objetivo del modelo es minimizar el costo de transporte, satisfaciendo tanto las

demandas de los consumidores como las restricciones de ujo en los conductos 
de la red.

La notación de las variables y los datos involucrados en el desarrollo del modelo

son:

c ij :  costo por unidad de ujo a través del arco que va del nodo i al nodo j.
uij :  capacidad de ujo del arco que va del nodo i al nodo j.
bi :  ujo neto generado del nodo i.

Donde bi puede ser positiva si el nodo i es un nodo fuente, negativa si el nodo i es

un nodo demanda o cero si el nodo i es un nodo trasbordo.

Las variables de decisión son el ujo en los conductos:

x ij :  ujo en el arco que va del nodo i al nodo j.

Como el objetivo es minimizar el costo de transporte a través de la red y

considerando que las sumas de los ujos se realiza sobre los nodos, la función de 
costos y las restricciones están determinadas por las expresiones:

Z min = ∑∑ c ij x ij
n n

i =1 j =1

Sujeto a:

∑x −∑x = bi , para cada nodo i.

n n

j =1 j =1
ij ji

0 ≤ x ij ≤ uij ; para cada arco del nodo i al nodo j.

La primera suma de la primera restricción indica el ujo total que sale del i-ésimo

nodo, mientras que la segunda suma indica el ujo total que entra al i-ésimo nodo,
por lo que la diferencia de las sumas debe ser igual a la producción o demanda del
nodo e igual a cero para los nodos de trasbordo.
Matemáticas para negocios 227

Ejemplo 5 Considerar los ujos máximos permisibles y los costos unitarios de los arcos de 
la siguiente red y determinar el costo mínimo de transporte. Tomando en cuenta
que se tienen dos puntos de producción de 500 y 350 metros cúbicos de un corte
ligero de crudo y que otros dos puntos consumen 450 y 400 metros cúbicos
del  mismo  corte  ligero.  Los  costos  unitarios  de  transporte  y  ujos  máximos 
permisibles, así como la producción y consumo de las fuentes y destinos, se
muestran sobre la red:

A partir de la información de la red se plantea el modelo de ujo restringido de 
costo mínimo:

Z min = ∑∑ c ij x ij
n n

i =1 j =1

Sujeto a:

∑x −∑x = bi , para cada nodo i.

n n

j =1 j =1
ij ji

0 ≤ x ij ≤ uij ; para cada arco del nodo i al nodo j.

De forma desarrollada se tiene:

Z min = c13 x13 + c14 x14 + c 24 x 24 + c 25 x 25 + c 34 x 34 + c 36 x 36 + c 46 x 46 + c 47 x 47 + c 54 x 54 + c 57 x 57

228 Unidad 6 ▪ Modelo de redes

Sujeto a:
x13 + x14 = b1
x 24 + x 25 = b2
x 34 + x 36 − x13 = 0
x 46 + x 47 − x14 − x 24 − x 34 − x 54 = 0
x 54 + x 57 − x 25 = 0
− x 36 − x 46 = b6
− x 47 − x 57 = b7

0 ≤ x13 ≤ u13
0 ≤ x14 ≤ u14
0 ≤ x 24 ≤ u24
0 ≤ x 25 ≤ u25
0 ≤ x 34 ≤ u34
0 ≤ x 36 ≤ u36
0 ≤ x 46 ≤ u46
0 ≤ x 47 ≤ u47
0 ≤ x 54 ≤ u54
0 ≤ x 57 ≤ u57

Si se sustituyen los valores conocidos tanto en la función objetivo como en las

restricciones, entonces se tiene:

Z min = 10 x13 + 15 x14 + 12 x 24 + 14 x 25 + 10 x 34 + 12 x 36 + 18 x 46 + 15x 47 + 18 x 54 + 15x 57

Sujeto a:
x13 + x14 = 500
x 24 + x 25 = 350
x 34 + x 36 − x13 = 0
x 46 + x 47 − x14 − x 34 − x 54 = 0
x 54 + x 57 − x 25 = 0
− x 36 − x 46 = −400
− x 47 − x 57 = −450

0 ≤ x13 ≤ 400
0 ≤ x14 ≤ 200
0 ≤ x 24 ≤ 300
0 ≤ x 25 ≤ 200
0 ≤ x 34 ≤ 400
0 ≤ x 36 ≤ 300
Matemáticas para negocios 229

0 ≤ x 46 ≤ 200
0 ≤ x 47 ≤ 350
0 ≤ x 54 ≤ 100
0 ≤ x 57 ≤ 300

Resolviendo el modelo con apoyo de un paquete computacional, hoja de cálculo

de Excel, se llega a la siguiente solución:

x13 = 300
x14 = 200
x 24 = 250
x 25 = 100
x 34 = 0
x 36 = 300
x 46 = 100
x 47 = 350
x 54 = 0
x 57 = 100

Con un costo total mínimo de Z min = $22,550.00

De esta solución cabe señalar que los conductos identicados por los arcos (3,4) y 
(5,4) no se utilizan en la misma. Entonces, otro resultado importante que puede
obtenerse de este algoritmo es identicar las áreas de oportunidad de las redes 
con las que se trabaja, sin embargo, esto sólo es una propuesta ya que, en realidad,
el responsable del proyecto es quien deberá identicar la información relevante 
para el buen logro de las metas y objetivos planteados.

6.5. Aplicaciones al entorno de los negocios

Aplicar los algoritmos de solución a problemas que involucren maximizar un ujo 
o minimizar el costo total de una serie de operaciones, siempre tendrá remarcada
importancia en cualquier tipo de negocio ya que, en la actualidad, debido a la
globalización y la tendencia de grandes corporaciones a expandir sus operaciones
más allá de sus países de origen, se hace presente la necesidad de herramientas
que apoyen, con resultados cuantitativos, la toma de decisiones de casi cualquier
índole referida a la empresa.
230 Unidad 6 ▪ Modelo de redes

Cabe mencionar que el hecho de contar con estas herramientas, permitirá

distinguir la calidad de las decisiones soportadas en éstas, de las decisiones
poco afortunadas tomadas porque “parecía lo correcto”. Aun así, también debe
considerarse que sólo la constante y repetida práctica en la solución de problemas,
fortalecerá las habilidades y conocimientos necesarios para aplicarlos en tareas
cada vez más complejas.

Con  el  fin  de  ejemplicar  una  de  las  posibles  aplicaciones  de  las  redes  a  los 
negocios se presenta un caso práctico para resolver e interpretar.

Ejemplo 6 El diagrama que a continuación se presenta corresponde al ujo de recursos que van 
desde dos Direcciones generales (fuentes) con disponibilidad de 7.5 millones y 4.5
millones de pesos respectivamente, hacia dos administradores de campañas publicitarias
(destinos) con requisitos de 5 y 7 millones cada una. Para este n, las dos direcciones 
canalizan los recursos a través de tres departamentos que tienen restricciones de ujo 
de capital. Estos requerimientos y los costos unitarios de las operaciones se indican en
el diagrama. Los valores negativos de las variables b6 y b7 indican requerimientos.

Cada una de las Direcciones generales (nodos 1 y 2 en el diagrama) destina

recursos a través de dos departamentos (nodos 3 y 5 para la fuente 1 y nodos 4 y
5 para la fuente 2). Los departamentos (nodos 3, 4 y 5) dirigen recursos hacia los
administradores de las campañas publicitarias (nodos 6 y 7). Los departamentos
representados por los nodos 3 y 5 envían recursos hacia el administrador ubicado
en el nodo 6, y los departamentos designados como nodos 4 y 5 canalizan sus
recursos hacia el administrador del nodo 7. Observa que el departamento del
nodo 5 también puede recibir transferencias desde los nodos 3 y 4.
Matemáticas para negocios 231

El objetivo del problema es determinar el ujo de recursos a través de la red al 
menor costo posible.

A partir de la información de la red se plantea al modelo de ujo restringido de 
costo mínimo, con las siguientes variables:

c ij : costo por unidad de ujo a través del arco que va del nodo i
: al nodo j.
uij : capacidad de ujo del arco que va del nodo i
: al nodo j.
bi : ujo neto generado del nodo i.
:

La función de costos y las restricciones están determinadas por las expresiones:

Z min = ∑∑ c ij x ij
n n

i =1 j =1

Sujeto a:

∑x −∑x = bi , para cada nodo i.

n n

j =1 j =1
ij ji

0 ≤ x ij ≤ uij ; para cada arco del nodo i al nodo j.

De forma desarrollada se tiene:

Z min = c13 x13 + c15 x15 + c 25 x 25 + c 24 x 24 + c 35 x 35 + c 36 x 36 + c 56 x 56 + c 57 x 57 + c 45 x 45 + c 47 x 47

Sujeto a:
x13 + x15 = b1
x 24 + x 25 = b2
x 35 + x 36 − x13 = 0
x 56 + x 57 − x15 − x 25 − x 35 − x 45 = 0
x 45 + x 47 − x 25 = 0
− x 36 − x 56 = b6
− x 45 − x 45 = b7

0 ≤ x13 ≤ u13
0 ≤ x15 ≤ u15
0 ≤ x 24 ≤ u24
0 ≤ x 25 ≤ u25
0 ≤ x 35 ≤ u35
0 ≤ x 36 ≤ u36
0 ≤ x 45 ≤ u45
232 Unidad 6 ▪ Modelo de redes

0 ≤ x 47 ≤ u47
0 ≤ x 56 ≤ u56
0 ≤ x 57 ≤ u57

Si se sustituyen los valores conocidos tanto en la función objetivo como en las

restricciones, se tiene:

Z min = 1000 x13 + 1500 x15 + 1200 x 25 + 1150 x 24 + 1000 x 35 + 1200 x 36 + 1300 x 56 +
1500 x 57 + 1000 x 45 + 1500 x 47

Sujeto a:
x13 + x15 = 7.5
x 24 + x 25 = 4.5
x 35 + x 36 − x13 = 0
x 56 + x 57 − x15 − x 25 − x 35 − x 45 = 0
x 45 + x 47 − x 25 = 0
− x 36 − x 56 = −5
− x 45 − x 45 = −7

0 ≤ x13 ≤ 8
0 ≤ x15 ≤ 6
0 ≤ x 24 ≤ 1.5
0 ≤ x 25 ≤ 3
0 ≤ x 35 ≤ 3
0 ≤ x 36 ≤ 6
0 ≤ x 45 ≤ 2
0 ≤ x 47 ≤ 1
0 ≤ x 56 ≤ 10
0 ≤ x 57 ≤ 1

Después se determina el valor de las variables de decisión del modelo matemático

con apoyo de un procesador de cálculo, hoja de Excel, para resolver el sistema de
ecuaciones del modelo.

Para este caso se obtuvieron los siguientes valores de las variables de decisión:

x13 = 5
x15 = 2.5
x 24 = 1.5
x 25 = 3
Matemáticas para negocios 233

=0
=5
x 35

= 0.5
x 36

=1
x 45

=0
x 47

=1
x 56
x 57

El valor de los ujos está dado en millones de pesos.

Con un costo mínimo de Z min = $31,075.00 .

Es importante notar que algunos arcos de la red no se utilizaron en la solución

del problema, lo cual podría indicar áreas de oportunidad en la estructura de la
empresa.

6.6. Algoritmo PERT

En 1958 aparece el sistema PERT (evaluación de programa y técnica de revisión), el

cual fue desarrollado por Booz, Allen y Hamilton, científicos de la oficina naval
de proyectos espaciales y la división de sistemas de armamentos de la corporación
Lockheed Aircraft. La técnica demostró tanta utilidad que ha ganado amplia
aceptación tanto en el gobierno como en el sector privado. El método PERT fue
probado en la construcción del submarino Polaris y se dice que redujo en dos años
la conclusión del proyecto.

Terminología

Actividad. En términos generales, se considera actividad a la serie de

operaciones realizadas por una persona o grupo de personas en forma continua,
sin interrupciones, con tiempos medibles de iniciación y terminación. Las
actividades pueden ser físicas o mentales, como construcciones, trámites, estudios,
inspecciones, dibujos, etcétera.

Relación entre actividades. Es la forma lógica como se conectan las diferentes

actividades del proyecto. Esta relación se puede obtener por antecedentes o por
secuencia. Por antecedentes se les preguntará a los responsables de los procesos
cuáles actividades deben quedar terminadas para ejecutar cada una de las que
aparecen en la lista. Debe tenerse especial cuidado de que todas y cada una de