Tema_6_Redes_Problemas O1

Vista previa del material en texto

OPTIMIZACIÓN DE REDES 
PROBLEMAS 
 
1. La figura siguiente muestra una serie de nodos y sus respectivas rutas mediante las cuales se 
propone distribuir las unidades de un producto, el número que lleva cada arco (flecha) representa 
el costo unitario asociado a esa ruta (arco), y las cantidades que se ubican en los nodos iniciales 
representan la oferta de cada planta, así como las cantidades de los nodos finales representa la 
demanda de cada distribuidor. 
 
 
a) Resuelva este problema de transporte analizándolo como una red y escribiendo el PPL 
que lo resuelva. 
b) Resuelve este problema, pero suponiendo ahora que la demanda en el punto D1 es de 
sólo 100. 
c) Resuelve este problema, pero suponiendo ahora que la demanda en el punto D1 vuelve a 
ser de 800, pero la oferta en P2 es de es de sólo 1000. 
 
2. Se tiene el siguiente esquema de trasbordo, los nodos 1 y 3 envían (origen) y los nodos 4 y 5 
reciben (destino). 
(a) Hallar la solución óptima usando un modelo de red. Los valores en los nodos son la oferta 
o demanda, y los valores en los arcos son el costo unitario de transporte. 
(b) Encuentre el árbol de expansión mínima tomado los costos unitarios como distancias. 
 
 
3. Se deben transportar 20 millones de barriles de petróleo desde Dhahran en Arabia Saudita a las 
ciudades de Rotterdam, Marsella y Nápoles en Europa. Las demandas de estas tres ciudades son 
4, 12 y 4 millones de barriles, respectivamente. A continuación, se presenta un diagrama con las 
posibles rutas: 
 
 
 
Observe que para cada ciudad existe la posibilidad directa de envío, es decir, que los barriles sean 
transportados directamente desde Dhahran. Sin embargo, la ruta que une Dhahran y Marsella no 
puede transportar más de 3 millones de barriles debido a ciertos acuerdos comerciales. Por otro 
lado, existe la posibilidad que se realice una detención, ya sea en el puerto de Alejandría o Suez, 
donde la capacidad de transbordo es de 8 y 10 millones respectivamente. Por último, observe que 
es posible enviar barriles de petróleo desde Marsella a Nápoles. Sin embargo, le está prohibido a 
Nápoles recibir más petróleo de Marsella que directamente de Dhahran. Formule y resuelva 
(usando software) un modelo de programación lineal, basado en el análisis de la red, que permita 
hallar la política óptima de transporte para cumplir con los requerimientos de demanda de los 
puertos. 
 
4. Para la red mostrada a continuación, formule un PPL para encontrar el patrón de flujo que 
proporciona el flujo máximo del nodo origen al nodo destino, donde la capacidad a través del arco 
que va del nodo i al nodo j es el número más cercano al nodo i del arco entre estos nodos. 
Resuélvalo con LINDO. 
 
 
5. En fecha reciente se reservó el área de SEERVADA PARK para paseos y campamentos. No se 
permite la entrada de automóviles, pero existe un sistema de caminos angostos con curvas para 
tranvías y “jeeps” conducidos por los guardabosques. El parque contiene un mirador a un 
hermoso paisaje en la estación T. Unos cuantos tranvías transportan a los visitantes desde la 
entrada (O) a la estación (T) y de regreso (ver figura. Los números son las distancias entre puntos) 
 
a) Determine la ruta más corta desde la entrada del parque a la estación T. 
b) La administración ha concluido que deben instalarse líneas telefónicas subterráneas para 
establecer comunicación entre todas las estaciones, incluso la entrada. Debido a que la 
instalación es cara y perturba la ecología, se deben instalar líneas que sigan sólo los 
caminos necesarios para obtener comunicación entre cualquier par de estaciones. La 
pregunta es por dónde deben tenderse las líneas para lograr este objetivo con el mínimo 
número total de millas de cable instalado. 
 
 
6. La compañía RELIABLE CONSTRUCTION acaba de ganar una licitación de 5.4 millones de dólares 
para construir una nueva planta para un fabricante importante. La siguiente tabla muestra la lista 
de actividades. 
 
 
a) Dibuja la red del proyecto. 
b) Escriba el PPL que permita calcular la ruta crítica y resuélvelo con LINDO. 
c) Dibuja el cronograma donde se visualicen las actividades críticas y las no críticas con sus 
holguras. 
 
 
7. Usted debe hacer un viaje en automóvil a una ciudad que nunca ha visitado. Estudia un plano para 
determinar la ruta más corta hasta su destino. Según la ruta que elija, hay otras cinco ciudades 
(llamadas A, B, C, D, E) por las que puede pasar en el camino. El plano muestra las millas de cada 
carretera que son una conexión directa entre dos ciudades sin que otra intervenga. Estas cifras se 
resumen en la siguiente tabla, donde un guion indica que no hay conexión directa sin pasar por 
otras ciudades. 
 
 
Formule un problema de la ruta más corta al trazar una red donde los nodos son ciudades, los 
arcos son carreteras y los números la distancia en millas. Escriba el PPL que permita resolverlo y 
halle la solución con LINDO. 
 
