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

Optimizacion, Pauta Solemne 2. Semestre Primavera 2011

Profesores: Paul Bosch, Fernando Paredes, Pablo Rey Tiempo: 100 min.

Problema 1 (2 puntos)

El administrador de un fondo de inversiones esta definiendo las inversiones del proximoano. Para esto, se debe seleccionar un conjunto de proyectos de un total de N (N ≥ 10)proyectos, y los montos a invertir en los proyectos seleccionados. Para cada proyecton (n = 1, . . . , N) se conoce retorno esperado por peso invertido rn pesos y el montomaximo posible a invertir Pn. El administrador cuenta con un presupuesto maximopara inversion de B pesos y puede seleccionar, a lo mas, Q proyectos.

(a). (1 punto) Formule un modelo de programacion lineal entera mixta que permitadefinir el portafolio de inversiones que maximiza el retorno esperado total.

Un modelo que permite determinar el portafolio optimo de inversiones se puede planteardefiniendo, para cada proyecto n, la variable binaria

xn =

{1 si se selecciona el proyecto i para invertir,

0 en caso contrario.

y la variable no negativa yn que indica el monto invertido en cada proyecto.La funcion objetivo es maximizar el retorno esperado de las inversiones:

maxN∑

n=1

rnyn .

Las restricciones son las siguientes:

• Solo invertir fondos en proyectos seleccionados (relacion entre variables xn e yn) yno exceder el maximo a invertir por proyecto:Para cada proyecto n, yn ≤ Pnxn.

• No exceder presupuesto:N∑

n=1

yn ≤ B.

• Seleccionar, a lo mas, Q proyectos:N∑

n=1

xn ≤ Q.

• Naturaleza de las variables: Para cada proyecto n, xn ∈ {0, 1} e yn ≥ 0.

Considere ahora que el administrador desea que el portafolio seleccionado cumpla, adi-cionalmente, con las siguientes condiciones: Si se invierte en el proyecto 3 no se puedeinvertir en los proyectos 2 o 4; si se invierte en el proyecto 5, se debe invertir tambien

en el proyecto 8, y el monto invertido en este ultimo debe ser, al menos, el doble de loinvertido en el proyecto 5; si se invierte en el proyecto 8, se debe invertir en el proyecto1 o el proyecto 4; el maximo entre lo invertido en los proyectos 1, 2 y 3 no deber superarel total invertido en los proyectos 4 y 5.

(b). (1 punto) Modifique el modelo propuesto en el punto anterior para considerar lasnuevas condiciones.

No es necesario definir nuevas variables. Para incluir las condiciones que se indican, sedefinen las siguientes restricciones adicionales:

• Si se invierte en el proyecto 3 no se puede invertir en los proyectos 2 o 4: x2 ≤ 1−x3y x4 ≤ 1− x3. Equivalentemente, tambien puede ser: x2 + x3 ≤ 1 y x3 + x4 ≤ 1.Otra alternativa serıa, 2x3 + x2 + x4 ≤ 2.

• Si se invierte en el proyecto 5, se debe invertir tambien en el proyecto 8, y el montoinvertido en este ultimo debe ser, al menos, el doble de lo invertido en el proyecto5: y8 ≥ 2y5.

La condicion x5 ≤ x8 modela el hecho que si se selecciona 5 tambien se selecciona elproyecto 8, pero no incluye la condicion sobre los montos. Definida la desigualdadentre los montos, la desigualdad con las x es innecesaria ya que esta implicada porla combinacion de y8 ≥ 2y5 y las yn ≤ Pnxn.

• Si se invierte en el proyecto 8, se debe invertir en el proyecto 1 o el proyecto 4:x8 ≤ x1 + x4.

• El maximo entre lo invertido en los proyectos 1, 2 y 3 no deber superar el totalinvertido en los proyectos 4 y 5: yn ≤ y4 + y5 para n = 1, 2, 3.

Problema 2 (2 puntos)

Considere el modelo de optimizacion:

min− x2 − y2

x2 + y − 1 = 0

− x− 2y + 1 ≤ 0 (P)

(a). (0,5 puntos) Compruebe que todos los puntos del conjunto de factibilidad sonregulares.

Sean g1(x, y) = x2 + y − 1 y g2(x, y) = −x− 2y + 1 las funciones que definen loslados izquierdos de las restricciones. Luego,

∇g1(x, y) =

(2x1

)y ∇g2(x, y) =

(−1−2

).

Ademas,

∣∣∣∣ 2x −11 −2

∣∣∣∣ = −4x + 1 = 0 ⇐⇒ x = 1/4. Pero no existe y tal que el

punto (1/4, y) pertenezca al dominio de factibilidad. En consecuencia, en todoslos puntos del conjunto de factibilidad se satisface la condicion de regularidad.

(b). (1,5 puntos) Encuentre todos los puntos de KKT. Determine la(s) solucion(es)optima(s) de (P), justificando la optimalidad de la(s) solucion(es) encontrada(s).

Un punto (x, y) es un punto de KKT si se satisface que existan λ ∈ mathbbR,µ ≥ 0 tales que: (

−2x−2y

)+ λ

(2x1

)+ µ

(−1−2

)=

(00

)(∗)

µ(−x− 2y + 1) = 0

g1(x, y) = x2 + y − 1 = 0

g2(x, y) = −x− 2y + 1 ≤ 0 .

Consideramos dos casos.

Caso 1: Restriccion e desigualdad inactiva en (x, y). Luego, µ = 0. Entonces, laprimera ecuacion en (∗) queda 2x(−1 + λ) = 0, lo que implica que x = 0 o λ = 1.

Si x = 0, entonces y = 1. Como el punto P1 = (0, 1) es factible, tenemos el primerpunto de KKT.

Si λ = 1, entonces y = 1/2 y x = ± 1√2

. El valor negativo x = − 1√2

no corre-

sponde a un punto factible: el punto (− 1√2, 12) no satisface la segunda restriccion.

Por otro lado, para el valor positivo x = 1√2, el punto P2 = (− 1√

2, 12) es factible y

satisface las condiciones de KKT.

Caso 2: Restriccion e desigualdad activa en (x, y). Por lo tanto, ambas restric-ciones son activas y esto ocurre en los puntos P3 = (−1

2, 34) y P4 = (1, 0).

Verifiquemos primero que P3 satisface la condicion (∗): Se tiene el sistema lineal,

λ+ µ = 1

λ− 2µ = −3/2 .

La unica solucion de este sistema es λ = 1/6 y µ = 5/6 ≥ 0. Por lo tanto, P3 esotro punto de KKT.

De manera similar, se comprueba facilmente que el punto P4 tambian satisface lacondicion (∗).Dado que (P) admite solucion optima (se verifica por el teorema de Weierstrass)y hemos encontrado todos los puntos de KKT (y no hay puntos no regulares),entonces basta con evaluar la funcion objetivo en dichos puntos para determinarlas soluciones optimas. En consecuencia, las soluciones optimas son los puntos P1

y P4 con valor optimo igual a -1.

Problema 3 (2 puntos)

Una fabrica de aberturas produce tres modelos de ventanas con marcos de aluminio.Los insumos principales para estos productos son el vidrio y los perfiles de aluminio.Diariamente, se dispone de un total de 220 planchas de vidrio y de 300 perfiles dealumnio.

Los materiales necesarios para fabricar cada uno de los modelos de ventanas, semuestran en la tabla.

Modelo A Modelo E Modelo UVidrio (planchas) 1 2 1Aluminio (perfiles) 3 1 1

Cada unidad del modelo A trae un beneficio para la empresa de 6 mil pesos, cada unidadde tipo E, un beneficio de 5 mil pesos y una unidad del modelo U, un beneficio de 4 milpesos.

Para planificar la produccion, la empresa ha formulado el siguiente modelo de pro-gramacion lineal:

max 6x1 + 5x2 + 4x3

x1 + 2x2 + x3 ≤ 220

3x1 + x2 + x3 ≤ 300

x1, x2, x3 ≥ 0

donde las variables son: x1: unidades del modelo A a fabricar; x2: unidades del modeloE a fabricar; x3: unidades del modelo U a fabricar.

(a). (0,4 puntos) Plantee el problema dual del modelo de planificacion utilizado por laempresa.

min 220y1 + 300y2

y1 + 3y2 ≥ 6

2y1 + y2 ≥ 5

y1 + y2 ≥ 4

y1, y2 ≥ 0

(b). (0,4 puntos) Resuelva graficamente el problema planteado en el punto (a). Ex-plique el significado de los valores de las variables en la solucion optima encontrada.

El conjunto factible del problema, se muestra en la figura:

El problema tiene solucion optima: si bien el conjunto factible no es acotado, lafuncion objetivo sı esta acotada en este conjunto. Ademas, si el problema tieneoptimo finito y hay soluciones basicas, al menos una de ellas es optima. Lassoluciones basicas factibles corresponden a los vertices del cojunto factible, quecomo se ve en la figura, en este caso son cuatro. Vamos a evaluar la funcionobjetivo en cada uno de ellos para ver cual de ellos es optimo. De la figura seve rapidamente que dos de los vertices son los puntos (6, 0) y (0, 5) con valoresobjetivo 1320 y 1500, respectivamente.

Los otros dos vertices corresponden a las intersecciones de dos rectas que definenla frontera de dos restricciones:

• R1 con R3: El punto satisface el sistema

y1 + 3y2 =6

y1 + y2 =4 .

La unica solucion de este sistema es y1 = 3, y2 = 1. El valor de la funcionobjetivo en este punto es 960.

• R2 con R3: El punto satisface el sistema

2y1 + y2 =6

y1 + y2 =4 .

La unica solucion de este sistema es y1 = 1, y2 = 3. El valor de la funcionobjetivo en este punto es 1120.

Por lo tanto, el optimo es el punto y∗ = (3, 1).

(c). (0,6 puntos) A partir de la solucion optima del dual encontrada en la parte (b),encuentre una solucion optima para el problema primal, utilizando el teorema deholguras complementarias.

En el optimo del dual calculado en el punto anterior, ambas variables son positivas,por lo que en el primal ambas restricciones son activas.

Ademas, como la segunda restriccion del dual, 2y1+y2 ≥ 5 no es activa (2y∗1 +y∗2 =2× 3 + 1 = 7 > 5) entonces, en el optimo del primal x∗2 = 0.

A partir de esta informacion, sabemos entonces que las otras variables del primaldeben satisfacer el sistema:

x∗1 + x∗3 =200

3x∗1 + x∗3 =4 .

Por lo tanto, el optimo del dual es x∗1 = 40, x∗2 = 0, x∗3 = 180.

(d). (0,6 puntos) Verifique la optimalidad de la solucion encontrada en (c), aplicandoel criterio correspondiente del metodo simplex. Indicacion. Recuerde que paraaplicar el metodo simplex, el problema debe estar en la forma estandar.

Para poder aplicar el criterio de simplex, primero debemos escribir la formaestandar del problema primal y determinar la base que corresponde a la solucionbasica x∗ determinada en el punto anterior.

La forma estandar del modelo de produccion que usa la fabrica es:

min − 6x1 − 5x2 − 4x3

x1 + 2x2 + x3 + x4 + = 220

3x1 + x2 + x3 + + x5 = 300

x1, x2, x3, x4, x5 ≥ 0

El problema tiene dos restricciones cuyos lados derechos son linealmente dependi-entes, por lo tanto, las bases del problema consisten de dos variables. Como en lasolucion x∗ las variables x1 y x3 toman valores positivos, la base esta formada porestas variables. Entonces,

B∗ =

[1 13 1

]lo que implica que (B∗)−1 =

[−1/2 1/23/2 −1/2

]Ahora, calculamos los costos reducidos de las variables no basicas (x2, x4, x5):

c>R = c>R − c>B∗R

= (−5, 0, 0)− (−6,−4)

[−1/2 1/23/2 −1/2

] [2 1 01 0 1

]= (−5, 0, 0)− (−3,−1)

[2 1 01 0 1

]= (−5, 0, 0)− (−7,−3,−1)

= (2, 3, 1) .

Como ninguno de los costos reducidos de las variables no basicas es negativo,podemos concluir que el punto x∗ es efectivamente el optimo del problema primal.