INFO 279 – Métodos de Optimización – Segundo semestre de 2017

Apunte 04:

Redes de optimización

Mauricio Ruiz-Tagle Molina

Instituto de Informática
Facultad de Ciencias de la Ingeniería
Universidad Austral de Chile
(Basado en apuntes de clases de la prof.
Miguelina Vega Rosales)
1.Problema de transporte

•Conceptos fundamentales.

•Problema Flujo Máximo.

•Problema de Costo Mínimo.

•Problema Flujo Máximo a Costo Mínimo.

•Problema de Transporte como Red de

Optimización.
Redes de Optimización
Existen problemas cuya representación por medio de una red es muy
fácil, en cambio expresarlo como PL es más complicado. Por esta
razón se han creado algoritmos para resolver problemas con esta
estructura.
Veremos tres tipos de problemas que son: Flujo máximo, Costo
mínimo y Flujo máximo a costo mínimo.
Conceptos fundamentales.
• Red: Es un conjunto de nodos, vértices o puntos, conectados por un
conjunto de arcos, líneas o ramas. Estos arcos pueden tener o no
dirección.
Ni se denota al Nodo i
Aij se denota al arco que une nodo i con el nodo j

• Camino Ni a Nk: es una serie de nodos y arcos que une nodo i con el
nodo k.
• Ciclo: es una cadena que empieza y termina en el mismo nodo.
• Camino simple: es aquel camino que no contiene ciclos.
 Redes de Optimización

• Red conexa: es aquella donde existe por lo menos un camino que

conecta a cada nodo con el resto de los nodos de la red.
• Red Inconexa: Es una red que no está conectada.
• Arbol: es una red conexa que no contiene ciclos.
Ejemplos:
4
4
1 3
1 3 3

2
2 1 2
N1-N2-N3-N1 ciclo
N1-N2-N3 y N4 camino simple
Red inconexa N1-N2-N3 y N, no árbol
N1-N3 y N4 camino simple
Camino simple
Red conexa
Red conexa
Redes de Optimización
• cij: costo por unidad de flujo que pasa de i a j
• Xij: de flujo que va de i a j.
• uij: capacidad máxima arco ij
• lij: capacidad mínima arco ij
En cualquier red distinguiremos el Nodo inicial u origen (No) y el Nodo final o
destino (Nf). Solamente ingresa flujo a la red por el nodo origen y sale el flujo
de la red por el nodo final. Además se deben cumplir las restricciones de
capacidad de los arcos.

Matemáticamente, para cada nodo Nj se tiene:

x
k
jk  v j=o flujo entra No

x x
i
ij
k
jk 0 j  o y j  f conserva flujo

x
k
kj v j=f flujo sale por Nf

0  lij  xkj  uij  ij capacidad arcos

1. Problema de Flujo Máximo
Max v   xij
i j
sujeto a:

x k
jk  v j=o

x x
i
ij
k
jk 0 jo y jf

x k
kj v j=f

0  lij  xkj  uij  ij

Este problema tiene tantas restricciones como nodos y arcos tenga la red. De sus variables, sólo
algunas son  0, lo que hace que solución PL no sea eficiente. Por esta razón, veremos el
algoritmo de las etiquetas.
Definición:
Corte de una red, es un conjunto de arcos cuya ausencia desconecta el nodo inicial con el
nodo final de una red.
Teorema: En cualquier red, el tamaño del corte mínimo corresponde al flujo máximo que puede
circular por esa red.
 1. Problema de Flujo Máximo
Corte = 8 Corte = 11 Corte = 8
5
2 4 5
3
2
1 4 6
5 2 3
3 2 5

Corte = 12 Corte = 11
5
2 4 5
3
2
1 4 6
5 2 3
3 2 5
Corte = 9
Corte = 7
5
2 4 5
3
2
1 4 6
5 2 3
3 2 5
 1. Problema de Flujo Máximo – Algoritmo de Etiquetas
Fase 1: Un nodo puede estar en uno de los siguientes estados mutuamente
excluyente:
• Con etiqueta y registrado (él y sus vecinos etiquetados)
• Con etiqueta sin registro (él y no todos sus vecinos etiquetados)
• Sin etiqueta (cuando no tiene etiqueta)
Al inicio todos los nodos están sin etiquetas.
Se comienza etiquetando el No con [0; ], y a todos sus vecinos Nj con [o; j],
donde j es la capacidad del arco Aoj.
A todos los nodos vecinos Nk de Nj que no tengan etiqueta, se les asigna la
etiqueta [j, k], donde k es el mínimo entre donde j y la capacidad del arco
Ajk.
A todos los nodos vecinos Nk de Nj que no tengan etiqueta y para los cuales sea
posible devolver flujo, se les asigna la etiqueta [j-, k], donde k es el mínimo
entre j y Xjk.
Como todos los nodos vecinos Nk de Nj han sido investigados, Nj pasa a ser
etiquetado y registrado. Se repite este proceso hasta llegar a Nf.
 1. Problema de Flujo Máximo – Algoritmo de Etiquetas
