Examen 2013-2

Vista previa del material en texto

Pontificia Universidad Católica de Chile
Escuela de Administración
EAA-251 Métodos de Optimización
Examen (120 puntos, 120 minutos)
Profesores: 	Marcos Singer
Bárbara Prieto 
Pascuala Domínguez
Christian Villalobos
Fecha: 		5 de diciembre de 2013
Pregunta 1 (40 puntos)
La multitienda “la navideña” está planificando la importación de juguetes para la próxima temporada de navidad. Específicamente, la empresa ha decidido importar 4 tipos de juguetes, todos los cuales son empacados en cajas del mismo tamaño que contienen 6, 12 o 24 unidades según el tamaño del juguete. Los tipos de juguetes a importar son:
· Juguetes didácticos para preescolares
· Peluches
· Autos radiocontrolados y a fricción
· Muñecas
La empresa cuenta con una bodega con capacidad máxima para guardar 300 cajas de juguetes.
Cada caja con muñecas tiene un costo de $100 mil pesos para la multitienda, en tanto que los demás tipos de juguetes tienen un costo un poco menor. La empresa tiene un presupuesto máximo de 40 millones de pesos para destinar a la compra de juguetes para esta navidad.
Además del costo directo del producto, la empresa debe hacer una fuerte inversión en publicidad y fuerza de ventas. Para este ítem, la multitienda cuenta con un presupuesto de 24 millones de pesos. Cada tipo de juguete tiene un costo unitario en publicidad y ventas diferente.
La empresa ha recientemente firmado un contrato con la junta nacional de jardines infantiles (JUNJI), a quien se ha comprometido a entregar 5 cajas de juguetes didácticos para esta navidad.
El objetivo de la multitienda es maximizar la utilidad derivada de la venta de sus juguetes. Se sabe que cada caja de peluches tiene un margen de utilidad de 240 mil pesos. Los demás productos tienen niveles de utilidad diferentes.
Los siguientes son algunos de los tableaus asociados al problema que enfrenta “la navideña”:
	A
	32
	100
	26
	0
	0
	0
	-2,8
	0
	-67.200
	
	0,4
	0,5
	0,2
	0
	1
	0
	-0,01
	0
	60
	
	0
	30
	0
	0
	0
	1
	-1
	0
	16.000
	
	0,6
	0,5
	0,8
	1
	0
	0
	0,01
	0
	240
	
	-1
	0
	0
	0
	0
	0
	0
	1
	-5
	
	
	
	
	
	
	
	
	
	
	B
	-48
	0
	-14
	0
	-200
	0
	-0,8
	0
	-79.200
	
	0,8
	1
	0,4
	0
	2
	0
	-0,02
	0
	120
	
	-24
	0
	-12
	0
	-60
	1
	-0,4
	0
	12.400
	
	0,2
	0
	0,6
	1
	-1
	0
	0,02
	0
	180
	
	-1
	0
	0
	0
	0
	0
	0
	1
	-5
	
	
	
	
	
	
	
	
	
	
	C
	0
	60
	10
	0
	-80
	0
	-2
	0
	-72.000
	
	1
	1
	0,5
	0
	2,5
	0
	-0,025
	0
	150
	
	0
	30
	0
	0
	0
	1
	-1
	0
	16.000
	
	0
	-0,25
	0,5
	1
	-1,5
	0
	0,025
	0
	150
	
	0
	1,25
	0,5
	0
	2,5
	0
	-0,025
	1
	145
	
	
	
	
	
	
	
	
	
	
	D
	0
	0
	-14
	0
	-200
	0
	-0,8
	-48
	-78.960
	
	1
	0
	0
	0
	0
	0
	0
	-1
	5
	
	0
	0
	-12
	0
	-60
	1
	-0,40
	-24
	12.520
	
	0
	0
	0,6
	1
	-1
	0
	0,02
	0,2
	179
	
	0
	1
	0,4
	0
	2
	0
	-0,02
	0,8
	116
	
	
	
	
	
	
	
	
	
	
	E
	0
	35
	0
	0
	-130
	0
	-2
	-20
	-74.900
	
	1
	0
	0
	0
	0
	0
	0
	-1
	5
	
	0
	30
	0
	0
	0
	1
	-1,0
	0
	16.000
	
	0
	-2
	0
	1
	-4
	0
	0,05
	-1
	5
	
	0
	3
	1
	0
	5
	0
	-0,05
	2
	290
