examen-sem-2-2006-1

Vista previa del material en texto

EXAMEN 
INVESTIGACION OPERATIVA I 
Ingeniería Civil Industrial 
 
Profesor: Iván Santelices Malfanti. – German Sanhueza Grandón 
Fecha: Lunes 30 de julio de 2012 
 
Problema 1. 
Se desea acceder a 5 archivos (Ai) que se encuentran guardados en 10 discos (Dj): 
 
 
 
 
 
 
 
 
 
 
Donde la x en la celda (i,j) significa que el archivo Ai se encuentra en el disco Dj. El costo de los discos 
es de: 3, 5, 1, 2, 1, 4, 3, 1, 2, 2 pesos, respectivamente. Se pide: 
 
a) Formule un modelo de programación lineal que permita decidir cuales discos conviene comprar. 
b) Modifique el modelo de programación lineal si existe la obligación de comprar el disco D2 si se 
compran los discos D3 y D4. 
c) Modifique el modelo de programación lineal si hay una promoción que, al comprar los discos D3 y 
D5, el disco D2 viene de regalo. 
 
Problema 2 
Sea el siguiente Problema de Programación Lineal, cuyas variables de decisión son x1 y x2: 
 
Max Z = 5 x1 + 4 x2 
 st 
-7 x1 + 5 x2 >= 35 
7 x1 + x2 <= 0 
x1 + x2 <= 8 
- 2 x1 + x2 <= 18 
x2 >= 1 
 
a. Encuentre la(s) Soluciones Optimas utilizando el Método de la Gran M. 
b. Determine la(s) Soluciones Optimas utilizando el Método Grafico. 
c. Determine la(s) Soluciones Optimas asociadas al Problema Dual. 
d. Determine la(s) la(s) soluciones óptimas al Problema, considerando que ambas variables de 
decisión deben ser enteras. Justifique. 
e. Determine claramente el Conjunto de Soluciones Factibles para el Problema Original, en el caso 
que las variables de decisión x1 y x2 deben ser enteras. 
 
Problema 3. 
 Disco Numero 
 aD1 aD2 aD3 aD4 aD5 aD6 aD7 aD8 aD9 aD10 
A
rc
h
iv
o
 
N
u
m
er
o
 A1 x x X x x x 
A2 x x 
A3 x x x 
A4 x x x 
A5 x x X x x x x 
Una empresa fabrica los productos A, B y C y puede vender todo lo que produzca a los siguientes 
precios: A, $700; B, $3.500; C, $7.000. Producir cada unidad de A necesita 1 hora de trabajo. Producir 
una unidad de B necesita 2 horas de trabajo, más 2 unidades de A. Producir una unidad de C necesita 3 
horas de trabajo, más 1 unidad de B. Cualquier unidad de A utilizada para producir B, no puede ser 
vendida. Similarmente cualquier unidad de B utilizada para producir C, no puede ser vendida. Para este 
período de planificación están disponibles 40 horas de trabajo. 
 
Formule un modelo de programación lineal que maximice los ingresos de la empresa. 
 
Problema 4. 
Se utilizan cuatro barcos cargueros para transportar bienes de un puerto a otros cuatro puertos 
(numerados: 1, 2, 3 y 4). Se puede usar cualquier barco para hacer cualquiera de los cuatro viajes. Sin 
embargo, dadas algunas diferencias entre los barcos y las cargas, el costo total de cargar, transporte y 
descarga de bienes para las distintas combinaciones de barcos y puertos varía mucho. Estos costos (en 
miles de $) se muestran en la siguiente tabla: 
 
 
 
B
ar
co
 
 Puerto 
 1 2 3 4 
B1 50 40 60 70 
B2 60 60 70 50 
B3 70 50 70 60 
B4 50 40 60 60 
 
a) Si el objetivo es asignar los barcos a los puertos en una correspondencia uno a uno, determine la 
asignación de manera que se minimice el costo total de los cuatro barcos. 
b) Suponga, ahora, que el barco 1 está en condiciones de transportar bienes para uno o dos puertos 
distintos. Si el costo del viaje para ir de cualquier puerto a otro cualquiera es de 5 mil pesos, diseñe 
un modelo de asignación que permita solucionar esta situación (¿no se pide resolver?). 
c) Explique cómo resolvería el problema planteado en b) si existe un costo Cij para ir del puerto i al 
puerto j. (A diferencia de la pregunta b) ahora los costos de viaje entre los puertos no 
necesariamente son los mismos). 
 
 
 
 
 
- - - - - - --- O --- - - - - - - 
"La peor decisión es la indecisión". 
Benjamin Franklin (1706-1790); filósofo, físico y político estadounidense. 
 
 
 
 
 