8. Una compañía aérea local piensa comprar un tractor nuevo para mover el tren de carros que 
llevan y traen el equipaje de los aviones que aterrizan en un pequeño aeropuerto que está en 
pleno crecimiento. 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, tendrá una carga de 
trabajo pesada y los costos de operación y mantenimiento aumentarán rápido y podría resultar 
costeable reemplazarlo en uno o dos años. La siguiente tabla proporciona los costos descontados 
netos totales asociados con la compra del tractor (precio de compra menos valor de venta del 
tractor en uso más costos de operación y mantenimiento) al final del año i y si se reemplaza al 
final del año j (donde el momento presente es el año 0). 
 
 
Dibuje la red y formule un PPL que permita determinar en qué momento (si existe) debe 
reemplazarse el tractor para minimizar el costo total durante los tres años. 
 
 
9. Formule un PPL para encontrar la ruta más corta a través de las redes a) y b), en las cuales los 
números representan las distancias reales entre los nodos correspondientes. Encuentre también 
el árbol de expansión mínima de cada red. 
 
 
 
 
10. La maderera Wirehouse talará árboles en ocho zonas de la misma área. Pero antes debe 
desarrollar un sistema de caminos de tierra para tener acceso a cualquier zona desde cualquier 
otra. La distancia (en millas) entre cada par de zonas es: 
 
 
 
Determine, usando los métodos que conozcas, los pares de zonas entre los que deben construirse 
caminos para conectar todas con una longitud de caminos total mínima. 
 
 
11. El Premiere Bank ha decidido conectar terminales de computadora de cada sucursal a la 
computadora central de su ofi cina matriz mediante líneas telefónicas especiales con dispositivos 
de telecomunicaciones. No es necesario que la línea telefónica de una sucursal esté conectada 
directamente con la ofi cina matriz. La conexión puede ser indirecta a través de otra sucursal que 
esté conectada (directa o indirectamente) a la matriz. El único requisito es que exista alguna ruta 
que conecte a todas las sucursales con la oficina matriz. El cargo por las líneas telefónicas 
especiales es directamente proporcional a la distancia cableada, donde la distancia (en millas) 
entre cada par de ofi cinas es: 
 
 
La administración desea determinar qué pares de sucursales conectar directamente con las líneas 
telefónicas especiales para que todas queden conectadas (de modo directo o indirecto) a la ofi 
cina matriz con un costo total mínimo. 
 
 
12. El siguiente diagrama describe un sistema de acueductos que se origina en tres ríos (Rl, R2 y R3) y 
termina en una ciudad importante (nodo T), donde los otros nodos son puntos de unión del 
sistema 
 
las siguientes tablas muestran la cantidad máxima de agua que puede bombearse, a través de 
cada acueducto, cada día (millones de m3). 
 
 
Formule este problema como un problema de flujo máximo; identifique un origen, un destino 
y los nodosde trasbordo, y trace la red completa que muestre la capacidad de cada arco. 
Resuélvalo mediante un PPL con LINDO. 
 
 
13. La Texago Corporation tiene cuatro campos de petróleo, cuatro refinerías y cuatro centros de 
distribución. Una fuerte huelga en la industria del transporte ha reducido de manera 
considerable la capacidad de Texago para enviar petróleo de sus campos a las refinerías y los 
productos derivados a los centros de distribución. Las tablas siguientes muestran el número 
máximo de unidades (miles de barriles) que puede enviar al día de cada campo a cada refiería 
y de éstas a cada centro de distribución. 
 
 
 