A partir de lo anterior, responda:
(a) Modele el problema de programación lineal que enfrenta “la navideña”. Defina claramente variables, función objetivo y restricciones. (10 puntos)
(b) Determine la solución óptima del problema. ¿Cuántas cajas de cada tipo de juguetes debiera importar y cuál es el nivel de utilidad total que la empresa alcanzaría? (3 puntos)
(c) ¿Qué restricciones son activas en el óptimo?, ¿cuáles son los precios sombra de las restricciones activas?, ¿y de las no activas? (3 puntos)
(d) Suponga que se encuentra en el tableau A: 
a. ¿Qué vértice representa? ¿Qué tipo de juguetes estaría importando en dicho vértice?, ¿le conviene importar algún otro tipo de juguete? (2 puntos)
b. Al estar en A, ¿cuánto aumentaría la utilidad de la empresa si se decidiera importar 1 caja de peluches adicional? ¿Es esto consistente con lo que dice el enunciado: “Se sabe que cada caja de peluches tiene un margen de utilidad de 240 mil pesos”? Explique claramente. (4 puntos)
Para contestar las siguientes preguntas, asuma que se encuentra operando según el tableau de la solución óptima. Responda cada pregunta de manera independiente.
(e) La empresa está planeando ampliar su bodega con el fin de tener mayor capacidad para almacenar los productos que venderá en la temporada navideña. Específicamente, la multitienda tiene el plan de ampliar en un 5% la capacidad de la bodega, lo que tendría un costo de 4 millones de pesos. ¿Cómo afectaría la decisión óptima de la empresa en caso de que se hiciera la ampliación de la bodega?, ¿es conveniente llevarla a cabo? Fundamente su respuesta (6 puntos)
(f) En caso de que la multitienda consiguiera 1 millón de pesos adicional de presupuesto, ¿a qué le convendría más destinarlo: a la compra (importación) de cajas de juguetes o a publicidad? Determine cómo cambiaría la solución óptima del problema y el valor de la función objetivo en cada caso. Explique claramente (6 puntos) 
(g) La empresa está interesada en potenciar la relación comercial con la JUNJI, ya que piensa que dicho vínculo es doblemente beneficioso para ella. La existencia de un compromiso de venta de juguetes a la JUNJI no sólo le permite a la empresa asegurar una cierta cantidad vendida, sino que a la vez representa una forma de aportar a los sectores más vulnerables debido a que esos juguetes son repartidos en los jardines infantiles de manera gratuita. Analice las consecuencias de la existencia de este contrato para la multitienda. ¿Qué pasaría si no existiera tal compromiso? Explique su respuesta en detalle (6 puntos) 
PAUTA
(a) Al pivotear hacia atrás se llega al siguiente tableau:
	200
	240
	250
	280
	0
	0
	0
	0
	0
	1
	1
	1
	1
	1
	0
	0
	0
	300
	60
	80
	80
	100
	0
	1
	0
	0
	40.000
	60
	50
	80
	100
	0
	0
	1
	0
	24.000
	-1
	0
	0
	0
	0
	0
	0
	1
	-5
Variables:
	X1: cajas de juguetes didácticos a importar
	X2: cajas de peluches a importar
	X3: cajas de autos a importar
	X4: cajas de muñecas a importar
La modelación es:
Maximizar 200 x1 + 240 x2 + 250 x3 + 280x4
Sujeto a:
	x1 + x2 + x3 + x4 ≤ 300			capacidad bodega
