• Author / Uploaded
• x10luis10x

Citation preview

IN34A: Optimizaci´on

4. 4.1.

Pag. 5

Problemas Problema 1

Una florista sabe hacer solo 2 tipos distintos de arreglos florales (x1 y x2 ) para los cuales dispone de 3 tipos distintos de flores: rozas, tulipanes e ibizcos. Los requerimientos de flores para cada arreglo, la disponibilidad de flores y los precios de cada arreglo vienen dados por:

FLORES Rozas Tulipanes Ibizcos PRECIO

x1 x2 DISPONIBILIDAD 3 1 300 1 1 140 1 3 300 2000 1000 -

1. Formule un PPL que resuelva el problema de maximizaci´on de ingresos por ventas sujeto a la disponibilidad de recursos. 2. ¿Cual es el problema dual asociado? ¿Que situaci´on podr´ıa estar optimizando? 3. Usando el teorema de holgura complementaria, encuentre el ´optimo del problema dual sabiendo que el ´optimo primal viene dado por (x1 = 80, x2 = 60). 4. Suponga que retorna frustrado despu´es que una bella dama le cerrara la puerta cuando usted le llevaba amablemente una rosa, un tulip´an y un ibizco 6 . Si se encuentra con la florista, ¿Cuanto cree que estar´ıa dispuesta a pagar ella por sus flores? Soluci´ on 1. A estas alturas del curso, todos debieran de poder modelar un problema tan sencillo como este por lo que ahorrar´e comentarios: m´ax z = 2000x1 + 1000x2 s.a 3x1 + x2 x1 + x2 x1 + 3x2 x 1 , x2 6

≤ ≤ ≤ ≥

300 140 300 0

Dependiendo el caso, puede alternativamente imaginar que es usted una bella dama quien cerr´o la puerta a un apuesto varon sin antes haberse quedado con las flores :)

IN34A: Optimizaci´on

Pag. 6

2. Para encontrar el dual, procedemos como se describi´o en la introducci´on teorica de esta clase aplicando las relaciones de dualidad: m´ın w = 300y1 + 140y2 + 300y3 s.a 3y1 + y2 + y3 ≥ 2000 y1 + y2 + 3y3 ≥ 1000 y 1 , y2 , y3 ≥ 0 Esta formulaci´on resuelve el problema de un agente externo que quiere saber que precio unitario ofrecer por cada una de las flores si quiere comprarle todas las flores a la florista. As´ı, y1 , y2 e y3 son los precios asociados a las rozas, tulipanes e ibizcos. 3. La florista ha encontrado su combinaci´on ´optima (¯ x1 = 80, x¯2 = 60). Sabemos que en el ´optimo se cumple el teorema de holgura complementaria. Entonces, podemos aplicarlo: a) (3¯ x1 + x¯2 − 300) · y¯1 = 0 b) (¯ x1 + x¯2 − 140) · y¯2 = 0 c) (¯ x1 + 3¯ x2 − 300) · y¯3 = 0 d ) (2000 − 3¯ y1 − y¯2 − y¯3 ) · x¯1 = 0 e) (1000 − y¯1 − y¯2 − 3¯ y3 ) · x¯2 = 0 Como x¯1 = 80 y x¯2 = 60, se tiene que: a) ⇒ y¯1 ∈ R b) ⇒ y¯2 ∈ R c) ⇒ y¯3 = 0 d ) ⇒ 3¯ y1 + y¯2 = 2000 e) ⇒ y¯1 + y¯2 = 1000 Resolviendo el sistema: y¯1 = 500

y¯2 = 500

y¯3 = 0

Notar que z(¯ x) = w(¯ y ) = 220000 ¿Como se interpreta esto?. La florista vender´a rosas y tulipanes a un precio de $500 cada una y entregar´a como oferta los ibizcos gratis, pero esto solo si se vende todo como un paquete. Esto toma sentido pues si vende todas las rosas y tulipanes (dado que solo sabe hacer los arreglos florales descritos) no podr´a sacarle provecho alguno a los ibizcos.

IN34A: Optimizaci´on

Pag. 7

4. Asumiendo los paradigmas de competencia perfecta7 , la florista ofrecer´a por las flores una cantidad identica a lo que ella ganar´ıa por ellas. Este valor viene dado nuevamente por los ´optimos duales o precios sombras: y¯1 = 500

