Ayudantía 07

Vista previa del material en texto

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE
ESCUELA DE ADMINISTRACIÓN
Segundo Semestre 2014
Ayudantía 7 – Tableau y KKT
EAA-251 Métodos de Optimización
05 de Noviembre de 2014
Profesores: Pascuala Domínguez 
Bárbara Prieto
Marcos Singer
Christian Villalobos
Ayudante: Pascale Cazabón
	Ayudante Jefe: Raimundo Gana
EJERCICIO 1
Considere el siguiente programa lineal: 
Maximizar: z = x – 2 y + 3 z + w
Sujeto a: 
i) 
x – 2 y + z + 3 w 8
ii) 
2x + 3 y - z + 2 w 5
iii) 
x + y - 3 z + 4 w 6
iv) 
x 0; y 0; z 0 ; w 0
a) Encuentre el punto óptimo y el valor de la función objetivo mediante el método Simplex, ocupando la regla de Dantzig para seleccionar la variable entrante. ¿Cuáles son los precios sombra en el óptimo de cada una de las restricciones? Demuestre con KKT que esos valores son los precios sombra de las restricciones activas.
b) Exprese el punto a representado por el primer tableau como vector de siete componentes e indique la dirección del borde b que hace crecer la variable x. 
c) ¿Cuál es el beneficio de relajar la restricción (iii) en el óptimo? 
d) ¿Cómo cambia el valor de la función objetivo si la restricción (i) es: 
 x – 2 y + z + 3 w 6
e) El borde que lleva del segundo al tercer tableau, ¿es paralelo, se aleja o se acerca de la restricción (iii)? 
PAUTA EJERCICIO 1
a) 
	
	X
	y
	z
	w
	H1
	H2
	H3
	F.O.
	
	1
	-2
	3
	1
	0
	0
	0
	0
	H1
	1
	-2
	1
	3
	1
	0
	0
	8
	H2
	2
	3
	-1
	2
	0
	1
	0
	5
	H3
	1
	1
	-3
	4
	0
	0
	1
	6
 
	
	X
	y
	z
	w
	H1
	H2
	H3
	F.O.
	
	-2
	4
	0
	-8
	-3
	0
	0
	-24
	Z
	1
	-2
	1
	3
	1
	0
	0
	8
	H2
	3
	1
	0
	5
	1
	1
	0
	13
	H3
	4
	-5
	0
	13
	3
	0
	1
	30
	
	X
	y
	z
	w
	H1
	H2
	H3
	F.O
	
	-14
	0
	0
	-28
	-7
	-4
	0
	-76
	Z
	7
	0
	1
	13
	3
	2
	0
	34
	Y
	3
	1
	0
	5
	1
	1
	0
	13
	H3
	19
	0
	0
	38
	8
	5
	1
	95
Pto. Óptimo = ( 0, 13, 34, 0, 0, 0, 95) 
Valor Función objetivo en el óptimo = 76
Precios Sombra: 
Restricciones activas: i) = 7
 ii) = 4
 “x 0” = 14
 “w 0” = 28
DEMOSTRAR CON KKT
Restricciones NO activas : “y 0” = 0
“z 0” = 0
restricción iii) = 0
b) 
 = ( 0, 0, 0, 0, 8, 5, 6 )
 = ( 1, 0, 0, 0, -1, -2, -1) (este es el borde a partir del tableau de a). Eventualmente alguien podría haber calculado el borde que hace crecer x a partir del tableau óptimo (no estaría malo…la pregunta no queda tan clara)
