Ayudantía7SimplexGeométrico_Pauta_

Vista previa del material en texto

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE
ESCUELA DE ADMINISTRACIÓN
Primer Semestre 2018
Ayudantía 7 – Simplex Geométrico
EAA251A Métodos de Optimización
6 y 7 de Junio de 2018
Profesores: Marcos Singer
Antonio Aninat
Christian Villalobos
Ayudante: Benjamin Campos
Mail Ayudante: bncampos@uc.cl
	Ayudante Jefe Cátedra: Miguel Pérez
Ejercicio 1
En lo que sigue, se analizará la resolución de un problema lineal de optimización, el cual posee el siguiente tableau inicial:
En el siguiente gráfico, se muestra los vértices y bordes del poliedro definidos por las restricciones del mismo problema:
Además, para encontrar una solución óptima se construyen la siguiente secuencia de tableaus:
Segundo tableau
Tercer tableau
Cuarto tableau
Para los apartados (i) a (iv) utilice solamente la información del gráfico y el tableau inicial:
1. Escriba el problema lineal e identifique las caras asociadas a cada restricción según los vértices que contiene cada cara (por ejemplo: asociado a la restricción …, se tiene la cara asociada a los vértices e, f y d)
1. Identifique si la solución inicial es o no degenerada. Justifique su respuesta. En , ¿siempre ocurre que una solución degenerada tiene 4 o más bordes adyacentes factibles? Justifique claramente su respuesta.
1. Señale si los vectores dirección del tableau inicial corresponden a bordes factibles o no. En cualquier caso, explicite estos vectores en el grafico y la variable asociada a la respectiva columna en el tableau.
1. Suponga que usted seguirá la dirección indicada por la Regla de Dantzig. ¿Cuál de los vértices del gráfico será el siguiente vértice del Simplex? Sin construir un nuevo tableau, determine si la nueva solución será degenerada. Justifique su respuesta en base a los conocimientos entregados en el curso.
Para los apartados (v) y (vi) utilice solamente la información del segundo tableau:
1. En otro gráfico, dibuje los vectores dirección asociados al segundo tableau e indique si estas direcciones están asociadas a bordes factibles o no.
1. Nuevamente, suponga que usted seguirá la dirección indicada por la Regla de Dantzig. Sin construir un nuevo tableau, indique cuál de los vértices del gráfico será el siguiente vértice entregado por el Método Simplex e indique si esta solución será degenerada o no.
Para los apartados (vii) y (viii) utilice solamente la información del tercer tableau.
1. ¿Cuál de los vértices del gráfico es el dado por el tercer tableau? Según la información del tableau, ¿puede usted afirmar si el vértice es óptimo o no? Justifique claramente su respuesta.
1. Verifique que los multiplicadores entregados por el tercer tableau cumplen con la condición de KKT: , donde es el multiplicador de KKT y es el vector normal asociado a la restricción activa i. Con esta nueva información, ¿puede usted afirmar si el vértice asociado es óptimo o no? Justifique su respuesta en base a los resultados fundamentales del curso.
Para el resto de los apartados, utilice toda la información disponible.
1. Compruebe la optimalidad de la solución dada por el cuarto tableau con ayuda de las Condiciones de KKT. ¿Cómo se relaciona el vértice dado por este tableau con el vértice dado por el tercer tableau? Comente.
1. Ahora que conoce toda la información, indique qué secuencia de tableaus hubiera escogido usted para llegar al tableau óptimo en el menor número de iteraciones. Indique claramente que variables entrantes y salientes de la base hubiera utilizado en cada iteración del método.
Solución:
i) 
Maximizar: z = 4x + 3y + 5z 
Sujeto a:	 4x + 5y + 4z ≤ 20			Restricción 1
	 –18x – 5y + 2z ≤ 0			Restricción 2
	 –3x + 10y + 7z ≤ 30			Restricción 3
	 x 0; y 0; z 0.
