FLUJO MÁXIMO

• Principio conservacíón de flujo

• Algoritmo de Ford Fulkerson
• Teorema de Mínimo Corte de flujo máximo
• Flujo Máximo a Costo Mínimo

 Docente : Dr. Raúl Rengifo Lozano

 Materia : Investigación Operativa II

 Integrantes :

• Sarmiento Prada Carla Silvana 18170260

• Rodriguez Carhuamanta Bryan Gerard 18170054
• Mucha Mallaupoma Alves Brolin 18170042
• García Mogollón, Joaquín Eduardo Nícolas 18170168
Principio de conservación de Flujo

Definición
Una red N es un digrafo D con dos vértices destacados s (fuente), y t (sumidero) , con una función
capacidad c, asociada a los arcos, que toma valores enteros no negativos.

Consideraciones

Un flujo f en N es una función entera

Restricción de capacidad.

Principio de Conservación.

Flujo neto de Salida y entrada.

 Principio de conservación de Flujo
Principio de Conservación
Consideraciones

Restricción de
Capacidad
• el flujo nunca
excede a la
capacidad

Flujo neto de Entrada

Flujo neto de Salida
Principio de conservación de Flujo
Flujo en un arco a =(x , y) es denotado
por
f(a)= f(x , y)

Puede ser interpretado cómo la

cantidad de material (personas
,coches , etc) transportado a lo largo del
arco (x , y).

El Principio de Establece que si y

Conservación de
Flujo considera :
Entonces su Flujo Neto de entrada y
Flujo Neto de Salida son ambos Igual
a cero, por tanto se cumple el
Principio establecido.
Principio de conservación de Flujo
Representación Matemática

Un flujo en (G,c) es una función f: que satisface:

Uij (Xij)
f(x, y) + f(y, x) = 0 ; f(x, y) ≤ c(x, y) ∀x, y ∈ V

Cij Un flujo de s a s´ , con s, s´ ∈ V , es un flujo tal que:

x y
Una demanda se dice factible si existe un flujo f
[bi] [bj] satisfaciendo.
Principio de conservación de Flujo
Ejercicio de aplicación
Encontrar el número máximo de viajes que
se pueden hacer desde el Origen O, hasta (-22)

el destino T. Cada nodo muestra el máximo 30$5 4

número de viajes que se pueden hacer 2
entre nodos (32) 25$15 20$10
Infinit
Infinit o$14 6
1 o$5
12$4
12$11
3 5
Infinito$5 (-10)
Principio de conservación de Flujo
Ejercicio de aplicación
Encontrando la solución, aplicando el algoritmo.

(-22)
20
30$5 4 En la ruta O-B-E-T = 7 – 5 - 6 = 5
20 2
(32) 25$15 20$10
Infinit
Infinito$5 o$14 6
1
12$4 2
12$11
12 3 5
Infinito$5 (-10)

10
 Principio de conservación de Flujo
Ejercicio de aplicación

En la ruta O-A-D-T = 5 – 3 – 6 = 3

Infinit
o$5
12$4
12$11
3 5
Infinito$5
Principio de conservación de Flujo
Ejercicio de aplicación En la ruta O-B-D-T = 2 – 4 – 3 = 2
En la ruta O-A-B-D-T = 2 – 1 – 2 – 1 = 1
Principio de conservación de Flujo
Ejercicio de aplicación
En la ruta O-C-E-T = 4 – 4 – 1 = 1
Principio de conservación de Flujo
Resultado
Solución Óptima del problema Flujo Máximo = 12
ALGORITMO DE FORD FULKERSON
PSEUDOCÓDIGO
HISTORIA
El algoritmo de Ford-Fulkerson, data de 1956 y
se trata del primer algoritmo propuesto para
resolver el problema de flujo máximo, basado
en el concepto de grafo residual.
Fue en 1962 cuando Ford y Fulkerson
establecieron el teorema de flujo máximo-corte
mínimo y resolvieron el problema de flujo
máximo a través de algoritmos de caminos
incrementales. Se trata de un método genérico
que aumenta la capacidad de los flujos
incrementalmente a lo largo de los caminos
que van del origen al destino y que sirve como
OBJETIVO
la base de una serie de algoritmos que van  Buscar caminos en los que se
más allá de encontrar el flujo máximo. pueda aumentar el flujo, hasta
. alcanzar el flujo máximo.

 La idea es encontrar una ruta de

