Ayudantía 08

Vista previa del material en texto

Pontificia Universidad Católica de Chile
Escuela de Administración
Primer Semestre 2012
EAA-251 Métodos de Optimización
Ayudantía Nº8 – Repaso Prueba 2
Profesores: Bárbara Prieto
Marcos Singer
Christian Villalobos
Ayudante: Andrés Cereceda
Ejercicio 1. Geometría Vectorial
Considere los siguientes vectores:
	a = (10, 20, 5)
	b = (5, 7, 2)
	c = (15, 40, 20)
	d = (10, 1, 9)
Con los cuales se forman dos rectas: (a + λb) y (c + µd)
a) Encuentre la intersección de estas dos rectas.
b) Detalle cuál es la condición que debe cumplirse para que las rectas sean paralelas, y dé un ejemplo.
c) En base a la respuesta en a) ¿De qué maneras se podría encontrar una solución a la intersección de las rectas?
d) ¿Qué tiene que ocurrir para que las rectas sean la misma? Dé un ejemplo.
e) ¿Cuáles son los componentes del vector d y los valores de λ, µ para que las rectas se intercepten en el punto (40, 62, 17)? 
f) ¿Qué debe ocurrir para que las rectas se intercepten en forma perpendicular? Resuelva. 
Ejercicio 2. Análisis Envolvente de Datos (DEA)
Considere que todos los vectores a continuación tienen n componentes. Responda las siguientes preguntas recordando que DEA evalúa mediante el siguiente programa lineal. Puede apoyarse en ejemplos de n = 2.
Maximizar 	ø
Sujeto a 	
 
 para i = 1,..., n.
a) Suponga que al evaluar la eficiencia de a mediante DEA resulta que b es uno de sus benchmark. ¿Está b en la frontera de factibilidad del problema como un todo, o habría que evaluar con un DEA a b y ver si acaso este es eficiente?
b) Si al evaluar la eficiencia de c mediante DEA el punto d no aparece como benchmark de c. ¿Está d en la frontera de factibilidad del problema como un todo? ¿Podría estarlo? 
c) Supongamos que se desconoce y0 pero se conocen . Además se conoce los valores óptimos de ¿Puede saberse en cuál punto intercepta la frontera de factibilidad?
d) ¿Cuál es el resultado del DEA si se reemplaza por ?
e) ¿Cuál es el efecto en la evaluación de la eficiencia si en vez de exigir se deja libre, es decir, que tome valores positivos o negativos?
Ejercicio 3. Precios Sombra - KKT 
Una empresa está maximizando la utilidad por la venta de los productos x e y. La empresa se enfrenta a las siguientes restricciones:
i) 3x + 2y 6		Insumos
ii) x + 2y 4		Mano de obra
iii) 2x 3		Demanda
Si las utilidades por x e y son de $6 por unidad y el óptimo está determinado por las restricciones i y ii se pide:
a) Encuentre el precio sombra de las restricciones mediante el teorema de KKT.
b)¿Cuántas dimensiones tiene el óptimo del problema?
c) ¿Qué pasa si el lado derecho de la restricción i cambia de 6 a 5? ¿Y si cambia de 6 a 7?¿Cambia su precio sombra?
d) ¿Cómo cambia la relación de los precios sombras encontrado en a) si sube la utilidad de x?
e) ¿Cómo cambia su respuesta en a) si el precio de x aumenta a $8? 
f) ¿Cómo cambia su respuesta en a) si el precio de x aumenta a $9?
g) ¿Cuántas dimensiones tiene ahora el óptimo del problema?
h) ¿Cómo cambia su respuesta en a) si el precio de y aumenta a $16?
Ejercicio 4. Programa Dual
En lo que sigue, se resolverá una modificación del problema del consumidor para funciones de utilidad lineales. Considere un consumidor que debe elegir la cantidad a consumir de dos bienes, y , los cuales tienen un precio de compra y , respectivamente. Estos productos ofrecen al consumidor una utilidad unitaria y , respectivamente, de modo que su función de utilidad es lineal. El consumidor debe maximizar su utilidad total, sujeto a una restricción presupuestaria que le impide gastar más de pesos, de modo que, bajo los supuestos de la Teoría del Consumidor, el problema de optimización que resuelve es:
Si denotamos por a la variable dual asociada a la restricción presupuestaria y asumimos que todos los parámetros del problema son estrictamente positivos, el valor óptimo de esta variable en el problema dual es .
a) Escriba el problema dual asociado al problema del consumidor para funciones de utilidad lineales .
b) Demuestre que la solución del problema dual es . 
c) ¿Cuál es la interpretación económica del valor de la variable dual en el óptimo? 
d) En base a la solución del problema dual obtenida en (ii), encuentre la solución óptima del problema primal . 
PAUTA AYUDANTÍA 8 – REPASO PRUEBA 2
Ejercicio 1 – Geometría Vectorial
Es importante recordar que el vector posición de una recta es el que determina en qué lugar del espacio se ubicará la recta (a) y el vector dirección el ángulo que tendrá dicha recta (b).
a) Para encontrar la intersección de las rectas, es necesario igualar ambas ecuaciones (a + λb) = (c + µd), esto se hace resolviendo el siguiente sistema;
i) 10 +5λ = 15 + 10µ
ii) 20 + 7λ = 40 + µ 
iii) 5 + 2λ = 20 + 9µ 
	Si se utilizan las ecuaciones i) y ii) se llega al resultado de que λ =3 y µ=1. Con lo que reemplazando en cualquiera de las dos ecuaciones de la recta, se llegaría a que el punto de intersección de ambas rectas es (25, 41, 11). El error de esta resolución está en que si se reemplazan los resultados de λ =3 y µ=1, en la ecuación iii) del sistema se llega a una contradicción (11=29), lo que significa matemáticamente que el problema no tiene solución, o geométricamente que ambas rectas no se cruzan.
