Solucions Seminari 3 (2017)

Ejercicio Catalán
Universidad Universidad Pompeu Fabra (UPF)
Grado Administración y Dirección de Empresas - 1º curso
Asignatura Matemáticas III
Año del apunte 2017
Páginas 12
Fecha de subida 18/06/2017
Descargas 0
Subido por

Vista previa del texto

tMatemàtiques Curs 2014-2015 III Seminari 3. Optimització amb restriccions en diverses Variables: mètode de Kuhn-Tucker Problema 1: Estudieu els màxims i mínims de la funció f ( x, y, z ) = x 2 + y 2 + z 2 sotmesa a les restriccions x2 + y2 = 6 + z i x − y + 3 = 0 Solució Problema 1: La funció pren el valor mínim en els punts −3 1 3 1 1 −3 1 3 1 1 − , − ,−  i  + , + ,−   2 2 2 2  2 2 2 2 2  2 I el valor mínim és 23/4.
Aquesta funció no té màxim global.
Problema 2: Useu el mètode de Kuhn-Tucker per trobar (si existeixen) els màxims i els mínims de les funcions següents. Raoneu per què els punts trobats són màxims/mínims.
Si no hi ha màxim o mínim, indiqueu per què.
2.1. f ( x, y ) = x 2 + y 2 s.t 2x + y ≤ 2 2.2. f ( x, y ) = x 2 + y 2 , amb x 2 + xy + y 2 ≤ 3 Com varia els valors òptims de f en 1.2 si considerem la restricció x 2 + xy + y 2 ≤ 3.2 Solució Problema 2: 2.1. En primer lloc, és convenient dibuixar el conjunt on està avaluada la funció: y y = 2 − 2x x Observem que aquest conjunt és convex, tancat, però no afitat.
1 La funció Lagrangiana és L ( x, y ) = x 2 + y 2 − λ ( 2 x + y − 2 ) Escrivim les condicions a) i b) necessàries de Kuhn-Tucker:  L'1 ( x, y ) = 2 x − 2λ = 0   L ' 2 ( x, y ) = 2 y − λ = 0 λ (2 x + y − 2) = 0  Cas 1: Restricció inactiva: 2 x + y < 2 ; així λ = 0 . Aleshores hem de trobar els punts que verifiquen els sistema reduït:  L '1 ( x , y ) = 2 x = 0   L '2 ( x, y ) = 2 y = 0 2 x + y < 2  El punt (0,0) és la única solució de l’anterior sistema i satisfà la restricció. Llavors el punt (0,0) amb λ = 0 és un possible candidat a màxim/ mínim.
Cas 2. La restricció està activa. 2 x + y − 2 = 0 . Busquem les solucions tals que  L'1 ( x, y ) = 2 x − 2λ = 0   L ' 2 ( x, y ) = 2 y − λ = 0 2 x + y = 2  De la primera equació obtenim que λ = x i de la segona que λ = 2 y . Llavors x = 2 y i substituint aquesta relació a la tercera equació obtenim que y = 2 / 5 i per tant x = 4 / 5 .
Ara substituint el valor trobat de x o de y a les expressions de λ = x o λ = 2 y , respectivament, tenim que λ = 4 / 5 . Aleshores el punt (4 / 5,2 / 5) amb λ = 4 / 5 és un candidat a màxim.
Observem que no podem aplicar el Teorema dels valors extrems ja que S no és compacte.
Estudiem la Lagrangiana a cada punt candidat.
Pel punt (0,0) amb λ = 0 . Com a candidat, el punt tant pot ser max com min ( λ = 0 ).
La funció Lagrangiana és igual a L( x, y ) = x 2 + y 2 , que és clarament convexa com a suma de funcions convexes. Alternativament, la matriu seva Hessiana corresponent és  2 0   que és clarament definida positiva a tot el domini.. En aquest cas, doncs, el punt  0 2 (0,0) és mínim global a S..
2 Pel punt (4/5,2/5) amb λ = 4 / 5 , tenim que serà un candidat a màxim ( λ > 0 ). La funció 4 Lagrangiana és igual a L( x , y ) = x 2 + y 2 − (2 x + y − 2 ) . Torna a ser una funció 5 convexa en tot el seu domini al ser suma d’una convexa amb una lineal.
 2 0 Alternativament, si mirem la seva matriu Hessiana, torna a ser   , ja que las  0 2 4 segones derivades del terme − (2 x + y − 2 ) són zero. Aleshores L( x , y ) és convexa.
