Ayudantía 07

Vista previa del material en texto

dfPontificia Universidad Católica de Chile
Escuela de Administración
Primer Semestre 2012
EAA-251 Métodos de Optimización
Ayudantía Nº 7
 Profesores: Bárbara Prieto
 Marcos Singer
Christian Villalobos
Ayudante: M. Soledad Silva
Ejercicio 1
Maximizar m + 1,6 d
Sujeto a:
i) 3m + 4d ≤ 480
ii) m ≤ 160
iii) d ≤ 80
iv) m – 2d ≤ 0
v) m + d ≥ 30
vi) m + 4d ≤ 320
vii) m ≥ 0
viii) d ≥ 0
Responda:
a) Encuentre los vectores normales de cada restricción
b) Encuentre mediante solución gráfica el punto óptimo y su valor z, luego compruebe si se cumple la condición de KKT
c) ¿Cuál restricción conviene relajar?
d) Identifique las restricciones activas y redundantes 
e) Si ud. no conociera la existencia de las condiciones de KKT, ¿cómo calcularía el precio sombre de la restricción i)?
f) Manteniendo las restricciones del problema anterior, analice el óptimo de acuerdo a KKT de:
	
Ejercicio 2
	El gobierno, producto de lo múltiples incendios ocurridos en el parque Nacional Torres del Paine, ha decidido implementar un proyecto que tiene como objetivo reforestar 2000 hectáreas de bosque. Para esto ha llamado a una licitación donde cuatro distintas empresas ofrecerán el servicio de reforestar, por supuesto que el gobierno busca reforestar el parque al menor costo posible. Cada empresa ha ofrecido distintos planes que incluyen cuatro diferentes tipos de árboles para reforestar. La tabla muestra lo que ofrece cada empresa, los valores están expresados en hectáreas. 
	 
	Empresa 1
	Empresa 2
	Empresa 3
	Empresa 4
	Lenga
	15
	0
	5
	1
	Ñirre
	1
	5
	5
	8
	Coigüe
	2
	10
	5
	7
	Calafate
	2
	5
	5
	4
En definitiva, cada empresa ofrece un patrón de árboles a plantar, por lo que el gobierno debe combinar los patrones de cada empresa para alcanzar las 2000 há que necesita reforestar. El costo del pack ofrecido por la empresa 1 es 0,5 millones, el de la 2 es 0,85, el de la empresa tres es un 20% más caro que el de la 1 y el de la 4 es 0,7.
Adicionalmente el gobierno busca que el terreno reforestado cumpla con cierta armonía con respecto al resto del parque, por esto ha sido bien específico en que quiere al menos 200 ha de coigüe y la diferencia entre la cantidad de packs contratados por la empresa 2 y la empresa 4 deben ser al menos 10. 
Preguntas:
1. Plantee el programa primal
2. Suponga que usted sabe de antemano que la cantidad de coigües plantados será de forma óptima mayor a 200 ha, plantee el programa dual y resuelva ambos problemas.
3. Compruebe que los valores de las variables del programa dual corresponden a los precios sombra del primal.
Ejercicio 3: 
Considere el siguiente programa lineal:
Maximizar: z = – 2 x1 + x2 +2 x3 + 2 x4
Sujeto a:
i) x1 0
ii) x2 0
iii) x1 + x2 + x3 + x4 5
iv) 2 x1 + x2 + x3 – x4 7
v) x1 + x3 3
vi) x1 + 2 x2 + x3 + x4 10
Utilizando el teorema de KKT responda las siguientes preguntas
a) Es óptimo este vértice determinado por las restricciones (ii), (iii), (iv) y (v).
b) Analice el punto determinado por las restricciones (i), (ii), (iii) y (v).
	1. ¿Es óptimo este vértice?
	2. En caso de serlo, indique las coordenadas del vértice y los precios sombra de todas las restricciones.
	3. Si el vértice es óptimo. ¿Cuántas dimensiones tiene la solución óptima?
Pontificia Universidad Católica de Chile
Escuela de Administración
Primer Semestre 2012
EAA-251 Métodos de Optimización
Pauta Ayudantía Nº 8
Ejercicio 1:
a) Los vectores normales son:
	m + 1,6 d (1;1,6)
i) 3m + 4d ≤ 480 v1= (3,4) 
ii) m ≤ 160 v2=(1,0)
iii) d ≤ 80 v3=(0,1)
iv) m – 2d ≤ 0 v4=(1,-2)
v) m + d ≥ 30 v5=(-1,-1)
vi) m + 4d ≤ 320 v6=(1,4)
b) 
 
