2-2

Vista previa del material en texto

Certamen 2 
INVESTIGACION OPERATIVA (430088) 
Ingeniería Civil 
 
Profesor: Carlos Obreque Niñez Fecha: Lunes 14 de julio de 2008 
 
Problema 1 (25 puntos) Una compañía produce tres tamaños de tubos: A, B y C, que son vendidos, 
respectivamente en 10 unidades monetarias (u.m), 12 u.m. y 9 u.m. por pie. Para fabricar cada pie del tubo A se 
requieren 30 segundos de tiempo de procesamiento en un tipo particular de máquina de modelado. Cada pie del 
tubo B requiere 27 segundos y cada pie del tubo C requiere 36 segundos. Después de la producción, cada pie de 
tubo, sin importar de qué tipo, requiere 25 gramos de material para soldar. El costo de producción total se estima 
en 3 u.m., 4 u.m. y 4 u.m. por pie de los tubos A, B y C respectivamente. 
Para la siguiente semana, la compañía ha recibido pedidos excepcionalmente grandes que totalizan 2000 pies del 
tubo A, 4000 pies del tubo B y 5000 pies del tubo C. Como sólo se dispone de 40 horas de tiempo de máquina 
esta semana y sólo se tienen en inventario 138 kg de material de soldar, el departamento de producción no podrá 
satisfacer esta demanda, que requiere un total de 97 horas de tiempo de máquina y 275 kg de material de soldar. 
No se espera que continúe este alto nivel de demanda. En lugar de expandir la capacidad de las instalaciones de 
producción, la gerencia está considerando la compra de algunos de estos tubos a proveedores de Japón a un costo 
de entrega de 6 u.m. por pie del tubo A, 6 u.m. por pie del tubo B y 7 u.m. por pie del tubo C. No obstante, los 
proveedores están dispuestos a satisfacer todo el pedido que les hagan siempre y cuando la longitud del tubo A 
sea a lo más el doble de la suma de los tubos B y C. 
Construya el modelo que permita hacer recomendaciones respecto a la cantidad de producción de cada tipo de 
tubo, y la cantidad de compra a Japón, para satisfacer la demanda y maximizar las ganancias de la compañía. 
 
Problema 2 (25 puntos) Considere el siguiente modelo de programación lineal: 
 
=Z Maximizar 
s.a. 
321 542 xxx ++ 
 140823 321 ≤++ xxx 
13074 321 ≤++ xxx 
0,0,0 321 ≥≥≥ xxx 
Considerando que las variables de holgura para la primera y segunda restricción son y , respectivamente y 
sabiendo que la tabla óptima viene dada por: 
4x 5x
 
1x 2x 3x 4x 5x b 
Z 4 0 11 2 0 280 
2x 3/2 1 4 1/2 0 70 
5x 5/2 0 3 -1/2 1 60 
 
 
 
 
 
Responda las siguientes preguntas de manera independiente: 
 
a) Suponga que el costo asociado a la variable 1x es 3 y el costo de 2x es 2. Determine la nueva solución 
óptima. 
b) Si el recurso de la primera restricción aumenta en una unidad, en cuánto aumenta o disminuye el valor de la 
función objetivo?. Justifique su respuesta. 
c) Determine la nueva solución óptima si se agrega la restricción 5023 321 ≤++ xxx al problema de 
programación lineal dado. 
d) Escriba el problema dual y determine su solución óptima. 
 
 
 
Problema 3 (25 puntos) Una cierta compañía puede producir su principal artículo en dos departamentos 
diferentes. Cada departamento puede enviar lo producido al centro de control de calidad final A o al centro de 
control de calidad final B, desde los cuales se remite a cualquiera de las cuatro líneas del empaque y envío de 
que dispone la empresa. El departamento 1 tiene capacidad para producir 80 unidades por hora y el departamento 
2 para producir máximo 60 unidades por hora. Según las demandas esperadas, se ha programado que las líneas 
de empaque atiendan al menos las siguientes cantidades por hora: 30, 20, 40, 40 respectivamente. 
 
