UNJBG / FACI - Escuela de Computación Matemática

Programación Matemática I 

CAPITULO V

REDES DE OPTIMIZACION

INTRODUCCION

Aplicaciones de la teoría y análisis de redes se encuentran en la teoría de la información, en cibernética,

en el estudio de los sistemas de transporte, en la planificación, entre otras.

La modelación o representación gráfica en redes proporciona una gran ayuda para visualizar las
relaciones entre los componentes de sistema complicados y que son estudiados en Investigación de
Operaciones. Los problemas más típicos que se resuelven incluyen: encontrar la ruta más corta de una
red, determinar el flujo máximo a través de una red, Problema de flujo a costo mínimo y problema de
flujo máximo a costo mínimo.
Los modelos de redes son casos particulares de la programación lineal que disponen de métodos de
solución propios que resultan más eficientes que el método simplex.
La teoría de redes también se conoce con el nombre de teoría de grafos.

5.1 Definiciones y Terminología de Redes.

Una red es un conjunto de nodos (vértices o puntos) conectados por un conjunto de arcos (líneas,
ramas, bordes). Existen arcos dirigidos de un nodo a otro y existen arcos que no tienen dirección.
A las redes cuyos arcos no tienen dirección se les llaman adireccionales .
Se denotará al nodo i por Ni y al arco dirigido del nodo i y al nodo j por Aij. Las redes de
optimización que se utilizan en este tendrán un número finito de nodos y arcos. Cuando se trate de
un arco no dirigido de Ni a Nj se utilizará indistintamente la nomenclatura Aij o Aji.
En la siguiente figura hay una red con cuatro nodos y seis arcos dirigidos.

N
2

A12 A24

N N
1
A23 A32 4

A13 A34

N
3

Una cadena de Ni a Nk es una serie de nodos y arcos que unen los nodos Ni y Nk. Por ejemplo, en
la figura, la cadena N1 , A12, N2, A24, N4 une a los nodos N2 y N4. un ciclo es una cadena que
empieza y termina en el mismo nodo. Por ejemplo en la figura, la cadena N 2 , A23, N3, A32, N2
forma un ciclo. Cadena simples son aquellas cadenas que no contiene ciclos.
Asociado a cada arco Aij se define lo siguiente:

Xij0, el flujo que va del nodo Ni al nodo Nj

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 215
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

uij0, capacidad máxima del flujo de arco Aij. Por lo general un número entero.
lij0, cantidad mínima de flujo que debe fluir del nodo Ni al nodo Nj.
cij0, costo por unidad de flujo que va del nodo Ni al nodo Nj.

Cuando cij0, se le toma como un egreso y cuando cij0, se le toma como un ingreso.
Se designará el nodo fuente por Ns y el nodo destino por Nt .
El flujo a través de una red debe satisfacer las siguiente restricciones:
a. El flujo entra a la red únicamente por el nodo fuente. Matemáticamente se representa por:

Donde v0 es el flujo total que entra a la red y s es el nodo fuente. Por convención, el
flujo que sale de un nodo (eflujo) es negativo y el flujo que entra en un nodo (influjo) es
positivo.
b. Hay conservación de flujo en un nodo intermedio, es decir, el total de flujo que entra en
cierto nodo es igual al total de flujo que sale del mismo. Matemáticamente se tiene:

c. El flujo sale de la red únicamente por el nodo destino.

El flujo total que sale de la red por el nodo destino es v0.

d. El flujo en un arco debe conformar los requerimientos mínimos y las capacidades máximas
del arc, es decir:

Forma matricial:

Una red es un grafo con algún tipo de flujo en los arcos o ramas. Se acostumbra a nombrar cada
nodo por un número o una letra mayúscula.
1 e
b
4
c

a f g
2
d Origen Final
3 5
Partida Llegada
1 -1

Figura 1.1

 Arcos adyacentes: (3,2) y (2,4)

 Nodos adyacentes: (2 y 4)
 Cadena que conecta: (3,2); (2,4); (4,1) los nodos 2 y 4
 Bucle: en el nodo 5 , Arco (5,5)
 Ciclo: (3,2), (2,4), (4,1), (1,3)

La representación gráfica de una red a través de nodos y arcos tienen correspondencia con una
representación matemática a través de matrices.

Una matriz de incidencia A está compuesta por los elementos aij de la siguiente manera.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 216
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

i=arcos
j=nodos

aij=+1 indica que el nodo j es el origen del arco i

aij=-1 indica que le nodo j es el extremo final del arco i
aij=2 si el nodo j es el origen y final del arco i
aij=0 si el arco i no incide en el nodo j

En el caso de la representación entregada en la figura 1.1 se construye la siguiente matriz de

incidencia A.

MATRIZ DE INCIDENCIA

1 e
b
4
a
c
f g
2
d
3 5

Si tenemos un grafo de n nodos y m arcos, existen n*m variables en la matriz de incidencia A.

Una matriz de adyacencia B esta compuesta por los elementos bij de la siguiente manera.
i= nodo origen
j= nodo final
bi j= 1 si existe el arco que va desde el nodo i al nodo j.
bij = 0 en caso contrario

La matriz de adyacencia B de la representación dada en la figura 1.1 es:

MATRIZ DE ADYACENCIA

existe el arco que ve

n n o d o f i n a l del nodo 1 al nodo 3
o
d 1 2 3 4 5
o
o 1 0 0 1 1 0 e
2 0 0 0 1 0 1
B =r
i 3 0 1 0 0 0 b 4
g 4 1 0 0 0 0 g
e 5 1 0 0 0 1 a
n 5x5 c
2 d 5
3

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 217
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

En un grafo de n nodos la matriz de adyacencia tiene n*n variables. Como normalmente el

número de arcos es mayor que el de nodos, la matriz de incidencia requiere una capacidad de
memoria mayor que la matriz de adyacencia, si desea representar el gráfico en un computador. En
todo caso la matriz de incidencia representa mejor al grafo.

Ejemplos de representaciones de situaciones reales usando grafos se indican a continuación,

describiendo los nodos los arcos y los flujos.

Nodos Arcos Flujo

Intersecciones Caminos Vehículos
Aeropuertos Rutas aéreas Aviones
Puntos de conmutación Cables, canales Mensajes
Estaciones de bombeo Tuberías Fluidos
Estaciones de trabajo Rutas de manejo de materiales Trabajos

5.1.1 Minimización de Redes

La minimización de redes tiene que ver con la determinación de los ramales que pueden unir todos
los nodos de una red, tal que minimice la suma de longitud de los ramales escogidos. Esta claro
que no resulta óptimo incluir ciclos en la solución del problema. La siguiente figura ilustra este
punto.
18
1 2

6 4

Las longitudes de las ramas se conectan los nodos 1,2 y 3 se indican en las ramas respectivas. Esta
claro también que la red mínima ocurre cuando el nodo 3 se conecta a 1 y 2, lo que da una longitud
mínima total de las ramas igual a 4+6=10. Si se conectan los nodos 1 y 2, se producirá un ciclo y
la red resultante no se minimiza.

La ausencia de ciclos en una red mínima nos ha llevada a crear el nombre sugestivo ARBOL DE
EXTENSION MINIMA (AEM). En cualquier red, el AEM se determina en forma iterativa de la
manera siguiente. Comience con cualquier nodo y únase éste a su nodo más próximo de la red. Los
dos nodos resultantes forman ahora un conjunto conectado y los nodos restantes constituyen el
conjunto no conectado. Después, elíjase un nodo del conjunto no conectado que está más
próximo(distancia mas corta) a cualquier nodo de los conjuntos conectados y súmelo al conjunto
conectado. Si redefinimos los conjuntos conectados y no conectados de acuerdo con esto, el
proceso se repetirá hasta que el conjunto conectado incluya todos los nodos de la red. Cualquier
empate se puede romper de forma arbitraria. Sin embargo, los empates indican la existencia de
otros AEM.

Ejemplos:
La Empresa Panamericana TV. esta planeando una red para dar servicio de TV por cable a cinco
nuevas áreas de desarrollo habitacional. La red del sistema de cable se resume en la siguiente
figura:

3 millas
2
5
6
1 9
4

1 3
Mgr. Manuel Alvarado5 Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 218
10

5 8
6
7

4 3
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Los números asociados con cada rama representan la longitud(en millas) que se necesita para
conectar dos sitios cualesquiera. El nodo 1 representa la estación de TV por cable y los nodos
restantes(2 y 6) representan las 5 áreas de desarrollo. Una rama faltante entre dos nodos implica
que es prohibitivamente costoso o físicamente imposible conectar las áreas de desarrollo
asociadas. Se requiere determinar los enlaces que originarán el uso mínimo de cable a la vez que
se garantiza que todas las áreas se conectan directamente o indirectamente a la estación de TV por
cable.

La solución gráfica se resume en la siguiente. Figura. Iteración 1

conjunto conectado C
3
2 conjunto no conectado
1 6
5
9
1
5

3
7 4
6
4

Iteración 1

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

Iteración 2

C 3
2
1 6
5
1
5
3 Roalcaba – Lic. Wilder Miñano León
Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera 219
4 5 C 6
8
4
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Iteración 3

2
C 1 6 3
5

1
5 C
3
10

4
5 6
3
4

Iteración 4

3
2
1
5