El óptimo corresponde al punto (80,60)
De acuerdo a las condiciones de KKT, las restricciones activas son la i) y vi).
Por lo tanto, se debe comprobar que:
Estos valores cumplen con las condiciones de óptimo de KKT. Adicionalmente de ser no negativos, se debe comprobar que el vértice obtenido cumpla con todas las restricciones del problema. Al usar el gráfico sabemos que estas si se están cumpliendo.
c) Dados los valore obtenidos es preferible relajar la restricción i) ya que el beneficio marginal de relajar esta restricción es mayor al de relajar la restricción vi).
d) Restricciones activas: i) y vi)
Restricciones redundantes: ii) iii) iv) y v).
e) El precio sombre corresponde al beneficio marginal de relajar la restricción en una unidad, por lo tanto deberíamos relajar la restricción i) en una unidad y ver cuál es el cambio en la función objetivo.
El óptimo era el punto (80, 60) con lo que obtenemos un z=176
Sabemos que las restricciones activas son i) y vi), por lo que ahora se calcula la nueva intersección:
De aquí se obtiene que el nuevo óptimo es el punto: (80,5; 59,875) con lo que z=176,3
f) Las restricciones que ahora vemos activas son la v) y vi)
El problema se transforma en lo siguiente:
De aquí se obtiene que: 
Nos encontramos en la situación en la que solo nos conviene relajar la restricción v), esto sucede ya que la pendiente de la función a minimizar es coincidente con la de la restricción v) por lo tanto solo obtenemos beneficios relajando esta restricción.
Ejercicio 2:
a)
Sujeto a:
i) 
ii) 
iii) 
iv) 
	b)
	 
	Sujeto a:
i) 
ii) 
iii) 
iv) 
v) 
 
Sabemos que la restricción i) del primal se cumplirá con holgura (por enunciado), estos significa que su precio sombra es 0, por lo tanto la variable , ya que los precios sombra del primal corresponden al valor de las variables del dual.	
Ahora nuestras restricciones son:
i) 
ii) 
iii) 
iv) 
v) 
Graficamos y buscamos el máximo.
De acá obtenemos que:
Por lo tanto, las restricciones activas del programa primal son la ii) y iii). Resolviendo ahora el primal:
ii) 
Se reemplaza la restricción iv) en la ii)
Dado que el valor de la empresa 1 es el menor, lo que se busca es contratar lo máximo posible de esta cumpliendo con la restricción iii):
c) El valor óptimo del primal es:
Si relajamos la restricción ii) la nueva restricción será:
Si relajamos la restricción iii)
Ejercicio 3
Programa lineal de maximización:
a) Se debe hacer un sistema de ecuaciones igualando el vector normal de la función objetivo 	con la suma ponderada de los vectores normales de las restricciones pertinentes:
(-2,1,2,2) = α(0,-1,0,0) + β(1,1,1,1) + ×(2,1,1,-1)+ δ(1,0,1,0)
	Entonces tenemos el siguiente sistema.
-2 = β +2× + δ
 1 = -α + β + ×
 2 = β + × + δ
 2 = β - ×
	Resolviendo obtenemos: α = -7, β = -2, × = -4, δ = 8
	No es óptimo ya que 3 ponderadores son negativos, lo que implica que el vector normal de z está fuera del cono formado por los vectores normales de las restricciones y por lo tanto el vértice no es óptimo. 
b) Haciendo el mismo procedimiento que en “a)”, tenemos:
 
(-2,1,2,2) = α(-1,0,0,0) + β(0,-1,0,0) + ×(1,1,1,1)+ δ(1,0,1,0)
(α, β, ×, δ) = (4,1,2,0)
1) Debido a que los ponderadores son mayores o iguales que cero ya que se cumplen todas las restricciones y desigualdades (lo que significa que la solución está dentro del poliedro factible), podemos concluir que el vértice formado por estas restricciones es óptimo.
2) Ya que se activan (i, ii, iii, v) se tiene que X1=0, X2=0, X3 + X4 = 5 y X3 < 3. Precios Sombra (ponderadores): α = 4, β = 1, × = 2, δ = 0, є = 0, = 0. Los precios є y de las restricciones iv y vi respectivamente son cero debido a que no determinan el vértice óptimo.
3) Debido a que un precio sombra de las restricciones activas es igual a cero, la solución óptima tiene una dimensión. Esto sucede porque un vector normal de las restricciones no aporta para la combinación lineal del vector normal de la función objetivo, lo que implica que el óptimo es un segmento.