5 Però aquest punt era candidat a màxim. Llavors, Kuhn-Tucker Tucker no ens pot dir res sobre aquest punt. No obstant,, podem observar directament que la funció no té màxim sobre la restricció atès que pot prendre valors tan grans com vulguem prenent x → −∞ , y → −∞ . Això últim també es pot raonar dibuixant corbes de nivell: Així sabem que (0,0) és un mínim global i que no hi ha màxim.
2.2. La funció Lagrangiana agrangiana és L( x, y ) = x 2 + y 2 − λ ( x 2 + xy + y 2 − 3) Escrivim les condicions a) i b) necessàries de Kuhn-Tucker,, és a dir, que compleixen el sistema  2 x − λ (2 x + y ) = 0   2 y − λ ( x + 2 y) = 0 λ x 2 + xy + y 2 − 3 = 0  ( ) Cas 1. Restricció inactiva x 2 + xy + y 2 < 3 , λ = 0 . En aquest cas el sistema queda: 2x = 0 2 y = 0   λ =0  x 2 + xy + y 2 < 3 I obtenim el candidat (0,0) amb λ = 0 (possible candidat a màxim i a mínim).
Observem que aquest punt efectivament compleix la restricció: 02 + 0 ⋅ 0 + 02 = 0 ≤ 3 .
3 Cas 2. Restricció activa, x 2 + xy + y 2 = 3 ,. En aquest cas el sistema queda:  2 x − λ (2 x + y ) = 0  2 y − λ ( x + 2 y ) = 0  x 2 + xy + y 2 = 3  Aïllem λ : 2x 2x + y 2y λ= 2y + x (podem suposar que cap dels denominadors és igual a zero: efectivament, si 2x + y = 0, la primera equació del sistema implicaria x = 0, i això, juntament amb 2x + y = 0, implicaria que y = 0, però això és incompatible amb la tercera equació del sistema. De manera similar es pot veure que 2y + x no pot ser zero).
2x 2y D’aquí deduïm que = , és a dir, 2 x(2 y + x) = 2 y (2 x + y ) , és a dir 2x + y 2 y + x 4 xy + 2 x 2 = 4 xy + 2 y 2 , és a dir, x 2 = y 2 , és a dir, y = x, y = − x λ= En el cas y = x el sistema queda 2 x − 3λx = 0  2  3x = 3 és a dir,  x(2 − 3λ ) = 0  2  3x = 3 que té com solució x = 1, x = −1 amb λ = 2 / 3 pels dos valors de x. Tenim doncs els candidats (1,1), (-1,-1) amb λ = 2 / 3 , que són candidats a màxim ( λ > 0 ).
En el cas y = − x el sistema queda  2 x − λx = 0  − 2 x + λ x = 0  x2 = 3  que ( té com )( solucions x = ± 3 amb λ = 2 .
Per tant tenim els candidats ) 3 ,− 3 , − 3 , 3 amb λ = 2 . Aquests punts també són candidats a màxim ( λ > 0 ).
Ara estudiem si cada un dels candidats és realment màxim o mínim: Punt (0,0): amb λ = 0 la funció Lagrangiana és igual a L( x, y ) = x 2 + y 2 , que és convexa (mireu la solució del problema de l’apartat 3.1) i el punt és candidat a màxim o a mínim. Per tant, el punt (0,0) és mínim.
Punt (1,1): amb λ = 2 / 3 la funció Lagrangiana és igual a 4 2 2 (x + xy + y 2 − 3).
3 La presència de xy fa que no puguem raonar per simple inspecció. Hem de treballar amb la Hessiana.
 2 3 − 2 3 La matriu Hessiana corresponent és   . Els Menors Principals són −2 3 2 3  ∆1 : 2 / 3; 2 / 3 ≥ 0; ∆ 2 : 0 . La Hessiana és semidefinida positiva a tot el seu domini.
