Investigacion Operativa I
Investigacion Operativa I
Investigacion Operativa I
SYLLABUS
SEPTIMO SEMESTRE
1
FACULTAD DE CIENCIA Y TECNOLOGIA
UDABOL
UNIVERSIDAD DE AQUINO BOLIVIA
Acreditada como PLENA mediante R.M. 288/01
VISIN DE LA UNIVERSIDAD
MISIN DE LA UNIVERSIDAD
SYLLABUS
2
FACULTAD DE CIENCIA Y TECNOLOGIA
Podr tomar decisiones, en problemas que tienen que ver con la coordinacin de operaciones y actividades de
una organizacin, utilizando el mtodo cientfico:
UNIDAD I
UNIDAD II
UNIDAD III
3
FACULTAD DE CIENCIA Y TECNOLOGIA
UNIDAD IV
4.1. Importancia.
4.2. Anlisis de sensibilidad y programacin paramtrica.
4.3. Anlisis geomtrico y matemtico.
4.4. Mtodo de la descomposicin lineal.
4.5. Tcnicas de cota inferior y superior.
4.6. Aplicaciones.
UNIDAD V
TEMA 6. ASIGNACION
4
FACULTAD DE CIENCIA Y TECNOLOGIA
2 Evaluacin Parcial
Fecha
Nota: 100 puntos
Examen final
Fecha:
Nota: 100 puntos
APUNTES
5
FACULTAD DE CIENCIA Y TECNOLOGIA
WORK PAPER # 1
ELABOR:
CDIGO: MAT 303A
DESTINADO A:
OBSERVACIONES:
FECHA DE DIFUSIN:
FECHA DE ENTREGA:
1
FACULTAD DE CIENCIA Y TECNOLOGIA
1. El granjero Jones tiene que determinar cuntos acres de maz y de trigo hay que sembrar este ao. Un acre de
trigo produce 25 bushel de trigo y requiere 10 horas semanales de trabajo. Un acre de maz produce 10 bushel
de maz y requiere 4 horas semanales de trabajo. Se puede vender todo el trigo a 4 dlares el bushel y todo el
maz a 3 dlares el bushel. Se dispone de 7 acres y de 40 horas semanales de trabajo. Disposiciones
gubernamentales especifican una produccin de maz de por lo menos 30 bushel durante el ao en curso. Sea
x1 el nmero de acres con maz y x2 el nmero de acres con trigo. Formule un PL, con estas variables de
decisin, cuya solucin indicar al granjero Jones cmo maximizar el ingreso total por la produccin de trigo y
maz.
2. Conteste las siguientes preguntas acerca del Problema 1.
(a) Se encuentra (x1 = 2, x2 = 3) en la regin factible?
(b) Se encuentra (x1 = 4, x2 = 3) en la regin factible?
(c) Se encuentra (x1 = 2, x2 = 1) en la regin factible?
(d) Se encuentra (x1 = 3, x2 = 2) en la regin factible?
3. Vuelva a formular el PL del granjero Jones, usando las variables x1 = nmero de bushel de maz producido y
x2 = nmero de bushel de trigo producido.
4. La empresa Truckco fabrica dos tipos de camiones: 1 y 2. Cada camin tiene que pasar por un taller de pintura
y un taller de montaje. Si el taller de pintura tuviera que dedicarse completamente a la pintura de camiones tipo
1, se podran pintar 800 camiones al da, mientras que si se dedicara enteramente a pintar camiones tipo 2, se
podran pintar 700 camiones al da. Si el taller de montaje se dedicara exclusivamente al ensamble de motores
para camiones tipo 1, se podran ensamblar 1500 motores diariamente, y si se dedicara nicamente a ensamblar
motores para camiones tipo 2, se podran ensamblar 1200 motores diariamente. Cada camin tipo 1 aporta 300
dlares a la ganancia, y cada camin tipo 2 500 dlares. Formule un PL que maximice la utilidad de Truckco.
5. Por qu no permitimos la existencia de restricciones < > en un PL?
6. Resuelva grficamente el Problema 1
7. Resuelva grficamente el Problema 4
8. Leary Chemical produce tres productos qumicos: A, B y C. Estos productos qumicos se obtienen mediante dos
procesos: 1 y 2. El funcionamiento del proceso 1 durante una hora, cuesta 4 dlares y produce 3 unidades del
producto A, 1 unidad del producto B y 1 unidad del producto C. El funcionamiento del proceso 2 durante una
hora, cuesta 1 dlar y produce 1 unidad del producto A, y 1 unidad del producto B. Para satisfacer la demanda
de los clientes, hay que producir diariamente por lo menos 10 unidades del producto A, 5 unidades del producto
B y 3 unidades del producto C. Determine grficamente un plan de produccin diaria para Leary Chemical, que
minimice el Costo de satisfacer las demandas diarias.
9. Para cada una de las siguientes funciones objetivo, determine la direccin en la cual la funcin objetivo aumenta:
a. (a) z = 4x1 - x2
b. (b) z = -x1 + 2x2
c. (c) z = -x1 - 3x2
10. Furnco produce escritorios y sillas. Para cada escritorio se necesitan 4 unidades de madera, y para cada silla 3
unidades. Un escritorio contribuye con 40 dlares a la utilidad, y una silla, 25. Restricciones del mercado
requieren que el nmero de sillas producidas sea por lo menos el doble del nmero de escritorios. Formule un
PL para maximizar la ganancia de Furnco, si hay 20 unidades de madera disponible. Despus resuelva
grficamente el PL.
11. Identifique cul de los Casos 1 a 4 corresponde a los siguientes PL
1. max z = x1 + x2
s.a. x1 + x2 4
x1 x2 5
x1, x2 0
2. max z = 4x1 + x2
s.a. 8x1 + 2x2 16
2
FACULTAD DE CIENCIA Y TECNOLOGIA
5x1 + 2x2 12
x1, x2 0
3. max z = - x1 + 3x2
s.a. x1 - x2 4
x1 +2x2 4
x1, x2 0
4. max z = 3x1 + x2
s.a. 2x1 + x2 6
x1 + 3x2 9
x1, x2 0
12. Verdadero o falso: para que un PL sea no acotado, la regin factible del PL tiene que ser no acotada.
13. Verdadero o falso: cada PL con una regin factible no acotada tiene una solucin ptima no acotada.
14. Si la regin factible de un PL es no acotada, decimos que la regin factible es acotada. Supngase que un PL
tiene una regin factible acotada. Explique por qu puede encontrar la solucin ptima del PL (Sin utilizar una
lnea de isoutilidad o isocosto) verificando simplemente los valores de z en cada uno de los puntos extremo de
la regin factible. Por qu podra fallar este mtodo si la regin factible del PL es no acotada?
15. Encuentre grficamente todas las soluciones ptimas para el siguiente PL:
min z = x1 - x2
s.a. x1 + x2 6
x1 - x2 0
x2 x1 3
x1, x2 0
16. Encuentre grficamente dos soluciones ptimas del siguiente PL:
min z = 3x1 + 5x2
s.a. 3x1 + 2x2 36
3x1 +5x2 45
x1, x2 0
17. Hay tres fbricas a lo argo del Ro Momiss (fbrica 1, 2 y 3). Cada fbrica descarga dos tipos de contaminantes
(contaminante 1 y 2) en el ro. Se puede reducir la contaminacin del ro si se procesan los desechos de cada
fbrica. El proceso de una tonelada de desechos de la fbrica 1, cuesta 15 dlares, y cada tonelada de desechos
procesados de la fbrica 1 reducir la cantidad de contaminante 1 en 0.10 tonelada y la cantidad de
contaminante 2 en 0.45 tonelada. El procesamiento de una tonelada de desechos de la fbrica 2, cuesta 10
dlares, y cada tonelada de desechos procesados de la fbrica 2 reducir la cantidad de contaminante 1 en
0.20 tonelada y la cantidad de contaminante 2 en 0.25 ton. El proceso de una tonelada de desechos de la fbrica
3, cuesta 20 dlares, y cada tonelada de desechos procesados de la fbrica 3 reducir la cantidad de
contaminante 1 en 0.40 tonelada y la cantidad de contaminante 2 en 0.30 tonelada. El estado quiere reducir la
cantidad de contaminante 1 en el ro en por lo menos 30 toneladas y de contaminante 2 en por lo menos 40 ton.
Formule un PL que minimizar el costo de reducir la contaminacin en las cantidades deseadas. Cree que las
suposiciones para el PL (proporcionalidad, aditividad, divisibilidad y certidumbre) son razonables para este
problema?
18. U.S. Labs. produce vlvulas mecnicas para el corazn a partir de vlvulas de cerdos. Operaciones diferentes
del corazn necesitan vlvulas de distintos tamaos. U.S. Labs compra vlvulas de puercos de tres proveedores
diferentes. Los costos y la mezcla de tamaos de las vlvulas compradas de cada proveedor, se muestran en
la Tabla. Cada mes, U.S. Labs hace un pedido a cada proveedor. Hay que comprar por lo menos 500 vlvulas
grandes, 300 medianas y 300 pequeas, al mes. Debido a la disponibilidad limitada de vlvulas de puercos,
solamente se pueden comprar mensualmente, a lo ms 500 vlvulas de cada proveedor. Formule un PL que se
puede utilizar para minimizar el costo para adquirir las vlvulas necesarias.
COSTO POR
VALVULA PORCENTAJE PORCENTAJE PORCENTAJE
(dlares) GRANDE MEDIANA PEQUEA
3
FACULTAD DE CIENCIA Y TECNOLOGIA
Proveedor 1 5 40 40 20
Proveedor 2 4 30 35 35
Proveedor 3 3 20 20 60
19. Peg y Al Fundy tienen un presupuesto limitado para su alimentacin, por lo que Peg trata de alimentar a la
familia lo ms econmicamente posible. Sin embargo, quiere asegurar que su familia tome sus requerimientos
alimenticios diarios. Peg puede comprar dos tipos de alimentacin. El tipo 1 se vende a 7 dlares la libra, y cada
libra contiene 3 unidades de vitamina A y 1 unidad de vitamina C. El tipo 2 se vende a 1 dlar la libra, y cada
libra contiene 1 unidad de cada vitamina. Cada da, la familia necesita por lo menos 12 unidades de vitamina A
y 6 unidades de vitamina C.
(a) Verifique si Peg podra comprar diariamente 12 unidades de alimento tipo 2 y de esta manera superar el
requerimiento de vitamina C en 6 unidades.
(b) Al dio exigi que Peg cumpliera estrictamente con los requerimientos nutricionales diarios de la familia dando
exactamente12 unidades de vitamina A y 6 unidades de vitamina C. La solucin ptima del nuevo problema
incluir ingerir menos vitamina C, pero ser ms costosa. Por qu?
20. Goldilocks tiene que obtener por lo menos 12 lb de oro y por lo menos 18 lb de plata para pagar la renta mensual.
Existen dos minas en las cuales Goldilocks puede encontrar oro y plata. Cada da que Goldilocks est en la
mina 1, encuentra 2 lb de oro y 2 lb de plata. Cada da que est en la mina 2, encuentra 1 lb de oro y 3 lb de
plata. Formule un PL para ayudar a Goldilocks a satisfacer sus requerimientos, minimizando el tiempo que tiene
que estar en las minas. Resuelva grficamente el PL.
4
FACULTAD DE CIENCIA Y TECNOLOGIA
WORK PAPER # 2
ELABOR:
CDIGO: MAT 303A
DESTINADO A:
OBSERVACIONES:
FECHA DE DIFUSIN:
FECHA DE ENTREGA:
5
FACULTAD DE CIENCIA Y TECNOLOGIA
3. Supngase que al resolver un PL, obtenemos el cuadro de la Tabla. Este PL es no acotado, aunque
x1 puede entrar a la base. Por qu?
z x1 x2 x3 x4 ld
1 -3 -2 0 0 0
0 1 -1 1 0 3
0 2 0 0 1 4
4. Aunque el cuadro inicial de un PL es no degenerado, cuadros posteriores pueden mostrar degeneracin. Cuadros
degeneradas se presentan frecuentemente despus de un empate en la prueba de la razn. Para ilustrar esto, resuelva
el PL siguiente:
max z = 5x1 +3x2
s.a. 4x1 +2x2 12
4x1 + x2 10
x1 +x2 4
x1, x2 0
Grafique tambin la regin factible y muestre cules de los puntos extremo corresponden a ms de un conjunto de
variables bsicas.
5. Encuentre la solucin ptima para el PL siguiente:
min z = -x1 - x2
s.a. x1 + x2 1
-x1 + x2 0
x1, x2 0
6. Demuestre que si se realiza un desempate en la prueba de la razn, a favor del rengln 1 en lugar del rengln 2, se
presenta la periodicidad al resolver el PL siguiente mediante el algoritmo simplex:
7. Demuestre que si se realiza un desempate en la prueba de la razn, a favor del rengln 1 en lugar del rengln 2, se
presenta la periodicidad al resolver el PL siguiente mediante el algoritmo simplex:
max z = 2x1 +3x2 x3 -12x4
s.a. -2x1 -9x2 + x3 + 9x4 0
x1 x
x2 3 2x4 0
3 3
xi 0 (i = 1,2,3,4)
6
FACULTAD DE CIENCIA Y TECNOLOGIA
7
FACULTAD DE CIENCIA Y TECNOLOGIA
14. Durante los prximos tres meses, Steelco enfrenta las siguientes demandas de acero: 100 toneladas (mes 1), 200
toneladas (mes 2); 50 toneladas (mes 3). En cualquier mes, un trabajador puede producir hasta 15 toneladas de acero.
A cada trabajador, se le paga 5000 dlares al mes. Se pueden contratar trabajadores a 4000 dlares el trabajador, o
despedir trabajadores a 3000 dlares el trabajador (la contratacin de un trabajador toma un tiempo 0). El costo de
mantener una tonelada de acero en el inventario por un mes, es de 100 dlares. Se permiten demandas pendientes, a
un costo de 70 dlares por tonelada-mes. Es decir, si se cumple con una demanda de 1 tonelada hecha en el mes 1,
durante el mes 3, se incurre en un costo por la demanda pendiente de 140 dlares. Al inicio del mes 1, Steelco tiene 8
trabajadores. Se pueden contratar lo ms 2 trabajadores durante cualquier mes. Toda la demanda se tiene que cumplir
para el final del mes 3. La materia prima para producir una tonelada de acero, cuesta 300 dlares. Formule un PL para
minimizar los costos de Steelco.
15. Demuestre cmo se podra utilizar la programacin lineal para resolver el problema siguiente:
max z = 2x1 -3 x2
s.a. 4x1 + x2 4
2x1 - x2 0.5
x1, x2 0
16. La fbrica principal de Steelco tiene un rea de produccin del acero y un rea de envo, localizadas como se
indica en la Fig. (Las distancias estn en pies.)
Area de Envo
(1000,0)
La compaa tiene que decidir en dnde colocar una instalacin de fundicin y una instalacin de montaje y
almacenaje, para minimizar los costos diarios de mover el material a travs de la fbrica, El nmero de viajes que se
realizan diariamente, se muestran en la Tabla
Supngase que todos los viajes se realizan solamente en una direccin este-oeste o norte-sur; formule un PL que se
puede utilizar para determinar la localizacin de las instalaciones de fundicin, y de montaje y almacenamiento, para
minimizar los costos diarios del transporte. (Sugerencia: Si la instalacin de fundicin tiene las coordenadas (cl, c2),
cmo habr que interpretarse la restriccin c1 - 700 = e1 - w1? (e = este, y w = oeste.)
NUMERO DE COSTO POR
VIAJES 100 PIES
DE HACIA DIARIAMENTE VIAJADOS
(en centavos)
Fundicin Montaje y almacenamiento 40 10
Produccin de Acero Fundicin 8 10
Produccin de Acero Montaje y almacenamiento 8 10
Envo Montaje y almacenamiento 2 20
8
FACULTAD DE CIENCIA Y TECNOLOGIA
17. Utilice el algoritmo simplex para encontrar dos soluciones ptimas para el PL siguiente:
max z = 5x1 + 3x2 + x3
s.a. x1 + x2 +3x3 6
5x1 + 3x2 +6x3 15
x1 + x2 = 3
` x1, x2, x3 0
18. Utilice el algoritmo simplex para encontrar la solucin ptima para el PL siguiente:
min z = - 4x1+ x2
s.a. 3x1 + x2 6
- x1 + 2x2 4
x1, x2 0
19. Utilice el Metodo de la M grande y el mtodo de las dos fases para obtener una solucin ptima del PL siguiente:
max z = 5x1 - x2
s.a. 2x1 + x2 = 6
x1 + x2 4
x1 + 2x2 5
x1, x2, 0
20. Utilice el algoritmo simplex para encontrar la solucin ptima para el PL siguiente:
max z = 5x1 - x2
s.a. x1 - 3x2 1
x1 - 4x2 3
x1, x2, 0
21. Utilice el algoritmo simplex para encontrar la solucin ptima para el PL siguiente:
min z = - x1 - 2x2
s.a. 2x1 + x2 5
x1 + x2 3
x1, x2, 0
22. Utilice el Metodo de la M grande y el mtodo de las dos fases para obtener una solucin ptima del PL siguiente:
max z = x1 + x2
s.a. 2x1 + x2 3
3x1 + x2 3.5
x1 + x2 1
x1, x2, 0
23. Utilice el algoritmo simplex para encontrar dos soluciones ptimas para el PL siguiente.Cuantas soluciones
ptimas tiene este PL?. Encuentre una tercera solucin ptima.
max z = 4x1 + x2
s.a. 2x1 + 3x2 4
x1 + x2 1
4x1 + x2 2
x1, x2, 0
24. Utilice el algoritmo simplex para encontrar la solucin ptima para el PL siguiente:
max z = 5x1 + x2
s.a. 2x1 + x2 6
x1 - x2 0
x1, x2, 0
9
FACULTAD DE CIENCIA Y TECNOLOGIA
25. Utilice el Metodo de la M grande y el mtodo de las dos fases para obtener una solucin ptima del PL siguiente:
min z = -3x1 + x2
s.a. x1 - 2x2 2
- x1 + x2 3
x1, x2, 0
27. Considrese el PL siguiente:
max z = 10x1 + x2
s.a. x1 1
20x1 + x2 100
x1, x2, 0
28. Considrese un problema de maximizacin con el cuadro de la tabla siguiente. La solucin ptima para este PL es
z = 10, x3 = 3, x4 = 5, x1, x2 = 0. Determine la mejor sbf, despus de la primera, para este PL. (Sugerencia: Demuestre
que la mejor solucin despus de la primera, tiene que ser una sbf que se encuentra a un pivoteo de la solucin
ptima.)
z x1 x2 x3 x4 ld
1 2 1 0 0 10
0 3 2 1 0 3
0 4 3 0 1 5
29. Un campista est considerando llevar dos tipos de artculos para ir a acampar. El artculo 1 pesa a1 lb. y el artculo
2 pesa a2 lb. Cada artculo 1 proporciona al campista un beneficio de c1 unidades, y cada artculo 2 proporciona al
campista un beneficio de c2 unidades. La mochila aguanta a lo ms b lb de artculos.
(a) Formule un PL para maximizar los beneficios, suponiendo que el campista puede llevar fracciones de los artculos
en su viaje.
b) Demuestre que si
c 2 c1
a 2 a1
entonces el campista podr maximizar los beneficios. llenando su mochila con Xx artculos tipo 2.
(c) Cuales de las suposiciones de la programacin lineal se violan en este planteamiento del problema del campista?
z x1 x2 x3 x4 x5 ld
1 -c 2 0 0 0 10
0 -1 a1 1 0 0 4
0 a2 -4 0 1 0 1
0 a3 3 0 0 1 b
Establezca las condiciones para las incgnitas a1, a2, a3, b, c, para que se cumplan los enunciados siguientes:
(a) La solucin actual es ptima.
(b) La solucin actual es ptima, y hay otras soluciones ptimas
(e) El PL es no acotado (en esta parte, supngase que b 0).
10
FACULTAD DE CIENCIA Y TECNOLOGIA
31. Supngase que hemos obtenido el cuadro de la Tabla siguiente para un problema de maximizacin.
z x1 x2 x3 x4 x5 x6 ld
1 c1 c2 0 0 0 0 10
0 4 a1 1 0 a2 0 b
0 -1 -5 0 1 -1 0 2
0 a3 -3 0 0 -4 1 3
Establezca las condiciones para a1, a2, a3, b, c1, y c2, para que se cumplan los enunciados siguientes:
(a) La solucin actual es ptima, y existen otras soluciones ptimas.
(b) La solucin bsica actual no es una solucin bsica factible.
(c) La solucin bsica actual es una sbf degenerada.
(d) La solucin bsica actual es factible, pero el PL es no acotado.
(e) La solucin bsica actual es factible, pero se puede mejorar el valor de la funcin objetivo al reemplazar x6 por x1
como una variable bsica.
32. Supngase que estamos resolviendo un problema de maximizacin y que la variable xr est por salir de la base.
(a) Cul es el coeficiente de xr en el rengln O actual?
(b) Demuestre que, despus de realizar el pivoteo actual, el coeficiente de xr en el rengln 0, no puede ser menor que
cero.
(e) Explique por qu una variable que sali de la base en un pivoteo dado, no puede volver a entrar a la base en el
pivoteo siguiente.
33. Una compaa de autobuses cree que necesita el siguiente nmero de choferes durante cada uno de los prximos
cinco aos: ao 1, 60 choferes; ao 2, 70 choferes; ao 3, 50 choferes; ao 4, 65 choferes; ao 5, 75 choferes. Al inicio
de cada ao, la compaa de autobuses debe decidir a cuntos choferes hay que contratar o despedir. Cuesta 4000
dlares contratar a un chofer, y 2000 dlares despedir a un chofer. El salario anual de un chofer es de 10000 dlares.
Al inicio del ao 1, la compaa tiene 50 choferes. Se puede utilizar a un chofer, contratado a principios de un ao, para
cumplir con los requerimientos del ao actual, y se le paga el salario completo por el ao actual. Formule un PL para
minimizar los costos de los salarios, de las contrataciones, y de los despidos, de lii compaa, durante los prximos
cinco aos.
34. Shoemakers of America predice las siguientes demandas para cada uno de los prximos seis meses: mes 1, 5000
pares; mes 2, 6000 pares; mes 3, 5000 pares; mes 4, 9000 pares, mes 5, 6000 pares; mes 6, 5000 pares. Un zapatero
tarda 15 minutos en producir un par de zapatos. Cada zapatero trabaja durante 150 horas al mes, ms 40 horas
mensuales de tiempo extra. El zapatero recibe un salario mensual normal de 2000 dlares, ms 50 dlares por hora
extra. Al principio de cada mes, Shoemakers puede contratar a un trabajador o despedir a un trabajador. A la compaa
le cuesta 1500 dlares contratar a un trabajador, y 1900 dlares despedirlo. El costo mensual, por par de zapatos, por
mantenimiento del inventario, es el 3 % del costo de produccin de un par de zapatos, con trabajo de tiempo regular.
(Las materias primas para un par de zapatos cuestan 20 dlares.) Formule un PL que minimiza el costo de cumplir (a
tiempo) con las demandas de los prximos seis meses. Al inicio del primer nies, Shoeniakers tiene 13 trabajadores.
35. Durante los cuatro trimestres siguientes. Dorian Auto debe satisfacer (a tiempo) las demandas siguientes de
automviles: trimestre 1, 4000; trimestre 2, 2000; trimestre 3, 5000; trimestre 4, 1000. Al inicio del trimestre 1, hay 300
automviles en la bodega, y la compaa tiene la capacidad de producir a lo mas 3000 automviles por trimestre. Al
inicio de cada trimestre, la compaa puede cambiar la capacidad de produccin. Cuesta 100 dlares aumentar la
capacidad de produccin trimestral en un automvil. Cuesta 50 dlares por trimestre mantener la capacidad de
produccin en un automvil (aunque no se use durante el trimestre actual). El costo variable de la produccin de un
automvil es de 2000 dlares. Se aplica un costo de mantenimiento del inventario de 150 dlares por automvil, al
11
FACULTAD DE CIENCIA Y TECNOLOGIA
inventario final de cada trimestre. Se necesita que, al final del trimestre 4. la capacidad de la fbrica este en por lo
menos 4000 automviles. Formule un PL para minimizar el costo total de los cuatro trimestres siguientes.
36. Ghostbusters. Inc. exorciza (se deshace de) fantasmas. Durante cada uno de los tres meses siguientes, recibirn la
siguiente cantidad de llamadas telefnicas de personas que quieren que se les exorcicen sus fantasmas: enero, 100
llamadas; febrero, 300 llamadas; marzo, 200 llamadas. Se le paga a Ghostbusters 800 dlares por cada fantasma
exorcizado durante el mismo mes de la llamada del cliente. No es obligatorio atender las demandas en el mismo mes
de la llamada, pero si se atiende la demanda un mes despus de la llamada, Ghostbusters perder 100 dlares en la
clientela futura, si se atiende la demanda dos meses despus de la llamada. Ghostbusters perder 200 dlares. Cada
empleado de Ghostbusters puede exorcizar 10 fantasmas durante un mes. A cada empleado se le paga un salario
mensual de 4000 dlares. A principios de enero, la compaa tiene 8 empleados. Se pueden contratar y entrenar (
inmediatamente) a trabajadores, a un costo de 5000 dlares el trabajador. Se pueden despedir a trabajadores, a un
costo de 4000 dlares el trabajador. Formule un PL para maximizar las ganancias (ingresos menos costos) de
Ghostbusters, para los tres meses siguientes. Supngase que se debe atender todas las demandas al final del mes de
marzo.
37. Carco utiliza autmatas para producir automviles. Hay que cumplir con las siguientes demandas de automviles
(no necesariamente a tiempo, pero se tiene que cumplir con todas las demandas al final del trimestre 4): trimestre 1,
600; trimestre 2, 800; trimestre 3, 500; trimestre 4, 400. Al inicio del trimestre 1, Carco tiene 2 autmatas. Se pueden
comprar a lo ms 2 autmatas al inicio de cada trimestre. Cada autmata puede producir hasta 200 automviles por
trimestre. Un autmata cuesta 5000 dlares. Durante cada trimestre, se incurren en costos de mantenimiento de 500
dlares
por autmata (aunque no se use para construir automviles). Tambin se puede vender los autmatas al inicio de cada
trimestre, a 3000 dlares el autmata. Al final de cada trimestre, se aplica un costo de mantenimiento del inventario de
200 dlares por cada automvil. Si se tiene una demanda pendiente, se incurre en un costo de 300 dlares por
automvil, por cada trimestre que se deja pendiente la demanda.
Al final de cada trimestre, Carco debe que tener por lo menos dos autmatas. Formule un PL para minimizar los costos
totales incurridos para cumplir las demandas de los automviles durante los cuatro trimestres siguientes.
38. Supngase que hemos obtenido un cuadro ptimo para un PL, y que la sbf para este cuadro no est degenerado.
Supngase tambin que hay una variable no bsica con un coeficiente cero en el rengln. Demuestre que el PL tiene
ms de una solucin ptima.
39. Supngase que la sbf de un cuadro ptimo esta degenerada, y que una variable no bsica tiene un coeficiente cero
en el rengln 0. Demuestre, mediante un ejemplo, que se puede presentar uno de los siguientes casos:
12
FACULTAD DE CIENCIA Y TECNOLOGIA
WORK PAPER # 3
ELABOR:
CDIGO: MAT 303A
DESTINADO A:
OBSERVACIONES:
FECHA DE DIFUSIN:
FECHA DE ENTREGA:
13
FACULTAD DE CIENCIA Y TECNOLOGIA
EJERCICIO 1 Recuerde el problema de la BlubberMaid, Inc., visto en clases, en el que A es el nmero de libras de
Airtex, E el nmero de libras Extendex y R el nmero de libras de Resistex que se utilizan para producir
Maximizar ganancia = 7A + 7E + 6R
Dependiendo de:
RESTRICCIONES DE RECURSOS
RESTRICCIONES DE DEMANDA
RESTRICCIONES LGICAS
A, E, R 0
Obtenga el resultado con el paquete de computacin STORM. Utilice el resultado de computacin obtenido para
responder a las preguntas siguientes:
a. Cul es el plan de produccin ptimo?
b. Cules de las cuatro restricciones de recursos son acotantes?
c. Con el plan de produccin actual, para cul de los tres productos se puede cumplir con una demanda adicional de
5% ? Explique.
EJERCICIO 2 Utilice el resultado de computacin del ejercicio 1 para responder a lo siguiente: Si usted pudiera
obtener cantidades adicionales de nicamente uno de los tres polmeros, cul de ellos recomendara? Explique.
EJERCICIO 3 Utilice el resultado de computacin del ejercicio 1 para responder a lo siguiente: Qu coeficiente o
coeficientes de ganancia podran duplicarse, mientras se mantienen fijos todos los dems coeficientes, sin que se afecte
el plan de produccin ptimo? Explique.
EJERCICIO 4 Utilice el resultado computacional del ejercicio 1 para responder lo siguiente: La ganancia de Extendex
acaba de disminuir en 20%. Cul es el nuevo plan de produccin y la ganancia total? Explique.
EJERCICIO 5 Utilice el resultado computacional del ejercicio 1 para responder a lo siguiente: (Si no puede hacerlo,
obtenga la respuesta resolviendo un modelo apropiadamente modificado con su paquete de computacin.) El
compromiso de producir 400 libras de Resistex acaba de caer en 10%. Qu le sucede a la ganancia ptima? Explique.
EJERCICIO 6 Utilice el resultado computacional del ejercicio 1 para responder a lo siguiente: (Si no puede hacerlo,
obtenga la respuesta resolviendo un modelo apropiadamente modificado con su paquete de computacin.) La compaa
desea aumentar sus ganancias a $18 000 adquiriendo ms cantidad del polmero A. Cunto ms del polmero A se
necesita? Explique.
EJERCICIO 7 Utilice el resultado computacional del ejercicio 1 para responder a lo siguiente: (Si no puede hacerlo,
obtenga la respuesta resolviendo un modelo apropiadamente modificado con su paquete de computacin.) Si la demanda
de Airtex aumenta en 2%, cul es el nuevo plan de produccin ptimo? Explique.
14
FACULTAD DE CIENCIA Y TECNOLOGIA
EJERCICIO 8 Recuerde el problema de MTV Steel visto en clases, en el cual se deseaba determinar los valores de las
variables:
AP =nmero de toneladas de acero tipo A por producir
BP =nmero de toneladas de acero tipo B por producir
CP =nmero de toneladas de acero tipo C por producir
AJ = nmero de toneladas de acero tipo A por comprar al Japn
BJ = nmero de toneladas de acero tipo B por comprar al Japn
CJ = nmero de toneladas de acero tipo C por comprar al Japn
De modo que
AP + AJ = 2000 (demanda A)
BP + BJ = 4000 (demanda B)
CP + CJ = 5000 (demanda C)
RESTRICCIONES DE RECURSOS
RESTRICCIONES LGICAS
Obtenga el resultado con el paquete de computacin STORM. Utilice el resultado de computacin obtenido para
responder a las preguntas siguientes:
a. Cul es el plan de produccin/adquisicin ptimo para la MTV Steel?
b. Cules de las dos restricciones de recursos son acotantes?
c. Si pudiera obtener ms material para soldar o ms tiempo de mquina, pero no ambas cosas, cul escogera?
Explique.
EJERCICIO 9 Utilice el resultado de computacin del ejercicio 8 para responder lo siguiente: (Si no puede hacerlo,
obtenga la respuesta resolviendo un modelo apropiadamente modificado con su paquete de computacin.) Los
japoneses acaban de aumentar el precio de sus tubos tipo C de $7 a $8 por pie. De qu manera cambia el plan de
produccin/adquisicin actual? Explique
EJERCICIO 10 Utilice el resultado de computacin del ejercicio 8 para responder lo siguiente: (Si no puede hacerlo,
obtenga la respuesta resolviendo un modelo apropiadamente modificado con su paquete de computacin.) La compaa
desea aumentar sus ganancias a $57 500. Cuntas horas ms de tiempo de mquina se necesitan para lograr este
objetivo? Explique.
EJERCICIO 11 Utilice el resultado de computacin del ejercicio 8 para responder lo siguiente: (Si no puede hacerlo,
obtenga la respuesta resolviendo un modelo apropiadamente modificado con su paquete de computacin.) La compaa
puede vender su material para soldar con una ganancia de $32 por libra. Cunto deber vender? Explique.
15
FACULTAD DE CIENCIA Y TECNOLOGIA
WORK PAPER # 4
ELABOR:
CDIGO: MAT 303A
DESTINADO A:
OBSERVACIONES:
FECHA DE DIFUSIN:
FECHA DE ENTREGA:
16
FACULTAD DE CIENCIA Y TECNOLOGIA
EJERCICIO 1 Cabinets Unlimited es una compaa en la que se manufactura y ensambla todo tipo de gabinetes. Se va
a manufacturar un nuevo gabinete, lo cual requiere las siguientes tareas:
Las ruedas se montan despus de ser preparadas. La base no puede unirse hasta que se ensamblen los costados y las
ruedas estn montadas. La parte superior no puede unirse ni insertarse las mnsulas hasta que estn ensamblados los
costados. Las repisas se colocan despus de haber colocado las mnsulas. El panel posterior se une despus de que
la base y la cubierta superior son colocadas. Las puertas se colocan despus de que se instalan las repisas, la base y la
cubierta superior. La unidad se pinta despus de haber sido colocadas la base y la cubierta superior.
EJERCICIO 2 Broadway Productions es una compaa que monta espectculos musicales para Broadway. Se acaba de
firmar el contrato de un nuevo musical, y el productor ha identificado las siguientes tareas que necesitan hacerse antes
de presentar el espectculo:
La coreografa se hace despus de orquestada la msica. Los ensayos de danza no pueden empezar hasta que cada
parte est preparada, se contrate a los artistas y se termine la coreografa. El escenario es diseado y construido despus
del ensayo de danza. El vestuario es preparado despus de que se contratan a los artistas. El ensayo de vestuario se
hace despus del ensayo de danza y cuando el vestuario est listo. Al ensayo de vestuario le sigue el ensayo general,
que tambin requiere el escenario. El ensayo final sigue despus del ensayo general.
17
FACULTAD DE CIENCIA Y TECNOLOGIA
EJERCICIO 3 Para el proyecto del ejercicio 1, a continuacin se presenta el costo adicional en dlares (costo normal -
costo de choque) para obtener los tiempos de choque de cada una de las tareas:
a. Utilizando esta informacin, formule un modelo de choque apropiado para lograr un tiempo de terminacin de
48 minutos.
b. Resuelva el modelo del inciso (a) utilizando su paquete de computacin.
c. Cunto costar lograr un tiempo de ensamblado de 48 minutos? Qu tarea debe acortarse para lograr este
objetivo? En cunto?
d. Cul es el tiempo de ensamblado ms corto que puede lograrse con un gasto adicional de $19?
EJERCICIO 4 Para el proyecto del ejercicio 2, a continuacin se presenta el costo adicional en dlares (costo normal -
costo de choque) para obtener los tiempos de choque para cada una de las tareas:
18
FACULTAD DE CIENCIA Y TECNOLOGIA
Tal vez usted piense que la programacin lineal slo interesa a los administradores de negocios y a los cientficos
espaciales. Bueno, qu hay ms comn que ir al puesto de hot dogs local? Aqu se ilustra cmo los modelos de
programacin lineal y la compleja tcnica simplex tienen relacin con nuestras vidas de tres maneras distintas al ir en
automvil por un refrigerio.
Considere el coche mismo, un producto de General Motors. GM tiene 60 modelos diferentes, y hay infinidad de nuevas
caractersticas que puede ofrecer a sus clientes. Todas estas posibilidades representan un vasto nmero de variaciones
que GM podra vender. Cmo determina esto la combinacin ptima del producto? La evaluacin de las diversas
combinaciones de modelos y opciones tomara dcadas incluso con computadoras de alta velocidad. Pero las
computadoras de GM son capaces de determinar la combinacin ptima del producto aplicando el mtodo smplex a los
modelos de PL.
"Revisin del aceite?" Incluso el aceite que mantiene andando suavemente el motor de nuestro auto es resultado de
una decisin basada en un modelo de programacin lineal. Las refineras de petrleo producen otras cosas aparte de
aceite. Pueden producir hasta 3000 productos diferentes, como tinta, aspirinas, cuerdas para guitarra, perfumes,
colorantes de cabello, repelentes de insectos, raquetas de tenis de mesa, alfombras e incluso goma de mascar. La
decisin de cules de estos productos hacer en un esfuerzo por maximizar las ganancias, dado que los recursos
disponibles son limitados, nuevamente se halla a travs de la programacin lineal.
Y ahora, estamos en el puesto de hot dogs. En cualquier semana, los ingredientes del hot dog hechos en la planta
pueden cambiar. Algunas veces los hot dogs son sobre todo carne de res, y otras semanas son principalmente carne de
puerco. Cmo lo decide el fabricante? Usted adivin. Un modelo de programacin lineal proporciona la informacin que
los administradores necesitan para decidir la mejor mezcla de ingredientes.
1. Cuando Henry Ford produjo por primera vez automviles, enfrent el problema que GM enfrenta ahora
respecto a los estilos y colores que ofrecer?
2. Qu es lo que hace que la programacin lineal sea necesaria en los tres ejemplos que se presentan?
1. Enumere unas cuantas categoras de caractersticas de un coche (estilo, color, tipo de techo, sistema de sonido,
etc.). Dentro de cada categora, enumere algunas opciones (por ejemplo, el estilo podra ser de dos puertas,
cuatro puertas, etc.). La multiplicacin del nmero de opciones de cada categora le da el nmero total de
variaciones posibles de un coche. Qu tan difcil piensa que sea llegar a 1000 variaciones? Comente por qu
un fabricante de autos podra tomar como una ventaja tener un modelo de programacin lineal al considerar las
variantes por producir.
2. Por qu no mantiene un fabricante de hot dogs la misma receta todos los das? Qu restricciones piensa que
tiene el fabricante en su modelo de programacin lineal?
Consideraciones prcticas
1. Suponga que GM tiene 10 000 000 variantes posibles de carros. Si una computadora de alta velocidad puede
determinar el plan de produccin para cada variante en un segundo, cunto tomar (en aos) determinar el
plan ptimo? Qu le dice esto sobre la necesidad de buenos mtodos matemticos?
1
FACULTAD DE CIENCIA Y TECNOLOGIA
2. Vaya a una tienda de pinturas y obtenga una tarjeta que muestre distintos colores al frente. Dle vuelta y observe
los cdigos de barras en la parte de atrs. Qu cree que representan los cdigos? Por qu cree que esta
informacin est en formato de cdigo de barras?
Fuente: "For All Practical Purposes", de The Consortium For Mathematics and Its Applications (Arlington, MA: 1986),
Programa 2.
2
FACULTAD DE CIENCIA Y TECNOLOGIA
Sigue manejando
Yellow Freight es una empresa de transportes que hace entregas de bienes que no rebasan la capacidad de un camin
lleno. La empresa tiene 26 zonas de descarga, que son puntos intermedios a lo largo de las rutas y donde llegan envos
de varios camiones diferentes. En estas zonas de descarga, las cargas son reclasificadas segn su destino comn y son
divididas en cargas ms pequeas que luego son enviadas a alguna de las terminales de fin de lnea (FdL).
Recuerda el Pony Express? Los jinetes llevaban el correo durante largas distancias haciendo cambios de caballo en
estaciones situadas a lo largo de la ruta. Con una ligera variacin, los conductores de Yellow Freight llevan su carga
hasta la zona de descarga y desenganchan el remolque. Otro chofer recoge la carga y la lleva hasta otra zona de
descarga. El proceso contina hasta que la carga alcanza su destino. Por ejemplo, un cargamento puede iniciar en la
terminal de Boston, pasar por las zonas de descarga situadas en Maybrook y Kansas City y llegar hasta su terminal de
destino en Des Moines.
En un da promedio, Yellow Freight hace 60 000 cargas y entregas; 250 000 envos distintos llegan a 35 000 comunidades
y a un total de 400 000 clientes. La red tiene 630 terminales. Para optimizar las rutas de fletes diarias mediante el
equilibrio de la demanda de servicio con los costos de operacin, Yellow Freight utiliza el paquete SYSNET, que es un
modelo de asignacin de recursos a gran escala y que corre en su computadora principal.
SYSNET es un avanzado programa de optimizacin interactivo, una herramienta administrativa de trabajo pesado que
ofrece a los gerentes de la empresa Yellow Freight un anlisis rpido y completo de las condiciones de la red, lo que les
permite controlar cuidadosamente una de las redes ms grandes del mundo y proporcionar de manera consistente un
servicio de alta calidad. SYSNET pesa los diferentes equilibrios entre variables, incluyendo costos de manipulacin,
capacidades de carga, tiempo de viaje, kilometraje en carretera y el nmero de remolques vacos. Los gerentes de
operacin no pueden agregar de manera directa envos adicionales sin que tengan que verificarlo con los administradores
de SYSNET. Por qu? Un pequeo ahorro que se podra obtener directamente en un envo, puede verse ms que
contrarrestado con un aumento en los costos en el resto del sistema.
1. De cuntas maneras diferentes puede Yellow Freight hacer un envo de Boston a Des Moines?
2. Cules son los pros y los contras de hacer un envo directo y hacer un envo de la manera habitual?
1. Describa las similitudes entre la empresa Yellow Freight y las aerolneas, con sus rutas estructuradas. Cules
son las zonas de descarga de las aerolneas? Qu problemas tienen con el "envo" de pasajeros y la capacidad
de funcionamiento?
2. Federal Express fue uno de los pioneros en el envo con una zona intermedia de descarga, ubicada en Memphis,
Tennessee. A menudo los paquetes enviados de Atlanta a Miami pasaban por Memphis. Explique la razn
fundamental para agregar un kilometraje extra, al envo de tales paquetes.
Consideraciones prcticas
1. Qu impacto tiene SYSNET sobre la autoridad de un gerente de envos local que efecta operaciones da a
da en Boston? En Maybrook? Por qu es necesario centralizar la autoridad en una estructura como la que
posee Yellow Freight?
3
FACULTAD DE CIENCIA Y TECNOLOGIA
2. La tcnica de solucin para un problema de programacin lineal tan grande como el de Yellow Freight debe ser
ms rpida que la tcnica simplex estndar. Su modelo de programacin lineal tiene una estructura especial
que utiliza solamente enteros. Qu otros algoritmos deberan ser ms rpidos que el simplex estndar?
4
FACULTAD DE CIENCIA Y TECNOLOGIA
De qu manera las aerolneas manejan la tarea de tener listas sus aeronaves para ser abordadas por los pasajeros?
Bill Rodenhizer, de la ahora extinta Western Airlines, explica las tareas bsicas implicadas en la preparacin de las
aeronaves comerciales que llegan a Boston y cuyo siguiente despegue se realizar en los siguientes 45 a 60 minutos.
El siguiente diagrama simplificado muestra las tareas que se deben hacer dentro y fuera del aeroplano, junto con el
tiempo que toma su realizacin.
A C
Abordaje de
13 15 Pasajeros
E
27
Descarga de carga Cargado de
Anterior Nueva Carga
B D
25 22
La grfica muestra que ciertas tareas deben hacerse primero, es decir, la grfica indica relaciones de precedencia. En
un ejemplo obvio, los pasajeros que llegan deben desalojar la nave y el interior ser limpiado antes de que puedan abordar
los nuevos pasajeros. Del mismo modo, la carga anterior debe ser descargada para tener espacio para la carga del
siguiente vuelo. Las restricciones del modelo se definen mediante, el mantenimiento de las relaciones de precedencia
requeridas y llevando a cabo todas las tareas en los tiempos fijados.
La trayectoria crtica es la secuencia de tareas ms larga (en trminos de tiempo), y el tiempo que lleva terminar esta
secuencia es el tiempo de terminacin ms temprano para todo el proyecto. De las tres trayectorias del sistema, A-C-E
(55 minutos), B-E (52 minutos) y B-D (47 minutos), la ms larga dura 55 minutos.
Puede la aerolnea utilizar el mtodo de la ruta crtica (CPM) para ahorrar dinero? Regrese a la trayectoria crtica y
considere las implicaciones de acortar una tarea en particular a lo largo de dicha trayectoria. Si la actividad A (desalojo
de pasajeros) se reduce en seis minutos, efectivamente la trayectoria crtica se acorta, pero solamente en tres minutos,
no en seis. Por qu? La trayectoria A-C-E ya no es crtica, ahora slo dura 48 minutos. La nueva trayectoria crtica es
B-E, que todava lleva 52 minutos para terminarla. Debera, entonces, la aerolnea gastar el dinero necesario para
acortar la trayectoria A-C-E en seis minutos? Reducir esta actividad no reducir el tiempo necesario para terminar el
proyecto entero tanto como se podra haber sospechado en un principio.
Un segundo ejemplo de una importante aplicacin de CPM contempla las miles de actividades que se requieren para
construir un edificio.
Los contratistas utilizan CPM para estimar justamente cunto tiempo tomar un proyecto y, en consecuencia, desarrollar
un programa de construccin.
5
FACULTAD DE CIENCIA Y TECNOLOGIA
1. D dos razones realistas del porqu la carga anterior necesita ser descargada antes de que los nuevos
pasajeros aborden la aeronave.
2. Cules son algunas de las tareas principales que se deben hacer en la construccin de un edificio? De qu
manera pueden secuenciarse en un diagrama CPM?
1. De qu maneras se podran acelerar algunas de las tareas en la preparacin de una aeronave? Cules
2. podran ser los costos en la instrumentacin de sus sugerencias?.
3. Cmo se puede aplicar el CPM en la escritura de un artculo de investigacin o de un trabajo final para uno de
sus cursos? De qu manera le podra ayudar esta tcnica?
Consideraciones prcticas
1. Si hay miles de tareas que se deben realizar en la construccin de un edificio, de qu manera CPM ayuda al
gerente de proyectos a "administrar por excepcin"?
2. Qu probabilidad cree usted que tengan de ser exactos los tiempos dados para terminar las tareas para tener
lista la aeronave? Qu impacto podra tener una variacin en el tiempo de tareas sobre el modelo CPM?
Fuente: "For ll Practical Purposes", tomado de The Consortium for Mathematics and its Applications (Arlington, MA:
1986), Programas 1 y 4.
6
FACULTAD DE CIENCIA Y TECNOLOGIA
Empacndolos
UPS es la mayor compaa en el mundo de distribucin de paquetes; opera una red global que maneja 11 millones de
paquetes diariamente. El pblico ve una compaa confiable y eficiente con conductores amables en esas familiares y
puntuales camionetas cafs, pero en UPS suceden ms cosas de las que el ojo puede ver.
UPS mantiene una de las aerolneas de carga ms grandes del mundo, con una flota de ms de 60 aviones Boeing 757
adaptados. La compaa tambin mantiene una completa variedad de vehculos de transportacin terrestre, desde las
camionetas cafs hasta remolques e incluso bicicletas. Todos sus vehculos han sido diseados para incrementar el
rendimiento de combustible, la eficiencia operativa y, a la vez, reducir la contaminacin y el ruido.
El corazn tcnico del sistema de informacin de UPS es una sofisticada red de computacin que cubre el globo
terrqueo, manteniendo a UPS en contacto constante con sus paquetes y clientes. En conexin con las tcnicas de la
ciencia administrativa, este sistema de informacin resuelve continuamente muchos problemas de transportacin,
trasbordo y asignacin.
El video muestra un enorme cuarto, donde se mantienen 49 000 mapas, uno para cada seccin de 7 por 9 millas de los
EE.UU. Estos mapas se almacenan electrnicamente en la computadora central de manera que UPS pueda tener acceso
a cualquier direccin. Mediante dispositivos de rastreo avanzado, el sistema de computacin puede asignar rpidamente
el conductor ms cercano disponible para una inmediata recoleccin de paquetes. Cada conductor tiene un moderno
tablero computarizado porttil que almacena los nmeros de contabilidad, los tiempos de entrega e incluso la firma del
cliente para la ruta de ese da. Al final del da el tablero se acopla a una terminal y todos los datos se cargan al sistema
central. Esta informacin es vital para la eficiente operacin de este complejo sistema de entregas.
UPS ha sido pionero del "empacado inteligente", al usar equipo de cdigo de barras, de examen y ordenamiento para
rastrear, trazar y facturar rpida y eficientemente, al mismo tiempo que contina la tradicin de la entrega puntual.
1. Cules son algunas de las estadsticas que sealan a UPS como la mayor compaa de entrega de paquetes
de los EE.UU. y del mundo?
2. Cules son algunos de los servicios flexibles que UPS puede ofrecer?
1. Describa cmo podra aplicar el problema de trasbordo para manejar recolecciones y entregas dentro de una
ciudad importante.
2. Cules son algunos de los datos necesarios diariamente para asignar conductores a camiones y rutas?
Consideraciones prcticas
1. Por qu es ms barato para UPS enviar un paquete de Miami a Atlanta a travs de su central de Louisville que
enviarlo directamente de Miami a Atlanta?
2. Discuta las similitudes entre UPS y Yellow Freight