60x1 + 80x2 + 80x3 + 100x4 ≤ 40.000		presupuesto importación
60x1 + 50x2 + 80x3 + 100x4 ≤ 24.000		presupuesto publicidad
x1 ≥ 5						compromiso JUNJI
x1, x2, x3 , x4 ≥ 0				no negatividad
(b) Óptimo: 5 cajas juguetes didácticos, 116 cajas de peluches y 179 cajas de muñecas. Utilidad = M$78.960 (tableau D)
	0
	0
	-14
	0
	-200
	0
	-0,8
	-48
	-78.960
	1
	0
	0
	0
	0
	0
	0
	-1
	5
	0
	0
	-12
	0
	-60
	1
	-0,40
	-24
	12.520
	0
	0
	0,6
	1
	-1
	0
	0,02
	0,2
	179
	0
	1
	0,4
	0
	2
	0
	-0,02
	0,8
	116
(c) Activas: no negatividad de x3, restricción 1 (bodega), restricción 3 (presupuesto publicidad) y restricción 4 (compromiso JUNJI). Precio sombra de estas restricciones: 14, 200, 0,8 y 48, respectivamente. Precio sombra de restricciones no activas es cero
(d) (i) Representa al vértice (0, 0, 0, 240), es decir, sólo se importan 240 cajas de muñecas. Sí le conviene comenzar a importar otros juguetes, ya que tiene bordes promisorios (costos reducidos positivos). (ii) Al estar en tableau A, si se importa una caja de peluches adicional aumentaría la función objetivo en 100 mil. Esto pasa porque por un lado se gana la utilidad de una caja de peluches (240 mil), pero al hacer esto se disminuye en 0,5 cajas de muñecas. En resumen, se gana neto 100 mil (240 – 0,5x280 = 100)
(e) Ampliación de bodega permitiría almacenar 15 cajas más. Utilidad adicional = 15 x 200 mil = 3 millones. Si el costo de ampliar es de 4 millones, no conviene
(f) No conviene destinarlo a la compra de más cajas, ya que esa restricción presupuestaria no es activa. Sí convendría destinarlo a publicidad: se podría alcanzar un mayor nivel de utilidad (1.000 mil x 0,8 = 800 mil)
(g) Si no existiera el compromiso se podría alcanzar un mayor nivel de utilidad (79.200 mil). Se puede ver en tableau B o bien a través del precio sombra de la restricción 4 (5 x 48 mil adicionales 240 mil adicionales pasar de 78.960 a 79.200 mil de utilidad.
Pregunta 2
Un laboratorio comercializa alrededor de 1.600 tipos de productos de diferentes formas y tamaños,tales como remedios, cremas y perfumes. Su distribución utiliza 165 tipos de caja, que también difieren en forma y tamaño. El laboratorio desea simplificar la operación, reduciendo los tipos de caja que necesita. Para ello cuenta con una base de datos sobre cuáles y cuántos productos se han empacado en cada caja que ha sido despachada. Por 
ejemplo, está registrado que el 3 de octubre se despachó a las 11:18 horas una caja tipo T con los siguientes productos: 16 perfumes X, 8 colonias Y y 5 cremas Z.
Utilizando DEA, plantee una manera en que se puedan eliminar las cajas menos convenientes para el laboratorio. Suponga que todos los tipos de caja cuestan lo mismo. Suponga además que cada caja siempre es llenada con la misma combinación de productos. En el ejemplo de la caja tipo T, esta caja se llena 100 veces con 16 perfumes X, 8 colonias Y y 5 cremas Z durante un mes. Para responder esta pregunta, usted debe:	
(i)	(10 ptos.) Plantear el programa lineal que corresponde señalando la interpretación de cada elemento del programa.
	(ii)	(5 ptos.) Explicar la manera en que se usará el programa lineal. Esto es, ¿qué instrucciones le daría a una persona (que conoce DEA) para realizar los cálculos?
	(iii)	(5 ptos.) Indicar un ejemplo que describa el caso en que se prescindirá de un tipo de caja, cuál es el motivo por el cual se descarta y cómo se reemplazará en el futuro.
i) 	El programa lineal DEA es el tradicional: Maximizar , sujeto a ;= 1; i 0 para i = 1,..., n. Los elementos son:
	 	en cuánto debería crecer (o disminuir, si es eficiente) la caja para tener una capacidad similar a sus benchmarks.
	yi 	vector de 1.600 componentes, que muestra la cantidad de productos empacados en la caja tipo i. Por ejemplo, yT = (16, 8, 5, 0, 0,…, 0). El primer componente del vector es el número de perfumes X, el segundo es el número de colonias Y, el tercero es el número de cremas Z y así sucesivamente.
	y0 	vector del tipo de caja que se está evaluando.
	i 	ponderador de los tipos de caja. Si en el óptimo i > 0, quiere decir que la caja tipo 0 podría ser parcialmente reemplazada por la caja tipo i.
	n	cantidad de tipos de caja. Dado que hay una caja 0, n = 164.
	ii)	Instrucciones:
	1) 	Determinar la manera en que se ha utilizado cada tipo de caja i. Expresar el uso como un vector yi.
	2) 	Designar el uso de la caja a ser evaluada como y0 y resolver el DEA.
	3)	Si el  > 1, la caja puede ser sustituida por cajas tipo i cuyos i > 0.
	4)	Hacer la evaluación con cada una de los 165 tipos de cajas. 
	iii)	Ejemplo: Supongamos que al correr el DEA para la caja tipo T se obtienen los siguientes valores:  = 1,2; A = 0,5; B = 0,3 y C = 0,2. En este caso se descarta T porque debería crecer en 20% para tener la capacidad de una combinación de cajas tipo A, B y C. En otras palabras, se necesitan 120 cajas tipo T para empacar la misma cantidad de productos que pueden empacar 50 cajas de tipo A, 30 de tipo B y 20 de tipo C.