ISM/CON.- 
 
PAUTA EXAMEN 
INVESTIGACION OPERATIVA I 
Ingeniería Civil Industrial 
 
Profesor: Iván Santelices Malfanti. – Carlos Obreque Niñez. 
Fecha: Viernes 12 de enero de 2007 
Tiempo: 100 Minutos 
 
Problema 1. 
Se desea acceder a 5 archivos (Ai) que se encuentran guardados en 10 discos (Dj)… 
 
a) Formule un modelo de programación lineal que permita decidir cuales discos conviene comprar. 
 
Variables de decisión 
Sea jx la variable que toma el valor 1 si se compra el disco Dj y el valor 0 si no se compra este disco. 
 
Minimizar Z = 
s.a. 
10987654321 2234253 xxxxxxxxxx  
 1985421  xxxxxx 
131  xx 
1752  xxx 
1863  xxx 
110976421  xxxxxxx 
6,5,4,3,2,11,0  jx j 
 
b) Modifique el modelo de programación lineal si existe la obligación de comprar el disco D2 si se 
compran los discos D3 y D4. 
 
Agregar la restricción 2
43
2
x
xx


 
 
c) Modifique el modelo de programación lineal si hay una promoción que, al comprar los discos D3 
y D5, el disco D2 viene de regalo. 
 
Agregar la restricción 2
53 1
2
x
xx


 
 
 
Problema 2 
Sea el siguiente Problema de Programación Lineal, cuyas variables de decisión son x1 y x2 … 
 
MAX 5 X1 + 4 X2 
 SUBJECT TO 
 2) - 7 X1 + 5 X2 >= 35 
 3) 7 X1 + X2 <= 0 
 4) X1 + X2 <= 8 
 5) - 2 X1 + X2 <= 18 
 6) X2 >= 1 
 END 
 FREE X1 
 
 LP OPTIMUM FOUND AT STEP 3 
 OBJECTIVE FUNCTION VALUE 
 1) 30.66667 
 
 VARIABLE VALUE REDUCED COST 
 X1 -1.333333 0.000000 
 X2 9.333333 0.000000 
 
 ROW SLACK OR SURPLUS DUAL PRICES 
 2) 21.000000 0.000000 
 3) 0.000000 0.166667 
 4) 0.000000 3.833333 
 5) 6.000000 0.000000 
 6) 8.333333 0.000000 
 
 THE TABLEAU 
 
 ROW (BASIS) X1 X2 SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 
 1 ART 0.000 0.000 0.000 0.167 3.833 0.000 0.000 30.667 
 2 X1 1.000 0.000 0.000 0.167 -0.167 0.000 0.000 -1.333 
 3 X2 0.000 1.000 0.000 -0.167 1.167 0.000 0.000 9.333 
 4 SLK 2 0.000 0.000 1.000 -2.000 7.000 0.000 0.000 21.000 
 5 SLK 5 0.000 0.000 0.000 0.500 -1.500 1.000 0.000 6.000 
 6 SLK 6 0.000 0.000 0.000 -0.167 1.167 0.000 1.000 8.333 
 
 
 
 
 
 
 
 
 
 
 
 MAX 5 X1 + 4 X2 
 SUBJECT TO 
 2) - 7 X1 + 5 X2 >= 35 
 3) 7 X1 + X2 <= 0 
 4) X1 + X2 <= 8 
 5) - 2 X1 + X2 <= 18 
 6) X2 >= 1 
 END 
 GIN 2 
 FREE X1 
 
OBJECTIVE FUNCTION VALUE 
 1) 30.00000 
 
 VARIABLE VALUE REDUCED COST 
 X1 -2.000000 -5.000000 
 X2 10.000000 -4.000000 
 
 ROW SLACK OR SURPLUS DUAL PRICES 
 2) 29.000000 0.000000 
 3) 4.000000 0.000000 
 4) 0.000000 0.000000 
 5) 4.000000 0.000000 
 6) 9.000000 0.000000 
 
 NO. ITERATIONS= 12 
 BRANCHES= 1 DETERM.= 1.000E 0 
 
 THE TABLEAU 
 
 ROW (BASIS) X1 X2 SLK 2 SLK 3 SLK 4 SLK 5 SLK 6 
 1 ART -5.000 -4.000 0.000 0.000 0.000 0.000 0.000 30.000 
 2 SLK 2 7.000 -5.000 1.000 0.000 0.000 0.000 0.000 29.000 
 3 SLK 3 7.000 1.000 0.000 1.000 0.000 0.000 0.000 4.000 
 4 ART 1.0001.000 0.000 0.000 1.000 0.000 0.000 0.000 
 5 SLK 5 -2.000 1.000 0.000 0.000 0.000 1.000 0.000 4.000 
 6 SLK 6 0.000 -1.000 0.000 0.000 0.000 0.000 1.000 9.000 
 
 
 
