Logo Studenta

Ayudantia 6 2003 (1)

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.

Otros materiales