ESCUELA SUPERIOR

POLITÉCNICA DE CHIMBORAZO

FLUJO MÁXIMO
INTEGRANTES:
ERIKA AILLA
MARIBEL CABA
LISETH GUACHILEMA
DEBORA PILAMUNGA
ANGELICA PÉREZ
JENIFER SHIGUANGO

DOCENTE:
ING. WILLIAN YANZA

SEGUNDO “1”
18/1/2024
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

INTRODUCCIÓN

El concepto de "flujo máximo" se utiliza en teoría de redes y optimización. Se refiere a

la cantidad máxima de flujo que puede pasar a través de una red desde un origen hasta un
destino, respetando las capacidades de los diferentes arcos o caminos de la red.

El flujo máximo es un método aplicable para la optimización de rutas entre dos puntos de
importancia, esto es aplicable a oleoductos, redes eléctricas o de transmisión de datos, ya
que en dichas situaciones se debe determinar el flujo máximo que pasa a través de una
red, aspectos más cercanos es la repartición de recursos con el fin de maximizar la eficacia
en su uso, por ejemplo si tenemos ingenieros y su repartición en las tareas durante un mes,
el flujo máximo es uno de los métodos que se emplea dentro de la ingeniería industrial
haciendo uso de los dígrafos (grafos dirigidos).

Página 2 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

¿QUÉ ES EL FLUJO MÁXIMO?

Previamente a la definición del problema del flujo máximo, es importante puntualizar el

concepto de red o grafo, el cual es un conjunto de varios nodos (puntos en el espacio) y
arcos (líneas) que salen de un determinado nodo y van hacia otro. Los grafos pueden ser
dirigidos, cuando cada arco tiene un nodo origen y uno destino (es decir los arcos tienen
un sentido), o no dirigidos en caso contrario. ( Marín Gonzales , 2017)

Según (Fernandez Baca, 2013) el problema del flujo máximo consiste en calcular la
cantidad máxima de flujo que puede ser transportada de un punto de partida o fuente a
uno de llegada o sumidero. Entiéndase por flujo, una cantidad medible de materia que
puede circular por cualquiera de los arcos. Dicho flujo está sometido a las restricciones
de capacidad de cada arco, es decir, a la cantidad máxima de flujo que puede soportar
cada uno de los mismos.

Además, considera que el objetivo del problema del flujo máximo es determinar la
máxima cantidad de material u objetos que pueden fluir en el grafo desde la fuente hacia
el sumidero. En aplicaciones del mundo real, conocer el valor del flujo máximo permite
a la fuente saber exactamente cuánto producir y enviar a través de una ruta sin generar
desperdicios.

Las redes deflujo normalmente son usadas para modelar líquidos que fluyen a través de
tubos o la corriente eléctrica que se transmite a través de redes eléctricas, en definitiva,
simulan transferencias entre nodos de una red. Por esto, las aristas dirigidas de la red son
las encargadas de representar un intercambio de materiales o energía.

Aplicaciones del Flujo Máximo

Para (Alvarez Moreno, 2016) el problema del flujo máximo tiene numerosas aplicaciones
en el mundo real. Los algoritmos de flujo máximo se aplican a la vida cotidiana para
resolver problemas de gestión de recursos, reparto en empresas de logística, control de
vuelos con escalas en aerolíneas, gestión de selección de proyectos o para calcular las
intensidades máximas en un circuito eléctrico, entre otros.

Por ejemplo, en aerolíneas aplicando métodos de flujo máximo se pretende determinar la

máxima cantidad de conexiones de vuelos que se pueden alcanzar conectando dos
ciudades entre las que los aviones deben realizar escala en diferentes aeropuertos antes

Página 3 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

de llegar a su destino. Los aeropuertos intermedios tienen capacidades limitadas, por lo

que si están ocupados por otros aviones que realicen otras trayectorias no admiten nuevos
aviones que quieran hacer una escala. (Alvarez Moreno, 2016)

Página 4 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

FUNCIÓN DEL FLUJO MÁXIMO