1
5 C ={1,2,3,4,5,6}
3
C 
4
5
enlaces 6
3
alternos 4

Iteración 5

A través de las iteraciones. El procedimiento puede iniciarse desde cualquier nodo, terminando
siempre con la misma solución optima.

Por lo tanto, el nodo 1 representa el conjunto de nodos conectados. El conjunto de nodos no

conectados lo representan los nodos 2,3,4,5 y 6. En forma simbólica, escribimos esto como.

El nodo 1 debe conectarse al nodo 2, que es el nodo más próximo en

Por tanto, la iteración 1 muestra que

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 220
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

C  {1,2} C  {3,4,5,6}...............iteracion2

Los nodos 1 y 2 de C ahora están unidos permanentemente. En la iteración 2 seleccionamos un

nodo En C = {3,4,5,6} que esta más próximo a un nodo en C = {1,2}. Como la distancia más
corta ocurre entre 2 y 5 (iteración 1) tenemos:

C  {1,2,5} C  {3,4,6}...............iteracion3
La iteración 2 da las distancias de los nodos C ={1,2,5} a todos los nodos de C = {3,4,6}. Por tanto
los nodos 2 y 4 están conectados, lo que produce

La iteracion 3 muestra que los nodos 4 y 6 deben estar conectados. Por lo tanto, obtenemos

C  {1,2,4,5,6} C  {3}...............iteracion5
En la iteracion 5 tenemos un paquete que podemos romper arbitrariamente. Esto quiere decir que
podemos conectar 1y 3 ó 4 y 3. ambas soluciones nos conducen a

Como todos los nodos están conectados, el procedimiento está completo, la longitud mínima(en
millas) de cable que se utiliza para conectar las áreas de desarrollo habitacional a la estación de
TV es de igual a 1+3+4+3+5=16.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 221
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

5.2 ALGORITMOS DE OPTIMIZACION EN REDES

5.2.1 PROBLEMA DE LA RUTA MAS CORTA

En el sentido evidente, el problema de la ruta más corta tiene que ver con la determinación de los
caminos conectados de una red de transporte que constituyen en conjunto la distancias más corta
entre una fuente y un destino.
En esta sección presentamos otros tipos de aplicaciones que se pueden representar por medio de
modelos y resolver como un problema de la ruta mas corta. Las aplicaciones van seguidas de los
siguientes algoritmos de solución.

a) Algoritmo de Ford
Para este procedimiento se utiliza la siguiente representación:
Los nodos están representados por un circulo en donde se indica el valor n el identificador A del
nodo.
n
----
A

Los arcos aij están orientados y valorizados con la distancia entre el nodo i y el nodo j.
Mediante un procedimiento se asigna un valor n a cada nodo que es igual a la longitud de la ruta
más corta que va desde el nodo origen al nodo j. Para ello el procedimiento consiste en:

Algoritmo de Ford:
Paso1: Asigna un valor 0 al nodo origen.

Paso2: Para valorizar cada nodo i es necesario conocer el valor de todos los nodos
predecesores a i. El valor asignado será igual al menor valor que resulta al sumar los
valores de los nodos predecesores con el valor del arco que une con el nodo i.

Paso 3: El punto anterior se repite hasta que se valoriza el nodo final. Si no puede valorizarse
el nodo final, significa que no hay un camino que los una. El valor asignado al nodo
final es la longitud de la ruta mas corta.

Paso 4: La ruta mas corta se encuentra partiendo con el valor del nodo final al que se le resta
el valor de cada arco que llega al nodo. El predecesor cuyo valor coincida con dicha
resta forma parte de la ruta mas corta. Este paso se repite con el nodo encontrado
hasta que se llegue al nodo de partida.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 222
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Diagrama de Flujo del Metodo de Ford

INICIO

Ingresar :N: # de nodos

Numero de arcos

Asignar el valor de 0 al nodo origen

I=2 - N

Valor del nodo i = Min{valor del nodo j + arco(j,i)}

j e Predecesores

i=N

RESTA = valor de nodo i – arco ( j , i )

SI
RESTA= valor nodo
j
Almacenar el nodo j

i=j

i=1
SI

Ruta Mas corta {si al restar el valor de los nods i y j

nos da el valor del arco(i, j) entonces es ruta mas
corta }

FIN

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 223
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

EJEMPLO. Encontrar la ruta mas corta entre 1 y T del grafo de la figura 1.2, donde las distancias
están expresadas en Km.

Figura 1.2

Se debe representar cada nodo con su identificador y su valor. Para ello se comienza con el nodo
0, asignándole un valor 0 (Paso 1 del procedimiento iterativo indicado anteriormente).

El siguiente paso es asignar a los nodos A y C su valor.

2 ---
--- 7 5 T
A ---
2 D
2 4
1 7
5
0 ---
--- B
O 1 3

4
4 4
---
C ---
E

Corresponde repetir el paso 2 para el nodo B.

2 ---
--- 7 5 T
A ---
2 D
2 4
4 1 7
5
0 ---
--- B
O 1 3

4
4 4
---
C ---
E

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 224
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

De igual manera se asignan los valores a los nodos D y E, para luego terminar con el nodo T.
13
2 ---
--- 7 8 5 T
A ---
2 D
2 4
4 1 7
5
0 ---
--- B
O 1 3

4
4 4
--- 7
C ---
E

La distancia mínima correspondiente al valor del nodo T, esto es 13 km.

El último paso es determinar la ruta mínima partiendo del nodo final T. Es decir, entre 13 – 5 = 8
y 13 – 7 = 6, se elige el nodo D ya que la resta igual a 8 coincide con el valor del nodo D. En este
caso corresponde a la cadena O – A – B – E – D – T y a la cadena O – A – B – D – T. Existe dos
rutas críticas ya que al analizar el nodo D, tanto el valor del nodo E como el del nodo B, coinciden
con sus respectivas restas.
Los valores que se indican en cada aro normalmente corresponden a distancia, pero el mismo
tratamiento se realiza si esta referido a costo o tiempo, y así determinar la ruta de mínimo costo o
que consume menos tiempo.

b) Algoritmo de Floyd
Este algoritmo entrega las distancias y rutas más cortas entre todos los pares posibles de la red.

En este algoritmo el valor del arco que va desde el nodo i al nodo j se denota por Cij. Si para
algún par de nodos i y j, el valor de Cij=, significa que no existe un arco que va de i a j. Se
forma una matriz C con los elementos Cij.

El algoritmo también requiere de una matriz D, donde los elementos dij=i,  j, donde i y j varían
de i a n (n=número de nodos).

La matriz C entrega las distancias y la matriz d las rutas, que van modificando sus valores de
acuerdo al siguiente procedimiento.

Algoritmo de Floyd

Paso 1: Formar las matrices C y D.

Paso 2: Seleccionar la fila 1 y la columna 1 de la matriz C. Para todo i,j  1

Si (ci1+c1j)<cij, entonces dij=d1j en caso contrario dij no cambia.

Paso 3: Repetir el paso 2 seleccionando esta vez la fila k y la columna k. El algoritmo se

completa cuando la fila y columna selecciona coincide con el número de nodos.

NOTA:
Los elementos cij de la matriz C obtenida corresponde a las distancias mínimas entre
los nodos i y j.
La matriz d sirve para encontrar las rutas más cortas entre los nodos i y j. El elemento
dij es el nodo predecesor de j. Si dij = i se ha obtenido el camino, si no debe elegirse

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 225
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

el elemento dip (p=dij) que será el predecesor de p. Esto debe repetirse hasta que
dip=i.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 226
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Diagrama de Flujo del Método de Floyd

INICIO

Ingresar :N: # de nodos

Numero de arcos

Valor del arco i , j

Cij =
, No hay enlace entre i , j
dij = i ,j , (i= 1,n j= 1,n)

k=1

i,j k

SI
Cij = min{ Cij , (Cik + Ckj)}

SI
Cik +Ckj < Cij

Dij = dkj

k = k +1

K=
n+1 SI
SI

Verificar la distancia mas corta en C entre los nodos

buscados Y en D buscar los predecesores desde el nodo final
De Asi se encuentra la ruta MÁS CORTA

FIN

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 227
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

EJEMPLO: Determinar las distancias más cortas de todos los nodos de la figura 1.2 y la ruta
más corta entre los nodos A y T.
7 5 T
A
D
2
2 4
1 7
5 B
D 1 3
4
C E
4

PASO 1.- al aplicar el algoritmo consiste en formar las matrices C y D. En este ejemplo se ha
asignado a cada nodo (O, A, B,...T) un valor correlativo entre 1 y 7, con el fin de facilitar la
explicación del Algoritmo de Floyd.

PASO 2.- El siguiente paso es seleccionar la fila 1 y la columna 1 de la matriz C y analizar cada
cij para todo i, j distinto de 1.

c22 = Min [ c22, ( c21 + c12 )] = Min [, ( 2 + 2 ) ] = 4

Si ci1 + c1j < cij entonces dij = d1j si reemplazamos
2 + 2 <  entonces d22 = d12=1
c23 = Min [ c23, ( c21 + c13 )] = Min [2, ( 2 + 5 )] = 2
Si ci1 + c1j < cij entonces dij = d1j si reemplazamos
2 + 5 > 2 entonces d22 = no cambia

