Practica1_O2_2018_II_solución

Vista previa del material en texto

1 
 
 
 
FACULTAD DE INGENIERÍA 
 
INVESTIGACIÓN DE OPERACIONES 2 
SEMESTRE 2018-II 
PRÁCTICA 1 
LUNES, 10 DE SEPTIEMBRE DE 2018 
Nombre:___________________________________________________________________________ 
Sección:___________________ 
 
Cuando se solicite reclamo, deberá adjuntarse copia de la solución publicada (sólo del ejercicio sobre el que se reclame). El 
reclamo deberá basarse en errores de corrección en base a esa solución. Si simplemente se alega que se merece más 
puntaje, el reclamo no va a prosperar. 
 
1. (14p) Una compañía desea invertir en dos nuevos proyectos relacionados con telefonía móvil, que denotaremos como 
proyectos A y B. En el proyecto A es necesario invertir un mínimo de 2 millones de dólares, mientras que en el proyecto 
B no hay dicha restricción inferior. Tampoco se quiere invertir más de 15 millones en cada uno. El proyecto A generará 
un beneficio del 5% y el proyecto B del 7%. Se desea calcular la cantidad óptima a invertir en cada proyecto si se han 
puesto las siguientes metas, en orden de prioridad: 
 
M1. No se quiere invertir más de 25 millones en total. 
M2. La inversión mínima total será de 3 millones. 
M3. La inversión en cada proyecto no debe ser más del doble que en el otro. 
M4. Maximizar el beneficio 
M5. Invertir la misma cantidad en ambos proyectos 
 
Resuelve este problema usando el método gráfico, especificando claramente en cada etapa de la modelización por 
metas qué modelo se está resolviendo y cómo se cumple cada una de las metas. 
 
SOLUCIÓN 
 
El problema de PL multiobjetivo por metas y prioridades es el siguiente: (2p) 
 
min 𝑍 = 𝑃1 𝑒1 + 𝑃2 𝑑2 + 𝑃3 (𝑒3 + 𝑑3) + 𝑃4 𝑑4 + 𝑃5(𝑑5 + 𝑒5) 
sa: 
 
𝑥𝐴 ≥ 2; 𝑥𝐴 ≤ 15; 𝑥𝐵 ≤ 15 
𝑥𝐴 + 𝑥𝐵 − 𝑒1 ≤ 25 
𝑥𝐴 + 𝑥𝐵 + 𝑑2 ≥ 3 
𝑥𝐴 ≤ 2𝑥𝐵 ⇒ 𝑥𝐴 − 2𝑥𝐵 − 𝑒3 ≤ 0 
𝑥𝐵 ≤ 2𝑥𝐴 ⇒ 2𝑥𝐴 − 𝑥𝐵 + 𝑑3 ≥ 0 
5𝑥𝐴 + 7𝑥𝐵 + 𝑑4 ≥ 𝑀 
𝑥𝐴 − 𝑥𝐵 + 𝑑5 − 𝑒5 = 0 
𝑥𝑖 , 𝑑𝑖 , 𝑒𝑖 ≥ 0 
 
 
Etapa 1 
(modelo 1p, resolución 1p) 
min 𝑍 = 𝑒1 
sa: 
𝑥𝐴 ≥ 2; 𝑥𝐴 ≤ 15; 𝑥𝐵 ≤ 15 
𝑥𝐴 + 𝑥𝐵 − 𝑒1 ≤ 25 
𝑥𝑖 , 𝑒𝑖 ≥ 0 
La región factible para el caso 𝑒1 = 0 se muestra en la figura. La solución 𝑒1 = 0 
es, por tanto, factible. La meta 1 se cumple. 
 
2 
 
 
 
 
 
Etapa 2 
(modelo 1p, resolución 1p) 
min 𝑍 = 𝑑2 
sa: 
 
𝑥𝐴 ≥ 2; 𝑥𝐴 ≤ 15; 𝑥𝐵 ≤ 15 
𝑥𝐴 + 𝑥𝐵 ≤ 25 
𝑥𝐴 + 𝑥𝐵 + 𝑑2 ≥ 3 
𝑥𝑖 , 𝑑𝑖 ≥ 0 
 
La región factible para el caso más favorable, donde 𝑑2 = 0, se muestra en la 
figura. Por tanto, la meta 2 también se cumple. 
 
Etapa 3 
(modelo 2p, resolución 1p) 
min 𝑍 = 𝑒3 + 𝑑3 
sa: 
𝑥𝐴 ≥ 2; 𝑥𝐴 ≤ 15; 𝑥𝐵 ≤ 15 
𝑥𝐴 + 𝑥𝐵 ≤ 25 
𝑥𝐴 + 𝑥𝐵 ≥ 3 
𝑥𝐴 − 2𝑥𝐵 − 𝑒3 ≤ 0 
2𝑥𝐴 − 𝑥𝐵 + 𝑑3 ≥ 0 
𝑥𝑖 , 𝑑𝑖 , 𝑒𝑖 ≥ 0 
 
La región factible que corresponde con el caso 𝑑3 = 𝑒3 = 0 se 
muestra en la figura de la der4echa. Puede verse entonces que la meta 3 también se cumple. 
 
