Ayudantía 07 (2)

Vista previa del material en texto

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE
ESCUELA DE ADMINISTRACIÓN
Primer Semestre 2017
Ayudantía 7 – Pauta– Simplex Geométrico
EAA251A Métodos de Optimización
7 y 8 de Junio de 2017
Profesores: Marcos Singer
Antonio Aninat
Bárbara Prieto 
Christian Villalobos
Ayudante: Martin Garcia
Mail Ayudante: mjgarcia5@uc.cl
	Ayudante Jefe Cátedra: Miguel Pérez
Ejercicio 2 (Propuesto)
En lo que sigue, se analizará la resolución de un problema de optimización con las siguientes restricciones
	Max 5x + 6y + 10z
(i) 2y + 5z ≤ 20
(ii) y ≤ 5
(iii) 5x + 6y + 10z ≤ 50
(iv) 5x + y – 5z ≤ 20
(v) x ≥ 0
(vi) y ≥ 0
(vii) z ≥ 0
cuya área factible está representada por el siguiente gráfico, donde se puede identificar los vértices A, B, C, D, E, F, G, H:
Inicialmente, utilice la información del siguiente tableau:
i) Identifique el vértice asociado al tableau. Además, encuentre los vectores dirección asociados a cada variable no-básica (todas las componentes del vector) y dibuje estos vectores. ¿Son factibles estos vectores? ¿Por qué?
Ahora, realice una iteración del Método Simplex utilizando el Criterio de Dantzig, eligiendo como variable saliente la holgura de la restricción (i) (variable h1). Elegir otra variable no da derecho a todo el puntaje
ii) Identifique el vértice asociado al nuevo tableau e indique si es o no degenerado. Justifique su respuesta.
iii) Encuentre los vectores dirección asociados a cada variable no básica y, además dibuje estos vectores. ¿Son factibles todos los vectores? En caso de no serlo, identifique cuáles vectores son factibles y cuáles no.
iv) ¿Puede usted decir si el vértice es óptimo o no con la información del tableau? Justifique claramente su respuesta
Realice nuevamente una iteración del Método Simplex utilizando el Criterio de Dantzig.
v) Identifique el vértice y compárelo con el anterior. ¿El vértice encontrado es degenerado? Justifique su respuesta.
vi) ¿Es óptimo el vértice encontrado? Justifique su respuesta
vii) En base a la información que posee de este tableau, ¿puede usted determinar el beneficio marginal de la restricción (iii) y la dimensión de la solución óptima? Justifique su respuesta. En caso que se pueda (solamente con la información del tableau), encuentre estos valores.
Ejercicio 2 (40 puntos)
a) Identifique el vértice asociado al tableau. Además, encuentre los vectores dirección asociados a cada variable no-básica (todas las componentes del vector) y dibuje estos vectores. ¿Son factibles estos vectores? ¿Por qué?
El vértice asociado al tableau es el (0, 5, 0) correspondiente al vértice A.
Las variables no básicas son x, z y h2. Sus vectores dirección asociados son:
· x: 	(1,	0,	0,	0,	0,	-5,	-5)
· z: 	(0,	0,	1,	-5,	0,	-10,	5)
· h2: 	(0,	-1,	0,	2,	1,	6,	1)
Todos los vectores son factibles puesto que es posible avanzar por ellos. De hecho, si se evalúa los test de minimización asociado a cada variable no básica x, z y h2 dan un avance de 3, 1 y 5, respectivamente.
Ahora, realice una iteración del Método Simplex utilizando el Criterio de Dantzig
b) Identifique el vértice asociado al nuevo tableau e indique si es o no degenerado. Justifique su respuesta.
El nuevo vértice asociado al tableau es el (0, 5, 2) correspondiente al vértice B. El vértice es degenerado puesto que existe una variable básica (h3) que tiene valor nulo. Esta variable, junto con las otras 3 variables no básicas, suma un total de 4 restricciones activas en el punto, para un espacio de dimensión 3.
c) Encuentre los vectores dirección asociados a cada variable no básica y, además dibuje estos vectores. ¿Son factibles todos los vectores? En caso de no serlo, identifique cuáles vectores son factibles y cuáles no.
Las variables fuera de base son x, h1 y h2. Los vectores dirección asociados son:
· x: 	(1,	0,	0,	0,	0,	-5,	-5)
· h1: 	(0,	0,	-1/5,	1,	0,	2,	-1)
· h2: 	(0,	-1,	2/5,	0,	1,	2,	3)
Tal como se puede ver en la figura, los vectores h1 y h2 son factibles. En cambio, no se puede avanzar por x. También se puede comprobar en los test de minimización. El avance por las direcciones h1 y h2 es 10 y 5. En cambio el test de minimización de x resulta cero.
d) ¿Puede usted decir si el vértice es óptimo o no con la información del tableau? Justifique claramente su respuesta
Los costos reducidos no son todos negativos, pero no es condición suficiente para decir que el punto no es óptimo, ya que es no degenerado. Esto implica que con una nueva base (dada por una iteración adicional de la solución degenerada) se podría encontrar costos reducidos que indicaran que el punto sí es óptimo.
Realice nuevamente una iteración del Método Simplex utilizando el Criterio de Dantzig.
e) Identifique el vértice y compárelo con el anterior. ¿El vértice encontrado es degenerado o no?
El vértice asociado al tableau es el (0, 5, 2) correspondiente al vértice B. Es el mismo vértice que el anterior. Es degenerado simplemente porque es el mismo vértice de la iteración anterior y éste último era degenerado.
Alternativamente, se puede decir que el vértice es degenerado puesto que existe una variable básica (x) que tiene valor nulo. Esta variable, junto con las otras 3 variables no básicas, suma un total de 4 restricciones activas en el punto, para un espacio de 
dimensión 3.
f) ¿Es óptimo el vértice encontrado? De ser así, muestre su optimalidad por KKT.
Sí, puesto que todos los costos reducidos son negativos y esto es condición suficiente para la optimalidad según el Método Simplex. Equivalentemente, se puede responder que el Método Simplex da el inverso aditivo de los precios sombra. Si los costos reducidos son negativos, entonces los precios sombra serán positivos, lo cual muestra optimalidad.
g) En base a la información que posee de este tableau, ¿puede usted determinar el beneficio marginal de la restricción (iii) y la dimensión de la solución óptima? En caso que se pueda con esta información, encuentre estos valores. Justifique su respuesta
No se puede, puesto que el análisis de sensibilidad y la dimensión de la solución óptima a través de los precios sombra sólo se puede utilizar en caso que el punto sea no-degenerado y este no es el caso.
Cualquier otra respuesta no es correcta.
500-2-200-50
0011/5-2/5002
01001005
500-2-2100
5001-30125
xh
1
h2
00000-10-50
0011/5-2/5002
01001005
100-2/5-2/51/500
0003-1-1125
50100-600-30
0051-20010
01001005
50100-61020
50-50-10115
xzh
2