Análisis de Redes
Ruta más corta
Problema del flujo de costos mínimos
Árbol de expansión mínima
Problemas de flujo máximo
Se debe encontrar o determinar el plan de rutas que genere la trayectoria con la mínima distancia total, que una un nodo fuente con un nodo destino
Pasos a seguir
Paso5: Repetir el proceso desde el paso 2 (Considerando ya no un nodo origen si no un
nodo temporal), hasta llegar al nodo destino.
Paso3: Una vez evaluado, sumar los costos de los caminos recorridos desde el nodo
origen hasta el nodo temporal.
Paso 1: Identificar nuestro nodo origen y nuestro nodo destino.
Paso2: Desde nuestro nodo origen evaluamos el “Camino” con el menor costo.
Paso4: Una vez realizadas las consideraciones y las sumas de cuánto nos costaría llegar
el mismo punto, eliminar las opciones que representen un mayor costo.
Repetir el proceso desde el paso 2 (Considerando ya no un nodo origen si no un
nodo temporal), hasta llegar al nodo destino.
Formulación
Propiedades:
No factible
“El flujo total generado por los nodos origen es igual al flujo total
absorbido por los nodos destino.
Existe un flujo que viaja desde un único lugar de origen hacia un único lugar de destino a través de arcos que conectan nodos intermediarios. Los arcos tiene una capacidad máxima de flujo, y se trata de enviar desde la fuente al destino la mayor cantidad posible de flujo.
Usos
Sistema de vías publicas
Transporte de petróleo desde la refinería hasta centros de almacenamientos
Distribución de energía eléctrica a través de una red de alambrado publico
Algoritmo de Ford-Fulkerson
El flujo es siempre positivo y con unidades enteras
El flujo que entra en un nodo es igual al que sale de él.
El flujo a través de un arco es menor o igual que la capacidad.
Es un mínimo conjunto de enlaces de E que conectan todos los nodos en V y por lo tanto al menos un árbol de expansión puede ser encontrado en un grafo G
El mínimo árbol de expansión denotado por T* es un árbol de expansión cuyo peso total de todos los enlaces es mínimo
Se utiliza una tabla para el desarrollo de este método en donde anotamos nuestros datos