Capítulo 6 - Modelos de Redes PDF

Preview

Summary

ejercicios resueltos...

Description

C A P Í T U L O

6

Modelos de redes

Hay una multitud de situaciones, en investigación de operaciones, que se pueden modelar y resolver como redes (nodos conectados por ramas). Algunas encuestas recientes informan que hasta el 70% de los problemas de programación matemática en el mundo real se pueden representar como modelos relacionados con redes. La lista siguiente ilustra algunas aplicaciones posibles de las redes. 1. Diseño de una red de gasoductos marinos para conectar bocas de pozos en el Golfo de México con un punto de entrega en tierra. El objetivo del modelo es minimizar el costo de construcción del gasoducto. 2. Determinación de la ruta más corta entre dos ciudades, en una red de carreteras. 3. Determinación de la capacidad máxima (en toneladas anuales) de una red de tubería para lodo de carbón que une las minas en Wyoming con las centrales eléctricas en Houston. (Las tuberías de lodo de carbón transportan el carbón suspendido en agua a través de tubos de diseño especial.) 4. Determinación del programa de flujo con costo mínimo desde los campos petroleros hasta las refinerías a través de una red de oleoductos. 5. Determinación del cronograma (fechas de inicio y terminación) de las actividades en la construcción de un proyecto. La solución de esas situaciones y otras parecidas se logra con una variedad de algoritmos de optimización de redes. Este capítulo presentará cinco de esos algoritmos: 1. 2. 3. 4. 5.

Árbol de expansión mínima (situación 1). Algoritmo de la ruta más corta (situación 2). Algoritmo del flujo máximo (situación 3). Algoritmo de red capacitada con costo mínimo (situación 4). Algoritmo de la ruta crítica (situación 5). 213

214

Capítulo 6

Modelos de redes

Las situaciones en las que se pueden aplicar estos algoritmos también se pueden formular y resolver en forma de programas lineales explícitos. Sin embargo, los algoritmos propuestos, basados en redes, son más eficientes que el método símplex.

6.1

DEFINICIONES PARA REDES Una red consiste en una serie de nodos enlazados con arcos (o ramas). La notación para describir una red es (N, A), donde N es el conjunto de nodos y A es el conjunto de arcos. Por ejemplo, la red de la figura 6.1 se describe como sigue: N = 51, 2, 3, 4, 56 A = 511,22, 11,32, 12,32, 12,52, 13,42, 13,52, 14,22, 14,526

FIGURA 6.1 Ejemplo de una red (N, A)

1

3

5

2

4

Con cada red se asocia algún tipo de flujo (por ejemplo, flujo de productos petroleros en un oleoducto y flujos de tráfico de automóviles en carreteras). En general, el flujo en una red está limitado por la capacidad de sus arcos, que pueden ser finitos o infinitos. Se dice que un arco es dirigido u orientado si permite un flujo positivo en una dirección, y flujo cero en la dirección opuesta. Una red dirigida tiene todos sus arcos dirigidos. Una ruta es una sucesión de arcos distintos que unen dos nodos pasando por otros nodos, independientemente de la dirección de flujo en cada arco. Una ruta forma un ciclo si conecta un nodo consigo mismo, pasando por otros nodos. Por ejemplo, en la figura 6.1, los arcos (2,3), (3,5) y (5,2) forman un bucle o circuito cerrado. Un ciclo es dirigido si consiste en una ruta dirigida, por ejemplo (2,3), (3,4) y (4,2) en la figura 6.1. Una red conectada es aquella en que cada dos nodos distintos están enlazados al menos por una ruta. La red de la figura 6.1 es un ejemplo de este tipo. Un árbol es una red conectada que puede consistir sólo en un subconjunto de todos los nodos en ella, donde no se permiten ciclos, y un árbol de expansión es un árbol que enlaza todos los nodos de la red, también sin permitir ciclos. En la figura 6.2 se ven ejemplos de un árbol y de un árbol de expansión para la red de la figura 6.1. FIGURA 6.2 Ejemplos de un árbol y de un árbol de expansión, para la red de la figura 6.1

