Formulacion Lineal

Licenciatura en Administraci´on y Direcci´on de Empresas
Programaci´on Matem´atica
19 de junio de 2006

Ejercicio 1 ( 3 pt.)
Considera la funci´on f (x, y) = (x − y)2 en la regi´on factible
R = {(x, y) ∈ R2 : (x − 1)2 + (y − 2)2

1; y

(x − 1)2 ; y

5}

1. ¿Existen puntos no regulares para este problema?
2. ¿Se trata de un problema convexo? ¿Puedes asegurar la existencia de m´aximo y m´ınimoglobal?¿por qu´e?
√

√

3. Da toda la informaci´on que puedas sobre los puntos A(2, 2), B(3/2, 1/4), C( 2−2 2 , 4+2 2 ).
´n
Solucio
La regi´on factible de este problema y las curvas de nivel de la funci´on objetivo est´an representadas
en las siguientes figuras:

A lo largo del problema, utilizaremos la siguiente notaci´on:
g1 (x, y) = (x − 1)2 + (y − 2)2 − 1; g2 (x, y) = y − (x − 1)2 ; g3 (x, y) = y− 5

L(x, y, µ1 , µ2 , µ3 ) = (x − y)2 + µ1 ((x − 1)2 + (y − 2)2 − 1) + µ2 (y − (x − 1)2 ) + µ3 (y − 5)

∇x L(x, y, µ1 , µ2 , µ3 ) =

2(x − y) + 2µ1 (x − 1) − 2µ2 (x − 1)
−2(x − y) + 2µ1 (y − 2) + µ2 + µ3

∇2x L(x, y, µ1 , µ2 , µ3 ) =

2(1 + µ1 − µ2 )
−2
−2
2(1 + µ1 )

1. Para ver si existen puntos no regulares, debemos buscar puntos en los que los gradientes de las
restricciones activas seanlinealmente dependientes. Para eso, dividimos el problema en los distintos
casos posibles de conjunto de restricciones activas.

•A = ∅
Todos los puntos estrictamente interiores de la regi´on factible son regulares.
•A = {1}
El gradiente de g1 es ∇g1 (x, y) = (2(x − 1), 2(y − 2)) . Este gradiente s´olo se anula en el punto
(1, 2), donde la restricc´
on no es activa (y adem´as es infactible).
•A = {2}El gradiente de g2 es ∇g2 (x, y) = (−2(x − 1), 1) , que no se anula en ning´
un punto.
•A = {3}
El gradiente de g3 es ∇g3 (x, y) = (0, 1) , que tampoco se anula en ning´
un punto.
•A = {1, 2}
No existe ning´
un punto en el que las restricciones 1 y 2 sean activas a la vez.
•A = {1, 3}
En este caso, tampoco existe ning´
un punto donde sean activas las restricciones 1 y 3 a la vez.
•A = {2, 3}
√
Losdos√u
´nicos puntos donde son activas las dos u
´ltimas restricciones son P 1(1 + 5, 5), y
P 2(1 − 5, 5).
√
En P 1, ∇g2 (P 1) = (−2 5, 1) y ∇g3 (P 1) = (0, 1) , que son independientes.
√
En P 2, ∇g2 (P 2) = (2 5, 1) y ∇g3 (P 2) = (0, 1) , que tambi´en son independientes.
Por tanto, los dos son puntos regulares.
•A = {1, 2, 3}
No existen puntos donde las tres restricciones sean activas.
Hemosexplorado impl´ıcitamente todos los puntos de la regi´on factible, y todos son regulares.
2. No se trata de un problema convexo, ya que la regi´on factible no es un conjunto convexo. Por
ejemplo, el segmento que une los puntos factibles (1, 1) y (1, 3) sale de la regi´on factible.
Por otro lado, s´ı podemos asegurar la existencia de m´aximo y m´ınimo locales, ya que se cumplen
las hip´otesis delTeorema de Weierstrass: la funci´on objetivo es continua, y la regi´on factible es
compacta (cerrada← contiene a su frontera, y acotada ← est´a contenida en el rect´angulo [−2, 2] ×
[0, 5] )
3. En ninguno de los puntos estudiaremos la regularidad ya que en el apartado 1 ya hemos visto que
todos los puntos factibles son regulares.
A(2, 2) .f (A) = 0
g1 (A) = 0; g2 (A) = 1; g3 (A) = −3. Se trata de unpunto factible, y la u
´nica restricci´on activa
es la primera.
Si se cumple la condici´
on necesaria de primer orden, existir´an multiplicadores con:




∇x L(2, 2, µ1 , µ2 , µ3 )

µ2 = 0



µ3 = 0

2µ1 − 2µ2
=0
µ2 + µ3
(la restricci´on 2 no es activa)
(la restricci´on 3 no es activa)

=

La u
´nica soluci´
on del sistema anterior es µ1 = µ2 = µ3 = 0. Se cumple la condici´on necesaria
deprimer orden, tanto para m´
aximo como para m´ınimo.
En las condiciones de segundo orden deberemos tener en cuenta que las condiciones de holgura
complementaria se cumplen s´
olo en su versi´on d´ebil, ya que el multiplicador µ1 ha tomado el
valor 0 a pesar de que la primera restricci´on es activa.
∇2x L(2, 2, 0, 0, 0) =

2 −2
−2
2

0

Z = {(z1 , z2 ) : (z1 , z2 )∇gi (A) = 0, ∀i : gi (A) = 0} =...