La administración de Texago desea elaborar un plan para determinar cuántas unidades debe 
enviar de cada campo petrolero a cada refinería y de cada refinería a cada centro de 
distribución de manera que se maximice el número total de unidades que llegan a los centros 
de distribución. 
a. Bosqueje un plano que muestre la ubicación de los campos, refinerías y centros de 
distribución de Texago. Agregue el flujo del petróleo crudo y de los productos del 
petróleo a través de la red de distribución. 
b. Dibuje de nuevo la red alineando en una columna los nodos de los campos, en otra los 
de refinerías y en una tercera los de centros de distribución. Después agregue arcos 
para mostrar el flujo posible. 
c. Modifique la red del inciso b) para formular este problema como uno de flujo máximo 
con sólo una fuente, un destino y una capacidad de cada arco. 
d. Formule un PPL que resuelva este problema y halle la solución con un programa. 
 
14. Una compañía fabricará el mismo producto nuevo en dos plantas y después lo enviará a dos 
almacenes. La fábrica 1 puede enviar una cantidad ilimitada por ferrocarril sólo al almacén 1, 
mientras que la fábrica 2 puede mandar una cantidad ilimitada por la misma vía sólo al almacén 
2. Sin embargo, se puede usar camiones de carga independientes para enviar hasta 50 unidades 
de cada fábrica a un centro de distribución desde el que se pueden enviar hasta 50 unidades a 
cada almacén. En la siguiente tabla se muestra el costo unitario de embarque de cada 
alternativa junto con las cantidades que se producirán en las fábricas y las cantidades que se 
necesitan en los almacenes. Formule un modelo de programación lineal para este problema 
 
 
15. Makonsel es una compañía integral que produce bienes y los vende en sus propias tiendas. 
Después de producidos los bienes se colocan en dos almacenes hasta que las tiendas los 
necesitan. Se usan camiones para transportar los bienes a los almacenes y luego a las tres 
tiendas. Utilice una carga completa de camión como unidad; la siguiente tabla muestra la 
producción mensual de cada planta, su costo de transporte por carga enviada a cada almacén 
y la cantidad máxima que se puede enviar al mes a cada uno. 
 
 
 
La siguiente tabla contiene la demanda mensual de cada tienda (T ), el costo de transporte 
por camión desde cada almacén y la cantidad máxima que se puede enviar al mes desde cada 
uno. 
 
 
 
La administración desea determinar un plan de distribución —número de cargas enviadas al 
mes de cada planta a cada almacén y de cada uno de éstos a cada tienda— de modo que se 
minimice el costo total de transporte. 
 
16. Considere el problema que se presenta en la siguiente figura, donde los valores de 𝑏𝑖 (flujos 
netos generados: positivos si es demanda, negativos si es suministro) están dados en los 
nodos, los valores de 𝑐𝑖𝑗 (costo por unidad de flujo) están dados en los arcos y los valores de 
𝑢𝑖𝑗 (capacidades de los arcos) se encuentran entre los nodos C y D. 
 
Plantee un PPL que permita minimizar el flujo de esta red y resuélvelo con software. 
 
 
17. La siguiente figura representa las tares de un proyecto, con las actividades representadas en 
los nodos. 
 
La siguiente tabla proporciona las duraciones de las diferentes actividades: 
 
 
a) Representa el proyecto como una red, con las actividades en los arcos, indicando en 
ellos la duración de cada tarea. 
b) Calcula la ruta crítica mediante un PPL y utilizando un programa. 
c) Representa gráficamente el cronograma del proyecto, donde puedan visualizarse las 
holguras de las tareas no críticas. 
 
 
 
 
18. Repite este mismo ejercicio, pero con el siguiente proyecto: 
 
 
 
 
19. La siguiente tabla resume las tareas de un proyecto, las precedencias y las duraciones. 
Dibuja las red del proyecto, calcula su camino crítico y representa su cronograma. 
 
 
Tarea Precedencia Duración 
A Realización de contrato -- 7 
B Compra de equipos A 5 
C Bases de equipo D-B 6 
D Excavación A 6 
E Mamposteria D 10 
F Colocacion de caños E-C 3 
G Parquizacion y accesorios F 4 
H Tramite municipal A 21 
I Colocacion de equipos C 5 
J Instal. electrica y pruebas I 4 
 
 
20. Realice el análisis CPM del proyecto que se resume en la siguiente tabla: 
 
 
Actividad 
Actividades 
predecesoras 
inmediatas 
Duración de 
la actividad 
(días) 
a - 20 
b a 10 
c b 8 
d a 11 
e c,d 7 
f e 6 
g d 12 
h e 13 
i g,h 5 
 
 
 
 
21. Un proyecto tiene las siguientes actividades, relaciones de precedencia y duración de 
actividades: 
 
 
Actividad 
Actividades 
predecesoras 
inmediatas 
Duración 
de la 
actividad 
(días) 
Actividad 
Actividades 
predecesoras 
inmediatas 
Duración 
de la 
actividad 
(días) 
a - 6 f a 1
5 b - 8 g a 1
7 c - 5 h f 9 
d b 1
3 
i g 6 
e c 9 j d,
e 
1
2 
a) Dibuje una red CPM para el proyecto 
b) ¿Cuál es la ruta crítica? ¿Cuál es la duración estimada del proyecto? 
c) Haz una representación gráfica del cronograma. 
 