c) El beneficio de relajar una restricción corresponde al precio sombra de ésta. En este caso, la restricción iii) NO es activa en el óptimo ( holgura 3 = 95), por lo tanto el precio sombra es igual a cero. Es decir, el beneficio marginal de relajar esta restricción es cero.
d) 
El hecho de que la restricción i) pase de: x – 2 y + z + 3 w 8 a: x – 2 y + z + 3 w 6, quiere decir que la restricción se CONTRAE en 2 unidades, es decir, se hace cada vez más restrictiva. Como el precio sombra de i) es 7, al restringirla en 2 unidades, la función objetivo disminuye en 7*2=14. Por lo tanto quedaría con un valor final de 76 – 14 = 62.
e) El vector borde que me lleva del segundo al tercer tableau es: (0, 1, 2, 0, 0, -1, 5). Vemos que el coeficiente de la restricción iii) es 5, positivo, por lo tanto al movernos por este borde la holgura con respecto a esta restricción está amentando, por lo tanto nos estamos ALEJANDO de la restricción.
EJERCICIO 2
El siguiente tableau representa un vértice del poliedro factible de un problema de optimización:
a) Determine la modelación lineal de este problema de optimización
b) Usando el método simplex, encuentre la solución óptima del problema y el valor de la función objetivo en dicho óptimo
c) Señale los vectores que representan los bordes adyacentes al vértice óptimo
d) A través del tableau simplex óptimo, determine el precio sombra de TODAS las restricciones del problema y demuestre que dichos precios sombras son los correctos utilizando el teorema de KKT
PAUTA EJERCICIO 2
a) Haciendo pívot de reversa, se llega a :
Del tableau se deriva la siguiente modelación
Maximizar 3x + 2y
Sujeto a:
i) 4x + 2y ≤ 80
ii) 2x + 2y ≤ 50
iii) x + 2y ≤ 45
iv) x – 4y ≤ 0
v) x ≤ 40
vi) y ≤ 40
vii) x ≥0
viii) y ≥ 0
b) Óptimo: (15, 10). Función objetivo = 65
c) Bordes: (-0,5; 0,5; 1; 0; -0,5; 2,5; 0,5; -0,5) y (0,5; -1; 0; 1; 1,5; -4,5; -0,5; 1)
d) Precios sombra de restricciones iii, iv, v y vi y las de no negatividad son cero, ya que no son activas.
Restricciones (i) y (ii) tienen precios sombra de 0,5 (demostrarlo con KKT)
EJERCICIO 3 (PROPUESTO)
La Ilustración muestra los tres primeros tableaus de un problema de maximización.
a) ¿Cuántas restricciones (aparte de las de no negatividad) tiene este problema?
b) ¿Qué punto representa el segundo Tableau?
c) ¿Cuál es la variable saliente de la segunda iteración? (la que lleva del segundo a tercer tableau)
d) ¿Qué restricciones determinan el borde que se elige en la segunda iteración? 
e) ¿A qué vértice se llega después de la segunda iteración? (Vértice del tercer tableau) ¿Cuál es el vector-dirección de cada uno de los bordes que nacen del vértice?
f) Eligiendo el menor costo reducido encuentre el siguiente tableau. ¿Es óptima la solución encontrada?
g) Indique si algún tableau representa un punto degenerado, y de ser así, indique el vértice y las restricciones que lo determinan.
PAUTA EJERCICIO 3
a) Cuatro restricciones.
b) El punto (0, 0, 0, 12, 12, 0, 0).
c) h3.
d) La restricción de no negatividad de x1 y la cuarta restricción del problema original.
e) Se llega al vértice (0, 0, 0, 12, 12, 0, 0). El vector-dirección de cada uno de los bordes es:
· x1: (1, 1, 2, -4, -4, 0, 0)
· h3: (0, -1, -2, 2, 4, 1, 0)
· h4: (0, 1/2, 0, 0, -1, 0, 1)
f) La Ilustración muestra el siguiente tableau.
La variable entrante es h4 y la variable saliente es h2. El vértice es el punto (0, 6, 0, 12, 0, 0, 12), pero no es óptimo, ya que hay dos bordes promisorios que se podrían elegir: x1 ó h3.
g) Los tres primeros tableaus muestran un punto degenerado, el punto (0, 0, 0, 12, 12, 0, 0), porque hay 5 restricciones activas y el problema original tiene sólo tres variables. En los tres tableaus este vértice está determinado por las restricciones de no-negatividad de x1, x2 y x3, y por las restricciones 3 y 4.
En el tableau encontrado en (f) el vértice es el punto (0, 6, 0, 12, 0, 0, 12) que está determinado por las restricciones de no-negatividad de x1 y x3, y por las restricciones 2 y 3, por lo que también es un punto degenerado.
³
a
r
b
r
0
14
0
0
0
-3
0
0
0
0
18
1
0
0
-4
0
0
80
0
10
0
1
0
-2
0
0
50
0
6
0
0
1
-1
0
0
45
1
-4
0
0
0
1
0
0
0
0
4
0
0
0
-1
1
0
40
0
1
0
0
0
0
0
1
40
3
2
0
0
0
0
0
0
0
4
2
1
0
0
0
0
0
80
2
2
0
1
0
0
0
0
50
1
2
0
0
1
0
0
0
45
1
-4
0
0
0
1
0
0
0
1
0
0
0
0
0
1
0
40
0
1
0
0
0
0
0
1
40
0
14
0
0
0
-3
0
0
0
0
18
1
0
0
-4
0
0
80
0
10
0
1
0
-2
0
0
50
0
6
0
0
1
-1
0
0
45
1
-4
0
0
0
1
0
0
0
0
4
0
0
0
-1
1
0
40
0
1
0
0
0
0
0
1
40
0
0
-0,78
0
0
0,11
0
0
-62,22
0
1
0,06
0
0
-0,22
0
0
4,44
0
0
-0,56
1
0
0,22
0
0
5,56
0
0
-0,33
0
1
0,33
0
0
18,33
1
0
0,22
0
0
0,11
0
0
17,78
0
0
-0,22
0
0
-0,11
1
0
22,22
0
0
-0,06
0
0
0,22
0
1
35,56
0
0
-0,5
-0,5
0
0
0
0
-65
0
1
-0,5
1,0
0
0
0
0
10
0
0
-2,5
4,5
0
1
0
0
25
0
0
0,5
-1,5
1
0
0
0
10
1
0
0,5
-0,5
0
0
0
0
15
0
0
-0,5
0,5
0
0
1
0
25
0
0
0,5
-1,0
0
0
0
1
30
16
16
2
0
0
0
2
0
1
1
0
12
0
2
1
0
1
12
-
2
0
1
0
0
0
0
0
0
0
0
0
1
0
0
-
2
1
0
0
0
0
1
16
20
0
0
0
0
2
2
0
1
0
12
0
4
0
0
1
12
-
1
10
0
0
0
0
0
-
2
0
-
1
0
-
1
1
-
0,5
0
-
2
1
0
0
0
0
1
36
0
0
0
0
0
4
0
0
1
0
12
4
0
0
0
1
12
-
1
1
0
0
0
0
-
20
8
-
2
0
-
4
1
1
-
0,5
-
2
0
1
0
0
0
2
0
h
1
h
4
x
2
x
1
h
1
h
2
h
3
h
4
x
2
x
3
x
3
4
0
0
0
-
8
-
96
4
0
0
1
0
12
4
0
0
0
1
12
1
1
0
0
0,5
0
12
0
-
2
0
-
4
1
-
1
0
-
2
0
1
0
0
0
2
0
£