Operativa IIMODELO DE REDES

FRANCISCO VARGASINGENIERO DE SISTEMAS

ESPECIALISTA EN GERENCIA DE SISTEMAS INFORMÁTICOSMAGÍSTER EN CIENCIAS DE LA INFORMACIÓN Y LAS COMUNICACIONES CON ÉNFASIS EN

TELEINFORMÁTICACANDIDATO A DOCTOR EN CIENCIA Y TECNOLOGÍA INFORMÁTICA

2015

MODELO DE REDES

Problemas de transporte ( o distribución)

Envío de mercancías entre fuentes y destinos

1. GENERALIDADES

Con costos de transporte mínimo

Modelo de red

Se representa y resuelve

Ejemplos:a. Diseño red de tubería de gas natural, conectar fuentes del Golfo de México con

un punto de entrega en tierra objetivo minimizar el costo de construcción del conducto.

b. Determinación de la ruta más corta que une 2 ciudades en una red de caminos existente

c. Determinación del programa de flujo de costo mínimo de los campos petrolíferos a refinerías , y finalmente a centros de distribución. Se puede enviar petróleo y derivados en buques, oleoductos y/o camiones.Conclusiones: Los problemas de optimización de redes se pueden

representar en términos generales a través de uno de cuatro modelos:1. Modelo del árbol de extensión mínima 2. Modelo de la ruta más corta3. Modelo del flujo máximo 4. Modelo de red capacitada de costo mínimo

MODELO DE REDES

1.1 Definición de redes

RED Nodo 1Nodo 2

Nodo n

.

.

.

Arcos o ramas

Ejemplo: Red de transporte

Notación: Red GG = (N, A), donde N es el conjunto de nodos y A es el conjunto de ramas

3

2 4

5

1

Figura 1.

La red de la figura se describe así:5 nodos, 8 ramas

N= 1,2,3,4,5A= (1,3), (1,2), (2,3), (2,4), (2,5), (3,4), (3,5), (4,5)

1.2 Notación de las redes

MODELO DE REDES

1.3 Conceptos: Rama dirigida, Red dirigida, Trayectoria, Lazo, Árbol• El flujo de una rama está limitado por su capacidad que puede ser finita o infinita• Rama dirigida u orientada: Si permite un flujo positivo en una dirección, y

cero flujo en la dirección opuesta.• Red dirigida: Red con todas sus ramas dirigidas.• Trayectoria: Es una secuencia de ramas distintas que conectan 2 nodos sin

considerar la orientación de las ramas individuales. Por ejemplo: en la figura 1 las ramas (1,3), (3,2), y (2,4) constituyen una trayectoria del nodo 1 al 4.• Una trayectoria forma un lazo o ciclo si conecta un nodo consigo mismo. Por ejp

en la figura 1 las ramas (2,3), (3,4), y (4,2) forman un lazo.• Lazo dirigido o circuito es un lazo donde todas las ramas tienen la misma

dirección u orientación.• Red conectada, Es una red donde cada dos nodos distintos están conectados por

una trayectoria como se observa en la figura 1.• Árbol: Es una red conectada que puede constar solo de un subconjunto de los

nodos.• Árbol extenso: Es una red conectada que incluye todos los nodos de la red sin

lazos.3

2

1

4

3

2

1

4

5

Árbol extenso

Árbol