penetración con un flujo positivo
neto que una los nodos origen y
destino.
ALGORITMO DE FORD FULKERSON
110
130 A
CONSIDERACIONES 220
Se considera como capacidad inicial el arco que une el R1 D T
nodo i y el nodo j como Cij y Cji. 90
Esta capacidad inicial irá variando a medida que avanza el
B 130
algoritmo, denominaremos capacidades residuales a las
capacidades restantes del arco una vez pasa algún flujo por
110
él.
130 A
220
1) Identificar los nodos origen y destino. R1 D T
2) Identificar la capacidad mas alta que sale del nodo 90
origen.
B 130
3) Identificar el nodo intermediario con [af,i].
K= 110
Repetir paso 3, como si el nodo intermediario fuera el nodo
origen. 0
Actualizar los flujos: Cij, Cji= (Ci–k, Cj+ k) 20 A
donde: 110
R1 D T
C = Capacidad
90
i , j = índices de los nodos B 130
K= flujo mínimo del camino seleccionado K= 90
Retornar al paso 2 si al menos hay una salida de flujo del
nodo fuente. FLUJO MÁXIMO
La suma de los K corresponde al Flujo Máximo
110 + 90 = 200
ALGORITMO DE FORD FULKERSON
SISTEMA DE ACUEDUCTOS

La Mina Oro Verde, tiene un sistema de acueductos

para alimentar de agua a diferentes puntos de los 110
socavones. Para esto cuenta con tres reservorios R1,
A
130 D 220
R2 y R3. R1 85
Los socavones de la mina, tiene tres niveles 115
terminados y un cuarto en construcción. En el
segundo nivel, se encuentras los puntos de consumo 70 130
330
de agua, identificados como A, B y C, en el tercer 90
B 90
E T
nivel se encuentran los puntos de consumo D, E y F, R2
en el cuarto nivel se encuentra el punto T, que es el 110 85
lugar de expansión de la mina y que actualmente
requiere de la mayor cantidad posible de agua, para 140
iniciar las excavaciones. Para este proceso, es R3 130
F
240
necesario que los puntos de consumo, no consuman 120
el agua y por el contrario utilicen bombas de agua, C 160
para bombear el agua hasta el punto T. En la imagen
se aprecia la red de acueductos. Los valores indican
la cantidad de agua en miles de m3 por día que
soporta cada acueducto, entre los puntos de
consumo, los reservorios y el punto T.
ALGORITMO DE FORD FULKERSON
Iteration 1

110
TRAMO Cantidad Cantidad
A de Flujo de Flujo
130 D 220
R1 85 al inicio al final
115
R3 – B 140 10
70 130
90 90
330
T B–D 130 0
R2 B E
110
D-T 220 90
85

140
R3 130
F
240
120 Mínimo = 130
C 160
ALGORITMO DE FORD FULKERSON
Iteration 2

110
TRAMO Cantidad Cantidad
A de Flujo de Flujo
130 D 90
R1 85 al inicio al final
115
R2 – C 110 0
70 0
90 90
330
T C–E 130 20
R2 B E
110
E–T 330 220
85

10
R3 130
F
240
120 Mínimo = 110
C 160
ALGORITMO DE FORD FULKERSON
Iteration 3

110
TRAMO Cantidad Cantidad
A de Flujo de Flujo
130 D 90
R1 85 al inicio al final
115
R3 – C 120 0
70 0
90 90
220
T C–F 160 40
R2 B E
0 F-T 240 120
85

10
R3 20
F
240
120 Mínimo = 120
C 160
ALGORITMO DE FORD FULKERSON
Iteration 4

110
TRAMO Cantidad Cantidad
A de Flujo de Flujo
130 D 90
R1 85 al inicio al final
115
R1 – A 130 40
70 0
90 90
220
T A–D 110 20
R2 B E
0 D-T 90 0
85

10
R3 20
F
120
0 Mínimo = 90
C 40
ALGORITMO DE FORD FULKERSON
Iteration 5

20
TRAMO Cantidad Cantidad
A de Flujo de Flujo
40 D 0
R1 85 al inicio al final
115
R1 – B 115 25
70 0
90 90
220
T B–E 90 0
R2 B E
0 E-T 220 130
85

10
R3 20
F
120
0 Mínimo = 90
C 40
ALGORITMO DE FORD FULKERSON
Iteration 6

20
TRAMO Cantidad Cantidad
A de Flujo de Flujo
40 D 0
R1 85 al inicio al final
25
R2 – A 70 0
70 0
90 0
130
T A–E 85 15
R2 B E
0 E-T 130 60
85