Pregunta 3
De acuerdo al modelo geocéntrico planteado por el astrónomo greco-egipcio Ptolomeo (100-170), la Tierra es el centro del universo. Cada cuerpo celeste gira alrededor de la Tierra en una órbita circular de radio R que está en un plano orbital que pasa por el centro de la Tierra. El vector normal del plano orbital es p.
a) (10 ptos.) Suponiendo conocidos R y p, exprese las dos ecuaciones vectoriales que determinan la posición xi del cuerpo i; la primera ecuación hace que i pertenezca al plano orbital y la segunda hace que la órbita sea circular.
La mayoría de los cuerpos celestes observables en la Antigüedad cumplían con el modelo geocéntrico de Ptolomeo. Sin embargo, unos pocos cuerpos celestes llamados “planetas” tenían un comportamiento extraño: en vez de describir órbitas circulares, parecían detenerse y retroceder en el firmamento.
Para resolver este enigma, se planteó que los planetas describían dos órbitas circulares, tal como se muestra en la ilustración. Una pequeña de radio E llamada epiciclo, alrededor de un eje ei. A su vez el eje ei gira alrededor de la Tierra en una órbita grande de radio F llamada deferente.
b) (10 ptos.) Exprese las ecuaciones que determinan la posición ci del planeta i de acuerdo al modelo de Ptolomeo. Suponga que el epiciclo y el deferente están en el mismo plano orbital.
a) Las ecuaciones son las siguientes:
· El cuerpo i pertenece al plano orbital que pasa por el origen: p • xi = 0.
· La órbita es circular: ||xi|| = R.
b) Expresamos xi como la suma de un vector ei que corresponde al eje del epiciclo y que se mueve en el deferente, otro vector fi que va desde el eje del epiciclo al planeta, es decir, xi = ei + fi. Las ecuaciones son las siguientes:
· El epiciclo del planeta i pertenece al plano orbital: p • fi = 0.
· El deferente del planeta i pertenece al plano orbital: p • ei = 0.
· La órbita del epiciclo es circular alrededor de ei: ||fi|| = E.
· La órbita del eje del epiciclo (el deferente) es circular: ||ei|| = F.
 Pregunta 4 (40 puntos)
