al nodo 1; es decir (5) S [20, 3] S (3) S [30, 1] S (1).
De este modo, N1 5 [1, 3, 5] y f1 5 mín{a1,
a3, a5} 5 {q, 30, 20} 5 20. Las capacidades residuales a lo largo de la ruta N1 son (c35, c53) =
(20 - 20, 0 + 20) = 10, 202 (c13, c31) = (30 - 20, 0 + 20) = (10, 20) [Link] 6.4
Modelo de flujo máximo 239 Iteración 2. Paso 1. Establezca a1 5 q, y etiquete el nodo 1 con [q,
2]. Establezca i 5 1. Paso 2. S1 5 {2, 3, 4}. Paso 3. k 5 2 y a2 5 c12 5 máx {20,10,10}. Establezca i
5 2, y repita el paso 2. Paso 2. S2 5 {3,5}. Paso 3. k 5 3 y a3 5 c23 5 40. Etiquete el nodo 3 con
[40,2]. Designe i 5 3 y repita el paso 2. Paso 2. S3 5 {4} (observe que c35 5 0, de ahí que el nodo
5 no pueda incluirse en S3). Paso 3. k 5 4 y a4 5 c34 5 10. Etiquete el nodo 4 con [10,3].
Establezca i 5 4, y repita el paso 2. Paso 2. S4 5 {5} (observe que los nodos 1 y 3 ya están
etiquetados, por lo tanto, no pueden incluirse en S4). Paso 3. k 5 5 y a5 5 c45 5 20. Etiquete el
nodo 5 con [20,4]. Se logró una ruta de avance. Vaya al paso 5. Paso 5. N2 5 {1, 2, 3, 4, 5} y f2 5
mín {q, 20, 40,10,20} 5 10. Los residuos a lo largo de la ruta de N2 son Iteración 3. Paso 1.
Establezca a1 5 q, y etiquete el nodo 1 con [q, 2]. Establezca i 5 1. Paso 2. S1 5 {2, 3, 4}. Paso 3.
k 5 2 y a2 5 c12 5 máx {10,10,10}. (Aunque los empates se rompen arbitrariamente, TORA
siempre selecciona el nodo empatado con el índice menor. Utilizaremos esta convención a lo
largo del ejemplo.) Etiquete el nodo 2 con [10,1]. Haga i 5 2, y repita el paso 2. Paso 2. S2 5
{3,5}. Paso 3. k 5 3 y a3 5 c23 5 30. Etiquete el nodo 3 con [30,2]. Establezca i 5 3, y repita el
paso 2. Paso 2. S3 5 [ (porque c34 5 c35 5 0). Vaya al paso 4 para retroceder Paso 4. Retroceso.
La etiqueta [30,2] en el nodo 3 da el nodo inmediatamente anterior r 5 2. Elimine el nodo 3
tachándolo para ya no considerarlo en esta iteración. Establezca i 5 r 5 2, y repita el paso 2.
Paso 2. S2 5 {5} (observe que el nodo 3 se eliminó en el paso de retroceso). Paso 3. k 5 5 y a5 5
c25 5 30. Etiquete el nodo 5 con [30,2]. Se logró una ruta de avance. Vaya al paso 5. Paso 5. N2
5 {1, 2,5} y c5 5 mín {q,10,30} 5 10. Los residuos a lo largo de la ruta de N3 son Iteración 4. Esta
iteración da N4 5 {1,3,2,5} con f4 5 10 (¡compruébelo!). (c25, c52) = (30 - 10, 0 + 10) = (20,10)
(c12, c21) = (10 - 10,10 + 10) = (0, 20) (c45, c54) = (20 - 10, 0 + 10) = (10, 10) (c34, c43) = (10 -
10, 5 + 10) = (0,15) (c23, c32) = (40 - 10, 0 + 10) = (30,10) (c12, c21) = (20 - 10, 0 + 10) = (10,10)
[Link] 240 Capítulo 6 Modelo de redes Iteración 5. Esta iteración da por
resultado N5 5 {1,4,5} con f5 5 10 (¡compruébelo!). Iteración 6. Todos los arcos que parten del
nodo 1 tienen residuos cero. Por lo tanto, no son posibles más rutas de avance. Procedemos al
paso 6 para determinar la solución. Paso 6. El flujo máximo en la red es F 5 f1 1 f2 1 … 1 f5 5 20
1 10 1 10 1 10 110 5 60 unidades. El fluj
de las capacidades de diseño , como lo muestra la siguiente tabla. (Cij, Cji) Momento de TORA
Podemos utilizar TORA para resolver el modelo de flujo máximo en un modo automático una
iteración a la vez. Seleccione el menú y la opción . Después de especificar el formato de salida,
vaya a la pantalla de resultados y seleccione la opción o . El archivo [Link] contiene los
datos para el ejemplo 6.4-2. CONJUNTO DE PROBLEMAS 6.4B *1. En el ejemplo 6.4-2. (a)
Determine las capacidades excedentes para todos los arcos. (b) Determine la cantidad de flujo
a través de los nodos 2, 3, y 4. (c) ¿Puede incrementarse el flujo a través de la red si se
aumentan las capacidades en las direcciones 3 S 5 y 4 S 5? 2. Determine el flujo máximo y el
flujo óptimo en cada arco para la red de la figura 6.31. 3. Tres refinerías envían un producto de
gasolina a dos terminales de distribución a través de una red de oleoductos. Cualquier
demanda que no puede ser satisfecha por medio de Maximum Flows Iterations
SOLVE/MODIFY Solve Problem Arco (Cij, Cji) - (cij, cji)6 Cantidad de flujo Dirección (1, 2) (20, 0)
- (0, 20) = (20, -20) 20 1 : 2 (1, 3) (30, 0) - (0, 30) = (30, -30) 30 1 : 3 (1, 4) (10, 0) - (0, 10) = (10, -
10) 10 1 : 4 (2, 3) (40, 0) - (40, 0) = (0, 0) 0 — (2, 5) (30, 0) - (10, 20) = (20, -20) 20 2 : 5 (3, 4) (10,
5) - (0, 15) = (10, -10) 10 3 : 4 (3, 5) (20, 0) - (0, 20) = (20, -20) 20 3 : 5 (4, 3) (5, 10) - (15, 0) = (-
10, 10) 0 — (4, 5) (20, 0) - (0, 20) = (20, -20) 20 4 : 5 [Link] 6.4 Modelo de flujo
máximo 241 FIGURA 6.31 Red para el problema 2, conjunto 6.4b 2 1 8 14 7 7 5 0 0 0 0 0 10 10
9 6 6 5 0 4 3 4 5 FIGURA 6.32 Red para el problema 3, conjunto 6.4b 2 10 20 1 15 50 20 3 4 7 8
5 20 10 30 6 20 10 30 50 Refinerías Estaciones de bombeo Terminales la red se adquiere de
otras fuentes. Tres estaciones de bombeo le dan servicio a la red, como se muestra en la figura
6.32. El producto fluye en la red en la dirección indicada por las flechas. La capacidad de cada
segmento de ducto (mostrada directamente en los arcos) está en millones de barriles por día.
Determine lo siguiente: (a) La producción diaria en cada refinería que iguala la capacidad
máxima de la red. (b) La demanda diaria en cada terminal que iguala la capacidad máxima de la
red. (c) La capacidad diaria de cada bomba que iguala la capacidad máxima de la red. 4.
Suponga que la capacidad diaria máxima de la bomba 6 en la red de la figura 6.33 está limitada
a 50 millones de barriles por día. Remodele la red para incluir esta restricción. Luego
determine la capacidad máxima de la red. 5. Se transporta alimento para gallinas por medio de
camiones desde tres silos hasta cuatro granjas. Algunos de los silos no pueden mandar los
envíos directamente a algunas de las granjas. Las capacidades de las demás rutas están
limitadas