D’on es dedueix que L(x,y) és convexa. Però aquest punt era candidat a màxim. Per tant, Kuhn-Tucker no ens pot dir res sobre aquest punt.
L ( x, y ) = x 2 + y 2 − Punt (-1,-1): novament, amb λ = 2 / 3 la funció Lagrangiana és igual a 2 L( x, y ) = x 2 + y 2 − (x 2 + xy + y 2 − 3) 3 que és la mateixa d’abans. Novament Kuhn-Tucker no ens pot dir res sobre aquest punt.
Punt ( ) 3 ,− 3 : amb λ = 2 la funció Lagrangiana és igual a ( ) L( x, y ) = x 2 + y 2 − 2 x 2 + xy + y 2 − 3 .
 − 2 − 2  . Els Menors Principals són La matriu Hessiana corresponent és   − 2 − 2 ∆1 : − 2; − 2 ≤ 0; ∆ 2 : 0 . La Hessiana és semidefinida negativa a tot el seu domini.
d’on es dedueix que L(x,y) és còncava. Aquest punt era candidat a màxim. Podem afirmar que aquest punt és màxim.
( ) Punt − 3 , 3 : amb λ = 2 la funció Lagrangiana és igual a L( x, y ) = x 2 + y 2 − 2 x 2 + xy + y 2 − 3 .
Que és la mateixa d’abans. Novament, aquest punt és màxim.
( ) ( )( ) Hem pogut deduir que el punt (0,0) és mínim i que els punts 3 ,− 3 , − 3 , 3 són màxims. Què podem dir dels altres candidats (-1,-1) i (1,1)? Observem que f (0,0) = 0, f ( −1,−1) = f (1,1) = 2 , i que f ( ) ( ) 3 ,− 3 = f − 3 , 3 = 6 .
Per tant es dedueix que (− 1,1) i (1,1) no són màxims ni mínims globals.
Estudiem ara els canvis en els òptims provocats per un augment de 0.2 en la constant de la restricció. Sabem que l’augment del valor òptim ve donat aproximadament per l’expressió λ dc1 on dc1 = 0.2 . Així tenim que aquest augment, aproximadament, ve donat en el cas del mínim per: 0·0.2 = 0, és a dir, aproximadament aquests canvis no canvien el mínim. I en el cas dels màxims per: 2·0.2= 0.4. El nou màxim valdrà, aproximadament 6.4.
5 Problema 3: Estudieu els òptims de les funcions següents amb les restriccions indicades utilitzant el mètode de Kuhn-Tucker: 3.1. f ( x, y ) = x 2 + y + z , amb z 2 − y ≤ 0 3.2. f ( x, y ) = x 2 + x + y 2 , amb x + y ≥ 2, x ≥ 0 Determineu com varia el valor òptim en el punt mínim de f en 2.2 si canviem les restriccions a x + y ≥ 1.7, x ≥ 0.1 Solució Problema 3: 3.1. f ( x, y ) = x 2 + y + z , amb z 2 − y ≤ 0 Busquem primer els punts de els punts que compleixen les condicions necessàries de Kuhn-Tucker: L ( x, y , z ) = x 2 + y + z − λ z 2 − y ( )  ∂L  ∂x = 2 x = 0  ∂L  =1+ λ = 0  ∂y  ∂L  = 1 − 2λ z = 0  ∂z 2  λ z −y =0 ( ) Cas 1. Restricció inactiva, z 2 − y < 0 , λ = 0 . En aquest cas el sistema queda  ∂L  ∂x = 2 x = 0  ∂L  =1= 0 , que no té cap solució  ∂y  ∂L =1= 0   ∂z  λ =0 2 Cas 2. Restricció activa, z − y = 0 . En aquest cas el sistema queda  ∂L  ∂x = 2 x = 0 (1)  ∂L  = 1 + λ = 0 (2)  ∂y  ∂L  = 1 − 2λz = 0 (3)  ∂z 2  z − y = 0 ( 4) De (1) obtenim que x = 0, de (2) que λ = −1 , posant això en (3) obtenim que 1 + 2z = 0, és a dir, z = −1/2, i posant això en (4) obtenim que y = 1/4. Per tant, obtenim el candidat (0,1/4,−1/2) amb λ = −1 . Aquest punt és candidat a mínim ( λ < 0 ).
Hem vist que tenim l’únic candidat (0,1/4,−1/2). Amb λ = −1 la funció Lagrangiana queda L ( x, y , z ) = x 2 + y + z + ( z 2 − y ) = x 2 + z 2 + z , que és convexa. Alternativament, 6 2 0 0   la Hessiana és  0 0 0  . Els menors principals són: ∆1 : 2, 0, 2. ∆ 2 : 0, 0, 0. ∆ 3 : 0. Tots  0 0 2   són ≥0. La funció és semidefinida positiva a tot el seu domini. Observem que els valors propis són 2,0,2 (la diagonal de la matriu). Per tant aquest punt és un mínim. No hi ha màxim perquè no hi ha més candidats.
3.2. f ( x, y ) = x 2 + x + y 2 , amb x + y ≥ 2, x ≥ 0 Dibuixem la restricció: Busquem els candidats.. La Lagrangiana és L( x, y ) = x 2 + x + y 2 − λ1 (− x − y + 2 ) + λ2 x  ∂L  ∂x = 2 x + 1 + λ1 + λ2 = 0 (1)  ∂L  = 2 y + λ1 = 0 (2)  ∂y   λ1 (− x − y + 2 ) = 0 (3)  λ2 x = 0 (4) Cas 1: les dues restriccions inactives; inactives λ1 = 0, λ2 = 0 . En aquest cas el sistema queda  ∂L  ∂x = 2 x + 1 = 0 (1)  ∂L   ∂y = 2 y = 0 (2)  λ1 = 0 (3)   λ2 = 0 (4) (1) dóna com a solució x = −1/2, però això és incompatible amb la restricció segona, x ≥ 0 . Aquest cas no ens dóna cap candidat.
Cas 2: la primera restricció inactiva (λ1 = 0) i la segona activa ( x = 0) . En aquest cas el sistema queda  ∂L  ∂x = 1 + λ2 = 0 (1)  ∂L   ∂y = 2 y = 0 (2)  λ1 = 0 (3)   x = 0 ( 4) 7 Aquest sistema té com a solució el punt (0,0), que tampoc està a la restricció. No obtenim doncs cap candidat en aquest cas.
Cas 3: la primera restricció activa (− x − y + 2 = 0) i la segona inactiva (λ2 = 0) . En aquest cas el sistema queda  ∂L  ∂x = 2 x + 1 + λ1 = 0 (1)  ∂L   ∂y = 2 y + λ1 = 0 (2)   − x − y + 2 = 0 (3)  λ2 = 0 (4) (1) i (2) ens donen que 2 x + 1 = 2 y (5). Ara, (5) i (3) ens donen  2x + 1 = 2 y  − x − y + 2 = 0 Aquest sistema té com solució única el punt (3/4,5/4). De (2) obtenim que λ1 = −10 / 4 = −5 / 2. Aquest punt és doncs candidat a mínim.
Cas 4: la primera i la segona restriccions actives (− x − y + 2 = 0, x = 0) . En aquest cas el sistema queda:  ∂L  ∂x = 1 + λ1 + λ2 = 0 (1)  ∂L   ∂y = 2 y + λ1 = 0 (2)  − y + 2 = 0 (3)   x = 0 ( 4) De (3) obtenim que y=2. Ara, de (2) deduïm que λ1 = −4 . Finalment, de (1) obtenim que 1 − 4 + λ2 = 0, és a dir, λ2 = 3. Aquest punt no és candidat a màxim ni a mínim perquè els multiplicadors tenen signes diferents.
En resum, hi ha un únic candidat a mínim. La funció Lagrangiana amb λ1 = −5 / 2, λ2 = 0 5 3 5 , és L( x, y ) = x 2 + x + y 2 + (− x − y + 2 ) = x 2 + y 2 − x − y + 5 és convexa. Per tant, 2 2 2 hi ha un únic mínim global de 2.875 en (3/4,5/4) i no hi ha màxim.
8 Sabem m que l’augment del valor del mínim ve donat aproximadament per l’expressió λ1dc1 + λ2 dc2 on dc1 = −0.3, dc2 = 0.1 . Així tenim que aquest augment, aproximadament, ve donat per: (–5/2)·(–0.3) + 0·0.1 = 0.75, és a dir, el valor òptim del mínim és 2.875+0.75=3.625 Problema 4: Useu el mètode de Kuhn-Tucker Kuhn Tucker per trobar (si existeix) el màxim (només el màxim) de la funció següent. Raoneu per què el punt trobat és màxim. Si no hi ha màxim, indiqueu per què.
2 f (x, y ) = 2 + ( x − 1) 2 − e y , amb x 2 + y 2 ≤ 1 Solució Problema 4: La funció Lagrangiana és 2 L(x, y ) = 2 + ( x − 1) 2 − e y − λ ( x 2 + y 2 − 1) .
Escrivim les condicions a) i b) necessàries necessàrie de Kuhn-Tucker:  L'1 = 2( x − 1) − λ 2 x = 0  y2  L' 2 = −2 ye − λ 2 y = 0  λ x2 + y2 −1 = 0  ( ) Cas 1. Restricció inactiva, λ = 0 . En aquest cas, el sistema queda  2( x − 1) = 0  y2 − 2 ye = 0  λ =0  Aquest sistema té com a única solució el punt (1,0), amb λ = 0 . És candidat a màxim i a mínim.
9 Cas 2. Restricció activa, x 2 + y 2 = 1 . En aquest cas, el sistema queda  2( x − 1) − λ 2 x = 0  y2 − 2 ye − λ 2 y = 0  x2 + y 2 = 1  és a dir, 2( x − 1) − λ 2 x = 0  y2  − 2 y (e + λ ) = 0  x2 + y 2 = 1  2 De la segona equació deduïm que, o bé y = 0 o bé e y + λ = 0 .
En el cas y = 0 , la tercera equació d’aquest sistema ens diu que, o bé x = 1 o bé x = −1 .
Tenim doncs els punts (1,0) i (-1,0). Pel punt (1,0), la primera equació ens dóna que λ = 0 (punt de fet que ja havíem trobat). Pel punt (-1,0), la primera equació ens diu que λ = 2. Tenim doncs un candidat a màxim.
2 2 En el cas e y + λ = 0 tenim que λ = −e y i és per tant negativa. Per tant, aquest cas no ens pot donar un candidat a màxim (recordem que a l’enunciat preguntaven només pel/pels màxim/màxims).
Així, tenim finalment dos candidats a màxim: els punts (1,0) i (-1,0). Podem aplicar el Teorema dels valors extrems perquè la restricció és un conjunt tancat i afitat. Tindrem que f (1,0) = 2 − 1 = 1, f ( −1,0) = 2 + 4 − 1 = 5 Per tant el màxim és el punt (-1,0).
Alternativament, podem estudiar la concavitat/convexitat de la Lagrangiana enc ada candidat.
Per (−1,0) amb λ = 2 , la Lagrangiana és 2 2 L( x, y) = 2 + ( x − 1) 2 − e y − 2( x 2 + y 2 − 1) = − x 2 − 2 y 2 − 2 x − e y + 5 , clarament còncava 2 atès que − x 2 ,−2 y 2 ,−e y són funcions còncaves d’una variable i que 5−2x és lineal.
El punt (−1,0) és un max.
Per (1,0) amb λ = 0 , la Larangiana és 2 2 L( x, y) = 2 + ( x − 1) 2 − e y = x 2 − e y − 2 x + 3 . No podem dir res per simple inspecció La Hessiana és 10 0 2    . TLa matriu és diagnoal i, per tant, els seus valors propis hsón els y2 2  0 − 2 e ( 1 + 2 y )   2 elements de la diagonal: 2>0 i − 2e y (1 + 2 y 2 ) <0. La Hessiana és indefinida (no convexa, no còncava) arreu.
Problema 5: Estudieu els màxims i mínims de la funció f ( x, y, z ) = y − x 2 + z, amb x + y + z ≤ 1, z + x ≤ 1 Solució Problema 5: 2 Tenim que L( x, y, z ) = y − x + z − λ1 ( x + y + z − 1) − λ2 ( z + x − 1). El sistema de Kuhn-Tucker quedarà  ∂L  ∂x = −2 x − λ1 − λ2 = 0  ∂L  = 1 − λ1 = 0 ∂y   ∂L  = 1 − λ1 − λ2 = 0  ∂z  λ1 ( x + y + z − 1) = 0  λ ( x + z − 1) = 0  2 Cas 1. Les dues restriccions inactives, λ1 = λ2 = 0. En aquest cas el sistema queda  ∂L  ∂x = −2 x = 0  ∂L  =1= 0  ∂y  ∂L =1= 0  ∂ z   i no té cap solució.
Cas 2. La primera restricció inactiva λ1 =0 i la segona activa, z + x = 1 En aquest cas el sistema queda  ∂L  ∂x = −2 x − λ2 = 0  ∂L  =1= 0 ∂y   ∂L  = 1 − λ2 = 0  ∂z  x + z −1 = 0   Novament, no té cap solució.
Cas 3. La segona restricció inactiva, λ2 =0 i la primera activa, x + y + z = 1 . El sistema queda: 11  ∂L  ∂x = −2 x − λ1 = 0  ∂L  = 1 − λ1 = 0  ∂y  ∂L  = 1 − λ1 = 0  ∂z  x + y + z =1   Aquest sistema té com solució tots els punts del tipus (-1/2, y, 3/2 – y), amb λ1 = 1, λ2 = 0. Per a que aquests punts compleixin les restriccions cal també y ≥ 0.
Aquests punts (-1/2, y, 3/2 – y) amb y no negativa són candidats a màxim.
Cas 4. Les dues restriccions actives, x + y + z = 1 , x + z = 1 . El sistema queda  ∂L  ∂x = −2 x − λ1 − λ2 = 0  ∂L  = 1 − λ1 = 0 ∂y   ∂L  = 1 − λ1 − λ2 = 0  ∂z  x + y + z −1 = 0  x + z −1 = 0  Com que λ1 = 1 , λ2 = 0. i la única solució ve donada pel punt (-1/2, 0,3/2). Com λ1 = 1 , λ2 = 0, aquest punt és candidat a màxim. Observem que és del mateix tipus que els de l’apartat anterior (amb y = 0).
No podem aplicar el TVE. Amb λ1 = 1 , λ2 = 0, la funció Lagrangiana queda L( x, y, z ) = y − x 2 + z − λ1 ( x + y + z − 1) = − x 2 − x + 1 que és còncava en ser suma de còncava i lineal. Aleshores aquests punts són màxims. No hi ha mínims.
12 ...