Examen 2012-1 (Solo pauta)

Vista previa del material en texto

Pontificia Universidad Católica de Chile		
Escuela de Administración
EAA-251 Métodos de Optimización
Pauta Examen (120 puntos)
Pregunta 1 (40 puntos)
Pauta
i) Escriba el problema lineal e identifique las caras asociadas a cada restricción según los vértices que contiene cada cara (por ejemplo: asociado a la restricción …, se tiene la cara asociada a los vértices e, f y d)
Maximizar: z = 4x + 3y + 5z 
Sujeto a:	 4x + 5y + 4z ≤ 20			Restricción 1
	 –18x – 5y + 2z ≤ 0			Restricción 2
	 –3x + 10y + 7z ≤ 30			Restricción 3
	 x 0; y 0; z 0.
Restricción 1: cara a-b-f
Restricción 2: cara e-d-f
Restricción 3: cara b-c-d-f
Restricción x 0: cara c-d-e
Restricción y 0: cara a-f-e
Restricción z 0: cara a-b-c-e
ii) Identifique si la solución inicial es o no degenerada. Justifique su respuesta. En , ¿siempre ocurre que una solución degenerada tiene 4 o más bordes adyacentes factibles? Justifique claramente su respuesta.
La solución es degenerada porque una variable básica tiene valor nulo, lo que implica que hay más de 3 restricciones activas en el vértice (definición de degenerancia). Alternativamente, se puede decir que es degenerada porque tiene más de 3 bordes adyacentes factibles. Sin embargo, esto es una condición suficiente, pero no necesaria para la degenerancia. Como contraejemplo, basta tomar una solución no-degenerada y agregarle una restricción activa pero redundante, de modo que no se generen nuevos bordes.
iii) Señale si los vectores dirección del tableau inicial corresponden a bordes factibles o no. En cualquier caso, explicite estos vectores en el grafico y la variable asociada a la respectiva columna en el tableau.
Vectores:
Los vectores de las columnas x e y están asociados a bordes factibles, el vector de la columna z, no.
iv) Suponga que usted seguirá la dirección indicada por la Regla de Dantzig. ¿Cuál de los vértices del gráfico será el siguiente vértice del Simplex? Sin construir un nuevo tableau, determine si la nueva solución será degenerada. Justifique su respuesta en base a los conocimientos entregados en el curso. 
La regla de Dantzig hace que la variable z entre a la base. El test de minimización tendría valor nulo, por lo que el siguiente vértice es el mismo que el inicial, igualmente degenerado (porque es el mismo vértice y la degenerancia es independiente de la representación básica del Método Simplex).
v) En otro gráfico, dibuje los vectores dirección asociados al segundo tableau e indique si estas direcciones están asociadas a bordes factibles o no.
Los vectores de las columnas x e y están asociados a bordes factibles, el vector de la columna h2, no.
vi) Nuevamente, suponga que usted seguirá la dirección indicada por la Regla de Dantzig. Sin construir un nuevo tableau, indique cuál de los vértices del gráfico será el siguiente vértice entregado por el Método Simplex e indique si esta solución será degenerada o no. 
La regla de Dantzig hace que la variable x entre a la base. El test de minimización tendría tiene valor 1/2 y ocurre un empate en el test de minimización, por lo que el siguiente vértice es degenerado. Como se sigue el vector dirección x, asociado al borde factible e-f, e nuevo vértice será el f.
vii) ¿Cuál de los vértices del gráfico es el dado por el tercer tableau? Según la información del tableau, ¿puede usted afirmar si el vértice es óptimo o no? Justifique claramente su respuesta.
El vértice del tercer tableau es el vértice f. NO se puede asegurar que el vértice sea o no óptimo, puesto que es degenerado y sus costos reducidos no son todos negativos. La condición de optimalidad del simplex dice que si los costos reducidos son todos negativos, se está en un máximo del problema, pero no viceversa (es condición suficiente de optimalidad, pero no necesaria). 
viii) Verifique que los multiplicadores entregados por el tercer tableau cumplen con la condición de KKT: , donde es el multiplicador de KKT y es el vector normal asociado a la restricción activa i. Con esta nueva información, ¿puede usted afirmar si el vértice asociado es óptimo o no?
Se tiene que cumplir que:
Reemplazando los vectores dirección y los multiplicadores de KKT dados por inversos aditivos de los costos reducidos, se tiene que: 
Consistentemente con el punto anterior, no se puede afirmar que el punto sea óptimo o no, puesto que, aun cuando no se cumple KKT (que junto con la factibilidad es condición necesaria y suficiente de optimalidad), en el sistema de arriba no se está considerando todas las restricciones activas en el punto, sino solamente las que corresponden a las variables fuera de base en el tercer tableau. 
Alternativamente, se puede considerar la restricción que falta y colocarle multiplicador nulo (la variable está fuera de base por lo que su costo reducido es cero). El resultado no cambia.
ix) Compruebe la optimalidad de la solución dada por el cuarto tableau con ayuda de las Condiciones de KKT. ¿Cómo se relaciona el vértice dado por este tableau con el vértice dado por el tercer tableau? Comente.
Se tiene que las siguientes restricciones son activas:
		 4x + 5y + 4z ≤ 20			
	 –18x – 5y + 2z ≤ 0			
	 –3x + 10y + 7z ≤ 30			
	 y 0
