Conceptos de redes

TEMA 3. Principios de redes

3.1 Modelos de optimización de redes

Los problemas de redes surgen en una gran variedad de situaciones.

Por nombrar algunos, las redes de transporte, eléctricas, de comunicaciones, agua potable, etc.

La representación de redes se utiliza extensamente en áreas tan diversas como producción, distribución, planeación de proyectos, localización de instalaciones, administración de recursos, planeación financiera, etc.

Una representación en red proporciona un panorama general tan poderoso y una ayuda conceptual para visualizar las relaciones entre las componentes de los sistemas, que se usa en casi todas las áreas científicas, sociales y económicas.

Uno de los principales desarrollos recientes de la investigación de operaciones ha sido en la metodología y en la aplicación de los modelos de optimización de redes.

Han tenido un impacto importante la aparición de ciertos algoritmos, así como de ideas computacionales respecto a la estructura de los datos y su manipulación efectiva.

En consecuencia, ahora se dispone de algoritmos y de paquetes computacionales que se usan rutinariamente para resolver problemas grandes imposibles de manejar hace algunos años.

Muchos modelos de optimización de redes son en realidad tipos especiales de problemas de programación lineal.

Tanto el problema de transporte como el de asignación pertenecen a esta categoría, debido a su representación mediante una red.

Por ejemplo, en el caso del petróleo, una representación en red es esencial debido al flujo del mismo a través de distintas etapas: obtención del petróleo en crudo, su envío a las refinerías, refinamiento de los diferentes derivados, el embarque de dichos productos a los centros de distribución y terminales de almacenamiento para su venta posterior.

3.2 Representación básica de redes

Se ha desarrollado una terminología relativamente extensa para describir los tipos de redes y sus componentes.

Red: conjunto de nodos, arcos y flujos que pasan de un nodo a otro través de los arcos.

Entonces, una red está formada por tres componentes:

Nodos: conjunto de puntos (o vértices), la figura anterior tiene 7 nodos simbolizados por 7 círculos que representan las 7 estaciones del parque.

Arcos: conjunto de líneas (ligaduras, cadenas, aristas o ramas) que unen ciertos pares de nodos mediante flechas, las cuales le dan orientación al arco, la figura anterior tiene 12 arcos que corresponden a los 12 caminos del parque.

Etiqueta de un arco: nombre que reciben los arcos a partir de los nodos en sus puntos extremos, en la figura anterior, AB es el arco entre los nodos A y B.

Flujo: propiedad que tienen los arcos en cuanto a que “algo” pueda pasar a través de ellos, normalmente es un factor desconocido que debe determinarse; en la figura anterior, las “vans” que pasan a través de los caminos.

La siguiente tabla proporciona algunos ejemplos de flujos en redes:

Arco dirigido: si el flujo a través de un arco se permite sólo en una dirección, como en las calles de un solo sentido, lo cual se indica agregando una punta de flecha al final de la línea que representa el arco.

Etiqueta de un arco dirigido: nombre que reciben los arcos dirigidos a partir de los nodos en sus puntos extremos, nombrando siempre primero al nodo de donde viene y después al nodo a donde va; es decir, un arco dirigido del nodo A al nodo B debe etiquetarse como AB o bien A → B.

Arco no dirigido o ligadura: si el flujo a través de un arco se permite en ambas direcciones, como en las calles de doble sentido, lo cual se indica con un par de líneas curvas con o sin puntas de flecha en los extremos a donde van.

[pic 1]

En las figuras anteriores, los arcos 1 – 2, 1 – 3, 2 – 4 y 3 – 4 son arcos dirigidos, mientras que el arco 2 – 3 es un arco no dirigido.

Flujo real: aunque se permite que el flujo a través de un arco no dirigido ocurra en cualquier dirección, se supone que ese flujo será en una sola dirección (flujo real) y no se tendrán flujos simultáneos en direcciones opuestas.

Flujo neto:  diferencia de los flujos asignados en las dos direcciones.

Estas dos últimas definiciones implican que flujo real = flujo neto; por ejemplo:

[pic 2]

[pic 3][pic 4]

[pic 5]

[pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12][pic 13]

[pic 14]

El flujo de una red puede constar de muchos bienes o servicios distintos; por ejemplo, gas natural en un gasoducto, distribución de artículos de mayoristas a minoristas o entre fábricas y almacenes. El costo unitario del flujo para cada arco se denota como Cij para los nodos i y j.

En el caso de una red carretera, las ciudades son los nodos y las rutas de transporte entre las ciudades son los arcos; el costo por automóvil para cada ruta es el costo del flujo y existen casi siempre capacidades para cada arco que lo limitan a cierta cantidad de flujo.

Para un arco dirigido, puede usarse la misma técnica como una manera conveniente para reducir un flujo previamente asignado.

Asignación ficticia: flujo impuesto a través de un arco dirigido pero en dirección “equivocada”, con el objeto de registrar una reducción en el flujo que va en dirección “correcta”.

Por ejemplo, si se desea reducir el flujo en 2 unidades en la figura de la derecha, se tendría:

[pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22][pic 23][pic 24][pic 25][pic 26][pic 27][pic 28]

[pic 29][pic 30]

Red dirigida: red que tiene solamente arcos dirigidos.

Red no dirigida: red que tiene solamente arcos no dirigidos.

Una red con mezcla de arcos dirigidos y no dirigidos (o solamente con arcos no dirigidos) puede convertirse en una red dirigida, sustituyendo cada arco no dirigido por un par de arcos dirigidos en direcciones opuestas (después puede optarse por interpretar los flujos netos).

Trayectoria entre dos nodos: sucesión de arcos distintos que conectan dichos nodos, en la figura del parque, una de las trayectorias que conectan los nodos O y T es la sucesión de arcos: OB → BD → DT (o bien O → B → D → T).

Cuando algunos o todos los arcos de una red son arcos dirigidos, se hace la distinción entre:

Trayectoria dirigida: del nodo i al nodo j, es una sucesión de arcos cuya dirección (si la tienen) es hacia el nodo j, de manera que el flujo del nodo i al nodo j, a través de esta trayectoria, es factible.

...