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.

...