La condición de KKT se cumple si los multiplicadores en el siguiente sistema son positivos:
Utilizando los costos reducidos del cuarto tableau, se tiene ; ; ;, que cumplen con el sistema y son positivos. 
Este es el mismo vértice que el dado por el tableau anterior. Sin embargo, este tableau, a diferencia del anterior, permite concluir que el vértice f es óptimo.
x) Ahora que conoce toda la información, indique qué secuencia de tableaus hubiera escogido usted para llegar al tableau óptimo en el menor número de iteraciones. Indique claramente que variables entrantes y salientes de la base hubiera utilizado en cada iteración del método.
Para este ejercicio particular, lo más lógico es tratar de salir de la degenerancia y llegar al tableau óptimo (cuarto tableau) asociado al vértice f por el camino más corto. Esto se logra pasando del primer al segundo tableau Esto se logra haciendo entrar la variable x a la base, de modo que salga h1. Luego debe entrar la variable z y se debe elegir h3 para que salga de la base, de modo que se tengan las mismas variables básicas que en el cuarto tableau. De este modo se llega al tableau óptimo al cabo de 3 iteraciones en vez de 4.
Pregunta 2 (50 puntos)
a) Modele el problema que enfrenta la empresa como programa lineal (10 puntos)
Al pivotear de reversa se llega al siguiente tableau inicial:
	50
	40
	30
	25
	0
	0
	0
	0
	0
	0
	1
	1
	1
	1
	1
	0
	0
	0
	0
	40
	50
	40
	20
	30
	0
	1
	0
	0
	0
	1.400
	25
	30
	40
	30
	0
	0
	1
	0
	0
	1.000
	1
	0
	0
	0
	0
	0
	0
	1
	0
	20
	0
	0
	-1
	-1
	0
	0
	0
	0
	1
	-6
Variables:
e: n° de conciertos en Estados Unidos
c: n° de conciertos en Canadá
m: n° de conciertos en México
b: n° de conciertos en Brasil
Maximizar z = 50e + 40c + 30m + 25 b
Sujeto a:
	(1) e + c + m + b ≤ 40				máximo conciertos de la gira
(2) 50e + 40c + 20m + 30 b ≤ 1.400		presupuesto
(3) 25e + 30c + 40m + 30b ≤ 1.000		horas de profesionales
(4) e ≤ 20					máximo conciertos en USA
(5) m + b ≥ 6					mínimo conciertos Latinoamérica 
(6) e , c , m, b ≥ 0				no negatividad
b) Determine qué valores toman las incógnitas A, B, C, D y E (5 puntos)
A= 40
B= 1.400
C= 1.000
D= 50 (en %) o 20 (en número absoluto)
E= 6
c) ¿Cuál es la solución óptima del problema? Determine la cantidad óptima de conciertos a realizar en cada país y el valor de la función objetivo en el óptimo. ¿Es una solución única? (4 puntos)
e = 20
c = 6
m = 8
z = 1.480
es una solución única
d) ¿Cuáles son las restricciones activas en el óptimo?, ¿cuál es el precio sombra de cada una de ellas? (4 puntos)
	TABLEAU D
	
	
	
	
	
	
	
	
	0
	0
	0
	-8
	0
	-0,7
	-0,4
	-5
	0
	-1.480
	0
	0
	0
	0,1
	1
	-0,01
	-0,02
	0
	0
	6
	0
	1
	0
	0,6
	0
	0,04
	-0,02
	-1,5
	0
	6
	0
	0
	1
	0,3
	0
	-0,03
	0,04
	0,5
	0
	8
	1
	0
	0
	0
	0
	0
	0
	1
	0
	20
	0
	0
	0
	-0,7
	0
	-0,03
	0,04
	0,51
	2
Activas: no negatividad de b y las restricciones (2), (3) y (4). Sus precios sombra son 8, 0,7 , 0,4 y 5, respectivamente 
e) Demuestre, utilizando el teorema de KKT, que los precios sombra que usted estableció en su respuesta anterior son los correctos (8 puntos)
 (50, 40, 30, 25) =  (0, 0, 0, -1) +  (50, 40, 20, 30) +  (25, 30, 40, 30) +  (1, 0, 0, 0)
