Redes

´ Tema 7: Optimizacion sobre Redes Muchos de los problemas de Investigaci´n Operativa pueden modelizaro se y resolverse sobre un grafo: conjunto de v´rtices o nodos conectados e con arcos y/o aristas. Dise˜ar el trazado de una red de fibra optica de manera que se n ´ ´ cubran ciertos puntos de la manera m´s econ´mica posible. Arbol a o generador de coste m´ ınimo. Determinar la ruta m´s cortaentre dos ciudades. Camino m´s a a corto. Determinar la cantidad m´xima de electricidad que se puede enviar a a trav´s de una red el´ctrica. Problema de flujo m´ximo. e e a Decidir el programa de fechas en el que deben iniciarse y terminarse una serie de tareas para llevar a cabo un proyecto. Camino cr´ ıtico (CPM).
1

Todos estos problemas se pueden modelizar como un Problema de Programaci´nLineal y resolverse con el Algoritmo del Simplex para o ıtulo 9) Redes (Bazaraa et al. 1990, Cap´ El algoritmo realiza las operaciones del Simplex directamente sobre el grafo lo que, en algunos casos, permite resolver problemas 200 o 300 veces m´s r´pido que el algoritmo del simplex normal. a a 7.1 Definiciones Un grafo consta de un conjunto de v´rtices (nodos), V , de un conjunto e e de aristas, E,y/o de un conjunto de arcos, A, que unen los v´rtices. Si en el grafo solamente hay: Aristas, se dice que es un grafo no dirigido. Arcos, se dice que es un grafo dirigido. En otro caso se trata de un grafo mixto.
2

Se denomina flujo a cualquier “bien” (tangible o no) que circule por las conexiones del grafo (o red) (electricidad, veh´ ıculo, mensaje, tiempo). Una ruta es una secuencia de arcosy/o aristas que unen dos v´rtices. e e Un ciclo es una ruta que une un v´rtice consigo mismo. Un grafo es conexo si cualquier pareja de v´rtices puede unirse con una e ruta sobre el grafo. ´ Un arbol generador es un subconjunto de |V | − 1 arcos que conecta todos los v´rtices del grafo y no contiene ciclos. e e Una cortadura se define a partir de un subconjunto de v´rtices S ⊆ V , como el conjuntode arcos (S, V \ S).

3

´ 7.2 Arbol generador de coste m´ ınimo ONO se est´ planteando trazar una red de televisi´n por cable para a o dar servicio a cinco nuevas areas recientemente urbanizadas. La si´ guiente figura representa los enlaces que podr´ establecerse entre las ıan cinco zonas. El coste asociado a cada arista indica los kil´metros de o cable que ser´ necesarios. La empresa deseaencontrar el trazado de ıan red de coste m´ ınimo.
From \ To Node1 Node2 Node3 Node4 Node5 Node6 Node1 Node2 1 Node3 5 6 Node4 7 4 5 8 Node5 9 3 10 3 Node6

4

Se puede resolver utilizando un algoritmo greedy por lo que no es necesaria la Programaci´n Lineal. o
2 1 9 1 6 5 3 7 5 3 4 10 8 6 3 5

4 (1, 2) −→ (2, 5) −→ (2, 4) −→ (4, 6) −→ (1, 3)

5

7.3 Problema de flujo de coste m´ ınimoDado G = (V, A) un grafo dirigido, V = {1, . . . , m} el conjunto de v´rtices y e A = {(i, j), . . . , i, j ∈ V }, su conjunto de arcos. En el que, Cada v´rtice tiene asociado un n´mero bi que representa la oferta o e u demanda en ese v´rtice de un determinado bien. e Si bi > 0, se dice que i es un v´rtice origen e Si bi < 0, se dice que i es un v´rtice destino e Si bi = 0, se dice que i es unv´rtice de transbordo e Cada arco tiene asociada una variable xij ≥ 0 que indica el flujo enviado desde i hasta j, y una cantidad cij que indica el coste de enviar una unidad desde i a j.
6

El Problema de Flujo de Coste M´ ınimo consiste en determinar c´mo enviar la oferta disponible a trav´s de la red a fin de satisfacer o e la demanda con un coste m´ ınimo. Min sa:
m i=1 m j=1 cij xij

m j=1xij −

m k=1

xki = bi , i = 1, 2, . . . , m

xij ≥ 0, ∀(i, j) Se trata del Problema del Transbordo introducido en el tema anterior. Hay situaciones en las que el flujo que puede pasar por cada arista est´ limitado, esto se traduce en cotas para las variables: a lij ≤ xij ≤ uij
7

´ 7.4 Problema de flujo maximo Determinar el flujo m´ximo que se puede enviar a trav´s de una red a e...