1. 2. 3. Introducción La asignatura Investigación Operativa es una asignatura cuatrimestral dedicada fundamentalmente a la introducción de los modelos deterministas más elementales dentro de la investigación de operaciones. Esta asignatura se ha impartido en los últimos años en el tercer curso de la Licenciatura de Administración y Dirección de Empresas (L.A.D.E.) en la Facultad de Ciencias Económicas y Empresariales de la U.P.V. Esta publicación recoge los problemas resueltos propuestos en los exámenes de las distintas convocatorias entre los años 2005 y 2010. El temario oficial de la asignatura desglosado por temas es el siguiente: Programación lineal entera 1.1 Formulación de problemas de Programación Lineal Entera. 1.2 Método de ramificación y acotación (Branch and Bound). 1.3 Otros métodos de resolución. Programación multiobjetivo y por metas 2.1 Introducción a la Programación Multiobjetivo. 2.2 Programación por metas. 2.3 Programación por prioridades. Modelos en redes 3.1 Conceptos básicos. 3.2 Problema del árbol de expansión minimal. 3.3 Problema del camino más corto. 3.4 Problema del camino más largo. 3.5 Problema del flujo máximo. 3.6 Problema de asignación. 3.7 Planificación de Proyectos: Métodos C.P.M. y P.E.R.T.
Referencias Bibliográficas: EPPEN, G.D. ; GOULD, F. J. ; SCHMIDT, C. P.; MOORE, J. H.; WEATHERFORD, L.R. (2000): “Investigación de Operaciones en la Ciencia Administrativa”. Ed. Pearson Educación. México. HILLIER, F.; LIEBERMAN, G.J. (2008): "Introducción a la Investigación de Operaciones", 8ª edición. Ed. McGraw-Hill. México. MATHUR, K. ; SOLOW, D. (1998): "Investigación de Operaciones. El arte de la toma de decisiones". Ed. Prentice-Hall Hispanoamericana, S.A. México. RIOS, S. (1988): "Investigación Operativa. Optimización". Ed. Centro de Estudios Ramón Areces. Madrid. TAHA, H.A. (2004): "Investigación de Operaciones, una Introducción", 7ª edición. Ed. Prentice Hall. México. WINSTON, W.L. (2004): "Investigación de Operaciones. Aplicaciones y Algoritmos", 4ª edición. Ed. Thompson. Madrid. YIH-LONG CHANG. (2003): "WinQSB Versión 2.0". Ed. John Wiley & Sons, Inc.
1. INVESTIGACION OPERATIVA (3º LADE) Extraordinario Febrero 2005 (10 puntos) Una inmobiliaria desea promocionar una nueva urbanización mediante una campaña publicitaria. Para ello dispone de 5 tipos de anuncios: anuncios en televisión local al mediodía (tvm), anuncios en televisión local a la noche (tvn), anuncios en periódico local (per), anuncios en suplemento dominical local (sup) y anuncios en radio local por la mañana (rad). La empresa ha reunido datos sobre la cantidad de clientes potenciales a los que se destina cada tipo de anuncio y el coste de cada anuncio en euros. Además, se ha llevado a cabo una valoración de la calidad que tiene cada anuncio de acuerdo al medio en el que se expone, en una escala de 0 a 100 (0 nula, 100 excelente). Los datos se recogen en la siguiente tabla: Anuncios Clientes Coste Calidad Potenciales (euros) exposición tvm tvn per sup rad 1000 2000 1500 2500 300 1500 3000 400 1000 100 65 90 40 60 20 El número máximo de anuncios que se pueden emitir es 15, 10, 25, 4 y 30 de tvm, tvn, per, sup y rad, respectivamente. La inmobiliaria, aconsejada por una agencia de publicidad, decide utilizar al menos 10 anuncios en la televisión, alcanzar por lo menos 50000 clientes potenciales, no gastar más de 18000 euros en anuncios en televisión y si se hacen anuncios en el periódico entonces no hacer anuncios en la televisión por la noche. El presupuesto máximo para la campaña publicitaria es de 30000 euros. Modelizar, sin resolver, mediante programación lineal entera el problema de cómo debe planificar la campaña si se desea maximizar la calidad de la exposición de todos los anuncios de la campaña publicitaria. 3
? ? ? ? ? 2. – + + + + – ? + – ? + – ? + – ? – s.a Solución: Definimos las variables de decisión siguientes: x1 = número de anuncios a emitir en tvm x2 = número de anuncios a emitir en tvn x3 = número de anuncios a emitir en per x4 = número de anuncios a emitir en sup x5 = número de anuncios a emitir en rad ?1 si se hacen anuncios per y = ? ?0 en caso contrario La modelización queda como sigue: Max ( 65×1 + 90 x2 + 40 x3 + 60 x4 + 20 x5 ) ? x1 = 15 ? x4 = 4 ? x5 = 30 ? x1 + x2 = 10 ?1000 x1 + 2000 x2 + 1500 x3 + 2500 x4 + 300 x5 = 50000 s.a ?1500 x1 + 3000 x2 = 18000 ?1500 x1 + 3000 x2 + 400 x3 + 1000 x4 + 100 x5 = 30000 ? x3 = 25 y ? x2 = 10 (1- y ) ? xi = 0 y enteras i = 1,…,5 ? y = 0 , 1 (10 Puntos) Resolver el problema siguiente. Min L ( y1 , y2 , y4 , y3 ) ? x1 + 2 x2 – y1 + y1 = 8 (1) ? x1 – x2 – y2 + y2 = -1 (2) ? x1 + x2 – y3 + y3 = 4 (3) ? x2 – y4 + y4 = 2 (4) ? yi = 0, yi+ = 0 i = 1,? , 5 ? ? x1 = 0, x2 = 0 4
? ?? 1 1 ? ? ? ? + ? ? – s.a ?? 1 1 ? 1 1 2 ? 2 ? ? ? – + ? ? ? ? – + ? ? ? – s.a ?? 1 1 ? 2 2 4 4 ? 4 Solución: – P1 = Min ( y1 ) ? x1 + 2 x2 – y+ + y- = 8 (1) ? s.a ? x1 = 0, x2 = 0 ? – + ? y1 = 0, y1 = 0 Soluciones óptimas: Valor óptimo: 0 + P2 = Min ( y2 ) ? x1 + 2 x2 – y+ + y- = 8 (1) ? ? x1 = 0, x2 = 0 ? ? y- = 0, y+ = 0 ? ? x1 – x2 – y2 + y- = -1 (2) ? y2 = 0, y+ = 0 Soluciones óptimas: ? A ? B Valor óptimo: 0 + P3 = Min ( y4 ) ? x1 + 2 x2 – y+ + y- = 8 (1) ? ? x1 = 0, x2 = 0 ? y1 = 0, y1 = 0 ? x1 – x2 – y+ + y- = -1 (2) ? y2 = 0, y2 = 0 ? ? x2 – y+ + y- = 2 (4) ? y4 = 0, y+ = 0 Solución óptima: (2,3) Valor óptimo: 1 5
? ? ? – + ? ? ? – + ? ? ? – ? ? ? ? – + ?? 1 1 2 2 ? 4 4 4 3 3 ? + P4 = Min ( y3 ) s.a ? x1 + 2 x2 – y+ + y- = 8 ? ? x1 = 0, x2 = 0 ? y1 = 0, y1 = 0 ? x1 – x2 – y+ + y- = -1 ? ? y2 = 0, y2 = 0 ? ? x2 – y+ + y- = 2 ? y4 = 0, y+ = 1 ? ? x1 + x2 – y+ + y- = 4 ? y3 = 0, y3 = 0 (1) (2) (4) (3) Solución óptima: (2,3) Valor óptimo: 1 Conclusión: la solución óptima es (2,3). En las metas 1ª y 2ª no hay ni exceso ni + – + – defecto ( y1 = 0, y1 = 0, y2 = 0, y2 = 0) . En la meta 3ª y en la 4ª hay un exceso + – + – de 1 ( y3 = 1, y3 = 0, y4 = 1, y4 = 0) . 3. La directora de un centro educativo debe asignar la docencia de 5 asignaturas, A1, A2, A3, A4 y A5 a 4 profesores, P1, P2, P3 y P4 teniendo en cuenta las valoraciones de las encuestas hechas por los alumnos y unas restricciones impuestas por un nuevo reglamento. En base a las encuestas de años anteriores, se tienen las siguientes valoraciones promedios (escala: 0 mala, 5 excelente): 6
a) a) ? ? A1 A2 A3 A4 A5 P1 P2 P3 P4 2.7 2 3.2 2.6 2.2 3.6 3.8 2.5 3.4 3.4 2.3 1.8 2.8 2.8 1.9 4.2 3.6 3.6 2.6 3.5 El nuevo reglamento dice que el profesor P3 no puede impartir las asignaturas A1 y A2. Las asignaturas no se pueden compartir y se han de impartir todas. Ningún profesor puede quedar sin asignaturas. Al profesor P1 solamente se le debe asignar una asignatura. (5 puntos) Modelizar como un problema de programación lineal entera con el objetivo de obtener la asignación que maximice la valoración media total. b) (5 puntos) Indicar a qué tabla habría que aplicar el método húngaro para determinar la asignación óptima. Solución: Definimos las variables de decisión siguientes: ?1 xij = ? ?0 si al profesor i se le asigna la asignatura j en caso contrario con i=1,…,4 y j=1,…,5 La modelización queda como sigue: Max ( 2.7×11 + 2.2×12 + … + 3.6×15 + 2 x21 + 3.6×22 + … + 3.6×25 + … + 3.5×45 ) ? x11 + x12 + x13 + x14 + x15 = 1 ?1 = xi1 + xi 2 + xi 3 + xi 4 + xi 5 = 2 i = 2, 3, 4 ? x1 j + x2 j + x3 j + x4 j = 1 j = 1,…,5 s.a ? ? x31 = 0 ? x32 = 0 ? xij = 0, 1 i = 1,…, 4 j = 1,…, 5 b) Aplicaremos el Método Húngaro a la siguiente tabla: 7
4. a) A1 A2 A3 A4 A5 F F P1 P2 P2 P3 P3 P4 P4 -2.7 -2 -2 M M -2.6 -2.6 -2.2 -3.6 -3.6 M M -2.5 -2.5 -3.4 -3.4 -3.4 -2.3 -2.3 -1.8 -1.8 -2.8 -2.8 -2.8 -1.9 -1.9 -4.2 -4.2 -3.6 -3.6 -3.6 -2.6 -2.6 -3.5 -3.5 M M 0 M 0 M 0 M M 0 M 0 M 0 Con M positivo suficientemente grande. La siguiente red representa un proyecto donde el valor de cada arco indica la duración de cada actividad en días: 3 5 3 4 4 7 2 t(1,3) 5 7 1 4 2 8 5 5 8 t(8,9) 9 t(1,6) 8 6 7 5 (4 puntos) Determinar para qué valores de t(1,3), t(1,6) y t(8,9) se cumplen las tres condiciones siguientes: La duración prevista del proyecto es de 23 días. La actividad (2,6) es crítica. El margen de la actividad (3,4) es 4. b) (6 puntos) Hallar el (los) camino(s) crítico(s) del proyecto y la tabla de actividades para los valores obtenidos en a) 8
Solución: a) Dado que la actividad (2,6) es crítica y P (6 ) = Max {12, t (1, 6)} , se tiene que P ( 6) = 12 y en consecuencia t (1, 6) = 12. Como la duración prevista del proyecto (d.p.p.) es de 23 días y la actividad (2,6) es crítica, se sabe que: 23=12+7+ t (8,9). Luego t (8,9) = 4. Dado que el margen de la actividad (3,4) es M (3, 4) = Q ( 4) – P (3) – t (3, 4) , se tiene que 4 = 16 – P (3) – 3 y por tanto P (3) = 9 . Como P (3) = Max {9, t (1,3)} = 9 entonces t (1,3) = 9. 3 9 3 4 12 5 7 20 10 16 21 t(1,3) 5 4 7 2 0 4 4 8 13 5 19 t(8,9)=4 23 1 0 t(1,6) 2 4 8 5 6 14 12 7 8 5 19 9 23 12 b) Si t (1, 6) < 12 , el camino crítico es (1,2,6,8,9). Si t (1, 6) = 12 los caminos críticos son (1,2,6,8,9) y (1,6,8,9). La tabla de actividades correspondiente a este proyecto es: 9
(i,j) (1,2) (1,3) (1,6) (2,3) (2,5) (2,6) (3,4) (3,5) (4,7) (5,7) (5,8) (6,8) (6,9) (7,9) (8,9) t(i,j) 4 t(1,3) t(1,6) 5 8 8 3 4 5 7 5 7 5 2 4 CMT(i,j) 0 0 0 4 4 4 9 9 12 13 13 12 12 20 19 FMT*(i,j) 4 10 12 10 14 12 16 14 21 21 19 19 23 23 23 M(i,j) 0* 10- t(1,3) 12- t(1,6) 1 2 0* 4 1 4 1 1 0* 6 1 0* Donde: t (i, j ) es la duración de la actividad (i, j ) CMT (i, j ) es el comienzo más temprano de la actividad (i, j ) FMT * (i, j ) es el final más tardío de la actividad (i, j ) M (i, j ) es el margen de la actividad (i, j ) 10
1. a) INVESTIGACION OPERATIVA (3º LADE) Junio 2005 Una empresa de juguetes está considerando la puesta en marcha de tres nuevos modelos de juguetes (1, 2 y 3) para su posible inclusión en la próxima campaña de Navidad. La preparación de instalaciones para la fabricación de estos modelos costaría 25000 €, 35000 € y 30000 € respectivamente, y la ganancia unitaria sería de 10 €, 15 € y 13 € respectivamente. La empresa dispone de tres plantas de producción para la elaboración de estos modelos, pero para evitar gastos sólo en una de ellas se producirían los juguetes, dependiendo la elección de la maximización de las ganancias. El número de horas que se precisa para producir cada juguete en cada planta es: juguete 1 juguete 2 juguete 3 planta 1 planta 2 planta 3 5 4 3 4 2 3 6 2 2 Las plantas disponen al día 500, 600 y 630 horas de producción respectivamente. La gerencia ha decidido desarrollar al menos uno de los tres juguetes. (8 puntos) Modelizar el problema utilizando programación lineal entera para maximizar el beneficio total. b) (2 puntos) La empresa decide producir únicamente el juguete tipo 3, pero debe tener en cuenta que si produce más de 50 unidades de este tipo de juguete entonces: el coste de preparación de instalaciones del juguete tipo 3 es de 40000 € debe producir en la planta 3 Modelizar el problema, añadiendo esta información, utilizando programación lineal entera. 11
a) ? ? ? 1 2 3 ? i ? ? ? ? ? 1 2 3 ? Solución: Definimos las variables de decisión siguientes: xi = número de juguetes producidos diariamente del tipo i i=1,2,3 ?1 yi = ? ?0 si se pone en marcha el juguete tipo i en caso contrario i = 1, 2, 3 ?1 z j = ? ?0 si se produce en la planta j en caso contrario j = 1, 2, 3 La modelización queda como sigue: Max(10 x1 – 25000 y1 + 15×2 – 35000 y2 + 13×3 – 30000 y3 ) ? y1 + y2 + y3 = 1 ? xi = Myi i = 1, 2, 3 ?5 x1 + 4 x2 + 6 x3 = 500 + M (1 – z1 ) ?4 x1 + 2 x2 + 2 x3 = 600 + M (1 – z2 ) s.a ?3×1 + 3×2 + 2 x3 = 630 + M (1 – z3 ) ? z + z + z = 1 ? xi = 0 y enteras i =1, 2, 3 ? y = 0, 1 i =1, 2, 3 ? z j = 0, 1 j =1, 2, 3 Con M positivo suficientemente grande. ?1 b) Definimos la variable de decisión siguiente: p = ? ?0 La modelización queda como sigue: Max (13×3 – 30000(1 – p) – 40000 p ) ?51 p = x3 = 50 (1 – p ) + Mp ? p = z3 ?6 x3 = 500 + M (1 – z1 ) ?2 x3 = 600 + M (1 – z2 ) s.a ?2 x3 = 630 + M (1 – z3 ) ? z + z + z = 1 ? x3 = 0 y entera ? ? p = 0, 1 ? zi = 0, 1 i =1,2,3 Con M positivo suficientemente grande. 12 si x3 = 51 en caso contrario
• • • ? ? ? ? ? ? ? – (5) (6) (2) (1) (3) (4) ?? 1 1 ? i? 2. En una industria panadera se quiere introducir la elaboración de dos nuevos tipos de pan: integral y de centeno, ya que se tiene asegurada la venta de su producción. Estos panes se elaboran principalmente a base de tres ingredientes: salvado integral, harina de trigo y harina de centeno. Para elaborar 1 kg de pan integral se necesitan 350 g de salvado integral y 150 g de harina de trigo y para la elaboración de 1 kg de pan de centeno se necesitan se necesitan 250 g de harina de trigo y 250 g de harina de centeno. La disponibilidad diaria de salvado integral es de 210 kg, 115 kg de harina de trigo y 100 kg de harina de centeno. El beneficio que deja cada kg de pan integral es de 0.40 € y 0.60 € cada kg de pan de centeno. Calcular la elaboración diaria de pan integral y de centeno, si se han puesto las siguientes metas por orden de prioridad: Prioridad 1. Se desea obtener un beneficio de al menos 240 € diarios. Prioridad 2. Se desea que la cantidad elaborada diariamente de pan integral sea al menos el doble que la de centeno. Prioridad 3. Se desea que la cantidad elaborada diariamente de pan de centeno no sea inferior a 300 kg. ¿Qué metas de las propuestas se han cumplido? Solución: Definimos las variables de decisión siguientes: x1 = kg de pan integral elaborado diariamente x2 = kg de pan de centeno elaborado diariamente La modelización queda como sigue: – – – Min L( y1 , y2 , y3 ) ?0.35 x1 = 210 ? ?0.25 x2 = 100 ?0.15×1 + 0.25×2 = 115 ? ?0.4 x1 + 0.6 x2 – y+ + y- = 240 s.a ? + – ?x1 – 2 x2 – y2 + y2 = 0 ? + – ?x2 – y3 + y3 = 300 ?x1 = 0, x2 = 0 ? yi = 0, y+ = 0 i = 1, 2,3 13
? ? ? ? ?? ? ? ? ? ? ? – + ? ? ? – + ?? 1 1 ? 2 2 ? El conjunto X de soluciones factibles del problema es: – P1 = Min ( y1 ) s.a ?0.35 x1 = 210 ? ?0.25 x2 = 100 ?0.15 x1 + 0.25 x2 = 115 ? + – ?0.4 x1 + 0.6 x2 – y1 + y1 = 240 ? x1 = 0, x2 = 0 ? – + ? y1 = 0, y1 = 0 (1) (2) (3) (4) – P2 = Min ( y2 ) Soluciones óptimas: Valor óptimo: 0 ? A s.a ?0.35 x1 = 210 ? ?0.25 x2 = 100 ?0.15×1 + 0.25×2 = 115 ? ?0.4 x1 + 0.6 x2 – y+ + y- = 240 ? ?x1 = 0, x2 = 0 ? y1 = 0, y1 = 0 ? ?x1 – 2 x2 – y+ + y- = 0 ? y2 = 0, y2 = 0 14 (1) (2) (3) (4) (5)
? ? ? ? ? – + ? ? ? – + ? ? ? ? ? – + ?? 1 1 ? 2 2 ? – P3 = Min ( y3 ) Soluciones óptimas: Valor óptimo: 0 ? B s.a ?0.35 x1 = 210 ? ?0.25 x2 = 100 ?0.15 x1 + 0.25 x2 = 115 ? ?0.4 x1 + 0.6 x2 – y+ + y- = 240 ? ? x1 = 0, x2 = 0 ? y1 = 0, y1 = 0 ? ? x1 – 2 x2 – y+ + y- = 0 ? y2 = 0, y2 = 0 ? + – ? x2 – y3 + y3 = 300 ? y3 = 0, y3 = 0 (1) (2) (3) (4) (5) (6) Solución óptima: (418.182, 209.091) Valor óptimo: 90.909 La solución óptima consiste en elaborar diariamente 418.182 kg de pan integral y 209.091 kg de pan de centeno. El beneficio diario es 292.73€ + – ( y1 = 52.7274, y1 = 0), la producción de pan integral es exactamente el doble que + – la producción de pan de centeno ( y2 = 0, y2 = 0), y la producción de este último – + es aproximadamente 209kg diarios ( y3 = 90.909, y3 = 0). Se cumplen, por lo tanto, la 1ª y la 2ª meta y no la 3ª. 15
3. a) a) Se considera el siguiente grafo: 3 2 5 9 1 a 7 1 4 4 2 7 1 4 3 2 6 6 4 (5 puntos) Si los valores de cada arco representan distancias, hallar razonadamente cómo debe ser a para que la ruta más corta del nodo 1 al 7 pase obligatoriamente por el nodo 2. Indicar esta ruta más corta. b) (5 puntos) Si a = 5 y los valores de los arcos representan capacidades de flujo, calcular el valor del flujo máximo del nodo 1 al 7. Solución: Los caminos del nodo 1 al nodo 7 pasan bien por el nodo 2, por el 3 o por el 4. Aplicando el método de la ruta más corta, calculamos los caminos más cortos desde cada uno de estos nodos al nodo 7. En el siguiente grafo se observa que el camino más corto del nodo 2 al nodo 7 es (2,4,6,7) cuyo valor es 8. 3 2 0 5 3 9 1 4 2 4 1 7 8 1 2 6 3 3 4 6 2 16
En el siguiente grafo se observa que el camino más corto del nodo 3 al nodo 7 es (3,6,7) cuyo valor es 10. 5 6 2 9 7 6 10 3 0 4 6 4 En el siguiente grafo se observa que el camino más corto del nodo 4 al nodo 7 es (4,6,7) cuyo valor es 7. 4 5 3 2 9 4 0 7 7 1 2 6 3 2 4 6 1 Luego necesariamente la ruta más corta del nodo 1 al nodo 7 debe ser alguna de las siguientes: (1,2,4,6,7) cuyo valor es a+8. (1,3,6,7) cuyo valor es 14. (1,4,6,7) cuyo valor es 14. Para que la ruta más corta pase obligatoriamente por el nodo 2 se debe cumplir que a + 8 < 14. Luego a < 6, y la ruta más corta es (1,2,4,6,7). Si a = 6 las 3 rutas anteriores tienen el mismo valor. 17
b) Partimos del flujo nulo: 3,0 2 5 5,0 7,0 1,0 4,0 2,0 9,0 1 4,0 3 2,0 4 1,0 6 6,0 7 4,0 Consideramos la cadena de crecimiento del origen al destino (1,2,5,7). ? f (1, 2,5, 7 ) = min {5,3,9} = 3 y llegamos al siguiente flujo cuyo valor es 3. 3,3 2 1,0 5 9,3 1 5,3 7,0 4 4,0 2,0 7 1,0 4,0 3 2,0 6 6,0 4,0 Consideramos la cadena de crecimiento (1,2,4,5,7). ? f (1, 2, 4,5, 7 ) = min {5 – 3,1, 4,9 – 3} = 1 y llegamos al siguiente flujo cuyo valor es 4. 18
3,3 2 1,1 5 9,4 1 5,4 7,0 4 4,1 2,0 7 1,0 4,0 3 2,0 6 6,0 4,0 Consideramos la cadena de crecimiento (1,3,6,7). ? f (1,3, 6, 7 ) = min {4, 4, 6} = 4 y llegamos al siguiente flujo cuyo valor es 8. 3,3 2 1,1 5 9,4 1 5,4 7,0 4 4,1 2,0 7 1,0 4,4 3 2,0 6 6,4 4,4 Consideramos la cadena de crecimiento (1,4,5,7). ? f (1, 4,5, 7 ) = min {7, 4 – 1,9 – 4} = 3 y llegamos al siguiente flujo cuyo valor es 11. 19
3,3 2 1,1 5 9,7 1 5,4 7,3 4 4,4 2,0 7 1,0 4,4 3 2,0 6 6,4 4,4 Consideramos la cadena de crecimiento (1,4,6,7). ? f (1, 4, 6, 7 ) = min {7 – 3,1,6 – 4} = 1 y llegamos al siguiente flujo cuyo valor es 12. 3,3 2 1,1 5 9,7 1 5,4 7,4 4 4,4 2,0 7 1,1 4,4 3 2,0 6 6,5 4,4 No existe ninguna cadena de crecimiento del nodo 1 al nodo 7. Luego este flujo es un flujo máximo, cuyo valor es V f = 12 . 4. Se considera un proyecto formado por 11 actividades. La tabla siguiente recoge dichas actividades, su duración en días y las relaciones de precedencia entre las mismas: 20
Actividad Duración Precedentes Inmediatas A B C D E F G H I J K 2 2 6 TD 1 2 4 TH 2 2 3 — — A A B B D, E D, E F, H G, I, C F, H a) (3 puntos) Elaborar un grafo que represente a dicho proyecto. b) (5 puntos) Sabiendo que las actividades críticas del proyecto son A, C, D, G, H, I y J calcular la duración prevista del proyecto, los caminos críticos y las duraciones de las actividades D y H. c) (2 puntos) Calcular el margen de las actividades no críticas. Solución: a) La siguiente red representa a este proyecto: C 1 A 2 E D 4 G H 6 I J 7 B K 3 F 21 5
b) 2 C (6) 6 J J (2) A (2) D (TD) G (4) 1 4 H (TH) I (2) 7 E (1) B (2) K (3) 3 F (2) 5 Si A, C, D, G, H, I, y J son críticas entonces: Caminos críticos: (1,2,6,7), (1,2,4,6,7) y (1,2,4,5,6,7) Duración prevista del proyecto (d.p.p.): Valor del camino (1,2,6,7) = 2 + 6 + 2 = 10 días. Duración de la actividad D: 2 + TD + 4 + 2 = 10 ? TD = 2 días. Duración de la actividad H: 2 + TD + TH + 2 + 2 = 2 + 2 + TH + 2 + 2 = 10 ? TH = 2 días c) 2 2 C (6) 6 J 8 J (2) A (2) 2 D (2) 8 1 0 0 4 4 4 H (2) G (4) I (2) 7 10 10 B (2) 3 2 E (1) F (2) 5 6 K (3) 3 22 6
M(i,j)=FMT*(i,j)-CMT(i,j)-t(i,j)=Q(j)-P(i)-t(i,j) M(1,3)=3-0-2=1 día M(3,4)=4-2-1=1 día M(3,5)=6-2-2=2 días M(5,7)=10-6-3=1 día 23
1. xi = ? ?1 ?0 INVESTIGACION OPERATIVA (3º LADE) Septiembre 2005 (10 puntos) Una universidad se encuentra en un proceso de formar una comisión. Diez personas han sido nominadas: A, B, C, D, E, F, G, H, I y J. El reglamento obliga a que sean incluidos en dicha comisión al menos una mujer, un hombre, un estudiante, un administrativo y un profesor. Además, el número de mujeres debe ser igual que el de hombres y el número de profesores no debe de ser inferior al de administrativos. La mezcla de los nominados en las siguientes categorías es como sigue: Categoría Mujeres Hombres Estudiantes Administrativos Profesores Personas A, B, C, D, E F, G, H, I, J A, B, C, J E, F D, G, H, I Modelizar sin resolver como un problema de programación lineal entera, si se trata de que la comisión sea lo más reducida posible. Solución: Definimos las variables de decisión siguientes: si se incluye la persona i en la comisión en caso contrario La modelización queda como sigue: 24 i = A, B, C, D, E, F, G, H, I, J
? s.a ? E ? 2. ? Min( xA + xB + xC + xD + xE + xF + xG + xH + xI + xJ ) ? xA + xB + xC + xD + xE = 1 ? xF + xG + xH + xI + xJ = 1 ? xA + xB + xC + xJ = 1 ? x + xF = 1 ? xD + xG + xH + xI = 1 ? xA + xB + xC + xD + xE = xF + xG + xH + xI + xJ ? xD + xG + xH + xI = xE + xF ? xi = 0, 1 i=A, B, C , D, E, F , G, H , I , J El director de personal de una empresa debe asignar 5 tareas (T1, T2, T3, T4 y T5) a 4 empleados (E1, E2, E3 y E4) teniendo en cuenta las valoraciones hechas en base a experiencias anteriores que muestran la siguiente tabla (puntuación: 0 mala, 10 excelente, “–” imposibilidad): T1 T2 T3 T4 T5 E1 E2 E3 E4 6 2 5 2 8 3 6 3 9 — 8 7 3 4 9 8 7 — 6 6 Además, hay que tener en cuenta las siguientes restricciones: los empleados no pueden quedarse sin tarea, al empleado E2 sólo se le puede asignar una tarea, y las tareas no se pueden compartir. a) (5 puntos) Modelizar como un problema de programación lineal entera. b) (5 puntos) Encontrar una solución óptima aplicando el Método Húngaro. Solución: a) Definimos las variables de decisión siguientes: ?1 xij = ? ?0 si se asigna al empleado Ei la tarea Tj en caso contrario i = 1, 2, 3, 4, 5; j=1, 2, 3, 4 La modelización queda como sigue: 25
? ? ? Max (6 x11 + 8 x12 + 9 x13 + 3×14 + 7 x15 + 2 x21 + 3×22 + 4 x24 + +5×31 + 6 x32 + 8 x33 + 9 x34 + 6 x35 + 2 x41 + 3×42 + 7 x43 + 8 x44 + 6 x45 ) ?1 = xi1 + xi 2 + xi3 + xi 4 + xi 5 = 2 i = 1,3, 4 ? x21 + x22 + x23 + x24 + x25 = 1 s.a ? x1 j + x2 j + x3 j + x4 j = 1 j = 1,…,5 ? ? x23 = x25 = 0 ? xij = 0,1 i = 1, 2,3, 4 j = 1,…,5 b) Aplicamos el Método Húngaro a la siguiente tabla: T1 T2 T3 T4 T5 F1 F2 E1 E1 E2 E3 E3 E4 E4 -6 -6 -2 -5 -5 -2 -2 -8 -8 -3 -6 -6 -3 -3 -9 -9 M -8 -8 -7 -7 -3 -3 -4 -9 -9 -8 -8 -7 -7 M -6 -6 -6 -6 M 0 M M 0 M 0 M 0 M M 0 M 0 ? +6 ? +8 ? +9 ? +9 ? +7 Con M positivo suficientemente grande. T1 T2 T3 T4 T5 F1 F2 E1 E1 0 0 0 0 0 0 6 6 0 0 M 0 M 0 E2 E3 E3 E4 E4 4 1 1 4 4 5 2 2 5 5 M 1 1 2 2 5 0 0 1 1 M 1 1 1 1 M M 0 M 0 M M 0 M 0 ? -4 ? -1 Con M positivo suficientemente grande. 26
3. + – – – + – + – + – ? + + – ? 1 – ? i T1 T2 T3 T4 T5 F1 F2 E1 E1 E2 E3 E3 E4 E4 0 0 0 1 1 3 4 0 0 1 2 2 4 5 0 0 M 1 1 1 2 6 6 1 0 0 0 1 0 0 M 1 1 0 1 M 0 M M 0 M 0 M 0 M M 0 M 0 Con M positivo suficientemente grande. Asignación óptima: E1 ? T2 y T3, E2 ? T1, E3? T4, E4 ? T5. Valor óptimo: 8+9+2+9+6 = 34 puntos. (10 puntos) Resuelve: Min L( y1 , y2 , y3 , y4 ) s.a ? x1 + x2 = 100 ? ?20 x1 + 8 x2 – y1 + y1 = 1600 ? ? x1 – x2 – y2 + y2 = 0 ? ? x2 – y3 + y3 = 45 ? y3 – y4 + y4 = 15 ? x = 0, x2 = 0 ? yi = 0, y + = 0 i = 1,…, 4 (1) (2) (3) (4) (5) Solución: El conjunto X de soluciones factibles del problema es: 27
? ? ? s.a ?? 1 1 ? ? ? ? + ? s.a ?? 1 1 2 ? + P1 = Min ( y1 ) ? x1 + x2 = 100 (1) ? ?20 x1 + 8 x2 – y+ + y- = 1600 (2) ? ? x1 = 0, x2 = 0 ? – + ? y1 = 0, y1 = 0 Soluciones óptimas: Valor óptimo: 0 – P2 = Min ( y2 ) ?x1 + x2 = 100 (1) ? ?20 x1 + 8×2 – y+ + y- = 1600 (2) ? ?x1 = 0, x2 = 0 ? – + ? y1 = 0, y1 = 0 ? ?x1 – x2 – y2 + y- = 0 (3) ? – + ? y2 = 0, y2 = 0 Soluciones óptimas: Valor óptimo: 0 28 ? A ? B
? ? ? – ? + ? ? – + ? ? ? ?? 1 1 1 2 3 3 ? ? ? ? – ? ? ? ? ? – ? ? + + ? ? – (2) (1) (4) (5) (3) ?? 1 1 1 2 2 ? 3 4 ? 4 – P3 = Min ( y3 ) s.a ? x1 + x2 = 100 ? ?20 x1 + 8×2 – y+ + y- = 1600 ? ? x1 = 0, x2 = 0 ? y1 = 0, y+ = 0 ? ? x1 – x2 – y2 + y- = 0 ? y2 = 0, y2 = 0 ? x2 – y+ + y- = 45 ? – + ? y3 = 0, y3 = 0 (1) (2) (3) (4) Soluciones óptimas: ? C Valor óptimo: 0 – P4 = Min ( y4 ) ? x1 + x2 = 100 ? ?20 x1 + 8×2 – y+ + y- = 1600 ? ? x1 = 0, x2 = 0 ? y1 = 0, y+ = 0 ? ? x1 – x2 – y+ + y- = 0 s.a ? – + ? y2 = 0, y2 = 0 ? + – ? x2 – y3 + y3 = 45 ? y3 = 0, y+ = 0 ? y3 – y4 + y- = 15 ? y4 = 0, y+ = 0 Solución óptima: (50, 50) Valor óptimo: 10 Solución óptima: + – + – x1 = 50, x2 = 50, y1 = 0, y1 = 200, y2 = 0, y2 = 0, + – + – y3 = 5, y3 = 0, y4 = 0, y4 = 10 29
4. i) ii) iii) (10 puntos) En la siguiente tabla se muestran el conjunto de actividades que componen un proyecto, así como su duración en días y las relaciones de precedencia entre las mismas. Actividad Duración Precedentes Inmediatas A B C D E F G H I J 3 2 6 2 3 3 5 1 1.5 2 – A A C A B C C F, H I a) Construir un grafo asociado al proyecto y hallar la duración prevista del proyecto. b) Elaborar la tabla de actividades del proyecto. c) Responder a las siguientes preguntas. ¿Qué ocurre con la duración del proyecto si la actividad I se retrasa 2 días? ¿Cuántos días se puede retrasar la actividad D sin que afecte a la duración prevista del proyecto? ¿Qué duración debería tener la actividad B para que fuese una actividad crítica, si la duración de las demás actividades se mantiene fija? 30
Esta presentación contiene mas diapositivas disponibles en la version de descarga