Investigacin Operativa
Del texto gua Investigacin de operaciones de Frederick S. Hillier, novena edicin,
de los problemas propuestos en la pgina 423, resuelva los problemas 10.2-1,
10.2-3 y 10.3-7.
10.2-1 Considere la siguiente red en la que cada nmero junto a una trayectoria
representa la distancia real entre el par de nodos que conecta. El objetivo es
encontrar la ruta ms corta del origen al destino.
a) Cules son las etapas y los estados para la formulacin de programacin
dinmica de este problema?
De la figura se deduce que el viaje se puede realizar en tres etapas.
Estas etapas contienen estados, partiendo desde el estado O hasta finalizar
en el estado T, los cuales son:
Etapa 1: estados O y (A, B, C).
Etapa 2: estados (A, B, C) y (D, E).
Etapa 3: estados (D, E) y T.
b) Utilice programacin dinmica para resolver el problema, pero en lugar de
emplear las tablas usuales muestre el trabajo en una grfica (similar a la
figura 10.2). En particular, comience con la red dada, en la que se
proporcionan los valores de ( ) de cuatro de los nodos; despus
encuentre 2 () y 1 (). Dibuje una punta de flecha para indicar la
trayectoria ptima que debe tomarse al salir de estos ltimos dos nodos.
Por ltimo identifique la ruta ptima con las flechas desde el nodo O hasta
el nodo T.
De acuerdo a los datos dados calculo 1 () tanto para A como para C:
1 = : 1 (, ) = , + 2 () = 9 + 11 = 20.
1 = : 1 (, ) = , + 2 () = 7 + 13 = 20.
Ahora calculo 2 () tanto para D como para E:
2 = : 2 (, ) = , + 3 () = 7 + 6 = 13.
2 = : 2 (, ) = , + 3 () = 8 + 7 = 15.
Elijo D, pues es la trayectoria mnima. Ahora debo calcular 1 () para B,
teniendo presente la eleccin que realic:
1 = : 1 (, ) = , + 2 () = 6 + 13 = 19.
De acuerdo a este ltimo valor hallado, observo que la ruta ptima a seguir es:
, como se muestra en el grfico a continuacin.
1 2 3
() =
() =
() =
() = () =
() =
() =
c) Utilice programacin dinmica para resolver este problema; construya a
mano las tablas usuales para = 3, = 2 = 1.
()
D 6 T
E 7 T
=
(, ) = + ( )
()
D E
A 11 - 11 D
B 7+6=13 8 + 7= 15 13 D
C - 6 + 7 = 13 13 E
=
(, ) = + ( )
()
A B C
O 9+11=20 6+13=19 7+13=20 19 B
Ruta:
d) Utilice el algoritmo de la ruta ms corta que se present en la seccin 9.3
para resolver este problema. Compare este enfoque con el de los incisos b)
y c).
Nodos
Nodo no
resueltos n-simo
resuelto Distancia
conectados nodo Distancia ltima
n ms total
directamente a ms mnima conexin
cercano involucrada
nodos no cercano
conectado
resueltos
1 O B 6 B 6 OB
2 O C 7 C 7 OC
3 B D 6 + 7 = 13 D 13 BD
4 C E 7 + 6 = 13 E 13 CE
5 D T 13 + 6 =19 DT 19 DT
6 E T 13+7= 20
En el mtodo desarrollado en los incisos b) y c) se avanza hacia atrs, en este
caso avanzo hacia adelante. Ambos enfoques son interesantes y en ambos
casos llego al mismo resultado.
10.2-3 Considere la siguiente red de proyecto (como se describe en la seccin
9.8), donde el nmero sobre el nodo es el tiempo que se requiere para la actividad
correspondiente. Considere el problema de encontrar la trayectoria ms larga (el
mayor tiempo total) a travs de esta red desde el inicio hasta su trmino, puesto
que la trayectoria ms larga es la ruta crtica.
a) Cules son las etapas y los estados para formular la programacin
dinmica de este problema?
Etapa 1 Etapa 2 Etapa 3 Etapa 4 Etapa 5
Etapa1
Etapa 1: estados (Inicio) y (A, B).
Etapa 2: estados (A, B) y (C, D, E).
Etapa 3: estados (C, D, E) y (F, G, H, I).
Etapa 4: estados (F, G, H, I) y (J, K, L)
Etapa 4: estados (J, K, L) y (Terminacin)
b) Use programacin dinmica para resolver este problema, pero en lugar de
emplear las tablas usuales, muestre su trabajo en una grfica. En particular,
determine los valores de las distintas ( ) junto a los nodos
correspondientes y el arco ptimo que debe tomarse al salir de cada nodo
mediante una punta de flecha cerca del inicio del arco. Despus identifique
la trayectoria ptima (la trayectoria ms larga) que siguen estas puntas de
flecha desde el nodo inicio hasta el de trmino. Si existe ms de una
trayectoria ptima, identifquelas a todas.
3 () = 6
() =
4 () = 5
() =
() =
2 () = 10
() = () =
1 () = 15, 16 () =
2 () = 11
4 () = 7
1 () = 15
3 () = 9
2 () = 12
Se hallaron dos rutas crticas (con la trayectoria ms larga), estas son:
Ruta crtica 1:
Ruta crtica 2:
Duracin estimada del proyecto = 17 unidades de tiempo
c) Utilice programacin dinmica para resolver el problema con las tablas
usuales para = 4, = 3, = 2 = 1.
=4
(, ) = + ( )
()
J K L
F 5 - - 5 J
G - 4 - 4 K
H - 4 - 4 K
I - - 7 7 L
=3
(, ) = + ( )
()
F G H I
C 1+5=6 4+4=8 - - 8 G
D - - 4+6=10 9 10 H
E - - 4+6=10 9 10 H
=2
(, ) = + ( )
()
C D E
A 6+6=12 2+10=12 - 12 C, D
B - - 3+10=13 13 E
=1
(, ) = + ( )
()
A B
Inicio 12+5=17 13+3=16 17 A
Ruta crtica 1:
Ruta crtica 2:
Duracin estimada del proyecto = 17 unidades de tiempo
10.3-7 Una compaa est por introducir un nuevo producto a un mercado muy
competido y planea su estrategia de comercializacin. Se ha tomado la decisin
de introducir el producto en tres fases. La fase 1 incluye ofertas especiales de
introduccin a precio reducido para atraer a los compradores de primera vez. La
fase 2 es una campaa intensiva de comerciales y anuncios para persuadir a
estos compradores de primera vez a que continen comprando el producto a
precio normal. Se sabe que otra compaa introducir otro nuevo producto
competitivo ms o menos al terminar la fase 2. En consecuencia, la fase 3 incluye
una campaa de seguimiento y promocin para tratar de evitar que los clientes
regulares cambien a la competencia.
Se cuenta con presupuesto total de 4 millones de dlares para realizar esta
campaa. El problema consiste en determinar cmo asignar este dinero de la
manera ms eficaz a las tres fases. Sea m la proporcin de mercado inicial
(expresada como porcentaje) que se logra en la fase 1, 2 , la fraccin de este
mercado que se retiene en la fase 2 y 3 la fraccin restante del porcentaje de
mercado que se retiene en la fase 3. Con los datos de la siguiente tabla, aplique
programacin dinmica para determinar la asignacin de $4 millones para
maximizar el porcentaje final del mercado para el nuevo producto, es decir,
maximizar 2 3 .
a) Suponga que el dinero se debe gastar en cantidades enteras mltiplos de 1
milln de dlares en cada fase y que el mnimo permisible es 1 para la fase
1 y 0 para las fases 2 y 3. En la siguiente tabla se proporciona el efecto
estimado de los gastos en cada fase:
Este problema requiere tomar tres decisiones interrelacionadas, cunto asignar
a cada fase de la campaa de comercializacin para maximizar 2 3 ,
recordando que el mnimo permisible en la fase 1 es uno y cero para las fases
2 y 3.
Sean:
= (0, 1, 2, 3, 4) ()
= (, . .4)
As en la etapa 1, cuando todava quedan millones por asignar, 1 = 4, pero en
las siguientes etapas, es exactamente 4 menos el nmero de millones
asignados en etapas anteriores, de manera que las secuencias de estados
son:
1 = 4, 2 = 4 1 , 3 = 2 2
El problema consiste en hallar la trayectoria del estado inicial 4 (inicio de etapa
1) al estado final 0 ( despus de la etapa 3) que maximice las sumas de los
nmeros a lo largo de la ruta.
Sea ( ) el efecto sobre el porcentaje del mercado, si se asignan millones
de dlares de acuerdo a los datos de la tabla. Entonces el objetivo es elegir
1 , 2 3 para maximizar:
3
()
=1
0
( 1 ) sea la cantidad gastada en fase n.
(1 milln) Cantidad que an debe gastarse .
( ) ser: 1) La cuota inicial del mercado alcanzada en la fase 1 cuando se
gasta en la fase 1, o 2) La fraccin de esta cuota de mercado retenida en la
fase n cuando se gasta en la fase n (n = 2 o 3).
=
( )
=m
0 0,3 0
1 0,5 1
2 0,6 2
3 0,7 3
Ahora vamos hacia atrs ( n = 2). Se necesita determinar y para ello
necesitamos calcular y comparar 2 (2 , 2 ) para los distintos valores de 2 .
(
Frmula: ( , ) = ( ) + +1 )
( )
(
+1 ) = 3
Para el caso de 2 = 0
2 = 0 2 (0, 0) = 2 (0) + 3 (0 0) = 2 (0) + 3 (0) = 0,2 0,3 = 0,06
2 = 1
2 = 0 2 (1, 0) = 2 (0) + 3 (1 0) = 0, 2 0,5 = 0,1
2 = 1 2 (1, 1) = 2 (1) + 3 (1 1) = 0,4 0,3 = 0,12
2 = 2
2 = 0 2 (2, 0) = 2 (0) + 3 (2 0) = 0,2 0,6 = 0,12
2 = 1 2 (2, 1) = 2 (1) + 3 (2 1) = 0,4 + 0,5 = 0,20
2 = 2 2 (2, 2) = 2 (2) + 3 (2 2) = 0,5 0,3 = 0,15
2 = 3
2 =0 2 (3, 0) = 2 (0) + 3 (3 0) = 0,2 0,7 = 0,14
2 =1 2 (3, 1) = 2 (1) + 3 (3 1) = 0,4 0,6 = 0,24
2 =2 2 (3, 2) = 2 (2) + 3 (3 2) = 0,5 0,5 = 0,25
2 =3 2 (3, 3) = 2 (3) + 3 (3 3) = 0,6 0,3 = 0,18
Teniendo presente que el objetivo es la maximizacin, se llega a la siguiente tabla:
=
( , )
()
0 1 2 3
0 0,06 0,06 0
1 0,10 0,12 0,12 1
2 0,12 0,20 0,15 0,20 1
3 0,14 0,24 0,25 0,18 0,25 2
Para este caso, el nico estado a considerar es el inicial 1 = 4
1 = 4
1 =1 1 (4, 1) = 1 (1) + 2 (4 1) = 20 0,25 = 5
1 =2 1 (4, 2) = 1 (2) + 2 (4 2) = 30 0,20 = 6
1 =3 1 (4, 3) = 1 (3) + 2 (4 3) = 40 0,12 = 4,8
1 =4 1 (4, 4) = 1 (4) + 2 (4 4) = 50 0,06 = 3
=
( , )
( )
1 2 3 4
4 5 6 4,8 3 6 2
Solucin ptima:
Millones
Fase
asignados
2 30
1 1 0,4
2 1 0,5
Con ello se logra conservar el 6% del mercado (30x0,4x0,5)
b) Suponga que se puede gastar cualquier cantidad del presupuesto en cada
fase, y que el efecto estimado al gastar una cantidad (en unidades de
millones de dlares) en la fase ( = 1, 2, 3) es
= 101 12
2 = 0,40 + 0.102
3 = 0,60 + 0.073.
[Sugerencia: Despus de obtener en forma analtica las funciones 2 () y 3 (),
obtenga 1 de manera grfica.]
Fase 3
()
04 0,60 + 0.073.
Fase 2
2 (, 2 ) = (0,40 + 0.102 )(0,60 + 0.07( 2 ))
= 0,00722 + (0,007 + 0,032)2 + (0,24 + 0,028)
0 2
(,
2 2 )
= 0,0142 + 0,007 + 0,032
0,0142 + 0,007 + 0,032 = 0
0,007 + 0,032
2 =
0,014
16
= +
2 7
Por lo tanto si:
16
2+ 2 = porque 2 (, 2 ) es estrictamente creciente en
7
16
[0, 2 + ] y entonces es creciente en (0, ).
7
16 16
Si > 2 + entonces 2 = 2 + porque el nivel mximo es entonces sensible.
7 7
16
Por lo tanto 2 = [2 + , ].
7
Pero si
32 16
0 +
7 2 7
y
32
4 2 =
7
y
2 () = 0.06 + 0.24
Fase 1:
1 (4, 1 ) = (101 12 )(0,06(4 1 ) + 0.24)
= 0,0613 1,0812 + 4,81
1 (4, 1 )
= 0,1812 2,161 + 4,8
2,16 2,162 4(0,18)(4,8)
0,1812 2,161 + 4,8 = 0 1 =
2(0,18)
1 = 2,945 9,055
Entonces, 1 (4, 1 ) logra lo mximo si en el intervalo de (0, 4) 1 = 2,945 con
1 (4) = 6,302.
As $2945.000 se dedica a la fase 1, $1055.000 en fase 2 y nada en la fase 3; lo
cual lleva a ganar una parte del mercado del 6,302%.
1
1
2,945 9,055
Actividad de aprendizaje 2.2.
Del texto gua Investigacin de operaciones de Frederick S. Hillier, novena edicin,
de los problemas propuestos en la pgina 759, resuelva los problemas 17.3-1,
17.4-1, 17.5-1 y 17.5-8.
17.3-1 Identifique los clientes y los servidores del sistema de colas en cada una
de las siguientes situaciones.
a) La caja de salida de un supermercado.
b) Una estacin de bomberos.
c) La caseta de pago para cruzar un puente.
d) Un taller de reparacin de bicicletas.
e) Un muelle de carga y descarga.
f) Un grupo de mquinas semiautomticas asignadas a un operador.
g) El equipo de manejo de materiales de una fbrica.
h) Un taller de plomera.
i) Un taller que produce artculos sobre pedido.
j) Un grupo de secretarias.
Clientes Servidores
a) Clientes que esperan en la caja Cajeros/as
b) Incendios Unidades de lucha contra incendios
c) Carros Colectores de peaje
d) Bicicleta daada Reparador de bicicleta
e) Buques de carga o descarga Estibadores y equipo
f) Mquinas semiautomticas que Operador de mquinas
necesitan operador
g) Materiales a ser manipulados Equipos de manejo
h) Llamadas a los plomeros Plomeros
i) Pedidos personalizados Atencin personalizada
j) Solicitud de carta Secretarias
17.4-1 Suponga que un sistema de colas tiene dos servidores, distribucin de
tiempos entre llegadas exponencial con media de dos horas y distribucin de
tiempos de servicio exponencial con media de dos horas para cada servidor. Lo
que es ms, a las 12h00 del da acaba de llegar un cliente.
a) Cul es la probabilidad de que la siguiente llegada ocurra i) antes de la
1:00 p.m.. ii) entre la 1:00 y las 2:00 p.m., iii) despus de las 2:00 p.m.?
1
1 = 1
= 2 para > 0 y = {2 = 1
1 2
I. ( 1: 00 ) = 1 12 = 0,3935
II. ( 1: 00 2: 00 ) =
= (1 122 ) (1 12 ) = 0,6321 0,3935 = 0,2386
III. ( 2: 00 ) = 212 = 0,3679
b) Suponga que no llegan ms clientes antes de las 1:00 p.m. Ahora, cul es
la probabilidad de que la siguiente llegada tenga lugar entre la 1:00 y las
2:00 p.m.?
(. 1: 00 2: 00 ) = 1 12 = 0,3935
c) Cul es la probabilidad de que el nmero de llegadas entre la 1:00 y las
2:00 p.m. sea i) 0, ii) 1 y iii) 2 o ms?
1
I. Llegadas = 0 =2 =0
()0
( 1: 00 2: 00 ) =
0!
= (12)1 = 0,6065
1
II. Llegadas = 1 =2 =1
()1
( 1: 00 2: 00 ) =
1!
1 (12)1 0,6065
= = = 0,3033
2 2
1
III. Llegadas = 2 o ms =2 =1
1
( 2 1: 00 2: 00 ) = 1 12 12
2
3 12
=1 = 0.0902
2
d) Si ambos servidores estn ocupados a las 1:00 p.m., cul es la
probabilidad de que ningn cliente haya completado su servicio i) antes de
las 2:00p.m., ii) antes de la 1:10 p.m., iii) antes de la 1:01 p.m.?
I. ( 2: 00 ) = 11
= 1 = 0,3679
II. ( 1: 10 ) = 1(16) = 16
= 0,8465
III. ( 1: 01 ) = 1(160) = 160
= 0,9835
17.5-1 Considere el proceso de nacimiento y muerte con todas las
= 2( = 1, 2, . ), 0 = 3, 1 = 2, 2 = 1, = 0 para = 3, 4, .
a) Construya el diagrama de tasas.
b) Calcule 0 , 1 , 2 , 3 para = 4, 5,
0 3
1 = 0 = 0
1 2
1 0 23 3
2 = 0 = 0 = 0
1 2 22 2
2 1 0 123 3
3 = 0 = 0 = 0
1 2 3 222 4
2 1 0 0123
= 0 = = 0 0 = 0
1 2 3 2222 0
1
= 1 0 = ( )
=0 =0
3 3 3
0 + 1 + 2 + 3 = (1 + + + ) 0 = 1
2 2 4
19
( ) 0 = 1 =
4
Por lo tanto:
3 3 4 6
1 = 0 1 = =
2 2 19 19
3 3 4 6
2 = 0 2 = =
2 2 19 19
3 3 4 3
3 = 0 = =
4 4 19 19
c) Calcule , , .
= = 1 + 22 + 33
=0
6 6 3 6 12 9 27
= +2 +3 = + + = = 1,421
19 19 19 19 19 19 19
= ( ) = 2 + 23
=
6 3 6 6 12
= +2 = + = = 0,632
19 19 19 19 19
= =
= = 0 0 + 1 1 + 2 2
=0
4 6 6 30
= 3 +2 +1 =
19 19 19 19
12 12 6 = 1,579
= + +
19 19 19
27 30 27 9
= = = = 0,9
19 19 30 10
12 30 12 2
= = = = 0,4
19 19 30 5
17.5-8 Un supermercado pequeo tiene una sola caja con un cajero de tiempo
completo. Los clientes llegan a la caja de manera aleatoria (proceso de entradas
de Poisson) con tasa media de 30 por hora. Cuando slo hay un cliente en la caja,
el cajero lo atiende solo, con un tiempo de servicio esperado de 1.5 min., pero el
muchacho que ayuda tiene instrucciones fijas de que si hay ms de un cliente en
la caja ayude al cajero a empacar mercanca. Esta ayuda reduce el tiempo
esperado de servicio a 1 min. En ambos casos la distribucin de estos tiempos de
servicio es exponencial.
= 30 1 = 40 2 = 60
a) Construya el diagrama de tasas de este sistema.
1 = 30 2 = 30 3 = 30
1 = 40 2 = 60 3 = 60
b) Obtenga la distribucin de probabilidad de estado estable del nmero de
clientes en la caja.
1 1
1
0 = [1 + ] = [1 + ( ) ]
1 21 1 2
=1 =1
1
3 1
1 = (1 + )
= [1 + ( )] 2
1 1 5 1
2 =( )
1 2
30 1 2
= [1 + ( )] =
40 1 30 5
60 = 0,4
1
3 1
= [1 + ( )]
4 1
2
= 0 ( ) 3 1 1
1 21 = ( )( )
1 2
10
2 30 2
=
5 40(60)1
3 1
2 30 301 = 2( )
= ( )( ) 10 2
5 40 (60)1
3 1
= ( ) 1
2 3 1 1 5 2
= ( )( )
5 4 30
1 60 2
c) Obtenga L de este sistema. (Sugerencia: Consulte el desarrollo de L del
modelo M/M/1 al principio de la seccin 17.6.) Utilice esta informacin para
determinar Lq, W y W q.
3 1 1
3 1 =
= = [ ( ) ] 5 2 1 2
5 2 (1 2)
=0 =0
3 1 6
= ( ) =
5 2 5
=1
3 1 1 1
= ( )
5 2 2
=1
6 2 3
= (1 0 ) = (1 ) =
5 5 5
6
6 1
= = 5 = =
30 150 25
3
3 1
= = 5 = =
30 150 50