c24 = Min [ c24, ( c21 + c14 )] = Min [ , ( 2 + 4 )] = 6

d24 = d14 = 1

c25 = Min [ c25, ( c21 + c15 )] = Min [ 7 , ( 2 +  )] = 7

d25 = no cambia
Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 228
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

c26 = Min [ c26, ( c21 + c16 )] = Min [, ( 2 +  )] = 

d26 = no cambia

c27 = Min [ c27, ( c21 + c17 )] = Min [, ( 2 +  )] = 

d27 = no cambia

c32 = Min [ c32, ( c31 + c12 )] = Min [2 , ( 5 + 2 )] = 2

d32 = no cambia

c33 = Min [ c33, ( c31 + c13 )] = Min [  , ( 5 + 5 )] = 10

d33 = d13 = 1

c34 = Min [ c34, ( c31 + c14 )] = Min [1 , ( 5 + 4 )] = 1

d34 = no cambia

c35 = Min [ c35, ( c31 + c15 )] = Min [ 4 , ( 5 +  )] = 4

d35 = no cambia

c36 = Min [ c36, ( c31 + c16 )] = Min [ 3 , ( 5 +  )] = 3

d36 = no cambia

c37 = Min [ c37, ( c31 + c17 )] = Min [  , ( 5 +  )] = 

d37 = no cambia

c42 = Min [ c42, ( c41 + c12 )] = Min [  , ( 4 + 2 )] = 6

d42 = d12 = 1

c43 = Min [ c43, ( c41 + c13 )] = Min [ 1 , ( 4 + 5 )] = 1

d43 = no cambia

c44 = Min [ c44, ( c41 + c14 )] = Min [  , ( 4 + 4 )] = 8

d44 = d14 = 1

c45 = Min [ c45, ( c41 + c15 )] = Min [  , ( 4 +  )] = 

d45 = no cambia

c46 = Min [ c46, ( c41 + c16 )] = Min [ 4 , ( 4 +  )] = 4

d46 = no cambia

c47 = Min [ c47, ( c41 + c17 )] = Min [  , ( 4 +  )] = 

d47 = no cambia

c52 = Min [ c52, ( c51 + c12 )] = Min [ 7 , (  + 2 )] = 7

d52 = no cambia

c53 = Min [ c53, ( c51 + c13 )] = Min [ 4 , (  + 5 )] = 4

d53 = no cambia

c54 = Min [ c54, ( c51 + c14 )] = Min [ , (  + 4 )] = 

d54 = no cambia

c55 = Min [ c55, ( c51 + c15 )] = Min [ , (  +  )] = 

d55 = no cambia
c56 = Min [ c56, ( c51 + c16 )] = Min [ 1 , (  +  )] = 1
d56 = no cambia

c57 = Min [ c57, ( c51 + c17 )] = Min [ 5 , (  +  )] = 5

d52 = no cambia
Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 229
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

c62 = Min [ c62, ( c61 + c12 )] = Min [  , (  + 2 )] = 

d62 = no cambia

c63 = Min [ c63, ( c61 + c13 )] = Min [ 3 , (  + 5 )] = 3

d63 = no cambia

c64 = Min [ c64, ( c61 + c14 )] = Min [ 4 , (  + 4 )] = 4

d64 = no cambia

c65 = Min [ c65, ( c61 + c15 )] = Min [ 1 , (  +  )] = 1

d65 = no cambia

c66 = Min [ c66, ( c61 + c16 )] = Min [  , (  +  )] = 

d66 = no cambia

c67 = Min [ c67, ( c61 + c17 )] = Min [ 7 , (  +  )] = 7

d67 = no cambia

c72 = Min [ c72, ( c71 + c12 )] = Min [  , (  + 2 )] = 

d72 = no cambia

c73 = Min [ c73, ( c71 + c13 )] = Min [  , (  + 5 )] = 

d73 = no cambia

c74 = Min [ c74, ( c71 + c14 )] = Min [  , (  + 4 )] = 

d74 = no cambia

c75 = Min [ c75, ( c71 + c15 )] = Min [7 , (  +  )] = 7

d75 = no cambia

c76 = Min [ c76, ( c71 + c16 )] = Min [ 7 , (  +  )] = 7

d76 = no cambia

c77 = Min [ c77, ( c71 + c17 )] = Min [  , (  +  )] = 

d77 = no cambia

Luego de aplicar el paso 2 del algoritmo, las matrices C y D quedan de la siguiente manera:

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 230
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

PASO 3.- Indica que debemos repetir el paso 2 pero elegir la fila 2 y columna 2 y recalcular las
matrices C y D para todo i,j distinto de 2, considerando:

cij = Min [ cij, ( ci2 + c2j )]