La siguiente tabla muestra los tiempos promedio (minutos) que se gasta en los diferentes movimientos de cada 
unidad del producto. 
 
DEPARTAMENTO LINEA DE EMPAQUE Y ENVÍO 
P1 P2 
CONTROL DE 
CALIDAD L1 L2 L3 L4 
10 12 C1 24 – 22 – 
9 11 C2 19 23 20 23 
 
El centro 1 de control de calidad, se demora 4 minutos para revisar un artículo y el centro 2 de control de calidad 
se demora 6 minutos. 
 
Considerando que ambos centros de control de calidad tiene capacidad ilimitada de almacenamiento. 
 
a) ¿Cómo debe organizarse el flujo de las unidades entre los departamentos productivos y las líneas de 
empaque y envío, pasando por algunos de los centros de control de calidad, de tal forma que se obtenga un 
mínimo tiempo total de producción? 
b) Suponiendo que el centro de control de calidad 2 puede atender como máximo 100 unidades, ¿qué 
modificaciones se deben realizar en la tabla de transporte para encontrar la nueva solución óptima?. Asuma 
que se conoce la solución óptima de la parte (a). No se pide resolver. Justifique su respuesta. 
 
 
Problema 4 (25 puntos) Un grupo de 6 hombres y 6 mujeres vive en una isla. Cada uno de los 6 hombres 
“corteja" a una de las 6 mujeres. Al cabo de un cierto tiempo se decide realizar una gran ceremonia durante la 
cual se casarán 6 parejas. Cada una de las mujeres tiene una lista con los nombres de los 6 hombres y en ella 
registra sus preferencias en una escala de 1 a 6, pudiendo eliminar los nombres correspondientes a los hombres 
que no son de su agrado. La tabla siguiente da las “calificaciones" otorgadas por cada mujer a cada hombre. 
 
 Hombre 
Mujer 1 2 3 4 5 6 
1 3 – 2 5 6 4 
2 4 4 3 – 5 – 
3 2 4 – 5 3 6 
4 4 5 6 – 2 3 
5 4 5 2 5 3 – 
6 5 2 3 1 4 6 
 
Si se supone que una medida válida de la felicidad conyugal en la isla viene dada por la suma de los números 
asignados: 
 
a) ¿Cuál es la asignación que maximiza la felicidad total de los isleños? 
b) El hombre designado con el número 5 asegura que puede aumentar el grado de felicidad conyugal en la isla 
si se le permite casarse con dos mujeres. ¿Cree Ud. que se lo permitirán los isleños?. Justifique su respuesta. 
c) Suponga que en la ceremonia sólo se casarán cuatro parejas. Construya la tabla de asignación apropiada que 
permita seleccionar a las cuatro parejas afortunadas. 
 
 
 
Tiempo: 2 horas 
 
 
Problema 1 
 
Variables de decisión 
 
Ax = cantidad del tubo A a producir 
Bx = cantidad del tubo B a producir 
Cx = cantidad del tubo C a producir 
Ay = cantidad del tubo A a comprar 
By = cantidad del tubo B a comprar 
Cy = cantidad del tubo C a comprar 
 
Maximizar =Z 
s.a. 
CBACBACCBBAA yyyxxxyxyxyx 766443)(9)(12)(10 −−−−−−+++++ 
 2000≥+ AA yx 
4000≥+ BB yx 
5000≥+ CC yx 
144000362730 ≤++ CBA xxx 
138000)(25 ≤++ CBA xxx 
)(2 CBA yyy +≤ 
0,,,,, ≥CCBBAA yxyxyx 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Problema 2 
=Z Maximizar 
s.a. 
321 542 xxx ++ 
 140823 321 ≤++ xxx 
13074 321 ≤++ xxx 
0,0,0 321 ≥≥≥ xxx 
 
 1x 2x 3x 4x 5x b 
Z -2 -4 -5 0 0 0 
4x 3 2 8 1 0 140 
5x 4 1 7 0 1 130 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
a) Se reemplaza la función objetivo original por la nueva función: 321 523 xxx ++ 
 
 
 
 
 
 
 
 
 
 
 
 
 
