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