Si (ci2 + c2j < cij , entonces dij = d2j
En caso contrario no cambia

Por razones de espacio y debido a que el procedimiento es análogo al anterior se omiten los
cálculos y sólo Se entregan las matrices C y D resultantes. A modo de ejercitación se recomienda
realizar los cálculos de la misma forma hecha con la fila 1 y la columna 1.

De igual forma debemos proceder a elegir la fila 3 y la columna 3, para luego seleccionar la fila 4
y la columna 4 y así sucesivamente hasta llegar la fila 7 y la columna 7. aquí solo se entregan los
últimos resultados obtenidos

Para la fila 7 y columna 7 :

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 231
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

d = 13 Km. entre O, T

d = 11 Km. entre A, T

La matriz C responde la primera pregunta de este ejemplo; las distancias mas cortas entre cada par
de nodos. Así por ejemplo la distancia más corta entre los nodos A y T es 11.

Ruta Mínima Nodos A y T (2 y 7) analizando d27(T) i=2 , j=7 d27 = 5

Si d27<>i entonces d2p= d25(D) ; donde p=dij=5
Si d25<>i entonces d2p= d23(B) ; donde p=dij=3
Si d23 = i entonces el siguiente nodo es (A) ;

Entonces la matriz D sirve para responder la pregunta de la ruta más corta entre los nodos A y T (2
y 7). Para ello se analiza el elemento d27 de tal forma que el predecesor de 7(T) es 5(D), el
predecesor de 5(D) es 3(B) y por último el predecesor de 3(B) es 2(A). Por lo tanto la ruta más
corta entre A y T corresponde a A – B – D – T , y tiene una distancia, como se dijo, de 11 Km.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 232
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Ejemplos de las aplicaciones de la ruta mas corta

EJEMPLO 1(Reemplazo de equipo)

Una compañía arrendadora de automóviles está desarrollando un plan de reemplazo de su flotilla
para los proximos 5 años. Un automóvil debe estar en servicio cuando menos un año antes de que
se considere ser reemplazado. La sgte. tabla resume el costo de reemplazo por unidad en miles de
unidades monetarias como función del tiempo y el número de años en operación.

1 2 3 4 5
1 4.0 5.4 9.8 13.7
2 4.3 6.2 8.1
3 4.8 7.1
4 4.9

Este problema se puede representar mediante una red como sigue. Cada año está representado por
un nodo. La longitud de un arco que une dos nodos es igual al costo de reemplazo asociado que se
da en la tabla. La sgte. figura

9.8 13.7
5.4

1 2 3 4 5
4 4.3 4.8 4.9

6.2 7.1
8.1

Representa la red. El problema se reduce a determinar la ruta mas corta del nodo 1 al nodo 5.
La ruta mas corta se puede determinar mediante el uso del algoritmo que presentaremos mas
adelante(seccion 6..2.2). La solución óptima produce la ruta 1 2  5 con un total de 4 + 8.1 =
12.1 (miles de unidades monetarias). Esto quiere decir que cada automóvil debe reemplazarse al
segundo año de uso y desecharse al quinto año( 2 y 5).

Ejemplo 2. (La ruta mas Confiable)

La señorita Maria tiene que conducir todos los días, de su residencia a su lugar de trabajo.
Habiendo tomado solo una clase de análisis de redes, ella pudo determinar la ruta mas corta para
llegar a su trabajo. Para su decepción, descubrió que la ruta mas corta estaba muy vigilada por la
policia, que siempre la detenía injustamente por violar los límites de velocidad.
Con todas la multas que pagaba ella, llegó a la conclusión de que su ruta mas corta
evidentemente no era la mas económica. Por lo tanto, decidió estudiar el problema desde un
ángulo diferente. La Srta. Maria desearía elegir su ruta de manera que se maximice la probabilidad
total de no ser detenida por la policia. Observando todos los segmentos del camino factibles entre
su residencia y su trabajo, ella recopiló las probabilidades que se indican en los diferentes arcos
(segmentos de camino) figura siguiente.
2 0.8
4 0.35
6
0.5
0.2
0.6
0.4 7
1 0.1

0.9
0.25
0.3
3 5

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 233
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

En este caso se dice que los arcos son dirigidos u orientados.

Investigando la información de las probabilidades, ella comprendió que la probabilidad total de no

ser detenida por la policia en una ruta dada es igual al producto de las probabilidades asociadas
con los segmentos de camino que constituyen la ruta dada. Por ejemplo, la probabilidad asociada
con la ruta:
1 2 3  5  7 es de 0.2 x 0.6 x 0.3 x 0.25 = 0.009.
Aunque es posible calcular todas estas probabilidades (ocho rutas diferentes), la Srta. Maria
decidió convertir el problema en un modelo de la ruta mas corta mediante el uso de la siguiente
conversión. Haciendo que:
P1k = P1 x P2 x...x Pk
sea la probabilidad de no ser detenida en la ruta específica (1,k) entonces:
log P1k = log P1 x log P2 x...x log Pk
Una maximizacíon de P1k es algebricamente equivalente a maximizar P1k y, en concecuencia, a
maximizar la suma de los algoritmos de las probabilidades individuales a lo largo de la ruta
elegida. Como los
Pj  j = 1, 2,..., k

Maximizar la suma de los logPj equivale a minimizar la suma de (-logPj). En la siguiente tabla
presentamos el resumen de las probabilidades y sus logaritmos del ejemplo

SEGMENTO DE
CAMINO Pij logPij -logPij
(i , j)
(1,2)
(1,3) 0.2 -0.69897 0.69897
(2,3) 0.9 -0.04576 0.04576
(2,4) 0.6 -0.22185 0.22185
(3,4) 0.8 -0.09691 0.09691
(3,5) 0.1 -1.0 1.0
(4,5) 0.3 -0.52288 0.52288
(4,6) 0.4 -0.39794 0.39794
(5,7) 0.35 -0.45593 0.45593
(6,7) 0.25 -0.60206 0.60206
0.5 -0.30103 0.30103

Luego, la figura siguiente expresa el problema de la Srta. Maria como un modelo de la ruta mas
corta.

2 0.096 4 0.455 6

0.301
0.698

7
1

0.045
0.602

0.522
3 5

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 234
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Algoritmo de la ruta mas corta para redes aciclicas

En esta sección presentamos un algoritmo para obtener la ruta mas corta en redes acíclicas. El
algoritmo es muy simple, pero presenta el concepto fundamental de los cálculos recursivos, que es
la base de los cálculos de programación dinámica.
Primero desarrollamos el algoritmo a través de un ejemplo numérico. Después se explica el
procedimiento desde el punto de vista de cálculos recursivos.
Ejemplo :

Considere la red de la figura

| fase 1 | fase 2 | fase 3 | fase 4 | fase 5 |

2 = 2 5 5= 7
2 5
6
2 11 8

10 7
1 4 4 = 7 7 =13
1 = 0
7
3 9
4
1
3 6

3 = 4 6 = 5

El nodo 1 es el punto inicial (origen) y el nodo 7 es el punto terminal(destino). Nótese que la red
es acíclica, ya que no existen cadenas que conecten un nodo con él mismo.

Antes de presentar el procedimiento de solución, necesitamos las definiciones siguientes:

dij = distancia de la red entre los nodos adyacentes i y j

jdistancia mas corta del nodo i al nodo j, 10

el procedimiento está completo cuando se calcula 7 La formula general para calcular j es :

la distancia mas corta a un nodo i inmediatamente anterior

j = Min mas = Min{ j+ dij }
la distancia entre el nodo actual j y su predecesor i

La formula implica que la distancia mas corta j al nodo j se puede determinar sólo después de que
se calcula la distancia mas corta a cada nodo predecesor i enlazado a j por un arco.
Dando inicio a los cálculos en el nodo 1, vemos que solo 2 y 3 se pueden determinar en este
punto. (aunque 4 está enlazado a 1, 4 no se pueden calcular sino hasta que se conozcan 2 y 3) La
sucesión de cálculos procede en fases del modo siguiente:

Fase 1:1 = 0
Fase 2:2 = 1+ d12 = 0 + 2 = 2 (desde 1)
3 = 1+ d13 = 0 + 4 = 4 (desde 1)
Fase 3:4 = min{1+ d14 , 2+ d24 , 3+ d34 }
= min{ 0 + 10 , 2 + 11 , 4 + 3} = 7 (desde 3)

Fase 4:5 = min{2+ d25 , 4+ d45 }

= min{ 2 + 5 , 7 + 8 } = 7 (desde 2)
6 = min{3+ d36 , 4+ d46 }

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 235
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

= min{ 4 + 1 , 7 + 7 } = 5 (desde 3)

Fase 5:7 = min{5+ d57 , 6+ d67 }

= min{ 7 + 6 , 5 + 9 } = 13 (desde 5)

La distancia mínima de 1 a 7 es 13 y sigue la ruta 1 2  5  7.

Observe también que la solución produce la distancia más corta de 1 a cada uno de los nodos
restantes de la red.

En realidad se pueden efectuar los cálculos directamente en la red, como se puede ver en la fig.
del ejemplo. El valor de j para el nodo j se determina solo después de calcular i para todos los
nodos i inmediatamente anteriores a j. Por tanto, comenzando con 1 = 0 obtenemos 2 = 2 y 3 =
4. Después puede obtenerse 4 =7. En este punto se obtienen 5 =7 y 6 = 5. En el paso final se
determina 7 = 13

El tipo de operaciones que se describen arriba es interesante porque tiene que ver con cálculos
recursivos. Esto se caracteriza por el uso de información que resume las distancias más cortas
hasta el nodo inmediatamente anterior. Por ejemplo, en el nodo 5 5 se calcula con base en las
distancias más cortas del nodo 1 a los nodos 2 y 4, es decir 2 y 4 . Nótese que nunca es
necesario conocer la ruta específica que nos conduce a la distancia más corta entre 1 y 4. el valor
de 4 resume toda la información que necesitamos conocer a cerca del nodo 4. Este tipo de
recopilación es lo que hace posible el uso del cálculo recursivo.

5.2.2 PROBLEMA DEL FLUJO MAXIMO

En esta sección se considera la situación en la que se enlazan un nodo fuente y un nodo destino a
través de una red de arcos unidirigidos (un solo sentido). Cada arco tiene una capacidad máxima
de flujo admisible. El objetivo es de obtener la máxima cantidad de flujo entre la fuente y el
destino. Un ejemplo de esta situacion es el caso donde un número de refinerias se conectan a
terminales de distrtibución a través de oleoductos. En los oleoductos están montadas unidades de
bombeo que impulsan los productos derivados del petróleo hasta las terminales de distribución. El
objetivo consiste en maximizar el flujo entre las refinerias y las terminales de distribución dentro
de los limites de capacidad de las refinerias y los oleoductos.
La figura siguiente ilustra el problema de flujo máximo de la refineria:

7
1
4
9
0 2 6

Fuente 5 8 Depósito
3

Refinerías Estaciones de Bombeo Terminales

Aquí sumamos una fuente que se conecta a todas las refinerias y un deposito que recibe flujo de
todas las terminales de distribución. Los nodos entre las refinerías. Cada oleoducto tiene una
capacidad de diseño máximo que determina el flujo máximo admisible en línea. Los arcos tendidos
de los terminales de distribución al depósito tienen supuestamente capacidades infinitas para hacer
posible la determinación del flujo máximo proveniente de las refinerias.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 236
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

En algunos casos, quiza deseemos utilizar las demandas en las terminales como capacidades de los
arcos del depósito.

El problema del flujo máximo en una red se define como

Este problema de programación línea tiene métodos propios de solución que resultan más
eficientes que el método simples.

Algoritmo de Ford – Fulkerson

En este algoritmo el valor de los arcos de la red representa la capacidad máxima( lo que permitiría
pasar) de una canalización entre los nodos.

Así la red es orientada y valorizada en sus arcos. Se requiere de un nodo de origen S y un nodo
destino T. En el caso que al plantear un problema existiesen más de un nodo origen o destino, se
deben incorporar nodos artificiales con capacidades infinitas para que no influyan en el resultado
del problema.

El algoritmo incluye los siguientes pasos:

PASO 1: Introducir un flujo cualesquiera en la red, compatible con las capacidades máximas
dadas.
PASO 2: Buscar flujos completos, de forma que haya a menos un arco saturado.
PASO 3: Repetir los pasos anteriores hasta que no pueda aumentarse el flujo que se reciba el
nodo final.

Alcanzando este punto se obtiene un flujo denominado flujo completo, que será la suma de los
flujos de los arcos que llegan al nodo final.

Para comprobar si este flujo es el máximo de la red se aplica el siguiente método de la cadenas
incrementales:

a) Marcar el nodo inicial con +

b) Marcar con + los sucesores de los nodos marcados cuyos arcos no estén saturados.
c) Marcar con – los predecesores de nodos marcados cuyos flujos sean distintos de cero. En
este procedimiento no se marca un nodo ya marcado.
d) Buscar un camino de nodos marcados que vaya del nodo inicial al nodo final de forma de
tomar la dirección del arco si los dos nodos están marcados con + y el arco no esta
saturado. También puede incluirse como parte del camino a arcos cuyo nodo inicial este
marcado con - , siempre y cuando el flujo de ese arco sea distinto de cero, en sentido
contrario a la dirección del arco.
e) La cadena seleccionada admite un flujo máximo, el cual incrementará el flujo completo de
la red.
El flujo introducido en la cadena se sumará al flujo de los arcos recorridos en sentido positivo y se
restará al flujo de los arcos recorridos en sentifdo negativo.
Esta operación puede saturar arcos no saturados y viceversa.
Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 237
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

f) Buscar nuevas cadenas increméntales mientras sea posible. Mientras no es encuentren más
cadenas increméntales, el flujo completo encontrado será el flujo será el flujo máximo de la red.

Diagrama de flujo de Ford – Fulkerson

INICIO

