Descarga la aplicación para disfrutar aún más
Vista previa del material en texto
1 Pontificia Universidad Católica de Chile Escuela de Administración EAA-251 Métodos de Optimización AYUDANTÍA Nº6 Profesores: Marcos Singer Francisco Poblete 1) Una cadena de tiendas evalúa sus sucursales con tres índices: ventas por empleado, calidad de servicio (evaluado del 1 al 8) y la ubicación de la tienda (evaluada del de 1 al 10, siendo 1 la mejor ubicada). Se desea comparar el desempeño de las cuatro tiendas de acuerdo con la información de la Tabla 1. Tabla 1: Desempeño de las Tiendas. Índices T1 T2 T3 T4 Ventas por empleado 5 2 7 6 Calidad de atención 6 5/2 5 8 Ubicación 3 7 6 2 a) ¿Qué tienda presenta el mejor desempeño? b) ¿Qué ente geométrico representa el conjunto de todas las combinaciones lineales posibles de los vectores T1, T3 y T4? ¿Cómo cambia su respuesta si se exige que los ponderadores sean siempre positivos? c) Exprese el plano que contiene a T1, T3 y T4 de la forma: a + δb + µc, en donde a, b y c son vectores en tanto δ y µ son escalares. d) Exprese el plano que contiene a T1, T3 y T4 de la forma: Ax + By + Cz = D, en donde A, B y C son escalares. e) Muestre ponderadores α, β y γ de una función lineal de evaluación del desempeño de los índices x, y, z, para los cuales las tiendas 1, 3 y 4 tendrían la misma evaluación. 2) Dado el siguiente problema de optimización: Maximizar: z = w + t Sujeto a: i) w ≥ 5 ii) t – w ≤ 15 iii) 3t – w ≤ 55 iv) 2w + t ≤ 65 v) t ≥ 0 vi) w + t ≥15 2 a) Encuentre los vectores normales de cada restricción. b) Encuentre mediante solución gráfica el punto óptimo y su valor z. Compruebe mediante KKT. c) Identifique las restricciones activas y redundantes. d) Calcule gráficamente el precio sombra de la primera y sexta restricción y compruebe su resultado mediante el teorema de KKT. e) Muestre gráficamente y mediante KKT la solución óptima si la función objetivo fuera minimizar: z = w + t 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 precio sombra de todas las restricciones. 3) Si el vértice es óptimo. ¿Cuántas dimensiones tiene la solución óptima? c) Si el vector normal del hiperplano optimizador coincide con el vector normal de la restricción (ii). ¿Cuántas dimensiones tendrá la faceta óptima? d) Si el óptimo del problema se pudiese describir mediante la expresión dcba rrrr 321 λλλ +++ donde dcba rrrr ,,, son vectores linealmente independientes y los ponderadores toman los valores entre los rangos 1725 1 ≤≤− λ , 343 2 ≤≤λ , 209 3 ≤≤− λ . ¿Cuántos precios sombra igual a cero tendrá el problema? Justifique claramente su respuesta 3 Pontificia Universidad Católica de Chile Escuela de Administración EAA-251 Métodos de Optimización AYUDANTÍA Nº6 Profesores: Marcos Singer Francisco Poblete 1) Los vectores de desempeño se construyen asignando el número mayor a el mejor desempeño, por lo tanto es necesario modificar los números de la “Ubicación” para poder realizar un análisis DEA. a) No podemos saber qué tienda presenta mejor desempeño entre T1, T3 y T4 porque ninguna presenta mejor evaluación que las otras dos en cada uno de los índices, por lo tanto, no podemos medir a simple vista cuál presenta mejor desempeño. Lo que si podemos afirmar es que T2, es la que tiene peor desempeño ya que es superado por las otras tiendas en todas las dimensiones consideradas al evaluar el desempeño. b) Se genera todo el espacio, pues los vectores son linealmente independientes, y no se está restringiendo el valor de los ponderadores. Si los ponderadores deben ser todos positivos entonces se genera el cono, que se muestra en el gráfico, que tiene como bordes los tres vectores correspondientes. 6 x y z 8 6 4 2 2 4 8 2 4 6 8 t4 t2 t3 t1 Índices T1 T2 T3 T4 Ventas por empleado 5 2 7 6 Calidad de atención 6 5/2 5 8 Ubicación 10 – 3 = 7 10 – 7 = 3 10 – 6 = 4 10 – 2 = 8 4 c) Una forma vectorial posible es : (5, 6, 7) + δ [ (7, 5, 4) - (5, 6, 7) ] + µ [ (6, 8, 8) - (5, 6, 7) ] = (5, 6, 7) + δ (2, -1, -3) + µ (1, 2, 1) La forma vectorial puede ser distinta dependiendo del vector posición que se elija. d) Para la forma general se debe resolver el siguiente sistema de ecuaciones x = 5 + 2δ + µ y = 6 - δ + 2µ z = 7 - 3δ + µ resolviéndolo obtenemos x – y + z = 5. e) Los ponderadores son los valores A, B, C obtenidos en la letra d), es decir 1, -1, 1. Si los tres vectores se ponderan por estos factores se obtiene la misma mediada de desempeño que es igual a 5. 2) Problema de optimización a) i) w ≥ 5 ⇒ -w ≤ -5 ⇒ v1 = ( -1, 0 ) ii) t – w ≤ 15 ⇒ v2 = ( -1, 1 ) iii) 3t – w ≤ 55 ⇒ v3 = ( -1, 3 ) iv) 2w + t ≤ 65 ⇒ v4 = ( 2, 1) v) t ≥ 0 ⇒ v5 = ( 0, -1) vi) w + t ≥15 ⇒ -w – t ≤ -15 ⇒ v6 = ( -1, -1) Es necesario que las desigualdades sean del tipo “≤ “, pues, de esta manera los vectores normales apuntan hacia fuera del poliedro factible. b) 10 10 t w 20 30 40 50 20 30 40 a i ii iii iv v vi 5 El óptimo se encuentra en la intersección de (iii) con (iv), el punto óptimo es (20, 25 ) y z = 45 Con KKT: α(-1, 3) + β(2, 1) = (1, 1) Resolviendo el siguiente sistema se obtiene α = 1/8 y β = 4/7. El punto es óptimo ya que α y β son positivos. -α + 2β = 1 3α + β = 1 c) Las restricciones (iii) y (iv) son activas y la (ii) es redundante. d) Al relajar las restricciones (i) y (vi) el área factible aumenta, pero al no ser activas, su precio sombra es cero. Con KKT: (1, 1) = α (-1, 0) + β (-1, -1) Resolviendo el sistema -α - β = 1 - β = 1 Se obtiene α = 0, β = -1, lo que implica que la normal a los planos optimizadores no se encuentra comprendida en el cono formado por la normal de las restricciones ( para que ocurra esto último, según KKT, se debe cumplir necesariamente α, β ≥ 0 ) a) 10 10 t w 20 30 40 50 20 30 40 i ii iii iv v vi 6 Para poder utilizar KKT es necesario transformar la minimización en una maximización. Por lo tanto se tiene: Maximizar: z = - x – y Resolviendo el siguiente sistema (-1, -1) = α (-1, 0) + β (-1, -1) -α - β = -1 - β = -1 Se obtiene β = 1 α = 0 Esto quiere decir que la normal a la función objetivo no tiene componente en la normal de la restricción (i) y por lo tanto es exactamente igual a la normal de la restricción (vi). Esto es, la función objetivo es coincidente con la restricción (vi), por lo tanto, la solución óptima será la arista señalada en el gráfico. 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. 7 b) Haciendo el mismo procedimiento que en “a)”, obtenemos (α, β, χ, δ) = (4,1,2,0) 1) Debido a que los ponderadores son mayoreso iguales que cero y a 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) Coordenadas del vértice: (x1, x2, x3, x4) = (0,0,3,2). Estas se obtienen resolviendo las restricciones que conforman el vértice (i, ii, iii y v). 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 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. c) Tendrá tres dimensiones. Esto se debe a que el hiperplano optimizador es paralelo al hiperplano de la restricción (ii). Lo que implica que la faceta óptima tiene las mismas dimensiones que el hiperplano de la restricción. El problema está definido en un hiperespacio de 4-D. Si se cumple la restricción (ii) obtenemos un hiperplano de 3- D. Que el vector normal a la función objetivo sea paralelo al de la restricción (ii), quiere decir que la función objetivo es paralela a la restricción 2 y por lo tanto seguiremos estando en 3-D d) Esto significa que el óptimo del problema se puede describir como un hiperplano compuesto por un vector posición más la combinación líneal de otros 3 vectores cuyos ponderadores varían en un rango determinado. Entonces se describe como un hiperplano. Y si este es el caso entonces el hiperplano optimizador se maximiza en un óptimo que tiene las mismas dimensiones que el hiperplano (3 dimensiones), lo que implica que tres precios sombra deberían ser iguales a cero.
Compartir