Investigacion de operaciones.

Pauta Control 3

a)

FORD-FULKERSON

 Solución Inicial: Por inspección se propone una solución inicial al problema y con ello obtendremos la primera figura. Es importante destacar que para cada iteración, veremos la red residual, que corresponde a la red que muestra las capacidades restantes de los arcos en dirección (origen, destino), como también los arcos en rojo, en caso de querer devolver algún flujo ya enviado. Por ser una red bidireccional se debe considerar la posibilidad de flujo en ambos sentidos.

[pic 1][pic 2][pic 3][pic 4][pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13][pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32]

[pic 33]

[pic 34][pic 35][pic 36]

[pic 37]

Actualización N° 1: En este caso, lo que hacemos es enviar 3 unidades de flujo por el arco (A,C),  y luego  por el arco (C,H) que corresponde al máximo posible dada la capacidad de este ultimo arco. La red residual se muestra a continuación:

[pic 38][pic 39][pic 40][pic 41][pic 42][pic 43][pic 44][pic 45][pic 46][pic 47][pic 48][pic 49][pic 50][pic 51][pic 52][pic 53][pic 54][pic 55][pic 56][pic 57][pic 58][pic 59][pic 60][pic 61][pic 62][pic 63][pic 64][pic 65][pic 66][pic 67][pic 68][pic 69][pic 70]

[pic 71]

[pic 72]

[pic 73][pic 74]

Criterio de parada: Como ya no existen rutas factibles que conecten el nodo A, con el nodo H, se dice que el algoritmo ha finalizado

Como se puede ver en el gráfico de la primera actualización, el corte mínimo se encuentra en los arcos (D,H) y (C,H), donde se puede obtener un valor total de 6 unidades, siendo este el máximo posible a enviar, dadas las restricciones de capacidad de los arcos. La red con los flujos finales se presenta a continuación, donde los flujos corresponden a los arcos de color verde.

[pic 75][pic 76][pic 77][pic 78][pic 79][pic 80][pic 81][pic 82][pic 83][pic 84][pic 85][pic 86][pic 87][pic 88][pic 89][pic 90][pic 91][pic 92][pic 93]

CORTES:        

La cantidad de cortes a realizar se puede obtener mediante la ecuación , en este caso n corresponde al número de nodos (5) y por lo tanto nos queda = 8 cortes a realizar.[pic 94][pic 95]

El flujo máximo corresponde al corte con la capacidad mínima. Para este caso, el ultimo corte donde el subconjunto de nodos-origen S={A-B-C-D} y el subconjunto nodos-destino N-S={H} con flujo máximo 6

...