Restricción 1: cara a-b-f
Restricción 2: cara e-d-f
Restricción 3: cara b-c-d-f
Restricción x 0: cara c-d-e
Restricción y 0: cara a-f-e
Restricción z 0: cara a-b-c-e
ii) 
La solución es degenerada porque una variable básica tiene valor nulo, lo que implica que hay más de 3 restricciones activas en el vértice (definición de degenerancia). Alternativamente, se puede decir que es degenerada porque tiene más de 3 bordes adyacentes factibles. Sin embargo, esto es una condición suficiente, pero no necesaria para la degenerancia. Como contraejemplo, basta tomar una solución no-degenerada y agregarle una restricción activa pero redundante, de modo que no se generen nuevos bordes.
iii) 
Vectores:
Los vectores de las columnas x e y están asociados a bordes factibles, el vector de la columna z, no.
iv) 
La regla de Dantzig hace que la variable z entre a la base. El test de minimización tendría valor nulo, por lo que el siguiente vértice es el mismo que el inicial, igualmente degenerado (porque es el mismo vértice y la degenerancia es independiente de la representación básica del Método Simplex).
v) 
Los vectores de las columnas x e y están asociados a bordes factibles, el vector de la columna h2, no.
vi) 
La regla de Dantzig hace que la variable x entre a la base. El test de minimización tendría tiene valor 1/2 y ocurre un empate en el test de minimización, por lo que el siguiente vértice es degenerado. Como se sigue el vector dirección x, asociado al borde factible e-f, e nuevo vértice será el f.
vii) 
El vértice del tercer tableau es el vértice f. NO se puede asegurar que el vértice sea o no óptimo, puesto que es degenerado y sus costos reducidos no son todos negativos. La condición de optimalidad del simplex dice que si los costos reducidos son todos negativos, se está en un máximo del problema, pero no viceversa (es condición suficiente de optimalidad, pero no necesaria). 
viii) 
Se tiene que cumplir que:
Reemplazando los vectores dirección y los multiplicadores de KKT dados por inversos aditivos de los costos reducidos, se tiene que: 
Consistentemente con el punto anterior, no se puede afirmar que el punto sea óptimo o no, puesto que, aun cuando no se cumple KKT (que junto con la factibilidad es condición necesaria y suficiente de optimalidad), en el sistema de arriba no se está considerando todas las restricciones activas en el punto, sino solamente las que corresponden a las variables fuera de base en el tercer tableau. 
Alternativamente, se puede considerar la restricción que falta y colocarle multiplicador nulo (la variable está fuera de base por lo que su costo reducido es cero). El resultado no cambia.
ix) 
Se tiene que las siguientes restricciones son activas:
		 4x + 5y + 4z ≤ 20			
	 –18x – 5y + 2z ≤ 0			
	 –3x + 10y + 7z ≤ 30			
	 y 0
La condición de KKT se cumple si los multiplicadores en el siguiente sistema son positivos:
Utilizando los costos reducidos del cuarto tableau, se tiene ; ; ;, que cumplen con el sistema y son positivos. 
Este es el mismo vértice que el dado por el tableau anterior. Sin embargo, este tableau, a diferencia del anterior, permite concluir que el vértice f es óptimo.
x) 
Para este ejercicio particular, lo más lógico es tratar de salir de la degenerancia y llegar al tableau óptimo (cuarto tableau) asociado al vértice f por el camino más corto. Esto se logra pasando del primer al segundo tableau Esto se logra haciendo entrar la variable x a la base, de modo que salga h1. Luego debe entrar la variable z y se debe elegir h3 para que salga de la base, de modo que se tengan las mismas variables básicas que en el cuarto tableau. De este modo se llega al tableau óptimo al cabo de 3 iteraciones en vez de 4.
Ejercicio 2 (Propuesto)
Considere el siguiente espacio factible en 3 dimensiones:
 