b) Si el recurso de la primera restricción aumenta en una unidad entonces 1411140111 =+=∇+= bbb , en tal 
caso el valor de la función objetivo aumenta en 2 unidades, pues el costo reducido asociado a la variable de 
holgura de la primera restricción 4x es 2. Otra forma es determinar el valor de la nueva solución y 
reemplazarla en la función objetivo. 
 
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−
=−
1
0
2
1
2
1
1B , , ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
=⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
=
5
2
2
1
x
x
x
x
x
B
B
B ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
=
130
141
b 
bBxB
vv 1−= ⇒ ⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
=⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
−
=⎟⎟
⎠
⎞
⎜⎜
⎝
⎛
2
119
2
141
2
1
2
1
130
141
1
0
2
1
B
B
x
x
v
v
 ,⇒ 0*1 =x 2141
*
2 =x y 0
*
3 =x ⇒ 282
* =Z
 
Luego, la función objetivo aumenta en 2 unidades 
 
 1x 2x 3x 4x 5x b 
Z -1/8 -11/4 0 5/8 0 175/2 
3x 3/8 1/4 1 1/8 0 35/2 
5x 11/8 -3/4 0 -7/8 1 15/2 
 1x 2x 3x 4x 5x b 
Z 4 0 11 2 0 280 
2x 3/2 1 4 1/2 0 70 
5x 5/2 0 3 -1/2 1 60 
 1x 2x 3x 4x 5x b 
Z -3 -2 -5 0 0 0 
2x 3/2 1 4 1/2 0 70 
5x 5/2 0 3 -1/2 1 60 
 1x 2x 3x 4x 5x b 
Z 0 0 3 1 0 140 
2x 3/21 4 1/2 0 70 
5x 5/2 0 3 -1/2 1 60 
 
c) Claramente la solución óptima: 0*1 =x , 70
*
2 =x y 0
*
3 =x no satisface la restricción 
 5023 321 ≤++ xxx
 
 1x 2x 3x 4x 5x 6x b 
Z 4 0 11 2 0 0 280 
2x 3/2 1 4 1/2 0 0 70 
5x 5/2 0 3 -1/2 1 0 60 
6x 3 1 2 0 0 1 50 
 
 
 
 
 
 
 
 1x 2x 3x 4x 5x 6x b 
Z 4 0 11 2 0 0 280 
2x 3/2 1 4 1/2 0 0 70 
5x 5/2 0 3 -1/2 1 0 60 
6x 3/2 0 -2 -1/2 0 1 -20 
 
 
 
 
 
 
 
 1x 2x 3x 4x 5x 6x b 
Z 10 0 3 0 0 4 200 
2x 3 1 2 0 0 1 50 
5x 1 0 5 0 1 -1 80 
4x -3 0 4 1 0 -2 40 
 
 
 
 
 
 
 
0*1 =x , , , , y con 50
*
2 =x 0
*
3 =x 40
*
4 =x 80
*
5 =x 0
*
6 =x 200
* =Z
 
d) 
=Z Maximizar 
s.a. 
321 542 xxx ++ 
 140823 321 ≤++ xxx 
13074 321 ≤++ xxx 
0,0,0 321 ≥≥≥ xxx 
1y 
2y 
 
Dual 
=WMinimizar
s.a. 
21 130140 yy + 
 243 21 ≥+ yy 
42 21 ≥+ yy 
578 21 ≥+ yy 
01 ≥y , 02 ≥y
 
2*1 =y , , 0
*
2 =y 280
* =W
 
 
 
 
 
Problema 3 
 
Para una mejor comprensión del problema se propone elaborar un grafo en el cual los nodos P1 y P2 representan los 
departamentos de producción, los nodos C1 y C2 representan los Centros de Control de Calidad y los nodos del L1 al L4 
representan las cuatro líneas de empaque. 
 
 
L4
22
L1
L2
12 
9 
10 
11 
23
20
23
19
C2
 6
