Ejercicios Resueltos de Investigagion Operativa PDF
Ejercicios Resueltos de Investigagion Operativa PDF
Ejercicios Resueltos de Investigagion Operativa PDF
resueltos de
investigacin
operativa
Exmenes propuestos en la
Facultad de Ciencias Econmicas
y Empresariales
ISBN: 978-84-694-5889-1
www.mundoindustrial.net
ndice
Introduccin
Exmenes ao 2005
Extraordinario Febrero .............................................................................................3
Convocatoria Junio ................................................................................................11
Convocatoria Septiembre ......................................................................................24
Exmenes ao 2006
Extraordinario Febrero ..........................................................................................33
Convocatoria Junio ...............................................................................................43
Convocatoria Septiembre .......................................................................................51
Exmenes ao 2007
Extraordinario Febrero ...........................................................................................60
Convocatoria Junio ...............................................................................................71
Convocatoria Septiembre .......................................................................................81
Exmenes ao 2008
Extraordinario Febrero ..........................................................................................94
Convocatoria Junio ..............................................................................................103
Convocatoria Septiembre .....................................................................................113
Exmenes ao 2009
Extraordinario Febrero .........................................................................................122
Convocatoria Junio .............................................................................................132
Convocatoria Septiembre ....................................................................................142
Exmenes ao 2010
Extraordinario Febrero .........................................................................................153
Convocatoria Junio ..............................................................................................163
Convocatoria Septiembre .....................................................................................173
www.mundoindustrial.net
Introduccin
Esta publicacin recoge los problemas resueltos propuestos en los exmenes de las
3. Modelos en redes
Referencias Bibliogrficas:
YIH-LONG CHANG. (2003): "WinQSB Versin 2.0". Ed. John Wiley & Sons, Inc.
www.mundoindustrial.net
1. (10 puntos) Una inmobiliaria desea promocionar una nueva urbanizacin mediante
una campaa publicitaria. Para ello dispone de 5 tipos de anuncios: anuncios en
televisin local al medioda (tvm), anuncios en televisin local a la noche (tvn),
anuncios en peridico local (per), anuncios en suplemento dominical local (sup) y
anuncios en radio local por la maana (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. Adems, se ha llevado a cabo una valoracin 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:
El nmero mximo 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 televisin, alcanzar por lo
menos 50000 clientes potenciales, no gastar ms de 18000 euros en anuncios en
televisin y si se hacen anuncios en el peridico entonces no hacer anuncios en la
televisin por la noche. El presupuesto mximo para la campaa publicitaria es de
30000 euros. Modelizar, sin resolver, mediante programacin lineal entera el
problema de cmo debe planificar la campaa si se desea maximizar la calidad de
la exposicin de todos los anuncios de la campaa publicitaria.
3
www.mundoindustrial.net
Solucin:
Definimos las variables de decisin siguientes:
x1 = nmero de anuncios a emitir en tvm
x2 = nmero de anuncios a emitir en tvn
x3 = nmero de anuncios a emitir en per
Min L ( y1 , y 2+ , y 4+ , y3+ )
x + 2 x2 y1+ + y1 = 8 (1)
1
x1 x2 y 2+ + y 2 = 1 (2)
x1 + x2 y3+ + y3 = 4 (3)
s.a
x2 y 4+ + y 4 = 2 (4)
yi 0, yi+ 0 i = 1, , 5
x1 0, x2 0
4
www.mundoindustrial.net
Solucin:
P1 Min ( y1 )
+
x1 + 2 x2 y1 + y1 = 8 (1)
s.a x1 0, x2 0
y 0, y1+ 0
1
Soluciones ptimas: A
Valor ptimo: 0
P2 Min ( y2+ )
x + 2 x y + + y = 8 (1)
1 2 1 1
x 0, x2 0
1
+
s.a y1 = 0, y1 0
x1 x2 y2 + y2 = 1 (2)
+
+
y2 0, y2 0
Soluciones ptimas: B
Valor ptimo: 0
P3 Min ( y4+ )
x + 2 x y + + y = 8 (1)
1 2 1 1
x 0, x 0
1 2
+
y1 = 0, y1 0
+
s.a x1 x2 y2 + y2 = 1 (2)
y 0, y + = 0
2 2
x y + + y = 2 (4)
2 4 4
y 0, y + 0
4 4
P4 Min ( y3+ )
x + 2 x y + + y = 8 (1)
1 2 1 1
x 0, x 0
1 2
+
y1 = 0, y1 0
+
x1 x2 y2 + y2 = 1 (2)
+
s.a y2 0, y2 = 0
x y + + y = 2 (4)
2 4 4
y 0, y + = 1
4 4
x + x y + + y = 4 (3)
1 2 3 3
+
y3 0, y3 0
de 1 ( y3+ = 1, y3 = 0, y4+ = 1, y4 = 0) .
A1 A2 A3 A4 A5
P1 2.7 2.2 3.4 2.8 3.6
P2 2 3.6 3.4 2.8 3.6
P3 3.2 3.8 2.3 1.9 2.6
P4 2.6 2.5 1.8 4.2 3.5
Solucin:
a) Definimos las variables de decisin siguientes:
1 si al profesor i se le asigna la asignatura j
xij = con i=1,,4 y j=1,,5
0 en caso contrario
La modelizacin queda como sigue:
Max ( 2.7x11 + 2.2x12 + ... + 3.6x15 + 2 x21 + 3.6x22 + ... + 3.6x25 + ... + 3.5x45 )
x11 + x12 + x13 + x14 + x15 = 1
1 x + x + x + x + x 2 i = 2, 3, 4
i1 i2 i3 i4 i5
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
7
www.mundoindustrial.net
A1 A2 A3 A4 A5 F F
P1 -2.7 -2.2 -3.4 -2.8 -3.6 M M
P2 -2 -3.6 -3.4 -2.8 -3.6 M M
P2 -2 -3.6 -3.4 -2.8 -3.6 0 0
P3 M M -2.3 -1.9 -2.6 M M
P3 M M -2.3 -1.9 -2.6 0 0
P4 -2.6 -2.5 -1.8 -4.2 -3.5 M M
P4 -2.6 -2.5 -1.8 -4.2 -3.5 0 0
Con M positivo suficientemente grande.
8
www.mundoindustrial.net
Solucin:
a)
Dado que la actividad (2,6) es crtica y P ( 6 ) = Max {12, t (1, 6 )} , se tiene
t ( 8,9 ) = 4.
9 12 20
3 5
3 4 7
10 16 21
2
t(1,3) 4
5 7
0 4 4 8 13 5 19 t(8,9)=4 23
1 2 5 8 9
0 4 14 19 23
8
t(1,6) 7
12
5
6
12
9
www.mundoindustrial.net
Donde:
t ( i, j ) es la duracin de la actividad ( i, j )
M ( i, j ) es el margen de la actividad ( i, j )
10
www.mundoindustrial.net
11
Solucin:
a) Definimos las variables de decisin siguientes:
xi = nmero de juguetes producidos diariamente del tipo i i=1,2,3
1 si se produce en la planta j
zj = j = 1, 2, 3
0 en caso contrario
La modelizacin queda como sigue:
Max(10 x1 25000 y1 + 15 x2 35000 y2 + 13 x3 30000 y3 )
y1 + y2 + y3 1
x My i = 1, 2, 3
i i
5 x1 + 4 x2 + 6 x3 500 + M (1 z1 )
4 x1 + 2 x2 + 2 x3 600 + M (1 z2 )
s.a 3 x1 + 3 x2 + 2 x3 630 + M (1 z3 )
z + z + z = 1
1 2 3
xi 0 y enteras i =1, 2, 3
y = 0, 1 i =1, 2, 3
i
z j = 0, 1 j =1, 2, 3
12
2. En una industria panadera se quiere introducir la elaboracin de dos nuevos tipos de
pan: integral y de centeno, ya que se tiene asegurada la venta de su produccin.
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 elaboracin 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 elaboracin 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?
Solucin:
Definimos las variables de decisin siguientes:
x1 = kg de pan integral elaborado diariamente
x2 = kg de pan de centeno elaborado diariamente
La modelizacin queda como sigue:
Min L( y1 , y2 , y3 )
0.35 x1 210 (1)
0.25 x2 100 (2)
0.15 x1 + 0.25 x2 115 (3)
0.4 x1 + 0.6 x2 y1+ + y1 = 240 (4)
s.a
x1 2 x2 y2+ + y2 = 0 (5)
x2 y3+ + y3 = 300 (6)
x1 0, x2 0
yi 0, yi+ 0 i = 1, 2,3
13
El conjunto X de soluciones factibles del problema es:
P1 Min ( y1 )
0.35 x1 210 (1)
0.25 x2 100 (2)
0.15 x + 0.25 x 115 (3)
1 2
s.a
0.4 x1 + 0.6 x2 y1+ + y1 = 240 (4)
x1 0, x2 0
y1 0, y1+ 0
Soluciones ptimas: A
Valor ptimo: 0
P2 Min ( y2 )
0.35 x1 210 (1)
0.25 x2 100 (2)
0.15 x1 + 0.25 x2 115 (3)
0.4 x1 + 0.6 x2 y1+ + y1 = 240 (4)
s.a
x1 0, x2 0
y1 = 0, y1+ 0
x1 2 x2 y2+ + y2 = 0 (5)
y2 0, y2+ 0
14
Soluciones ptimas: B
Valor ptimo: 0
P3 Min ( y3 )
0.35 x1 210 (1)
0.25 x2 100 (2)
0.15 x + 0.25 x 115 (3)
1 2
0.4 x + 0.6 x y + + y = 240 (4)
1 2 1 1
x 0, x2 0
1
s.a y = 0, y1+ 0
1
+
x1 2 x2 y2 + y2 = 0 (5)
y2 = 0, y2+ 0
+
x2 y3 + y3 = 300 (6)
y3 0, y3+ 0
Solucin ptima:
(418.182, 209.091)
Valor ptimo: 90.909
tanto, la 1 y la 2 meta y no la 3.
15
3. Se considera el siguiente grafo:
3
2 5
9
1
a
4
2
7
1 4 7
1
4
2
6
3 6
4
Solucin:
a) Los caminos del nodo 1 al nodo 7 pasan bien por el nodo 2, por el 3 o por el 4.
Aplicando el mtodo de la ruta ms corta, calculamos los caminos ms cortos
desde cada uno de estos nodos al nodo 7.
En el siguiente grafo se observa que el camino ms 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
4
3 3 6 2
16
En el siguiente grafo se observa que el camino ms corto del nodo 3 al nodo 7
es (3,6,7) cuyo valor es 10.
5 6 9
2
7 10
4
3 0 6 4
5 3 9
4
2
4 0 7 7
1
2 6
4
3 2 6 1
Luego necesariamente la ruta ms 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 ms corta pase obligatoriamente por el nodo 2 se debe cumplir
que a + 8 < 14. Luego a < 6, y la ruta ms 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
9,0
1,0
5,0
4,0
2,0
7,0
1 4 7
1,0
4,0
2,0
6,0
3 6
4,0
1,0
4,0
2,0
6,0
3 6
4,0
valor es 4.
18
3,3
2 5
9,4
1,1
5,4
4,1 2,0
7,0
1 4 7
1,0
4,0
2,0
6,0
3 6
4,0
4,4
2,0
6,4
3 6
4,4
es 11.
19
3,3
2 5
9,7
1,1
5,4
4,4 2,0
7,3
1 4 7
1,0
4,4
2,0
6,4
3 6
4,4
es 12.
3,3
2 5
9,7
1,1
5,4
4,4 2,0
7,4
1 4 7
1,1
4,4
2,0
6,5
3 6
4,4
20
Actividad Duracin Precedentes Inmediatas
A 2 --
B 2 --
C 6 A
D TD A
E 1 B
F 2 B
G 4 D, E
H TH D, E
I 2 F, H
J 2 G, I, C
K 3 F, H
Solucin:
a) La siguiente red representa a este proyecto:
C
2 6
J
D
A
G
I
1 4 7
H
E
B
K
3 5
F
21
b)
C (6)
J
2 6 J (2)
A (2) D (TD)
G (4)
4 I (2)
1 7
H (TH)
E (1)
B (2)
K (3)
3 5
F (2)
Duracin de la actividad H: 2 + TD + TH + 2 + 2 = 2 + 2 + TH + 2 + 2 = 10
TH = 2 das
c)
2 C (6) 8
J
2 6 J (2)
A (2) 2 D (2) 8
4 G (4)
0 10
4
1 I (2) 7
4 H (2)
0 10
E (1)
B (2) 2 6
K (3)
3 5
F (2)
3 6
22
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 da
M(3,4)=4-2-1=1 da
M(3,5)=6-2-2=2 das
M(5,7)=10-6-3=1 da
23
INVESTIGACION OPERATIVA (3 LADE)
Septiembre 2005
Categora Personas
Mujeres A, B, C, D, E
Hombres F, G, H, I, J
Estudiantes A, B, C, J
Administrativos E, F
Profesores D, G, H, I
Solucin:
Definimos las variables de decisin siguientes:
1 si se incluye la persona i en la comisin
xi = i = A, B, C, D, E, F, G, H, I, J
0 en caso contrario
La modelizacin queda como sigue:
24
Min( x A + xB + xC + xD + xE + xF + xG + xH + xI + xJ )
x A + xB + xC + xD + xE 1
x + x + x + x + x 1
F G H I J
x A + xB + xC + xJ 1
x + xF 1
s.a E
xD + xG + xH + xI 1
x A + xB + xC + xD + xE = xF + xG + xH + xI + xJ
xD + xG + xH + xI xE + xF
x = 0, 1 i =A, B, C , D, E , F , G, H , I , J
i
2. 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 (puntuacin: 0 mala,
10 excelente, -- imposibilidad):
T1 T2 T3 T4 T5
E1 6 8 9 3 7
E2 2 3 -- 4 --
E3 5 6 8 9 6
E4 2 3 7 8 6
Adems, hay que tener en cuenta las siguientes restricciones: los empleados no
pueden quedarse sin tarea, al empleado E2 slo se le puede asignar una tarea, y las
tareas no se pueden compartir.
a) (5 puntos) Modelizar como un problema de programacin lineal entera.
b) (5 puntos) Encontrar una solucin ptima aplicando el Mtodo Hngaro.
Solucin:
a) Definimos las variables de decisin siguientes:
1 si se asigna al empleado E i la tarea Tj
xij = i = 1, 2, 3, 4, 5; j=1, 2, 3, 4
0 en caso contrario
La modelizacin queda como sigue:
25
Max (6 x11 + 8 x12 + 9 x13 + 3 x14 + 7 x15 + 2 x21 + 3 x22 + 4 x24 +
+5 x31 + 6 x32 + 8 x33 + 9 x34 + 6 x35 + 2 x41 + 3 x42 + 7 x43 + 8 x44 + 6 x45 )
1 x + x + x + x + x 2 i = 1,3, 4
i1 i2 i3 i4 i5
21 22 23 24 25 = 1
x + x + x + x + x
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
T1 T2 T3 T4 T5 F1 F2
E1 0 0 0 6 0 M M
E1 0 0 0 6 0 0 0
E2 4 5 M 5 M M M -4
E3 1 2 1 0 1 M M
E3 1 2 1 0 1 0 0
E4 4 5 2 1 1 M M -1
E4 4 5 2 1 1 0 0
Con M positivo suficientemente grande.
26
T1 T2 T3 T4 T5 F1 F2
E1 0 0 0 6 0 M M
E1 0 0 0 6 0 0 0
E2 0 1 M 1 M M M
E3 1 2 1 0 1 M M
E3 1 2 1 0 1 0 0
E4 3 4 1 0 0 M M
E4 4 5 2 1 1 0 0
Con M positivo suficientemente grande.
Min L( y1+ , y2 , y3 , y4 )
x1 + x2 100 (1)
+
20 x1 + 8 x2 y1 + y1 = 1600 (2)
+
x1 x2 y2 + y2 = 0 (3)
s.a x2 y3+ + y3 = 45 (4)
+ +
y3 y4 + y4 = 15 (5)
x 0, x 0
1 2
y 0, y + 0 i = 1,..., 4
i i
Solucin:
El conjunto X de soluciones factibles del problema es:
27
P1 Min ( y1+ )
x1 + x2 100 (1)
20 x1 + 8 x2 y1+ + y1 = 1600 (2)
s.a
x1 0, x2 0
+
y1 0, y1 0
Soluciones ptimas: A
Valor ptimo: 0
P2 Min ( y2 )
x1 + x2 100 (1)
20 x + 8 x y + + y = 1600 (2)
1 2 1 1
x1 0, x2 0
s.a
y1 0, y1+ = 0
x1 x2 y2+ + y
2 =0 (3)
+
y2 0, y2 0
Soluciones ptimas: B
Valor ptimo: 0
28
P3 Min ( y3 )
x1 + x2 100 (1)
20 x1 + 8 x2 y1+ + y1 = 1600 (2)
x1 0, x2 0
+
y1 0, y1 = 0
s.a
x1 x2 y2+ + y 2 =0 (3)
y2 = 0, y2+ 0
x y + + y = 45 (4)
2 3 3
y3 0, y3 0
+
Soluciones ptimas: C
Valor ptimo: 0
P4 Min ( y4 )
x1 + x2 100 (1)
20 x + 8 x y+ + y = 1600 (2)
1 2 1 1
x1 0, x2 0
y 0, y + = 0
1 1
x x y + + y = 0 (3)
1 2 2 2
s.a +
y2 = 0, y2 0
x2 y3+ + y3 = 45 (4)
y = 0, y + 0
3 3
y y + y = 15
+ +
(5)
3 4 4
y 0, y + 0
4 4
29
4. (10 puntos) En la siguiente tabla se muestran el conjunto de actividades que
componen un proyecto, as como su duracin en das y las relaciones de
precedencia entre las mismas.
30
Solucin:
a) El siguiente grafo representa a este proyecto:
6 10 11.5
F(3) I(1.5)
3 5 7
7.5 10.5 12 J(2)
B(2)
H(1)
0 3 9 D(2) 11 14
A(3) C(6)
1 2 4 6 8
0 3 9 14 14
G(5)
E(3)
31
c)
i) Si la actividad I se retrasa 2 das, dado que su margen es de 0.5 das, la
duracin prevista del proyecto se retrasa 1.5 das.
ii) El margen de la actividad D es de 3 das. Luego esta actividad se
puede retrasar hasta 3 das sin que la duracin prevista del proyecto se
vea afectada.
iii) Para que una actividad sea crtica, debe formar parte de un camino
crtico. Dado que la duracin de la actividad B es de 2 das y su
margen de 2.5 das, su duracin debera ser mayor o igual que 4.5 das
para que fuese crtica.
32
INVESTIGACION OPERATIVA (3 LADE)
Extraordinario Febrero 2006
1. Una empresa que fabrica electrodomsticos est pensando abrir una nueva factora
para producir 3 modelos de lavadora: modelo de gama alta, media y baja. Tiene dos
posibles ubicaciones: 1 y 2. La inversin necesaria para construir la fbrica en la
ubicacin 1 es de 2000000 unidades monetarias y de 1750000 unidades monetarias
en la ubicacin 2. Los costes unitarios de produccin son 15, 13 y 10 unidades
monetarias, respectivamente para gama alta, media y baja, en la ubicacin 1 y 16,
12 y 9 unidades monetarias, respectivamente, en la ubicacin 2.
De la gama alta se han de producir al menos 75000 unidades anuales, 100000 de la
media y 200000 de la baja.
a) (7 puntos) Si slo se va a construir una factora, modelizar el problema con el
objetivo de minimizar costes.
b) (3 puntos) Si se incluye la posibilidad de construir las dos factoras (ubicacin
1 y 2), modelizar el problema con el objetivo de minimizar costes
considerando, adems, las siguientes restricciones:
En caso de producirse lavadoras de gama baja en la ubicacin 1 se
recibir una subvencin de 1000000 unidades monetarias.
La gama alta se producir nicamente en una de las dos ubicaciones.
Solucin:
a) Definimos las variables de decisin siguientes:
xij = nmero de lavadoras de la gama j producidas en la ubicacin i al ao
con i = 1, 2; j = a, m, b ( siendo a = alta, m = media y b = baja )
1 si se produce en la ubicacin i
yi = con i=1, 2
0 en caso contrario
La modelizacin queda como sigue:
33
Min (15 x1a + 13 x1m + 10 x1b + 16 x2 a + 12 x2 m + 9 x2b + 2000000 y1 + 1750000 y2 )
x1a + x2 a 75000
x + x 100000
1m 2 m
x1b + x2b 200000
y1 + y2 = 1
x1a My1
x2 a My2
s.a
x1m My1
x2 m My2
x1b My1
x My
2b 2
ij
x 0 y enteras i = 1, 2; j = a, m, b
y = 0,1 i = 1, 2
i
Con M positivo suficientemente grande.
34
Min (15 x1a + 13 x1m + 10 x1b + 16 x2 a + 12 x2 m + 9 x2b +
+2000000 z1 + 1750000 z2 1000000 y1b )
x1a + x2 a 75000
x + x 100000
1m 2 m
x1b + x2b 200000
y1a + y2 a = 1
z1 + z2 1
y1a z1
y z
2a 2
y1m z1
y z
2m 2
y z
s.a 1b 1
y2 b z 2
x1a My1a
x2 a My2 a
x My
1m 1m
x2 m My2 m
x My
1b 1b
x2b My2b
xij 0 y enteras i = 1, 2; j = a, m, b
yij = 0, 1 i = 1, 2; j = a, m, b
zi = 0, 1 i = 1, 2
2. (10 puntos) Una empresa dispone de dos tipos de mquinas A y B. Por cada hora de
trabajo en la mquina A se obtienen 20 piezas y 30 piezas por cada hora en la
mquina B. Por motivos de capacidad de la empresa no se pueden fabricar al da
ms de 600 piezas ni menos de 250. Adems debido a las caractersticas de las dos
mquinas el coste por unidad producida por la mquina A es de 4 y 3 por
unidad producida por B. Determinar las horas diarias ptimas para las dos
mquinas con las siguientes metas y prioridades:
Prioridad 1. El coste total diario no supere los 2000 .
Prioridad 2. Las horas de trabajo diarias en las mquinas A y B sean iguales.
Prioridad 3. Maximizar el nmero de piezas diarias.
35
Solucin:
Definimos las variables de decisin siguientes:
x1 = nmero de horas diarias de trabajo de la mquina A
x2 = nmero de horas diarias de trabajo de la mquina B
P1 Min ( y1+ )
20 x1 + 30 x2 250 (1)
20 x1 + 30 x2 600 (2)
s.a 80 x + 90 x y + + y = 2000 (3)
1 2 1 1
x1 0, x2 0
+
y1 0, y1 0
Soluciones ptimas: A
Valor ptimo: 0
36
P2 Min ( y2+ + y2 )
20 x1 + 30 x2 250 (1)
20 x1 + 30 x2 600 (2)
+
80 x1 + 90 x2 y1 + y1 = 2000 (3)
x 0, x 0
s.a 1 2
y1 0, y1+ = 0
x1 x2 y2+ + y2 = 0 (4)
y2 0, y2+ 0
P3 Max (20 x1 + 30 x2 )
20 x1 + 30 x2 250 (1)
20 x1 + 30 x2 600 (2)
80 x1 + 90 x2 y1+ + y1 = 2000 (3)
s.a x1 0, x2 0
y1 0, y1+ = 0
x1 x2 y2+ + y2 = 0 (4)
y2 = 0, y2+ = 0
Solucin ptima: (11.765,11.765)
Valor ptimo: 588.25
37
cuando se reemplaza el equipo dependen de la edad del equipo y son los que se
recogen en la siguiente tabla:
Solucin:
a) Se trata de un problema de reemplazamiento de equipo que tiene como objetivo
minimizar el coste total a lo largo del periodo de planificacin. Puede
representarse por la siguiente red en la que el valor de cada arco ( i, j ) , d ( i, j ) ,
d (1, 4 ) = d ( 2,5 ) = 7 + 1 + 1 + 2 2 = 9
d (1,5 ) = 7 + 1 + 1 + 2 + 3 = 14
38
14
9
6.5
6.5
4 4 4 4
1 0 2 4 3 6.5 4 9 5 13
6.5
b) Solo cambian los valores de los arcos que representan tres a ms aos, es decir
d (1, 4 ) = d ( 2,5 ) = 7 + 1 + 1 + 2 2 + 2 = 11 ;
d (1,5) = 7 + 1 + 1 + 2 + 3 + 2 = 16
16
11
6.5
6.5
4 4 4 4
1 0 2 4 3 6.5 4 10.5 5 13
6.5
11
39
Ahora la estrategia ptima es nica y viene dada por el camino (1,3,5) de la
red. Consiste en transcurridos dos aos cambiar el equipo comprado
inicialmente por uno nuevo y mantener este ltimo hasta el final.
Coste mnimo: 13000 u.m.
a) (4 puntos) Decidir la ruta que debe realizar cada camin para que el beneficio
total obtenido sea mximo.
b) El comercial de la empresa ha conseguido dos nuevas rutas y desea probarlas
durante este ao. Los beneficios obtenidos por cada camin son:
40
diarios, los camiones 2 y 3 podrn realizar, como mucho, 300 km diarios
y el camin 4, 160 km y las rutas 1, 2, 3, 4, 5, 6 son de 110, 150, 130,
150, 120 y 90 km respectivamente.
Solucin:
a) Aplicamos el Mtodo Hngaro a la siguiente tabla:
R1 R2 R3 R4
C1 -150 -200 -300 -100
C2 -100 -220 -300 -250
C3 -250 -140 -240 -240
C4 -300 -250 -100 -300
+300 +250 +300 +300
R1 R2 R3 R4
C1 150 50 0 200
C2 200 30 0 50
C3 50 110 60 60 -50
C4 0 0 200 0
R1 R2 R3 R4
C1 150 50 0 200 -30
C2 200 30 0 50 -30
C3 0 60 10 10
C4 0 0 200 0
+30
R1 R2 R3 R4
C1 120 20 0 170
C2 170 0 0 20
C3 0 60 40 10
C4 0 0 230 0
41
Asignacin ptima: Camin 1 Ruta 3, Camin 2 Ruta 2, Camin 3
Ruta 1, Camin 4 Ruta 4.
Beneficio mximo 1070.
b)
i) Aplicaremos el Mtodo Hngaro a la siguiente tabla:
R1 R2 R3 R4 R5 R6
C1 -150 -200 -300 -100 -200 -260
C2 -100 -220 -300 -250 -300 -280
C3 -250 -140 -240 -240 -250 -250
C4 -300 -250 -100 -300 -250 -320
F1 0 0 0 0 M M
F2 0 0 0 0 M M
Con M positivo suficientemente grande.
42
INVESTIGACION OPERATIVA (3 LADE)
Junio 2006
1. (10 puntos) Una fbrica produce 4 tipos de jabones, para lo cual son necesarios 6
componentes. En la siguiente tabla se muestran las cantidades necesarias para
realizar una pastilla de jabn de cada tipo.
J1 250 ml 240 ml 42 g 1g 1 ml 3 ml
J2 200 ml 210 ml 2g 40 g 2 ml 1 ml
J3 230 ml 240 ml 20 g 25 g 3 ml 1 ml
43
Solucin:
Definimos las variables de decisin siguientes
xi = nmero de pastillas de jabn tipo Ji producidas diariamente; i = 1,..., 4
y1 y3 + z 1
xi Myi i = 1,..., 4
xi 0 y enteras i = 1,..., 4
yi = 0, 1 i = 1,..., 4
z = 0, 1
44
c) (3 puntos) Si el coste de embalaje de los caramelos es de 0.1 euros por kg para
los caramelos de tipo C1 y 0.2 euros por kg para C2. Obtener una solucin
eficiente que maximice el ingreso semanal, minimice el azcar utilizado a la
semana y minimice el coste semanal de embalaje.
Solucin:
a) Definimos las variables de decisin siguientes:
xi = kg de caramelos producidos a la semana del tipo Ci i = 1, 2 .
La modelizacin queda como sigue:
Max ( 200x1 + 300x2 , 100x1 400x2 )
x1 x2 5 (1)
s.a 200 x1 + 400 x2 1600 (2)
x 0, x 0
1 2
X f ()) f ( X )
(6,1) (1500, 1000)
(8, 0) (1600, 800)
(7, 2) (2000, 1500)
(10, 0) (2000, 1000)
45
Soluciones eficientes: {( x , 0 ) donde x
1 1 8 } es decir, producir 8 kg o ms de
C1 y nada de C2.
O1 O2 O3 O4 O5
R1 60 -- 90 -- 120
R2 70 90 80 100 80
R3 -- 70 120 90 100
(Donde -- significa que dicho equipo no restaurar en ningn caso la obra
correspondiente).
46
El primer equipo restaurador est compuesto por seis personas, el segundo por
cuatro y el tercero por tres. En la restauracin de cada una de las obras son
necesarias dos personas. Cada persona de un equipo slo restaura una obra.
a) (3 puntos) A qu tabla se debe aplicar el Mtodo Hngaro para realizar las
cinco restauraciones, con el menor coste posible, teniendo en cuenta que cada
una de ellas debe ser realizada por un nico equipo restaurador, y que los tres
equipos deben participar en dichas restauraciones?
b) (6 puntos) Dado que el coste de restauracin de las cinco obras es muy
elevado, la directiva del museo decide restaurar nicamente tres, asignando una
nica obra a cada equipo. Determinar, aplicando el Mtodo Hngaro, todas las
posibles asignaciones que minimicen el coste total.
Solucin:
a) Aplicaremos el Mtodo Hngaro a la siguiente tabla:
O1 O2 O3 O4 O5 F
R1 60 M 90 M 120 0
R1 60 M 90 M 120 0
R1 60 M 90 M 120 0
R2 70 90 80 100 80 0
R2 70 90 80 100 80 0
R3 M 70 120 90 100 M
Con M positivo suficientemente grande.
47
O1 O2 O3 O4 O5
R1 60 M 90 M 120 -60
R2 70 90 80 100 80 -70
R3 M 70 120 90 100 -70
F1 0 0 0 0 0 0
F2 0 0 0 0 0 0
Con M positivo suficientemente grande.
O1 O2 O3 O4 O5
R1 0 M 30 M 60 -10
R2 0 20 10 30 10 -10
R3 M 0 50 20 30 -10
F1 0 0 0 0 0
F2 0 0 0 0 0
+10 +10
Con M positivo suficientemente grande.
O1 O2 O3 O4 O5
R1 0 M 20 M 50
R2 0 20 0 20 0
R3 M 0 40 10 20
F1 10 10 0 0 0
F2 10 10 0 0 0
Con M positivo suficientemente grande.
Las asignaciones ptimas son:
Asignacin ptima 1: R1 O1, R2 O3, R3 O2.
Asignacin ptima 2: R1 O1, R2 O5, R3 O2.
Coste mnino 210000
48
4. Dada la siguiente red:
1,0
1 3 3,2
2,2
4,4
2,2
2,2
3,3
0 4 6
3,0
4,2
4,3
1,1
2 5
2,1
a) (2 puntos) Indicar una cadena de origen a destino que no sea un camino y que
pase por el nodo 5.
b) (4 puntos) Si los valores de los arcos representan la capacidad del arco (izda) y
el valor del flujo del arco (dcha), calcular, si es posible, una cadena de
crecimiento (no saturada) asociada a este flujo.
c) (3 puntos) Partiendo del flujo dado, obtener el valor del flujo mximo.
Solucin:
a) La cadena (0,2,5,4,6) es una cadena que sin ser camino pasa por el nodo 5.
b) La cadena (0,2,1,3,6) no est saturada, es decir sus arcos directos no estn
saturados y el inverso no tiene flujo nulo.
c) Considerando el flujo dado, cuyo valor es 6, y la cadena de crecimiento dada en
el apartado b), el valor del flujo puede aumentar en:
f ( 0, 2,1,3, 6 ) = min {4 2, 2,1 0,3 2} = 1
49
1,1
1 3 3,3
2,2
4,4
2,2
2,1
3,3
0 4 6
3,0
4,3
4,3
1,1
2 5
2,1
En esta nueva situacin todas las cadenas de origen a destino estn saturadas,
por tanto el flujo que atraviesa la red es mximo y de valor V f = 7 .
Solucin:
El comienzo ms temprano de una actividad del proyecto es el periodo de
tiempo mnimo que debe transcurrir desde iniciado el proyecto para que sean
realizadas todas sus actividades precedentes y poder empezar dicha actividad.
El final ms tardo de una actividad del proyecto es el periodo de tiempo mximo
que debe transcurrir desde iniciado el proyecto para que sea realizada dicha
actividad sin alterar la duracin prevista del proyecto.
50
INVESTIGACION OPERATIVA (3 LADE)
Septiembre 2006
1. (10 puntos) Una empresa est considerando cinco proyectos. Cada proyecto
aprobado ser ejecutado sobre un periodo de tres aos. Los rendimientos esperados
y los gastos anuales para cada proyecto, junto con los fondos anuales disponibles en
miles de euros, se recogen en la siguiente tabla:
Gastos en
Proyecto Rendimientos
Ao 1 Ao 2 Ao 3
1 5 1 8 20
2 4 7 10 40
3 3 9 2 20
4 7 4 1 15
5 8 6 10 30
Fondos
25 25 25
disponibles
La empresa, teniendo en cuenta su capital disponible, debe elegir los proyectos con
el objetivo de maximizar los rendimientos totales. Adems se dispone de la
siguiente informacin:
El proyecto 3 no se hace si se hace el 5.
Los proyectos 1 y 2 se hacen de forma conjunta solo si no se hacen ni el 4 ni el
proyecto 5.
La empresa debe reducir en uno de los tres aos sus fondos disponibles en 5
mil euros y debe decidir en qu ao hacerlo.
Modelizar sin resolver el problema usando la programacin lineal entera.
Solucin:
Definimos las variables de decisin siguientes
1 si se lleva a cabo el proyecto i
yi = con i = 1,...,5
0 en caso contrario
51
1 si se reducen los fondos en el ao j
zj = con j = 1, 2, 3
0 en caso contrario
La modelizacin queda como sigue:
Max ( 20 y1 + 40 y2 + 20 y3 + 15 y4 + 30 y5 )
5 y1 + 4 y2 + 3 y3 + 7 y4 + 8 y5 25 5 z1
y + 7 y + 9 y + 4 y + 6 y 25 5 z
1 2 3 4 5 2
8 y1 + 10 y2 + 2 y3 + y4 + 10 y5 25 5 z3
z1 + z2 + z3 = 1
s.a y 1 y
3 5
y4 + y5 4 2 ( y1 + y2 )
yi = 0, 1 i = 1,...,5
z j = 0, 1 j = 1, 2,3
2. (10 puntos) Una empresa posee dos cadenas de produccin para un mismo artculo.
La cadena 1 produce 2 unidades por minuto con un beneficio unitario de 3000 ,
mientras que la cadena 2 produce 3 unidades por minuto con un beneficio de 5000
por unidad. El coste de almacenamiento por unidad asciende a 10 .
Calcular el tiempo de produccin semanal que debe asignarse a cada una de las
cadenas, si la empresa se ha planteado las siguientes metas y objetivos con el
siguiente orden de prioridades.
Prioridad 1. Producir al menos 30000 unidades semanales.
Prioridad 2. Los gastos de almacenamiento no superen los 450000 semanales.
Prioridad 3. El tiempo de produccin semanal en la cadena 1 sea al menos
tanto como en la 2, pero no ms del triple de la 2.
Prioridad 4. Maximizar el beneficio semanal.
Solucin:
Definimos las variables de decisin siguientes:
x1 = minutos de produccin de la cadena 1 a la semana
x2 = minutos de produccin de la cadena 2 a la semana
52
Min L( y1 , y2+ , y3 + y4+ , 6000 x1 15000 x2 )
2 x + 3 x y+ + y = 30000 (1)
1 2 1 1
+
10 (2 x1 + 3 x2 ) y2 + y2 = 450000 (2)
x1 x2 y3+ + y3 = 0 (3)
s.a
+
x1 3 x2 y4 + y4 = 0 (4)
x 0, x 0
1 2
y 0, y + 0 i = 1,..., 4
i i
P1 Min ( y1 )
2 x + 3 x y + + y = 30000 (1)
1 2 1 1
s.a x 0, x 0
1 2
y 0, y + 0
1 1
Soluciones ptimas: A
Valor ptimo: 0
P2 Min ( y2+ )
2 x + 3 x y + + y = 30000 (1)
1 2 1 1
x 0, x2 0
1
s.a. y1 = 0, y1+ 0
20 x + 30 x y + + y = 450000 (2)
1 2 2 2
y 0, y + 0
2 2
Soluciones ptimas: B
Valor ptimo: 0
53
P3 Min ( y3 + y4+ )
2 x + 3 x y + + y = 30000 (1)
1 2 1 1
x 0, x2 0
1
+
y1 = 0, y1 0
+
20 x1 + 30 x2 y2 + y2 = 450000 (2)
s.a.
y2 0, y2+ = 0
x x y + + y = 0 (3)
1 2 3 3
x 3 x y + + y = 0 (4)
1 2 4 4
y 0, y + 0, y 0, y + 0
3 3 4 4
Soluciones ptimas: C
Valor ptimo: 0
P4 Max (6000 x1 + 15000 x2 )
2 x + 3 x y + + y = 30000 (1)
1 2 1 1
x 0, x2 0
1
+
y1 = 0, y1 0
+
20 x1 + 30 x2 y2 + y2 = 450000 (2)
+
s.a y2 0, y2 = 0
x x y + + y = 0 (3)
1 2 3 3
x 3 x y + + y = 0 (4)
1 2 4 4
y = 0, y + 0,
3 3
+
y4 0, y4 = 0
54
Solucin ptima: (9000,9000)
Valor ptimo: 189000000
Los tiempos ptimos de produccin son de 9000 minutos semanales en cada una de
las cadenas. Se realizan, a la semana, 45000 productos (no existe ni exceso ni
defecto en la primera meta) con un gasto de almacenamiento de 450000 (no hay
ni exceso ni defecto en la segunda meta) y un beneficio de 189 millones de euros.
i j 2 3 4 5
1 12 22 38 40
2 -- 13 20 29
3 -- -- 10 19
4 -- -- -- 12
El dueo quiere conocer cundo arrendar y por cunto tiempo para maximizar la
utilidad esperada durante los prximos 4 aos.
Solucin:
Este es un problema de reemplazamiento de contratos para maximizar la utilidad
esperada y puede ser representado por la siguiente red, en la que el valor de cada
55
arco ( i, j ) indica la utilidad esperada de un contrato de arrendamiento desde el
40
38
19
22
12 13 10 12
1 0 2 12 3 25 4 38 5 50
20
29
4. (10 puntos) En la siguiente tabla quedan recogidas las duraciones en das y las
relaciones de precedencia de las actividades que forman un proyecto:
56
b) Cul es la duracin del proyecto si la duracin de la actividad D es menor de
dos das? Elaborar la tabla de actividades del proyecto, sealando las
actividades crticas.
c) La actividad D puede retrasarse hasta da sin alterar la duracin del proyecto.
Cul es la duracin de la activad D?
Solucin:
a)
2 F(1)
A(4)
D(t)
B(6) G(2)
1 3 5
C(7) E(5)
H(3)
b) Para t < 2 :
4
2 F(1)
6-t
A(4)
D(t)
0 B(6) 6 G(2) 14
1 3 5
0 6 14
C(7) E(5)
H(3)
11
4
11
57
Tabla de actividades:
(i,j) t(i,j) CMT(i,j) FMT*(i,j) M(i,j)
A (1,2) 4 0 6-t 2-t
B (1,3) 6 0 6 0*
C (1,4) 7 0 11 4
F (2,5) 1 4 14 9
E (3,4) 5 6 11 0*
G (3,5) 2 6 14 6
H (4,5) 3 11 14 0*
Actividades crticas: B, E, H.
Duracin prevista del proyecto (d.p.p.): 14 das.
c) Del enunciado se sabe que el margen de la actividad D es 0.5 das y por tanto
no es una actividad crtica.
Comprobamos en primer lugar que en esta situacin se cumple que t < 2 . Ya
que para t 2 se tendra que:
4
2 F(1)
4
A(4)
D(t)
C(7) E(5)
H(3)
9+t
4
9+t
58
Por tanto para t = 2 , los caminos crticos seran: (1,2,3,4,5) y (1,3,4,5), y para
t > 2 , el camino crtico sera: (1,2,3,4,5). En ambos casos, D sera una
actividad crtica y por tanto su margen sera nulo.
Luego si el margen de la actividad D es 0.5 das se sabe que t < 2 y en
consecuencia se cumple que:
M ( 2,3) = 2 t = 0.5 t = 1.5 das.
59
INVESTIGACION OPERATIVA (3 LADE)
Extraordinario Febrero 2007
1. (10 puntos) Una empresa estudia producir sus tres productos P1, P2 y P3 en una
sola de las ubicaciones U1, U2 y U3. La produccin de cada producto genera un
volumen de contaminacin de 0.5, 2 y 1 cm3 respectivamente por unidad
producida, independientemente de la ubicacin.
La siguiente tabla recoge para cada una de las ubicaciones: los ingresos unitarios
(euros) de cada producto, la capacidad de produccin diaria (unidades), los
volmenes mximos de contaminacin permitidos (cm3 ) y la penalizacin por
U1 U2 U3
Ingreso Unitario P1 2 4 3
Ingreso Unitario P2 5 3 6
Ingreso Unitario P3 3 4 2
Capacidad produccin diaria 200 400 300
Volumen mximo contaminacin diaria 150 250 200
Penalizacin de contaminacin excedente 20 15 10
La empresa, concienciada con los problemas del medio ambiente, propone unos
objetivos y metas, con un orden de prioridades dado por:
Prioridad 1. Maximizar ingresos diarios.
Prioridad 2. No superar el nivel mximo de contaminacin de la ubicacin
Prioridad 3. Se desea no gastar ms de 9000 al da por exceso de
contaminacin.
Formular un modelo de programacin lineal que permita determinar cuntas
unidades diarias de cada producto deben producirse y en qu ubicacin.
60
Solucin:
Definimos las variables de decisin siguientes:
xij = unidades producidas al da de Pj en Ui i = 1, 2, 3 , j = 1, 2,3
1 si se elige la ubicacin j
uj = j = 1, 2, 3
0 en cualquier otro caso
El artista va a vender todas las obras de arte y cada galera va a adquirir por lo
menos una obra de arte. Se da la circunstancia de que la galera A ha decidido que
slo va a comprar una obra de arte.
61
a) (6 puntos) Determinar cmo asignar el artista las obras de arte entre las
distintas galeras si lo que persigue es maximizar sus ingresos.
b) (4 puntos) Modelizar empleando la programacin lineal entera el anterior
problema si, adems, el artista aade la siguiente restriccin: las obras de arte 2
y 4 han de venderse a la misma galera.
Solucin:
a) Aplicamos el Mtodo Hngaro a la siguiente tabla:
O1 O2 O3 O4 F1
Galeria A -12 -10 -8 -10 M
Galeria B -14 -11 -6 -7 0
Galeria B -14 -11 -6 -7 0
Galeria C -15 -13 -8 -9 0
Galeria C -15 -13 -8 -9 0
+15 +13 +8 +10
Con M positivo suficientemente grande.
O1 O2 O3 O4 F1
Galera A 3 3 0 0 M
Galera B 1 2 2 3 0
Galera B 1 2 2 3 0
Galera C 0 0 0 1 0
Galera C 0 0 0 1 0
Con M positivo suficientemente grande.
O1 O2 O3 O4 F1
Galera A 3 3 0 0 M
Galera B 1 2 2 3 0 - 1
Galera B 1 2 2 3 0 - 1
Galera C 0 0 0 1 0
Galera C 0 0 0 1 0
+1
Con M positivo suficientemente grande.
62
O1 O2 O3 O4 F1
Galera A 3 3 0 0 M
Galera B 0 1 1 2 0
Galera B 0 1 1 2 0
Galera C 0 0 0 1 1
Galera C 0 0 0 1 1
Con M positivo suficientemente grande.
x A3 + xB 3 + xC 3 = 1
x A4 + xB 4 + xC 4 = 1
x A1 + xA 2 + xA3 + x A4 = 1
s.a
1 xB1 + xB 2 + xB 3 + xB 4 2
1 xC1 + xC 2 + xC 3 + xC 4 2
xB 2 = xB 4
xC 2 = xC 4
xij = 0, 1 i = A,B,C; j = 1,..., 4
3. (10 puntos) Una empresa emplea dos procesos de produccin diferentes para
producir un producto. En cada uno de los procesos se precisa utilizar tres mquinas
M1, M2 y M3. Para fabricar una unidad de producto segn el proceso productivo
63
elegido se necesita usar en cada una de las mquinas las horas indicadas en la
siguiente tabla:
Proceso 1 Proceso 2
M1 1 3
M2 4 2
M3 3 4
Por una unidad de producto fabricado con el proceso 1 se obtienen 55 euros y con
el proceso 2 se obtienen 75 euros. El coste de una hora de mquina es de 5 euros.
Cada mquina est disponible 60 horas.
La empresa propone las siguientes metas por orden de prioridad:
Prioridad 1. Obtener un beneficio de al menos 300 euros.
Prioridad 2. El nmero de horas trabajadas en las mquinas M1 y M2
coincidan.
Prioridad 3. El nmero de horas trabajadas en la mquina M3 no sea superior a
2 veces el nmero de horas trabajadas en la mquina M1.
Modelizar, utilizando programacin lineal, el problema de calcular las unidades
ptimas que deben asignarse a cada proceso productivo. Resolver el problema
relajado asociado.
Solucin:
Definimos las variables de decisin siguientes:
x1 = unidades producidas con el proceso 1 a la hora
x2 = unidades producidas con el proceso 2 a la hora
64
Min L( y1 , y2+ + y2 , y3+ )
x1 + 3x2 60 (1)
4 x1 + 2 x2 60 (2)
3x + 4 x 60 (3)
1 2
15 x + 30 x y + + y = 300 (4)
1 2 1 1
s.a
x1 + 3x2 (4 x1 + 2 x2 ) y2+ + y2 = 0 (5)
3x1 + 4 x2 2( x1 + 3 x2 ) y3+ + y3 = 0 (6)
x1 0, x2 0
yi 0, yi+ 0 i = 1, 2, 3
P1 Min ( y1 )
x1 + 3 x2 60 (1)
4 x1 + 2 x2 60 (2)
3x + 4 x 60 (3)
1 2
s.a
15 x1 + 30 x2 y1+ + y1 = 300 (4)
x1 0, x2 0
y1 0, y1+ 0
Soluciones ptimas: A
Valor ptimo: 0
65
P2 Min ( y2+ + y2 )
x1 + 3x2 60 (1)
4 x1 + 2 x2 60 (2)
3x + 4 x 60 (3)
1 2
15 x + 30 x y + + y = 300 (4)
s.a 1 2 1 1
x1 0, x2 0
+
y1 = 0, y1 0
3x1 + x2 y2+ + y2 = 0 (5)
+
y2 0, y2 0
Soluciones ptimas: B
Valor ptimo: 0
P3 Min ( y3+ )
x1 + 3x2 60 (1)
4 x1 + 2 x2 60 (2)
3x + 4 x 60 (3)
1 2
15 x + 30 x y + + y = 300 (4)
1 2 1 1
x1 0, x2 0
s.a y = 0, y + 0
1 1
+
3x1 + x2 y2 + y2 = 0 (5)
+
y2 = 0, y2 = 0
x1 2 x2 y3+ + y3 = 0 (6)
+
y3 0, y3 0
Soluciones ptimas: (2.857,8.571)(4,12)
Valor ptimo: 0
66
4. (10 puntos) La siguiente red representa un proyecto y los valores asignados a cada
arco las duraciones de las actividades en l recogidas en das.
6
3 5 9
7 3 10
12
5 3
1 4 7 8
15
6 4
5 8
2 6
67
Solucin:
a)
7 6 13
3 5
7 13 9
3
7
10
0 12 23 26
12 5 3
1 4 7 8
0 18 23 26
15
6 4
6 15 8
2 5 6
13 18
b) La siguiente tabla recoge los tiempos (CMT y FMT*) de todas las actividades
que conforman el proyecto:
(i,j) t(i,j) CMT(i,j) FMT*(i,j) M(i,j)
(1,2) 6 0 13 7
(1,3) 7 0 7 0*
(1,4) 12 0 18 6
(1,6) 15 0 18 3
(2,4) 5 6 18 7
(3,4) 3 7 18 8
(3,5) 6 7 13 0*
(4,7) 5 12 23 6
(5,7) 10 13 23 0*
(5,8) 9 13 26 4
(6,7) 4 15 23 4
(6,8) 8 15 26 3
(7,8) 3 23 26 0*
68
Como FMT ( i, j ) = CMT ( i, j ) + t ( i, j ) , CMT * ( i, j ) = FMT * ( i, j ) t ( i, j ) , y
FMT ( 2, 4 ) = 6 + 5 = 11 , CMT * ( 2, 4 ) = 18 5 = 13 , M ( 2, 4 ) = 18 6 5 = 7
FMT ( 4, 7 ) = 12 + 5 = 17 , CMT * ( 4, 7 ) = 23 5 = 18 , M ( 4, 7 ) = 23 12 5 = 6
FMT ( 6, 7 ) = 15 + 4 = 19 , CMT * ( 6, 7 ) = 23 4 = 19 , M ( 6, 7 ) = 23 15 4 = 4
c)
i) Si incorporamos una nueva actividad (2,6) de duracin t ( 2, 6 ) = 11 , se
tiene que:
7 6 13
3 5
7 13 9
3
7 10
0 12 23 26
12 5 3
1 4 7 8
0 18 23 26
15
6 4
6 5 17 8
2 6
7 18
11
los mrgenes M ( 6, 7 ) = Q ( 7 ) P ( 6 ) t ( 6, 7 ) y
69
7 6 13
3 5
9
3
7 10
0 12 23 t+14
12 5 3
1 4 7 8
15
6 4
8
6 5 t+6
2 6
t(2,6)=t
t satisfaciendo:
P ( 6 ) = Max {t + 6,15} = t + 6
70
INVESTIGACION OPERATIVA (3 LADE)
Junio 2007
1. Un empresario que fabrica tres artculos P1, P2, P3, desea encontrar la produccin
diaria que le permita maximizar sus beneficios. Los artculos son procesados en dos
de las cuatro mquinas de las que dispone, bien en la A y B, o bien en la C y D,
siendo el coste diario fijo de la puesta en marcha de cada una de estas mquinas 20,
25, 35 y 15 unidades monetarias respectivamente. El ingreso de estos artculos es
de 5 unidades monetarias por unidad de P1, 5 unidades monetarias por unidad de
P2, y 10 unidades monetarias por unidad de P3. Las horas que se necesitan por
mquina y unidad de articulo son:
Siendo el nmero de horas disponibles en cada mquina 190, 210, 170 y 200
respectivamente.
Solucin:
a) Definimos las variables de decisin siguientes
xi = unidades de Pi , i=1, 2, 3
71
La modelizacin queda como sigue:
(
Max 5 x1 + 5 x2 + 10 x3 ( 20 + 25 ) y1 + ( 35 + 15 ) y2 )
x1 + x2 + 2 x3 190 + M (1 y1 )
x1 + x2 + x3 210 + M (1 y1 )
2 x1 + x2 + x3 170 + M (1 y2 )
x1 + 2 x2 + x3 200 + M (1 y2 )
s.a
y1 + y2 = 1
xi 0 y enteras i = 1, 2, 3
y1 = 1, 0
y = 1, 0
2
Con M positivo suficientemente grande.
10 z x2 20 + M (1 z )
5 z x1 Mz
z = 0, 1
72
B1 B2 B3 B4 B5 C
A1 45 40 30 -- -- --
A2 -- -- 30 -- -- --
B1 -- -- -- 20 30 --
B2 -- -- -- 25 -- --
B3 -- -- -- -- 35 20
B4 -- -- -- -- -- 40
B5 -- -- -- -- -- 65
a) (1 punto) Construir una red asociada al problema de planificar cmo enviar los
turistas a C.
b) (9 puntos) La siguiente tabla nos indica una planificacin para enviar turistas al
destino C. Cuntos turistas viajaran al destino C?
B1 B2 B3 B4 B5 C
A1 45 20 25 -- -- --
A2 -- -- 30 -- -- --
B1 -- -- -- 20 25 --
B2 -- -- -- 20 -- --
B3 -- -- -- -- 35 20
B4 -- -- -- -- -- 40
B5 -- -- -- -- -- 60
Solucin:
a) Problema de flujo mximo cuya red asociada es:
73
45 B1 20
A1
40 30
B4 40
30
M
O B2 25 C
M 65
B5
A2 35
30 20
B3
B1
45,45 20,20
A1
40,20 30,25
B4
40,40
M,90 30,25
O B2 C
25,20
65,60
M,30
B5
A2
35,35
30,30 B3
20,20
Con esta planificacin se pueden enviar hasta 120 turistas desde el origen hasta
el destino C ( V f = 120 ).
Una cadena de crecimiento (no saturada) asociada a este flujo es (O, A1, B2,
B4, B1, B5, C), dado que sus arcos directos no estn saturados y su arco
inverso no tiene flujo nulo. El incremento de flujo que permite esta cadena es:
f ( O, A1, B2, B4, B1, B5, C ) = min {M, 40 20, 25 20, 20,30 25, 65 60} = 5
Saturamos la cadena aadiendo esta cantidad a los arcos directos y restndosela
74
a los inversos. El resultado es el siguiente flujo en el que todas las cadenas de
origen a destino estn saturadas, por tanto el flujo que atraviesa la red es
mximo y de valor V f = 125 turistas.
45,45 B1 20,15
A1
40,25 30,30
B4 40,40
M,95 30,25
O B2 C
25,25
65,65
M,30
B5
A2 35,35
30,30 20,20
B3
75
Junio Julio Agosto
P4 6 -- 9
Teniendo en cuenta que las cuatro personas han de disfrutar sus vacaciones en
los meses de Junio, Julio, Agosto (cada uno un mes completo) y que en cada
uno de estos tres meses debe haber al menos una persona de vacaciones.
Solucin:
a) Aplicamos el Mtodo Hngaro a la siguiente tabla:
Junio Junio Julio Julio Agosto Agosto
P1 -5 -5 -4 -4 -9 -9 +9
P2 M M -3 -3 -6 -6 +6
P3 -7 -7 -5 -5 -5 -5 +7
P4 -6 -6 M M -9 -9 +9
F1 M 0 M 0 M 0
F2 M 0 M 0 M 0
Con M positivo suficientemente grande.
76
Con M positivo suficientemente grande.
Junio Junio Julio Julio Agosto Agosto
P1 4 4 3 5 0 0 -1
P2 M M 1 3 0 0 -1
P3 0 0 0 2 2 2
P4 3 3 M M 0 0 -1
F1 M 0 M 0 M 0
F2 M 0 M 0 M 0
+1 +1
Con M positivo suficientemente grande.
77
D(5,6,13)
3 4
B(1,2,3)
F(2,2,2)
E(6,6,6)
1
A(2,3,4) C(4,11,12)
2 5
Solucin:
a) Bajo los supuestos del PERT se estima la duracin media de cada actividad
to ( i, j ) + 4tm ( i, j ) + t p ( i, j )
como t ( i, j ) = donde to representa la duracin
6
optimista, tm la modal y t p la pesimista. Y la varianza de la duracin de cada
t p ( i, j ) to ( i, j )
2
78
3 10
D(7)
3 4
4 11
B(2)
E(6) F(2)
0
1 A(3)
0 3 13
C(10)
2 5
3 13
Tabla de actividades:
A (1,2) 3 0 3 0*
B (1,3) 2 0 4 2
Fict (2,3) 0 3 4 1
C (2,5) 10 3 13 0*
D (3,4) 7 3 11 1
E (3,5) 6 3 13 4
F (4,5) 2 10 13 1
b)
i) Se puede reducir C hasta 1 da. A partir de aqu el proyecto durar, en
media, 12 das ya que aparece un nuevo camino crtico
ii) Como mucho debe durar en media 4 das, ya que este es el margen de la
actividad E.
79
iii) Como mucho 3 das, ya que su comienzo ms temprano es el da 10 (un
da ms tarde que en el apartado ii)) y queremos que su final ms tardo
sea el da 13
3 10
D(7)
3 4
B(2)
E(6) F(2)
0 10
G
1 A(3) 5
3 13
C(10)
2 6
80
INVESTIGACION OPERATIVA (3 LADE)
Septiembre 2007
Solucin:
a) Resolucin del problema relajado:
PR
81
PR
R = (3/ 2,3) zR = 18
Cota = ---
x1 1 x1 2
P4 P1
4 = (1,3) z4 = 17 1 = (2 ,8/ 3) z1 = 17.333
Cota = 17 Cota = ---
Terminal x2 2 x2 3
P3 P2
3 = (3,2) z3 = 16
Infactible
Cota = 16
Terminal Terminal
P1
P3
82
P4
83
Gerencia de la Empresa ha decidido replantearse la situacin con las siguientes
metas y objetivos, con el siguiente orden de prioridades:
Prioridad 1. La cantidad de artculos destinados diariamente a primer
equipo no sea inferior al 75% de la produccin total.
Prioridad 2. La cantidad de artculos destinados diariamente a piezas de
recambio permita satisfacer las necesidades del nuevo cliente.
Prioridad 3. La cantidad de artculos destinados diariamente a piezas de
recambio no sea superior al 20% de la produccin total.
Prioridad 4. Mximo Beneficio.
Solucin:
a) Definimos las variables de decisin siguientes:
x1 = unidades diarias destinadas a "primer equipo"
x2 = unidades diarias destinadas a "piezas de reemplazamiento"
La modelizacin queda como sigue:
Max ( Kx1 + 2 Kx2 , x1 )
x1 + x2 800
x 0.75 x + x
( 1 2)
s.a 1
x2 160
x1 0, x2 0 y enteras
84
Vrtices Vrtices
X f (X )
(480,160) (800 K , 480)
(600, 200) (1000 K , 600)
(640,160) (960 K , 640)
85
P1 Min ( y1 )
x1 + x2 800 (1)
0.25 x1 0.75 x2 y1+ + y1 = 0 (2)
s.a
x1 0, x2 0
+
y1 0, y1 0
Soluciones ptimas: A
Valor ptimo: 0
P2 Min ( y2 )
x1 + x2 800 (1)
0.25 x1 0.75 x2 y1+ + y1 = 0 (2)
x1 0, x2 0
s.a
y1 = 0, y1+ 0
x2 y2+ + y2 = 180 (3)
y 0, y + 0
2 2
86
Soluciones ptimas: B
Valor ptimo: 0
P3 Min ( y3+ )
x1 + x2 800 (1)
0.25 x1 0.75 x2 y1+ + y1 = 0 (2)
x1 0, x2 0
+
y1 = 0, y1 0
s.a +
x2 y2 + y2 = 180 (3)
+
y2 = 0, y2 0
+
0.2 x1 + 0.8 x2 y3 + y3 = 0 (4)
+
y3 0, y3 0
87
P4 Min (Kx1 2 Kx2 )
x1 + x2 800 (1)
0.25 x1 0.75 x2 y1+ + y1 = 0 (2)
x1 0, x2 0
+
y1 = 0, y1 0
s.a
x2 y2+ + y2 = 180 (3)
y = 0, y2+ 0
2
0.2 x + 0.8 x y + + y = 0 (4)
1 2 3 3
y 0, y + = 20
3 3
equipo son el 77.5% del total producidos ( y1+ = 20, y1 = 0). Se satisfacen
las necesidades del nuevo cliente, 180 unidades diarias de piezas de
88
3. Un ayuntamiento quiere disear el modo de llevar el agua desde el depsito
municipal D a 7 casas rurales, no necesariamente de forma directa, con el menor
coste posible. Las posibles conducciones entre los depsitos y las casa con sus
costes correspondientes, en unidades monetarias, vienen recogidas en la siguiente
tabla:
D C1 C2 C3 C4 C5 C6 C7
D -- 10 12 14 -- -- -- --
C1 -- -- -- 3 -- -- --
C2 -- -- 2 4 -- --
C3 -- -- 3 -- --
C4 -- 3 5 6
C5 -- 7 5
C6 -- 4
C7 --
Por ejemplo, realizar una conduccin entre la casa 2 y la casa 5 tiene un coste de 4
unidades monetarias.
a) (9 puntos) Calcular todas las formas posibles de establecer las conexiones para
que el coste total sea mnimo.
b) (1 punto) Si en lugar de 7 casas tenemos 8 casas, cuntas conducciones se
necesitaran? Razonar la respuesta.
Solucin:
a) Problema del rbol de expansin minimal cuya red asociada es:
89
C1 3
5
10 C4 C6
6
2 3
12 4
D C2
4 7
14 C5 C7
5
3
C3
C1 3
5
10 C4 C6
6
2 3
12 4
D C2
4 7
14 C5 C7
5
3
C3
90
Solucin ptima B:
C1
3
C4
5
C6
10
6
2 3
12 4
D C2
4 7
14 C5 C7
5
3
C3
91
Solucin:
I
6 7
M
C
J
D K
2 4 8
E
A L
1 H 9
5
B F
G
3
5. (6 puntos) Sean tres actividades que vienen representadas en una red por los arcos
(3, 8), (4, 8) y (4, 9). Sabiendo que:
las tres tienen una duracin de dos semanas,
la actividad (4,8) debe estar finalizada al de 20 semanas de iniciado el proyecto
si se desea cumplir con la duracin prevista del proyecto,
la actividad (4,8) puede retrasarse hasta 3 semanas sin que se retrase la
duracin prevista del proyecto.
Contestar razonadamente a las siguientes cuestiones:
a) Cul es el comienzo y el final ms temprano de la actividad (4,9)?
b) Cul es el comienzo y el final ms tardo de la (3,8)?
Solucin:
Se sabe que:
t ( 3,8 ) = t ( 4,8 ) = t ( 4,9 ) = 2
FMT * ( 4,8) = Q ( 8 ) = 20
M ( 4,8) = Q ( 8 ) P ( 4 ) t ( 4,8) = 20 P ( 4 ) 2 = 3 P ( 4 ) = 15
92
2
3 8
20
15
2
4 9
93
INVESTIGACION OPERATIVA (3 LADE)
Extraordinario Febrero 2008
Solucin:
a) Definimos las variables de decisin siguientes:
xi = nmero de pacientes diarios atendidos por el Servicio i , i=1,2,3
La modelizacin queda como sigue:
94
Max ( x1 + x2 + x3 )
x1 100
x 60
2
x3 40
s.a
10 x1 + 20 x2 + 25 x3 2400
x1 + x2 2 x3
x1 0, x2 0, x3 0 y enteras
1 si se abre el Servicio 4
z=
0 no se abre el Servicio 4
La modelizacin queda como sigue:
Max ( x1 + x2 + x3 + x4 )
x1 100 + 20(1 z )
x 60 + 20(1 z )
2
x3 40 + 20(1 z )
x4 50 z
s.a
10 x1 + 20 x2 + 25 x3 + 22 x4 3200
x1 + x2 2 x3
x1 0, x2 0, x3 0, x4 0 y enteras
z = 0, 1
2. Una empresa desea cubrir un puesto de trabajo con personal eventual durante los
prximos 4 meses. Para ello utiliza una empresa de trabajo temporal que cobra 200
euros por cada persona contratada. El primer mes, la empresa contrata una persona
y a principios de los siguientes meses decide si contrata una nueva persona o sigue
con la contratada anteriormente. Se conoce que el sueldo del primer mes trabajado
es de 900 euros y la ganancia proporcionada a la empresa es de 2000. El segundo
mes trabajado el empleado tendr un sueldo de 1000 euros proporcionando una
ganancia de 2100. Si el empleado trabaja tres meses o ms tendr un sueldo de
1100 el tercer mes y de 1200 el cuarto mes, proporcionando una ganancia de 2200 y
2300 para el tercer y cuarto mes, respectivamente.
95
Adems, se sabe que la empresa de trabajo temporal al finalizar el contrato de un
trabajador que ha trabajado durante 1, 2, 3 4 meses debe abonarle 100, 200, 300
650 euros respectivamente.
a) (8 puntos) Calcular la poltica de contratacin de trabajadores para los
prximos 4 meses que proporcione un mayor beneficio a la empresa.
b) (2 puntos) Si la empresa deseara cubrir el puesto de trabajo durante los
prximos 3 meses, cul sera la mejor poltica de contratacin? Y su
beneficio mximo?
Solucin:
a) Este es un problema de reemplazamiento de contratos para maximizar
beneficios, cuya red asociada es:
1800
2 800
8 2800 4 2800
800 3
800
2800
800
1 0
3550
3 1800
d (1, 4 ) = 2000 + 2100 + 2200 900 1000 1100 300 200 = 2800 = d ( 2,5)
d (1,5 ) = 2000 + 2100 + 2200 + 2300 900 1000 1100 1200 650 200 = 3550
96
Las polticas de contratacin ptimas se corresponden con los caminos ms
largos del origen al destino. Aplicando el mtodo de la ruta ms larga se tiene
que las polticas de contratacin ptimas son:
(1,2,5) Contratar un empleado durante un mes y despus otro empleado
durante tres meses.
(1,3,5) Contratar un empleado durante dos meses y despus otro empleado
durante dos meses.
(1,4,5) Contratar un empleado durante tres meses y despus otro empleado
durante un mes.
El beneficio mximo es de 3600 euros.
3. (10 puntos) Una fbrica de quesos produce tres tipos de quesos: queso curado,
queso semicurado y queso fresco. Para ello se utilizan dos tipos de leche, leche de
oveja y leche de cabra. La fbrica est dotada de dos tipos de mquinas. La
mquina 1, utiliza en cada hora 70 litros de leche de oveja y 200 litros de leche de
cabra para producir 9 kilogramos de queso curado, 2 kilogramos de queso
semicurado y 5 kilogramos de queso fresco. Con la mquina 2, se obtienen cada
hora 10, 5 y 4 kilogramos de cada queso respectivamente con un gasto de 100 litros
de leche de oveja y 80 litros de leche de cabra.
Teniendo en cuenta los estudios de demanda de los tres productos la compaa
estima que debe producir al da al menos 900 y 300 kilogramos de queso curado y
semicurado, respectivamente, y no ms de 800 kilogramos de queso fresco. Los
beneficios por kilogramo producido de cada tipo de queso son de 4, 6, y 7 euros
respectivamente.
La gerencia de la empresa se ha planteado las siguientes metas y objetivos con el
siguiente orden de prioridades:
Prioridad 1. La cantidad de leche utilizada para la produccin de los quesos no
supere 14000 litros diarios para la leche de oveja y 20000 litros diarios para la
leche de cabra.
97
Prioridad 2. La cantidad de leche de cabra no sea superior a la de oveja.
Prioridad 3. Maximizar beneficios.
Modelizar y resolver el problema para calcular el nmero de horas al da que deben
operar las mquinas.
Solucin:
Definimos las variables de decisin siguientes:
x1 = horas al da que debe operar la mquina 1
x2 = horas al da que debe operar la mquina 2
(
Min L y1+ + y2+ , y3 , ( 4 (9 x1 + 10 x2 ) + 6 (2 x1 + 5 x2 ) + 7 (5 x1 + 4 x2 ) ) )
9 x1 + 10 x2 900 (1)
2 x + 5 x 300 (2)
1 2
5 x1 + 4 x2 800 (3)
70 x1 + 100 x2 y1+ + y1 = 14000 (4)
s.a +
200 x1 + 80 x2 y2 + y2 = 20000 (5)
70 x + 100 x 200 x 80 x y + + y = 0 (6)
1 2 1 2 3 3
x1 0, x2 0
yi 0, yi+ 0 i = 1, 2, 3
98
(
P1 Min y1+ + y2+ )
9 x1 + 10 x2 900 (1)
2 x1 + 5 x2 300 (2)
5 x + 4 x 800 (3)
1 2
s.a 70 x1 + 100 x2 y1+ + y1 = 14000 (4)
+
200 x1 + 80 x2 y2 + y2 = 20000 (5)
x 0, x 0
1 2
y1 0, y1+ 0, y2 0, y2+ 0
Soluciones ptimas: A
Valor ptimo: 0
( )
P2 Min y3
9 x1 + 10 x2 900 (1)
2 x + 5 x 300 (2)
1 2
5 x1 + 4 x2 800 (3)
70 x1 + 100 x2 y1+ + y1 = 14000 (4)
+
200 x1 + 80 x2 y2 + y2 = 20000 (5)
s.a x 0, x 0
1 2
y1 0, y1+ = 0
y2 0, y2+ = 0
130 x1 + 20 x2 y3+ + y3 = 0 (6)
+
y3 0, y3 0
99
Soluciones ptimas: B
Valor ptimo: 0
P3 Min ( 83 x1 98 x2 )
9 x1 + 10 x2 900 (1)
2 x1 + 5 x2 300 (2)
5 x1 + 4 x2 800 (3)
70 x1 + 100 x2 y1+ + y1 = 14000 (4)
+
200 x1 + 80 x2 y2 + y2 = 20000 (5)
s.a x 0, x 0
1 2
+
y1 0, y1 = 0
y2 0, y2+ = 0
130 x1 + 20 x2 y3+ + y3 = 0 (6)
+
y3 = 0, y3 0
Precedentes
Actividad Descripcin Duracin
Inmediatas
a Hacer el guin -- 30
b Localizar exteriores a 10
c Permisos para rodar en exteriores b 4
d Localizar interiores a 8
e Contratar actores a 10
f Contratar personal tcnico a 8
g Alojamiento actores y personal tcnico e, f 1
h Vestuario e 5
i Rodar escenas exteriores sin actores c, f 1
j Rodar con actores i, h, g, d 20
a) (6 puntos) Elaborar una red que represente el proyecto. Indicar el o los caminos
crticos y la duracin prevista del proyecto.
b) (2 puntos) Si la localizacin de interiores se retrasa en 2 das, afecta este
retraso a la duracin prevista del proyecto? Por qu?
c) (2 puntos) Si por problemas de produccin el objetivo fuese reducir el tiempo
de rodaje sera una poltica adecuada eliminar el rodaje en exteriores (eliminar
actividades b, c, i)? Por qu?
101
Solucin:
a) La siguiente red representa a este proyecto:
d(8)
0
1 30
e(10) 40
0 2 h(5)
3
a(30) 30 45
40
8
f(8) 40 45
7
b(10) 38 44 g(1)
4 j(20)
44
i(1)
40 44 65
c(4)
5 6 9
40 44 65
c) No. La d.p.p. sera la misma, ya que estas actividades no forman parte de uno
de los caminos crticos, el camino (1,2,3,8,9).
102
INVESTIGACION OPERATIVA (3 LADE)
Junio 2008
1. (10 puntos) Una empresa fabrica dos productos A y B que se procesan en tres
mquinas M1, M2 y M3. Los tiempos de procesamiento en horas de cada unidad de
producto en cada mquina, los ingresos unitarios de cada producto y las
disponibilidades semanales de cada mquina estn recogidos en la siguiente tabla:
Disponibilidad
A B semanal (horas)
M1 3 5 30
M2 1 10 35
M3 2 8 40
Ingresos unitarios
1000 2000
(euros)
Solucin:
Definimos las variables de decisin siguientes:
xi = nmero de unidades del producto i que se producen a la semana i = A, B
103
Max (1000 x A + 2000 xB 400 z1 600 z2 500 z3 )
3 x A + 5 xB 30 + 10 z1
x + 10 x 35 + 15 z
A B 2
2 x A + 8 xB 40 + 20 z3
s.a z2 z1
400 z + 600 z + 500 z 1200 ( )
1 2 3
xi 0 y enteras i = A, B
z = 0, 1 j = 1, 2, 3
j
Solucin:
El conjunto X de soluciones factibles del problema es:
104
P1 Min ( y1+ )
x1 + x2 40 (1)
2 x1 + x2 y1+ + y1 = 60 (2)
s.a
x1 0, x2 0
+
y1 0, y1 0
Soluciones ptimas: A
Valor ptimo: 0
P2 Min ( y2 + y3+ )
x + x 40 (1)
1 2
+
2 x1 + x2 y1 + y1 = 60 (2)
x1 0, x2 0
+
s.a y1 0, y1 = 0
3x x y + + y =0 (3)
1 2 2 2
x 3 x y + + y =0 (4)
1 2 3 3
+ +
y2 0, y2 0, y3 0, y3 0
Soluciones ptimas: B
Valor ptimo: 0
105
P3 Min ( y4 )
x1 + x2 40 (1)
2 x1 + x2 y1+ + y1 = 60 (2)
x1 0, x2 0
+
y1 0, y1 = 0
3x1 x2 y2+ + y2 =0 (3)
s.a
x1 3 x2 y3+ + y3 =0 (4)
y2 = 0, y2+ 0
y 0, y + = 0
3 3
4 x + 3 x y + + y =180 (5)
1 2 4 4
+
y4 0, y4 0,
Solucin ptima: (20, 20)
Valor ptimo: 40
Solucin ptima: x1 = 20, x2 = 20
3. Una compaa estatal de petrleo cuenta con una red de oleoductos que utiliza para
transportar petrleo desde su refinera R hasta su centro de almacenamiento A,
como se muestra en el grafo siguiente. Cada arco viene valorado por la capacidad
mxima diaria que se puede enviar, en miles de litros.
4
1
8 5 12
1 1
3
R 2 4 1
2 A
9
3 4 6
10
106
Solucin:
a) Partimos del flujo nulo y consideramos la cadena de crecimiento del origen al
destino (R,1,5,A). El incremento de flujo que permite esta cadena viene dado
por f ( R,1,5, A ) = min {8, 4,12} = 4 y llegamos al siguiente flujo cuyo valor
4,4
1
8,4 5 12,4
1,0 1,0
3,0
R 2 4,0 1,0
2,0 A
9,0
3 4 6,0
10,0
4,4
1
8,5 5 12,5
1,1 1,1
3,0
R 2 4,0 1,0
2,0 A
9,0
3 4 6,0
10,0
4,4
1
8,5 5 12,6
1,1 1,1
3,1
R 2 4,1
1,1
2,0 A
9,0
3 4 6,0
10,0
107
f ( R, 2, 4, A ) = min {3 1, 4 1, 6 0} = 2 y llegamos al siguiente flujo cuyo
4,4
1
8,5 5 12,6
1,1 1,1
3,3
R 2 4,3
1,1
2,0 A
9,0
3 4 6,2
10,0
4,4
1
8,5 5 12,6
1,1 1,1
3,3
R 2 4,3 1,1
2,0 A
9,4
3 4 6,6
10,4
4,4
1
8,5 5 12,9
1,1 4,4
3,3
R 2 4,0 1,1
2,0 A
9,7
3 4 6,6
10,7
108
No existe ninguna cadena de crecimiento del nodo R al nodo A. Luego este
flujo es un flujo mximo y su valor es 15000 litros diarios. Si queremos mandar
60000 litros, ahora se necesitan 4 das, luego se reducira en un da.
Precedentes
Actividades Descripcin Duracin
Inmediatas
A Inventario (Recuento fsico) 2 --
109
Solucin:
G 7 K
D
2 4 I J 10
D 8 9
E
C
E5 L
1
F
A
H
3 6 11
4
2
2 5 6
4
2
1 4
7 8
3 2 4
3 6 1
1
110
Solucin:
a)
2 6
2 4 5 6
2 7
13
2
8
4 13
0 6 9
2
1 4 7
0 4
6 9
3 2
1
3 8
1
3 6
6 8
b)
2 6
2 4 5 6
12
2
8
0 3
5 2 8
1 4
4 7
3 2
1
3 7
1
3 6
111
Si la duracin de la actividad (2,4) se redujera en un da, la duracin prevista
del proyecto se reducira en un da, es decir durara 12 das. Los caminos
crticos seran: (1,2,4,6,7,8) y (1,2,5,8).
112
INVESTIGACION OPERATIVA (3 LADE)
Septiembre 2008
Solucin:
a) Definimos las variables de decisin siguientes:
xi = euros invertidos en el fondo i i = 1,...,7
1 si se invierte en el fondo i
yi = con i=1,,7
0 en caso contrario
La modelizacin queda como sigue:
113
Max (R1 x1 + R 2 x2 + ... + R 7 x7 )
x1 + ... + x7 1000000
y y
2 1
y4 y1 + y3 1
y6 1 y1
s.a y6 1 y4
y + y y
2 5 7
600 yi xi Myi i = 1,..., 7
x 0 i = 1,...,7
i
yi = 0, 1 i = 1,...,7
114
Dadas las necesidades existentes, para que el proyecto resulte factible y apropiado,
el nmero total de habitaciones debe ser como mucho 400, y las habitaciones
pequeas deben ser al menos el 40% del total de habitaciones
El coste de construccin de cada habitacin pequea es de 40000 y de cada
habitacin grande 60000 . La corporacin pretende minimizar el coste de
construccin y maximizar la capacidad de estudiantes de la residencia.
a) Modelizar el problema multiobjetivo y encontrar todas las soluciones eficientes
del problema relajado.
b) Sabiendo que cada habitacin pequea requiere 22 m2 y cada habitacin grande
28 m2, si adems de los dos objetivos anteriores se pretende tambin minimizar
el espacio construido, obtener 2 soluciones eficientes del nuevo problema
multiobjetivo.
Solucin:
a) Definimos las variables de decisin siguientes:
x1 = nmero de habitaciones pequeas
x2 = nmero de habitaciones grandes
La modelizacin del modelo multiobjetivo relajado queda como sigue:
Max ( 40000x1 60000 x2 , 2 x1 + 4 x2 )
x1 + x2 400 (1)
s.a x1 0.4 ( x1 + x2 ) (2)
x 0, x 0
1 2
115
Vrtices Vrtices
X f (X )
(0, 0) (0, 0)
(400,0) (16000000,800)
(160, 240) (20800000,1280)
116
La solucin ptima es (160,240), luego (160,240) es solucin eficiente del
modelo multiobjetivo.
3. (10 puntos) Una empresa dispone de dos camiones frigorficos C1 y C2 con una
capacidad de 100 y 60 toneladas respectivamente. La empresa desea realizar un
slo viaje y hay 4 cargas para transportar, A y B de 40 toneladas cada una y C y D
de 50 toneladas cada una. El beneficio de transporte por carga en miles de euros se
indica en la tabla
A B C D
C1 10 10 8 8
C2 6 6 4 4
Solucin:
a) Aplicamos el Mtodo Hngaro a la siguiente tabla:
b)
A B C D
C1 -10 -10 -8 -8 +10
C1 -10 -10 -8 -8 +10
C2 -6 -6 -4 -4 +6
F1 0 0 0 0
117
A B C D
C1 0 0 2 2 -2
C1 0 0 2 2 -2
C2 0 0 2 2 -2
F1 0 0 0 0
+2 +2
A B C D
C1 0 0 0 0
C1 0 0 0 0
C2 0 0 0 0
F1 2 2 0 0
118
A B C D F1 F2
C1 -10 -18 -8 -8 0 0
C1 -10 -10 -8 -8 M M
C2 -6 -6 -4 -4 M M
C3 M M -7 -7 0 0
C3 M M -7 -7 0 0
C3 M M -7 -7 0 0
Con M positivo suficientemente grande.
4. (10 puntos) La siguiente red representa un proyecto, cada arco una actividad del
mismo y su valor asociado su duracin en das. La duracin de la actividad (3,7)
viene dada por t, donde t 10 .
t
3
12 7 6
4 5
1
5 8
7
10 8 9
7
2 4 6
6 11
119
Solucin:
a)
12 23
t
3 7
16 30
12 4 5 6
0 18 36
1 5 7 8
0 20 36
7
10 8 9
10 16 27
2 4 6
10 6 16 11 27
b) CMT ( 3,5 ) = P ( 3) = 12
CMT ( 5, 6 ) = P ( 5 ) = 18
FMT * ( 3,5 ) = Q ( 5 ) = 20
FMT * ( 5, 6 ) = Q ( 6 ) = 27
M ( 5, 6 ) = FMT * ( 5, 6 ) CMT ( 5, 6 ) t ( 5, 6 ) = 27 18 7 = 2
120
d) Si la duracin de la actividad (5,7) se retrasa 2 das, su margen se reduce en dos
das. Adems este retraso afecta al comienzo ms temprano de la actividad
(7,8), que se retrasa en 2 das, luego el margen de esta actividad tambin se
reduce en 2 das.
121
INVESTIGACION OPERATIVA (3 LADE)
Extraordinario Febrero 2009
Solucin:
a) Definimos las variables de decisin siguientes:
x1 = nmero de operaciones de rin al da
122
1 si se realizan operaciones de vescula
y3 =
0 en caso contrario
La modelizacin queda como sigue:
Max ( x1 + x2 + x3 )
2 x1 + 3x2 + x3 20
x1 + 5 x2 + x3 60
y + y + y 2
1 2 3
x1 x3
s.a x1 My1
x2 My2
x 50 y
3 3
x 0 i = 1, 2,3 y enteras
i
y = 0, 1 i = 1, 2,3
i
Con M positivo suficientemente grande.
123
2. En la tabla siguiente quedan recogidas las actividades que componen un proyecto
as como la duracin en das y las relaciones de precedencia de dichas actividades:
124
Solucin:
a) La siguiente red representa a este proyecto:
7 10 23
A4 (3)
4 5 8
7 10 A8 (7) 23
A1 (7)
A5 (2)
A3 (1)
17
A9 (3)
A2 (5) 5 12 7
0 A6 (7)
2 6 17 A11 (6)
1
0 6 14
A7 (8)
13 A10 (2)
3
15
125
c) El tiempo mximo que se puede esperar desde el inicio del proyecto para dar
comienzo a la actividad A6, sin variar la duracin prevista del proyecto, es de 7
das, ya que el margen de dicha actividad es 2.
3. (10 puntos) Una empresa produce dos productos A y B. Cada unidad de A requiere
2 horas de trabajo y 3 unidades de materia prima y cada unidad de B requiere 4
horas de trabajo y 3 unidades de materia prima. Para su produccin, la empresa
dispone al da de 12 unidades de materia prima. La empresa obtiene 200 de
beneficio por cada unidad de A y 400 por cada unidad de B. Modelizar y resolver
el problema, sabiendo que la empresa se ha fijado las siguientes prioridades para las
metas:
Prioridad 1: Las horas de trabajo diarias no sean inferiores a 8.
Prioridad 2: Los beneficios alcanzados sean al menos 1600 .
Prioridad 3: Por cada unidad de B no se produzcan ms de tres unidades de A.
Solucin:
Definimos las variables de decisin siguientes:
x1 = unidades producidas diariamente del producto A
x2 = unidades producidas diariamente del producto B
La modelizacin queda como sigue:
Min L( y1 , y2 , y3+ )
3 x1 + 3x2 12 (1)
2 x1 + 4 x2 y1+ + y1 = 8 (2)
200 x1 + 400 x2 y2+ + y2 = 1600 (3)
s.a
x 3x y + + y = 0 (4)
1 2 3 3
x1 0, x2 0 y enteras
y 0, y + 0 i = 1, 2, 3
i i
126
Resolveremos el problema relajado. El conjunto de soluciones factibles ser:
P1 Min ( y1 )
3x1 + 3 x2 12 (1)
2 x + 4 x y + + y = 8 (2)
s.a 1 2 1 1
x1 0, x2 0
+
y1 0, y1 0
Soluciones ptimas: A
Valor ptimo: 0
P2 Min (y2 )
3 x + 3 x 12 (1)
1 2
+
2 x1 + 4 x2 y1 + y1 = 8 (2)
x 0, x2 0
s.a 1
y = 0, y + 0
1 1
200 x + 400 x y + + y = 1600 (3)
1 2 2 2
+
y2 0, y2 0
127
Solucin ptima: (0,4)
Valor ptimo: 0
P3 Min (y3+ )
3 x1 + 3 x2 12 (1)
2 x + 4 x y + + y = 8 (2)
1 2 1 1
x 0, x 0
1 2
y = 0, y + 0
1 1
s.a
200 x1 + 400 x2 y2+ + y2 = 1600 (3)
y2 = 0, y2+ 0
x 3 x y + + y = 0 (4)
1 2 3 3
+
y3 0, y3 0
128
La solucin ptima consiste en producir diariamente 4 unidades del producto B y
ninguna unidad del producto A.
Las horas de trabajo diarias con esta produccin ptima son 16 ( y1 = 0, y1+ = 8 ).
Polideportivo
P1 P2 P3 P4
Distrito
A 12 14 17 19
B 16 19 24 17
C 10 12 18 15
D 13 9 20 17
Solucin:
Aplicamos el Mtodo Hngaro a la siguiente tabla:
129
P1 P2 P3 P4 F1
A -12 -14 -17 -19 M
B -16 -19 -24 -17 M
B -16 -19 -24 -17 0
C -10 -12 -18 -15 0
D -13 -9 -20 -17 0
Con M positivo suficientemente grande.
P1 P2 P3 P4 F1
A -12 -14 -17 -19 M
B -16 -19 -24 -17 M
B -16 -19 -24 -17 0
C -10 -12 -18 -15 0
D -13 -9 -20 -17 0
+16 +19 +24 +19
Con M positivo suficientemente grande.
P1 P2 P3 P4 F1
A 4 5 7 0 M
B 0 0 0 2 M
B 0 0 0 2 0
C 6 7 6 4 0
D 3 10 4 2 0
Con M positivo suficientemente grande.
P1 P2 P3 P4 F1
A 4 5 7 0 M -3
B 0 0 0 2 M
B 0 0 0 2 0
C 6 7 6 4 0 -3
D 3 10 4 2 0 -3
+3 +3
Con M positivo suficientemente grande.
130
P1 P2 P3 P4 F1
A 1 2 4 0 M
B 0 0 0 5 M
B 0 0 0 5 3
C 3 4 3 4 0
D 0 7 1 2 0
Con M positivo suficientemente grande.
131
INVESTIGACION OPERATIVA (3 LADE)
Junio 2009
El coste de las semillas y fertilizantes por hectrea cultivada, para cada uno de los
productos, junto con el coste fijo del cultivo de cada uno de ellos vienen reflejados
en la siguiente tabla:
132
Tomates Pimientos Zanahorias Cebollas Lechugas
Horas/ha 4 2 2 1 2
Implantar este nuevo sistema de labranza requiere una inversin inicial de 1000 .
Modelizar el problema incorporando las 2 alternativas: continuar con el actual
sistema de labranza o implantar el nuevo.
Solucin:
a) Definimos las variables de decisin siguientes:
xi = hectreas cultivadas del producto i
i=1,,5 (1 son tomates, 2 pimientos, 3 zanahorias, 4 cebollas y 5 lechugas)
1 si se cultiva el producto i
yi = con i=1,,5
0 en caso contrario
La modelizacin queda como sigue:
Min ( 25 x1 + 15 x2 + 10 x3 + 8 x4 + 25 x5 + 100 y1 + 120 y2 + 100 y3 + 80 y4 + 150 y5 )
x1 + x2 + x3 + x4 + x5 100
5 x + 4 x + 5 x + 2 x + 3 x 300
1 2 3 4 5
3 y1 + y2 + y3 + y4 + y5 4
s.a y4 1 y1
y y
5 2
0 xi Myi i = 1,..., 5
y = 0,1 i = 1,..., 5
i
Con M positivo suficientemente grande.
133
Min ( 25 x1 + 15 x2 + 10 x3 + 8 x4 + 25 x5 + 100 y1 + 120 y2 + 100 y3 + 80 y4 + 150 y5 +
+1000 z )
x1 + x2 + x3 + x4 + x5 100
5 x + 4 x + 5 x + 2 x + 3 x 300 + Mz
1 2 3 4 5
4 x1 + 2 x2 + 2 x3 + 1x4 + 2 x5 300 + M (1 z )
3 y1 + y2 + y3 + y4 + y5 4
s.a y4 1 y1
y y
5 2
0 xi Myi i = 1,...,5
yi = 0, 1 i = 1,...,5
z = 0, 1
2. (10 puntos) Una empresa dedicada a la elaboracin de piensos produce dos tipos de
compuestos C1 y C2 a partir de dos materias primas A y B. Para producir 1 tonelada.
de C1 se necesitan 0.25 toneladas de materia prima A y 0.75 toneladas de B, y para
producir 1 tonelada de C2 se necesitan 0.5 toneladas de A y 0.5 toneladas de B. El
beneficio por tonelada de C1 es de 1 unidad monetaria y por tonelada de C2 son 2
unidades monetarias.
Las cantidades totales semanales disponibles de las materias A y B son 10 y 18
toneladas respectivamente.
Para ajustarse al programa comunitario de elaboracin de pienso, la empresa se
plantea las siguientes metas y objetivos, en el siguiente orden de prioridades.
Prioridad 1: Desea obtener con el compuesto C2 al menos tanto beneficio
semanal como con el compuesto C1.
Prioridad 2: Desea que la produccin semanal de C1 no sea inferior a 16
toneladas.
Prioridad 3: Minimizar la produccin semanal de C2.
Determinar la produccin ptima semanal de cada uno de los compuestos.
Interpretar la solucin obtenida planteando y resolviendo grficamente cada una de
las metas y objetivos.
134
Solucin:
Definimos las variables de decisin siguientes:
x1 = produccin semanal en toneladas del compuesto C1
Min L( y1 , y2 , x2 )
0.25 x1 + 0.5 x2 10 (1)
0.75 x1 + 0.5 x2 18 (2)
+
2 x2 x1 y1 + y1 = 0 (3)
s.a
x1 y2+ + y2 = 16 (4)
x1 0, x2 0
yi 0, yi+ 0 i = 1, 2
P1 Min ( y1 )
0.25 x1 + 0.5 x2 10 (1)
0.75 x + 0.5 x 18 (2)
1 2
+
s.a 2 x2 x1 y1 + y1 = 0 (3)
x 0, x 0
1 2
y 0, y + 0 i = 1, 2
i i
Soluciones ptimas: A
Valor ptimo: 0
135
P2 Min ( y2 )
0.25 x1 + 0.5 x2 10 (1)
0.75 x + 0.5 x 18 (2)
1 2
2 x x y + y = 0
+
(3)
2 1 1 1
x 0, x 0
s.a 1 2
y = 0, y + 0
1 1
x y + + y = 16 (4)
1 2 2
y2 0, y2+ 0
Soluciones ptimas: B
Valor ptimo: 0
P3 Min ( x2 )
0.25 x1 + 0.5 x2 10 (1)
0.75 x1 + 0.5 x2 18 (2)
2 x2 x1 y1+ + y1 = 0 (3)
s.a x1 0, x2 0
y1 = 0, y1+ 0
x1 y2+ + y2 = 16 (4)
y2 = 0, y2+ 0
Solucin ptima: (16,8)
Valor ptimo: 8
136
3. El director general de una empresa de publicidad se enfrenta al problema de asignar
publicistas a 4 nuevos clientes importantes: C1, C2, C3 y C4. En la tabla se
presenta el coste estimado que le supondra asignar sus 3 mejores publicistas P1, P2
y P3 a cada uno de los clientes, en miles de euros:
P1 P2 P3
C1 4 6 8
C2 2 3 4
C2 4 8 5
C4 1 2 6
Solucin:
a) Aplicamos el Mtodo Hngaro a la siguiente tabla:
P1 P2 P3 F1
C1 4 6 8 0
C2 2 3 4 0
C3 4 8 5 0
C4 1 2 6 0
-1 -2 -4
P1 P2 P3 F1
C1 3 4 4 0
C2 1 1 0 0
C3 3 6 1 0
C4 0 0 2 0
137
P1 P2 P3 F1
C1 3 4 4 0 -1
C2 1 1 0 0
C3 3 6 1 0 -1
C4 0 0 2 0
+1
P1 P2 P3 F1
C1 2 3 3 0 -1
C2 1 1 0 1 -1
C3 2 5 0 0 -1
C4 0 0 2 1
+1 +1
P1 P2 P3 F1
C1 1 2 3 0
C2 0 0 0 1
C3 1 4 0 0
C4 0 0 3 2
138
b) Aplicaremos el Mtodo Hngaro a la siguiente tabla:
P1 P2 P3 P1 P2 P3
C1 4 6 8 4 6 8
C2 2 3 4 2 3 4
C3 4 8 5 4 8 5
C4 1 2 6 1 2 6
F1 0 0 0 M M M
F2 0 0 0 M M M
Con M positivo suficientemente grande.
4. Una empresa desea diversificar su oferta hacia un nuevo segmento del mercado, y
para ello, encarga al departamento de marketing que realice un estudio de mercado.
El departamento de marketing elabora una lista con las actividades a realizar, la
duracin de cada una de las actividades y las relaciones entre ellas, tal y como se
muestra en la siguiente tabla:
Realizar encuestas y
E (5, 6) 10 CyD
codificar informacin
Disear la entrevista y
F (3, 4) seleccionar expertos para la 2 AyB
entrevista
G (4, 6) Realizacin de entrevistas t F
Anlisis de la informacin
H (6, 7) k EyG
cuantitativa y cualitativa
139
donde la duracin de la actividad G y H vienen dadas por las variables t y k
respectivamente.
a) (2 puntos) Elaborar el grafo asociado al proyecto aadiendo actividades
ficticias si fuera necesario para mantener las relaciones de precedencia
indicadas en la tabla y teniendo en cuenta la numeracin de los arcos indicada.
b) (8 puntos) Si se sabe que t es menor que 9 das:
i) Es posible calcular la duracin prevista del proyecto y el camino crtico
independientemente de los valores que toman t y k? Calcularlos en
funcin de t y k si fuese necesario.
ii) Qu valores puede tomar k si se desea concluir el proyecto en menos de
25 das?
iii) Si se sabe que para no retrasar la duracin prevista del proyecto la
actividad F debe estar finalizada el sexto da cul es el valor de t?
Teniendo en cuenta el valor obtenido cuntos das se podr retrasar la
actividad G para no retrasar la duracin prevista del proyecto?
Solucin:
a) La siguiente red representa a este proyecto:
3 F(2) 5
3 4
A(3) 3 14-t
G(t<9)
D(1)
14 14+k 17+k
0 6 7 8
1 14 H(k) 14+k I(3) 17+k
0
E(10)
B(1) 1 4
2 5
2 C(2) 4
b)
i) Si t < 9 , la duracin prevista del proyecto (d.p.p.) es 17+k y el camino
crtico es (1,3,5,6,7,8).
140
d.p.p. < 25 17 + k < 25 k < 8 . Luego la duracin de la actividad H
ha de ser inferior a 8 das.
G ha de ser de 8 das.
Si t = 8 , se tiene que:
M ( 4, 6 ) = FMT * ( 4, 6 ) CMT ( 4, 6 ) t ( 4, 6 ) = Q ( 6 ) P ( 4 ) 8 = 14 5 8 = 1
Luego la actividad G se podr retrasar a lo sumo 1 da para que la
duracin prevista del proyecto no se vea afectada.
141
INVESTIGACION OPERATIVA (3 LADE)
Septiembre 2009
Solucin:
a) Resolucin del problema relajado:
PR
142
PR
R = (1.2 ,0) z R = 1.2
Cota = ---
x1 1
x1 2
P2 P1
2 = (1,0.5) z2 = 1.5 1 = (2,1) z1 = 3
Cota = 3 Cota = 3
x2 0 x2 1
Terminal
P6 P3
3 = (0.8,1) z3 = 1.8
Infactible
Cota = 3
Terminal x1 0 x1 1
P5 P4
5 = (0,3) z5 = 3 4 = (1,1) z4 = 2
Cota = 2 Cota = 2
Terminal Terminal
P1
143
P2
P3
P4
144
P5
Solucin: = (1,1)
z =2
b) Si: > 5 / 2 entonces la solucin del Problema Relajado es:
R = (0,3)
zR = 3
Dado que la solucin tiene ambas variables enteras sta ser la solucin del
Problema Lineal Entero.
145
Cada seminario se impartir en una de las salas de reuniones de la sede central en
Madrid, cada una de ellas con capacidad mxima para 8 personas.
Solucin:
a) Este problema puede ser modelizado como un problema de flujo de
trabajadores mediante el siguiente grafo.
Bilbao 4
1,
S1
2
7 Barcelona 3 8
5
7 2 2 8
O Sevilla S2 D
3
2
Valencia 2 8
6
3 S3
1
Zaragoza
146
b) Un grafo que representa esta situacin es:
Bilbao 4, 4
1, 1
S1
7, 5 2, 2
Barcelona 3, 3 8, 6
5, 5
7, 5 2 2, 2 8, 8
O Sevilla S2 D
3, 3
2, 2
2, 2
8, 4
6, 1 Valencia
3 1, 1 S3
Zaragoza
Bilbao 4, 4
1, 1
S1
7, 5 2, 2
Barcelona 3, 3 8, 8
5, 5
2,2
7, 7 2, 2 8, 8
O Sevilla S2 D
3, 3
2, 2
2, 2
8, 4
6, 1 Valencia
3,0 1, 1 S3
Zaragoza
En esta nueva situacin todas las cadenas del origen al destino estn saturadas,
por tanto el flujo que atraviesa la red es mximo y de valor V f = 20 .
147
c) Se crea un nuevo arco desde Valencia al seminario S3 con una capacidad de 2.
Bilbao 4, 4
1, 1
S1
7, 5 2, 2
Barcelona 3, 3 8, 8
5, 5
2, 2
7, 7 2, 2 8, 8
O Sevilla S2 D
3, 3
2, 2
2, 2
8, 4
6, 1 Valencia 2,0
3,0 S3
1, 1
Zaragoza
En esta nueva situacin hay una cadena de crecimiento (no saturada), la cadena
(O,Zaragoza,S2,Valencia, S3,D), ya que sus arcos directos no estn saturados y
su inverso no tiene flujo nulo. Considerando esta cadena el valor del flujo
puede aumentar en:
f ( O, Zaragoza,S2, Valencia, S3, D ) = min {6 1,3 0, 2, 2 0,8 4} = 2 .
Bilbao 4, 4
1, 1
S1
7, 5 2, 2
Barcelona 3, 3 8, 8
5, 5
2, 2
7, 7 2, 2 8, 8
O S2 D
Sevilla
3, 3
2, 2
2, 0
8, 6
Valencia 2, 2
6, 3 S3
3, 2
1, 1
Zaragoza
148
3. Una empresa realiza dos tipos de bombones, de calidad excelente y de primera
calidad. Para producirlos utiliza cacao y almendras, de los que dispone
semanalmente de 48 kilos y 4.5 kilos respectivamente. Para realizar una caja de
bombones de calidad excelente se necesita 600 gramos de cacao y 50 gramos de
almendras mientras que para una caja de primera calidad se necesita 400 gramos de
cacao y 50 gramos de almendras. Por cada caja de calidad excelente se obtiene un
beneficio de 70 y por cada una de primera calidad de 40 y adems se vende sin
problemas todo lo que se produce.
a) (5 puntos) Determinar, resolviendo el problema relajado, las producciones
semanales eficientes de cajas de bombones de modo que la empresa maximice
sus beneficios y el volumen de ventas.
b) (2 puntos) Si la empresa considera cada venta como 10 de beneficio,
modelizar el problema relajado correspondiente.
c) (3 puntos) Si la empresa necesita 7 horas de produccin para obtener una caja
de calidad excelente y 4 horas para una caja de primera calidad, determinar al
menos dos producciones semanales eficientes del problema relajado de modo
que la empresa maximice sus beneficios, y el volumen de ventas y minimice
las horas de produccin.
Solucin:
a) Definimos las variables de decisin siguientes:
x1 = cajas de bombones de calidad excelente producidas semanalmente
149
Vrtices Vrtices
X f (X )
(0, 0) (0, 0)
(80, 0) (5600,80)
(60,30) (5400,90)
(0,90) (3600,90)
150
Asignando: 1 = 1, 2 = 1, 3 = 10 el modelo lineal ponderado tiene como
soluciones ptimas (0, 90)(60,30) . Estas sern soluciones eficientes del modelo
multiobjetivo.
Precedentes
Actividad Descripcin Duracin
Inmediatas
A Composicin de canciones 10 -
B Produccin 5 -
C Diseo de portada 7 -
E Fabricacin 3 CyD
F Promocin 6 E
H Distribucin 2 FyG
151
Solucin:
a) Un grafo que representa este proyecto es:
10 23 H(2) 25
2 7 8
A(10) F(6)
0 B(5) 10 17 18
1 3 5 6
G(1)
C(7) D(4)
E(3)
14
4
b) Un grafo que representa este proyecto y que recoge la nueva actividad es:
A(10)
F(6) H(2)
B(5)
1 3 7 8 9
I(5)
D(4)
C(7) 4 G(1)
6
E(3)
5
152
INVESTIGACION OPERATIVA (3 LADE)
Extraordinario Febrero 2010
Solucin:
a) Definimos las variables de decisin siguientes:
xi = nmero de llaves del tipo i producidas semanalmente i=1,2,3
153
Max (10 x1 + 15 x2 + 20 x3 1500 y1 1750 y2 1800 y3 x1 1.5 x2 2 x3 )
1.5 x1 + 0.75 x3 200
2 x + 0.75 x 150
2 3
0.75 x1 + 1.25 x2 + 0.75 x3 100
s.a
xi 0 y enteras i = 1, 2,3
xi Myi i = 1, 2,3
yi = 0, 1 i = 1, 2, 3
154
de 200 euros y el del KS600 lleva 1.5 horas de trabajo y su beneficio es de 500
euros.
Teniendo en cuenta las restricciones anteriores, el director de la compaa desea
alcanzar las siguientes metas en orden de prioridad:
Prioridad 1. Producir semanalmente al menos 200 ordenadores KS500.
Prioridad 2. Ensamblar al menos 500 ordenadores en total a la semana.
Prioridad 3. Igualar el nmero de horas totales de trabajo dedicadas al
ensamblaje de los dos tipos de ordenador.
Prioridad 4. Obtener un beneficio semanal de al menos 250000 euros.
Obtener e interpretar la solucin ptima del problema relajado, planteando y
resolviendo grficamente cada una de las metas.
Solucin:
Definimos las variables de decisin siguientes:
x1 = unidades ensambladas semanalmente del ordenador Core Duo KS500
Min L( y1 , y2 , y3+ + y3 , y4 )
2 x1 + x2 1000 (1)
x2 500 (2)
x + x 600 (3)
1 2
x y + + y = 200 (4)
1 1 1
+
s.a x1 + x2 y2 + y2 = 500 (5)
x1 1.5 x2 y3+ + y3 = 0 (6)
200 x1 + 500 x2 y4+ + y4 = 250000 (7)
x1 0, x2 0 y enteras
yi 0, yi+ 0 i = 1, 2,3,4
155
P1 Min ( y1 )
2 x1 + x2 1000 (1)
x2 500 (2)
x1 + x2 600 (3)
s.a
x1 y1+ + y1 = 200 (4)
x1 0, x2 0
+
y1 0, y1 0
Soluciones ptimas: A
Valor ptimo: 0
P2 Min ( y2 )
2 x1 + x2 1000 (1)
x2 500 (2)
x + x 600 (3)
1 2
x y + + y = 200 (4)
1 1 1
s.a x 0, x 0
1 2
+
y1 0, y1 = 0
x1 + x2 y2+ + y2 = 500 (5)
+
y2 0, y2 0
Soluciones ptimas: B
Valor ptimo: 0
156
P3 Min ( y3+ + y3 )
2 x1 + x2 1000 (1)
x2 500 (2)
x + x 600 (3)
1 2
x y + + y = 200 (4)
1 1 1
x 0, x2 0
1
s.a y + 0, y = 0
1 1
+
x1 + x2 y2 + y2 = 500 (5)
+
y2 0, y2 = 0
x1 1.5 x2 y3+ + y3 = 0 (6)
+
y3 0, y3 0
Soluciones ptimas: (300, 200)(360, 240)
Valor ptimo: 0
P4 Min ( y4 )
2 x + x2 1000 (1)
1
x2 500 (2)
x1 + x2 600 (3)
x1 y1+ + y1 = 200 (4)
x1 0, x2 0
+
y1 0, y1 = 0
s.a
+
x1 + x2 y2 + y2 = 500 (5)
+
y2 0, y2 = 0
x1 1.5 x2 y3+ + y3 = 0 (6)
y3+ = 0, y3 = 0
200 x + 500 x y + + y = 250000 (7)
1 2 4 4
y 0, y 0
+
4 4
157
Solucin ptima: (360,240)
Valor ptimo: 58000
158
Bilbao Sevilla Valencia
2 habitaciones 20 25 30
3 habitaciones 30 30 35
4 habitaciones 40 45 45
4 habitaciones y garaje 45 50 50
Solucin:
a) Aplicamos el Mtodo Hngaro a la siguiente tabla:
159
Bilbao Bilbao Sevilla Sevilla Valencia
P1 0 0 250 250 500
P2 0 0 0 0 500
P3 0 0 400 400 400
P4 0 0 400 400 400
F1 0 0 0 0 M
-400
Con M positivo suficientemente grande.
160
4. Considerar el proyecto cuyas actividades y duraciones correspondientes (en
semanas) aparecen recogidas en la siguiente tabla:
Solucin:
a) Bajo los supuestos del PERT se estima la duracin media de cada actividad
to ( i, j ) + 4tm ( i, j ) + t p ( i, j )
como t ( i, j ) = donde to representa la duracin
6
optimista, tm la ms probable y t p la pesimista.
161
Un grafo que representa a este proyecto es el siguiente, donde el valor de cada
arco es la duracin media estimada de cada actividad.
8 9 23
2 6
14 23
8 5
14
0 28
6
1 7
0 28
8 4 12 5 17
8 9
3 4 5
8 12 17
162
INVESTIGACION OPERATIVA (3 LADE)
Junio 2010
1. Una compaa produce cuatro productos P1, P2, P3 y P4. Cada uno de ellos pasa
por tres plantas de produccin: la planta A, la planta B, y la planta C. En cada
planta se dispone de una capacidad de 10000 horas semanales de trabajo.
La tabla siguiente muestra el ingreso unitario, en euros, y las horas de trabajo
necesarias en cada planta para la produccin de una unidad de cada uno de los
productos.
P1 P2 P3 P4
Ingreso unitario 6 7 8 9
Planta A 5 horas 3 horas 6 horas 4 horas
Planta B 4 horas 6 horas 3 horas 5 horas
Planta C 5 horas 6 horas 3 horas 2 horas
Solucin:
a) Definimos las variables de decisin siguientes:
xi = unidades producidas semanalmente del producto Pi , i = 1,..., 4
163
1 si se produce el producto Pi
yi = i = 1,..., 4
0 en cualquier otro caso
Solucin:
a) Definimos las variables de decisin siguientes
x1 = hectreas cultivadas de olivos
165
Vrtices Vrtices
X f (X )
(8, 2) (90000,8)
(12, 2) (130000,12)
(12,3) (135000,12)
(9, 6) (120000,9)
(8, 6) (110000,8)
Min L(y1 , x1 x2 )
x1 + x2 15
8 x 12
1
2 x2 6
s.a +
10000 x1 + 5000 x2 y1 + y1 = 140000 (1)
x1 0, x2 0
y1+ 0, y1 0
166
P1 Min (y1 )
x1 + x2 15
8 x 12
1
2 x2 6
s.a +
10000 x1 + 5000 x2 y1 + y1 = 140000 (1)
x1 0, x2 0
y1+ 0, y1 0
167
3. Dada la siguiente red donde el primer nmero del par asignado representa la
capacidad del arco:
6,3
2 5
7,6
5,5
2,2 1,1 3,2
6,5 3,2
1 3 3,3 6 8
2,2 1,1
1,1
a,6
8,8
4 7
12,8
donde a 6 .
a) (5 puntos) Si la capacidad del arco (1,4) es 6, la asignacin dada en la red es
un flujo? Es un flujo mximo? (Contestar razonadamente a las preguntas).
b) (5 puntos) A partir de la asignacin dada en la red, calcular el valor del flujo
mximo para a = 8 .
Solucin:
a) La asignacin dada en la red es un flujo ya que:
El valor de cada arco es un nmero no negativo y no excede la capacidad
del arco.
Para cada nodo (excepto el origen y el destino), la suma de los valores de
los arcos que llegan al nodo es igual a la suma de los valores de los arcos
que salen de dicho nodo:
Nodo 2: 5 = 2 + 3
Nodo 3: 5 + 2 = 1 + 3 + 1 + 2
Nodo 4: 6 + 2 = 8
Nodo 5: 3 + 1 + 2 = 6
Nodo 6: 3 + 1 = 2 + 2
Nodo 7: 1 + 8 = 1 + 8
Para este flujo la cadena (1,3,2,5,8) no est saturada, ya que sus arcos directos
no estn saturados y el inverso no tiene flujo nulo. El valor del flujo puede
168
aumentar en: f (1,3, 2,5,8 ) = min {6 5, 2, 6 3, 7 6} = 1 , luego este flujo no
es mximo.
6,4
2 5
7,7
5,5
2,1 1,1 3,2
6,6 3,2
1 3 3,3 6 8
2,2 1,1
1,1
8,6
8,8
4 7
12,8
6,5
2 5
7,7
5,5
2,0 1,1 3,1
6,6 3,3
1 3 3,3 6 8
2,1 1,1
1,1
8,7
8,8
4 7
12,8
169
4. En el grafo siguiente se representa un proyecto. En los arcos se indica los tiempos
optimista, modal y pesimista, en das, de las diferentes actividades.
(4,4,4)
3 4
(3,4,5)
(6,7,8)
(5,6,7)
(3,6,9)
5 6 7
1 (1,3,5)
(2,3,4) (5,13,15)
2
Solucin:
a) Bajo los supuestos del PERT se estima la duracin media de cada actividad
to ( i, j ) + 4tm ( i, j ) + t p ( i, j )
como t ( i, j ) = donde to representa la duracin
6
optimista, tm la ms probable y t p la pesimista. Y la varianza de la duracin de
t p ( i, j ) to ( i, j )
2
170
Un grafo que representa a este proyecto es el siguiente, donde el valor de cada
arco es la duracin media estimada de cada actividad.
7 4 11
3 4 4
7 7 11
6
17 20 6 26
0 5 6 7
1 17 3 20 26
0
3 3 12
2
5
b)
i) Si t 8 , un grafo que representa a este proyecto es el siguiente
7 4 11
3 4 4
7 t-1 11
6
t 8 17 20 6 26
0 5 6 7
1 17 3 20 26
0
3 3 12
2
3
171
7 4 3+t
3 4 4
7 t-1 3+t
6
3 3 12
2
3
172
INVESTIGACION OPERATIVA (3 LADE)
Septiembre 2010
Solucin:
Resolucin del problema relajado:
PR
173
PR
R = (4/ 3, 5/3)
z R = 17 / 3
Cota = ---
x1 1 x1 2
P1 P2
1 = (1 , 5/ 2)
z1 = 5.5 Infactible
Cota = ---
x2 2 x2 3 Terminal
P3 P4
3 = (1 , 2) 4 = (4/ 5 , 3)
z3 = 5 z4 = 27 / 5
Cota = 5 Cota = 5
Terminal x1 0 x1 1
P6 P5
6 = (0 , 5)
z6 = 5 Infactible
Cota = 5
Terminal Terminal
P1
174
P3
P4
P6
175
www.mundoindustrial.net
2. (10 puntos) Una compaa agrcola dispone de 1000 hectreas de terreno para el
cultivo de trigo y centeno. Por cada hectrea dedicada al cultivo de trigo la
compaa, con un coste de 150 unidades monetarias, obtiene 2 toneladas de este
cereal, y por hectrea dedicada al centeno, con un coste de 200 unidades
monetarias, obtiene 3 toneladas. La prxima temporada debe atender un pedido de
2500 toneladas de cada uno de estos dos cereales. Dado que no dispone de
suficientes hectreas para poder atender a este pedido mediante la cosecha de sus
terrenos, la compaa va a recurrir al mercado para comprar las cantidades de trigo
y centeno que precisa para cubrir esta demanda, con un coste de 200 unidades
monetarias por cada toneladas de trigo y 180 por cada toneladas de centeno.
a) (4 puntos) Modelizar, sin resolver, para decidir cuntas hectreas de trigo y de
centeno deben ser cultivadas y cuntas toneladas de estos cereales deben ser
adquiridas en el mercado, para minimizar los costes totales y maximizar las
hectreas de terreno cultivadas.
b) (6 puntos) La compaa decide flexibilizar sus objetivos. Desea que los costes
totales no superen 180000 unidades monetarias y que el terreno cultivado sea al
menos 800 hectreas. Modelizar el problema, sin resolver, teniendo en cuenta
estas metas y que se valora el doble la carencia de una hectrea de terreno
cultivada que el exceso de una unidad monetaria en el coste total.
Solucin:
a) Definimos las variables de decisin siguientes:
xT = hectreas dedicadas al trigo.
176
www.mundoindustrial.net
Min ( y1+ + 2 y2 )
2 xT + yT = 2500
3x + y = 2500
C C
xT + xC 1000
s.a 150 x + 200 x + 200 y + 180 y y + + y = 180000
T C T C 1 1
x + x y + y = 800
+
T C 2 2
xT 0, xC 0, yT 0, yC 0, y1+ 0, y1 0, y2+ 0, y2 0;
A B C D
T1 4 8 9 3
T2 9 1 6 4
T3 7 3 6 8
T4 6 5 7 --
177
www.mundoindustrial.net
E
T1 4
T2 9
T3 7
Solucin:
a) Aplicamos el Mtodo Hngaro a la siguiente tabla:
A B C D
T1 4 8 9 3 -3
T2 9 1 6 4 -1
T3 7 3 6 8 -3
T4 6 5 7 M -5
A B C D
T1 1 5 6 0
T2 8 0 5 3
T3 4 0 3 5
T4 1 0 2 M
-1 -2
Con M positivo suficientemente grande
178
www.mundoindustrial.net
A B C D
T1 0 5 4 0
T2 7 0 3 3 -1
T3 3 0 1 5 -1
T4 0 0 0 M
+1
Con M positivo suficientemente grande
A B C D
T1 0 6 4 0
T2 6 0 2 2
T3 2 0 0 4
T4 0 1 0 M
Asignacin ptima: T1 D, T2 B, T3 C, T4 D.
Mnimo nmero total medio de defectos es16.
b)
179
www.mundoindustrial.net
4.
a) (4 puntos) En la siguiente tabla se presentan el conjunto de actividades en las
que se encuentra dividido un proyecto junto con sus relaciones de precedencia.
180
www.mundoindustrial.net
8
2 4 3
1 2 3
1 3 5
5 4
Solucin:
a) El siguiente grafo representa a este proyecto:
C
3 10
A D K
4 6 8 9
E I J
1
H
B
2 5 7
F G
181
www.mundoindustrial.net
b)
1 8 9
2 4
1 2 9
1
3
3
0 5
1 3 12
0 5 6 5
4
12
i) CMT ( 3, 4 ) = P ( 3) = 5
FMT * ( 2,3) = Q ( 3) = 6
M ( 3,5 ) = Q ( 5 ) P ( 3) t ( 3,5 ) = 3
ii)
1) CMT ( 3, 4 ) = P ( 3) = max {3 + t ,5} = 5 t 2
1 8 6+t
2 4
1 2+t 6+t
1
3
3
0 3+t
1 3 9+t
0 5 3+t 5
4
9+t
182
www.mundoindustrial.net
en el que FMT * ( 3, 4 ) = Q ( 4 ) = 6 + t
Cuando t < 3 :
1 8 9
2 4
1 2+t 9 3
1
0 3+t
1 3 12
0 5 6 5
4
12
en el que FMT * ( 3, 4 ) = Q ( 4 ) = 9
183