N: número de
nodos
Número de arcos

Introducir un flujo cualquiera en la red, compatible

con las capacidades máximas dadas

Marcar el nodo inicial con

Marcar con los sucesores de los nodos

marcados cuyos arcos no estén saturados.

Marcar con los predecesores de los nodos

marcados cuyos flujos sean distintos de cero

Buscar un camino de nodos marcados de forma de

tomar la dirección del arco si los dos nodos están
marcados con y el arco no esta saturado

La cadena seleccionada admite un flujo máximo, el

cual incrementará el flujo completo de la red.

Se pueden
encontrar cadenas a
traves de los nodos
marcados?
NO
El flujo completo hallado es el flujo máximo de la red

FIN

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 238
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

EJEMPLO.- Calcular el flujo máximo en la red de la figura 1.3, donde los valores sobre los
arcos representan las capacidades máximas entre los dos nodos.
A 3 B
5
10

S T
5 8
7

6 4 5
E
7

C 3 D

Figura 1.3.

Aplicaremos paso a paso uno de los puntos del algoritmo descrito.

Iteración 1.
Introducir un flujo completo en la red, es decir, encontrar una ruta del origen al destino con
capacidad positiva
S 10 A 8 E 1 T

Como el flujo posible es 1, debe descontarse en todos los arcos correspondientes. El arco saturado
es (E, T).

Iteración 2.

S 9 A 3 B 5 T

Flujo = 3, por lo que debe descontarse de los arcos (S, A), (A, B) y (B, T). Arco saturado = (A, B).

Iteración 3.

S 6 C 3 D 5 T

Flujo = 3. Arco saturado (C, D).

Iteración 4.

S 3 C 4 B 2 T

Flujo = 2, arco saturado (B, T).

Iteración 5.

S 1 C 7 A 5 D 2 T

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 239
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Flujo = 1, arco saturado (S, C).

Iteración 6.

S 6 A 4 D 1 T

Flujo = 1, arco saturado (D,T).

Como se han saturado todos los arcos que llegan al nodo final el flujo completo de la red
encontrado corresponde al flujo máximo.
Lo anterior también ocurre si todos los arcos salen del nodo origen están saturados.

Al aplicar el método de las cadenas incrementales obtenemos:

A B
3
5
10

S 5 T
8
7

1
6
4 5
E
7
C D
3

Debido a que no es posible encontrar una cadena que vaya del nodo origen al ndo final a través de
los nodos marcados, el flujo completo hallado es el flujo máximo de la red.

5.2.3 PROBLEMA DE FLUJO A COSTO MÍNIMO

En estas redes se va a calcular a costo mínimo de enviar flujo de un nodo de un nodo a otro.

Si Cij0 es el costo unitario del arco Aij que va del nodo Ni al nodo Nj entonces, Cij no satisface la
propiedad geométrica que dice que el trayecto más corto y por ende más económico entre dos
puntos, es que el se utiliza la recta que une a esos dos puntos. En términos de la siguiente figura se
tiene que no se cumple necesariamente la siguiente desigualdad.

Cij + Cjk  Cik

Cik
N N
i k

Cij
Cjk

N
j

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 240
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

En una red se puede tener que Cik Cij + Cjk o bien Cik Cij + Cjk dependiendo de los costos
unitarios en cuestión.
El algoritmo que se va a presentar es el que determina la cadena de arcos más económicas de la
fuente al destino de una red.

Algoritmo de Dijkstra para determinar el trayecto más económico de la fuente al

destino de una red

El algoritmo que diseño Dijkstra sirve para determinar la ruta más económica entre la fuente y el
destino de una redes. Este tipo de problemas tiene aplicaciones en problemas de distribución y
asignación de recursos.
En este algoritmo se considera que los arcos de una red pueden pertenecer a sólo uno de los
siguientes conjuntos, mutuamente excluyentes, a saber:
a) El arco pertenece a un árbol.
b) El arco no pertenece a un árbol.
Al principio los arcos los arcos no pertenecen al árbol. En cada iteración el algoritmo incrementa
en uno el número de arcos en el árbol, hasta llegar a n-1 arcos, donde n es el número de nodos en
la red. Cuando el árbol queda formado por n-1 arcos, el algoritmo llega a su conclusión y
determina la solución del problema.

Algoritmo del método de Dijkstra

PASO 1:Sea Ns el nodo fuente. Entonces L´sk = Csk para toda Ask que este definido en la red. El
nodo Ns pasa a ser un Elemento del árbol. Se define Lss.= 0.

PASO 2:Sea

L´sr = Min{L´sk} = Min[Lsj + Cjk]

Donde Nk son todos los nodos vecinos a los nodos del árbol en cuestión.

PASO 3:El arco Ajr pasa a ser un elemento del árbol. Se etiqueta al nodo Nr con ( Lsr, Nj ).

PASO 4:Si el árbol tiene n – 1 arcos, pare, la solución óptima ha sido encontrada en caso contrario
continúe son el PASO 5.

PASO 5:Sea:

L´sk = Min[ L´sk ; Lsr + Crk ]

Para todos los nodos Nk vecinos a los nodos del árbol en cuestión. Regrese al PASO 2.
Este algoritmo también etiqueta a todos los nodos. Un nodo N j puede tener una etiqueta temporal o
permanente. Independientemente del tipo de etiqueta, cada una estas llevará dos componentes. La
primera indica el costo temporal o permanente más económico de alcanzar el nodo N j desde el
nodo fuente y la segunda componente indica el nodo del cual se procede.
Una etiqueta (L´sk, Ni) es temporal mientras que una etiqueta (L sk, Ni) es permanente. Cuando un
costo no esta definido, se toma a este como .

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 241
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Diagrama de flujo del Método de Dijkstra

INICIO

Ingresar el número de nodos N

y los arcos L’ij donde i,j = 1,n

Hacer Lss = 0

Hallar los vecinos Nkdel árbol

Hacer L´sr = Min{L´sk} = Min[Lsj + Cjk]

El arco Ajr pasa a ser un elemento del árbol. Se

etiqueta al nodo Nr con ( Lsr, Nj ).

SOLUCION
Si el árbol tiene OPTIMA
n – 1 arcos ?

Hallar los vecinos Nk del árbol en cuestión

FIN

Hacer L´sk = Min[ L´sk ; Lsr + Crk ]

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 242
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Ejemplo: Supóngase que en la siguiente red (después se le da un significado intuitivo) se quiere

hallar la ruta más económica del nodo fuente N s al nodo destino Nt, en donde los números
indicados sobre el arco Aij son los costos unitarios Cij. Los arcos sin flecha son adireccionales.

1
4
4 5
4 2 4

t
3
s 2
1
1

5
1
1
7

Iteración 1:
Paso 1. Ns pasa a formar parte del árbol, Lss = 0.
Vecinos a los nodos del árbol son N1 , N2 , N3 .
Lss = 0 , L’14 = L’41 = 2 , L’s1 = 4 , L’12 = L’21 = 2 , L’s2 = 3 , L’15 = L’51 = 4 , L’s3 = 1 , L’24 = L’42 =
5, L’32 = 1 , L’4t = L’t4 = 4 , L’5t = L’t5 = 1 , L’1s = ,L’23 =  , L’3s =  , L’st =  , etc.
Paso 2. Lsr = Min{L´sk} = Min[Lss + Csk] = Min{4, 3, 1} = 1
K=1,2,3 K=1,2,3
Lsr = L´s3
r=3

Paso 3. El arco As3 pasa a ser un elemento del árbol. Se etiqueta al nodo N3 con ( 1 , s ).
Paso 4. como el árbol no contiene n – 1 = 7 – 1 = 6 elementos. Se continua.
Paso 5. L´sk = Min[ L´sk ; Lsr + Crk ]
K=1,2,4,5

Como todos los nodos vecinos a los nodos del árbol son N1 , N2 , N4 , N5 se tiene:

L´s1 = Min[ L´s1 ; Ls3 + C31 ] = Min(4, 1 + ) = 4

L´s2 = Min[ L´s2 ; Ls3 + C32 ] = Min(3, 1 + 1) = 2
L´s4 = Min[ L´s4 ; Ls3 + C34 ] = Min(, 1 + ) = 
L´s5 = Min[ L´s5 ; Ls3 + C35 ] = Min(, 1 + 7) = 8

Iteración 2:

Paso 2. Lsr = Min{4, 2, ,8} = 2

Lsr = L´s2
r=2

Paso 3. El arco A32 pasa a ser un elemento del árbol. Se etiqueta al nodo N2 con ( 2 , 3 ).
Paso 4. Hay dos elementos 2 < 6 elementos. Se continua.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 243
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Paso 5. Los nodos vecinos a los nodos del árbol son N1 , N4 , N5 se tiene:

L´s1 = Min[ L´s1 ; Ls2 + C21 ] = Min(4, 2 + 2) = 4

L´s4 = Min[ L´s4 ; Ls2 + C24 ] = Min(, 2 + 5) = 7
L´s5 = Min[ L´s5 ; Ls2 + C25 ] = Min(8, 2 + ) = 8

Iteración 3:
Paso 2. Lsr = Min{4, 7 ,8} = 4

Lsr = L´s1
r=1