22. Una empresa está a punto de iniciar un proyecto para diseñar un proceso de producción para 
la elaboración de un nuevo producto. Las actividades del proyecto se resumen en la siguiente 
tabla: 
Actividad Duración de 
la actividad 
(días) 
Actividades 
predecesoras 
inmediatas 
a 12 - 
b 10 - 
c 8 - 
d 14 b 
e 6 c 
f 18 b,a 
g 11 d,e 
h 21 c 
i 7 f,g 
a) Dibuje una red CPM para el proyecto. 
b) ¿Cuál es la ruta crítica? ¿Cuál es la duración estimada del proyecto? 
c) Haz una representación gráfica del cronograma. 
 
Las actividades de un proyecto están relacionadas las relaciones de precedencia que se indica en 
la siguiente tabla. Se requiere graficar la red de flechas y calcular la ruta crítica. 
 
 
23. Una compañía arrendadora de automóviles está desarrollando un plan de reemplazo de su 
flotilla para los próximos cinco años. Un automóvil debe de estar en servicio al menos un año 
antes de que se considere ser reemplazado. La tabla siguiente resume el costo de reemplazo por 
unidad (en miles de unidades monetarias) como función del tiempo y el número de años en 
operación. El costo incluye la compra, prima del seguro, operación y mantenimiento. Determine 
el plan de reemplazo óptimo. 
 
 
 
 
 
 
24. La empresa EF está preparando la planificación, aplicando la técnica PERT, de un proyecto 
informático, cuyas actividades se indican en la tabla inferior, así como sus precedentes y la 
duración expresada en semanas (optimista, pesimista y más probable). Realice el diseño 
completo del grafo, incluyendo holguras y camino crítico. En qué rango de valores estará la 
duración total del proyecto con una probabilidad del 90%. 
 
 
 
Actividad 
 
 
Precedentes 
Estimación 
optimista 
Estimación 
más 
probable 
Estimación 
pesimista 
a - 1 2 3 
b a 2 4 6 
c b,h 1 1 1 
d - 3 6 9 
e g 2 3 4 
f e 3 5 7 
g d 1 2 3 
h g 1 2 3 
i d 1 3 5 
j i 3 4 5 
k d 2 3 4 
l j,k 3 5 7 
m c,l 1 2 3 
 
25. Construya el diagrama de red e identifique las actividades críticas y no críticas, para el 
proyecto "X", tomando en cuenta el siguiente cuadro: 
 
ACTIVIDAD PRECEDENCIA TIEMPOSMP
OS A 5 
B 3 
C 2 
D A 3 
E B 4 
F C 3 
G D E 1 
H D-E 5 
I F 4 
J G I 6 
 
 
Año 1 2 3 4 5 
1 4.0 5.4 9.8 13.7 
2 4.3 6.2 8.1 
3 4.8 7.1 
4 4.9 
 
 
26. Suponga que cuesta $10 000 comprar unautomóvil nuevo. El costo de operación anual y el valor 
de reventa de un automóvil usado se muestran en la siguiente tabla: 
Edad del 
automóvil 
(Años) 
Valor de 
reventa 
($) 
Costo de 
operación ($) 
1 7 000 300 (año 1) 
2 6 000 500 (año 2) 
3 4 000 800 (año 3) 
4 3 000 1 200 (año 4) 
5 2 000 1 600 (año 5) 
6 1 000 2 200 (año 6) 
 
Suponiendo que en la actualidad se tiene un automóvil nuevo, determine una política de 
reemplazo que minimice los costos netos de poseer y operar un automóvil durante los 
siguientes seis años. 
 
27. La red de la figura presenta las distancias en millas entre pares de ciudades. Determine la ruta 
más corta entre las ciudades 1 y 8. 
 
 
28. La red de la figura presenta las distancias en millas entre pares de ciudades. Determine la ruta 
más corta entre las ciudades 1 y 7.