10
R3 20
F
120
0 Mínimo = 70
C 40
ALGORITMO DE FORD FULKERSON
Iteration 7

20
TRAMO Cantidad Cantidad
A de Flujo de Flujo
40 D 0
R1 15 al inicio al final
25
R2 – B 90 5
0 0
90 0
60
T B–F 85 0
R2 B E
0 F-T 120 35
85

10
R3 20
F
120
0 Mínimo = 85
C 40
ALGORITMO DE FORD FULKERSON
Iteration 8

20
TRAMO Cantidad Cantidad
A de Flujo de Flujo
40 D 0
R1 15 al inicio al final
25
R1 – A 40 25
0 0
5 0
60
T A–E 15 0
R2 B E
0
0 E-T 60 45

10
R3 20
F
35
0 Mínimo = 15
C 40
ALGORITMO DE FORD FULKERSON
RESULTADO FINAL FLUJO ACUMULADO
R3-B-D-T 130
R2-C-E-T 110
20
A
25 0 D 0 R3-C-F-T 120
R1
25
R1-A-D-T 90
R1-B-E-T 90
0 0 45
5
B 0
E T R2-A-E-T 70
R2
0
0
R2-B-F-T 85
10 R1-A-E-T 15
R3 20
F
35
TOTAL 710
0
C 40

Por lo tanto, la cantidad máxima de agua

No existe más caminos que puede llegar a la expansión de la
mina ( punto T) es 710 000 m3 por día.
ALGORITMO DE FORD FULKERSON
CON SOFTWARE LINGO

110
130 A
R1 D 220
85
115

70 130
90 330
R2 B
90
E T
110
85
140
R3 130 240
120 F
C
160
ALGORITMO DE FORD FULKERSON
CORROBORACIÓN

Por lo tanto, la cantidad máxima de agua

que puede llegar a la expansión de la
mina ( punto T) es 710 000 m3 por día.
Teorema de mínimo corte de flujo máximo
DEFINICIO
NES

Serie de arcos cuya supresión de la red

causa un interrupción completa del flujo
Flujo del corte: entre los nodos de la fuente al sumidero. Capacidad del corte:

Suma de flujos de los Suma de capacidades de

arcos asociados. los arcos asociados.

En todo diagrama de flujo máximo existe un corte tal que el flujo de la red es igual a la
capacidad del corte generado.
 Teorema de mínimo corte de flujo máximo
Ejercicio de aplicación
Se desea implementar gasolinerías entre la
ciudad S y T de tal manera que cualquier
viaje realizado entre ambos puntos A (8,0)
encuentre por lo menos una, ¿dónde la
ubicaríamos y cuál sería el costo mínimo? (4,0) (2,0)
Entiéndase las capacidades de cada arco
como lo que costaría implementar una
(6,0) (3,0)
gasolinera en cada carretera en miles de S
B T
soles.

(7,0) (5,0)

C (4,0)
Teorema de mínimo corte de flujo máximo
Ejercicio de aplicación

A (8,6)
Conclusión:
(4,4) (2,2)
Estableciendo gasolinerías en las
carreteras SA – AB – BT – CT
(6,5) (3,3)
S estarán implementadas en todo viaje
B T
desde la ciudad A a la ciudad B y será
bajó el costo de 13 mil soles.
(7,4) (5,0)

C (4,4)
FLUJO MÁXIMO A COSTO MÍNIMO

Objetivo
Es minimizar el costo total de enviar el suministro disponible a través de la red para satisfacer la
demanda dada. (Un objetivo alternativo es maximizar la ganancia o utilidades total del envío.)

Consideraciones

La red es una red dirigida y conexa.

Al menos uno de los nodos es un nodo fuente.

Al menos uno de los nodos es un nodo demanda.

El resto de los nodos son nodos de trasbordo.

 FLUJO MÁXIMO A COSTO MÍNIMO
Consideraciones
Se permite el flujo a través La red tiene suficientes Cualquier nodo puede El costo del flujo a
de un arco sólo en la arcos como suficiente actuar como fuente o través del arco es
dirección indicada por la capacidad para permitir pozo, es decir cualquier proporcional a la
flecha, donde la cantidad que todos lo flujos nodo puede ser punto de cantidad de ese flujo,
máxima de flujo está dada generados por los nodos oferta (fuente) o punto de donde se conoce el
por la capacidad del arco. fuente lleguen a los nodos demanda (pozo). costo por unidad.
(Si el flujo puede ocurrir en demanda.
ambas direcciones, debe
representarse por un par
de arcos con direcciones
opuestas.)
Capacida
de Costo por
máxima unidad
del arco transportada
FLUJO MÁXIMO A COSTO MÍNIMO
Representación de la red