Fase 1: Un nodo puede estar en uno de los siguientes estados mutuamente
excluyente:
• Con etiqueta y registrado (él y sus vecinos etiquetados)
• Con etiqueta sin registro (él y no todos sus vecinos etiquetados)
• Sin etiqueta (cuando no tiene etiqueta)
Al inicio todos los nodos están sin etiquetas.
Se comienza etiquetando el No con [0; ], y a todos sus vecinos Nj con [o; j],
donde j es la capacidad del arco Aoj.
A todos los nodos vecinos Nk de Nj que no tengan etiqueta, se les asigna la
etiqueta [j, k], donde k es el mínimo entre donde j y la capacidad del arco
Ajk.
A todos los nodos vecinos Nk de Nj que no tengan etiqueta y para los cuales sea
posible devolver flujo, se les asigna la etiqueta [j-, k], donde k es el mínimo
entre j y Xjk.
Como todos los nodos vecinos Nk de Nj han sido investigados, Nj pasa a ser
etiquetado y registrado. Se repite este proceso hasta llegar a Nf.
1. Problema de Flujo Máximo – Algoritmo de Etiquetas
Algoritmo etiquetas (continuación):
Si el nodo final de la red, no puede ser etiquetado, el flujo actual de la red no
cambia y por consiguiente es el flujo máximo.
En caso que el Nf tenga etiqueta, el flujo actual cambia de acuerdo a lo
siguiente:
Fase 2 (modificación del flujo):
Si el Nf tiene la etiqueta [k; f] , modifíquese el flujo de Njk por Xjk+ j y pase al
nodo Nj.
Si el Nk tiene la etiqueta [j-; k] , modifíquese el flujo de Nkj por Xkj- k y pase
al nodo Nj.
Continúe de esta manera hasta llegar al No y regrese a la Fase 1. En esta
iteración se han introducido f unidades de nuevo flujo.
Ejemplo: Determine flujo máximo
en la siguiente red: 2 5 4 5
3
2
1 4 6
5 2 3
2
3 5
1. Problema de Flujo Máximo – Algoritmo de Etiquetas
1a Iteración
Fase 1: etiquetado de nodos
[1;3] [3;4]
2 5 4
[1;] 5
3
2
1 4 6
5 2 3
2 [4;4]
3 5
[1;5] [3;2]
Fase 2: Ajuste del flujo
[1;3] [3;4]
2 5 4 5 1
[1;]
3
2 4 0
1 6
5 1 2 3
2 [4;4]
3 5
[1;5] [3;2]

Flujo de la iteración 1: V1= 4

1. Problema de Flujo Máximo – Algoritmo de Etiquetas
2a Iteración [1;3] [2;3]
2 5 4
[1;] 1
3
2
1 0 6 [1;3] [2;3]
1 2 3
2 [5;2] 5
3 5 [1;] 3 1 2 4 1
[2;2] [3;2] 2 0
1 0 6
1 2 3 1
2 0 [5;2]
Flujo de la iteración 2: V2= 2 3 5
[2;2] [3;2]
3a Iteración [1;1] [2;1]
2 5 4
[1;] 1 1
0
1 0 6 [1;1] [2;1]
1 2 1
0 [4;1] 2 5 4 4
3 5 [1;] 1 0 1 0
[1;1] [- ; -] 0
1 0 6
1 2 1
0 [4;1]
3 5
Flujo de la iteración 3: V3= 1 [1;1] [- ; -]
1. Problema de Flujo Máximo – Algoritmo de Etiquetas

4
[1;] 0 2 4 0 No se llega a Vf . Termina la ejecución del algoritmo.
0
1 0 6
1 2 1
0
3 5
[1;1]

Flujo total: V=V1 + V2 + V3 = 4 + 2 + 1 = 7

Ejercicio: Determine flujo máximo en la siguiente red y encuentre el corte mínimo:

2 4
2
2 4
1
4 3
3
1. Problema de Flujo Máximo – Algoritmo de Etiquetas

