TEMA 3. OPTIMIZACIÓN CON RESTRICCIONES DE...
Transcript of TEMA 3. OPTIMIZACIÓN CON RESTRICCIONES DE...
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
1/12
TEMA 3. OPTIMIZACIÓN CON RESTRICCIONES DE DESIGUALDAD:
CONDICIONES DE KUHN – TUCKER
Observemos que minimizar f(x) equivale a maximizar f(x), luego si se tratase de
minimizar f(x), la lagrangiana sería
L(x) = f(x) +
m
1j
jjjc)x(g
y la primera condición de Kuhn-Tucker:
0x
g
x
f m
1j i
j
j
i
, (i=1, 2, ..., n)
o, cambiando el signo:
0x
g
x
f m
1j i
j
j
i
, (i=1, 2, ..., n)
Lo que equivale a escribir la lagrangiana:
L(x) = f(x)
m
1j
jjjc)x(g
Observemos también que si alguna condición está escrita en la forma g(x) ≥ c, la
escribiremos multiplicando por 1: g(x) ≤ c.
Para que las condiciones de Kuhn-Tucker sean necesarias debe cumplirse cierta
cualificación de las restricciones para lo cual es suficiente que los puntos de la región factible
sean regulares. Un punto es regular si en él no se satura ninguna restricción (la restricción se
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
2/12
convierte en igualdad para ese punto) o, en caso contrario, los gradientes de las restricciones
saturadas son linealmente independientes.
Por ejemplo, supongamos que las restricciones son x2 + y
2 ≤ 1; x ≥ 0.
- Si un punto (x, y) satura solamente la 1ª restricción, el gradiente y2,x2 es
independiente, pues es distinto de 0,0 .
- Si un punto (x, y) satura solamente la 2ª restricción, el gradiente 0,1 es
independiente, pues es distinto de 0,0 .
- Si un punto (x, y) satura las dos restricciones es (0, 1) ó (0, –1) y los gradientes
2,0 y 0,1 son independientes.
Supondremos en lo que sigue que se cumple la hipótesis de cualificación de las
restricciones por lo que las condiciones de Kuhn-Tucker serán necesarias para la existencia de
óptimo.
Teorema de los valores extremos.-
Si f es una función continua sobre un conjunto S compacto (cerrado y acotado) de
n, existe al menos un mínimo d y un máximo c en S, es decir f(d) ≤ f(x) ≤ f(c), xS
Condiciones de no negatividad para las variables.- En muchos problemas de optimización con restricciones de desigualdad, dos de las
restricciones son x ≥ 0 e y ≥ 0 (que podemos escribir x ≤ 0, y ≤ 0). En ese caso, para no
manejar muchos multiplicadores de Lagrange, puede procederse de la siguiente forma.
Supongamos el problema:
Maximizar f(x,y), s.a g(x,y) ≤ c, x ≤0, y ≤ 0.
La lagrangiana: L(x,y) = f(x,y) + 1(g(x,y)c) 2x 3y
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
3/12
Las condiciones de Kuhn-Tucker:
x
g
x
f1
2 = 0
x
g
x
f1
= 2
y
g
y
f1
3 = 0
y
g
y
f1
= 3
1(g(x,y)c) = 0 1(g(x,y)c) = 0
2x = 0 2x = 0
3y = 0 3y = 0
g(x,y) ≤ c g(x,y) ≤ c
x ≥ 0 x ≥ 0
y ≥ 0 y ≥ 0
i ≤ 0 i ≤ 0
Observamos que si x > 0 2 = 0, luego las condiciones x
g
x
f1
= 2 , 2x = 0 y
2 ≤ 0 se pueden sustituir por x
g
x
f1
≤ 0 (= 0 si x > 0). Análogamente las condiciones
y
g
y
f1
= 3 , 3y=0 y 3 ≤ 0 se pueden sustituir por
y
g
y
f1
≤ 0 (= 0 si y > 0). Por
tanto, las condiciones de Kuhn-Tucker quedarían:
x
g
x
f1
≤ 0 (= 0 si x > 0)
y
g
y
f1
≤ 0 (= 0 si y > 0)
1(g(x,y)c) = 0; 1 ≤ 0; x ≥ 0; y ≥ 0
EJERCICIOS.-
Solución.- Las condiciones necesarias de Kuhn-Tucker serían:
01yx
0y
0y2y2
0x21
22
2
1
21
2
cuya única solución con i 0 es: x = 1, y = 0, 1 = 0 , 2 = 2
1 .
La región factible es convexa (se trata de un semicírculo) y la función objetivo es
cóncava (el hessiano es
20
00 cuya forma cuadrática asociada es semidefinida negativa),
luego el punto (1, 0) es máximo global.
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
4/12
Solución.- Como se cumple la condición de no negatividad de las variables, la lagrangiana:
L(x,y) = 2y – x2 + (x
2 + y
2 – 1). Las condiciones de Kuhn-Tucker:
–2x + 2x ≤ 0 (= 0 si x > 0)
2 + 2y ≤ 0 (= 0 si y > 0)
(x2 + y
2 – 1) = 0
x2 + y
2 ≤ 1
≤ 0, x ≥ 0, y ≥ 0
Así pues, el único punto de Kuhn-Tucker es (0, 1), con = –1
Como queremos maximizar una función continua sobre un conjunto cerrado y acotado,
por el teorema de los valores extremos, sabemos hay solución al problema. Luego el punto
(0, 1) maximiza 2y – x2, siendo 2 el valor máximo.
Solución.-
La función lagrangiana;
(x, y) = 1 x + y2 (x
2 + y
2 1)
Las condiciones necesarias de Kuhn-Tucker
01yx
0
01yx
0y2y2
0x21
22
22
Imposible011y
11y0x
Imposible10x
0Si
Imposible,020Si
Caso que = 0. Imposible porque la 1ª ecuación quedaría 1 = 0.
Caso que < 0
imposible10y
imposible2
11x
punto2
11x
0y
01,
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
5/12
Como se trata de minimizar una función continua sobre un conjunto cerrado y acotado,
el teorema de los valores extremos garantiza solución al problema luego el punto (1, 0),
minimiza 1–x+y2.
Solución.-
La función lagrangiana:
(x, y) = e–x
+ e–y
+ (x + y – 4)
Las condiciones necesarias de Kuhn-Tucker:
–e–x
+ = 0
–e–y
+ = 0
(x + y – 4) = 0
x + y – 4 ≤ 0
x + y = 4
x = y = 2 = e–2
e–x
= e–y
x = y
Como > 0, el punto hallado cumple la condición necesaria para mínimo.
Puesto que e–x
+ e–y
es convexa y el conjunto factible es convexo, la solución (2, 2) es un
mínimo global del problema propuesto.
Solución.-
El lagrangiano:
(x, y) = –(x–2)2– (y – 3)
2+ 1(x– 1) + 2(y–2)
Las condiciones necesarias de Kuhn-Tucker:
No puede ser = 0, porque e–x
> 0, luego:
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
6/12
–2(x–2) + 1 = 0
–2(y–3) + 2 = 0
1(x – 1) = 0
2(y–2) = 0
1 ≤ 0; 2 ≤ 0
x – 1 ≤ 0
y – 2 ≤ 0
La función objetivo es cóncava pues la forma cuadrática asociada a su hessiano
20
02 es definida negativa. Como la región factible es convexa, el punto (1, 2) es
máximo global para la función objetivo).
Solución.-
El lagrangiano del problema es:
(x, y) = y – x2 + 1(x
2 + y
2 – 1) + 2(–x)
Las condiciones necesarias de Kuhn-Tucker:
–2x + 21x – 2 = 0
1 + 21y = 0
1(x2 + y
2 – 1) = 0
2(–x) = 0
1 ≤ 0; 2 ≤ 0
x2 + y
2 ≤ 1
x ≥ 0
Así pues solamente un punto, el (0, 1) cumple las condiciones necesarias de Kuhn-Tucker.
Puesto que la región factible es cerrada y acotada (es un semicírculo), el punto (0, 1) es la
solución del problema. Se trata de un máximo global.
1 = 0 imposible pues se deduciría que x = 2, que contradice la 1ª
restricción.
1 < 0 x = 1 1 = –2
22y0
nrestricció 2ª la contra 3,y
que deduciría se pues imposible0
22
2
Así pues, el único punto que verifica las condiciones necesarias es
(1, 2).
Debe ser 1 < 0 porque si 1 = 0, la segunda igualdad es
imposible.
Luego x2 + y
2 = 1
Si 2 = 0, de la 1ª igualdad x(–1+1) = 0 x = 0
imposible 2
11y
1,0 punto 2
11y
1
1
Si 2 < 0 x = 0 lo cual contradice la 1ª igualdad pues se
obtendría 2 = 0.
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
7/12
Solución.-
La lagrangiana:
(x, y) = f(x, y) + 1g1(x, y) + 2g2(x, y) = x2 + y + 1(x
2 + y
2 1) + 2(x y)
Las condiciones necesarias de Kuhn-Tucker:
0yx
01yx
0,0
0yx
01yx
0y21
0x2x2
22
21
2
22
1
21
21
Caso que 1 = 2 = 0. Imposible porque la 2ª ecuación quedaría 1 = 0.
Caso que 1 = 0 y 2 < 0. Imposible porque se obtiene que 2 = 1.
Caso que 1<0 y 2 = 0. El sistema queda:
0yx
1yx
0y21
01x
22
1
1
que tiene dos soluciones: {x = 0, y = 1, 2
11
} y {2
3x ,
2
1y ; = 1}.
Caso que 1<0 y 2 < 0. El sistema queda:
yx
1yx
0y21
0x2x2
22
21
21
que proporciona las soluciones
2
1
2
1,
22
1
2
1,
2
1y,
2
1x
21 y
2
1
2
1,
22
1
2
1,
2
1y,
2
1x
21 pero ninguna es válida porque en ambas
2> 0.
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
8/12
Así pues, los puntos que verifican las condiciones necesarias son (0, 1) y
2
1,
2
3
Solución.-
Solución trivial pues en el recinto dado, el valor máximo de
xy2 es cero, en el punto (0,0).
Veámoslo formalmente:
Como se cumple la condición de no negatividad de las variables, la
lagrangiana:
(x, y) = x y2 + (2x + y
2 – 4)
Las condiciones necesarias de Kuhn-Tucker:
1 2 ≤ 0 (= 0 si x > 0)
2y + 2y≤ 0 (= 0 si y > 0)
(2x + y2 – 4) = 0
2x + y2 ≤ 4
≤ 0 ; x ≥ 0, y ≥ 0
Luego solamente el punto (0, 0) es de Kuhn-Tucker
La función x y2 es cóncava por que la forma cuadrática asociada a su hessiano
20
00 es semidefinida negativa. Además la región factible es convexa por ser intersección
de conjuntos convexos. Luego el punto obtenido (0, 0) es el máximo global de x y2.
Solución.-
Como se cumple la condición de no negatividad de las variables, la lagrangiana:
(x, y) = x2 + y
2 + (x + y–1)
Las condiciones necesarias de Kuhn-Tucker:
2x + ≤ 0 (=0 si x > 0)
2y + ≤ 0 (=0 si y > 0)
(x + y –1) = 0
x + y ≤ 1
≤0, x ≥ 0, y ≥ 0.
00xLuego
imposible2x2
10210xSi
0x;0
04x2
0) xsi 0(021
0y Luego
imposible 10y Si
Si = 0 x = y = 0
Sea entonces < 0.
Si x > 0 e y > 0 = −1, y = 2
1, x =
2
1
Si x > 0 e y = 0 x = 1, = −2
Si x = 0 y = 1, = −2
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
9/12
Tenemos pues cuatro puntos de Kuhn-Tucker: (0, 0);
2
1,
2
1, (1, 0) y (0, 1).
Sustituyendo en la función objetivo comprobamos que los puntos que la maximizan son (1, 0)
y (0, 1).
(Puede comprobarse que la resolución gráfica es bastante sencilla)
Solución.-
El lagrangiano: (x, y) = x + y + 1(y – 4) + 2 (x2 − y)
Las condiciones necesarias de Kuhn-Tucker:
1 + 22x = 0
1 + 1 − 2 = 0
1(y – 4) = 0
2(x2 − y) = 0
1≤0, 2≤0
y ≤ 4, y ≥ x2
sistema que resuelto proporciona una única solución: x = 2,
y = 4, 1 = 4
1 , 2 =
4
5
Como el conjunto factible es convexo y la función objetivo es cóncava, podemos aplicar
la condición suficiente de óptimo global, luego el punto (2, 4) es la solución.
Solución.- Lo resolveremos en primer lugar
gráficamente. La región factible está limitada
por la circunferencia x2 + y
2 = 1 y la parábola
x = y2. La pendiente de la función objetivo es
2 y, según observamos en la figura, 2x + y
se maximizará en un punto de la
semicircunferencia positiva 2x1y de
pendiente 2. Así pues, derivando
y’ = 2x1
x
= 2 x =
5
2 y =
5
1
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
10/12
Es decir, 2x + y se maximiza en el punto
5
1,
5
2 y su valor en ese punto es igual a 5
Ahora lo resolveremos formalmante.
El lagrangiano: (x, y) = 2x + y + 1(x2 + y
2 1) + 2(y
2 x)
Las condiciones necesarias de Kuhn-Tucker:
2 + 21x 2 = 0
1 + 21y + 22y = 0
1(x2 + y
2 1) = 0
2(y2 x) = 0
x2 + y
2 ≤ 1; y
2 x ≤ 0; 1 ≤ 0; 2 ≤ 0
Solución.-
El problema equivale a maximizar –x –y s.a. x2 – y ≤ 0
El lagrangiano: (x, y) = −x − y + (x2 − y)
Las condiciones necesarias de Kuhn-Tucker:
−1+ 2x = 0
−1 – = 0
(x2 − y) = 0
sistema cuya solución es 4
1y,
2
1x , = −1.
La función objetivo es cóncava y convexa por tratarse de una función lineal. Además la región
factible es convexa (es la parte interior de la parábola y = x2), luego el punto
4
1,
2
1es
mínimo global y por tanto el valor mínimo de x + y sería 4
1
4
1
2
1
Solución.-
Escribiremos el problema en la forma canónica:
Maximizar x2 y
2
sujeto a: x + y ≤ 1
x ≤ 1
El lagrangiano: (x, y) = x2 y
2 + 1(x + y – 1) + 2 (1 − x)
Las condiciones necesarias de Kuhn-Tucker:
Resuelto el sistema se obtiene una única solución
0;2
5,
5
1y,
5
2x
21. Así pues el
máximo valor de
2x + y en la región factible sería 55
5
5
1
5
4 .
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
11/12
2x + 1 2 = 0
2y + 1 = 0
1(x + y – 1) = 0
2 (1 − x) = 0
1≤0, 2≤0
x + y ≤ 1, x ≥ 1
sistema que resuelto proporciona una única solución: x = 1, y = 0, 1 = 0, 2 = 2
La función x2 + y
2 es convexa por que la forma cuadrática asociada a su hessiano
20
02 es definida positiva. Además la región factible es convexa. Luego el punto obtenido
(1, 0) es el mínimo global de x2 + y
2.
Solución.-
El ejercicio es trivial pues (x1)2 + y
2 ≥ 0, luego el valor mínimo es 0 y ello implica que
x= 1; y = 0. Hagámoslo formalmente:
Escribiremos el problema en la forma canónica:
Maximizar (x1)2 y
2
sujeto a: x2 y
2 ≤ 4
x + y ≤ 1
El lagrangiano: (x, y) = (x1)2 y
2 + 1(x
2 y
2 4) + 2 (1 – x + y)
Las condiciones necesarias de Kuhn-Tucker:
2(x1) + 21x 2 = 0
2y 21 + 2= 0
1(x2 y
2 4) = 0
2 (1 – x + y)= 0
1≤0, 2≤0
x2 y
2 ≤ 4, x y ≥ 1
sistema que resuelto proporciona una única solución: x = 1, y = 0, 1 = 0, 2 = 0
UNED. ELCHE. e-mail: [email protected]
TUTORÍA DE MATEMÁTICAS AVANZADAS PARA LA ECONOMÍA https://www.innova.uned.es/webpages/Ilde/Web/index.htm
12/12
Solución.-
Veamos primeramente una solución gráfica.
Para k ≥ 0, las curvas 2x2 + y
2 = k 1
k
y
2k
x 22
constituyen una familia de elipses, de semiejes 2
k y k ,
que obviamente aumentan al aumentar k. La región factible
es el triángulo de vértices (0,0), (0, 110) y
0,
3
110.Se
observa en la gráfica que el valor máximo de k se obtiene
en el punto (0, 110), para el que se obtiene un valor de k =
12100.
Resolvámoslo aplicando las condiciones de Kuhn-Tucker: el planteamiento sería:
Maximizar 2x2 + y
2
s.a. 3x + y ≤ 110
x ≥ 0; y ≥ 0
Como se cumple la condición de no negatividad de las variables, la lagrangiana:
(x,y) = 2x2 + y
2 + (3x + y 110)
Y las condiciones de Kuhn-Tucker:
0y,0x,0
0110yx3
0 y si 00y2
0 x si 003x4
El conjunto factible es convexo pero la función objetivo no es cóncava de modo que no
podemos aplicar la condición suficiente de óptimo global, pero al ser la función objetivo
continua y el conjunto factible compacto, por el teorema de los valores extremos sabemos que
existe al menos un óptimo global. Comprobamos sustituyendo en la función objetivo que el
valor máximo lo proporciona el punto (0, 110).
Solución.-
El ejercicio resulta trivial. En efecto, la expresión –x2 – (y−2)
2 resulta ser ≤ 0 para
cualquier punto (x,y). Su máximo valor pues es el cero que lo toma únicamente en el punto
(0, 2) que pertenece a la región factible.
9
440,
3
110x0y
40,20y,30x0y
0x
220,110y0x
0Si
0y,0x0Si