a. Encuentre la(s) Soluciones Optimas utilizando el Método de la Gran M. 
Notar que X2>=0; x1 s.r.s.
Sean los siguientes cambios de variables:
x1 = x1
+
 - x1
-
x2 = x2' + 1
donde x2', x1
+,
 x1
-
 >=0
x1+ x1- x2' d1 d2 h3 h4 A1 A2
-5 5 -4 0 0 0 0 0 0 4
0 0 0 0 0 0 0 1 1 0
-7 7 5 -1 0 0 0 1 0 30
-7 7 -1 0 -1 0 0 0 1 1
1 -1 1 0 0 1 0 0 0 7
-2 2 1 0 0 0 1 0 0 17
estandarizando: ?
-5 5 -4 0 0 0 0 0 0 4
14 -14 -4 1 1 0 0 0 0 -31
-7 7 5 -1 0 0 0 1 0 30 4,3
-7 7 -1 0 -1 0 0 0 1 1 0,1 ?
1 -1 1 0 0 1 0 0 0 7 -
-2 2 1 0 0 0 1 0 0 17 8,5
?
0 0 -3 2/7 0 5/7 0 0 0 - 5/7 3 2/7
0 0 -6 1 -1 0 0 0 2 -29
0 0 6 -1 1 0 0 1 -1 29 4,8 ?
-1 1 - 1/7 0 - 1/7 0 0 0 1/7 1/7 -
0 0 6/7 0 - 1/7 1 0 0 1/7 7 1/7 8,3
0 0 1 2/7 0 2/7 0 1 0 - 2/7 16 5/7 13,0
?
0 0 0 - 5/9 1 1/4 0 0 5/9 -1 1/4 19 1/6
0 0 0 0 0 0 0 1 1 0
0 0 1 - 1/6 1/6 0 0 1/6 - 1/6 4 5/6 -
-1 1 0 -0 - 1/8 0 0 0 1/8 5/6 -
0 0 0 1/7 - 2/7 1 0 - 1/7 2/7 3 21,0 ?
0 0 0 1/5 0 0 1 - 1/5 -0 10 1/2 49,0
x1+ x1- x2' d1 d2 h3 h4 A1 A2
0 0 0 0 1/6 3 5/6 0 0 - 1/6 30 2/3
0 0 0 0 0 0 0 1 1 0
0 0 1 0 - 1/6 1 1/6 0 0 1/6 8 1/3
-1 1 0 0 - 1/6 1/6 0 0 1/6 1 1/3
0 0 0 1 -2 7 0 -1 2 21
0 0 0 0 1/2 -1 1/2 1 0 - 1/2 6
Solucion Optima: Solucion Optima Dual
Z 30 2/3 Z -30 2/3
x1 -1 1/3 w1 0
x2 9 1/3 w2 0
d1 21 w3 0
d2 0 w4 1/6
h3 0 wh1 3 5/6
h4 6 wh2 0
Max Z = 5 x1 + 4 x2 
 st 
-7 x1 + 5 x2 >= 35 
7 x1 + x2 <= 0 
x1 + x2 <= 8 
- 2 x1 + x2 <= 18 
x2 >= 1 
 Max Z = 5 x1+ - 5 x1- + 4 x2’ + 4 
 st 
-7 x1+ + 7 x1- + 5 x2’ >= 30 
7 x1+ - 7 x1- + x2’ <= -1 ( -7 x1+ + 7 x1- - x2’ >= 1 ) 
x1
+
 - x1
- + x2’ <= 7 
- 2 x1+ + 2 x1- + x2’ <= 17 
x2’ + 1 >= 1 (se puede eliminar) 
x1
+
, x1
-
, x2’>= 0 
 
 
c) Determine la(s) Soluciones Optimas asociadas al Problema Dual. 
b.- Determine la(s) Soluciones Optimas utilizando el Método Grafico. 
d.- Determine la(s) la(s) soluciones óptimas al Problema, considerando que ambas variables de 
decisión deben ser enteras. Justifique. 
e.- Determine claramente el Conjunto de Soluciones Factibles para el Problema Original, en el caso 
que las variables de decisión x1 y x2 deben ser enteras. 
 
De acuerdo al grafico, se tiene: 
 
b. Solución Optima Problema Relajado: 
 X1 = - 1,33 
 X2 = 9,33 
