Pauta Solemne 2 (2-2012)

  • Published on
    28-Sep-2015

  • View
    227

  • Download
    7

DESCRIPTION

solemne2

Transcript

<ul><li><p>UNIVERSIDAD DIEGO PORTALES. FACULTAD DE INGENIERIA.ESCUELA DE INGENIERIA INDUSTRIAL.</p><p>Optimizacion, Solemne 2. Semestre Otono 2012Profesores: Paul Bosch, Rodrigo Lopez, Fernando Paredes, Pablo Rey Tiempo: 110 min.</p><p>Problema 1Un inversionista esta analizando las diferentes opciones para invertir un presupuesto que</p><p>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.</p><p>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.</p><p>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.</p><p>(a) [0,7 puntos] Formule un modelo de programacion lineal que permita construir unportfolio que maximice la rentabilidad total.</p><p>(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.</p><p>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.</p><p>Modifique el modelo de la parte (a) para incluir la alternativa de incluir monedasextrajeras a la hora de conformar el portafolio.</p><p>(c) [0,6 puntos] Finalmente, analizando las caractersticas de las diferentes opciones deinversion se han definido reglas adicionales para la conformacion del portafolio:</p><p> El portafolio debe estar compuesto por un mnimo deK y un maximo de L activosdiferentes (incluidas las monedas extranjeras).</p><p> Si se invierte en el activo 1, no se puede invertir en ningun activo del conjuntoP {2, 3, . . . , N}.</p><p> Si se invierte en los activos 2 y 3, se debe invertir, al menos, un millon de pesosen el activo 4.</p><p>Modifique el modelo de la parte (b) para incluir estas nuevas condiciones que debesatisfacer el portafolio.</p><p>1</p></li><li><p>Problema 2Dado el problema de optimizacion:</p><p>min 12(x21 + x</p><p>22 + x</p><p>23)</p><p>s.a.x1 + x2 + x3 = 1xi 0, i = 1, 2, 3</p><p>(P)</p><p>(a) [0,4 puntos] Compruebe que la funcion objetivo es convexa y que el conjunto defactibilidad es un conjunto convexo.</p><p>(b) [1,0 punto] Encuentre un punto que cumpla las condiciones de optimalidad de KKT.Analice la optimalidad global del punto encontrado.</p><p>(c) [0,6 puntos] Para el caso general:</p><p>min 12(x21 + + x2n)</p><p>s.a.x1 + + xn = 1xi 0, i = 1, . . . , n</p><p>(Pn)</p><p>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.</p><p>Problema 3Considere el siguiente modelo de programacion lineal de minimizacion:</p><p>min 2x1 + 3x2 + x3 + 2x4 + x5s.a.</p><p>2x1 x2 + 3x3 + 2x4 + x5 = 6x1 + 2x2 2x3 + x5 4xi 0, i = 1, . . . , 5</p><p>(PL)</p><p>(a) [0,7 puntos] Suponga que la solucion optima del dual de (PL) es y&gt; = (y1 , y2) =(35, 25</p><p>). Encuentre la solucion optima de (PL).</p><p>(b) [0,7 puntos] Verifique la optimalidad de la solucion optima de (PL) usando lascondiciones de optimalidad del metodo Simplex.</p><p>(c) [0,6 puntos] En forma alternativa, justifique la optimalidad de la solucion optimade (PL) usando las condiciones de optimalidad del Teorema de KKT.</p><p>2</p></li><li><p>SOLUCION</p><p>Pregunta 1</p><p>(a) A continuacion, se muestra un modelo que cumple con lo solicitado.</p><p>Variables</p><p>Para plantear el modelo definimos un conjunto de variables continuas no negativas:</p><p> xn: millones de pesos a invertir en el activo n.</p><p>Funcion objetivo</p><p>La funcion objetivo consiste en maximizar la rentabilidad total:</p><p>maxNn=1</p><p>Rnxn .</p><p>Restricciones</p><p>Incluimos las siguientes restricciones:</p><p> Presupuesto:Nn=1</p><p>xn B.</p><p> Disponibilidad en mercado: xn sn, para todo activo n = 1, . . . , N .</p><p> Diversificacion de riesgo: xn 0,3N</p><p>m=1</p><p>xm, para todo activo n = 1, . . . , N .</p><p> Naturaleza de las variables: xn 0, para todo activo n = 1, . . . , N .</p><p>(b) Para incluir la opcion de la compra de moneda extranjera, se realizan las siguientesmodificaciones.</p><p>Variables</p><p>Se agregan dos conjuntos de variables:</p><p> 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.</p><p>Funcion objetivo</p><p>A la funcion objetivo del punto anterior se le agregan dos terminos:</p><p> Se suma la rentabilidad de las inversiones en moneda extranjera:Ee</p><p>Ueye.</p><p>3</p></li><li><p> Se restan los costos fijos por las inversiones en moneda extranjera: Ee</p><p>Feze.</p><p>Restricciones</p><p>Se mantienen las restricciones de disponibilidad de mercado y naturaleza de lasvariables xn.</p><p>Se modifican las restricciones:</p><p> Presupuesto:Nn=1</p><p>xn +Ee=1</p><p>ye B.</p><p> Diversificacion de riesgo: xn 0,3N</p><p>m=1</p><p>xm+Ee=1</p><p>ye, para todo activo n = 1, . . . , N .</p><p>Se agregan las restricciones:</p><p> Relacion entre las variables ye y ze: ye Bzn, para toda moneda extranjerae = 1, . . . , E.</p><p> Condicion adicional de diversificacion de riesgo:Ee=1</p><p>ye 0,2( Nn=1</p><p>xn +Ee=1</p><p>ye</p><p>).</p><p> Naturaleza de las variables ye y ze: ye 0, ze {0, 1}, para toda moneda extran-jera e = 1, . . . , E.</p><p>(c) Para incluir las condiciones adicionales indicadas, se realizan las siguientes modifica-ciones.</p><p>Variables</p><p>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):</p><p> wn: 1 si se invierte en el activo n; 0, en caso contrario.</p><p>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.</p><p>Funcion objetivo</p><p>La funcion objetivo no se modifica.</p><p>Restricciones</p><p>Se mantienen todas las restricciones del punto (b)</p><p>Se agregan las restricciones:</p><p> Relacion entre las variables xn y wn: xn Bwn o xn y wn: xn Snwn, para todoactivo n = 1, . . . , N .</p><p>4</p></li><li><p> Cantidad de activos diferentes: K Nn=1</p><p>wn +Ee=1</p><p>ze L.</p><p> Si se invierte en 1, no se puede invertir en los activos en P : w1 + wn 1, paratodo activo n P .</p><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}.</p><p>Pregunta 2</p><p>(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.</p><p>(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:</p><p>f(x) + h(x) = 0</p><p>donde h(x) = x1 + x2 + x3 1 x1x2x3</p><p>+ 11</p><p>1</p><p> = 00</p><p>0</p><p>y por tanto, obtenemos que x1 = x2 = x3 = . Evaluando en la funcion h(x1, x2, x3)llegamos finalmente a que x1 = x2 = x3 =</p><p>13y = 1</p><p>3. El punto encontrado es un</p><p>mnimo global dado que nuestro problema de optimizacion es convexo.</p><p>(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</p><p>f(x) + h(x) = 0donde h(x) = x1 + + xn 1. Evaluando en el punto se tiene: x1...</p><p>xn</p><p>+ 1...</p><p>1</p><p> = 0...</p><p>0</p><p>es decir, existe = 1</p><p>n. Finalmente, el punto encontrado es un mnimo global dado</p><p>que nuestro problema de optimizacion sigue siendo convexo.</p><p>5</p></li><li><p>Pregunta 3</p><p>(a) El problema dual de (PL) se escribe como:</p><p>max 6u1 + 4u2s.a.</p><p>2u1 + u2 2u1 + u2 33u1 2u2 12u1 2u1 + u2 1u2 irrestrictau2 0</p><p>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.</p><p>Luego las variables basicas en el primal son las variables x3 y x5 . En consecuencia, labase optima es :</p><p>B =</p><p>(3 1</p><p>2 1)= B1 =</p><p>(151</p><p>525</p><p>35</p><p>)Luego en el optimo se tiene:</p><p>xB =</p><p>(x3x5</p><p>)= B1b =</p><p>(25245</p><p>)y la solucion del problema es:</p><p>x =(0 0 2</p><p>50 24</p><p>5</p><p>)(Sol. (PL))</p><p>(b) El vector de variables duales optimas es:</p><p>piT =</p><p>(3</p><p>5</p><p>2</p><p>5</p><p>)= c&gt;BB</p><p>1</p><p>Luego se tiene que el vector ( fila ) de costos reducidos de las variables no basicas es:</p><p>c&gt;N = c&gt;N c&gt;BB1N</p><p>=(2 3 2</p><p>) ( 35</p><p>25</p><p>)( 2 1 21 2 0</p><p>)=</p><p>(25</p><p>145</p><p>45</p><p>) 0En consecuencia, se satisface la condicion de optimalidad del metodo Simplex paraminimizacion.</p><p>6</p></li><li><p>(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:</p><p>23121</p><p>+ </p><p>21321</p><p>+ 12201</p><p>5i=1</p><p>iei =</p><p>00000</p><p>donde ei representa el i-esimo vector canonico, por tanto</p><p>23121</p><p>+ </p><p>21321</p><p>+ 12201</p><p> =</p><p>12345</p><p> (1)Ademas, se tienen las condiciones de holgura complementarias:</p><p> (4 x1 2x2 + 2x3 x5) = 0ixi = 0 , i = 1, . . . , 5</p><p>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:</p><p>23121</p><p>+ </p><p>21321</p><p>+ 12201</p><p> =</p><p>12040</p><p>De la tercera y de la quinta ecuacion obtenemos inmediatamente que{</p><p>3+ 2 = 1 = 1</p><p>y por tanto = 35y = 2</p><p>5 0. Finalmente, sustituyendo estos valores tenemos</p><p>que 1 =25, 2 =</p><p>145y 4 =</p><p>45, es decir, existen multiplicadores R , 0 y</p><p> = (1, . . . , 5) R5 donde i 0, i = 1, ...., 5 que cumplen las condiciones delTeorema de KKT.</p><p>7</p></li></ul>