Programación Lineal 6c3o3j

Unidad 2: Modelos en redes 2.1.

Definiciones b´ asicas de redes

Definici´ on 1 (Conceptos b´ asicos en redes) En esta unidad haremos uso de los siguientes conceptos: • Red no dirigida es un objeto G = (N, A), con N un conjunto no vac´ıo de elementos llamados nodos y A conjunto de subconjuntos no vac´ıos de a lo m´as dos elementos de N , los cuales se llaman aristas. • Red dirigida es un objeto D = (N, A), con N un conjunto no vac´ıo de elementos llamados nodos y A un conjunto de pares ordenados de elementos de N llamados arcos. • Si cada arista de una red tiene asociado un peso que representa una distancia, o un costo asociado al par de nodos unidos por la arista, o un flujo que circula desde el nodo inicial hacia el nodo final del arco, entonces la red se llama ponderada. • En una red un par de nodos se llaman adyacentes, si existe una arista (arco) que los une. • Una red es conexa si para cualesquiera par de nodos a, b de la red, existe una sucesi´on de nodos que inicia en a y termina en b, tal que cualquiera dos nodos consecutivos de la sucesi´on son adyacentes. • Ciclo en una red es una sucesi´on de nodos, con nodos inicial y final iguales, y en la que cualquiera dos nodos sucesivos son adyacentes. ´ • Arbol es una red conexa sin ciclos. ´ • Arbol de expansi´on de una red G con n nodos es una red que contiene a todos los nodos de G y n − 1 aristas de G.

2.2.

El modelo de transporte

El modelo de transporte Consid´erense m lugares llamados or´ıgenes donde hay disponibilidad de un cierto bien y n lugares llamados destinos donde hay demanda del mismo bien. Se conocen la oferta del origen i, la demanda del destino j, y la tabla de costos de transporte, la cual contiene los costos unitarios de transporte del bien desde el origen i hasta el destino j, i = 1, . . . , m, j = 1, . . . , n. Bajo la condici´on que la oferta total es igual a la demanda total, se debe transportar los bienes desde los or´ıgenes hasta los destinos sin exceder las disponibilidades y satisfaciendo la demanda, con un costo total de transporte m´ınimo. Las variables en un problema de transporte corresponden a cantidades de unidades del art´ıculo considerado a transportar entre cada origen y destino del problema. El modelo de programaci´on lineal para el problema de transporte es: xij : unidades a transportar desde el origen i hasta el destino j, i = 1, . . . m, j = 1, . . . , n

P

min

cij xij

i,j

s.a. n P

xij = ai , i = 1, . . . , m

j=1 m P

xij = bj , j = 1, . . . , n

i=1

xij ≥ 0, i = 1, . . . , m j = 1, . . . , n La situaci´on planteada en un problema de transporte puede ser representada mediante una red o una tabla como se muestra a continuaci´on: Red del problema de transporte Or´ıgenes

Destinos c1,1

a1 1

1

b1

j

bj

n

bn

c1,j c1,n ci,1 ci,j

ai i

ci,n cm,1 cm,j

am m

cm,n

Tabla de un modelo de transporte Tiene una cantidad de filas igual a la cantidad de or´ıgenes y una cantidad de columnas igual a la cantidad de destinos. En cada entrada de la tabla se coloca el costo de transporte unitario del origen de la fila al destino de la columna, y el valor de la variable del problema correspondiente al origen y destino. Ejemplo 1 Una compa˜ n´ıa de aerol´ıneas puede comprar gasolina a tres proveedores. Los proveedores disponen de 2000, 2000, y 6000 galones respectivamente. La compa˜ n´ıa necesita gasolina en tres localidades, las cuales requieren 5000, 3000 y 2000 galones. El precio en cienes de d´olares por cada mil galones entregados en cada localidad es como se indica en la tabla: ``` `

```

Proveedor

Localidad ```

1 2 3