El poliedro factible está formado por los planos OEG, EDG, DCG, CBG, BAG, AFG, FOG las no-negatividades de x, y y z. 
a) Encuentre las inecuaciones de las restricciones que conforman el poliedro factible. 
HINT: Los términos libres de las restricciones OEG, EDG, DCG, CBG, BAG, AFG, FOG son 0, 6, 12, 15, 12, 6 y 0. El termino libre en una ecuación del tipo Ax + By + Cz = D es el que noacompaña a ninguna variable, en este caso D.
b) Muestre la función objetivo suponiendo que el conjunto de soluciones óptimas tiene dimensión 2 y que el segmento DG junto con el punto (3,4,0) son parte de este conjunto. ¿Cuál es el valor de la función objetivo evaluada en el conjunto de soluciones óptimas que encontró? ¿Es única esta función objetivo? Explique su respuesta.
c) Muestre el tableau inicial.
d) Muestre el tableau siguiente, usando la regla de Danzig para avanzar.
HINT: Use el siguiente vector dirección: (0,1,0,0,-3,-4,-3,0,4,4)
e) ¿Qué vértice representa?
f) Muestre el vector dirección del borde por el que habría que avanzar para llegar al punto D. ¿Qué otros vectores dirección nacen de este tableau? ¿Hacía donde llegaría con ellos?
g) Construya el tableau correspondiente al punto D
h) ¿Cuáles son las variables básicas y no básicas en este tableau?
i) Demuestre que el punto es óptimo con KKT apoyándose en los precios sombras entregados por el tableau.
Solución:
1. R1: -4x + z ≤ 0
R2: 3y - 3x +z ≤ 6
R3: 4y + z ≤ 12
R4: 3x + 3y +z ≤ 15
R5: 4x + z ≤ 12
R6: 3x – 3y +z ≤ 6
R7: -4y + z ≤ 0
1. FO: 24y – 12x + 7z
Valor en el óptimo = 60
1. 
	-12
	24
	7
	0
	0
	0
	0
	0
	0
	0
	0
	-4
	0
	1
	1
	0
	0
	0
	0
	0
	0
	0
	-3
	3
	1
	0
	1
	0
	0
	0
	0
	0
	6
	0
	4
	1
	0
	0
	1
	0
	0
	0
	0
	12
	3
	3
	1
	0
	0
	0
	1
	0
	0
	0
	15
	4
	0
	1
	0
	0
	0
	0
	1
	0
	0
	12
	3
	-3
	1
	0
	0
	0
	0
	0
	1
	0
	6
	0
	-4
	1
	0
	0
	0
	0
	0
	0
	1
	0
1. 
	12
	0
	-1
	0
	-8
	0
	0
	0
	0
	0
	-48
	-4
	0
	1
	1
	0
	0
	0
	0
	0
	0
	0
	-1
	1
	1/3
	0
	1/3
	0
	0
	0
	0
	0
	2
	4
	0
	-1/3
	0
	-4/3
	1
	0
	0
	0
	0
	4
	6
	0
	0
	0
	-1
	0
	1
	0
	0
	0
	9
	4
	0
	1
	0
	0
	0
	0
	1
	0
	0
	12
	0
	0
	2
	0
	1
	0
	0
	0
	1
	0
	12
	-4
	0
	7/3
	0
	4/3
	0
	0
	0
	0
	1
	8
1. (0,2,0,0,0,4,9,12,12,8)
1. (1,1,0,4,0,-4,-6,-4,0,4)
1. 
	0
	0
	0
	0
	-4
	-3
	0
	0
	0
	0
	-60
	0
	0
	2/3
	1
	-4/3
	1
	0
	0
	0
	0
	4
	0
	1
	1/4
	0
	0
	¼
	0
	0
	0
	0
	3
	1
	0
	-1/12
	0
	-1/3
	¼
	0
	0
	0
	0
	1
	0
	0
	½
	0
	1
	-3/2
	1
	0
	0
	0
	3
	0
	0
	4/3
	0
	4/3
	-1
	0
	1
	0
	0
	8
	0
	0
	2
	0
	1
	0
	0
	0
	1
	0
	12
	0
	0
	2
	0
	0
	1
	0
	0
	0
	1
	12
1. Básicas: x, y, h1, h4, h5, h6, h7.
No-básicas: z, h2, h3.
1. (-12 , 24 , 7) = α * (0 , 0 , -1) + β * (-3 , 3 , 1) + µ * (0 , 4 , 1)
α = 0
β = 4
µ = 3
0-6,9600,358-0,81-24,50-3,3310,333-0,66001,620-0,0250,154,510,450-0,0580,010,50010xyzh
1
h
2
h
3
0-3,370-1,075-0,1-24,50-1013-2001,37500,0750,14,51-0,1300,175-0,10,50010xyzh
1
h
2
h
3
xyz422424abdfcexyz
xyz422424abdfcexyh
2
22
3
3
yy
zvvv
aaa
++
=
0,358
40183
36,961510
5
0
2
1
7
,
0
8
--
æöæöæöæö
ç÷ç÷ç÷ç÷
=--
ç÷ç÷ç÷ç÷
ç÷ç
-+
÷ç÷ç÷
èøèøèøèø
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
+
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
+
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
-
-
+
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
=
÷
÷
÷
ø
ö
ç
ç
ç
è
æ
0
1
0
7
10
3
2
5
18
4
5
4
5
3
4
d
g
b
a
07
,
1
=
a
0
=
b
1
,
0
=
g
3
,
3
=
d
4300004510020-18-50100-310001305427xyzh
1
h
2
h
3
xyz422424abdfce
4915,50-2,50040151-2020-9-2,500,5006027,50-3,51300010xyzh
1
h
2
h
3