y¯2 = 500

y¯3 = 0

En efecto y para reforzar lo dicho, en el ´optimo se tendr´a que: X

z ∗ = cB B ∗ −1 b −

c¯R xR

no b´ asica

X

∗

= π b−

c¯R · xR

no b´ asica

Entonces ∂z ∗ ∗ = cB B ∗ −1 ·i = πi ∂bi

4.2.

Problema 2

Considere el cl´asico problema de combinaci´on de productos sujeto a restricciones de disponibilidad de recursos: m´ax z = x1 + 3x2 s.a x1 + 4x2 x1 + 2x2 x1 + x2 x 1 , x2

≤ ≤ ≤ ≥

100 60 50 0

1. Realice un an´alisis de sensibilidad para el vector del lado derecho de las restricciones. 2. Realice un an´alisis de sensibilidad para el vector de coeficientes de la funci´on objetivo. 3. Suponga que se evalua la posibilidad de fabricar un nuevo producto xnuevo de modo que el problema queda descrito como m´ax z = x1 + 3x2 + xnuevo s.a x1 + 4x2 + 5xnuevo x1 + 2x2 + 3xnuevo x1 + x2 + 2xnuevo x1 , x2 , xnuevo 7

≤ ≤ ≤ ≥

100 60 50 0

Es decir, que el precio de transacci´ on de un bien es tal todos los agentes quedan indiferentes

IN34A: Optimizaci´on

Pag. 8

¿Sigue siendo ´optima la soluci´on anteriormente planteada? Hint: En el ´optimo, la base esta formada por las variables x1 , x2 y x5 , en donde se han asignado las variables x3 , x4 y x5 como holgura de las restricciones seg´ un el orden enunciado. Soluci´ on Antes de cualquier cosa, pasamos a forma estandar: m´ın z˜ = −x1 − 3x2 s.a

x1 + 4x2 + x3 x1 + 2x2 + x4 x1 + x2 + x5 x 1 , x 2 , x3 , x 4 , x5

= = = ≥

100 60 50 0

De la indicaci´on. x1 x2 x5   1 4 0 −1 2 0 B ∗ = 1 2 0 ⇒ B ∗ −1 =  1/2 −1/2 0  1 1 1 1/2 −3/2 1 1. Ante variaciones de b, ya dijimos que solo tenemos que verificar factibilidad:   −1 2 0 b1 B ∗ −1 · b =  1/2 −1/2 0   b2  ≥ ~0 1/2 −3/2 1 b3 

Un an´alisis general nos conducir´ıa a un espacio de soluciones en R3 . Sin embargo, lo usual es analizar la variaci´on de la disponibilidad de un recurso dejando los otros constantes (ceteris paribus). b1 :     −b1 + 120 b1 −1 2 0  1/2 −1/2 0   60  =  b1 − 30  ≥ ~0 2 b1 1/2 −3/2 1 50 − 40 2 

Entonces, la inecuaci´on vectorial nos entrega 3 inecuaciones escalares que finalmente imponen que: 80 ≤ b1 ≤ 120

IN34A: Optimizaci´on

Pag. 9

b2 : 

    −100 + 2b2 −1 2 0 100  1/2 −1/2 0   b2  =   ≥ ~0 50 − b22 1/2 −3/2 1 50 50 − 3b22 + 500 Entonces, la inecuaci´on vectorial nos entrega 3 inecuaciones escalares que finalmente imponen que: 50 ≤ b2 ≤

200 3

b3 :     −100 + 120 −1 2 0 100  1/2 −1/2 0   60  =  50 − 30  ≥ ~0 50 − 90 + b3 1/2 −3/2 1 b3 

Entonces, la inecuaci´on vectorial nos entrega s´olo una inecuaci´on con dependencia de b3 , la que nos dice que: b3 ≤ 40 2. Como ya se argument´o, ahora solo nos preocuparemos de la condici´on de optimalidad: c¯R = cR − cB B −1 R ≥ 0. Al igual que el caso anterior, se estudiar´a la sensibilidad de los parametros independientemente. c1 : x1 es b´asica, entonces tenemos que considerar todos los costos reducidos. (¯ c3 , c¯4 ) = (c3 , c4 ) − (c1 , c2 , c5 )B −1 R  −1 2  = (0, 0) − (−c1 , −3, 0) 1/2 −1/2 1/2 −3/2  −1 2  = (0, 0) − (−c1 , −3, 0) 1/2 −1/2 1/2 −3/2 = −(c1 − 3/2, −2c1 + 3/2) ≥ (0, 0) Entonces 3/4 ≤ c1 ≤ 3/2

  0 1 0 0  0 1  1 0 0  