Z = 30,33 (igual a utilizando Gran M o LINDO) 
d. Solución Optima Problema Entero: 
 X1 = - 2,00 
 X2 = 10,00 
Z = 30,00 (igual a utilizando P.Entera o LINDO) 
 
e.- El Conjunto de Soluciones Factibles estará dado por los puntos 
rojos del grafico (puntos en enteros dentro de la RSF del problema 
relajado). 
 = {(x1,x2) pertenece al Area A,B,C,D,E tal que x1, x2 enteros} 
 = { (-3;11), (-4;10), (-3;10), (-2;10), (-4;9), (-3;9), (-2;9), 
(-5;8), (-4;8), (-3;8), (-2;8), (-5;7), (-4;7), (-3;7), 
(-2;7), (-1;7), (-6;6), (-5;6), (-4;6), (-3;6), (-2;6), 
(-1;6), . . . (-8;1), (-7;1), (-6;1),(-5;1) } 
 
 
 
Problema 4. 
Se utilizan cuatro barcos cargueros para transportar bienes de un puerto a otros cuatro puertos … 
a) Si el objetivo es asignar los barcos a los puertos en una correspondencia uno a uno, determine la 
asignación de manera que se minimice el costo total de los cuatro barcos. 
Solución del problema de asignación: 
 1 2 3 4 
B1 50 40 60 70 
B2 60 60 70 50 
B3 70 50 70 60 
B4 50 40 60 60 
 
 1 2 3 4 
B1 10 0 20 30 
B2 10 10 20 0 
B3 20 0 20 10 
B4 10 0 20 20 
 
 1 2 3 4 
B1 0 0 0 30 
B2 0 10 0 0 
B3 10 0 0 10 
B4 0 0 0 20 
Solución óptima 
 1 2 3 4 
B1 50.000 
B2 50.000 
B3 70.000 
B4 40.000 
Costo total = $ 210.000 
 
b) Suponga, ahora, que el barco 1 está en condiciones de transportar bienes para uno o dos puertos 
distintos. Si el costo del viaje para ir de cualquier puerto a otro cualquiera es de 5 mil pesos, 
diseñe un modelo de asignación que permita solucionar esta situación (¿no se pide resolver?). 
La idea es duplicar el barco 1, agregar un nodo ficticio para balancear el problema. Además, darle costo 
cero a los arcos ficticios del barco1 y costo 5 a los arcos ficticios asociados a los barcos 2, 3 y 4. 
 
 
 
 1 2 3 4 F 
B1 50 40 60 70 0 
B1 50 40 60 70 0 
B2 60 60 70 50 5 
B3 70 50 70 60 5 
B4 50 40 60 60 5 
 
 1 2 3 4 F 
B1 50 40 60 70 0 
B1 50 40 60 70 0 
B2 55 55 65 45 0 
B3 65 45 65 55 0 
B4 45 45 55 55 0 
 
 1 2 3 4 F 
B1 5 0 5 25 0 
B1 5 0 5 25 0 
B2 10 15 10 0 0 
B3 20 5 10 10 0 
B4 0 5 0 10 0 
 
 1 2 3 4 F 
B1 0 0 0 20 0 
B1 0 0 0 20 0 
B2 10 20 10 0 5 
B3 15 5 5 5 0 
B4 0 5 0 10 5 
 
 1 2 3 4 F 
B1 50.000 
B1 40.000 
B2 50.000 
B3 5.000 
B4 60.000 
 
Costo total = $ 205.000 
 
 
 
 
 
 
 
 
 
 
c) Explique cómo resolvería el problema planteado en b) si existe un costo Cij para ir del puerto i al 
puerto j. (A diferencia de la pregunta b) ahora los costos de viaje entre los puertos no 
necesariamente son los mismos). 
La idea es formular un modelo de transbordo para resolver mediante el algoritmo de transporte. 
 
 
 
 
 
Problema 3. Una empresa fabrica los productos A, B y C y puede vender todo lo que produzca … 
 
Formule un modelo de programación lineal que maximice los ingresos de la empresa. 
Variables de Decisión: 
1Ax Unidades del producto A producidas y vendidas 
2Ax Unidades del producto A producidas y utilizadas para producir el producto B 
1Bx Unidades del producto B producidas y vendidas 
2Bx Unidades del producto B producidas y utilizadas para producir el producto C 
Cx Unidades del producto C producidas y vendidas 
 
Maximizar Z = 
s.a. 
CBA xxx 000.7500.3700 11  
   4032 2121  CBBAA xxxxx 
221 )(2 ABB xxx  
2BC xx  
0,,,, 2121 CBBAA xxxxx