Esta meta también puede escribirse como 
𝑥𝐴 − 2𝑥𝐵 − 𝑒31 ≤ 0 
𝑥𝐵 − 2𝑥𝐴 − 𝑒32 ≤ 0 
con dos variables de exceso diferentes. La FO sería 
min 𝑍 = 𝑒32 + 𝑒33 
 
La solución sería la misma 
Etapa 4 
(modelo 2p, resolución 1p) 
min 𝑍 = 𝑑4 
sa: 
 
𝑥𝐴 ≥ 2; 𝑥𝐴 ≤ 15; 𝑥𝐵 ≤ 15 
𝑥𝐴 + 𝑥𝐵 ≤ 25 
𝑥𝐴 + 𝑥𝐵 ≥ 3 
𝑥𝐴 − 2𝑥𝐵 ≤ 0 
2𝑥𝐴 − 𝑥𝐵 ≥ 0 
5𝑥𝐴 + 7𝑥𝐵 + 𝑑4 ≥ 𝑀 
 
Si asumimos la situación más favorable, con 𝑑4 = 0 tenemos que 
5𝑥𝐴 + 7𝑥𝐵 = 𝑀 es un conjunto de rectas paralelas, y que 𝑀 
 crece cuando nos desplazamos hacia el noroeste. El máximo valor 
de 𝑀 se alcanzaría en el punto A: (10,15) 
A 
3 
 
 
 
Otra forma de resolverlo es reescribiendo este modelo como 
max 𝑍 = 5𝑥𝐴 + 7𝑥𝐵 
sa: 
𝑥𝐴 ≥ 2; 𝑥𝐴 ≤ 15; 𝑥𝐵 ≤ 15 
𝑥𝐴 + 𝑥𝐵 ≤ 25 
𝑥𝐴 + 𝑥𝐵 ≥ 3 
𝑥𝐴 − 2𝑥𝐵 ≤ 0 
2𝑥𝐴 − 𝑥𝐵 ≥ 0 
 
Para resolverlo gráficamente dibujamos las rectas paralelas 𝑍 = 5𝑥𝐴 + 7𝑥𝐵 de forma que crezca 𝑍 hasta que nos 
encontramos en la frontera de la región factible. Gráficamente, vemos que el óptimo es el punto A (10,15), donde el 
beneficio es 5(10) + 7(15) = 155 ⇒ 1.55 millones de dólares 
 
 
 
Etapa 5 
(modelo 1p, resolución 1p) 
El modelo a resolver es: 
min 𝑍 = 𝑑5 + 𝑒5 
sa: 
 
𝑥𝐴 ≥ 2; 𝑥𝐴 ≤ 15; 𝑥𝐵 ≤ 15 
𝑥𝐴 + 𝑥𝐵 ≤ 25 
𝑥𝐴 + 𝑥𝐵 ≥ 3 
𝑥𝐴 − 2𝑥𝐵 ≤ 0 
2𝑥𝐴 − 𝑥𝐵 ≥ 0 
5𝑥𝐴 + 7𝑥𝐵 = 155 
𝑥𝐴 − 𝑥𝐵 + 𝑑5 − 𝑒5 = 0 
𝑥𝑖 , 𝑑𝑖 , 𝑒𝑖 ≥ 0 
 
Como de la etapa anterior la región factible se ha reducido ya al punto (10,15), no hay margen para que esta 
meta se cumpla, por lo que la solución sigue siendo (10,15). Se invierten así 25 millones, y el beneficio es de 1.55 
millones, que es el 6.2% de rentabilidad. 
 
 
4 
 
2. (6p) La siguiente red muestra una serie de nodos que 
representan localizaciones geográficas, y donde los 
números de las flechas representan la distancia entre los 
puntos que unen. Determine el camino más corto para ir 
de A a F aplicando programación dinámica. Observa que el 
arco entre B y C puede recorrerse en ambos sentidos. 
Justifique la respuesta. 
 
SOLUCIÓN 
 
Redibujamos la red par que todas las trayectorias tengan el mismo número de etapas. Para ello, añadimos nodos 
ficticios. 
 
 
Hay 4 etapas. Para cada una construimos una tabla. 
 
Etapa 1 (1p) 
x1 f1(s1,x1)=d11 
s1 F f1* X1* 
D 3 3 F 
E 6 6 F 
Etapa 2 (1p) 
 
x2 f2(s2,x2)=d22+f1*(s1) 
s2 D E f2* X2* 
B' 8 8 8 D o E 
C' 5 10 5 D 
Etapa 3 (1p) 
x3 f3(s3,x3)=d33+f2*(s2) 
s3 B' C' f3* X3* 
B 8 7 7 C' 
C 10 5 5 C' 
Etapa 4 (1p) 
 
x3 f3(s3,x3)=d33+f2*(s2) 
s3 B C f4* X4* 
A 8 8 8 B o C 
 
La ruta mínima tiene una distancia de 8 unidades, y hay dos recorridos posibles: 
A-B-C-D-F (1p) o A-C-D-F (1p)