b) La condición que se debe cumplir para que ambas rectas sean paralelas es que el vector dirección de una de las rectas sea una combinación lineal del vector dirección de la otra recta. 
Un ejemplo de esto es 2b = d, es decir 
b = (5, 7, 2) y 
d = 2*(5, 7, 2)= (10, 14, 4)
El sistema a resolver quedaría de la siguiente manera;
i) 10 +5λ = 15 + 10µ
ii) 20 + 7λ = 40 + 14µ 
iii) 5 + 2λ = 20 + 4µ 
	Manteniendo todo el resto de los vectores de las rectas constantes (como en la letra a) Las rectas seguirán sin tener un punto de intersección, pero ahora estarán sobrepuestas espacialmente de manera paralela.
c) Para encontrar una solución a la intersección de ambas rectas en un punto, se pueden dar una de dos condiciones;
i) Mover el vector posición de una de las dos rectas, lo que hace subir o bajar la recta que se está moviendo, de manera de que se encuentre con la otra, para esto se tendría que resolver el siguiente sistema, en que z es una tercera incógnita a encontrar:
(1) z +5λ= 15 + 10µ
(2) 20 + 7λ = 40 + 1µ 
(3) 5 + 2λ = 20 + 9µ
ii) Mover el vector posición de una de las dos rectas, lo que hace cambiar la inclinación de ese vector para encontrarse con la otra recta, para esto se resuelve el siguiente sistema nuevamente con z como tercera variable a encontrar:
(1) 10 +zλ = 15 + 10µ
(2) 20 + 7λ = 40 + 1µ 
(3) 5 + 2λ = 20 + 9µ
d) Para que las rectas sean iguales, el vector posición de la recta 2 tiene que ser una combinación lineal de los vectores posición y dirección de la recta 1.(Ej. c´= a + ½b = (12,5; 23,5; 6))
	Y el respectivo vector dirección de la recta 2 debe ser una combinación lineal del vector dirección de la recta 1. (Ej. d´= 2b = (10, 14, 4))
Se resuelve el siguiente sistema;
i) 10 +5λ = 12,5 + 10µ
ii) 20 + 7λ = 23,5 + 14µ 
iii) 5 + 2λ = 6 + 4µ
Siendo la solución λ = 0,5 y µ=2λ, lo que se puede ver gráficamente así:
e) El valor de λ es 6, lo que se obtiene al resolver el siguiente sistema;
i) 10 +5λ = 40
ii) 20 + 7λ = 62
iii) 5 + 2λ = 17
	Para obtener el valor de µ y los componentes del vector d (x, y, z), se resuelve el siguiente sistema;
iv) 40 = 15 + a
v) 62 = 40 + b
vi) 15 = 20 + c
	En que a = 25, b = 22, c = -5. Donde se supone que a = µ* x, b = µ* y, c =µ*z, ya que no se podría resolver un sistema de cuatro variables, con tres ecuaciones.
f) Para que las rectas se intercepten en forma perpendicular, el producto punto de los vectores dirección de ambas rectas debe ser igual a cero, y mover el vector dirección o posición de una de las rectas para que se puedan intercectar.
Resolviendo,
	(5, 7, x) • (10, 1, 9) = 0
	x = -57/9