Xij: Es el número de unidades de flujo enviado del nodo i al nodo j.

Cij: Costo de transportar 1 unidad de producto del nodo i al nodo j.
(Xij) Uij: Capacidad máxima del arco (i, j).
bij: Flujo neto en el nodo i ( salida – entrada )
Uij (Cij) bi > 0 Si el nodo i es un punto de oferta.
bi < 0 Si el nodo i es un punto de demanda. .
bi = 0 Si el nodo i es un punto de transbordo.
i j Condición: En una red de costo mínimo una condición necesaria
para que tenga solución factible es:
[bi] [bj]
∑ bi = 0 ( oferta = demanda )
FLUJO MÁXIMO A COSTO MÍNIMO
Formulación de un PL para una red

Función objetivo Min Z = ∑ C i j . X i j

(Xij)
Restricciones Uij (Cij)
Para todo nodo i Para la oferta y la demanda

i j
Capacidad máxima del arco (i, j).
[bi] [bj]
Xij ≤ Uij
Xij ≥ 0
FLUJO MÁXIMO A COSTO MÍNIMO
Ejercicio de aplicación
Determinar el flujo máximo a mínimo costo
en la siguiente red. [-22]

Una fábrica desea distribuir 32 productos 30$5 4

en total a dos almacenes A(Nodo 4) y 2
B(Nodo 5) que demandan ciertas [32] 25$15 20$10
cantidades, en el recorrido hacen paradas Infinito$14
6
en centros de distribución(Nodo 2 y 3). Se 1 Infinito$5

desea determinar el recorrido más óptimo

12$4
donde se puede transportar la mayor 12$11
3 5
cantidad de productos tanto de la fábrica a Infinito$5 [-10]
los centros de distribución, como de estos
últimos a los almacenes y a la vez
minimizando los costos de estos recorridos
FLUJO MÁXIMO A COSTO MÍNIMO
Ejercicio de aplicación: Planteamiento
FO

Min Z= 15X12+ 11X13 + 5X23 + 5X24 + 10X25 + 4X34 + 5X35 + 14X54 + 0X46 + 0X56

Restricciones:
[-22]
Nodo 1
X12 +X13=32 Con respecto a la
30$5 4
Nodo 2 capacidad de arco 2
X23+X25+X24=X12 X12 <=25 [32] 25$15 20$10
Nodo 3 X13 <=12 Infinito$14
X34+X35=X13+X23 X24 <=30
6
1 Infinito$5
Nodo 4 X23 no tiene restricción
12$4
-X24 - X34 - X54 = -22 X34 <=12 12$11
Nodo 5 X35 no tiene restricción
3 5
Infinito$5 [-10]
-X35 -X25 = -10 X25 <=20
Nodo 6 X54 no tiene restricción
X56+X46=32
FLUJO MÁXIMO A COSTO MÍNIMO
Ejercicio de aplicación: Resolución

X24=20 [-22]
30$5 4
X12=20 Costo total: 20x$15 +
2
12x$11 + 2x$4 + 20x$5 +
[32] 25$15 20$10
X34=2
5x$10 = $ 590
Infinito$14
6
1 Infinito$5

12$11
12$4 $ 590 sería el costo mínimo
3 5 que tendría que gastar la
X13=12 Infinito$5 [-10] empresa para transportar los
X35=10 32 productos de la fábrica a
los centros de distribución y
de estos a los almacenes.
FLUJO MÁXIMO A COSTO MÍNIMO
Ejercicio de aplicación: [-22]
30$5 4
En Lingo 2
[32] 25$15 20$10
Determinar el flujo máximo Infinito$14
a mínimo costo en la 6
1 Infinito$5
siguiente red.
12$4
12$11
3 5
Infinito$5 [-10]
FLUJO MÁXIMO A COSTO MÍNIMO
(-22)
Resultado en Lingo 4
30$5
2
(32) 25$15 20$10
Determinar el flujo máximo Infinit
Infinit o$14 7
a mínimo costo en la 1 o$5
siguiente red. 12$4
12$11
3 5
Infinito$5 (-10)
FLUJO MÁXIMO A COSTO MÍNIMO

Ejercicio de aplicación en Storm

!!!Gracias¡¡¡