La función del flujo máximo tiene varias aplicaciones prácticas, y algunas de sus
funciones principales son:

Diseño de Redes de Transporte: En el ámbito de la logística y el transporte, el problema

del flujo máximo se utiliza para diseñar eficientemente redes de transporte. Esto puede
aplicarse a la planificación de rutas para vehículos, la distribución de productos, o la
gestión de flujos en redes de comunicación.

Redes de Telecomunicaciones: En las redes de comunicación, el flujo máximo puede

modelar la cantidad máxima de datos que puede ser transmitida desde una fuente hasta
un destino a través de la red. Esto es fundamental para optimizar el rendimiento de las
redes de telecomunicaciones y garantizar una transmisión eficiente de datos.

Problemas de Asignación de Recursos: En situaciones donde hay recursos limitados

que deben asignarse de manera eficiente, el flujo máximo puede ayudar a encontrar la
distribución óptima de estos recursos. Por ejemplo, en la asignación de personal, la
distribución de energía, o la asignación de capacidad en una red de computadoras.

Transporte y Logística: El flujo máximo se utiliza en problemas de transporte y logística

para determinar la cantidad máxima de bienes que pueden ser transportados desde
proveedores hasta consumidores, teniendo en cuenta las restricciones de capacidad en los
diferentes segmentos de la cadena de suministro.

Flujo de Información: En el contexto de sistemas de información, el flujo máximo puede

modelar la cantidad máxima de información que puede ser transmitida entre diferentes
nodos de una red. Esto es esencial en la optimización de redes de información y en la
planificación de sistemas de comunicación.

Programación Lineal: El problema del flujo máximo se puede formular como un

problema de programación lineal y se resuelve utilizando algoritmos específicos, como
el algoritmo de Ford-Fulkerson. Estos algoritmos encuentran la asignación óptima de
flujo para maximizar la capacidad de la red.

En resumen, la función del flujo máximo es modelar y resolver problemas de

optimización relacionados con la transferencia de recursos, ya sea físicos (como bienes o

Página 5 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

materiales) o abstractos (como datos o información), a través de una red, garantizando

que se respeten las restricciones de capacidad de la red.

EJERCICIOS DE FLUJO MÁXIMO

➢ EJERCICIO 1
• Encuentra el flujo máximo del siguiente ejemplo:

• Primero identificamos la capacidad más alta que sale del nodo origen: en este caso
es el 30 Después se identifica la capacidad más alta del nodo con la etiqueta (aj,
i).

• Copiamos la misma red y vamos a poner la actualización de flujo que nos dio
arriba en los respectivos segmentos.

Página 6 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

• Se vuelve a copiar la red y se hace la actualización de los flujos de arriba en los

respectivos segmentos.

• Volvemos a hacer lo mismo y se actualizan los valores de flujo de la red anterior

en los respectivos segmentos que se utilizaron.

• Se vuelve a hacer el mismo procedimiento que arriba y se copia la red.

• Nos detenemos cuando ya no hay una ruta de avance, es decir del nodo 1 ya las
capacidades de flujo al resto de la red son de cero, por lo que esto sería lo último,
así que sacamos el valor de fujo máximo y
sumamos los valores de K de todas las redes
que hicimos anteriormente.
𝐹. 𝑀. = 𝛴𝐾′=20 +10 +10 +10 +10 F.M = 60

Página 7 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

PASOS PARA LA SOLUCIÓN DEL FLUJO MÁXIMO

1. Identificar el nodo origen y de destino.

2. Partiendo del nodo de origen se elige el arco que posea mayor flujo

3. Identificar los nodos de transbordo.

4. Repetir el proceso como si el nodo intermediario fuera el nodo origen.

5. Calcular 'k' y las nuevas capacidades.

6. Obtenido el resultado se cambian las capacidades y se repite idéntico procedimiento

desde el inicio.

El Flujo Máximo que puede pasar del nodo origen hasta el nodo destino es la suma de las
capacidades ∑k de la ruta.

Calcular el flujo máximo del grafo:

Página 8 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

➢ EJERCICIO 2

