Apuntes para todos los estudiantes y cursos

La ruta de camino critico

Cap 4 Flow Algorithm 

Ford – Fulkerson


Se basa en encontrar en cada iteración caminos aumentantes. Un camino aumentante se forma por: un arco hacia delante que no esté lleno o un arco hacia “atrás” que no esté vacío. Los nodos siempre tienen que estar en equilibrio, la cantidad que entra tiene que ser igual a la que sale.


Repetir 3 veces:


  1. Encuentre un camino aumentante

  2. Determine el cuello de botella (que es la mínima capacidad del conjunto de arcos seleccionados). 

  3.  Incremente el flujo de cada arco y calcule el flujo total sumando esa mínima capacidad del cuello de botella.

Camino aumentante: se forma por un conjunto de arcos para adelante que no estén llenos y/o arcos para atrás que no estén vacíos.


05/11


Cuando se está buscando flujo con costo mínimo

  1. Primero se debe ejecutar ford fulkerson para determinar el flujo máximo de la red.

  2. Luego se escoge un número menor de unidades que se desean movilizar y para cada costo posible se corre ford-fulkerson con el subgrafo de los caminos que tienen ese costo. 

  1. Se puede usar el depth-first search para obtener los costos de los caminos, y luego ordenarlos de menor a mayor

Cap 9

Ruta Critica


Forward pass se hace por breadth first. (se agarran los máximos)

Backward pass se pinta primero la ruta crítica por breadth first al revés. (se agarran los mínimos)


Estructuras de datos auxiliares: tablas relacionales. 


Ruta crítica (Critical camino): aquellos nodos que se tienen que respetar y que se les tomó como máximo en el forward path. Es una ruta cuyos retrasos (por más pequeños que sean) en cualquiera de sus actividades atrasaría al proyecto.


Early Finish = Early Start + Duration

Late Start = Late Finish – Duration

Float/Slack Time = Late Start – Early Start

Ruta crítica:Tiempo de flotación / holgura: es el tiempo que una actividad puede retrasarse sin retrasar el proyecto. Definición dada en clase: es la diferencia entre la fecha de terminación tardía y la temprana.


Resumen Esc .

It’s a secret to everybody

Capacidad del flujo: es la cantidad máxima de flujo que puede ingresar por el nodo fuente y salir por el nodo destino

Origen o fuente de flujo: es el nodo por el cual el flujo ingresa al sistema.

Destino: es el nodo por el que el flujo sale del sistema.

Capacidades residuales: capacidades restantes del arco una vez pasado un flujo por él.

Algoritmo de flujo máximo: dada una red (o grafo) de arcos y nodos, cada arco con una capacidad determinada, y con un nodo fuente y otro destino, se trata de hallar la cantidad máxima de flujo que puede circular desde el nodo fuente hasta el nodo destino, de manera que el flujo individual que va por cada arco no supere la capacidad de sí mismo, se utiliza para reducir los embotellamientos entre ciertos puntos de partida y destino de una red.

Algoritmo de Ford Fulkerson: propone buscar caminos en los que se pueda aumentar el flujo, hasta que se pueda aumentar el flujo máximo. El algoritmo inicia otorgando un valor de flujo de cero a cada uno de los arcos de la red. Luego, se pasa a una fase iterativa, en la cual en cada repetición se busca una trayectoria de aumento, y se incrementa el valor del flujo que circula en cada arco de dicha trayectoria por el valor de la capacidad residual de la misma (es decir, el flujo en esos arcos se incrementa en el menor valor de entre todas las capacidades de los arcos que constituyen la mencionada trayectoria), hasta que ya no se puedan encontrar trayectorias de aumento en la red. Entonces, por el teorema del flujo máximo – corte mínimo, una vez que ya no existan trayectorias de aumento el flujo máximo habrá sido calculado. ES UN ALGORITMO DE FLUJO MÁXIMO GREEDY.

Red residual: camino de la fuente al sumidero, donde cada una de las aristas tiene un flujo residual mayor que cero. Siendo el flujo residual, el flujo que se puede obtener en una arista una vez que haya pasado un flujo por ella. 

Trayectoria de aumento: una trayectoria simple que va del origen al destino en la red residual.
Por ende, cada uno de sus arcos admite cierta cantidad de flujo positivo sin violar la restricción de capacidad de estos.

Red de flujo: en teoría de grafos una red de flujos es un grafo dirigido donde existen dos vértices especiales, uno llamado origen y otro llamado destino y a cada arista se le asocia cierta capacidad positiva.

En las redes cada arista lleva asociada 2 números: el costo de recorrerla y su capacidad. Una red de flujo en un grafo en el que se representa un problema para transportar unidades entre dos sitios. Las aristas tienen asociado dos parámetros numéricos, la capacidad del medio de transporte y su costo. 

Uno de los usos principales de los llamados algoritmos de flujo es encontrar el flujo máximo de la fuente al sumidero, siempre cumpliendo unas determinadas restricciones.

Algoritmo de flujo máximo

Tenemos el conocido problema de flujo máximo o maximal: ¿cuál es la tasa mayor a la cual el material puede ser transportado de la fuente al sumidero sin violar ninguna restricción de capacidad?

En otras palabras, el problema consiste en determinar la máxima capacidad de flujo que puede ingresar a través de la fuente y salir por el nodo de destino.

El procedimiento para obtener el flujo máximo de una red, consiste en seleccionar repetidas veces cualquier trayectoria de la fuente al destino y asignar el flujo máximo posible en esa trayectoria.

Podemos, mediante el Algoritmo de Ford-Fulkerson, encontrar el flujo máximo de una red.

Este algoritmo es un método iterativo, el cual, empieza con un flujo nulo y en cada iteración se va obteniendo un valor del flujo que va aumentando el camino, hasta que no se pueda aumentar más. Depende de tres puntos vitales:

Red residual: camino de la fuente al sumidero, donde cada una de las aristas tienen un flujo residual mayor que cero. Siendo el flujo residual, el flujo que se puede obtener en una arista una vez que haya pasado un flujo por ella

Aumento de camino: se basa en ir aumentando el camino, hasta alcanzar el flujo máximo (capacidad residual)

Restricciones:

  • Los valores de flujo existentes en cada arista no pueden sobrepasar los valores máximos. 

  • La suma de las entradas de cada nodo interno tiene que ser igual a la suma de las salidas.

Carácterísticas principales

  • El flujo va a ser siempre positivo y con unidades enteras

  • El flujo que entra en un nodo es igual al que sale.

  • El flujo que atraviesa un arco nunca será mayor que la capacidad, solo puede ser menor o igual que ella.

Camino aumentante: Un camino aumentante consta de un arco hacia adelante que no esté lleno y un arco hacia atrás que no esté vacío


No se permite realizar comentarios.