Logo Studenta

Ayudantía 07

Vista previa del material en texto

PONTIFICIA UNIVERSIDAD CATÓLICA DE CHILE
ESCUELA DE ADMINISTRACIÓN
Primer Semestre 2017
Ayudantía 7 – 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 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.
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.
4915,50-2,50040151-2020-9-2,500,5006027,50-3,51300010xyzh
1
h
2
h
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
50100-600-30
0051-20010
01001005
50100-61020
50-50-10115
4300004510020-18-50100-310001305427xyzh
1
h
2
h
3
xyz422424abdfce

Otros materiales

Materiales relacionados