Al resolver,  = 8,  = 0,7,  = 0,4 y  =5
f) Observe el tableau B y conteste las siguientes preguntas
i. ¿Qué vértice representa?, ¿cuántos conciertos se realizarían en cada país? (1 punto)
Vértice (20, 10, 0, 0) (20 conciertos en Estados Unidos y 10 en Canadá
ii. ¿Es óptimo este vértice?, justifique su respuesta (1 punto)
No es óptimo, ya que existe un borde promisorio (costo reducido positivo)
iii. Suponga que se encuentra tomando la decisión asociada al tableau B y decide trabajar en la producción de un concierto en México. ¿En cuánto se incrementaría el valor de la función objetivo si produce un concierto en ese país? ¿Se cumple, tal como dice el enunciado, que “cada show en México representa una utilidad de 30 mil dólares”? Fundamente su respuesta (5 puntos)
Por cada concierto en México, aumentaría en 10 (mil dólares) el valor de la función objetivo. Esto debido a que por cada concierto en México, disminuiría en 0,5 el número de conciertos en Canadá. Por lo tanto, la utilidad neta sería = +30 – 40 x0,5 = 10.
En resumen, sí se cumple lo que dice el enunciado, el problema es que junto con aumentar los conciertos en México disminuirían los de Canadá y, el neto, sería una ganancia de sólo 10 mil dólares (en vez de los 30 mil)
Para responder las siguientes preguntas, que son independientes entre sí, asuma que se encuentra tomando la decisión óptima:
g) El gerente comercial de la compañía ha determinado, en base a estudios de mercado realizados en los 4 países que contempla la gira, que existe una gran demanda por asistir a los conciertos de Lionel Richie. Este ejecutivo asegura que sería recomendable alargar la gira debido al creciente interés del público por escuchar al intérprete de “Hello”, “Say You, Say Me”, entre otras canciones que han estado en el N°1 de la lista Billboard. Determine cuál sería el beneficio de agregar 5 conciertos adicionales a los 40 que contempla originalmente la gira. Fundamente su respuesta (4 puntos)
No hay beneficio, la restricción de número máximo de conciertos no es activa
h) El gerente de finanzas de PS MEDIOS, viendo las conclusiones del estudio de mercado realizado por el gerente comercial, insiste en la necesidad de aumentar la inversión en este proyecto. Específicamente, el ejecutivo plantea la posibilidad de conseguir financiamiento adicional y, con esto, aumentar en un 10% el presupuesto destinado a la producción de la gira de Lionel Richie. Determine cuál sería el beneficio de contar con este presupuesto adicional. (4 puntos)
Restricción presupuestaria tiene un precio sombra de 0,7. Es decir, por cada 1 mil dólares adicionales invertidos, la función objetivo aumenta en 0,7 mil dólares.
Aumentar en un 10% el presupuesto, significa contar con 140 dólares adicionales, los que harían aumentar el valor de la función objetivo en 140 x 0,7
i) El gerente de recursos humanos, también incentivado por el manifiesto interés del público por ver a Lionel Richie, sugiere destinar más horas-hombre para la producción de la gira. Específicamente, se plantea la posibilidad de aumentar en un 10% las horas disponibles de profesionales, lo que tendría un costo adicional de 10 mil dólares. ¿Es conveniente para PS MEDIOS realizar esta inversión con el fin de incrementar las horas hombre dedicadas a la producción de la gira? Fundamente su respuesta (4 puntos)
Restricción de horas de profesionales tiene un precio sombra de 0,4. Aumentar en un 10% las horas disponibles significa contar con 100 horas adicionales, las que permitirían incrementar el valor de la función objetivo en 0,4x100 = 40 mil dólares. Como el costo de realizar esta inversión es de 10 mil dólares, sí le conviene.
Pregunta 3 (30 puntos)
a) Conjuntos:
P = {Línea Blanca, Vestuario, Menaje}	: tipos de productos
Z = {Norte, Centro, Sur}			: zonas de ventas
S = {1º, 2º}					: semestres
B = {San Joaquín, San Cristóbal}		: centros de distribución
Parámetros:
Cp [$/pll]	: costo compra del producto p
Tp [pll]		: cuota máxima del producto p
Dp,z,s [pll]	: demanda del producto p en la zona z durante el semestre s
Ab [pll]		: capacidad de almacenamiento del centro b
Ip,b [pll]	: inventario inicial del producto p en el centro b
Ns,b [pll]	: mínimo inventario al final del semestre s en el centro b
Fs,b [pll]	: capacidad de despacho durante el semestre s desde el centro b
Ep,z,b [$/pll]	: costo de distribución del producto p a la zona z desde el centro b
Pm,z,s [$/pll]	: precio del producto p en la zona z durante el semestre s
Op,s,b [$/pll]	: costo de obsolescencia del producto p almacenado en el centro b al final del semestre s
Variables: 
z [US$]	: función objetivo (utilidad contable, pero eventualmente no contable si se agrega una pérdida del 15% por pedidos no entregados)
vp,z,s [pll]	: ventas del producto p en la zona z durante el semestre s
cp,s,b [pll]	: compras del producto p durante el semestre s que se almacena en el centro b[footnoteRef:1] [1: Cuando las empresas compran bajo la modalidad “puesto en destino” (cost, insurance and freight en inglés o CIF), deben señalar dónde el vendedor debe entregar el producto. En el caso de importaciones, la unidad de Adquisiciones debe determinar el puerto de desembarco.] 
ip,s,b [pll]	: inventario del producto p al final del semestre s en el centro b
dp,z,s,b [pll]	: despacho del producto p a la zona z durante el semestre s desde el centro b
b) 
Maximizar: z [$] = – –
Sujeto a:
Unidad de Ventas:
				 		Demanda máxima
