lij, xij œ (c) Use la solución factible de la red en (b) junto con el algoritmo de flujo máximo para
determinar el flujo mínimo en la red original. (Sugerencia: Primero calcule la red residuo dada
la solución factible inicial. Luego determine el flujo máximo del nodo final al nodo inicial. Esto
equivale a determinar el flujo máximo que se debe cancelar del nodo inicial al nodo final.
Ahora, combinando las soluciones factible y de flujo máximo se obtiene el flujo mínimo en la
red original.) (d) Use la solución factible de la red en (b) junto con el modelo de flujo máximo
para determinar el flujo máximo en la red original. (Sugerencia: Como en (c), inicie con la red
residuo. Luego aplique el algoritmo de avance a la red residuo resultante, exactamente como
en el modelo de flujo máximo regular.) 6.4.3 Formulación de programación lineal en el modo
de flujo máximo Defina xij como la cantidad de flujo en el arco (i,j) con capacidad Cij. El
objetivo es determinar xij para toda i y j que maximice el flujo entre el nodo de inicio s y el
nodo terminal t sujeto a restricciones de flujo (flujo de entrada 5 flujo de salida) en todos
excepto en los nodos s y t. Arco ( ) i, j ( ) lij, uij (1, 2) (5, 20) (1, 3) (0, 15) (2, 3) (4, 10) (2, 4) (3,
15) (3, 4) (0, 20) [Link] 6.4 Modelo de flujo máximo 245 Ejemplo 6.4-3 En el
modelo de flujo máximo de la figura 6.30 (ejemplo 6.4-2), s 5 1 y t 5 5. La siguiente tabla
resume la PL asociada con dos funciones objetivo diferentes, pero equivalentes, según si
maximizamos la salida del modo de inicio 1 (5 z1) o la entrada al nodo terminal 5 (5 z2). x12
x13 x14 x23 x25 x34 x35 x43 x45 Maximizar z1 = Maximizar z2 = 1 1 1 1 1 1 Nodo 2 1 - 1 - 1 = 0
Nodo 3 1 1 - 1 - 1 1 = 0 Nodo 4 1 1 - 1 - 1 = 0 Capacidad 20 30 10 40 30 10 20 5 20 La solución
óptima utilizando una u otra función objetiva es El flujo máximo asociado es z1 5 z2 5 60.
Momento de Solver La figura 6.33 proporciona el modelo de flujo máximo del ejemplo 6.4-2
(archivo solverEx6.4- [Link]). La idea general es parecida a la del modelo de la ruta más corta,
que se detalla siguiendo el ejemplo 6.3-6. Las diferencias principales incluyen las siguientes: (1)
no hay ecuaciones de flujo para el nodo inicial 1 y el nodo final 5, y (2) el objetivo es maximizar
el flujo de salida total en el nodo inicial 1 (F9) o, de forma equivalente, el flujo de entrada total
en el nodo terminal 5 (G13). El archivo solverEx6.4-2 utiliza G13 como celda [Link] de
ejecutar el modelo con G13 reemplazando a F9. Momento de AMPL El archivo [Link]
proporciona el modelo para el problema de flujo máximo entre cualquiera de los dos nodos en
la red del ejemplo 6.4-2. El modelo se aplica a cualquier cantidad de nodos. La explicación del
modelo se detalla en la sección C.9 en el sitio web. CONJUNTO DE PROBLEMAS 6.4C 1. Modele
cada uno de los siguientes problemas como un programa lineal, luego resuélvalo utilizando
Solver o AMPL. (a) Problema 2, conjunto 6.4b. (b) Problema 5, conjunto 6.4b. (c) Problema 9,
conjunto 6.4b. x12 = 20, x13 = 30, x14 = 10, x25 = 20, x34 = 10, x35 = 20, x45 = 20
[Link] 246 Capítulo 6 Modelo de redes FIGURA 6.34 Red para el problema 2,
conjunto 6.4c 1 4 9 12 Y 14 13 10 11 8 7 3 6 5 2 D FIGURA 6.35 Red para el problema 3,
conjunto 6.4c 2 7 9 8 5 4 3 1 6 2. Jim vive en Denver, Colorado, y le gustar pasar sus vacaciones
anuales en el Parque Nacional de Yellowstone en Wyoming. Por ser un amante de la
naturaleza, Jim toma una ruta escénica diferente cada año. Después de consultar los mapas
apropiados, Jim representó sus rutas preferidas entre Denver (D) y Yellowstone (Y) por medio
de la red de la figura 6.34. Los nodos 1 a 14 representan ciudades intermedias. Aunque la
distancia de manejo no es un factor, la estipulación de Jim es que las rutas seleccionadas entre
D y Y no incluyan ciudades comunes. Determine (por medio de AMPL o Solver) todas las rutas
distintas disponibles para Jim. (Sugerencia: Modifique el modelo de programación lineal de
flujo máximo para determinar el máximo de rutas únicas entre D y Y.) 3. (Guéret and
Associates, 2002, sección 12.1) En la figura 6.35 se aparece un sistema de telecomunicación
militar que conecta 9 sitios . Los sitios 4 y 7 deben continuar comunicándo-
[Link] 6.5 CPM y PERT 247 FIGURA 6.36 Fases para la planificación de un
proyecto con CMP-PERT Red Cronograma Tiempo Actividades del proyecto Cálculo de red se
incluso si otros tres sila red después de (1) mod