Determinar el flujo máximo en la red siguiente: Interacción 1:

PASOS:

Determinamos las residuales iniciales (cij,cji) iguales a las capacidades iniciales (Cij,Cji).

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Paso 2: S1= {2,3,4} (no vacío).

Paso 3: k = 3 ya que c13 = Max {c12, c13, c14} = {20,30,10} = 30. Hacemos a3=c13=30
y clasificamos el nodo 3 con [30,1]. Tomamos i=3 y repetimos el paso 2.

Paso 2: S3= {4,5}

Paso 3: k = 5 y a5 = c35 = Max {10,20} = 20. Clasificamos el nodo 5 con [20,3].

Logramos la penetración, vamos al paso 5.

Paso 5: La ruta de la penetración se determina de las clasificaciones empezando en el

nodo 5 y terminando en el nodo 1, es decir, 5→ [20,3]→3→ [30,1]→1.

Entonces la ruta es N1= {1,3,5} y f1=min {a1, a3, a5} = {∞,30,20} = 20. Las capacidades
residuales a lo largo de esta ruta son:

(c13, c31) = (30-20, 0+20) = (10,20)

(c35, c53) = (20-20, 0+20) = (0,20)

Página 9 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

Interacción 2:

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Paso 2: S1= {2,3,4}.

Paso 3: k=2 y a2=c12=max{20,10,10}=20. Clasificamos el nodo 2 con [20,1]. Tomamos

i=2 y repetimos el paso 2.

Paso 2: S2= {3,5}

Paso 3: k=3 y a3=c23=max {30,40} =40. Clasificamos el nodo 3 con [40,2]. Tomamos
i=3 y repetimos el paso 2.

Paso 2: S3= {4} (c35=0, el nodo 1 ya ha sido clasificado y el nodo 2 cumple ambas
condiciones, por tanto, los nodos 1, 2 y 5 no pueden ser incluidos en S3).

Paso 3: k=4 y a4=c34=10. Clasificamos el nodo 4 con [10,3]. Tomamos i=4 y repetimos
el paso 2.

Paso 2: S4= {5}

Paso 3: k=5 y a5=c45=20. Clasificamos el nodo 5 con [20,4]. Logramos la penetración,

vamos al

Paso 5: La ruta de la penetración es: 5→ [20,4]→4→ [10,3]→3→ [40,2]→2→

[20,1]→1.

Entonces la ruta es N2= {1,2,3,4,5} y f2=min {∞,20,40,10,20} =10. Las capacidades

residuales a lo largo de esta ruta son:

(c12, c21) = (20-10, 0+10) = (10,10)

(c23, c32) = (40-10, 0+10) = (30,10)

Página 10 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

(c34, c43) = (10-10, 5+10) = (0,15)

(c45, c54) = (20-10, 0+10) = (10,10)

Iteración 3:

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Paso 2: S1= {2,3,4}.

Paso 3: k=2 y a2=c12=Max {10,10,10} =10, rompemos el empate arbitrariamente.

Clasificamos el nodo 2 con [10,1]. Tomamos i=2 y repetimos el paso 2.

Paso 2: S2= {3,5}

Paso 3: k=3 y a3=c23=Max {30,30} =30. Clasificamos el nodo 3 con [30,2]. Tomamos
i=3 y repetimos el paso 2.

Paso 2: S3 vacío ya que c34=c35=0. Vamos al paso 4 para retroceder.

Paso 4: La clasificación [30,2] nos dice que el nodo inmediatamente precedente es el 2.

Eliminamos el nodo 3 de una consideración posterior en esta iteración. Tomamos i=2 y
repetimos el paso 2.

Paso 2: S2= {5}

Paso 3: k=5 y a5=c25=30. Clasificamos el nodo 5 con [30,2]. Logramos la penetración,

vamos al

Paso 5: La ruta de la penetración es: 5→ [30,2]→2→ [10,1]→1.

Entonces la ruta es N2= {1,2,5} y f3=min {∞,10,30} =10. Las capacidades residuales a
lo largo de esta ruta son:

(c12, c21) = (10-10, 10+10) = (0,20)

Página 11 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

(c25, c52) = (30-10, 0+10) = (20,10)

Iteración 4:

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Paso 2: S1= {3,4}.

Paso 3: k=3 y a3=c13=max{10,10}=10. Clasificamos el nodo 3 con [10,1]. Tomamos i=3

y repetimos el paso 2.

Paso 2: S3= {2}

Paso 3: k=2 y a2=c32=10. Clasificamos el nodo 2 con [10,3]. Tomamos i=2 y repetimos
el paso 2.

Paso 2: S2= {5}

Paso 3: k=5 y a5=c25=20. Clasificamos el nodo 5 con [20,2]. Logramos la penetración,

vamos al paso 5.

Paso 5: La ruta de la penetración es: 5→ [20,2]→2→ [10,3]→3→ [10,1]→1.

Entonces la ruta es N4= {1,3,2,5} y f4=min {∞,10,10,20} =10. Las capacidades

residuales a lo largo de esta ruta son:

(c13, c31) = (10-10, 20+10) = (0,30)

(c32, c23) = (10-10, 30+10) = (0,40)

(c25, c52) = (20-10, 10+10) = (10,20)

Página 12 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

Iteración 5:

Paso 1: Hacemos ai=∞, y clasificamos el nodo 1 con [a1,-]. Tomamos i=1.

Paso 2: S1={4}.

Paso 3: k=4 y a4=c14=10. Clasificamos el nodo 4 con [10,1]. Tomamos i=4 y repetimos
el paso 2.

Paso 2: S4={3,5}

Paso 3: k=3 y a3=c23=max{15,10}=15. Clasificamos el nodo 3 con [15,4]. Tomamos i=3

y repetimos el paso 2.

Paso 2: S3 vacío ya que c32=c34=c35=0. Vamos al paso 4 para retroceder.

Paso 4: La clasificación [15,4] nos dice que el nodo inmediatamente precedente es el 4.

Eliminamos el nodo 3 de una consideración posterior en esta iteración. Tomamos i=4 y
repetimos el paso 2.

Paso 2: S4= {5}

Paso 3: k=5 y a5=c45=10. Clasificamos el nodo 5 con [10,4]. Logramos la penetración,

vamos al paso 5.

Paso 5: La ruta de la penetración es: 5→ [10,4]→4→ [10,1]→1.

Entonces la ruta es N2= {1,4,5} y f3=min {∞,10,10} =10. Las capacidades residuales a
lo largo de esta ruta son:

(c14, c41) = (10-10, 0+10) = (0,10)

(c45, c54) = (10-10, 10+10) = (0,20)

Página 13 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

Iteración 6:

No son posibles más penetraciones, debido a que todos los arcos fuera del nodo 1 tienen
residuales cero.

Para determinar la solución:

Paso 6: El flujo máximo en la red es F = f1+ f2 + …+ f5 = 60 unidades. El flujo en los

diferentes arcos se calcula restando las últimas residuales obtenidas en la última iteración
de las capacidades iniciales:

Página 14 de 15
 Escuela Superior Politécnica De Chimborazo
Carrera: Contabilidad Y Auditoría
Asignatura: Investigación Operativa

BIBLIOGRAFÍA
Marín Gonzales , G. P. (06 de 02 de 2017). UAB. Obtenido de UAB:
https://ddd.uab.cat/record/173874

Alvarez Moreno, L. M. (21 de 2 de 2016). Scribd. Obtenido de chrome-

extension://efaidnbmnnnibpcajpcglclefindmkaj/https://repositorio.unican.es/xmlui/bit
stream/10902/9189/1/Alvarez+Moreno%2C+Luz+Maria.pdf

Fernandez Baca, J. V. (13 de 05 de 2013). PUCP. Obtenido de PUCP:

http://hdl.handle.net/20.500.12404/4538

Medina, H. (21 de Abril de 2019). WordPress. Obtenido de

https://whdeveloper.wordpress.com/2019/04/21/algoritmo-del-flujo-maximo/

Página 15 de 15