Final_O1_2018_I_solucion

Vista previa del material en texto

Facultad de Ingeniería 
INVESTIGACIÓN DE OPERACIONES 1 
SEMESTRE 2018-I 
EXAMEN FINAL 
11:30 3/7/2018 
Duración: 2 h 
Nombre:___________________________________________________________________________ 
 
Cuando se solicite RECLAMO, deberá adjuntarse copia de la solución publicada. El reclamo deberá basarse en 
errores de corrección en base a esa solución. 
 
1. (14p) Una importante empresa de productos de cosmética comercializa sus productos en tres ciudades, que 
denotaremos por C1, C2 y C3. La demanda semanal de sus productos en estos tres mercados es de 1500, 2000 y 900 
unidades, respectivamente. No puede enviarse a estas ciudades más cantidad que la que demandan. La empresa cuenta 
con 4 centros de producción, que denotaremos por P1, P2, P3 y P4. La capacidad máxima de producción de estos centros 
es de 2100, 1500, 1200 y 2400 unidades semanales, respectivamente. La empresa no lleva directamente los productos 
desde los centros de producción a las ciudades, sino que siempre lo hace a través de tres grandes centros de distribución 
(trasbordos), que denotaremos por T1, T2 y T3. La capacidad máxima de distribución de estos centros de distribución es 
2100, 2400, y 2500 unidades, respectivamente. Estos centros de distribución entregan cada semana todo lo que reciben 
en esa semana, es decir, no almacenan mercancía para semanas posteriores. Cada centro de producción tiene acceso a 
estos tres centros de distribución. De dada centro de distribución se puede acceder a cualquiera de las tres ciudades. La 
tabla siguiente muestra los costes de transporte unitario desde los centros de producción a los centros de distribución, y 
desde los centros de distribución a las ciudades: 
$ T1 T2 T3 
P1 30 20 23 
P2 34 23 25 
P3 25 30 20 
P4 24 35 23 
C1 14 16 15 
C2 15 17 15 
C3 15 16 16 
Se pide: 
a) Dibuja una red que represente este sistema de suministro, colocando en ella toda la información disponible. 
(2p) 
b) Plantea un modelo lineal que permita encontrar un modelo de cadena de suministro que permita satisfacer 
toda la demanda con costes de operación mínimos. (9p) 
c) Se plantea ahora que la utilización de los centros de distribución T1, T2, T3 tiene unos costes fijos de 3000, 2800 
y 5000 dólares semanales, respectivamente. Modifica el modelo lineal realizado anteriormente para que tenga 
en cuenta esta nueva información. (3p) 
 
SOLUCIÓN 
a) (max 2p. Cada fallo -1 o -0.5 dependiendo de la gravedad) 
 
 
 
 
b) La demanda suma 4400 unidades, y la oferta máxima 7200. No está balanceado. Hay que comprobar también que 
la capacidad de distribución no supone una limitación adicional al cómputo del balance total. La capacidad total 
de los centros de distribución es de 7000, que es más de la demanda total. Por tanto, el problema es cómo 
transportar 4400 unidades (a cada ciudad sus cantidades correspondientes) de la forma más económica posible. 
El balanceo podría hacerse añadiendo un nodo-ciudad ficticio al que llevar las 7200-4400=2800 unidades, como 
se muestra en la siguiente figura, donde los costes de transporte al nodo 11 son nulos. No tiene sentido hacer 
pasar el flujo ‘ficticio’ por los puntos de trasbordo, pues físicamente no se está moviendo nada. Además, en este 
caso, no sería factible, pues la capacidad de trasbordo es menor que la de suministro, lo que obligaría a crear otro 
nodo ficticio de trasbordo. En este caso, además, parte del flujo ‘ficticio’ tendría costes, por lo que la única 
solución válida con nodo ficticio sería la siguiente: 
 
 
 
 
No obstante, aquí sólo desarrollaremos la solución en la que la falta de balanceo se resuelve utilizando las 
desigualdades oportunas en las restricciones. 
 
• Variable de decisión: 
𝑥𝑖𝑗 =unidades a transportar desde el nodo i al j 
 
• Función objetivo 
min 𝑍 = 30𝑥15 + 20𝑥16 + 23𝑥17 + ⋯ + 23𝑥47 + 14𝑥58 + 15𝑥59 + ⋯ + 16𝑥710 
(v. de decisión + F.O max 1 punto) 
 
• Restricciones: 
Flujo en nodos de origen. (2p) 
𝑥15 + 𝑥16 + 𝑥17 ≤ 2100 
𝑥25 + 𝑥26 + 𝑥27 ≤ 1500 
𝑥35 + 𝑥36 + 𝑥37 ≤ 1200 
𝑥45 + 𝑥46 + 𝑥47 ≤ 2400 
Flujo en nodos de trasbordo. (2p) 
𝑥58 + 𝑥59 + 𝑥510 − 𝑥45 − 𝑥35 − 𝑥25 − 𝑥15 = 0 
𝑥68 + 𝑥69 + 𝑥610 − 𝑥46 − 𝑥36 − 𝑥26 − 𝑥16 = 0 
𝑥78 + 𝑥79 + 𝑥710 − 𝑥47 − 𝑥37 − 𝑥27 − 𝑥17 = 0 
 