IN34A: Optimizaci´on

Pag. 10

c2 : x2 tambien es b´asica y por lo tanto tenemos que considerar todos los costos reducidos. (¯ c3 , c¯4 ) = (c3 , c4 ) − (c1 , c2 , c5 )B −1 R  −1  = (0, 0) − (−1, −c2 , 0) 1/2 1/2  −1  1/2 = (0, 0) − (−1, −c2 , 0) 1/2 c2 c2 = −(1 − , −2 + ) ≥ (0, 0) 2 2 Entonces

  1 0 2 0 −1/2 0   0 1  −3/2 1 0 0  2 −1/2  −3/2

2 ≤ c2 ≤ 4 Obs:An´alisis para c3 , c4 y c5 no tienen sentido para este problema pues las variables asociadas son las de holgura. De todas formas, el procedimiento es an´alogo (con la diferencia que cuando es variable no b´asica podr´ıan hacerse menos calculos). 3. Adelantando un poco, este problema cabe dentro de an´alisis post optimal pues veremos cual es nuevo ´optimo para una variaci´on dada del los parametros del problema. Claramente la incorporaci´on de este nuevo producto, como no se esta produciendo (xnuevo = 0), no viola la factibilidad del problema. Luego, s´olo tenemos que verificar la ´optimalidad: 

  −1 2 0 5 1 0 (¯ cnuevo , c¯3 , c¯4 ) = (−1, 0, 0)(−1, −3, 0)  1/2 −1/2 0   3 0 1  1/2 −3/2 1 2 0 0 = −(3, 1/2, 1/2) ≥ (0, 0) .·. La base sigue siendo ´optima. Obs: En mas de alguna parte habr´an le´ıdo que dualidad es una poderosa herramienta de an´alisis de sensibilidad y post optimal, pero sin embargo nunca la hemos usado con esos propositos. En efecto, la parte 3. de este problema es equivalente a la verificaci´on de una u ´nica condici´on dada por la restricci´on dual asociada a la nueva variable xnuevo : 5¯ y1 + 3¯ y2 + 3¯ y3 ≥ 1 y¯1 , y¯2 e y¯3 son los valores ´optimos del problema original y se determinan a partir de la soluci´on primal.

IN34A: Optimizaci´on

4.3.

Pag. 11

Problema 3 Comente acerca de la veracidad o falsedad de las siguientes aseveraciones:

1. Si un problema de programaci´on lineal es infactible su dual es necesariamente no acotado. 2. Si conozco la soluci´on ´optima de un PPL, tengo inmediatamente el valor de la funci´on objetivo ´optima del problema dual asociado sin necesidad de utilizar el teorema de holgura complementaria. 3. Si conozco los precios sombra de un problema de programaci´on lineal puedo reconstruir directamente la soluci´on (primal) de este problema. 4. El precio sombra de toda restricci´on inactiva es cero. 5. Hacer an´alisis de sensibilidad corresponde a utilizar la informaci´on dada por la resoluci´on de un PPL para ver como seri´a la nueva soluci´on si var´ıa alguno de los par´ametros del problema. Soluci´ on 1. Falso ya que el problema dual puede ser infactible. 2. Verdadero porque se tendra que el valor de la funci´on objetivo dual ´optima coincidir´a con el valor de la funci´on objetivo primal ´optima. 3. Verdadero pues el vector de precios sombras es el vector de variables duales ´optimas. Luego, puedo aplicar el teorema de holgura complementaria para recuperar la soluci´on primal. 4. Verdadero. Basta aplicar el teorema de holgura complementaria. Otra forma de verlo es a trav´es de un problema de producci´on (combinaci´on de productos): Al aumentar marginalmente la disponibilidad de un recurso sobre el cual tenemos holguras, no nos aporta ning´ un aumento de los beneficios. 5. Falso. Eso corresponder´ıa a an´alisis post optimal. An´alisis de sensibilidad estudia las condiciones que deben darse sobre los par´ametros para que la soluci´on siga siendo ´optima.