Paso 3. El arco As1 pasa a ser un elemento del árbol. Se etiqueta al nodo N1 con ( 4 , s ).
Paso 4. Hay elementos < 6. Se continua.
Paso 5. Los nodos vecinos a los nodos del árbol son N4 , N5 se tiene:

L´s4 = Min[ L´s4 ; Ls1 + C14 ] = Min(7, 4 + 2) = 6

L´s5 = Min[ L´s5 ; Ls1 + C15 ] = Min(8, 4 + 4) = 8

Iteración 4:
Paso 2. Lsr = Min{6 ,8} = 6

Lsr = L´s4 = 6
r=4

Paso 3. El arco A14 pasa a ser un elemento del árbol. Se etiqueta al nodo N4 con ( 6 , 1 ).
Paso 4. Hay elementos < 6. Se continua.
Paso 5. Los nodos vecinos a los nodos del árbol son N5 , Nt se tiene:

L´s5 = Min[ L´s5 ; Ls4 + C45 ] = Min(8, 6 + ) = 8

L´st = Min[ L´st ; Ls4 + C4t ] = Min(, 6 + 4) = 10

Iteración 5:
Paso 2. Lsr = Min{8 ,10} = 8

Lsr = L´s5 = 8
r=5

Paso 3. El arco A35 pasa a ser un elemento del árbol. Se etiqueta al nodo N5 con ( 8 , 3 ).
Paso 4. Hay elementos < 6. Se continua.
Paso 5. L´st = Min[ L´st ; Ls5 + C5t ] = Min(10 , 8 + 1) = 9

Iteración 6:
Paso 2. Lsr = L´st = 9
r=t

Paso 3. El arco A5t pasa a ser un elemento del árbol. Se etiqueta al nodo Nt con ( 9 , 5 ).
Paso 4. Como el árbol contiene n – 1 = 6 elementos, se ha llegado a la solución óptima
del problema, que gráficamente aparece a continuación .

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 244
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

(4,s)
(6,1)
1
4

(9,5
)
(2,3 t
)
s 2
(8,3
)
5

(1,s
)
3

La solución óptima indica que la ruta más económica del nodo destino a la fuente, es vía la cadena
Ns , As3 , N3 , A35 N5 , A5t , Nt y cuesta 9 unidades por unidad de flujo en esta cadena, esta cadena
óptima no es única. Otra alternativa hubiera sido la Ns , As1 , N1 , A15 N5 , A5t , Nt.
Este problema se podría pensar como una red ferrocarrilera que une varios puntos. Los arcos
dirigidos representarían una sola via, mientras que los arcos no dirigidos representan una doble via
donde el trafico de ferrocarriles se desarrolla simultáneamente en ambos sentidos y los nodos son
estaciones.

5.2.4 PROBLEMA DE FLUJO MÁXIMO A COSTO MÍNIMO

Este tipo de problemas tiene una aplicación bastante amplia dentro del área de optimización de
recursos.
Formulación Matemática
El problema de flujo máximo a costo mínimo puede representarse matemáticamente como:

sujeto a:

Algoritmo de Busacker y Gowen

PASO 1:Xij = 0 para todos los arcos Aij y v = 0.

PASO 2:Constrúyase un nuevo costo en el arco Aij basado en la siguiente definición:

= cij, si 0 Xij < uij (el costo no cambia).
= , si Xij = uij (el arco se satura).
= - cij , si Xij > 0 (arcos en reserva para posible reducción de flujo).

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 245
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

PASO 3:Encuéntrese la ruta más económica del nodo fuente Ns al nodo destino Nt basado
en los costos e utilizando cualquier algoritmo disponible, por ejemplo, el de
Dijkstra.

Mándese la mayor cantidad de flujo permisible por la ruta más económica que se
encuentre, es decir, hasta que uno o varios arcos que componen esta ruta se
saturan.

Añádase al flujo actual en toda la red, el flujo adicional que se encuentre en este
paso. Si todas las rutas que conducen al destino N t están saturadas, la solución
optima ha sido encontrada, de otra manera, regrese con el flujo actual al paso 2.

Ejemplo: Supóngase la red que se muestra en la figura. Los números en los arcos representan
respectivamente la capacidad mínima, máxima y el costo unitario.
3

(0,1,1) (0,1,2)

(0,1,1) (0,1,2) (0,1,1)

s 1 2 t

(0,2,2) (0,2,2)

4
Iteración 1

Paso 1. v=0.
Xij = 0, para toda Aij.

Paso 2. = 1, = 2, =2
=2
= 1, = 2,

Paso 3. Utilizando algoritmo de Dijkstra se encuentra que la cadena más económica de la fuente al
destino es la Ns, As1, N1, A12, N2, A2t, Nt, o bien la Ns, As3, N3, A32, N2, A2t, Nt, ambas con un
costo de 4 unidades.

En ambas rutas, la máxima capacidad de flujo que se puede mandar es una unidad. Se han elegido
arbitrariamente la primera cadena.

Iteración 2

Paso 2. El flujo actual y los nuevos costos, junto con los arcos en reversa para posible
disminución del flujo, se muestran a continuación:

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 246
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

(0,1,1) (0,1,2)
(0,1,-2)

(0,1,1) (0,1,2) (0,1,1)

V=1 s 1 2 t V=1
1 1 1

(0,1,-1)
(0,1,-1) (0,2,2)

(0,2,2)

Los nuevos costos son:

=  (por estar saturado el arco As1)

=  (por estar saturado el arco A12)
=  (por estar saturado el arco A2t)
= -1 (por tener el arco As1 flujo positivo)
= -2 (por tener el arco A12 flujo positivo)
= -1 (por tener el arco A2t flujo positivo)

los restantes permanecen igual.

Paso 3. Aplicando el algoritmo de Dijkstra se encuentra que la cadena más económica es la N s,

As3, N3, A32, N2, A21, N1, A14, N4, A4t, Nt con costo de 1 + 2 – 2 + 2 + 2 = 5 unidades. El flujo
máximo que puede pasar a través de esta cadena es una unidad, tal como se muestra a
continuación.

3
1
1 (0,1,1) (0,1,2)
1

(0,1,1) (0,1,2) (0,1,1)

V=2 s 1 2 t V=2
1

(0,2,2) (0,2,2)
1
1

Nótese que el flujo de una unidad en A 12 se cancela con el flujo de una unidad de A 21. el resultado
neto es que eliminando el flujo en A12 se puede incrementar el flujo total de la red a dos unidades.
La solución óptima consiste en mandar dos unidades a un costo de nueve.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 247
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Diagrama de Flujo del Método de Busacker y Gowen

INICIO

Hacer Xij = 0 para todos los arcos Aij y v = 0

Si
, si 0 Xij < uij

= cij

Si
si Xij = uij

=

Si
si Xij > 0

= - cij

Aplicar el algoritmo de DIJKSTRA, basado en los

costos

Encontrado el flujo adicional, añádase al flujo actual en

toda la red.

todas las rutas

están
saturadas?
rutas que Si
conducen al
destino Nt
Solución
están
Optima
saturadas, la
solución
FIN
optima ha sido

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 248
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

5.3 PRESENTACIÓN DE PROGRAMACIÓN LINEAL DE REDES

Los problemas de la ruta más corta y del flujo máximo pueden formularse como modelos de PL en forma
explícita. Sin embargo, destacamos que la solución de modelos de redes a través del método simplex no
es recomendable. Por otra parte, un estudio de formulaciones de programación lineal a redes debe
ayudarnos a reconocer modelos de PL que no pueden ser redes en el sentido directo, pero que pueden
formularse directamente o con modificaciones como una red. La ventaja evidente que se obtiene es que
se puede mejorar drásticamente la eficiencia de los cálculos cuando se utiliza la formulación de redes.
El modelo PL de un problema de la ruta más corta se construye de la manera siguiente:
1. Cada variable corresponde a un arco.
2. Cada restricción corresponde a un nodo.
Por lo tanto, si Xij representa la cantidad de flujo en el arco (i,j), el modelo de la ruta mas corta con n
nodos está dado como:

Las restricciones del modelo de PL están basados en la formulación de transbordo del problema de la ruta
más corta que se presentó antes. Se envía una unidad de flujo del nodo 1 para ser recibida en el nodo n.
La primera y última restricción señalan que el flujo total (suma de variables) que sale del nodo 1 es igual
a 1 y que el flujo total que se recibe el nodo n es también igual a 1. en cualquier nodo intermedio, el flujo
total que entra al nodo es igual al flujo total que sale del mismo nodo. La función objetivo requiere que se
minimice la distancia total que recorre la unidad de flujo.
Debemos señalar que la formulación anterior producirá una solución significativa solo si X ij = 0 ó 1; esto
es, una arco(i,j) está en la ruta más corta sólo si X ij = 1, Si Xij = 0, (i,j) no esta en la ruta mas corta.
Aunque los requisitos Xij = 0 ó 1 no se describen explícitamente en el modelo de PL, su estructura
especial produce siempre una solución óptima en la que se cumple esta condición. En realidad, el modelo
posee la propiedad totalmente unimodular, que garantiza que la solución de PL produce siempre X ij = 0 ó
1.

El problema del flujo máximo se puede formular como un modelo PL de manera análoga.
Específicamente, sea que y represente el flujo entre el nodo fuente 1 y el nodo terminal n. Mediante el uso
de la misma notación Xij para representar el flujo en el arco (i,j), en el modelo de PL se transforma en