1

3

2 Árbol

1

3

2

5

4

Árbol de expansión

6.2 Algoritmo de árbol de expansión mínima

215

CONJUNTO DE PROBLEMAS 6.1A 1. Para cada red de la figura 6.3 determine a) una ruta, b) un ciclo, c) un ciclo dirigido, d) un árbol y e) un árbol de expansión. 2

FIGURA 6.3 Redes para el problema 1, conjunto 6.1a

3

1

5 4

1

3

2

4 (i)

(ii)

2. Determine los conjuntos N y A en las redes de la figura 6.3. 3. Trace la red definida por N = 51, 2, 3, 4, 5, 66 A = 511,22, 11,52, 12,32, 12,42, 13,52, 13,42, 14,32, 14,62, 15,22, 15,626

4. Hay ocho cuadrados iguales ordenados en tres renglones, cada uno con dos cuadrados en el primer renglón, cuatro en el segundo y dos en el tercero. Los cuadrados de cada fila están arreglados en forma simétrica respecto al eje vertical. Se desea poner números distintos en los cuadrados, entre los límites de 1, 2, ..., 8, de modo que no haya dos cuadrados adyacentes vertical, horizontal o diagonalmente que tengan números consecutivos. Use la representación en red como vehículo hacia la solución de una forma sistemática. 5. Se deben transportar en un bote tres reclusos escoltados por tres guardias, de San Francisco a la penitenciaría de la isla de Alcatraz, para que purguen sus sentencias. El bote no puede transportar más de dos personas en cualquier dirección. Los reclusos les ganan con seguridad a los guardias si su número es mayor en cualquier momento. Formule un modelo de red para diseñar los viajes del bote de modo que se asegure la transferencia segura de los reclusos. Suponga que no se fugan si tienen oportunidad.

6.2

ALGORITMO DE ÁRBOL DE EXPANSIÓN MÍNIMA El algoritmo de árbol de expansión mínima enlaza los nodos de una red, en forma directa o indirecta, con la mínima longitud de las ramas enlazantes. Una aplicación característica es en la construcción de carreteras pavimentadas que unen varias poblaciones. El camino entre dos poblaciones puede pasar por uno o más poblaciones adicionales. El diseño más económico del sistema de caminos indica que se minimice la distancia total de caminos pavimentados, resultado que se obtiene implementando el algoritmo de árbol de expansión mínima. Los pasos del procedimiento son los siguientes. Sea N ⫽ {1, 2, ..., n} el conjunto de nodos de la red, y se definen C k ⫽ Conjunto de nodos que se han conectado en forma permanente en la iteración k C k ⫽ Conjunto de nodos que todavía se deben conectar en forma permanente

216

Capítulo 6

Modelos de redes

Paso 0. El conjunto C0 = O y C0 = N . Paso 1. Comenzar con cualquier nodo en el conjunto C0 no conectado (o “inconexo”), e igualar C1 = 5i6 , con lo que C1 = N - 5i6 . Igualar k ⫽ 2. Paso general k. Seleccionar un nodo j* en el conjunto no conectado Ck - 1 que produzca el arco más corto a un nodo, en el conjunto conectado C k⫺1. Enlazar a j* en forma permanente con Ck⫺1 y sacarlo de Ck - 1 , esto es Ck = Ck - 1 + 5j*6, Ck = Ck - 1 - 5j*6

Si el conjunto Ck, de nodos no conectados es vacío, detenerse. En cualquier otro caso, igualar k ⫽ k ⫹ 1 y repetir el paso. Ejemplo 6.2-1 Midwest TV Cable Company está en el proceso de proporcionar servicio de cable a cinco nuevas áreas habitacionales. La figura 6.4 representa los enlaces posibles de TV entre las cinco áreas. Las millas de cable se muestran en cada arco. Determine la red de cable más económica. El algoritmo comienza en el nodo 1 (cualquier otro nodo podría ser), con lo que se obtiene C1 = 516, C1 = 52, 3, 4, 5, 66

