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

image

Pasos a seguir

image
Paso5: Repetir el proceso desde el paso 2 (Considerando ya no un nodo origen si no un
nodo temporal), hasta llegar al nodo destino.

image
Paso3: Una vez evaluado, sumar los costos de los caminos recorridos desde el nodo
origen hasta el nodo temporal.

image
Paso 1: Identificar nuestro nodo origen y nuestro nodo destino.

image
Paso2: Desde nuestro nodo origen evaluamos el “Camino” con el menor costo.

image
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.

image
Formulación

Propiedades:

image
No factible

“El flujo total generado por los nodos origen es igual al flujo total
absorbido por los nodos destino.

image

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.

image

Usos

image
Sistema de vías publicas

image
Transporte de petróleo desde la refinería hasta centros de almacenamientos

image
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

image

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

image

Se utiliza una tabla para el desarrollo de este método en donde anotamos nuestros datos

image