24
 4
C1
P2 
P1 
L3
–30 
 +80 
 
 –20 
 +60 
–40 
 
 
 –40 
 
Se observa que la oferta total es 140 entre los dos departamentos de producción, mientas que la demanda total de las cuatro 
líneas de empaque es de 130, por lo que se debe agregar un nodo ficticio a la demanda, para balancear el problema y 
equilibrar este exceso de producción. Además, los tiempos que demoran los centros de control de calidad en revisar las 
unidades (4 min en C1 y 6 min en C2) se pueden sumar a los tiempos que se gastan en mover las unidades desde los 
departamentos de producción a los centros de control de calidad o desde éstos a las líneas de empaque. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Obtención de una solución básica factible inicial con el Método de Vogel: 
 
 C1 C2 L1 L2 L3 L4 F Oferta ui 
 14 15 M M M M 0 
P1 0 80 M-34 M-38 M-35 M-38 2 
 
80 
 
15 
 16 17 M M M M 0 
P2 0 50 M-36 M-40 M-37 M-40 10 
 
60 
 
17 
 0 M 24 M 22 M M 
C1 140 M-1 4 M-24 1 M-24 M+16 
 
140 
 
1 
 M 0 19 23 20 23 M 
C2 M+1 10 30 20 40 40 M+17 
 
140 
 
0 
Demanda 140 140 30 20 40 40 10 
vj -1 0 19 23 20 23 -17 
F 
–30 
–20 
–40 
–40 
–10
0
0
22
L1
L2
L3
L4
P2 C2
 6
11 
12 
19
23
20
23
+60 
9 
10 24
 4
C1P1 +80 
 
La solución actual es óptima, debido a que todos los costos reducidos de las variables no básicas son no negativos. Además 
se observa que existen múltiples soluciones, debido a que se tiene un costo reducido de una variable no básica con valor 0. 
 
Entonces, el plan de producción que minimiza los costos es el siguiente: 
 
 
 
Desde A Unidades/hora Tiempo
Planta 1 Control Calidad 2 80 15
Planta 2 Control Calidad 2 50 17
Control Calidad 2 Empaque 1 30 19
Control Calidad 2 Empaque 2 20 23
Control Calidad 2 Empaque 3 40 20
Control Calidad 2 Empaque 4 40 23
COSTO TOTAL 4800
PLAN DE PRODUCCIÓN:
 
 
d) Considerando que de la solución óptima se tiene que C2 atiende a todas las unidades (130), basta con asignar una oferta 
y una demanda de 100 unidades a la fila C1 y columna C1, respectivamente. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Problema 4 
 
a) 
 1 2 3 4 5 6 
1 3 -M 2 5 6 4 
2 4 4 3 -M 5 -M 
3 2 4 -M 5 3 6 
4 4 5 6 -M 2 3 
5 4 5 2 5 3 -M 
6 5 2 3 1 4 6 
 
 1 2 3 4 5 6 
1 -3 M -2 -5 -6 -4 (-6) 
2 -4 -4 -3 M -5 M (-5) 
3 -2 -4 M -5 -3 -6 (-6) 
4 -4 -5 -6 M -2 -3 (-6) 
5 -4 -5 -2 -5 -3 M (-5) 
6 -5 -2 -3 -1 -4 -6 (-6) 
 
 1 2 3 4 5 6 
1 3 M+6 4 1 0 2 
2 1 1 2 M+5 0 M+5 
3 4 2 M+6 1 3 0 
4 2 1 0 M+6 4 3 
5 1 0 3 0 2 M+5 
6 1 4 3 5 2 0 
 (1) (0) (0) (0) (0) (0) 
 
 1 2 3 4 5 6 
