MODELOS DE REDES

MODELO DE REDES

La importancia del análisis de flujo de redes, en los últimos años ha crecido de una manera progresiva en todos los campos de la planificación; de procesos tareas y recursos tanto económicos como físicos y del tiempo de los proyectos que requieren de este tipo de planificación.

La aplicación de estos tipos de modelos tiene infinidades campos de acción en los diferentes proyectos de inversión tales como:

• En los proyectos de diseños de tuberías de acueducto, gas natural, electrificación, vías, tanto férreas como carrete hables.

• En la determinación del camino más corto entre dos lugares o ciudades de acuerdo a una red existente.

• En la determinación de las capacidades máximas que deben fluir a través de una red, de un recurso especifico.

• La determinación del programa de flujo de costo mínimo de los campos de origen a los centros de distribución de un recurso especial.

Un estudio de esta lista representativa, revela que los problemas de optimización de redes se pueden representar en términos generales a través de los siguientes modelos.

• Modelo del flujo máximo

• Modelo de la ruta más corta.

• Modelo del árbol de extensión mínima.

• Modelo de red de capacidad de costo mínimo.

• Modelo de la ruta critica.

• Modelo de la técnica de evaluación y revisión de proyectos (PERT.

Para la comprensión de los diferentes modelos, se deben tener en cuenta las siguientes definiciones.

DEFINICIÓN DE RED. Es un conjunto de nodos conectados por arcos o ramas, a veces los nodos reciben el nombre de “vértices” y los ramales de “arcos”.

CADENA : Una cadena es una secuencia de ramales que conectan dos nodos que al especificarles dirección forman lo que se llama un camino o ruta.

RED SIMÉTRICA: Significa que un vértice “x” esta conectado a uno “y”; entonces “y”, esta conectado a “x”.

RED ASIMÉTRICA: Significa que un vértice “x” esta conectado a uno “y”; entonces “y”, no esta conectado a “x”.

CAPACIDAD: Es el flujo que circula por una determinada red y puede ser finita o infinita.

RAMA DIRIGIDA U ORIENTADA: Cuando se permite el paso de un flujo positivo en una determinada dirección y cero en la dirección opuesta.

TRAYECTORIA: Es una secuencia de ramas que conectan dos nodos sin considerar su orientación de las demás ramas individuales.

LASO O CICLO: Se presenta cuando un nodo se conecta consigo mismo.

LASO DIRIJIDO U CIRCUITO: Es un lazo donde todas las ramas tienen las mismas dirección u orientación.

PROBLEMA DEL FLUJO MÁXIMO

Este problema determina el estado factible de flujos a través de la red, que maximiza el flujo total desde el origen hasta el destino en forma tal, que la capacidad de cada rama en esta trayectoria sea mínima.

El flujo máximo a lo largo de esta trayectoria debe ser igual a la capacidad mínima, de todas las ramas que constituyen la trayectoria.

FORMULACION DEL MODELO

Para resolver este tipo de modelos se presentan los siguientes métodos.

1. Formulación de un problema de programación lineal.

2. Algoritmo del flujo máximo.

El primer método de plantea de la siguiente manera:

Supongamos que existen “n” nodos, donde los nodos 1 y n son el origen y el destino respectivamente como se representa en la red.

Fuente destino

Cij Xij

El flujo que circula por la red debe cumplir la siguiente restricción:

0 < Xij < Cij

Además debe cumplir la siguiente restricción de conservación de flujo.

 Xik -  Xkj = 0

Formulación de un problema de programación lineal

1. Se define la variable de decisión Xn.

XIJ = La cantidad de flujo que circula de la fuente i al destino j.

2. Se define la función objetivo.

MAX F =  Xik.

3. Se define las restricciones.

Flujo circulante 0 < Xij < Cij

Conservación flujo  Xik -  Xkj = 0

4. restricción de no negatividad

Xij > 0.

Formulación del modelo de flujo máximo.

Para la formulación del modelo del flujo máximo se debe seguir los siguientes pasos.

1. Buscar una ruta con capacidad positiva

2. Buscar la capacidad mínima en esta ruta y disminuir el flujo por este valor en sentido de izquierda a derecha. Y aumentarlo en sentido contrario.

Ejemplo.

8 0 4

0 4 3

8

7 0

10 2 1 7 0

0 0 3 0 4 0

3

4

0 5

solución.

Rutas clasificación status

1-2-4-7 (7,8,4) flujo mínimo 4

1-3-6-7 (10,3,5) flujo mínimo 3

1-2-4-5-7 (3,4,3,7) flujo mínimo 3

1-3-5-7 (7,3,4) flujo mínimo 3

1-3-4-2-5-6-7 (4,2,7,4,4,2) flujo mínimo 2

total flujo máximo = 15

MODELO DEL ALGORITMO DE LA RUTA MÁS CORTA

Para la solución de este problema se tiene el método del algoritmo de DIJKSTRA, el cual se estudiara para resolver dos tipos de problemas de redes las aciclicas y cíclicas.

ALGORITMO ACICLICO

Este algoritmo se basa en el uso de cálculos recursivos que son la base para los cálculos de la programación dinámica. Para un mejor entendimiento del algoritmo desarrollaremos sus pasos de solución a través de un ejemplo.

5 6

2 11 3

10

4

3 7 9

1

sea Uj = la distancia mas corta entre el nodo i y el nodo j.

Ui = 0 por definición.

Los valores de Uj; j= 1,2,........n se calcularan mediante la siguiente formula.

Uj = min. { Uj + Dij.

...