RESUMEN ALGORITMO DE FLUJO DE COSTO MINIMO Y PERT

RESUMEN ALGORITMO DE FLUJO DE COSTO MINIMO Y PERT-CPM
ALGORITMO DE FLUJO DE COSTO MINIMO:
1.- Plantear el grafo basándose en el enunciado.
2.- Convertirlo en una red de flujo R (e,v,a,b,c).
3.-Calcular A = sum (costos) +1. – Si es F.M de C.m pongo –A como costo del arco retorno.
– Si es F.m de C.m pongo +A como costo del arco retorno.– Y si es F de C.m no coloco arco retorno.
4.- Empiezo Hoffman para factibilizar el flujo del grafo.
5.- Calculo Indic.
6.- Una vezcalculado el indic se crea una red e sombrero para corregir el primer arco con violación superior. Siendo este arco el nuevo arco retorno (si es violación superior el arco va en sentido contrario al arcooriginal y si es una violación por debajo va en el mismo sentido, con cota inferior b=0 y capacidad igual a la violación del arco). Los demás arcos que violadores de la red original se factibilizantomando como cotas el flujo ya sea por violación inferior o superior.
7.- Se corre F&F.
Tools
Primera Parte de F&F
- se inicializa épsilon = 0, delta = al valor de la violación y S ={}
- Buscar caminosdel nuevo nodo inicial al nuevo final, primero buscando arcos directos y en caso q no se consigan se usan arcos inversos.
- Conjunto de nodos visitados S = {}.
-calcular delta. (El delta inicial esigual al valor es la violación que se desea corregir). Luego, se calcula para cada nodo en el camino que se está buscando. Delta = min C – f.
- Calcular el antecesor de cada nodo visitado (en este caso“los antecesores son arcos”).
- una vez se llega al nodo final se termina la primera parte. Y épsilon toma el valor del último delta.
Segunda Parte de F&F
Se inicializa X = {} con el ultimo nodo.
Seanaliza en qué dirección se recorrieron los arcos de atrás hacia adelante.
Se crean las listas C+ y C- , las cuales contienen en C+ los arcos recorridos de manera directa y C- los arcos recorridos de...