Las iteraciones del algoritmo se resumen en la figura 6.5. Los arcos con línea delgada son todos los enlaces posibles entre C y C. Las ramas gruesas representan los enlaces permanentes entre los nodos del conjunto conectado (o “conexo”) C, y la rama con línea interrumpida representa el nuevo enlace (permanente) que se agrega en cada iteración. Por ejemplo, en la iteración 1, la rama (1,2) es la más corta (⫽ 1 milla) entre todas las ramas posibles del nodo 1 a los nodos 2, 3, 4 y 5 del conjunto no conectado C1. Por consiguiente, el enlace (1,2) se vuelve permanente y j * ⫽ 2, con lo que se obtiene C2 = 51, 26, C2 = 53, 4, 5, 66

La solución se expresa con el árbol de expansión mínima que se ve en la iteración 6, de la figura 6.5. La cantidad mínima de millas necesarias para proporcionar el servicio de cable que se desea resulta ser 1 ⫹ 3 ⫹ 4 ⫹ 3 ⫹ 5 ⫽ 16 millas.

FIGURA 6.4

3 (millas)

2

Conexiones de cable para la Midwest TV Cable Company

1

4

5 6

9 1 5 7

10

3 5

6 8 3

4

6.2 Algoritmo de árbol de expansión mínima C1

1

C1

5

4

6

7

5

6

6

8

7

1

3

Iteración 4

3

5

6

C5 6 4

Iteración 5

3

2 C5

10

5 5

6

5 4

3

C4

3

5

1

Iteración 3

4

C4

4

4

2

5

6

1

C3

3

3

2 C3

5

4 Iteración 2

3

1

6

7

Iteración 1

4

3

5

1

4

2

5

6

9

3

5

1

3

2 1

9

1

1

C2

C2 2

217

1 1

4 5

3

5 Ramas alternas 6

5 3

3 4

Iteración 6 (árbol de expansión mínimo)

FIGURA 6.5 Iteraciones de la solución para la Midwest TV Cable Company

Se puede usar TORA para generar las iteraciones del árbol de expansión mínima. En el menú Main menu (menú principal) seleccione, Network models 1 (modelos de red/árbol de expansión mínima). A continuación en el menú SOLVE/MODIFY (resolver/modificar), seleccione Solve problem 1 Go to output screen (resolver el problema/ir a la pantalla de resultados). En la pantalla de resultados seleccione un Starting node (nodo de inicio) y a continuación use Next iteration (iteración siguiente) o All iterations (todas las iteraciones) para general las iteraciones sucesivas. Puede usted recomenzar las iteraciones seleccionando un nuevo Starting node (nodo de inicio). La figura 6.6 muestra los resultados de TORA para el ejemplo 6.2-1 (archivo ch6ToraMinSpanExp6-2-1.txt).

218

Capítulo 6

Modelos de redes

FIGURA 6.6 Resultados del árbol de expansión mínima del ejemplo 6.2-1

CONJUNTO DE PROBLEMAS 6.2A 1. Resuelva el ejemplo 6.2-1 comenzando en el nodo 5 (en lugar del nodo 1) y demuestre que con el algoritmo se obtiene la misma solución. 2. Determine el árbol de expansión mínima de la red del ejemplo 6.2-1 bajo cada una de las siguientes condiciones por separado: a) Los nodos 5 y 6 están unidos por un cable de 2 millas. b) Los nodos 2 y 5 no se pueden enlazar. c) Los nodos 2 y 6 están unidos por un cable de 4 millas. d) El cable entre los nodos 1 y 2 tiene 8 millas de longitud. e) Los nodos 3 y 5 están unidos por un cable de 2 millas. f) El nodo 2 no se puede enlazar en forma directa con los nodos 3 y 5. 3. En el transporte intermodal, los camiones remolque cargados se mueven entre las terminales de ferrocarril colocando la caja en carros especiales (“camas bajas”). La figura 6.7 muestra la ubicación de las principales terminales de ferrocarril en Estados Unidos, y las vías actuales de FC. El objetivo es decidir cuáles vías se deben “revitalizar” para manejar el tráfico intermodal. En especial, se debe unir la terminal de Los Ángeles (LA) en forma directa con la de Chicago (CH) para dar cabida al intenso tráfico esperado. Por otra parte, todas las terminales restantes se pueden enlazar, en forma directa o indirecta, de tal modo que se minimice la longitud total (en millas) de las vías seleccionadas. Determine los segmentos de vías de ferrocarril que se deben incluir en el programa de revitalización.