Formulación PL:
Max v=X12+X13=X24+X34
SA: X12+X13-v=0 (Nodo 1)
X12-X23-X24=0 (Nodo 2)
X13+X23-X34=0 (Nodo 3)
X24+X34-v=0 (Nodo 4)
2 4
X12 ≤ 2 2
X13 ≤ 4 2 4
1
X23 ≤ 2 4 3
X24 ≤ 4 3
X34 ≤ 3
Xij0
1. Problema de Flujo Máximo – Algoritmo de Etiquetas
Ejercicio: Determine en la siguiente red:
4
• Flujo máximo 18 68
35 2 35
48
• Corte mínimo 22 7 46
1 37
47 32 5 8
• Formulación PL
3 20 34
41
6
 2. Problema de Costo Mínimo
Min Z   cij  xij
i j
sujeto a:
 1 jo

i ij k jk  0
x  x  jo y j f
 1 j f

xij  0 ;1

Este problema tiene tantas restricciones como nodos y arcos tenga la red. De sus
variables, sólo algunas son 1, lo que hace que solución PL-entera no sea eficiente por
lo que utilizaremos el algoritmo de Dijkstra:
Se considera que los arcos de una red pueden pertenecer a sólo uno de los siguientes
conjuntos mutuamente excluyentes:
•El arco pertenece a un árbol
•El arco no pertenece a un árbol.

Al principio los arcos no pertenecen al árbol. En cada iteración el algoritmo incrementa

en 1 el número de arcos, hasta llegar a n-1 arcos, donde n es el número de nodos de la
red. Cuando el árbol tiene n-1 arcos, el algoritmo termina.
2. Problema de Costo Mínimo – Algoritmo de Dijkstra

 Paso 1: Sea No el nodo origen, entonces L´ok=cok Aok que esté

definido en la red. No pasa a ser elemento del árbol. Se define Loo=0
 Paso 2: Sea Lor=Mink{L´ok} = Lor=Mink{Loj+cjk}, donde Nk son todos los
vecinos a los nodos del árbol. (L indica costo permanente y L´ un
costo temporal)
 Paso 3: El arco Ajr pasa a ser elemento del árbol. Se etiqueta el nodo
Nr con [Lor,Nj], 1º elemento indica el costo y el 2º el nodo origen)
 Paso 4: Si el árbol tiene n-1 arcos, la solución óptima se ha
encontrado y se detiene el algoritmo. En caso contrario, ir a 5.
 Paso 5: Sea L´ok=Mink[L´ok;Lor+crk], para todos los nodos Nk vecinos a
los nodos del árbol, regresar a 2.
Cuando un costo no está definido, se considera .

Ejemplo: Determine costo mínimo 5

en la siguiente red: 2 4 5
3
2
1 4 6
5 2 3
2
3 5
2. Problema de Costo Mínimo – Algoritmo de Dijkstra
Primera iteración: [3;1]
N1 árbol , sus vecinos son: N2, N3 2 5 4 5
L´12= 3 ; L´13= 5 [0;1] 3
2
⇒ L1r = Min {3,5}=3 ⇒ r =2 1 4 6
5 2 3
N2=[3,1] ; A12 árbol 3
2
5

Segunda iteración: [3;1]

N1, N2 árbol, sus vecinos son: N3, N4 2 5 4 5
L´13 =Min{5,5}=5 ; L´14= Min{ ,8}=8 [0;1] 3
2
⇒ L1r= Min {5,8}=5 1 4 6
5 2 3
⇒ r=3 y N3=[5,1] 3
2
5
hay 2 arcos en el árbol [5;1]

Tercera iteración: [3;1]

N1, N2,N3  árbol, sus vecinos son: N4, N5 2 5 4 5
L´14 =Min{8,9}=8 ; L´15= Min {,7}=7 [0;1] 3
2
⇒ L1r= Min {7,8}=7 1 4 6
5 2 3
⇒ r=5 y N5=[7,3] 3
2
5
hay 3 arcos en el árbol [5;1] [7;3]
2. Problema de Costo Mínimo – Algoritmo de Dijkstra
[3;1] [8;2]
Cuarta iteración: 5
N1,N2,N3,N5 árbol, sus vecinos son: N4, N6 2 4 5
[0;1] 3
L´14 =Min{8,9}=8 ; L´16= Min{ ,10}=10 1
2
6
⇒ L1r= Min {10,8}=8 5 4 2 3
⇒ r=4 y N4=[8,2] 2
3 5
hay 4 arcos en el árbol [5;1] [7;3]

Quinta iteración: [3;1] [8;2]