Flujo en los nodos de las ciudades. (2p) 
1500 − 𝑥78 − 𝑥68 − 𝑥58 = 0 
2000 − 𝑥79 − 𝑥69 − 𝑥59 = 0 
900 − 𝑥710 − 𝑥610 − 𝑥510 = 0 
 
 
 
 
Capacidad de los centros de distribución. (2p) 
𝑥15 + 𝑥25 + 𝑥35 + 𝑥45 ≤ 2100 
𝑥16 + 𝑥26 + 𝑥36 + 𝑥46 ≤ 2400 
𝑥17 + 𝑥27 + 𝑥37 + 𝑥47 ≤ 2500 
 
y las restricciones de no negatividad y variables enteras: 𝑥𝑖𝑗 ∈ ℤ
+ + {0} 
 
 
c) (3p) Para introducir los costes fijos de cada centro de distribución definimos la siguiente variable binaria 
𝑦𝑘 = {
1, 𝑠𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎 𝑒𝑙 𝑐𝑒𝑛𝑡𝑟𝑜 𝑑𝑒 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑐𝑖ó𝑛 𝑘
0, 𝑛𝑜 𝑠𝑒 𝑢𝑡𝑖𝑙𝑖𝑧𝑎 𝑒𝑙 𝑐𝑒𝑛𝑡𝑟𝑜 𝑑𝑒 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑐𝑖ó𝑛 𝑘
 
 
Con ella modificamos la función objetivo de la siguiente manera: 
 
min 𝑍 = 30𝑥15 + ⋯ + 16𝑥710 + 3000𝑦1 + 2800𝑦2 + 5000𝑦3 
 
(var de decisión más F.O. 1p) 
Esta función tenderá a asignar valor 0 a las 𝑦𝑘 , por lo que necesitamos introducir restricciones que digan que si les 
llegan artículos tomen valor 1. Estas restricciones pueden ser las siguientes: (2p) 
𝑥15 + 𝑥25 + 𝑥35 + 𝑥45 ≤ 2100𝑦1, 
𝑥16 + 𝑥26 + 𝑥36 + 𝑥46 ≤ 2400𝑦2, 
𝑥17 + 𝑥27 + 𝑥37 + 𝑥47 ≤ 2500𝑦3, 
 
de esta forma, si la parte izquierda de la desigualdad es mayor que 0, necesariamente la variable binaria de la 
derecha debe ser 1. Y si la parte derecha es 0, no se obliga a nada a la variable binaria, pero la función objetivo, que 
busca minimizar los costes, les asignará entonces valor cero. Estas restricciones sustituirán a las restricciones de 
capacidad de los nodos de trasbordo. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2. (6p)La siguiente tabla muestra una secuencia de actividades en las que se descompone un proyecto, así como la 
duración (días) de cada una de ellas y el orden de precedencia más inmediata. 
 
Actividad 
Actividades 
predecesoras 
Duración 
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 
Se pide: 
a) Construye una red del proyecto de acuerdo con el método CPM.(2p) 
b) A la vista de esta red, y usando simple inspección ¿cuál es la ruta crítica, y cuál la duración del proyecto? (1p) 
c) Escribe un modelo lineal que permita calcular esta ruta crítica usando el simplex.(3p) 
 
 
SOLUCIÓN 
 
a) (2p. cada fallo -1 o -0.5 según el fallo) 
 
 
b) La ruta crítica es la más larga, que es la secuencia de actividades A-B-C-E-H-I, y tiene duración 63.(1p) 
c) El PL tiene las siguientes variables de decisión: 
𝑥𝑖𝑗 = {
1, 𝑒𝑙 𝑎𝑟𝑐𝑜 (𝑖, 𝑗) 𝑒𝑠𝑡á 𝑒𝑛 𝑙𝑎 𝑟𝑢𝑡𝑎 
0, 𝑒𝑙 𝑎𝑟𝑐𝑜 (𝑖, 𝑗)𝑛𝑜 𝑒𝑠𝑡ç𝑎 𝑒𝑛 𝑙𝑎 𝑟𝑢𝑡𝑎
 
 
La búsqueda de la ruta más larga tiene la siguiente función objetivo 
max 𝑍 = 20𝑥12 + 10𝑥23 + 11𝑥24 + 8𝑥35 + 7𝑥56 + 12𝑥47 + 6𝑥68 + 13𝑥67 + 5𝑥78 
(v de decisión y FO: 1p. Si pone min Z son 0p) 
) 
Las restricciones son el balance de flujo en cada nodo, donde ingresa 1 en el nodo 1 y sale 1 en el nodo 8 
(2p) 
• 𝑥12 − 1 = 0 
• 𝑥23 + 𝑥24 − 𝑥12 = 0 
• 𝑥35 − 𝑥23 = 0 
• 𝑥45 + 𝑥47 − 𝑥24 = 0 
• 𝑥65 − 𝑥45 − 𝑥35 = 0 
• 𝑥68 + 𝑥67 − 𝑥56 = 0 
• 𝑥78 − 𝑥47 − 𝑥65 = 0 
• 1 − 𝑥78 − 𝑥68 = 0 
 
𝑥𝑖𝑗 ∈ {0,1}