En lo que sigue, se analizará la resolución de un problema lineal de optimización, cuya área factible está representada por el siguiente gráfico:
Las restricciones del problema se definen en término de los vértices del gráfico, como:
· Restricción A: b - c - d
· Restricción B: a - b - c
· Restricción C: c - d - e
· Restricción D: a - c - e - f
· Restricción E: a - b - f
· Restricción F: b - d - e - f
En cualquier momento, usted se puede referir indistintamente a una restricción (por ejemplo, restricción A) o a su respectiva variable de holgura (vA para el mismo ejemplo). 
Geométricamente y sólo con argumentos gráficos (sin considerar el tableau entregado más adelante), responda las siguientes preguntas relativas al punto a:
a) ¿Cuáles restricciones son activas en el punto? ¿Es el punto degenerado? Justifique su respuesta (3 puntos).
b) Si usted tuviera un tableau asociado a este punto, ¿en cuáles columnas de este tableau (dicho de otro modo, las columnas asociadas a cuáles variables) se encuentra la matriz identidad (desordenada) y por qué? (5 puntos).
c) Suponga que b y d son los únicos vértices óptimos del problema y usted desea llegar a uno de ellos a partir del punto a, utilizando el Método Simplex. ¿Existe garantía de que usted realice menos iteraciones siguiendo la dirección a - b que la dirección a - c? Justifique su respuesta (5 puntos).
Ahora suponga que usted avanza por el borde que lleva de a a b. 
d) ¿Cuál es la variable no-básica asociada al vector dirección respectivo? (5 puntos).
e) En el vector dirección a – b ¿cuáles elementos del tienen valor positivo, negativo o nulo? (recuerde que cada elemento está asociado a una variable de holgura de alguna restricción). Justifique claramente su respuesta (7 puntos).
f) Si usted hubiera avanzado por este borde mediante el Método Simplex, ¿qué sucedería al aplicar el test de minimización? ¿Qué variable debiera salir de la base? (4 puntos).
Finalmente, se le entrega el siguiente tableau asociado al vértice b:
0
15/11
-
13/11
0
-
3/11
-
15
0
-
10/11
5/11
0
2/11
10
0
10/11
-
5/11
1
-
2/11
0
1
6/11
-
3/11
0
1/11
5
0
1
0
0
0
14/11
15/11
0
6/11
30
0
0
0
0
0
1
g) Con la información de este tableau, ¿puede usted determinar si el vértice b es óptimo o no? Justifique claramente su respuesta a partir de los contenidos enseñados en el curso (5 puntos).
h) Muestre que el vértice b es óptimo realizando una iteración del Método Simplex sobre el tableau entregado (6 puntos).
Geométricamente y sólo con argumentos gráficos (sin considerar los tableaus entregados más adelante), responda las siguientes preguntas relativas al punto a:
a) ¿Cuáles restricciones son activas en el punto? ¿Es el punto degenerado? Justifique su respuesta.
Existen 3 restricciones activas en el punto: B, E y D. El punto no es degenerado puesto que sólo hay n = 3 restricciones activas para el espacio R3. También se podría argumentar que solamente nacen 3 bordes adyacentes desde el punto en cuestión.
b) Si usted tuviera un tableau asociado a este punto, ¿en cuáles columnas de este tableau (dichode otro modo, las columnas asociadas a cuáles variables) se encuentra la matriz identidad (desordenada) y por qué?
Las columnas de la identidad siempre están asociadas a las variables básicas y viceversa. Dado que el punto es no-degenerado, las variables no-básicas corresponden a todas las restricciones activas: B, E y D y las variables básicas son el resto: A, C y F. En conclusión, las columnas del tableau donde se encuentra la matriz identidad son las asociadas a las variables de holgura de las restricciones A, C y F.
c) Suponga que b y d son los únicos vértices óptimos del problema y usted desea llegar a uno de ellos a partir del punto a, utilizando el Método Simplex. ¿Existe garantía de que usted realice menos iteraciones siguiendo la dirección a - b que la dirección a - c? Justifique su respuesta
No existe garantía, puesto que el punto b es degenerado. Esto quiere decir que si se sigue la dirección a-b se podría llegar a un tableau que indique que el punto b no es óptimo y se tendría que realizar iteraciones adicionales para demostrar que el punto sí lo es. 
Si se sigue la dirección a-c, se debe realizar 2 o más iteraciones y si se sigue la dirección a-b, 1 o más. Se concluye que no existe garantía de llegar en menos iteraciones (sí existiría si es que el punto b fuera no-degenerado, pero éste no es el caso).
Ahora suponga que usted avanza por el borde que lleva de a a b. 
d) ¿Cuál es la variable no-básica asociada al vector dirección respectivo?
Al avanzar por el vector dirección a-b las restricciones que siguen activas son las B y E, por lo que la variable asociada al vector es la variable de holgura de la restricción D
e) En el vector dirección a – b ¿cuáles elementos del tienen valor positivo, negativo o nulo? (recuerde que cada elemento está asociado a una variable de holgura de alguna restricción). Justifique claramente su respuesta.
En general, el elemento asociado a la variable entrante tiene valor positivo y los elementos asociados al resto de las variables no básicas tienen valor nulo. Por ende, la componente asociada a D tienen valor positivo y las asociadas a B y E tienen valor nulo.
En las restricciones asociadas a variables básicas (A,C,F), los elementos asociados a una restricción cuya holgura disminuye de valor (es decir, de restricciones a las que se acerca la semirrecta que parte en el punto y avanza por el vector dirección) tienen valores negativos. En el caso particular de este problema, todas las restricciones se van “haciendo más activas” por lo que están asociadas a elementos con valor negativo.
f) Si usted hubiera avanzado por este borde mediante el Método Simplex, ¿qué sucedería al aplicar el test de minimización? ¿Qué variable debiera salir de la base?
Al avanzar desde el punto a al b utilizando el Método Simplex hay un empate en el test de minimización. Esto se debe a que el punto b es degenerado, por lo que se activan 2 restricciones cuando se llega al mismo: las restricciones A y F (ambas asociadas a variables básicas). Como siempre, cualquiera de las restricciones empatadas, A o F, puede ser elegida indistintamente como saliente de la base
g) Con la información de este tableau, ¿puede usted determinar si el vértice b es óptimo o no? Justifique claramente su respuesta a partir de los contenidos enseñados en el curso
Con la información del tableau NO se puede determinar la optimalidad del punto, puesto que el criterio de los costos reducidos es una condición necesaria, pero no suficiente para determinar optimalidad. Si el punto fuera no-degenerado, sí se podría decir que no es óptimo, pero éste no es el caso.
h) Muestre que el vértice b es óptimo realizando una iteración del Método Simplex sobre el tableau entregado.
Iterando:
0
15/11
-
13/11
0
-
3/11
-
15
0
-
10/11
5/11
0
2/11
10
0
10/11
-
5/11
1
-
2/11
0
1
6/11
-
3/11
0
1/11
5
0
1
0
0
0
14/11
15/11
0
6/11
30
0
0
0
0
0
1
0
0
-
1/2
-
3/2
0
-
15
0
0
0
1
0
10
0
1
-
1/2
11/10
-
1/5
0
1
0
0
-
3/5
1/5
5
0
1
0
0
0
0
2
-
7/5
4/5
30
0
0
0
0
0
1
Dado que en la iteración el test de minimización arrojó valor nulo, el nuevo tableau todavía corresponde al vértice b. Como los costos reducidos son todos negativos, el vértice b es óptimo
8
å
=
n
i
i
1
l
MarteTierraDeferenteEpicicloTierraDeferentee
xyz4
abcdef
0
1
y
y
f
l
³
å
=
n
i
i
i