Vecinos al árbol son: N6 2 5 4 5
L´16 =Min{13,10}=10 ⇒ L1r= 10 [0;1] 3
2 [10;5]
⇒ r=6 y N6=[10,5] 1 4 6
5 2 3
hay 5 arcos en el árbol 2
3 5
[5;1] [7;3]
La ruta de costo mínimo es: N1-N3-N5 -N6
y el costo mínimo es 10.
2. Problema de Costo Mínimo – Algoritmo de Dijkstra

Formulación PL:
Min Z= 3X12+5X13+2X23+5X24+4X34+2X35+ 2X45+ 5X46+3X56
SA: X12+X13=1 (Nodo 1)
X12-X23-X24=0 (Nodo 2)
2 5 4 5
X13+X23-X34-X35=0 (Nodo 3) 3
2
1 4 6
X24+X34-X45-X46=0 (Nodo 4) 5 2 3
2
X35-X54-X56=0 (Nodo 5) 3 5

X46+X56=1 (Nodo 6)
Xij=0;1
2. Problema de Costo Mínimo – Algoritmo de Dijkstra
Ejercicio: Determine en la siguiente red:
4 68
• Ruta de costo mínimo 18
35 2 48 35 7 46
• Formulación PL 22
1 47 37 8
32 5
3 34
20
41
6
 3. Problema de Flujo Máximo a Costo Mínimo
Min Z   cij  xij
i j
sujeto a:  v jo

i ij k jk  0
x  x  jo y j f
 v j f

0  lij  xkj  uij i, j
xij  0 ;1
En este caso se aplica el algoritmo de Busacker Gowen:
• Paso 1: Sea v=0 y Xij=0,  Aij.
• Paso 2: Construya un nuevo costo Cij para el arco Aij basado en:
Cij=cij si 0 ≤ Xij ≤ uij (costo no cambia)
Cij= si Xij = uij (arco se satura)
Cij=-cij si Xij >0 (arco en reversa)
• Paso 3: Encuentre la ruta mas económica entre No y Nf, basado en los costos Cij .
Envíe por esa ruta la mayor cantidad de flujo permisible. Añada al flujo actual de la red este nuevo
flujo. Si todas las rutas que conducen a Nf están saturadas, la solución óptima se ha encontrado. De
otra forma volver al Paso 2.
3. Problema de Flujo Máximo a Costo Mínimo
(5,10)
2 4 (5,7)
Ejemplo: Determine el flujo máximo a (3,8)
costo mínimo de la siguiente red: (2,5) (4,8)
1 (2,8) 6
(1er elemento es el costo, 2° es el flujo):
(5,5) (2,5) (3,5)
3 5

1º Iteración: Primero determinamos la ruta de costo mínimo [3;1]

2 5 4
N1 árbol , sus vecinos son: N2, N3 5
[0;1] 3
L´12= 3 ; L´13= 5 2
1 4 6
⇒ L1r = Min {3,5}=3 ⇒ r =2 5 2 3
N2=[3,1] ; A12 árbol 2
3 5
N1, N2 árbol, sus vecinos son: N3, N4
L´13 =Min{5,5}=5 ; L´14= Min{ ,8}=8
⇒ L1r= Min {5,8}=5
⇒ r=3 y N3=[5,1]
hay 2 arcos en el árbol N1, N2,N3  árbol, sus vecinos son: N4, N5
L´14 =Min{8,9}=8 ; L´15= Min {,7}=7
⇒ L1r= Min {7,8}=7
⇒ r=5 y N5=[7,3]
hay 3 arcos en el árbol
 3. Problema de Flujo Máximo a Costo Mínimo
N1,N2,N3,N5 árbol, sus vecinos son: N4, N6 Vecinos al árbol son: N6
L´14 =Min{8,9}=8 ; L´16= Min{ ,10}=10 L´16 =Min{13,10}=10 ⇒ L1r= 10
⇒ L1r= Min {10,8}=8 ⇒ r=6 y N6=[10,5] , hay 5 arcos en el árbol
⇒ r=4 y N4=[8,2]
hay 4 arcos en el árbol
[3;1] [8;2]
(5,10)
(3,8) 2 4 (5,7)
[0;1] (4,8) [10;5]
1 (2,5) (2,8) 6
(5,5) (2,5) (3,5)
La ruta de costo mínimo es: A13-A35-A56 y 3 5
el costo mínimo es 10. [7;3]
[5;1]

En esta ruta pueden pasar 5 unidades de flujo (mínimo entre 5, 5 y 5)

(5,10) Por lo tanto en 1º iteración:

(3,8) 2 4 (5,7) flujo v1=5
(4,8) costo C1= 5*10 = 50
1 (2,5) (2,8) 6
(5,5) (2,5) (3,5)
3 5
Se modifican los costos para la segunda iteración:
3. Problema de Flujo Máximo a Costo Mínimo
(5,10)
Observación: No se marcan (3,8) 2 4 (5,7)
los arcos A31 y A65 con costo
(2,5) (4,8)
negativo pues nunca se van a 1 (2,8) 6
utilizar. (,5) (,5)
3 5 (,5)
(-2,5)
Segunda iteración: Primero determinamos la ruta de costo mínimo.
[3;1] [8;2] •N1 árbol , sus vecinos son: N2
5
2 4 5 [13;4] L´12= 3 ⇒ L1r=3 ⇒ r=2
[0;1] 3
2 y N2=[3,1] , A12  árbol
1 4 6
2
3 5 •N1, N2  árbol , sus vecinos son: N3, N4
[5;1] L´13 =Min{,5}=5 ; L´14= Min{ ,8}=8
-2 ⇒ L1r= Min {5,8}=5 , r=3 y N3=[5,2]
hay 2 arcos en el árbol

•N1, N2,N3  árbol , sus vecinos son: N4. L´14 =Min{8,9}=8 ⇒ L1r= 8 , r=4
y N5=[8,2] hay 3 arcos en el árbol
•N1, N2,N3,N4  árbol , sus vecinos son: N6. L´16 =Min{,13}=13 ⇒ L1r= 13, r=6
y N6=[13,4], hay 4 arcos en el árbol.
 3. Problema de Flujo Máximo a Costo Mínimo
La ruta de costo mínimo es: A12-A24-A46 y
(5,10) el costo mínimo es 13.
(3,8) 2 4 (5,7)

(2,5) (4,8) En esta ruta pueden pasar 7 unidades

1 (2,8) 6
(,5) de flujo (mínimo entre 8, 10 y 7)
(,5) 3 5 (,5)
(-2,5) Por lo tanto en 2° iteración:
flujo v2=7
Flujo total: v1 + v2 = 12
costo C2= 7*13 = 91
Costo total: C1 + C2 = 141
Se modifican los costos para la tercera iteración: (-5,7)
(5,10)
(3,8) 2 4 (5,7)
(5,3)
(3,1) 2 4 (,7)
1 (2,5) (4,8) (2,8) 6
(2,5) (4,8)
(,5) (,5) 1 (2,8) 6
3 5 (,5)
(,5) (,5)
(-2,5) 3 5 (,5)
(-2,5)

Como no hay camino hasta Nf, llegamos al óptimo, V*=12 a un costo de 141.
3. Problema de Flujo Máximo a Costo Mínimo
Formulación PL:
Min Z= 3X12 + 5X13 + 2X23 + 5X24 + 4X34 + 2X35 + 2X45 + 5X46 + 3X56
SA: X12+X13=v (Nodo 1)
X12-X23-X24=0 (Nodo 2)
(5,10)
(3,8) 2 4 (5,7)
X13+X23-X34-X35=0 (Nodo 3)
(2,5) (4,8)
X24+X34-X45-X46=0 (Nodo 4) 1 (2,8) 6
(5,5) (2,5) (3,5)
X35-X54-X56=0 (Nodo 5) 3 5
X46+X56=v (Nodo 6)
X12 ≤ 8; X46 ≤ 7
X13 ≤ 5 ; X56 ≤ 8
X23 ≤ 5 ; X54 ≤ 5
X24 ≤ 10; X34 ≤ 8
X35 ≤ 5
v = 10 (valor mayor o igual a la máxima capacidad de las aristas)
3. Problema de Flujo Máximo a Costo Mínimo
Ejercicio: Determine en la siguiente red el flujo máximo a costo mínimo (el primer elemento
de cada arco es el flujo y el segundo es el costo).

(3,1) 2 (3,1)
6 (10,1)
1 (2,1) 8
(2,1)
(7,2)
3 (5,3)
(2,2) 7
(5,4) 5 (8,2)
(5,2)
4
3. Problema de Transporte como Red de Optimización
Dado el siguiente problema transporte:

Formulación como red: Flujo máximo a costo mínimo.

(a1, c11)
1 1
(b1,0)
(a1,0) (a1, c11)

(a2,0) (b2,0)
o 2 2 f

(an,0)
(an, cn1)
(bm,0)

n (an, cnm) m
3. Problema de Transporte como Red de Optimización
Ejemplo: formule el siguiente problema de
transporte como red, la capacidad de
transporte es de 50 unidades.

Formulación como red: Flujo

máximo a costo mínimo.

(20,8)
1 1
(20,5)

(20,0) (40,0)

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

o (70,0) f
(40,0)

3 3 (80,0)
(70,0)

4 (70,2) 4