Tarea 1

Esta es una vista previa del archivo. Inicie sesión para ver el archivo original

EAE 211 B 2º semestre 2019
Profesor Felipe Zurita
Ayudantes Begoña Bilbao Felipe del Canto
Viviana Díaz Rodrigo Icarán
Lucía Langlois Vedran Razmilic
Tarea Nº1
Repaso
Respuestas
Pregunta 1.– KKT1
Resuelva, por el método de KKT, el siguiente problema:
máx
x1,x2,x3,x4
2 ln(x1) + 2 ln(x2)
sujeto a x3x4 = k
x1 + x3 ≤ 100
x2 + x4 ≤ 200
x ≥ 0
donde k ∈ R+. En su respuesta, considere lo siguiente:
Ilustre en un gráfico el conjunto factible.
En el siguiente gráfico, x1 y x3 se miden como distancia vertical respecto de cada 0 respectivo
(x1 hacia arriba, x3 hacia abajo), mientras que x2 y x4 horizontalmente (x2 hacia la derecha,
y x4 hacia la izquierda).
200
100
O1,2
O2,3
x1
x2
x3
x4
x satisface las últimas 3 desigualdades mientras los puntos se mantengan dentro de la caja
y el rojo se mantenga por debajo y a la izquierda del azul.
La curva amarilla ilustra el conjunto factible en el caso en que k = 10.000. Observe que
si k fuera mayor que 20.000 (100 × 200), el conjunto factible sería vacío (la curva amarilla
se saldría de la caja). En los extremos de lo posible, entonces, k = 0 (y x3 = x4 = 0), ó
k = 20.000 (y x1 = x2 = 0).
Especifique cómo tratará las condiciones de no negatividad.
Hoja 1 de 4
Por un lado, se puede expresar el problema con las restricciones expresamente en el lagran-
geano de esta manera:
L = 2 ln(x1) + 2 ln(x2) + λ(k − x3x4) + δ1(100− x1 − x3) + δ2(200− x2 − x4)+
γ1x1 + γ2x2 + γ3x3 + γ4x4,
de donde se debe sacar las CPO para las cuatro variables y todos los multiplicadores. De ma-
nera alternativa, se pueden incorporar las restricciones de no negatividad como condiciones
de holgura complementaria para las CPO de x, de la siguiente manera:
L = 2 ln(x1) + 2 ln(x2) + λ(x3x4 − k) + δ1(100− x1 − x3) + δ2(200− x2 − x4)
con CPO:
∂L
∂x1
=
2
x1
− δ1 ≤ 0 c.h.c.
∂L
∂x1
x1 = 0 (1)
∂L
∂x2
=
2
x2
− δ2 ≤ 0 c.h.c.
∂L
∂x2
x2 = 0 (2)
∂L
∂x3
= λx4 − δ1 ≤ 0 c.h.c.
∂L
∂x3
x3 = 0 (3)
∂L
∂x4
= λx3 − δ2 ≤ 0 c.h.c.
∂L
∂x4
x4 = 0 (4)
∂L
∂λ
= x3x4 − k = 0 (5)
∂L
∂δ1
= 100− x1 − x3 ≥ 0 c.h.c.
∂L
∂δ1
δ1 = 0 (6)
∂L
∂δ2
= 200− x2 − x4 ≥ 0 c.h.c.
∂L
∂δ2
δ2 = 0 (7)
Considere todos los casos posibles, y explique por qué descarta o no alguno a priori.
Los 27 = 128 casos se construyen a partir de las combinaciones de “positivo” (+) y cero
para los multiplicadores:
λ, δ1, δ2, γ1, γ2, γ3, γ4 ∈ {0,+}
Pero:
• En primer lugar, como hay cuatro variables “a elegir” (n = 4) basta con revisar las
soluciones en que máximo cuatro restricciones estén activas (m ≤ 4). Se descartan,
entonces los 29 casos en que más de cuatro restricciones están activas.
• También se pueden descartar aquellas soluciones que tengan a x3 = 0 (γ3 > 0) ó
x4 = 0 (γ4 = 0) ya que no se cumpliría la primera restricción, porque k pertenece a
los reales positivos. Esto permite descartar 68 casos adicionales.
• También podemos descartar los casos en que x1 = 0 (γ1 > 0) ó x2 = 0 (γ2 > 0) porque
sabemos que el logaritmo de x cuando x tiende a 0 es −∞, fácilmente superado, por
ejemplo, por x1 = x2 = 1. Esto permite descartar 23 casos adicionales.
• Finalmente, como tanto la función a maximizar como la primera restricción son cuasi-
cóncavas (es decir, sus curvas de nivel son convexas), se pueden descartar escenarios en
que las restricciones de recursos no se cumplan con igualdad. Esto permite descartar
6 casos adicionales.
En total descartamos 126 casos. Los que quedan son:
λ δ1 δ2 γ1 γ2 γ3 γ4
1 + + + 0 0 0 0
2 0 + + 0 0 0 0
Hoja 2 de 4
Solución interior: x>0 y ∂L
∂δi
= 0:
A partir de (1) y (2) obtenemos que δ1
δ2
=
x2
x1
. Luego de (3) y (4) obtenemos que δ1
δ2
=
x4
x3
,
por lo tanto, x2
x1
=
x4
x3
.
Luego, sabemos que 100 = x1+x3 y 200 = x2+x4, por lo que la expresión anterior se puede
escribir como: x2
x1
=
200− x2
100− x1
. Reordenando llegamos a que: x2 = 2x1.
En cuanto a x3 y x4, sabemos que a la vez deben cumplir (5). Así, se reescribe (5), usando
(6) y (7), k = (100− x1)(200− x2) = (100− x1)(200− 2x1).
Finalmente, k = 2(100− x1)2 y despejando, x1 = 100−
√
k
2
. Luego, x2 = 200−
√
2k, x3 =√
k
2
y x4 =
√
2k. Se verifica que k = 0 =⇒ x3 = x4 = 0, y k = 20.000 =⇒ x1 = x2 = 0
Para los multiplicadores:
δ1 =
2
100−
√
k
2
δ2 =
2
200−
√
2k
λ =
δ1
x4
=
2
√
2k(100−
√
k
2 )
=
2
100
√
2k − k
Finalmente, para que se cumplan los supuestos iniciales necesitamos que:
δ1 =
2
100−
√
k
2
> 0, lo que se cumple para 0 < k < 20.000.
δ2 =
2
200−
√
2k
> 0, lo que también se cumple para 0 < k < 20.000
λ =
2
100
√
2k − k
> 0, lo que también se cumple para todo 0 < k < 20.000. Esto último
implica que el caso 2 es imposible, lo que concluye el análisis de las CPO.
Especifique las condiciones de segundo orden cuando corresponda, o explique por qué no
existen si fuera el caso.
Ahora sabemos que hay 3 de las 7 restricciones activas y son 4 variables a elegir, por lo que
debemos revisar 4-3=1 sub-determinantes del hessiano orlado, es decir, el determinante del
hessiano orlado completo. Para ver el signo: (−1)(1+m) = (−1)(1+3) = 1 > 0, es decir, el
hessiano debe ser positivo.∣∣∣∣∣∣∣∣∣∣∣∣∣∣
0 0 0 0 0 x4 x3
0 0 0 1 0 1 0
0 0 0 0 1 0 1
0 1 0 −2
x21
0 0 0
0 0 1 0 −2
x22
0 0
x4 1 0 0 0 0 λ
x3 0 1 0 0 λ 0
∣∣∣∣∣∣∣∣∣∣∣∣∣∣
=
400
√
2k
(
√
k − 100
√
2)2
,
lo que es estrictamente positivo para cualquier k ∈ (0, 20.0000). Así concluimos que estamos
en un máximo.
Interprete los multiplicadores de Lagrange.
Los multiplicadores de Lagrange son un precio sombra, es decir, representan el aporte de
una unidad extra del recurso restringido a la función objetivo.
Encuentre la función de valor.
Hoja 3 de 4
L∗(k) = 2 ln(100−
√
k
2
) + 2 ln(200−
√
2k)
Pregunta 2.– KKT2
Resuelva, bajo las mismas condiciones anteriores, el siguiente problema:
máx
x1,x2,x3,x4
(x1 − 50)2 + (x2 − 25)2
sujeto a x3x4 ≥ k
x1 + x3 ≤ 100
x2 + x4 ≤ 200
x ≥ 0
donde k ∈ R+. Explique las diferencias entre ambos problemas.
Resolvemos de manera análoga:
L = (x1 − 50)2 + (x2 − 25)2 + λ(x3x4 − k) + δ1(100− x1 − x3) + δ2(200− x2 − x4)
con CPO:
∂L
∂x1
= 2(x1 − 50)− δ1 ≤ 0 c.h.c.
∂L
∂x1
x1 = 0 (8)
∂L
∂x2
= 2(x2 − 25)− δ2 ≤ 0 c.h.c.
∂L
∂x2
x2 = 0 (9)
∂L
∂x3
= λx4 − δ1 ≤ 0 c.h.c.
∂L
∂x3
x3 = 0 (10)
∂L
∂x4
= λx3 − δ2 ≤ 0 c.h.c.
∂L
∂x4
x4 = 0 (11)
∂L
∂λ
= x3x4 − k ≥ 0 c.h.c.
∂L
∂λ
λ = 0 (12)
∂L
∂δ1
= 100− x1 − x3 ≥ 0 c.h.c.
∂L
∂δ1
δ1 = 0 (13)
∂L
∂δ2
= 200− x2 − x4 ≥ 0 c.h.c.
∂L
∂δ2
δ2 = 0 (14)
Se pueden descartar casos otra vez de restricciones de recursos y de x3 y x4 igual a 0.
También, se puede demostrar que la solución interior no es un máximo.
Solución esquina: x1 = 0, x3 = 100, x2, x4 > 0 : x4 = k100 y x2 = 200 −
k
100 y su función valor
sería 502 + (175− k100 )2
Otra solución esquina: x2 = 0, x4 = 200, x1, x3 > 0: x3 = k200 , x1 = 100−
k
200 . Es demostrable
que este no es un óptimo.
Otra solución esquina es x1 = x2 = 0, x3 = 100, x4 = 200 y su función valor sería 502+252 = 3.125
Como hay cuatro restricciones activas (las dos de recursos y dos de no negatividad) no es necesario
sacar CSO.
Así, dependiendo del valor de k, el óptimo puede ser una o la otra. Si 502+(175− k100 )2 > 3.125,
entonces es la primera solución, es decir, si k es menor a 15.000. Y con la condición de que
k < 20.000
Hoja 4 de 4