6.2 Algoritmo de árbol de expansión mínima

219

SE 2000 1100

1300 1000

DE

800 NY 200

CH

DC

2000 LA

2600

780 900

1300

1400

FIGURA 6.7

DA

Red para el problema 3, conjunto 6.2a

4. En la figura 6.8 se ven las distancias, en millas, de las conexiones factibles que unen nueve pozos marinos de gas natural con un punto de entrega en tierra. Como la ubicación del pozo 1 es la más cercana a la costa, tiene capacidad de bombeo y de almacenamiento suficiente para bombear la producción de los ocho pozos restantes hasta el punto de entrega. Determine la red mínima de tubería que una las bocas de pozo con el punto de entrega.

FIGURA 6.8

Punto de entrega

Red para el problema 4, conjunto 6.2a 5

2

1

9

6

4

20 3

15 14

5

10

15

9

6

20

8

5

4

12 3

7

5 13

7

7

6

5. En la figura 6.8 del problema 4, suponga que los pozos se pueden dividir en dos grupos, dependiendo de la presión del gas: un grupo de alta presión, que comprende los pozos 2, 3, 4 y 6, y un grupo de baja presión, que comprende los pozos 5, 7, 8 y 9. Debido a la diferencia de presiones, no se pueden enlazar pozos de grupo diferente. Al mismo tiempo, ambos grupos se deben conectar con el punto de entrega pasando por el pozo 1. Determine la red mínima de tubería para este caso. 6. Electro produce 15 partes electrónicas en 10 máquinas. La empresa desea agrupar las máquinas en celdas, diseñadas para minimizar las “desigualdades” entre las partes procesadas en cada cel-

220

Capítulo 6

Modelos de redes

da. Una medida de la “desigualdad” dij entre las partes procesadas en las máquinas i y j se puede expresar como sigue: nij dij = 1 nij + mij siendo nij la cantidad de partes compartidas entre las máquinas i y j, y mij es la cantidad de partes que sólo se usan ya sea en la máquina i o en la j. La tabla siguiente asigna las partes a las máquinas: Máquina

Partes asignadas

1 2 3 4 5 6 7 8 9 10

1, 6 2, 3, 7, 8, 9, 12, 13, 15 3, 5, 10, 14 2, 7, 8, 11, 12, 13 3, 5, 10, 11, 14 1, 4, 5, 9, 10 2, 5, 7, 8, 9, 10 3, 4, 15 4, 10 3, 8, 10, 14, 15

a) Exprese el problema como modelo de red. b) Demuestre que la determinación de las celdas se puede basar en la solución del árbol de expansión mínima. c) Para los datos de la tabla anterior, construya las soluciones con dos y tres celdas.

6.3

PROBLEMA DE LA RUTA MÁS CORTA En el problema de la ruta más corta se determina ésta, entre una fuente y un destino, en una red de transporte. Hay otras soluciones que se pueden representar con el mismo modelo, como se ve en los ejemplos siguientes.

6.3.1