Se reemplaza a en el siguiente sistema, en se mueve el vector posición de la segunda recta;
i) 10+5λ = 15 + 10µ
ii) 20 + 7λ = 40 + µ 
iii) 5 – 57/9λ = 20z + 9µ 
Obteniéndose λ = 3, µ =1, z = -1,15.
Ejercicio 2 - Análisis Envolvente de Datos (DEA)
a) Si evaluando un cierto punto a resulta que b es uno de sus benchmarks, entonces b está en la frontera de eficiencia de todo el problema. La demostración es por contradicción: supongamos que b es benchmark de a pero b es dominado colectivamente por c y d. Si b es dominado entonces su ø es estrictamente mayor que 1. Entonces, la suposición anterior no puede ser correcta porque b no habría sido un benchmark de a, ya que el programa lineal que evalúa al punto a habría reemplazado b por una combinación convexa de c y d. De haberse hecho tal reemplazo, la nueva frontera estaría por encima de b y por ende el programa que evalúa al punto a obtendría una frontera más lejana con un ø de a mayor. Dado que el programa lineal maximiza el ø de a, siempre encuentra la mejor combinación de puntos benchmark, así es que no puede ser que c y d dominen a b. Al no existir ningún par c y d que dominan a b, concluimos que b es eficiente. 
b) Si d no aparece como benchmark no necesariamente significa que no es eficiente. Podría ser que d es co-lineal con a y b. Entonces, el DEA de c podría elegir a a y d no obstante podría haber elegido a b.
c) Sólo sabemos en cuál punto intercepta la frontera de factibilidad si la desigualdad se da en estricta igualdad en el óptimo. En tal caso, la intercepción es .
d) El problema queda no determinado porque ø se hace infinito.
e) Depende si a es eficiente o no. Si está en la frontera, no hay efecto al relajar i 0, ya que de todos los vectores sería igual a 0 y no tomará valores negativos. Si no está en la frontera, la evaluación podría empeorar, porque se hacen factibles combinaciones que dominan con un  mayor, es decir, estaría fuera de la frontera y la combinación convexa sería , con 
Ejercicio 3 – Precios Sombra – KKT
Gráfico:
a) 
α=1,5 y β=1,5 donde α=precio sombra de i) y β=precio sombra de ii)
b) 
Como no hay restricciones activas igual a cero, el óptimo es un punto lo que es de dimensión 0.
 (
h
2
n
o
)
c) 
Los precios sombra no cambian si se restringe o se relaja la restricción. Si se restringe entonces la función objetivo disminuye en 1,5. Si se relaja la restricción, la función objetivo aumenta en 1,5. 
d) 
Si aumenta la utilidad de x entonces la pendiente de la función objetivo es mayor con lo que el vector normal al plano optimizador se proyecta más en el vector normal de la restricción de i)
e) 
α = 2,5 y β = 0,5 donde α = precio sombra de i) y β = precio sombra de ii).
f) 
α = 3 y β = 0 donde α = precio sombra de i) y β = precio sombra de ii).
g) 
Como hay una restricción activa igual a 0, el óptimo es una línea y por tanto su dimensión es 1. 
h) 
En este caso el vector normal del plano optimizador es (6,16) y los precios sombra, si lo consideramos en el punto (1, 3/2), son a = -1 y b = 9 con lo que no cumple la condición de KKT y por lo tanto no es óptimo aquél punto. Viendo el gráfico, el punto óptimo está determinado por la restricción ii) y la no negatividad de x. En este punto los precios sombra son b=8 y c = 2 donde c = precio sombra de restr. No negatividad de X y b = precio sombra de restricción ii).
	
Ejercicio 4 – Programa Dual
a) El problema dual es:
b) Modificando las restricciones del problema en (i), se tiene:
que es equivalente a:
Como I es estrictamente positivo, el problema minimiza el valor de , luego:
Como y son estrictamente positivos, se tiene:
c) El valor de representa la relación Beneficio/Costo del bien . De este modo está asociada al bien con mejor relación Beneficio/Costo y su valor representa esta relación, para este mismo bien.
d) La expresión determinará cuál de las relaciones Beneficio/Costo es la mejor, lo que indicará cual de las restricciones del problema dual será activa y por lo tanto, cuál de las variables primales tendrá un valor positivo. Claramente, por el valor que tienen los parámetros, la restricción presupuestaria siempre será activa. Tomando esto en cuenta, si queremos que la solución óptima sea un vértice, la otra variable tendrá que tener un valor nulo, de modo de tener 2 restricciones activas (el problema tiene dimensión 2). Así, en la siguiente restricción:
la variable con mayor relación beneficio/costo tendrá valor positivo y la otra variable tendrá valor nulo. Despejando se tiene que la variable con mayor relación beneficio costo tendrá valor:
(La otra variable tendrá valor nulo).
(1, 3/2)
(3/2, 3/4)
y
x
1
2
ii
i
iii
h
2
h
1
n
o
h
2
n
o
h
1
h
2
(1, 3/2)
n
o
h
2
h
1
h
x
abcdfae