Pauta Solemne 2 (2-2012)

  • Published on
    28-Sep-2015

  • View
    225

  • Download
    7

DESCRIPTION

solemne2

Transcript

  • UNIVERSIDAD DIEGO PORTALES. FACULTAD DE INGENIERIA.ESCUELA DE INGENIERIA INDUSTRIAL.

    Optimizacion, Solemne 2. Semestre Otono 2012Profesores: Paul Bosch, Rodrigo Lopez, Fernando Paredes, Pablo Rey Tiempo: 110 min.

    Problema 1Un inversionista esta analizando las diferentes opciones para invertir un presupuesto que

    dispone por el periodo fijo de un mes. Para esto debe seleccionar algunos de los N activosdisponibles (n = 1, . . . , N) para armar su portafolio y elegir cuanto invertir en cada uno delos activos seleccionados.

    Para cada uno de estos activos se conoce su rentabilidad (beneficio por peso invertido) enel plazo estipulado y el maximo disponible para adquirir en el mercado. Especficamente, elactivo n tendra una rentabilidad Rn y se puede adquirir un maximo de Sn millones de pesosde este activo. El inversionista tiene un presupuesto de B millones de pesos para invertir.

    La composicion del portafolio deseado debe cumplir con una condicion de diversificaciondel riesgo que implica no invertir en ninguno de los activos mas de un 30% del total invertido.

    (a) [0,7 puntos] Formule un modelo de programacion lineal que permita construir unportfolio que maximice la rentabilidad total.

    (b) [0,7 puntos] Considere ahora que adicionalmente a los bienes del mercado bursatilnacional, el inversionista puede adquirir moneda extranjera. Existen E tipos de mone-das extranjeras (e = 1, . . . , E) que se pueden adquirir y no hay lmites en la cantidaddisponible. Sin embargo, si se incluye cierta cantidad de la moneda e, se debera abonarun costo fijo Fe, independiente de la cantidad comprada.

    La moneda e tiene rentabilidad Ue y la condicion de diversificacion de riesgo, en estecaso, implica adicionalmente que no mas del 20% del total del portafolio puede ser enmoneda extranjera.

    Modifique el modelo de la parte (a) para incluir la alternativa de incluir monedasextrajeras a la hora de conformar el portafolio.

    (c) [0,6 puntos] Finalmente, analizando las caractersticas de las diferentes opciones deinversion se han definido reglas adicionales para la conformacion del portafolio:

    El portafolio debe estar compuesto por un mnimo deK y un maximo de L activosdiferentes (incluidas las monedas extranjeras).

    Si se invierte en el activo 1, no se puede invertir en ningun activo del conjuntoP {2, 3, . . . , N}.

    Si se invierte en los activos 2 y 3, se debe invertir, al menos, un millon de pesosen el activo 4.

    Modifique el modelo de la parte (b) para incluir estas nuevas condiciones que debesatisfacer el portafolio.

    1

  • Problema 2Dado el problema de optimizacion:

    min 12(x21 + x

    22 + x

    23)

    s.a.x1 + x2 + x3 = 1xi 0, i = 1, 2, 3

    (P)

    (a) [0,4 puntos] Compruebe que la funcion objetivo es convexa y que el conjunto defactibilidad es un conjunto convexo.

    (b) [1,0 punto] Encuentre un punto que cumpla las condiciones de optimalidad de KKT.Analice la optimalidad global del punto encontrado.

    (c) [0,6 puntos] Para el caso general:

    min 12(x21 + + x2n)

    s.a.x1 + + xn = 1xi 0, i = 1, . . . , n

    (Pn)

    y usando los resultados de los tems anteriores, postule cual podra ser una solucionoptima para este problema, y justifique la optimalidad de esta a partir del teoremade KKT.

    Problema 3Considere el siguiente modelo de programacion lineal de minimizacion:

    min 2x1 + 3x2 + x3 + 2x4 + x5s.a.

    2x1 x2 + 3x3 + 2x4 + x5 = 6x1 + 2x2 2x3 + x5 4xi 0, i = 1, . . . , 5

    (PL)

    (a) [0,7 puntos] Suponga que la solucion optima del dual de (PL) es y> = (y1 , y2) =(35, 25

    ). Encuentre la solucion optima de (PL).

    (b) [0,7 puntos] Verifique la optimalidad de la solucion optima de (PL) usando lascondiciones de optimalidad del metodo Simplex.

    (c) [0,6 puntos] En forma alternativa, justifique la optimalidad de la solucion optimade (PL) usando las condiciones de optimalidad del Teorema de KKT.

    2

  • SOLUCION

    Pregunta 1

    (a) A continuacion, se muestra un modelo que cumple con lo solicitado.

    Variables

    Para plantear el modelo definimos un conjunto de variables continuas no negativas:

    xn: millones de pesos a invertir en el activo n.

    Funcion objetivo

    La funcion objetivo consiste en maximizar la rentabilidad total:

    maxNn=1

    Rnxn .

    Restricciones

    Incluimos las siguientes restricciones:

    Presupuesto:Nn=1

    xn B.

    Disponibilidad en mercado: xn sn, para todo activo n = 1, . . . , N .

    Diversificacion de riesgo: xn 0,3N

    m=1

    xm, para todo activo n = 1, . . . , N .

    Naturaleza de las variables: xn 0, para todo activo n = 1, . . . , N .

    (b) Para incluir la opcion de la compra de moneda extranjera, se realizan las siguientesmodificaciones.

    Variables

    Se agregan dos conjuntos de variables:

    ye: millones de pesos a invertir en la moneda e. ze: 1 si se invierte en la moneda e (i.e. se paga el costo fijo); 0, en caso contrario.

    Funcion objetivo

    A la funcion objetivo del punto anterior se le agregan dos terminos:

    Se suma la rentabilidad de las inversiones en moneda extranjera:Ee

    Ueye.

    3

  • Se restan los costos fijos por las inversiones en moneda extranjera: Ee

    Feze.

    Restricciones

    Se mantienen las restricciones de disponibilidad de mercado y naturaleza de lasvariables xn.

    Se modifican las restricciones:

    Presupuesto:Nn=1

    xn +Ee=1

    ye B.

    Diversificacion de riesgo: xn 0,3N

    m=1

    xm+Ee=1

    ye, para todo activo n = 1, . . . , N .

    Se agregan las restricciones:

    Relacion entre las variables ye y ze: ye Bzn, para toda moneda extranjerae = 1, . . . , E.

    Condicion adicional de diversificacion de riesgo:Ee=1

    ye 0,2( Nn=1

    xn +Ee=1

    ye

    ).

    Naturaleza de las variables ye y ze: ye 0, ze {0, 1}, para toda moneda extran-jera e = 1, . . . , E.

    (c) Para incluir las condiciones adicionales indicadas, se realizan las siguientes modifica-ciones.

    Variables

    Se agrega un conjunto de variables binarias para indicar si se invierte o no en el activon (similar a las ze de las monedas, pero para los activos):

    wn: 1 si se invierte en el activo n; 0, en caso contrario.

    Ademas, se agrega una variable binaria v que toma valor 1 si se invierte en ambosactivos 2 y 3 (entonces se debe invertir en 4), 0, si no.

    Funcion objetivo

    La funcion objetivo no se modifica.

    Restricciones

    Se mantienen todas las restricciones del punto (b)

    Se agregan las restricciones:

    Relacion entre las variables xn y wn: xn Bwn o xn y wn: xn Snwn, para todoactivo n = 1, . . . , N .

    4

  • Cantidad de activos diferentes: K Nn=1

    wn +Ee=1

    ze L.

    Si se invierte en 1, no se puede invertir en los activos en P : w1 + wn 1, paratodo activo n P .

    Definicion de variable v: w2 + w3 v + 1. Si se invierte en 2 y 3, se debe invertir un millon en 4: x4 v. Naturaleza de las variables wn y v: wn {0, 1}, para todo activo n = 1, . . . , N yv {0, 1}.

    Pregunta 2

    (a) Se comprueba facilmente que la Hessiana de la funcion objetivo es la matriz identidadla que evidentemente es una matriz definida positiva y por tanto, la funcion es estric-tamente convexa. Respecto al conjunto de factibilidad es suficiente ver que este estaformado por una restriccion lineal y restricciones de no negatividad de las variables, ypor resultados del curso, este conjunto es convexo.

    (b) Analicemos el caso donde el conjunto de ndices activos es el vacio, es decir I(x) = .Esto implica que los multiplicadores asociados a las restricciones de no negatividad sontodos nulos, y por tanto, se tiene que:

    f(x) + h(x) = 0

    donde h(x) = x1 + x2 + x3 1 x1x2x3

    + 11

    1

    = 00

    0

    y por tanto, obtenemos que x1 = x2 = x3 = . Evaluando en la funcion h(x1, x2, x3)llegamos finalmente a que x1 = x2 = x3 =

    13y = 1

    3. El punto encontrado es un

    mnimo global dado que nuestro problema de optimizacion es convexo.

    (c) Para el caso general, y viendo los resultados de los item anteriores, un buen postulantepara optimo es x1 = = xn = 1n . Por otro lado, este punto es regular y cumple lacondicion

    f(x) + h(x) = 0donde h(x) = x1 + + xn 1. Evaluando en el punto se tiene: x1...

    xn

    + 1...

    1

    = 0...

    0

    es decir, existe = 1

    n. Finalmente, el punto encontrado es un mnimo global dado

    que nuestro problema de optimizacion sigue siendo convexo.

    5

  • Pregunta 3

    (a) El problema dual de (PL) se escribe como:

    max 6u1 + 4u2s.a.

    2u1 + u2 2u1 + u2 33u1 2u2 12u1 2u1 + u2 1u2 irrestrictau2 0

    Las restricciones 1, 2 y 4 del dual son inactivas en el optimo. Luego por el teorema deholgura complementaria las variables x1, x2 y x4 en el primal deben ser iguales a cero.

    Luego las variables basicas en el primal son las variables x3 y x5 . En consecuencia, labase optima es :

    B =

    (3 1

    2 1)= B1 =

    (151

    525

    35

    )Luego en el optimo se tiene:

    xB =

    (x3x5

    )= B1b =

    (25245

    )y la solucion del problema es:

    x =(0 0 2

    50 24

    5

    )(Sol. (PL))

    (b) El vector de variables duales optimas es:

    piT =

    (3

    5

    2

    5

    )= c>BB

    1

    Luego se tiene que el vector ( fila ) de costos reducidos de las variables no basicas es:

    c>N = c>N c>BB1N

    =(2 3 2

    ) ( 35

    25

    )( 2 1 21 2 0

    )=

    (25

    145

    45

    ) 0En consecuencia, se satisface la condicion de optimalidad del metodo Simplex paraminimizacion.

    6

  • (c) Como todo modelo de programacion lineal es un modelo convexo entonces las condi-ciones necesarias de optimalidad del teorema de KKT se convierten en suficientes,sin importar regularidad. Estas condiciones se satisfacen para la solucion optima en-contrada en el tem anterior). En Efecto, existen multiplicadores R , 0 y = (1, . . . , 5) R5 donde i 0, i = 1, ...., 5 tales que:

    23121

    +

    21321

    + 12201

    5i=1

    iei =

    00000

    donde ei representa el i-esimo vector canonico, por tanto

    23121

    +

    21321

    + 12201

    =

    12345

    (1)Ademas, se tienen las condiciones de holgura complementarias:

    (4 x1 2x2 + 2x3 x5) = 0ixi = 0 , i = 1, . . . , 5

    y evaluando en la solucion (Sol. (PL)) se tiene que la restriccion de desigualdad esactiva. Ademas, viendo las restricciones de no negatividad tenemos que 3 = 5 = 0.Sustituyendo todo esto en (1) obtenemos:

    23121

    +

    21321

    + 12201

    =

    12040

    De la tercera y de la quinta ecuacion obtenemos inmediatamente que{

    3+ 2 = 1 = 1

    y por tanto = 35y = 2

    5 0. Finalmente, sustituyendo estos valores tenemos

    que 1 =25, 2 =

    145y 4 =

    45, es decir, existen multiplicadores R , 0 y

    = (1, . . . , 5) R5 donde i 0, i = 1, ...., 5 que cumplen las condiciones delTeorema de KKT.

    7