Donde ij representa la capacidad del flujo en el arco (i,j). Notamos que la construcción de las
restricciones sigue la misma lógica que se utilizó en el desarrollo del modelo PL de la ruta más corta.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 249
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

EJERCICIOS RESUELTOS

1. (Ford)En la red de la figura proporciona la distancia en millas entre los pares de ciudades 1,2,...y 8
encuentre la ruta más corta entre las ciudades:
a) Ciudades 1 y 8.
b) Ciudades 1 y 6.

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

1 2 3
7 6

2 4 7
5 8

SOLUCION:
Para solucionar este problema utilizamos el método de Ford.

PASO 1.-Asignamos N1=0

PASO 2.- Hallamos los valores de los nodos utilizando sus predecesores j:
N2= Min{valor del nodo j + arco(j,2)} = Min {0 +1} =1
N3= Min{valor del nodo j + arco(j,3)} = Min {0 + 2,1+1} =2
N4= Min{valor del nodo j + arco(j,4)} = Min {2+2,1+5} =4
N5= Min{valor del nodo j + arco(j,5)} = Min {2+1,1+2, 3+4} = 3
N6= Min{valor del nodo j + arco(j,6)} = Min {2+4,3+3,6+4} = 6
N7= Min{valor del nodo j + arco(j,7)} = Min {6+5,3+7,4+8} = 10
N8= Min{valor del nodo j + arco(j,8)} = Min {6+2,10+6} =8

PASO 3.-restar a partir del ultimo nodo los valores de los nodos de sus predecesores j
N8= {valor del nodo 8 - arco(6,8)} = 6 almacenar por que es igual al valor del nodo 6
N8= {valor del nodo 8 - arco(7,8)} = 2 no se almacena

Analizar con el nodo del valor almacenado

N6= {valor del nodo 6 - arco(5,6)} = 3 almacenar por que es igual al valor del nodo 5
N6= {valor del nodo 6 - arco(3,6)} = 2 almacenar por que es igual al valor del nodo 3
N6= {valor del nodo 6 - arco(4,6)} = 0 no se almacena

Analizar con el nodo del valor almacenado(5)

N5= {valor del nodo 5 - arco(4,5)} = 0 no se almacena
N5= {valor del nodo 5 - arco(3,5)} = 2 almacenar por que es igual al valor del nodo 3
N3= {valor del nodo 5 - arco(2,5)} = 1 almacenar por que es igual al valor del nodo 2

Analizar con el nodo del valor almacenado(3)

N3= {valor del nodo 3 - arco(2,3)} = 1 almacenar por que es igual al valor del nodo 2
N3= {valor del nodo 3 - arco(1,3)} = 0 almacenar por que es igual al valor del nodo 1

En conclusión se hallo 5 rutas cortas de l nodo 1 al 8

 1,3,6,8
 1,3,5,6,8
 1,2,5,6,8
 1,2,3,5,6,8
 1,2,3,6,8

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 250
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

2. (floyd)Para la red de la figura encuentre las rutas más cortas entre cada dos nodos. Las distancias en
millas se dan en los arcos. El arco(3,5) e direccional de manera que no esta permitido ningún tráfico
del nodo 5 al nodo 3. Todos los demás arcos permiten el tráfico en ambas direcciones.
2 5 4
3
4

1 6

10 5
15

SOLUCION
PASO 1.- al aplicar el algoritmo consiste en formar las matrices C y D.

PASO 2.- El siguiente paso es seleccionar la fila 1 y la columna 1 de la matriz C y analizar cada cij
para todo i, j distinto de 1.

Para la Fila 1 y Columna 1

c22 = Min [ c22, ( c21 + c12 )] = Min [, ( 3 + 3 ) ] = 6

Si ci1 + c1j < cij entonces dij = d1j si reemplazamos
3 + 3 <  entonces d22 = d12=1
c23 = Min [ c23, ( c21 + c13 )] = Min [, ( 10 + 3 )] = 13
Si ci1 + c1j < cij entonces dij = d1j si reemplazamos
10 + 3 <  entonces d22 = d13=1
c24 = Min [ c24, ( c21 + c14 )] = Min [ 5, ( 3 +  )] = 5
d24 = no cambia

c25 = Min [ c25, ( c21 + c15 )] = Min [ , ( 3 +  )] = 

d25 = no cambia

c32 = Min [ c32, ( c31 + c12 )] = Min [ , ( 10 + 3 )] = 13

d32 = d12 =1

c33 = Min [ c33, ( c31 + c13 )] = Min [  , ( 10 + 10 )] = 20

d33 = d13 = 1

c34 = Min [ c34, ( c31 + c14 )] = Min [6 , ( 10 +  )] = 6

d34 = no cambia
c35 = Min [ c35, ( c31 + c15 )] = Min [ , ( 10 +  )] = 
d35 = no cambia

c42 = Min [ c42, ( c41 + c12 )] = Min [ 5 , ( + 3 )] = 5

d42 = no cambia

c43 = Min [ c43, ( c41 + c13 )] = Min [ 6 , ( + 10 )] = 6

d43 = no cambia

c44 = Min [ c44, ( c41 + c14 )] = Min [  , ( +  )] = 

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 251
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

d44 = no cambia

c45 = Min [ c45, ( c41 + c15 )] = Min [ 4 , (  +  )] = 4

d45 = no cambia

c52 = Min [ c52, ( c51 + c12 )] = Min [ , (  + 3 )] = 

d52 = no cambia

c53 = Min [ c53, ( c51 + c13 )] = Min [ 15 , (  + 10 )] = 15

d53 = no cambia

c54 = Min [ c54, ( c51 + c14 )] = Min [4 , (  +  )] = 4

d54 = no cambia

c55 = Min [ c55, ( c51 + c15 )] = Min [ , (  +  )] = 

d55 = no cambia

Luego de aplicar el paso 2 del algoritmo, las matrices C y D quedan de la siguiente manera:

PASO 3.- Indica que debemos repetir el paso 2 pero elegir la fila 2 y columna 2 y recalcular las
matrices C y D para todo i,j distinto de 2, considerando:

Por razones de espacio y debido a que el procedimiento es análogo al anterior se omiten los cálculos
y sólo Se entregan las matrices C y D resultantes. A modo de ejercitación se recomienda realizar
los cálculos de la misma forma hecha con la fila 1 y la columna 1.
(Resultados)Para la Fila 2 y Columna 2

Resultados)Para la Fila 3 y Columna 3

(Resultados)Para la Fila 4 y Columna 4

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 252
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

(Resultados)Para la Fila 5 y Columna 5

la distancia más corta entre los nodos 1 y 5 es 12.

Entonces la matriz D sirve para responder la pregunta de la ruta más corta entre los nodos 1 y 5.
Para ello se analiza el elemento d25 de tal forma que el predecesor de 5 es 4, el predecesor de 4 es 2.
Por lo tanto la ruta más corta entre 1 y 5 corresponde a 1 – 2 – 4 – 5 , y tiene una distancia, como se
dijo, de 12 Km.

3. (floyd)Tell – All, una compañía de teléfonos, le da servicio a seis áreas geográficas. Las distancias
por satélite (en millas) entre las seis áreas se proporcionan en la figura. Tell – All necesita
determinar las rutas de mensajes más eficientes que se deben establecer entre cada dos áreas de la
red.
2 700
700 6
200 100
300
1 4 500

200 700 300

3 5
600

SOLUCION
Dividimos los valores 700, 200,....,etc entre 100 para facilitar el trabajo y en el resultado final se
restablecerá la solución verdadera multiplicando por 100.
PASO 1.- al aplicar el algoritmo consiste en formar las matrices C y D.

PASO 2.- El siguiente paso es seleccionar la fila 1 y la columna 1 de la matriz C y analizar cada cij
para todo i, j distinto de 1.

Para la Fila 1 y Columna 1

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 253
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

c22 = Min [ c22, ( c21 + c12 )] = Min [, ( 7 + 7 ) ] = 14

Si ci1 + c1j < cij entonces dij = d1j si reemplazamos
7 + 7 <  entonces d22 = d12=1
c23 = Min [ c23, ( c21 + c13 )] = Min [3, ( 7 + 2 )] = 3
d22 = no cambia

c24 = Min [ c24, ( c21 + c14 )] = Min [ 2, ( 7 +  )] = 2

d24 = no cambia

c25 = Min [ c25, ( c21 + c15 )] = Min [ , ( 7 +  )] = 

d25 = no cambia

c26 = Min [ c26, ( c21 + c16 )] = Min [7 , ( 7 +  )] = 7

d26 = no cambia

c32 = Min [ c32, ( c31 + c12 )] = Min [3 , ( 2 + 7 )] = 3

d32 = no cambia

c33 = Min [ c33, ( c31 + c13 )] = Min [  , ( 2 + 2 )] = 4

d33 = d13 = 1

c34 = Min [ c34, ( c31 + c14 )] = Min [7 , ( 2 +  )] = 7

d34 = no cambia

c35 = Min [ c35, ( c31 + c15 )] = Min [6 , (2 +  )] = 6

d35 = no cambia

c36 = Min [ c36, ( c31 + c16 )] = Min [ , ( 2 +  )] = 

d36 = no cambia

c42 = Min [ c42, ( c41 + c12 )] = Min [ 2 , ( + 7 )] = 2