```

` `

1

2

3

2 4 1

3 2 8

1 5 9

Balanceo de un problema de transporte En caso que la oferta total y la demanda total sean distintas, es posible transformar el problema para obtener un problema equilibrado, como sigue: Si la oferta total es mayor que la demanda total, se agrega un destino ficticio con demanda igual a la oferta total menos la demanda total. En la soluci´on los embarques hacia el destino ficticio tienen el caracter de oferta no distribuida. En caso que la oferta total sea menor que la demanda total, se agrega un origen ficticio con oferta igual a la demanda total menos la oferta total. En la soluci´on los embarques desde el origen ficticio tienen el caracter de demanda no satisfecha. En ambos casos si no hay informaci´on acerca de penalidades por no distribuci´on o no satisfacci´on de la demanda, se le asigna costo cero a las asignaciones que llegan o parten de un nodo ficticio. Definici´ on 2 (Plan de embarque factible) Plan de embarque factible es una asignaci´on de valores a las variables del problema que satisfacen las restricciones del problema de transporte. Ejemplo 2 Una tabla del modelo de transporte del ejemplo 1 con un plan de embarque inicial es: 2

3

1

4

2

5

1

8

9

2000 2000 1000

2.3.

3000

2000

Soluci´ on del modelo de transporte

El modelo de transporte se resuelve usando el m´etodo de escal´on, cuyo primer paso es la determinaci´on de un plan de embarque factible inicial que tenga m + n − 1 celdas no vacias. Para esto pueden usarse varios m´etodos, entre los cuales est´a el m´etodo de la esquina noroeste.

Obtenci´ on de un plan de embarque factible inicial M´ etodo de la esquina noroeste 1. Ub´ıquese en la celda noroeste de la tabla de transporte. 2. Asigne a la celda actual el valor m´ınimo entre oferta y demanda de la celda. 3. Actualice la oferta de la fila rest´andole el m´ınimo anterior. 4. Actualice la demanda de la columna rest´andole el m´ınimo anterior. 5. En caso que tanto oferta como demanda de la celda actual quedaron en cero • Si la celda est´a en la u ´ltima fila y columna, entonces termine pues el plan de embarque actual es factible con m + n − 1 celdas ocupadas. • En caso contrario pase a la celda inmediata inferior o inmediata derecha y regrese al paso 2.

6. En caso que solo la oferta de la celda quedara en cero • Si la celda est´a en la u ´ltima fila, entonces termine pues el plan de embarque actual es factible con m + n − 1 celdas ocupadas. • En caso contrario pase a la celda inmediata inferior y regrese al paso 2. 7. En caso que solo la demanda de la celda quedara en cero • Si la celda est´a en la u ´ltima columna, entonces termine pues el plan de embarque actual es factible con m + n − 1 celdas ocupadas. • En caso contrario mu´evase a la celda inmediata derecha y regrese al paso 2.

Soluci´ on del modelo de transporte El algoritmo de escal´ on 1. Determine un plan de embarque factible con m + n − 1 celdas no vac´ıas y sin ciclos. 2. Calcule los costos reducidos • Para cada celda vac´ıa: • Determine el u ´nico ciclo que inicia y termina en esa celda y rec´orralo a partir de la celda vac´ıa asign´andole + y - alternativamente a cada celda del ciclo. • Calcule el costo reducido de la celda recorriendo las celdas del ciclo anterior sumando, si el signo es +, o restando, si el signo es -, los costos de cada celda sobre el ciclo. 3. Investigue la optimalidad • Determine el m´ınimo de los costos reducidos calculados en el paso anterior. • Si el m´ınimo anterior es no negativo, detenga el proceso y diga que el plan de embarque actual es o´ptimo. En caso contrario contin´ ue. 4. Construya un plan de embarque mejorado • Llame celda entrante a aquella que tenga el menor de los costos reducidos. • Llame celda saliente a aquella donde ocurre el m´ınimo de todos los valores en las celdas con signo - en el ciclo de la celda entrante. • Asigne a la celda entrante el valor del m´ınimo anterior y declare vac´ıa la celda saliente. • Actualice los valores de las restantes celdas en el ciclo restando el m´ınimo anterior en las celdas con signo - y sum´andolo a las celdas con +. 5. Regrese al paso 2. Ejemplo 3 Resuelva el modelo de transporte del ejemplo 1 usando el m´etodo de escal´on Soluci´on

Iter.

1

2

2 2000 Tabla

3 -6

4 2000

2 -9

4 2000

9 2000

3 3

5

8 3000

2 9

-7

1 1000

1 -9

3

2 -9

1 3000

1 2000 5 -7

8 3000

2 9 4 9

9 0

3 3 2 2000

1 5000

1 2000 5 2

8 1000

9 0

Soluci´on o´ptima: Pro. 1 2 3 3

2.4.

Loc. Emb.(gln.) 3 2000 2 2000 1 5000 2 1000 Costo m´ınimo

Costo ($) 200 400 500 800 1900

El modelo de asignaci´ on

Definici´ on 3 (El modelo de asignaci´ on) Consid´erense dos grupos cada uno con n objetos, cuyos elementos deben ser asociados entre si. Es conocida la matriz de costos, cuyos elementos son los costos de asociar cada objeto del primer grupo con cada objeto del segundo grupo. Se debe asociar uno a uno los objetos de ambos grupos, de tal manera que el costo total de asociaci´on sea m´ınimo. Ejemplo 4 Una cia. de contabilidad tiene un especialista en impuestos en cada una de sus oficinas en las ciudades A, B, C, D, y ha recibido una solicitud para un especialista en impuestos de cada uno de sus clientes E, F, G, H, I. Los costos de viaje, en miles de d´olares, para llegar a cada uno de los clientes desde las ciudades se dan en la tabla al final. Determine como distribuir los especialistas entre los clientes para minimizar los costos totales de viaje.

XXX XXX Cliente XXX Ciudad XXX

A B C D

2.5.

E

F

G

H

I

25 20 28 30

24 22 25 23

30 30 28 25

38 32 30 30

40 40 28 30

El m´ etodo h´ ungaro para el modelo de asignaci´ on

1. Construya la matriz reducida inicial

• Reste a cada elemento de la matriz de costos el m´ınimo de la fila. • En la matriz resultante del paso anterior reste a cada elemento de la matriz el m´ınimo de la columna. 2. Investigue la optimalidad • Trace el menor n´ umero de l´ıneas horizontales y/o verticales para cubrir todas la celdas cero de la matriz reducida. • Si el menor n´ umero de lineas para cubrir todos los ceros de la matriz reducida es igual a n, encuentre un grupo de n celdas con cero, las cuales no comparten la misma fila ni la misma columna y detenga el proceso pues la asignaci´on que corresponde a esas celdas es ´optima. En caso contrario contin´ ue. 3. Construya la nueva matriz reducida • Determine el m´ınimo valor en las celdas no cubiertas por las l´ıneas trazadas antes. • Reste el m´ınimo anterior a cada celda no cubierta y s´ umelo a cada celda cubierta por dos l´ıneas. 4. Regrese al paso 2. Ejemplo 5 Resuelva el problema de asignaci´on del ejemplo 4 usando el m´etodo h´ ungaro Soluci´on: Paso 1: 25 20 28 30 0

24 22 25 23 0

30 30 28 25 0

38 32 30 30 0

40 40 28 30 0

24 20 25 ⇒ 23 0

1 0 3 7 0 0

0 2 0 0 0 0

6 10 3 2 0 0

14 12 5 7 0 0

16 20 3 7 0 0

Pasos 2-3: 1 0 3 7 0

0 2 0 0 0

6 10 3 2 0

14 12 5 7 0

16 20 3 7 0

⇒

Soluci´on o´ptima: Ciudad A B C D Costo

Cliente F E I G total

Costo 24 20 28 25 97

1 0 3 7 2

0 2 0 0 2

4 8 1 0 0

12 10 3 5 0

14 18 1 5 0

⇒

1 0 3 7 3

0 2 0 0 3

4 8 1 0 1

11 9 2 4 0

13 17 0 4 0

2.6.

El modelo del ´ arbol de expansi´ on m´ınimo

Definici´ on 4 (El modelo del ´ arbol de expansi´ on m´ınimo) Con el modelo del ´arbol de expansi´on m´ınimo se busca determinar, para una red ponderada G, un a´rbol de expansi´on con peso total m´ınimo

2.7.

Soluci´ on del modelo del ´ arbol de expansi´ on m´ınimo

Algoritmo de Prim 1. Defina el ´arbol T con conjuntos de v´ertices y aristas ambos vac´ıos. 2. Elija arbitrariamente un v´ertice u de G y agr´eguelo al ´arbol T . 3. Determine la arista e de menor peso entre un v´ertice v de T y un v´ertice w de G fuera de T . 4. Agregue el v´ertice w y la arista e a T . 5. Si T tiene n − 1 aristas termine, pues T es ´arbol de expansi´on m´ınimo. En caso contrario vaya al paso 3. Ejemplo 6 Midwest TV Cable Company est´a en el proceso de proporcionar servicio de cable a cinco nuevas a´reas habitacionales. La figura representa los enlaces posibles de TV entre las seis ´areas. Las millas de cable se muestran en cada arco. Determine la red de cable m´as econ´omica. 5 5 1

3

4

2 1

4 4

3

2 3 Soluci´on:

9

6

6

1 1.

1

2

3.

2 2

2

1

1

2

1 5.

2.

1

2

4.

4 3

4

1

3

2

3

1

3

3

5

5 4

3

6.

1

6

2 2

4

1

3 3

4 6

Soluci´on Arista 1,3 2,3 2,5 3,4 4,6 Peso m´ınimo

2.8.

Peso 2 1 5 3 4 15

El modelo de la ruta m´ as corta

Definici´ on 5 (Modelo de la ruta m´ as corta) El modelo de la ruta m´as corta en una red dirigida determina la distancia m´as corta y la ruta correspondiente para llegar de un v´ertice a otro en la red.

2.9. 2.9.1.

Soluci´ on del modelo de la ruta m´ as corta Algoritmo de Dijkstra

Este algoritmo considera una red ponderada con nodos no aislados y calcula para un nodo s de inicio las distancias y caminos m´as cortos de s a cualquier nodo de la red. Aqu´ı se denota con:

• V , al conjunto de nodos de la red • w(u, v), al peso del arco que va del nodo u al nodo v • Au , al conjunto de todos los nodos adyacentes al nodo u, llamada lista de adyacencia de u. • d(v), la distancia m´as corta desde el nodo de inicio s al nodo v de la red • c(v), al camino m´as corto desde el nodo de inicio s al nodo v de la red. Algoritmo de Dijkstra 1. Haga d(s) = 0, p(s) = s y T = V 2. Para todo nodo v ∈ V − {s}, haga d(v) = ∞ 3. Mientras T 6= ∅ • Determine alg´ un nodo u ∈ T tal que d(u) es minimal • Haga T = T − {u} • Para todo v ∈ T ∩ Au , • Si d(v) > d(u) + w(u, v), haga d(v) = d(u) + w(u, v) y p(v) = u 4. Para todo nodo v ∈ V • Haga r = v y inserte r en c(v) • Mientras p(r) 6= s • Inserte p(r) al inicio de c(v) • Haga r = p(r) • Inserte s al inicio de c(v) Ejemplo 7 Para la red de la figura determine las rutas y distancias m´as cortas desde el nodo 1 a cualquier otro nodo de la red 1 1

2

4 4

5

4

8

3

5 5

Soluci´on La aplicaci´on del algoritmo se registra en la tabla siguiente:

Iteraci´on 0 1 2 3 4 5

u 1 2 3 4 5

p T 1, 2, 3, 4, 5 2, 3, 4, 5 3, 4, 5 4, 5 5 ∅

1 d(1) 0 0 0 0 0 0

1 d(2) ∞ 1 1 1 1 1

1 d(3) ∞ 5 5 5 5 5

2 d(4) ∞ ∞ 5 5 5 5

3 d(5) ∞ ∞ ∞ 10 10 10

Las distancias y rutas m´as cortas a partir del nodo 1 son: Hacia 1 2 3 4 5

Distancia 1 1 5 5 10

Camino 1 1, 2 1, 3 1, 2, 4 1, 3, 5

Ejemplo 8 (Problema de reemplazo de equipo) Acabo de comprar un auto nuevo por $12,000. El costo de mantener un auto durante una a˜ no depende de su edad al comienzo del a˜ no, a como se indica en la tabla. Para evitar costos de mantenimiento altos con un auto muy antiguo, podr´ıa entregar a cuenta mi auto y comprar uno nuevo. El precio que recibo por dejar a cuenta mi auto, depende de la edad del auto al momento del intercambio, a como tambi´en se indica en la tabla. Para simplificar los c´alculos asuma que en cualquier momento el costo de un auto nuevo es $ 12,000. El objetivo es minimizar el costo neto de poseer auto durante los cinco a˜ nos siguientes, momento en que el auto poseido ser´a vendido. Formule este problema como uno de trayectoria m´as corta. Costo de mantenimiento Edad del auto Costo 0 2000 1 4000 2 5000 3 9000 4 12000

Precio de intercambio Edad del auto Precio 1 7000 2 6000 3 2000 4 1000 5 0

Soluci´on Se definen los nodos 0, . . . , 5, representando el nodo i el momento inicial del a˜ no i + 1, i=1,. . . ,5 Se definen los arcos (i, j) para 0 ≤ i < j ≤ 5, representando este la estrategia parcial de comprar un auto nuevo en el momento i y este mismo venderlo en el momento j. Cada arco (i, j) tiene asociado el costo cij que se calcula sumando al costo de compra del auto en el momento i, la suma de los costos por mantenimiento, y restando el precio de intercambio de un auto que se vende con edad j − i. Note que una estrategia completa de mantenimiento del auto durante los 5 a˜ nos est´a representada

por una ruta que va desde el nodo 0 hasta el nodo 5. As´ı el problema planteado es el de determinar la ruta m´as corta desde 0 hasta 5 en la red siguiente: 44 31 12 0

1

7

31

12

12

2

7

21

7

12

3

7

21

4

7

5

21

Ejemplo 9 Juan conduce diariamente hacia su trabajo. Como acaba de terminar un curso de an´alisis de redes, puede determinar la ruta m´as corta. Desafortunadamente, la ruta seleccionada est´a muy patrullada por la polic´ıa, y debido a las multas por manejar a alta velocidad, podr´ıa ser que la ruta m´as corta no sea la mejor elecci´on. Juan decide entonces escoger una ruta que maximice la probabilidad de no ser detenido por la polic´ıa. La red de la figura muestra las ruta posibles para ir y regresar del trabajo y las probabilidades de no ser detenido por la polic´ıa en cada tramo. Se trata de modelar el problema de minimizar la probabilidad de ser detenido por la polic´ıa como un problema de ruta m´as corta. 0.8

2

4

0.35

6

0.2

0.5

1

0.1

0.1

0.4

7

0.9

0.25 3

0.3

5

Soluci´on En una ruta la probabilidad que la polic´ıa no detenga a Juan es el producto de las probabilidades de cada uno de los tramos. Asi el logaritmo de la probabilidad de que en una ruta Juan no sea detenido es la suma de los logaritmos de las probabilidades. Dado que el m´aximo de los productos es igual a menos el m´ınimo de los productos sobre las rutas, el problema se resuelve planteando un problema de ruta m´as corta en la misma red anterior asign´andole como peso a cada arco el negativo del logaritmo de la probabilidad original.

2.9.2.

Algoritmo de Floyd

Este algoritmo considera una red ponderada con nodos no aislados y calcula las distancias y caminos m´as cortos entre cualquier par de nodo de la red.

Algoritmo de Floyd (para determinar rutas m´ as cortas en una red dirigida G) 1. Defina la matriz de distancia inicial D(0) y la matriz S (0) de secuencia de nodos. (0) • Para i, j = 1, . . . , n, i 6= j, asigne a Dij la distancia directa del v´ertice i al v´ertice j, poniendo infinito si no hay arco de i a j. Bloqu´ee las entradas diagonales. (0)

• Para i, j = 1, . . . , n, i 6= j, asigne Sij = j y bloqu´ee las entradas diagonales. 2. Haga k = 1 3. Defina la fila k y la columna k como fila y columna pivote 4. Construya D(k) y S (k) . (k−1) • Para cada elemento dij de D(k−1) que no sea diagonal, ni est´e en la fila o columna (k−1) (k−1) (k−1) (k−1) (k−1) pivote, si dij > dik + dkj , llene la posici´on ij de D(k) con dik + dkj y la (k)

posici´on ij de sij con el valor k. Todas las dem´as posiciones de D(k) y S (k) son iguales a las de D(k−1) y S (k−1) . 5. Haga k = k + 1 6. Si k < n + 1, regrese al paso 3. En caso contrario obtenga la soluci´on y termine. Obtenci´on de la soluci´on • La distancia m´as corta del v´ertice i al v´ertice j de la red se toma de la entrada (i, j) de la matriz D(n) . • La ruta m´as corta del v´ertice i al v´ertice j se obtiene de la siguiente manera: • Defina la ruta inicial como i, j y como incompleta. • Hasta que la ruta este completa: (n) ◦ Si existen dos v´ertices consecutivos u, v de la ruta con Suv distinto de v, entonces (n) inserte Suv entre u y v en la ruta. ◦ En caso contrario declare completa la ruta. Ejemplo 10 Para la red de la figura determine las rutas m´as cortas entre cada par de nodos. En los arcos aparecen distancias en millas. El arco (3, 5) es direccional, por lo que no se permite trafico alguno del nodo 5 al nodo 3. Todos los dem´as arcos permiten tr´afico en ambas direcciones. 3 1

2

5 6

10

4

3

4 5

15

Soluci´on: 3 10 ∞ ∞

3 10 8 ∞

3 10 8 12

3 ∞ 5 ∞

D0 10 ∞ ∞ 5 6 6 ∞ 4

3 13 5 ∞

D2 10 13 6 ∞

3 11 5 9

D4 10 11 6 10

8 5 6 4

8 5 6 4

∞ ∞ 15 4 -

∞ ∞ 15 4 -

12 9 10 4 -

1 1 1 1

1 1 2 1

1 1 2 4

2 2 2 2

S0 3 3 3 3

4 4 4 4

5 5 5 5 -

3 10 ∞ ∞

2 1 2 2

S2 3 1 3 3

2 4 2 4

S4 3 4 3 4

1

2

3

4

5

3 10 8 12

3 11 5 9

10 11 6 10

8 5 6 4

12 9 10 4 -

2 4 4 4

5 5 5 5 -

2 4 4 4

3 10 8 ∞

4 4 4 5 -

3 10 8 12

3 13 5 ∞

D1 10 ∞ 13 5 6 6 ∞ 4

3 13 5 ∞

D3 10 13 6 ∞

3 11 5 9

D5 10 11 6 10

8 5 6 4

8 5 6 4

Distancias m´as cortas ``` ``` ```Nodo final ``` Nodo inicial `` `