1 2 M+6 4 1 0 2 
2 0 1 2 M+5 0 M+5 
3 3 2 M+6 1 3 0 
4 1 1 0 M+6 4 3 
5 0 0 3 0 2 M+5 
6 0 4 3 5 2 0 
 
 1 2 3 4 5 6 
1 2 M+5 4 0 0 2 
2 0 0 2 M+4 0 M+5 
3 3 1 M+6 0 3 0 
4 1 0 0 M+5 4 3 
5 1 0 4 0 3 M+6 
6 0 3 3 4 2 0 
 
1 5 = 6 
2 1 = 4 
3 4 = 5 
4 3 = 6 
5 2 = 5 
6 6 = 6 
 Total = 32 
 
 
b) 
 
2 
1 
3 
4 
5 
2
1
3
4
5
5’6 
F 6
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Notar que el nodo ficticio no está conectado con el nodo 5 ni con el nodo 5’. Esto significa que el 
hombre 5 deberá asignársele dos mujeres y en tal caso la solución debe compararse con la solución 
obtenida en la parte (a). Otra forma de modelar el problema es conectando el nodo ficticio con el nodo 
5’ y en tal caso la solución inmediatamente responde la pregunta planteada. Esto es así, pues si el arco 
(F,5’) está en la solución óptima entonces no se le permite al hombre casarse con dos mujeres a la vez. 
 
 
 1 2 3 4 5 5’ 6 
1 3 – 2 5 6 6 4 
2 4 4 3 – 5 5 – 
3 2 4 – 5 3 3 6 
4 4 5 6 – 2 2 3 
5 4 5 2 5 3 3 – 
6 5 2 3 1 4 4 6 
F 0 0 0 0 – – 0 
 
 1 2 3 4 5 5’ 6 
1 -3 M -2 -5 -6 -6 -4 
2 -4 -4 -3 M -5 -5 M 
3 -2 -4 M -5 -3 -3 -6 
4 -4 -5 -6 M -2 -2 -3 
5 -4 -5 -2 -5 -3 -3 M 
6 -5 -2 -3 -1 -4 -4 -6 
F 0 0 0 0 M M 0 
 
 
 
 
 
 1 2 3 4 5 5’ 6 
1 3 M+6 4 1 0 0 2 
2 1 1 2 M+5 0 0 M+5 
3 4 2 M+6 1 3 3 0 
4 2 1 0 M+6 4 4 3 
5 1 0 3 0 2 2 M+5 
6 1 4 3 5 2 2 0 
F 0 0 0 0 M M 0 
 
 1 2 3 4 5 5’ 6 
1 2 M+5 3 0 0 0 2 
2 0 0 1 M+4 0 0 M+5 
3 3 2 M+5 0 3 3 0 
4 2 1 0 M+6 5 5 4 
5 1 0 3 0 3 3 M+6 
6 0 3 2 4 2 2 0 
F 0 0 0 0 M+1 M+1 1 
 
 1 2 3 4 5 5’ 6 
1 3 – 2 5 6 6 4 
2 4 4 3 – 5 5 – 
3 2 4 – 5 3 3 6 
4 4 5 6 – 2 2 3 
5 4 5 2 5 3 3 – 
6 5 2 3 1 4 4 6 
F 0 0 0 0 – – 0 
 
1 5 = 6 
2 5’ = 5 
3 4 = 5 
4 3 = 6 
5 2 = 5 
6 6 = 6 
 Total = 33 
Conclusión: Se le permite al hombre casarse con dos mujeres pues el grado de felicidad aumenta de 32 
a 33. 
 
c) 
 
 1 2 3 4 5 6 F F 
1 3 – 2 5 6 4 0 0 
2 4 4 3 – 5 – 0 0 
3 2 4 – 5 3 6 0 0 
4 4 5 6 – 2 3 0 0 
5 4 5 2 5 3 – 0 0 
6 5 2 3 1 4 6 0 0 
F 0 0 0 0 – 0 – – 
F 0 0 0 0 0 0 – – 
 
Como se trata de un problema de máximo el “–“ equivale a un “–M” 
	Certamen 2