Investigacion de operaciones.

...

b) Aún cuando conceptualmente la utilización de cortes es más simple que el algoritmo de Ford&Fulkerson, potencialmente es computacionalmente mucho más “caro” o más costoso, debido a que el número total de cortes crece muy rápido con el número de nodos de la red, mientras que el algoritmo de Ford&Fulkerson posee un consumo de recursos bastante menor (número de iteraciones). Por ejemplo, una red con 20 nodos posee en total [pic 96] cortes a ser evaluados, mientras que Ford&Fulkerson, dependiendo de la solución inicial factible considerada, requiere tantas iteraciones como rutas factibles existen entre r y s (que muy probablemente es un número bastante menor a [pic 97]. F-F es exponencial, pero menos complejo que la utilización de cortes.

c)

Variable de decisión:

F: Flujo máximo = Flujo del arco i al arco j[pic 98]

Parámetros:

N= Conjunto de nodos

A= Conjunto de arcos= Capacidad del arco i,j

r=nodo inicio

s=nodo final[pic 99]

Función Objetivo:

(i) Max F

Restricciones:

(ii) [pic 100]

(iii) [pic 101]

Explicación:

(i) La función objetivo busca maximizar el flujo máximo que puede circular por toda la red

(ii) Restricción de balance de masa: lo que entra a cada arco es igual a lo que sale para todos los nodo menos el inicial y el final, en el caso del nodo inicial (r) lo que sale es igual al flujo máximo. Por otro lado en el nodo final (s) el resultado es (-) el flujo máximo, ya que por no tener arcos de salida se asume que el flujo máximo queda ahí.

(iii) Restricción de capacidad y no negatividad, el flujo por todos los arcos debe ser como mínimo cero y nunca mayor a la capacidad máxima de cada arco.

Nota: Puede resolverse también como adaptación a PFMC donde en vez de F se considera un flujo desde el nodo s al nodo r por lo que la función objetivo queda como min - Xs,r.