Unidad de Distribución:
				 		Despacho de demanda
				 			Capacidad de la flota
Unidad de Operaciones:
				 			Capacidad del centro
				Balance de inventario
					 		Inventario inicial
					 			Utilización de los centros
Unidad de Abastecimiento:
							Cuota de importación
	
c) Nuevo Parámetro:
Gp,s [$/pll]	: costo de traspaso del producto p entre centros el semestre s
Nueva Variable: 
gp,s,b [pll]	: traspaso del producto p durante el semestre s desde b
Cambios en el programa lineal: 
· 
En la función objetivo, agregar 
· 
Reemplazar 	 
por 
	
	
· 
Agregar 	
9
22
3
3
yy
zvvv
aaa
++
=
0,358
40183
36,961510
5
0
2
1
7
,
0
8
--
æöæöæöæö
ç÷ç÷ç÷ç÷
=--
ç÷ç÷ç÷ç÷
ç÷ç
-+
÷ç÷ç÷
èøèøèøèø
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
+
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
+
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
-
+
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
0
1
0
7
10
3
2
5
18
4
5
4
5
3
4
d
g
b
a
07
,
1
=
a
0
=
b
1
,
0
=
g
3
,
3
=
d
(
)
(
)
å
×
-
s
z
p
s
z
p
p
s
z
p
v
,
,
,
,
,
,
C
P
(
)
å
×
b
s
p
b
s
p
b
s
p
i
,
,
,
,
,
,
O
(
)
å
×
b
s
z
p
b
s
z
p
b
s
z
p
d
,
,
,
,
,
,
,
,
,
E
s
z
p
s
z
p
v
,
,
,
,
D
£
s
z
p
,
,
"
s
z
p
b
b
s
z
p
v
d
,
,
,
,
,
=
å
s
z
p
,
,
"
b
s
z
p
b
s
z
p
d
,
,
,
,
,
F
£
å
b
s
,
"
b
p
b
s
p
i
A
,
,
£
å
b
s
,
"
å
-
+
=
-
z
b
s
z
p
b
s
p
b
s
p
b
s
p
d
c
i
i
,
,
,
,
,
,
1
,
,
,
b
s
p
,
,
"
b
p
b
p
i
,
,
0
,
I
=
b
p
,
"
b
s
p
b
s
p
i
,
,
,
N
³
å
p
b
b
s
p
c
T
,
,
£
å
s
p
,
"
0
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
³
b
s
z
p
b
z
p
b
s
p
s
z
p
s
z
p
d
c
i
f
v
b
s
z
p
,
,
,
"
(
)
å
×
-
b
s
p
b
s
p
s
p
g
,
,
,
,
,
G
.
,
,
.
,
,
,
.
,
,
.
,
,
.
,
1
,
.
,
,
Crist
s
p
z
Crist
s
z
p
Joaq
s
p
Crist
s
p
Crist
s
p
Crist
s
p
g
d
g
c
i
i
-
-
+
+
=
å
-
s
p
,
"
.
,
,
.
,
,
,
.
,
,
.
,
,
.
,
1
,
.
,
,
Joaq
s
p
z
Joaq
s
z
p
Crist
s
p
Joaq
s
p
Joaq
s
p
Joaq
s
p
g
d
g
c
i
i
-
-
+
+
=
å
-
0
,
,
³
b
s
p
g
b
s
p
,
,
"
xyz422424abdfcexyz
xyz422424abdfcexyh
2