Fundamentos de Investigación de Operaciones.17.10.2002

MODELOS DE GRAFOS

1. Desde una central de despacho (1) se desea enviar a seis mensajeros a seis puntos de una ciudad. Las rutas posibles y las respectivas distancias se ilustran en la figura. Determinar la ruta que debe seguir cada mensajero de modo de minimizar la distancia a recorrer.

2. Actualmente, todas las calles del barrio que aparece en la figura son de tierra. Se está desarrollando un proyecto de pavimentación para enviar a la Municipalidad. Se desea que al menos sea posible trasladarse entre los seis puntos más importantes del sector por calles pavimentadas. ¿Cuáles calles recomendaría Ud. pavimentar de modo de minimizar el costo del proyecto?

3. Debido a la construcción de un nuevo sistema de vías subterráneas en una ciudad, se han planeado dos redes de rutas alternas para el desvío del tránsito. Los diferentes límites de velocidad y las vías de tránsito producen diversas capacidades de flujo en los distintos arcos de las redes propuestas. ¿Cuál de las dos redes es la más adecuada? Fundamente su respuesta.

Alternativa nº1.

Alternativa nº2.

1

2

3

4

5

7

610

15

3

4

6617

56

4 2

1

2

3

4

5

640

2040

20

50

40

30

10 3040

30

1

2

3

4

5

7

6

20

25

3

6

0

5

3

0

0

0 0

5

03

0

0

0

71

1

7

8

(Fin desvío)(Inicio desvío)

1

2

3

4

5

6

00

3

6

6

0

42

00 0

0

04

1

0

2

6

(Fin desvío)(Inicio desvío)

4. En un pequeño aeropuerto que está creciendo, la compañía aérea local piensa comprar un nuevo tractor para mover los carros que llevan y traen el equipaje de los aviones. Dentro de tres años se instalará un nuevo sistema mecanizado de transporte de equipaje, por lo que después no se necesitará el tractor. No obstante, el tractor tendrá una carga de trabajo pesada por lo cual los costos de operación y mantenimiento aumentarán rápidamente con el tiempo y podría resultar económico reemplazarlo en uno o dos años. La tabla proporciona los costos totales asociados a un tractor que se compra al inicio del año i y se reemplaza al final del año j (el momento presente es el inicio del año 1)

Año de compra iAño de reemplazo j

1 2 31 8 18 312 - 10 213 - - 12

El problema consiste en determinar un programa de compra y reemplazo de mínimo costo disponiendo cada año de un tractor. Desarrolle un modelo de red para representar esta situación y resuélvalo utilizando un algoritmo adecuado. Indique explícitamente los pasos que sigue.

5. Suponga que las distancias entre cuatro ciudades vecinas son las que se presentan en el esquema.

Suponga que hay interés de pavimentar y conectar estas ciudades a un costo mínimo. Indique cuáles serían las rutas a pavimentar desde un punto de vista gubernamental o del estado y desde un punto de vista de los usuarios.

6. Suponga que usted se encuentra en la ciudad 1 y debe trasladarse a la ciudad 6 para realizar un importante negocio. Para ello dispone de varias rutas y tipos de transporte que se ilustran a continuación:

Ruta Transporte Tiempo [h] Costo Ruta Transporte Tiempo [h] Costo1-2 Tren 4 20 3-4 Taxi 1 151-5 Avión 1 115 4-5 Tren 7/3 151-3 Bus 2 10 3-6 Bus 19/3 251-6 Taxi 6 90 2-6 Taxi 10/3 501-4 Tren 10/3 30 5-6 Tren 4/3 102-5 Bus 3 15 4-6 Bus 14/3 203-5 Bus 14/3 20

Suponga que usted gana $1.500 por hora y que el tiempo de viaje no se lo consideran como trabajo. Determine cuál es la ruta más corta entre la ciudad 1 y la ciudad 6 de manera tal de minimizar sus costos.

A

C D

B2

6

7

3

6

5

2

1

3

4

6

5