Aunque el procedimiento de la figura 10.7 es relativamente sencillo, será útil poder reconocer cuándo se tiene un patrón óptimo sin tener que buscar de manera exhaustiva una ruta que no existe. A veces es posible esto con el resultado de un teorema importante de teoría de redes, conocido como el teorema del flujo máximo cortadura mínima. Una cortadura se puede definir como cualquier conjunto de arcos dirigidos que contienen al menos un arco de cada tayectoria dirigida que va del nodo origen al nodo destino. El valor de la cortadura es la suma de las capacidades de los arcos (en las dirección específica) de la cortadura. El teorema del flujo máximo-cortadura mínima establece que para cualquier red con un solo nodo origen y un solo nodo destino, el flujo máximo factible del origen al destino es igual al valor de la cortadura mínima para todas las cortaduras de la red. Así, si F denota la cantidad de flujo del origen al destino para cualquier patrón de flujo factible, el valor de cualquier cortadura proporciona una cota superior para F, y el menor de los valores de las cortaduras es igual al máximo valor de F. Entonces, si se puede encontrar, en la red original, una cortadura cuyo valor sea igual al valor actual de F encontrado con el procedimiento de solución, el patrón de flujo actual debe ser óptimo. Eventualmente se alcanza la optimalidad siempre que exista una cortadura cuyo valor sea cero en la red residual.
Para ilustrar esto, considérese en la figura 10.5 la cortadura que se indica en la figura 10.8. Nótese que el valor de la cortadura es (3+4+1+6) =14 que, según se había encontrado , corresponde al máximo el valor de F, por lo que se tata de una cortadura mínima. Nótese también que en la red residual obtenida en la iteración 7, en donde = 14, la cortadura correspondiente tiene el valor cero. Si estos se hubiera observado, no habría sido necesario buscar trayectorias aumentadas adicionales.
No hay comentarios.:
Publicar un comentario