1 2 3 4 5

Rutas m´as cortas ``` ``` ```Nodo final ``` Nodo inicial `` `

1 2 3 4 5

1

2

3

4

5

2,1 3,1 4,2,1 5,4,2,1

1,2 3,4,2 4,2 5,4,2

1,3 2,4,3 4,3 5,4,3

1,2,4 2,4 3,4 5,4

1,2,4,5 2,4,5 3,4,5 4,5 -

∞ ∞ 15 4 -

25 28 15 4 -

12 9 10 4 -

1 1 1 1

1 1 2 1

1 1 2 4

2 1 2 2

S1 3 1 3 3

4 4 4 4

5 5 5 5 -

2 1 2 2

S3 3 1 3 3

2 4 4 4

3 3 5 5 -

2 4 2 4

S5 3 4 3 4

2 4 4 4

4 4 4 5 -

2.10.

El modelo de flujo m´ aximo

Definici´ on 6 (problema de flujo m´ aximo, PFM) Consid´erese una red D = (N, A) con m nodos y n arcos a trav´es de la cual fluye un solo tipo de bien. Llamamos flujo atravesando el arco (i, j) a la cantidad de unidades del bien que pasa por el arco (i, j). Con cada arco (i, j) de la red est´a asociado una cota inferior entera lij = 0 y una cota superior entera uij , las cuales son las cantidades m´ınima y m´axima de flujo que puede atravesar el arco (i, j) de la red. Se desea determinar la cantidad m´axima de flujo que puede enviarse desde el nodo 1 al nodo m pasando por los arcos de la red, sin violar sus capacidades y asumiendo que el flujo se conserva al pasar por los nodos y arcos de la red. Formulaci´on de un PFM como PPL Las variables • xij : cantidad de flujo que pasa por el arco (i, j), para (i, j) ∈ A. • f : flujo saliente de la fuente (flujo entrante en el sumidero). El modelo Max f s.a. P

  f P 0 (xij − xki ) =  (i,j)∈A (k,i)∈A −f 0 ≤ xij ≤ uij

, si i = 1 , si i 6= 1, i 6= m , si i = m

, i = 1, . . . , m , para todo (i, j) ∈ A

2.11.

Soluci´ on del modelo de flujo m´ aximo

2.11.1.

Algoritmo de la red auxiliar para el PFM

Dada la red D = (N, A) del PFM y xij = 0 para todo (i, j) ∈ A como flujo inicial. 1. Construya la red auxiliar D0 • Ponga todos los nodos de D en D0 • Para todo (i, j) ∈ A • Si xij < uij , ponga el arco (i, j) en D0 y as´ıgnele cambio de flujo permisible igual a ∆ij = uij − xij . • Si xij > 0, ponga el arco (j, i) en D0 y as´ıgnele cambio de flujo permisible igual a ∆ji = xij . 2. Si existe una trayectoria P en D0 del nodo 1 al nodo m, entonces • Haga ∆ igual al m´ınimo de todos los cambios de flujo permisible en los arcos de P . • Actualice los flujos en la red D como sigue: • Si (i, j) est´a en P y (i, j) ∈ A , entonces xij = xij + ∆.

• Si (i, j) est´a en P y (j, i) ∈ A , entonces xji = xji − ∆. • Deje los flujos restantes iguales. • Regrese al paso 1. 3. Si no existe una trayectoria P del nodo 1 al nodo m en D0 , entonces tome el flujo actual como ´optimo y termine. Ejemplo 11 Determine el flujo m´aximo del nodo 1 al nodo 5 en la red. 5

2 3

5

1

4

4

5

6

15

10

3

Soluci´on: Paso

G0

G 0 0

1.

1

2

0

0

2

3 0

5

1

15

0 2.

1

10

0 3

10

5

1,2,5

3

5 2

3 0

5

1 10

5 6

5 10

1,3,5

10

3

0 4

4

4

0 2

5

5 6

0

3

∆

5

0 4

P

3

4 10

4

Paso

G0

G

3.

1

2

10

0 0

2

3 0

4

5

3 4.

1

14

4 3

5

4

No hay

–

3 2

3 4

5

2

5

1 14

2 4 1

10

4

10

3

0 4

4

6

5

3 2

1,3,4,5

2

5

1 10

10

3

∆

3

3 3

P

4

5

4 3

10

Flujo m´aximo de 1 a 5: 17 Desde 1 1 2 3 3 4

2.12.

Hacia 2 3 5 4 5 5

Flujo 3 14 3 4 10 4

Ejercicios

Ejercicios sobre el problema de transporte 1. La Compa˜ n´ıa Childfair tiene tres plantas de producci´on de carros para beb´es que deben distribuirse a cuatro centros de distribuci´on. Las plantas 1, 2 y 3 producen 12, 17 y 11 cargamentos por mes, respectivamente. Cada centro de distribuci´on necesita recibir 10 cargamentos por mes. El costo del flete de cada embarque es de $ 100 m´as $ 0.50 por milla. La distancia (en millas) de cada planta a su respectivo centro de distribuci´on se da en la siguiente tabla:

Planta 1 2 3

Centro de distribuci´on 1 2 3 4 800 1,300 400 700 1,100 1,400 600 1000 600 1,200 800 900

Formule y resuelva este problema como un problema de transporte. 2. Tom desear´ıa comprar exactamente 3 litros de cerveza casera hoy y al menos 4 litros ma˜ nana. Dick quiere vender un m´aximo de 5 litros en total a un precio de $ 3.00 por litro hoy y de $ 2.70 por litro ma˜ nana. Harry est´a dispuesto a vender un m´aximo de 4 litros en total, a un precio de $ 2.90 por litro hoy, y $ 2.80 por litro ma˜ nana. Tom quiere saber cu´anto debe comprar a cada uno para minimizar su costo y a la vez cumplir con los requisitos m´ınimos para satisfacer su sed. Formule y resuelva este problema como un problema de transporte. 3. La corporaci´on Versatech producir´a tres productos nuevos. En este momento, cinco de sus plantas tienen exceso de capacidad de producci´on. El costo unitario en $ respectivo de fabricaci´on del primer producto ser´a de 41, 39, 42, 38 y 39 en las plantas 1, 2, 3, 4 y 5. El costo unitario de fabricaci´on del segundo producto en $ ser´a de 55, 51, 56, 52 y 53 en las plantas respectivas 1, 2, 3, 4 y 5; y para el tercer producto ser´a de 48, 45 y 50 en las plantas respectivas 1, 2 y 3, pero las plantas 4 y 5 no pueden fabricar este producto. Los pron´osticos de ventas indican que la producci´on diaria debe ser de 700, 1 000 y 900 unidades de los productos 1, 2 y 3, respectivamente. Las plantas 1, 2, 3, 4 y 5 tienen capacidades para producir 400, 600, 400, 600 y 1 000 unidades diarias, sin importar el producto o combinaci´on de productos. Suponga que cualquier planta que tiene capacidad y posibilidad de fabricarlos podr´a producir cualquier cantidad de productos y con cualquier combinaci´on. La istraci´on desea asignar los nuevos productos a las plantas con el m´ınimo costo total de fabricaci´on. Formule y resuelva este problema como un problema de transporte. 4. Steelco fabrica tres tipos de acero en diferentes plantas. El tiempo requerido para fabricar una tonelada de acero (sin importar el tipo) y los costos en cada planta se ilustran en la tabla. Cada semana deben producirse 100 toneladas de cada tipo de acero. Cada planta est´a abierta 40 horas por semana. Formule y resuelva un problema de transporte equilibrado para minimizar el costo de satisfacer los requerimientos semanales de Steelco. Planta 1 2 3

Costo ($) Acero 1 Acero 2 Acero 3 60 40 28 50 30 30 43 20 20

Tiempo (min) 20 16 15

5. Un hospital necesita comprar 3 galones de una medicina perecedera que utilizar´a durante el mes actual y cuatro galones para uso durante el mes siguiente. Debido a que la medicina es perecedera, s´olo puede utilizarse durante el mes de compra. Dos compa˜ n´ıas (Daisy y Laroach) venden la medicina. La medicina est´a escasa. Por consiguiente, durante los siguientes dos meses, el hospital est´a limitado a comprar a lo sumo 5 galones de cada compa˜ n´ıa. Las compa˜ n´ıas cargan los precios mostrados en la tabla. Formule y resuelva un modelo de transporte equilibrado para minimizar el costo de comprar la medicina necesaria.

Compa˜ n´ıa Daysi Laroach

Precio por gal´on mes actual ($) 800 710

Precio por gal´on mes siguiente ($) 720 750

6. La Ayatola Oil Company controla dos campos petroleros. El campo 1 puede producir hasta 40 millones de barriles de petr´oleo por d´ıa y el campo 2 puede producir hasta 50 millones de barriles por d´ıa. En el campo 1 cuesta $ 3 extraer y refinar un barril de petr´oleo, en el campo 2 el costo es $ 2. Ayatola vende petr´oleo a dos paises: Inglaterra y Jap´on. El costo de env´ıo por barril se presenta en la tabla. Cada d´ıa, Inglaterra est´a dispuesta a comprar hasta 40 millones de barriles (a $ 6 por barril) y Jap´on est´a dispuesto a comprar hasta 30 millones de barriles ( a $ 6.5 por barril). Formule y resuelva un problema de transporte equilibrado para maximizar la ganancia de Ayatola. Inglaterra 1 2

Campo1 Campo2

Jap´on 2 1

7. Una cia. suministra bienes a tres clientes, y cada uno requiere 30 unidades. La cia. tiene dos almacenes. El almac´en 1 tiene 40 unidades disponibles y el almac´en 2 tiene 30 unidades disponibles. Los costos de enviar una unidad desde el almac´en al cliente se muestra en la tabla. Hay una penalizaci´on por cada unidad de demanda no suministrada al cliente: con el cliente 1, se incurre en un costo de penalizaci´on de $ 90; con el cliente 2, $ 80, y con el cliente 3, $ 110. Formule y resuelva un problema de transporte equilibrado para minimizar la suma de escasez y costo de env´ıo. Almac´en 1 Almac´en 2

Cliente 1 15 10

Cliente 2 35 50

Cliente 3 25 40

8. Con respecto al problema anterior asuma que podr´ıan comprarse unidades extras y enviarse a cualquier almac´en para un costo total de $ 100 por unidad. Formule y resuelva un problema de transporte equilibrado para minimizar la suma de costos de compra y env´ıo.

Ejercicios sobre el problema de asignaci´ on 9. Se cuenta con cinco empleados para llevar a cabo cuatro tareas. El tiempo que toma a cada persona realizar cada tarea se da en la tabla siguiente. Determine la asignaci´on de empleados a las tareas que reduce el tiempo total requerido para efectuar las cuatro tareas XXX XXX Tarea XXX Persona XXX

1 2 3 4 5

1

2

3

4

22 18 26 16 21

18 – 20 22 –

30 27 28 – 25

18 22 28 14 28

10. Doc Councillman re´ une a un equipo de relevos para el relevo de 400 metros. Cada nadador

debe nadar 100 metros de brazada de pecho, dorso, mariposa o estilo libre. Doc cree que cada nadador obtendr´a los tiempos dados en la tabla siguiente. Para reducir el tiempo del equipo en la competencia, ¿Qu´e nadador debe nadar cada estilo? XXX XXX Estilo XXX Nadador XXX

Gary Hall Mark Spitz Jim Montgomery Chet Jastremski

Libre

Pecho

Mariposa

Dorso

54 51 50 56

54 57 53 54

51 52 54 55

53 52 56 53

11. Una compa˜ n´ıa recibe ofertas para cuatro trabajos de construcci´on. Tres personas realizaron ofertas en relaci´on con los trabajos. Sus ofertas (en miles de d´olares) se dan en la tabla. La persona 1 puede hacer solo un trabajo, pero las personas 2 y 3 pueden llevar a cabo dos tareas XXX XXX Trabajo XXX Persona XXX

1 2 3

1

2

3

4

50 51 –

46 48 47

42 44 45

40 – 45

12. El consejo de educaci´on de Chicago est´a aceptando ofertas en relaci´on con las cuatro rutas del autob´ us escolar de la ciudad. Cuatro compa˜ n´ıas hicieron las ofertas de la tabla siguiente: XXX XXX Ruta X Compa˜ n´ıa XXXXX

1 2 3 4

1

2

3

4

4000 – 3000 –

5000 4000 – –

– – 2000 4000

– 4000 – 5000

a) Suponga que a cada licitante se le puede asignar solo una ruta y minimice el costo de recorrer las cuatro rutas de autob´ us. b) Suponga que a cada compa˜ n´ıa se le puede asignar dos rutas para minimizar el costo de recorrer las cuatro rutas de autob´ us (sugerencia: para cada compa˜ n´ıa son necesarios dos puntos de suministro) 13. Se deben utilizar cuatro barcos cargueros para transportar bienes de un puerto a otros cuatro puertos (numerados 1, 2, 3 y 4). Se puede usar cualquier barco para hacer cualquiera de los cuatro viajes. Sin embargo, dadas algunas diferencias entre las naves y las cargas, el costo total de carga, transporte y descarga de bienes de las distintas combinaciones de barcos y puertos var´ıa de manera considerable. Estos costos se muestran en la siguiente tabla:

XXX XXX Puerto XXX Barco XXX

1 2 3 4

1

2

3

4

500 600 700 500

400 600 500 400

600 700 700 600

700 500 600 600

El objetivo es asignar los barcos a los puertos en una correspondencia uno a uno de manera que se minimice el costo total de los cuatro env´ıos. Formule este problema como un problema de asignaci´on y obtenga la soluci´on o´ptima. 14. One To One trabaja un servicio de citas en el que hombres y mujeres llenan un cuestionario referente a sus preferencias sobre un compa˜ nero. De estos cuestionarios un programa de computadora determina que hombres son compatibles con que mujeres, obteniendose la lista de abajo. Determine el n´ umero m´aximo de parejas compatibles que pueden arreglarse. Hombres Adams Clark Gifford Patton

Mujeres compatibles Berk, Herat Herat Berk, Herat Heart, Delroy, Macy, Thomas

Ejercicios sobre ´ arbol de expansi´ on m´ınimo 15. El parque Seervada se usa para paseos y campamentos, sin permitirse la entrada de autos. Existe solo un sistema de caminos angostos, los cuales se muestran en la figura. Las letras representan la localizaci´on de las casetas de los guardabosques y otras instalaciones de servicio. Los n´ umeros son las distancias en millas de estos caminos accidentados. La istraci´on del parque quiere instalar l´ıneas telef´onicas subterr´aneas para establecer comunicaci´on entre todas las estaciones e instalaciones. Debido a consideraciones ecol´ogicas, se deben instalar l´ıneas solo siguiendo los caminos y con el fin de obtener comunicaci´on entre cualquier par de estaciones. La pregunta es por d´onde deben tenderse las l´ıneas para lograr este objetivo con el m´ınimo n´ umero total de millas de cable. Formule y resuelva este problema como uno de a´rbol de expansi´on m´ınima. 7

A 2 O

2 5

4

T 7

1 3

B 4

5

D

E 4

1 C

16. En el transporte intermodal, los camiones remolque cargados se mueven entre las terminales de ferrocarril colocando la caja en carros especiales. La figura muestra la ubicaci´on de las principales terminales de ferrocarril en los Estados Unidos, y las vias actuales de FC. El objetivo es decidir cu´ales v´ıas deben ser revitalizadas para manejar el tr´afico intermodal. En

´ especial, se debe unir la Terminal de Los Angeles en forma directa con la de Chicago para dar cabida al intenso tr´afico 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 de las v´ıas seleccionadas. Determine los segmentos de v´ıas de ferrocarril que se deben incluir en el programa de revitalizaci´on.

SE 2000

1300 1100

DE

800

1000

CH

200 DC

2000 2600

LA

NY

1300 780

900

1400 DA 17. En la figura se ven las distancias, en millas, de las conexiones factibles que unen nueve pozos marinos de gas natural con un punto de entrega en la tierra. Como la ubicaci´on del pozo 1 es la m´as cercana a la costa, tiene capacidad de bombeo y de almacenamiento suficiente para bombear la producci´on de los ocho pozos restantes hasta el punto de entrega, determine la red m´ınima de tuber´ıa que una las bocas de pozo. 2

5

9 6

4

9

6

15

1

5

20 3

5

10 20

15

13

14 8

5 12

4

7 7

3

7 6

18. La maderera Wirehouse talar´a a´rboles en ocho zonas de la misma ´area. Pero antes debe desarrollar un sistema de caminos de tierra para tener a cualquier zona desde cualquier otra. La distancia (en millas) entre cada par de zonas es:

Zonas 1 2 3 4 5 6 7 8

1 – 1.3 2.1 0.9 0.7 1.8 2.0 1.5

2 1.3 – 0.9 1.8 1.2 2.6 2.3 1.1

3 2.1 0.9 – 2.6 1.7 2.5 1.9 1.0

4 0.9 1.8 2.6 – 0.7 1.6 1.5 0.9

5 0.7 1.2 1.7 0.7 – 0.9 1.1 0.8

6 1.8 2.6 2.5 1.6 0.9 – 0.6 1.0

7 2.0 2.3 1.9 1.5 1.1 0.6 – 0.5

8 1.5 1.1 1.0 0.9 0.8 1.0 0.5 –

El problema es determinar los pares de zonas entre los que deben construirse caminos para conectar todas con una longitud de caminos total m´ınima. Formule y resuelva este problema como uno de a´rbol de expansi´on m´ınima. 19. El Premiere Bank ha decidido conectar terminales de computadora de cada sucursal a la computadora central de su oficina matriz mediante l´ıneas telef´onicas especiales con dispositivos de telecomunicaciones. No es necesario que la l´ınea telef´onica de una sucursal est´e conectada directamente con la oficina matriz. La conexi´on puede ser indirecta a trav´es de otra sucursal que est´e conectada (directa o indirectamente) a la matriz. El u ´nico requisito es que exista alguna ruta que conecte a todas las sucursales con la oficina matriz. El cargo por las l´ıneas telef´onicas especiales es directamente proporcional a la distancia cableada, donde la distancia (en millas) entre cada par de oficinas es como aparece en la tabla: Of. pr. Suc. 1 Suc. 2 Suc. 3 Suc. 4 Suc. 5

Of. pr. – 190 70 115 270 160

Suc. 1 190 – 100 110 215 50

Suc. 2 70 100 – 140 120 220

Suc. 3 115 110 140 – 175 80

Suc. 4 270 215 120 175 – 310

Suc. 5 160 50 220 80 310 –

La istraci´on desea determinar qu´e pares de sucursales conectar directamente con las l´ıneas telef´onicas especiales para que todas queden conectadas (de modo directo o indirecto) a la oficina matriz con un costo total m´ınimo. Formule y resuelva este problema como uno de ´arbol de expansi´on m´ınima.

Ejercicios sobre el problema de ruta m´ as corta 20. La figura muestra la red de comunicaciones entre dos estaciones, 1 y 7. La probabilidad de que un enlace de la red funcione sin fallar se ve en cada arco. Los mensajes se mandan de la estaci´on 1 a la estaci´on 7, y el objetivo es determinar la ruta que maximice la probabilidad de una buena transmisi´on. Formule el caso como modelo de ruta m´as corta y resu´elvalo.

0.5

2 0.8

0.9 0.65

1 0.3

5 0.7

0.8

4

0.5 0.9

0.6

0.85 0.95

3

7

6

21. La telef´onica Tell-All da servicio a seis a´reas geogr´aficas. Las distancias (en millas) de sat´elites entre las seis a´reas se ven en la figura. Tell-All debe determinar las rutas de mensaje m´as eficientes que se van a establecer entre cada par de ´areas en la red. 400

2 200

700

300

1

6

100 4

700

200 3

500 300

600

5

22. RentCar est´a desarrollando un plan de reposici´on de su flotilla de autom´oviles para un horizonte de planeaci´on de 4 a˜ nos, que comienza el 1 de enero de 2001 y termina el 31 de diciembre de 2004. Al iniciar cada a˜ no se toma la decisi´on de si un auto se debe mantener en operaci´on o se debe sustituir. Un autom´ovil debe estar en servicio durante 1 a˜ no como m´ınimo, y 3 a˜ nos como m´aximo. La tabla muestra el costo de reposici´on en funci´on del a˜ no de adquisici´on del veh´ıculo y los a˜ nos que tiene en funcionamiento. Formule un problema de ruta m´as corta que sirva para determinar el plan de reposici´on m´as econ´omico. A˜ no de adquisici´on 2001 2002 2003 2004

A˜ nos 1 4,000 4,300 4,800 4,900

de operaci´on 2 3 5,400 9,800 6,200 8,700 7,100 – – –

23. Use el algoritmo de Dijkstra para calcular la ruta m´as corta del nodo 1 la nodo 6 en el ejercicio 21. 24. Use el algoritmo de Dijkstra para calcular la ruta m´as corta a partir del nodo 2 en la red.

2 1

2

4

1 1

3

4

4 2

3

a)

b)

3 5

5

2

4 4

3

5

3 2

6

2

3

3

6 2

2

5

6

Ejercicios sobre el problema de flujo m´ aximo 25. Las aerol´ıneas Fly-by-Night deben determinar cu´antos vuelos de conexi´on diarios se pueden concretar entre Juneau, Alaska y Dallas, Texas. Los vuelos de conexi´on deben detenerse en Seattle y despu´es parar en Los a´ngeles o Denver. Debido al espacio de aterrizaje limitado Fly-by-Night est´a limitado a hacer el n´ umero de vuelos diarios entre los pares de ciudades que se muestran en la tabla. Establesca un problema de flujo m´aximo cuya soluci´on le permita saber a la aerol´ınea como maximizar el n´ umero de vuelos de conexi´on diarios de Juneau a Dallas. Cuidades Juneau-Seattle Seattle-L.A. Seattle-Denver L.A.-Dallas Denver-Dallas

No. m´aximo de vuelos diarios 3 2 3 1 2

26. Un padre tiene cinco hijos adolescentes y cinco tareas para asignarles. La experiencia ha indicado que es contraproducente forzar a que los ni˜ nos acepten demasiadas tareas. Teniendo eso en cuenta, les pide a sus hijos hacer una lista de preferencias entre las cinco tareas, y resulta la siguiente tabla: Ni˜ no Rif Mai Ben Kim Ken

Tareas preferidas 3, 4, 5 1 1,2 1, 2, 5 2

El objetivo del padre es terminar todas las tareas posibles, y atender al mismo tiempo las preferencias de sus hijos. Determine la cantidad m´axima de tareas que pueden terminarse y la asignaci´on de tareas a hijos. 27. Cuatro f´abricas producen cuatro clases de juguetes. La siguiente tabla es una lista de los juguetes que se producen en cada una de ellas

F´abrica 1 2 3 4

Juguetes que produce 1, 2, 3 2,3 1,4 3,4

Todos los juguetes requieren la misma mano de obra y los mismos materiales por unidad. Las capacidades diarias de las cuatro f´abricas son 250, 180, 300 y 100 juguetes respectivamente. Las demandas diarias de los cuatro juguetes son 200, 150, 350 y 100 unidades, respectivamente. Determine los programas de producci´on que satisfagan la mayor parte de las demandas de los cuatro juguetes. 28. Cinco varones y cinco mujeres est´an en un baile. Un casamentero tiene como objetivo emparejar cada mujer con un hombre de manera que maximice el n´ umero de personas cuya pareja es compatible. La compatibilidad de los hombres y mujeres se describe en la tabla. Dibuje una red que haga posible representar el problema de maximizar el n´ umero de parejas compatibles como un problema de flujo m´aximo. HH

H

H M HH H

A B C D E

F

G

H

I

J

– C C C –

C – C C –

– – – – C

– – – – C

– – – C C

29. Cinco camiones entregan siete tipos de paquetes. Hay tres paquetes de cada tipo, y las capacidades de los cinco camiones son 6, 4, 5, 4 y 3 paquetes respectivamente. Prepare un problema de flujo m´aximo que se puede usar para determinar si pueden cargarse los paquetes de tal manera que cada cami´on no lleve dos paquetes del mismo tipo. 30. Cuatro trabajadores est´an disponibles para efectuar las tareas 1 a 4. Desafortunadamente, tres trabajadores pueden hacer solo ciertas tareas; el trabajador 1, solo la tarea 1; el trabajador 2, solo las tareas 1 y 2; el trabajador 3, s´olo la tarea 2; el trabajador 4 cualquier tarea. Formule un problema de flujo m´aximo que permita determinar si las tareas se pueden asignar a un trabajador adecuado. 31. Los Hatfields, los Montagues, los McCoys y los Capulets se van a su d´ıa de campo familiar aual. Se dispone de cuatro autom´oviles para transportar a las familias. En los autom´oviles caben los siguientes n´ umeros de personas: auto 1, cuatro; auto 2, tres; auto 3, tres, y auto 4, cuatro. Hay cuatro personas en cada familoia, y ning´ un autom´ovil puede llevar m´as de dos personas de cualquier familia. Formule el problema de transportar el n´ umero m´aximo de personas al d´ıa de campo como un problema de flujo m´aximo. 32. De tres silos se transporta alimento para pollos a cuatro granjas. Algunos de los silos no pueden mandar en forma directa a algunas granjas. Las capacidades de las dem´as rutas se limitan por la cantidad de camiones disponibles y la cantidad de viajes que se hacen diario. La tabla muestra las cantidades diarias de oferta en los silos, y la demanda en las granjas (en miles de libras). Los elementos de las celdas de la tabla especifican las capacidades diarias de las rutas correspondientes. Formule como un problema de flujo m´aximo el problema de

determinar la cantidad m´axima de alimento que puede transportarse de los silos a las granjas. PP

PP Granja PP PP Silo P

1 2 3 Demanda

1

2

3

4

Oferta

30 0 100 200

5 0 40 10

0 5 30 60

40 90 40 20

20 20 200 -

33. Calcule el flujo m´aximo desde el nodo fuente (F ) al nodo sumidero (S) en la red

6 a)

F

3

1 1

2 2

3

3

S

7 7

b)

1

c)

F

5

30

15

2 14

10

19

3

d)

F

1 3

6 2

10 4

4 2

3

3

4 S

S

2

6

27

2

3

3

F

4

1

1

1

1 20

3

4

2

7

9

S