d42 = no cambia

c43 = Min [ c43, ( c41 + c13 )] = Min [ 7 , ( + 2 )] = 7

d43 = no cambia

c44 = Min [ c44, ( c41 + c14 )] = Min [  , ( +  )] = 

d44 = no cambia

c45 = Min [ c45, ( c41 + c15 )] = Min [ 3 , (  +  )] = 3

d45 = no cambia

c46 = Min [ c46, ( c41 + c16 )] = Min [1 , ( +  )] = 1

d46 = no cambia

c52 = Min [ c52, ( c51 + c12 )] = Min [ , (  + 7 )] = 

d52 = no cambia

c53 = Min [ c53, ( c51 + c13 )] = Min [ 6 , (  + 2 )] = 6

d53 = no cambia

c54 = Min [ c54, ( c51 + c14 )] = Min [3 , (  +  )] = 3

d54 = no cambia

c55 = Min [ c55, ( c51 + c15 )] = Min [ , (  +  )] = 

d55 = no cambia

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 254
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

c56 = Min [ c56, ( c51 + c16 )] = Min [5 , ( +  )] = 5

d56 = no cambia

c62 = Min [ c62, ( c61 + c12 )] = Min [7 , (  + 7 )] = 7

d62 = no cambia

c63 = Min [ c63, ( c61 + c13 )] = Min [ , (  + 2 )] = 

d63 = no cambia
c64 = Min [ c64, ( c61 + c14 )] = Min [1 , (  +  )] = 1
d64 = no cambia

c65 = Min [ c65, ( c61 + c15 )] = Min [5 , (  +  )] = 5

d65 = no cambia

c66 = Min [ c66, ( c61 + c16 )] = Min [ , ( +  )] = 

d66 = no cambia

Luego de aplicar el paso 2 del algoritmo, las matrices C y D quedan de la siguiente manera:

PASO 3.- Indica que debemos repetir el paso 2 pero elegir la fila 2 y columna 2 y recalcular las
matrices C y D para todo i,j distinto de 2, considerando:

Por razones de espacio y debido a que el procedimiento es análogo al anterior se omiten los cálculos
y sólo Se entregan las matrices C y D resultantes. A modo de ejercitación se recomienda realizar
los cálculos de la misma forma hecha con la fila 1 y la columna 1.

(Resultados)Para la Fila 2 y Columna 2

(Resultados)Para la Fila 3 y Columna 3

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 255
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

(Resultados)Para la Fila 4 y Columna 4

(Resultados)Para la Fila 5 y Columna 5

(Resultados)Para la Fila 6 y Columna 6

la distancia más corta entre los nodos 1 y 6 es 8.

Entonces la matriz D sirve para responder la pregunta de la ruta más corta entre los nodos 1 y 6.
Para ello se analiza el elemento d26 de tal forma que el predecesor de 6 es 4, el predecesor de 4 es 2,
el predecesor de 2 es 3 y por ultimo el predecesor de 3 es 1. Por lo tanto la ruta más corta entre 1 y 6
corresponde a 1 – 3 – 2 – 4 – 6, y tiene una distancia, como se dijo, es 8. Multiplicando por 100 sería
800 km

4. Para la siguiente red encontrar el flujo máximo del origen al destino, si el número junto al
arco(i,j) mas cercano al nodo representa la capacidad de flujo del nodo i al nodo j.

2 4

6
1 5
4
2
1 3
4 7
3
9
2 3
1 6
4

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera4 Roalcaba – Lic. Wilder Miñano León 256
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Aplicaremos paso a paso uno de los puntos del algoritmo descrito.

Iteración 1.
Introducir un flujo completo en la red, es decir encontrar una ruta del origen al destino con capacidad
positiva
1 4 3 1 5 4 7

Como el flujo posible es 1, debe descontarse en todos los arcos correspondientes. El arco saturado es (3, 5).

Iteración 2.
1 3 3 3 6 9 7

Flujo = 3, por lo que debe descontarse de los arcos (1, 3), (3, 6) y (6, 7). Arco saturado = (1, 3).

Iteración 3.
1 1 4 4 6 6(9-3) 7

Flujo = 1. Arco saturado (1, 4).

Iteración 4.

1 6 2 4 5 2 3 3 4 3(4-1) 6 5 7

Flujo = 2, arco saturado (5, 3).

Iteración 6.

1 4(6-2) 2 2(4-2) 5 3(4-1) 7

Flujo = 2, arco saturado (2,5).

Como se han saturado todos los arcos que llegan al nodo final el flujo completo de la red encontrado
corresponde al flujo máximo.
Lo anterior también ocurre si todos los arcos salen del nodo origen están saturados.
Al aplicar el método de las cadenas incrementales obtenemos:
2 4

6
1 5
4
2
1 3
4 7
3
9
2 3
1 6
4

Aplicando el INVOP

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 257
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 258
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

5. Aplicación del software INVOP para redes:

Tenemos el siguiente ejemplo: Hallar la ruta mas corta que une los nodos 1 al nodo 5:

15
2 4
100
50
20
1 10

30 5
60

SOLUCION

La ruta más corta sería N1 – N3 – N5, con un costo de 80 unidades.

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 259
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

EJERCICIOS PROPUESTOS

1. (Prawda)Supóngase el siguiente mapa de los ferrocarriles Nacionales de México, donde las vías son
de doble tráfico, es decir adireccionales. ¿Cuál es la ruta más rápida entre México y Veracruz?
Los tiempos están dados en horas.

1 2

2 1.5
4 5 3
4
2 8 9
2 0.5 2
2
6 7 1.4
3
México 1 15

3 4
4
1 Veracruz
1.6 14 3.5 23
3 2
10 21
4
13 17
3 22
1.3 3
2 4
2 2.7

11
1.5 12 18 19

2 3

20

2. Por medio del algoritmo de Busacker y Gowen, encuentre el flujo máximo a costo mínimo en la
siguiente red . los números en cada arco representan respectivamente la capacidad mínima, máxima y
el costo unitario.

(0,1,3) (0,4,9)
(0,2,6)

V (0,1,1) (0,1,1) (0,1,1) (0,2,1) V

S 2 4 6 t

(0,2,2) (0,2,2) (0,3,1)

(0,3,4)

3 5 7
(0,2,1) (0,3,3)
Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 260
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

3. Supóngase que una unidad móvil de la Distribuidora PRONAA cargada con cerca de 3000 Kilos de
unos 50 artículos de consumo popular (azúcar, aceite, menestras, sal, arroz, etc.) deben recorrer n
poblaciones rurales de menos de 2000 habitantes cada uno en los próximos n días (una población por
día). Todas las poblaciones están comunicadas entre sí por caminos vecinales, de terraceria o de mano
de obra, la distancia entre un poblado i y otro j es d ij . La unidad móvil sale de un poblado el primer
día de su recorrido, visita una población por día (sin repetir la visita a una población) y al n+1 día
regresa al punto de partida. Formule sin resolver , un modelo de redes que minimice el recorrido total
de la unidad móvil por todas esta n poblaciones. Recuerde que la población de partida debe ser la
misma al finalizar el recorrido de n días, que se visita una población diferente cada dia y que no se
visita más de uan vez una población.

4. Considere el siguiente sistema de distribución .

Bodega1 (2,4) Mercado1

2 4

(,0)
(2,3) (2,2)

Planta
1 6

(3,1)
(2,4)
(,0)
3 (2,2) 5

Bodega2 Mercado2

Asociado a cada arco Aij se tiene un par de números (uij,cij) donde uij es la capacidad máxima del arco
cij es el costo unitario de expansión del arco. Se desea que la producción de la planta se incremente en
10 unidades ¿ Cuál es la política de expansión y a que costo?.
Ahora considere que el presupuesto es de 14 unidades ¿cuál es la producción máxima que se puede
tener en ese sistema?.

5. En un pequeño aeropuerto que está creciendo, la compañía local piensa comprar un tractor nuevo para
mover los arcos que llevan y traen equipaje a los aviones. Dentro de tres años se instalará un nuevo
sistema mecanizado de transporte de equipaje, por lo que después no se necesitará el tractor. No
obstante tendrá una carga de trabajo pesada y los costos de operación y mantenimiento aumentarán
rápidamente con el tiempo y podría resultar rentable reemplazando en uno o dos años.

La siguiente tabla proporciona los costos netos totales asociados a la compra del tractor (precio de
compra - valor a cambio del tractor en uso más los costos de operación y mantención) al final del año
i y si se reemplaza al final del año j (en donde el momento presente es el año 0).

j
1 2 3
0 8 18 31
1 10 21
2 12

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 261
UNJBG / FACI - Escuela de Computación Matemática
Programación Matemática I 

El problema es determinar en que momento (si es que existe) debe reemplazarse el tractor para
minimizar el costo total durante los tres años.
a) Formule este problema como un problema de la ruta más corta.
b) Utilice un algoritmo para resolver este problema de la ruta más corta.

6. Encontrar la ruta más corta a través de la red, en donde los números representan las distancias reales
entre los nodos correspondientes.

A
7
4
1 D
5 6

O B
6 T
4
8
2
5 E
1

Mgr. Manuel Alvarado Contreras – Lic. Ramón Vera Roalcaba – Lic. Wilder Miñano León 262