Ejemplos de aplicaciones de ruta más corta Ejemplo 6.3-1 (Reemplazo de equipo) RentCar está desarrollando un plan de reposición de su flotilla de automóviles para un horizonte de planeación de 4 años, que comienza el 1 de enero de 2001 y termina el 31 de diciembre de 2004. Al iniciar cada año se toma la decisión de si un auto se debe mantener en operación o se debe sustituir. Un automóvil debe estar en servicio durante 1 año como mínimo, y 3 años como máximo. La tabla siguiente muestra el costo de reposición en función del año de adquisición del vehículo y los años que tiene en funcionamiento. Equipo adquirido al comenzar 2001 2002 2003 2004

Costo de reposición ($) para los años en operación 1

2

3

4000 4300 4800 4900

5400 6200 7100 —

9800 8700 — —

6.3 Problema de la ruta más corta

221

9800 5400 1

4000

7100 4300

2

4800

3

4900

4

5

FIGURA 6.9 El problema de reemplazo de equipo como problema de ruta más corta

6200 8700

El problema se puede formular como una red, en el que los nodos 1 a 5 representan el inicio de los años 2001 a 2005. Los arcos del nodo 1 (año 2001) sólo pueden alcanzar los nodos 2, 3 y 4, porque un vehículo debe estar en funcionamiento entre 1 y 3 años. Los arcos desde los otros nodos se pueden interpretar en forma parecida. La longitud de cada arco es igual al costo de reposición. La solución del problema equivale a determinar la ruta más corta entre los nodos 1 y 5. En la figura 6.9 se ve la red que resulta. Si se usa TORA,1 la ruta más corta, que se indica con la ruta gruesa, es 1 S 3 S 5 . Eso quiere decir que un automóvil adquirido al iniciar 2001 (nodo 1) se debe reemplazar pasados 2 años, al iniciar 2003 (nodo 3). El auto de reposición debe estar en servicio hasta el final de 2004. El costo total de esta política de reposición es $12,500 (⫽ $5400 ⫹ $7100).

Ejemplo 6.3-2 (Ruta más segura) I.Q. Smart conduce diariamente hacia su trabajo. Como acaba de terminar un curso de análisis de redes, puede determinar la ruta más corta. Desafortunadamente, la ruta seleccionada está muy patrullada por la policía, y debido a las multas por manejar a alta velocidad, podría ser que la ruta más corta no sea la mejor elección. Smart decide entonces escoger una ruta que maximice la probabilidad de no ser detenido por la policía. La red de la figura 6.10 muestra las rutas posibles para ir y regresar del trabajo, y las probabilidades correspondientes de no ser detenido en cada segmento. La probabilidad de no ser detenido en el trayecto hacia el trabajo es el producto de las probabilidades relacionadas con los segmentos sucesivos de la ruta seleccionada. Por ejemplo, la probabilidad de no recibir

2 .2

.8

.35

4

.6

.9

3

.3

FIGURA 6.10 Modelo de red de la ruta más segura

.5

.4

.1

1

6

7 5

.25

1En Main menu (menú principal), seleccione Network models 1 Shortest route (modelos de red/ruta más corta). En el menú SOLVE/MODIFY (resolver/modificar), seleccione Solve problem 1 Shortest routes (resolver problema/ruta más corta).

222

Capítulo 6

Modelos de redes

2 .69897

FIGURA 6.11 Representación de la ruta más segura como modelo de ruta más corta

.09691

.45593

4

.22185 1.

1 .04576

3

6

.30103

.39794

.52288

5

7 .60206

una multa en la ruta 1 S 3 S 5 S 7 es 0.9 ⫻ 0.3 ⫻ 0.25 ⫽ 0.0675. El objetivo de Smart es seleccionar la ruta que maximice la probabilidad de no ser multado. Se puede formular el problema como un modelo de ruta más corta aplicando una transformación logarítmica que convierta la probabilidad producto en la suma de los logaritmos de las probabilidades; es decir, si p1k ⫽ p 1 ⫻ p 2 ⫻ · · · ⫻ pk es la probabilidad de no ser detenido, entonces log p1k ⫽ log p 1 ⫹ log p2 ⫹ · · · ⫹ log p k. Matemáticamente, la maximización de p1k equivale a la maximiza...