3 La idea es que la hoja de cálculo trata una celda en blanco como un valor cero.
Si sucede que
un problema tiene una distancia cero entre nodos, la distancia cero puede reemplazarse con
un valor positivo muy pequeño. 4 La solución del modelo presenta una curiosa ocurrencia. Si la
restricción netFlow = 0 se reemplaza con outFlow = inFlow en el cuadro de diálogo Solver
Parameters, Solver no determina una solución factible, incluso si se ajusta la precisión en el
cuadro de diálogo Solver Option. (Para reproducir esta experiencia, las celdas de solución
B9:E12 deben ser cero o estar vacías.) Aún más curioso, si las restricciones se reemplazan con
inFlow = outFlow, se encuentra la solución óptima. No está claro por qué ocurre esta
peculiaridad, pero el problema puede estar relacionado con error de redondeo.
[Link] 234 Capítulo 6 Modelo de redes Momento de AMPL El archivo
[Link] proporciona el modelo para resolver el ejemplo 6.3-6. El modelo es general
en el sentido de que puede usarse para determinar la ruta más corta entre dos nodos
cualesquiera en un problema de cualquier tamaño. El modelo se explica en la sección C.9 en el
sitio web. CONJUNTO DE PROBLEMAS 6.3E 1. Modifique el archivo [Link] para
determinar la ruta más corta entre los siguientes pares de nodos: (a) Nodo 1 a nodo 5. (b)
Nodo 4 a nodo 3. 2. Adapte el archivo [Link] para el problema 2, conjunto 6.3a,
para hallar la ruta más corta entre el nodo 1 y el nodo 7. Los datos de entrada deben ser las
probabilidades puras. Use las funciones de programación para imprimir y visualizar en pantalla
la ruta de transmisión óptima y su probabilidad de éxito. 6.4 MODELO DE FLUJO MÁXIMO
Considere una red de oleoductos que transporta petróleo crudo desde pozos hasta refinerías.
Se instalan estaciones intermedias de reforzamiento y bombeo a distancias apropiadas para
mover el crudo en la red. Cada segmento de tubería tiene una velocidad de descarga finita (o
capacidad) de flujo de crudo. Un segmento de tubería puede ser unidireccional o bidireccional,
según su diseño. La figura 6.26 muestra una red de oleoductos típica. El objetivo es determinar
la capacidad de flujo máxima de la red. La solución del problema propuesto requiere agregar
una sola fuente y un solo sumidero o vertedero, utilizando arcos de capacidad infinita
unidireccionales, como se muestra mediante los arcos de rayas en la figura 6.26. Para el arco
(i,j), la notación proporciona las capacidades de flujo en las dos direcciones i S j y j S i. Para
eliminar la ambigüedad, colocamos a junto al nodo i y a junto al nodo C j, como se muestra en
la figura 6.27. ji Cij (Cij, Cji) FIGURA 6.26 Red capacitada que conecta los pozos y las refinerías
por medio de estaciones reforzadoras 2 5 Pozos Reforzadores Fuente Sumidero Refinerías 1 4
9 7 3 6 8 [Link] 6.4 Modelo de flujo máximo 235 FIGURA 6.27 Flujos de arcos Cij
de i S j y Cji de j S i i j Cij Cji FIGURA 6.28 Ejemplos de cortes en redes de flujo 2 1 5 10 10 5 30
30 0 40 0 0 C 0 orte 1 Corte 3 Corte 2 0 0 0 20 20 20 4 3 6.4.1 Enumeración de cortes Un corte
define un conjunto de arcos cuya eliminación de la red interrumpe el flujo entre los nodos
fuente y sumidero. La capacidad de corte es igual a la suma de las capacidades de su conjunto
de arcos. Entre todos los cortes posibles en la red, el corte con la capacidad mínima es el cuello
de botella que determina el flujo máximo en la red. Ejemplo 6.4-1 Considere la red de la figura
6.28. Las capacidades bidireccionales se muestran en los arcos respectivos por medio de la
convención utilizada en la figura 6.27. Por ejemplo, el límite de flujo para el arco (3,4) es de 10
unidades de 3 a 4, y de 5 unidades de 4 a 3. La figura 6.28 ilustra tres cortes con las siguientes
capacidades: La única información de los tres cortes es que el flujo máximo en la red no puede
exceder de 60 unidades. Para determinar el flujo máximo es necesario enumerar todos los
cortes, una tarea difícil para la red general. Por lo tanto, la necesidad de un algoritmo eficiente
es imperativa. CONJUNTO DE PROBLEMAS 6.4A *1. Para la red de la figura 6.28, determine dos
cortes más y encuentre sus capacidades. Corte Arcos asociados Capacidad 1 (1, 2), (1, 3), (1, 4)
20 + 30 + 10 = 60 2 (1, 3), (1, 4), (2, 3), (2, 5) 30 + 10 + 40 + 30 = 110 3 (2, 5), (3, 5), (4, 5) 30 +
20 + 20 = 70 [Link] 236 Capítulo 6 Modelo de redes 6.4.2 Algoritmo de flujo
máximo Este algoritmo se basa en el hallazgo de rutas de avance con flujo positivo entre los
nodos fuente y sumidero. Cada ruta destina una parte de o todas las capacidades de sus arcos
al flujo total en la red. Considere el arco (i, j) con las capacidades bidireccionales (de diseño) .
Como algunas partes de estas capacidades se destinan al flujo en el arco, los residuos
(capacidades no utiliz