Universidad de los Andes

Departamento de Ingenierı́a Industrial

Modelos Probabilı́sticos (IIND-2104)
2019-II
Base de Problemas Parcial 3

Base de Problemas Parcial 3

1. Andrés es un estudiante que vive bastante lejos de la universidad y por eso ha optado por hacer carpooling
por las mañanas. Tiene un gran grupo de amigos que les gustarı́a estar en el carro, el problema es que
solo tiene 3 puestos y no todos están en una vı́a adecuada respecto al resto. Además cada amigo le intento
ofrecer un aporte económico mayor al parqueadero y gasolina. Andrés quiere maximizar las ganancias de
este aporte, pero sabiendo que su desvı́o máximo en tiempo es de 30 minutos de la ruta que hace sin llevar a
nadie. La siguiente tabla dice los amigos que están interesados, el tiempo del desvı́o y el aporte que harı́an.

Amigo Aporte ($) Tiempo de desvı́o (minutos)

Andrea 2,500 3
Camilo 1,000 1
Ricardo 5,000 7
Fernando 4,500 5
Diana 1,500 4
Juliana 7,500 13
Daniela 2,500 3
Sebastián 3,000 8

Considerando las rutas posibles, las primeras personas que podrı́a recoger serian Camilo, Ricardo, Diana o
Juliana. En el caso de recoger a Camilo o Ricardo, puede recoger después a Daniela o Sebastián. Si recoge
a Diana puede recoger a Fernando o Sebastián. Si recoge a Juliana puede recoger a Fernando o Andrea.
Si recoge a Daniela puede recoger a Fernando, Sebastián o Andrea. Finalmente si Recoge a Fernando o
Sebastián puede recoger a cualquier otro de los 2 o a Andrea. Otras combinaciones no son posibles de
hacer. Diga cual es la mejor ruta que Andrés puede hacer maximizando sus ingresos por recoger a sus
amigos.
Primero hagamos el gráfico de las posibles opciones planteadas. Visto que todas cumplen la restricción
de tiempo, no se reducen las rutas posibles.

Figure 1: Diagrama Carpooling

1
 Sea fn (i) como la ganancia del pasajero i en el turno n. Consideremos el tercer paso:

f3 (Fernando) = 4, 500 f3 (Sebastián) = 3, 500

f3 (Andrea) = 2, 500 f3 (Nadie) = 0

∗
f3 (Fernando) = 4, 500

f2 (Daniela) = 2, 500 + f3 (Sebastián) = 3, 500 = 7, 000

f3 (Andrea) = 2, 500

(
f3 (Fernando) = 4, 500∗
f2 (Sebastián) = 3, 500 + = 8, 000
f3 (Andrea) = 2, 500
(
f3 (Sebastián) = 3, 500∗
f2 (Fernando) = 4, 500 + = 8, 000
f3 (Andrea) = 2, 500
f2 (Andrea) = 2, 500 + f3 (N adie) = 2, 500
(
f2 (Daniela) = 7, 000
f1 (Camilo) = 1, 000 + = 9, 000
f2 (Sebastián) = 8, 000∗
(
f2 (Daniela) = 7, 000
f1 (Ricardo) = 5, 000 + = 13, 000
f2 (Sebastián) = 8, 000∗
(
f2 (Fernando) = 8, 000∗
f1 (Diana) = 1, 500 + = 9, 500
f2 (Sebastián) = 8, 000∗
(
f2 (Fernando) = 8, 000∗
f1 (Juliana) = 5, 500 + = 13, 500
f2 (Andrea) = 2, 500

Por lo tanto la mejor ruta es recoger a Juliana, Fernando y Sebastián.

2. El Vapor, una página de internet que vende juegos para computador, saca una oferta semanal muy peculiar.
En esta oferta, la página vende un paquete de juegos, el cual se puede comprar a 90, 100 o 110 dólares.
Usted es libre de comprar el paquete a cualquiera de estos 3 precios, pero si paga más que el promedio
entonces se le obsequia un juego adicional. Si paga lo mismo o menos que el promedio no se le da nada
adicional. El promedio de lo que se ha pagado también es uno de estos tres valores, ası́ que si usted paga
100 y el promedio fue 90 entonces se le regalará el juego adicional. Al momento de comprar el paquete,
usted no sabe cuál va a ser el promedio y lo único que sabe es el promedio de la semana anterior. El
promedio de la semana va a depender del precio que usted paga y del promedio de la semana anterior.
Si paga lo mismo que el promedio de la semana anterior P entonces el promedio será justo mayor a P
con probabilidad de 12 y justo menor a este precio con 12 . Pero si paga más que el promedio de la semana
anterior P , entonces el promedio será justo mayor a P con probabilidad de 34 y justo menor a este precio
con 41 . Por ejemplo no se puede tener que el promedio de la semana sea 110 si la semana pasada el promedio
fue de 90, ni viceversa. Y como usted sabe cómo se comportó el promedio de la semana pasada, solo va a
pagar por el paquete un valor igual o superior a este promedio, para tener más posibilidades de conseguir
un regalo. Usted va a comprar 3 paquetes durante tres semanas y sabe que antes de comenzar a comprar el
promedio fue de 100 dólares. Si desea maximizar la cantidad de juegos adicionales regalados, solucione el
sistema utilizando programación dinámica, definiendo la variable de estado, espacio de estados, las etapas,
los conjuntos de decisiones y la función objetivo.
Se define la variable Xt = el promedio de venta del paquete de juegos de la semana t-1. En donde las
épocas son cada semana. Las decisones son comprar el paquete a 90, 100 o 110 dólares. Las ganancias
asociadas son 0 si se paga igual o menos que el promedio o 1 si se paga más que el promedio. Y las
probabilidades son las de tener un promedio en particular con respecto al precio pagado. El problema,
resolviendolo con programación dinámica es el siguiente:

f3 (110) = 21 (0) + 12 (1) = 21 (pagar110)

f3 (100) = max{ 12 (0) + 12 (1), 43 (0) + 14 (1)} = max{ 21 , 14 }(pagar100)

f3 (90) = max{0, 34 (0) + 14 (1), 1} = max{0, 14 , 1}(pagar110)

1
f2 (110) = 2 + 21 f3 (110) + 12 f3 (100) = 1(pagar110)

2
 f2 (100) = max{ 12 + 12 f3 (110) + 12 f3 (90), 14 + 34 f3 (110) + 14 f3 (90)} = max{ 45 , 78 }(pagar100)

f2 (90) = max{ 21 f3 (100) + 12 f3 (90), 41 + 34 f3 (100) + 41 f3 (90), 1 + 34 f3 (100) + 14 f3 (90)} =

max{ 43 , 78 , 13
8 }(pagar110)

f1 (100) = max{ 12 + 12 f2 (110) + 12 f2 (90), 41 + 43 f2 (110) + 14 f2 (90)} = max{ 58 45

32 , 32 }(pagar100)

Entonces la polı́tica óptima es pagar 100 si la semana pasada fue 100 el promedio, si no entonces pagar
110.
3. El valor de un instrumento financiero A1 se denomina PA1 y depende tanto del valor PA2 de un instrumento
financiero A2 , como de un precio fijo conocido como strike price (K). Especı́ficamente, se sabe que el valor
de un instrumento A1 está dado por: PA1 = max{0, K − PA2 }. Suponga que hoy es 1 de diciembre de 2014
y usted posee un instrumento A1 y el precio de A2 es 100 dólares. En las siguientes fechas: 01/12/2014
(hoy), 01/03/2015 y 01/06/2015 usted debe decidir si vender el instrumento financiero o sostenerlo por
los siguientes 3 meses. Se sabe que en caso de sostener el instrumento luego del 01/06/2015 éste deberá
ser vendido el 01/09/2015. En caso de venderlo usted obtendrá el valor del instrumento A1 , dependiendo
del valor del instrumento A2 y del strike price (K). Se sabe que el valor del instrumento A2 en intervalos
de 3 meses puede subir 2 dólares o bajar 2 dólares con igual probabilidad. Suponga que el strike price es
igual a 104 dólares.

(a) Si alguien está dispuesto a pagarle por el instrumento A1 lo equivalente a la ganancia máxima
esperada que podrı́a obtener al poseer dicho instrumento, ¿cuál serı́a el precio al que usted estarı́a
dispuesto a vender el instrumento A1 hoy? Para lo anterior, formule el problema descrito usando
Programación Dinámica.
Las épocas de decisión se definen como el principio de cada trimestre incluyendo el principio del
cuarto trimestre en el cual se debe vender necesariamente el instrumento A1 . En concreto se define
E = {1, 2, 3, 4}. La variable de estado Xt se puede definir como la diferencia K − A2 en el trimestre
t, con t ∈ E. Note que la variable de estado no es exactamente el precio del instrumento A1 , ya que
Xt puede ser negativo mientras que PA1 no. El espacio de estados de Xt para cada trimestre está
dado por:

S1 = {4}
S2 = {2, 6}
S3 = {0, 4, 8}
S4 = {−2, 2, 6, 10}
El espacio de las posibles decisiones que se pueden tomar está definido por: At (i) = {V, M } ∀ t ∈
E \ {4} i ∈ St donde V representa la decisión de vender y M representa la decisión de sostener el
instrumento. Para la época de decisión 4 A4 (i) = {V } ∀i ∈ S4 . Para las ganancias inmediatas, note
que si usted vende el instrumento A1 que posee, usted recibirá el precio actual de este instrumento.
Por otro lado, si usted decide mantenerlo, no recibirá nada en el periodo actual.

ct (i, V ) = max{0, i} ∀ t∈E i ∈ St

ct (i, M ) = 0 ∀ t ∈ E i ∈ St
Por último, las probabilidades de transición están definidas únicamente para la decisión de mantener
(M ) en cuyo caso se tiene que para cada época de decisión:

2 6


P1 (M ) = 4 0.5 0.5

0 4 8
 
2 0.5 0.5 0
P2 (M ) =
6 0 0.5 0.5

3
 −2 2 6 10
 
0 0.5 0.5 0 0
P3 (M ) = 4  0 0.5 0.5 0 
8 0 0 0.5 0.5
Una vez formulado el problema, podemos aplicar inducción hacia atrás para encontrar cuál serı́a la
ganancia máxima que ofrecerı́a el instrumento A1 y por tanto se podrı́a determinar el precio al cuál
se podrı́a vender este instrumento. Se tiene que:

f4 (−2) = 0
f4 (2) = 2
f4 (6) = 6
f4 (10) = 10
Para el resto de épocas en general se cumple que:
(
max{0, i} a=V
ft (i) = max
0 + 0.5ft+1 (i + 2) + 0.5ft+1 (i − 2) a = M
Para la época de decisión 3:
(
0 a=V
f3 (0) = max
0.5f4 (2) + 0.5f4 (−2) = 1 a = M ∗∗
(
4 a = V ∗∗
f3 (4) = max
0.5f4 (6) + 0.5f4 (2) = 4 a = M ∗∗
(
8 a = V ∗∗
f3 (8) = max
0.5f4 (10) + 0.5f4 (6) = 8 a = M ∗∗
Para la época de decisión 2:
(
2 a=V
f2 (2) = max
0.5f3 (4) + 0.5f3 (0) = 2.5 a = M ∗∗
(
6 a = V ∗∗
f2 (6) = max
0.5f3 (8) + 0.5f3 (4) = 6 a = M ∗∗
Para la época de decisión 1:
(
4 a=V
f1 (4) = max
0.5f2 (6) + 0.5f2 (2) = 4.25 a = M ∗∗
Por lo tanto, al precio al que usted estarı́a dispuesto a vender su instrumento A1 es $4.25.
(b) ¿Cuál es la polı́tica que maximiza la ganancia esperada que ofrece el instrumento A1 ?
La polı́tica óptima se denota como π ? = (d?1 , d?2 , d?3 ), donde d?t denota la regla de decisión óptima en
la época de decisión t. Recuerde que d?4 es vender, puesto que no hay otra alternativa. De acuerdo a
los resultados encontrados en el literal a), se tiene que:

n
d?1 (i) = Mantener i = 4
(
? Mantener i ∈ {2, 6}
d2 (i) =
Vender i=6
(
Mantener i ∈ {0, 4, 8}
d?3 (i) =
Vender i ∈ {4, 8}

Note que hay varias polı́ticas que son óptimas. Sin embargo, solo necesitamos una de estas. Según
esto, la decisión de sostener el instrumento nunca es subóptima, por lo tanto la polı́tica (M, M, M )
es óptima.

4
4. Cada año, Santa Claus debe producir en su fábrica del polo norte los regalos que entregará a los niños en
noche buena. Él no conoce con exactitud la cantidad de niños que escribirán cartas cada año para pedir
regalos, por lo que no sabe a ciencia cierta cuantos regalos deberı́a producir. Sin embargo, ha estimado
que la cantidad de niños que le pedirán regalos serán: 100 con probabilidad 1/3, 200 con probabilidad
1/6 y 300 en otro caso. Para Santa Claus es muy importante tomar la decisión de producir o no regalos
y asimismo decidir cuántos producir. No obstante, si Santa decide que la fábrica debe producir, esta solo
lo puede hacerlo en múltiplos de 100, es decir, puede producir 100, 200 o 300 regalos.

Los costos que debe asumir Santa Claus se pagan siempre en unidades de chocolate caliente. Ası́, si Santa
decide que debe producir, debe pagar un costo fijo de 400 chocolates calientes. Adicionalmente, debe pagar
2 chocolates calientes por cada regalo producido. Cuando Santa produce los regalos, él debe entregarlos
a los niños, pero si produce más regalos de los necesarios y necesita almacenar, debe asumir el costo de 2
chocolates calientes por cada regalo almacenado. Sin embargo, cuando Santa Claus no produce suficiente
como para llevar regalos a todos los niños que escribieron carta, debe dejar a cada niño 12 chocolates
calientes. Este año en la bodega del polo norte hay 100 regalos en inventario y se sabe que en la bodega
no se pueden almacenar más de 200 regalos de un año a otro.

Santa Claus quiere planear los siguientes 3 años (es decir, el último año para tomar decisiones es el año
3) de tal manera que minimice el valor esperado de chocolates calientes que debe pagar.

(a) (25 puntos) Plantee un modelo de programación dinámica estocástica. Defina todos los componentes
del mismo.
E: Conjunto de etapas (años)
E = {1, 2, 3}

St : Inventario de regalos en cada perı́odo de tiempo

S1 = {100}
S2 = {0, 100, 200}
S3 = {0, 100, 200}

At (i): Producción en el periodo t dado el inventario.

At (0) = {0, 100, 200, 300}
At (100) = {0, 100, 200}
At (200) = {0, 100}

Pt (a): Matriz de probabilidad pt (j|i, a)

(0) (100) (200)

 
(0) 1 0 0
Pt (0) = (100)  1 0 0 
(200) 2/3 1/3 0

(0) (100) (200)

 
(0) 1 0 0
Pt (100) = (100)  2/3 1/3 0 
(200) 1/2 1/6 1/3

(0) (100) (200)

 
(0) 2/3 1/3 0
Pt (200) =
(100) 1/2 1/6 1/3
(0) (100) (200)


Pt (300) = (0) 1/2 1/6 1/3

Los costos inmediatos están compuestos por los costos fijos y variables de producción, los costos
de inventario, y los costos de no atender a todas las cartas de los niños.

5
 ct (i, a): Costo inmediato de decidir a dado que se está en el estado i. En este caso el costo es
independiente del tiempo.

ct (0, 0) = 0 + 0 + 0 + ( 13 100niños + 61 200niños + 12 300niños) ∗ 12 chocolates

niño = 2600chocolates

ct (0, 100) = 400chocolates + 100regalos ∗ 2 chocolates 1 1

regalos + 0 + ( 6 ∗ 100niños + 2 200niños) ∗ 12
chocolates
niño =
2000chocolates

ct (0, 200) = 400chocolates + 200regalos ∗ 2 chocolates 1 chocolates

regalos + ( 3 ∗ 100regalos) ∗ 2 regalo + ( 12 ∗ 100niños) ∗
12 chocolates
niño = 1466.6chocolates

ct (0, 300) = 400chocolates+300regalos∗2 chocolates 1 1 chocolates

regalos +( 3 ∗200regalos+ 6 ∗100regalos)∗2 regalo +0 =
1166.6chocolates

ct (100, 0) = 0 + 0 + 0 + ( 16 ∗ 100niños + 1
2 ∗ 200niños) ∗ 12 chocolates
niño = 1400chocolates

ct (100, 100) = 400chocolates + 100regalos ∗ 2 chocolates 1 chocolates 1

regalos + ( 3 ∗ 100regalos) ∗ 2 regalo + ( 2 ∗ 100niños) ∗
chocolates
12 niño = 1266.6chocolates

ct (100, 200) = 400chocolates+200regalos∗2 chocolates 1 1 chocolates

regalos +( 3 ∗200regalos+ 6 ∗100regalos)∗2 regalo +0 =
966.6chocolates

ct (200, 0) = 0 + 0 + ( 31 ∗ 100regalos) ∗ 2 chocolates

regalo + ( 21 ∗ 100niños) ∗ chocolates
niño = 666.6chocolates

ct (200, 100) = 400chocolates+100regalos∗2 chocolates 1 1 chocolates

regalos +( 3 ∗200regalos+ 6 ∗100regalos)∗2 regalo +0 =
766.6chocolates

(b) (15 puntos) Solucione la siguiente programación dinámica en donde se busca minimizar los costos, en
donde se tienen tres épocas de decisión, y las siguiente información. Muestre claramente la polı́tica
óptima. Recuerde que enumeración exhaustiva no es programación dinámica.

(b) (c)
 
(b) 1 0
Pt (d1) =
(c) 3/4 1/4

(b) (c)
 
(b) 3/4 1/4
Pt (d2) =
(c) 2/4 1/2

(b) (c)
 
(b) 3/4 1/4
Pt (d3) =
(c) 2/4 1/2

ct (i, a): Costo inmediato de tomar una decisión, dado que se está en el estado i. En este caso
el costo es independiente del tiempo.

ct (b, d1) = 7
ct (b, d2) = 11
ct (b, d3) = 12
ct (c, d1) = 4
ct (c, d2) = 9
ct (c, d3) = 14

6
 Sea ft (i) el mı́nimo costo esperado de operación si en el tiempo t ∈ E el inventario es i ∈ St
n
min = ct (b, a) + E[f3 |b, a]
∀a∈A2 (b)

ct (b, d1) + f3 (a)

min = ct (b, d2) + 34 ∗ f3 (a) + 1
4 ∗ f3 (b)
ct (b, d3) + 24 ∗ f3 (a) + 1 1

∗ f3 (b) + ∗ f3 (c)

4 4


7 d1 ∗

f3 (b) = min 11 d2

12 d3


4 d1 ∗

f3 (c) = min 9 d2

14 d3


7 + f3 (b) = 14∗
 d1
f2 (b) = min 11 + 34 f3 (b) + 14 f3 (c) = 17.5 d2
12 + 34 f3 (b) + 14 f3 (c)) = 18.25 d3



3 1
4 + 4 f3 (b) + 4 f3 (c) = 10.25 d1 ∗

f2 (c) = min 9 + 12 f3 (b) + 12 f3 (c) = 14.5 d2
14 + 34 f3 (b) + 14 f3 (c) = 19.5 d3



7 + f2 (b) = 21
 d1 ∗
3 1
f1 (b) = min 11 + 4 f2 (b) + 4 f2 (c) = 24 d2
12 + 34 f2 (b) + 14 f2 (c)) = 25 d3



3 1
4 + 4 f2 (b) + 4 f2 (c) = 17.0625 d1 ∗

f1 (c) = min 9 + 2 f2 (b) + 12 f2 (c) = 21.125
1
d2
3 1

14 + 4 f2 (b) + 4 f2 (c) = 26.125 d3


Polı́tica óptima: Siempre d3

5. En un problema de programación dinámica estocástica se toman decisiones en t = 0, t = 1 y t = 2. El

espacio de estados es S = {x, y}, independiente del tiempo, y las posibles acciones a tomar en cada estado
son A(i) = {δ1 , δ2 }, para i ∈ S independiente del tiempo. Las ganancias inmediatas por cada estado en
cada tiempo para cada decisión se presentan en las siguientes tablas

Estado/Tiempo t=0 t=1 t=2

x 12 24 18
y 6 36 12

Table 1: Ganancias inmediatas para cada estado en cada tiempo si la decisión es δ1

Estado/Tiempo t=0 t=1 t=2

x 12 30 24
y 15 24 18

Table 2: Ganancias inmediatas para cada estado en cada tiempo si la decisión es δ2

Por otra parte se tiene que las probabilidades de transición no dependen del tiempo y que están dadas por

x y x y
   
x 1/2 1/2 x 1/3 2/3
P (δ1 ) = P (δ2 ) =
y 2/3 1/3 y 1/2 1/2

7
 Utilizando la anterior información y si se desean maximizar las ganancias en las que se incurren hasta el
periodo t = 2, determine cuál es la polı́tica óptima y cuál es la ganancia esperada de utilizar la polı́tica
óptima si en el tiempo t = 0 el estado es x. Como en t = 2 es el último tiempo en donde se toman
decisiones, f2 (x) = 24 (δ2 ) y f2 (y) = 18 (δ2 ). En t = 1 se tiene que
1 1
f1 (x) = max{24 + (f2 (x) + f2 (y)), 30 + (f2 (x) + 2f2 (y))}
2 3
= max{45, 50}
= 50 (δ2 )

y que
1 1
f1 (y) = max{36 + (2f2 (x) + f2 (y)), 24 + (f2 (x) + f2 (y))}
3 2
= max{58, 45}
= 58 (δ1 )

Por último en t = 0,
1 1
f0 (x) = max{12 + (f1 (x) + f1 (y)), 12 + (f1 (x) + 2f1 (y))}
2 3
= max{66, 202/3}
= 202/3 (δ2 )

Ası́ pues la ganancia máxima esperada durante los tres primeros periodos si el estado en el tiempo t = 0
es x es de 202/3. Y la polı́tica que se debe seguir para esto es: en el tiempo t = 0 tomar la decisión δ2 . En
el tiempo t = 1 si el estado es x se debe tomar la decisión δ2 ; si el estado es y se debe tomar la decisión
δ1 . Por último en t = 2 independiente del estado se debe tomar la decisión δ2 .
6. En el tennis, cuando el jugador A está al servicio, este jugador tiene dos oportunidades para servir. La bola
debe rebotar dentro de un cuadro especı́fico pintado en la cancha, y si lo hace, el oponente debe responder
(devolver la bola con su raqueta). Si la bola no cae dentro de este cuadro en la primera oportunidad, el
jugador usa su segunda chance para servir. Si en su segunda oportunidad no hace que la bola caiga en
el cuadro, el jugador pierde el punto. Los jugadores profesionales usualmente planean su estrategia de
servicio para maximzar la probabilidad de ganar el punto.

Stephanie Graffiti ha practicado dos tipos de servicio: servicio fuerte (H) y servicio suave (S). La proba-
bilidad de que su servicio fuerte caiga en el cuadro es PH = 0.6 y la probabilidad de que el servicio suave
caiga en ese mismo cuadro es PS = 0.9. Si el saque fuerte de Stephanie cae en el cuadro, la probabilidad
de que ella gane el punto actual es WH = 0.7 y si su servicio suave es correcto, con probabilidad WS = 0.5
ella gana el punto actual.

(a) ¿Cuál es la mejor estrategia que Stephanie puede poner en práctica en un punto (dos oportunidades
de servicio) si su objetivo es maximizar la probabilidad de ganar el punto actual? ¿Cuál es la prob-
abilidad máxima de ganar el punto actual? Resuelva el problema usando programación dinámica.
(Ayuda: Para aplicar inducción hacia atrás en este problema, solo es necesario definir explı́citamente
las etapas de decisión y el espacio de decisiones para cada etapa.)

Note que las etapas de decisión son cada oportunidad de saque, es decir T = {1, 2}. La definición del
estado es la información que Stephanie debe tener en cuenta para tomar decisiones. Sin embargo, el
problema no habla de de estado de un sistema como tal (por ejemplo, marcador del partido, cansancio
de Stephanie, entre otros) y por lo tanto no es necesario definir una variable de estado. El espacio
de decisiones es At = {H, S}, ∀t ∈ T donde H representa servir fuerte y S representa servir suave.
Estas dos decisiones son posibles en cualquiera de las dos oportunidades de saque.
A continuación aplicamos inducción hacia atrás para encontrar la estrategia de servicio óptima.
Empezamos por la etapa t = 2:

(
PH · WH = 0.42 a = H
f2 = max
PS · WS = 0.45 a = S ∗∗

Ahora, para la etapa t = 1 tenemos que:

8
 (
PH · WH + (1 − PH )f2 a = H
f1 = max
PS · WS + (1 − PS )f2 a=S
(
0.42 + 0.4 · 0.45 = 0.6 a = H ∗∗
f1 = max
0.45 + 0.1 · 0.45 = 0.495 a = S

La mejor estrategia que Stephanie puede aplicar es servir fuerte en la primera oportunidad. Si este
saque no cae en el cuadro designado, entonces también debe servir suave en la segunda oportunidad.
La probabilidad de ganar el punto con esta estrategia óptima es 60%.

(b) Resuelva de nuevo el problema con programación dinámica si PH = 0.25, PS = 0.8, WH = 0.6 y
WS = 0.45.
Aplicando de nuevo inducción hacia atrás obtenemos:

(
PH · WH = 0.15 a = H
f2 = max
PS · WS = 0.36 a = S ∗∗

(
PH · WH + (1 − PH )f2 a=H
f1 = max
PS · WS + (1 − PS )f2 a=S
(
0.15 + 0.75 · 0.36 = 0.42 a=H
f1 = max
0.36 + 0.2 · 0.36 = 0.432 a = S ∗∗

Note que la estrategia óptima cambia para estos nuevos parámetros, ya que ahora Stephanie debe
servir suave en su primera oportunidad y si este saque no es exitoso, debe servir suave de nuevo en
su segunda oportunidad. La probabilidad de ganar el punto con esta estrategia se reduce bastante,
puesto que ahora es 43.2%.
7. Ha sido su sueño viajar a Latvia para sus vacaciones y ya tiene todo el paquete de hotel pagado pero aún
no ha comprado su tiquete. Como se sabe, una aerolı́nea sube los precios entre más cerca es el dı́a del
vuelo pero pueden que salgan descuentos en algún momento. Quedan cuatro semanas para comprar su
tiquete y cada martes usted va a decidir comprar el tiquete o no. Hoy el tiquete cuesta $100 dólares y
cada semana sube $50. Por otro lado, existe una probabilidad de 1/2 de que salga una promoción, donde
el tiquete vale $50, de lo contrario sale al precio de esa semana (Tenga en cuenta que hoy también puede
saler una promoción). Por otro lado usted sólo tiene $200 dólares, por lo que si el tiquete está más caro
que eso, su única opción es esperar que salga una promoción. Si no logra comprar el tiquete perderá los
$200 dólares que le costó el paquete de hotel.
(a) (15 puntos) Su deseo es tener la mayor cantidad de plata disponible para el viaje (lo que sobra
después de comprar el tiquete) y que si no viaja entonces tendrá como costo lo que pierde del hotel.
Entonces defina el problema como una programación dinámica, definiendo claramente los siguientes
componentes: Épocas, Variable, Estados, Decisiones, Costos/Ganancias Asociadas y Probabilidades.
• Épocas: Cada semana de compra. T = {1, 2, 3, 4}
• Xn = Estado de venta del tiquete en la semana n.
• Estados: Promoción o Precio Normal
• Decisiones: Comprar o no el tiquete
• Ganancias Inmediatas:

P romo N ormal
 
1 150 100
2 150 50 
Gan(Compra) =  
3 150 0 
4 150 −200
P romo N ormal
 
1 0 0
2 0 0 
Gan(N oCompra) =  
3 0 0 
4 −200 −200

9
 • Probabilidades: Si se compra el tiquete, no se pasarı́a al siguiente periodo, ası́ que la probabilidad
serı́a 0. Por otro lado la matriz de probabilidad serı́a:

P romo N ormal
 
P romo 1/2 1/2
P (N oCompra) =
N ormal 1/2 1/2
(b) (15 puntos) Encuentre la polı́tica óptima de decisión para este problema y ¿cuál es el valor esperado
de dinero disponible después de comprar el tiquete?
• Semana 4:

f4 (P romo) = max{Comprar, No Comprar}

= 150∗
= −200

f4 (N ormal) = max{Comprar, No Comprar}

= −200∗
= −200
• Semana 3:

f3 (P romo) = max{Comprar, No Comprar}

= 150∗
1 1
= f4 (P romo) + f4 (N ormal) = −25
2 2

f3 (N ormal) = max{Comprar, No Comprar}

= 0∗
1 1
= f4 (P romo) + f4 (N ormal) = −25
2 2
• Semana 2:

f2 (P romo) = max{Comprar, No Comprar}

= 150∗
1 1
= f3 (P romo) + f3 (N ormal) = 75
2 2

f2 (N ormal) = max{Comprar, No Comprar}

= 50
1 1
= f3 (P romo) + f3 (N ormal) = 75∗
2 2
• Semana 1:

f1 (P romo) = max{Comprar, No Comprar}

= 150∗
1 1
= f2 (P romo) + f2 (N ormal) = 112.5
2 2

f1 (N ormal) = max{Comprar, No Comprar}

= 100
1 1
= f2 (P romo) + f2 (N ormal) = 112.5∗
2 2

10
 Entonces como polı́tica, si sale una promoción debe comprar sin importar la semana y si no hay
promoción debe comprarla desde la semana 3. El valor esperado de dinero disponible después de
comprar el tiquete serı́a: 21 f1 (P romo) + 12 f1 (N oP romo) = $131.25.

(c) (10 puntos) Si el precio del paquete de hotel fuera menor, ¿qué pasarı́a con la polı́tica óptima? ¿Se
comprarı́a antes, después o seguirı́a igual? Justifique en 50 palabras o menos.
Cuando el valor del paquete hotelero sea menor a $150 entonces si no sale promoción en la semana
3, se esperará hasta la semana 4 para comprar el tiquete.

8. Ximena se encuentra jugando la final de un torneo de triqui (tres en lı́nea) contra Oscar, uno de los mejores
jugadores de Colombia. El juego consiste en dos jugadores: O y X, que marcan los espacios de un tablero
de 3 × 3 alternadamente. Un jugador gana si consigue tener una lı́nea de tres de sus sı́mbolos: la lı́nea
puede ser horizontal, vertical o diagonal. Se sabe que Oscar inició el juego (jugando con O) y que en este
momento se tiene el siguiente tablero:

Es el turno de Ximena. Ella sabe que la estrategia de Oscar es marcar aleatoriamente cualquiera de las
casillas que hay disponibles.
(a) (20 puntos) Usando programación dinámica encuentre la mejor estrategia de juego para Ximena de
tal forma que se maximice su probabilidad de ganar el juego de triqui y mencione cuál serı́a dicha
probabilidad. Para esto defina claramente las épocas de decisión y la variable de estado. Sea claro
en el procedimiento, de lo contrario su puntaje se verá afectado. Ayuda 1: se recomienda dibujar
el grafo asociado al problema. Ayuda 2: puede asumir una ganancia de 1 para la situación en la
que Ximena gana el juego y 0 de lo contrario.

Se definen las épocas de decisión como E = {1, 2, 3}. A Ximena le quedan dos posibles decisiones
en dicho juego, las cuales se tomarán en las épocas 1 y 2. La época 3 es terminal y en ella no se
toma ninguna decisión. Se define ahora Xi,t como el tipo de marca en la casilla i antes de realizar la
jugada t, i ∈ {A, B, C, D}, t ∈ E. La variable de estado se define como Yt = (XA,t , XB,t , XC,t , XD,t ).
El grafo asociado al problema se muestra en la figura 2, en el cual un borde rojo significa que se tiene
una ganancia de 0 mientras que uno azul una ganancia de 1:

Sea ft (s) la máxima probabilidad de que Ximena gane el juego dado que antes de la jugada t el
estado del tablero es s. Se inicia la recursión por el último periodo donde se toma una decisión, es
decir t = 2.

(
0 C∗
f2 (X, O, −, −) = max
0 D∗
(
0 B∗
f2 (X, −, O, −) = max
0 D∗
f2 (X, −, −, O) = 0 N ada∗

f2 (O, X, −, −) = 0 N ada ∗
(
0 A∗
f2 (−, X, O, −) = max
0 D∗
f2 (−, X, −, O) = 0 N ada∗

11
 Figure 2: Relaciones entre estados

f2 (O, −, X, −) = 0 N ada ∗
(
0 A
f2 (−, O, X, −) = max
1 D∗
f2 (−, −, X, O) = 0 N ada∗

f2 (O, −, −, X) 0 N ada ∗
=
(
0 A
f2 (−, O, −, X) = max
1 C∗
(
0 A∗
f2 (−, −, O, X) = max
0 B∗

1 1 1

 f2 (X, O, −, −) + f2 (X, −, O, −) + f2 (X, −, −, O) = 0
 A

 3 3 3
1
 f2 (O, X, −, −) + 1 f2 (−, X, O, −) + 1 f2 (−, X, −, O) = 0

B

f1 (−, −, −, −) = max 31 3
1
3
1 1

 f2 (O, −, X, −) + f2 (−, O, X, −) + f2 (−, −, X, O) = C∗
3 3 3 3


 1 f2 (O, −, −, X) + 1 f2 (−, O, −, X) + 1 f2 (−, −, O, X) = 1


D∗

3 3 3 3
De esta manera se obtiene que la probabilidad de que Ximena gane el juego es de 1/3 siguiendo una
de las dos polı́ticas óptimas:

• La primera polı́tica que puede seguir es primero seleccionar la celda C. En el caso en que el
Oscar juegue en la celda B, Ximena deberá jugar en la celda D. Si Oscar juega en la celda A o
D Ximena no puede tomar ninguna acción pues Oscar habrá ganado.
• La segunda polı́tica que puede seguir es primero seleccionar la celda D. En el caso en que el
Oscar juegue en la celda B, Ximena deberá jugar en la celda C. Si Oscar juega en la celda A
Ximena no puede tomar ninguna acción pues Oscar habrá ganado. Finalmente si Oscar juega
en la celda C Ximena puede jugar en cualquier celda (no ganará en ningún caso).

12
 (b) (5 puntos) En el caso de encontrar óptimos alternos, ¿Cuál de las polı́ticas escogerı́a si además quiere
reducir la probabilidad de que Oscar gane? Si no encontró óptimos alternos encuentre la probabilidad
de que Oscar gane el juego.

Se escogerı́a la segunda polı́tica pues jugando primero en D se reduce la probabilidad de que Oscar
gane en la siguiente jugada, ya que solamente si selecciona la casilla A gana. Por otra parte, si
Ximena juega en la casilla B Oscar podrá ganar si selecciona cualquiera de dos casillas: A o D.

(c) (5 puntos) ¿Cómo cambiarı́a su espacio de estados en tal caso que el juego acabara de empezar y
Oscar no ha realizado ninguna jugada? ¿Cuántas decisiones deberı́a hacer Ximena en dicho caso?
Escriba su respuesta en menos de 50 palabras.

El espacio de estados crecerı́a para cada periodo debido a que se tendrı́a un mayor número de
combinaciones de juego posibles. Ximena tendrı́a que tomar 4 decisiones en total.
9. (30 puntos). Juan está planeando un viaje por Europa que durará 4 semanas. Cada semana tiene decidido
visitar un paı́s y si le gusta mucho, puede escoger visitar este paı́s una vez más. Por otro lado Juan tiene
un presupuesto de 5000 Euros para todo el viaje y cada paı́s le ofrece una cierta felicidad al visitarlo. En
la siguiente tabla podrá observar cuanto le cuesta a Juan visitar cada paı́s y la felicidad que le da visitarlo:

Table 3: Tabla Felicidad y Costos

Paı́s Costo Felicidad
Croacia 2000 4
Islandia 3000 10
República Checa 1000 5
Estonia 500 3

¿Si Juan desea maximizar su felicidad, cuales paı́ses debe visitar? Recuerde que Juan puede visitar de
una vez un paı́s y que debe visitar al menos un paı́s cada semana (no puede quedarse una semana sin
visitar algún paı́s). Resuelva este problema utilizando programación dinámica, si se utiliza enumeración
exhaustiva, la nota será de cero.
Se define las etapas de decisión como el paı́s a visitar, entonces E = {C, I, R, E}, donde la decisión es
cuantas veces va a visitar este paı́s, teniendo en cuenta que máximo puede ir a un paı́s 2 veces. Pero se
tienen dos restricciones, que vamos a tomar como los estados del problema, plata disponible y semanas
desocupadas. Finalmente las ganancias asociadas por tomar una decisión es la felicidad asociada a visitar
un paı́s. Hay que tener en cuenta que en ningún momento se puede quedar sin plata y con semanas
disponibles y que en la época Estonia, no puede quedar con más de 2 semanas disponibles. Ası́ que
podemos ver la siguiente red:

1000, 2 1000, 1

1000, 2 2000, 3 1000, 2

5000, 4 3000, 3 3000, 3 2000, 2

5000, 4 5000, 4 3000, 2

Republica
Croacia Islandia Estonia
Checa

Figure 3: Red de Programación Dinámica Viaje por Europa

13
 Ası́ que arranquemos solucionando con programación dinámica el problema:
Estonia:

fE (1000, 1) = (1) 3
fE (1000, 2) = (2) 6
fE (2000, 2) = (2) 6
fE (3000, 2) = (2) 6

República Checa:

fR (1000, 2) = (0) 0 + fE (1000, 2) = 6

fR (2000, 3) = (1) 5 + fE (1000, 2) = 11
(
(1) 5 + fE (2000, 2) = 11
fR (3000, 3) = max
(2) 10 + fE (1000, 1) = 13∗
fR (5000, 4) = (2) 10 + fE (3000, 2) = 16

Islandia:

fI (1000, 2) = (0) 0 + fR (1000, 2) = 6

fI (3000, 3) = (0) 0 + fE (3000, 3) = 13
(
(0) 0 + fE (5000, 4) = 16
fI (5000, 4) = max
(1) 10 + fE (2000, 3) = 21∗

Croacia:


(0) 0 + fI (5000, 4) = 21∗

fC (5000, 4) = max (1) 4 + fI (3000, 3) = 17

(2) 8 + fI (1000, 3) = 14


Ası́ que Juan debe ir a Islandia 1 semana, a República Checa 1 semana y a Estonia 2 semanas.

10. (30 puntos) Usted y sus amigos han decidido montar un negocio de perros calientes en un parque de
diversiones dentro de Bogotá. Según lo planeado, el negocio se abrirá el próximo mes de Enero. Se sabe
con certeza que en Enero llegan 6 clientes por hora a comprar un perro, mientras que en Febrero, Marzo
y Abril serán de 8, 18 y 21 respectivamente. Usted sabe que su empleado puede preparar y vender los
perros calientes a una tasa de 10 perros por hora. Se asume que la capacidad de la fila es infinita, por
lo que usted debe planear la cantidad de empleados que trabajarán en cada mes de tal forma que la cola
nunca crezca indefinidamente. Suponga que todos los empleados tienen la misma tasa de servicio. Tenga
en cuenta que en cada mes puede contratar máximo un nuevo empleado y que máximo puede haber 3
empleados. El costo de contratar un empleado adicional es de $100 y el salario de cada empleado es de
$200 mensuales. Por otra parte, dado que el parque desea que los clientes esperen menos en cola, usted
obtendrá una bonificación de $2000(1 - ui ), donde ui es la utilización promedio de sus empleados en el
mes i. Suponga que para el mes de Enero usted cuenta con un único empleado y que durante este mes
usted no puede contratar otro empleado.

Si su objetivo es maximizar las utilidades (ganancias-costos) hasta el mes de Abril, encuentre la polı́tica
óptima de contratación y los costos esperados de utilizar dicha polı́tica utilizando programación dinámica.
Defina claramente las épocas de decisión, la variable de estado, el espacio de estados, los conjuntos
de posibles acciones y los costos o ganancias inmediatas. Recuerde que enumeración exhaustiva no es
programación dinámica. Ayuda: Una vez contratado un empleado, este no se puede despedir.

14
En primer lugar se deben definir las etapas, que corresponden a los 4 meses que son el horizonte de tiempo
sobre el cuál se quiere esyablecer la polı́tica óptima:

E = {Enero (E), Febrero (F), Marzo (M), Abril (A)}

Luego la variable de estado y los espacios de estado.

Xt = Número de empleados al finalizar el mes t-1

Sx = {1, 2, 3}
SE = {1}
SF = {1}
SM = {1, 2}
SA = {2, 3}
Finalmente sabemos que en cada mes solo puede contratar a un empleado, por lo tanto la decisión en
cada época será de Contratar o no. Sin embargo existen ciertas restricciones. En Enero se dispone de un
empleado y durante este mes no se puede contratar más. Además se debe tener la cantidad de empleados
necesaria para que la utilización siempre sea menor a 1.

Ai = {Contratar (C), No contratar (N)}

AE (1) = {No contratar (N)

AF (1) = {Contratar (C), No contratar (N)
AM (1) = {Contratar (C)
AM (2) = {Contratar (C), No contratar (N)
AA (2) = {Contratar (C)
AE (3) = {No contratar (N)

Las ganancias inmediatas serı́anrt (s, A):

6
rE (1, N ) = 2000 ∗ (1 − ) − 200 = 600
10
8
rF (1, N ) = 2000 ∗ (1 − ) − 200 = 200
10
8
rF (1, C) = 2000 ∗ (1 − ) − 400 − 100 = 700
20
18
rM (1, C) = 2000 ∗ (1 − ) − 400 − 100 = −300
20
18
rM (2, C) = 2000 ∗ (1 − ) − 600 − 100 = 100
30
18
rM (2, N ) = 2000 ∗ (1 − ) − 400 = −200
20
21
rA (2, C) = 2000 ∗ (1 − ) − 600 − 100 = −100
30
21
rA (3, N ) = 2000 ∗ (1 − ) − 600 = 0
30
Ahora podemos plantear la función de ingresos empezando de atrás para adelante:
21
fA (3) = 2000 ∗ (1 − ) − 600 = 0 N*
30
21
fA (2) = 2000 ∗ (1 − ) − 600 − 100 = −100 C*
30

15
 Note que para Abril los posibles estados de la variable Xt son 2 y 3, y que en cualquier caso debe terminar
con 3 empleados para cumplir estabilidad. Ahora para Marzo:
(
18
2000 ∗ (1 − 20 ) − 400 + fA (2) = −300 N
fM (2) = max 18
2000 ∗ (1 − 30 ) − 600 − 100 + fA (3) = 100 C*

18
fM (1) = 2000 ∗ (1 − ) − 400 − 100 + fA (2) = −400 C*
20
Para Febrero sabemos que la variable de estado solo puede tomar el valor de 1, ya que al final de Enero
se va a tener 1 solo empleado:
(
8
2000 ∗ (1 − 10 ) − 200 + fM (1) = −200 N
fF (1) = max 8
2000 ∗ (1 − 20 ) − 400 − 100 + fM (2) = 800 C*

6
fE (1) = 2000 ∗ (1 − ) − 200 + fF (1) = 1400 N*
10
La polı́tica óptima para el puesto de perros calientes es contratar un empleado en Febrero y otro en
Marzo. En Abril como ya tiene el máximo número de empleados entonces no puede contratar. Las
ganancias totales serı́an de $ 1400 para los 4 meses.
11. Isabel y Pablo son dos amigos que les encantan las actividades extracurriculares de fin de semana. Cada
viernes después de clases deciden el plan que realizarán en esa noche dependiendo de su presupuesto.
Pueden salir de rumba, lo cual tiene un costo de $40 para cada uno. Por otra parte, tienen la opción de
ir a cine, con lo que incurren en un gasto de $20 cada uno. Por último, siempre existe la opción de ver
pelı́culas en casa, por lo que no gastarı́an nada durante esa noche. Los padres de cada uno de ellos les
dan $100 semanales como mesada, los cuales los reciben el lunes en la mañana. Puesto que Isabel y Pablo
son los mejores amigos, juntan su mesada, comparten sus gastos de la semana y van a la misma actividad
juntos. De lunes a viernes (antes de decidir su plan) gastarán todo el dinero que tienen disponible con
probabilidad de 1/3, gastarán la mitad de su dinero con probabilidad 1/3 ó no gastarán nada con la
probabilidad restante. Suponga que al final de cada plan terminan de gastar el dinero que les sobra en
comida, por lo que cada semana gastarán todo el dinero que les dan sus papás (nunca ahorran). Por otra
parte, tenga en cuenta que si salen de rumba un viernes, con probabilidad de 1/2 el padre de Isabel se
dará cuenta que ella tiene resaca. En dicho caso, no le dará mesada el siguiente lunes, pues no quiere que
su hija malgaste su dinero. Finalmente, ellos consideran que ir de rumba se traduce en un beneficio de 10
unidades, ir a cine un beneficio de 7 unidades y ver pelı́culas en casa un beneficio de 5 unidades. Asuma
que en ningún momento los amigos podrán endeudarse.
(a) (15 puntos) Defina los componentes de un modelo MDP (épocas, espacio de estados, decisiones,
ganancias inmediatas y matrices de probabilidades de transición) que le permita maximizar el ben-
eficio de Isabel y Pablo en el largo plazo.
• Épocas: cada viernes en la noche. E = {0, 1, 2, ...}
• Estado: Sea Yt el presupuesto justo antes de decidir la actividad a realizar el viernes t.

S = {200, 100, 50, 0}

• Decisiones: Las posibles decisiones dependen del estado. R corresponde a ”Rumba”, C corre-
sponde a ”Cine” y P corresponde a ”Pelı́cula en casa”.

A(0) = {P }

A(50) = {P, C}
A(100) = A(200) = {P, C, R}
• Ganancias inmediatas: En este caso las ganancias únicamente dependen de la decisión tomada.

r(P ) = 5

r(C) = 7
r(R) = 10

16
 • Matrices de transición: Las matrices varı́an según la decisión tomada. Sea pr el presupuesto
para salir un viernes cualquiera.

En el caso en que la decisión tomada sea quedarse en casa o ir a cine se tiene un presupuesto para
la siguiente semana de $200. Gastarán 200, 100 o 0 con igual probabilidad, independientemente
del presupuesto de la semana anterior. De esta manera se construyen las matrices asociadas a
las decisiones P y C.

200 100 50 0
 
200 1/3 1/3 0 1/3
100 
 1/3 1/3 0 1/3 
P (P ) = 
50  1/3 1/3 0 1/3 
0 1/3 1/3 0 1/3
200 100 50 0
 
200 1/3 1/3 0 1/3
P (C) = 100  1/3 1/3 0 1/3 
50 1/3 1/3 0 1/3
Finalmente para construir la matriz asociada a la decisión de rumba, se debe tener en cuenta
que con probabilidad de 1/2 se tendrán $100 para los gastos de toda la semana y con el resto de
probabilidad se tendrán los $200 completos.

200 100 50 0
 
200 1/6 1/3 1/6 1/3
P (R) =
100 1/6 1/3 1/6 1/3
Por ejemplo, para tener $50 disponibles para salir la siguiente semana es la probabilidad de que
no le den dinero a Isabel (1/2) multiplicado por la probabilidad de que los amigos se gasten la
mitad del dinero de la semana antes del viernes en la noche (1/3).

(b) (10 puntos) Defina el programa lineal asociado al modelo definido en el numeral anterior. Utilice un
factor de descuento β = 0.9.
Debido a que se quiere maximizar el beneficio el programa lineal asociado es de minimización.

min z = V200 + V100 + V50 + V0

s.a.
 
1 1 1
V200 ≥ 5 + 0.9 V200 + V100 + V0 → (P)
3 3 3
 
1 1 1
V200 ≥ 7 + 0.9 V200 + V100 + V0 → (C)
3 3 3
 
1 1 1 1
V200 ≥ 10 + 0.9 V200 + V100 + V50 + + V0 → (R)
6 3 6 3
 
1 1 1
V100 ≥ 5 + 0.9 V200 + V100 + V0 → (P)
3 3 3
 
1 1 1
V100 ≥ 7 + 0.9 V200 + V100 + V0 → (C)
3 3 3
 
1 1 1 1
V100 ≥ 10 + 0.9 V200 + V100 + V50 + + V0 → (R)
6 3 6 3
 
1 1 1
V50 ≥ 5 + 0.9 V200 + V100 + V0 → (P)
3 3 3
 
1 1 1
V50 ≥ 7 + 0.9 V200 + V100 + V0 → (C)
3 3 3
 
1 1 1
V0 ≥ 5 + 0.9 V200 + V100 + V0 → (P)
3 3 3

17
 (c) (5 puntos) Suponga que hoy es viernes e Isabel y Pablo cuentan juntos con $100 para las actividades
de la noche. ¿Cuál es la diferencia en el largo plazo del beneficio que los amigos obtienen si en lugar
de tener $100 tengan $200 para gastar hoy en la noche?

Debido a que los estados 100 y 200 son iguales en cuanto a probabilidades y posibles decisiones (y
por lo tanto tienen el mismo lado derecho en las restricciones en el LP), V200 = V100 . Lo que significa
que no hay ninguna diferencia en el largo plazo, V200 − V100 = 0.

12. El ministro de hacienda de cierta nación ubicada en una isla del oceano Índico revisa al comienzo de
cada año la percepción que tienen los ciudadanos de su gestión. Esta percepción se clasifica en mala
(M), promedio (P), o buena (B). Dependiendo de lo que observa el puede decidir si hace una reforma trib-
utaria ese año (R), si pasa un par de decretos para aumentar algunos impuestos (D) o si no hace nada (N).

La tabla que se muestra a continuación muestra los recaudos anuales promedio asociados a la percepción
del ministro y a la decisión que él toma. Por ejemplo, si al comienzo de un año los ciudadanos tienen
una percepción Promedio del ministro y él decide hacer una reforma tributaria, entonces se recaudan en
promedio 6 millones de dólares por cuestión de impuestos durante ese año.

Percepción (i)/acción (a) Reforma (R) Decretos (D) Nada (N)

Buena (B) 10 7 3
Promedio (P) 6 5 2
Mala (M) 3 2 1

Table 4: Recados anuales promedio (en millones de dólares) si al comienzo de un año cualquiera la percepción
de la gestión del ministro es i y él realiza la acción a

Naturalmente, la evolución de la percepción que tienen los ciudadanos del ministro depende de las deci-
siones que él toma. Con datos históricos se han logrado obtener las matrices que se presentan a contin-
uación. Estas matrices describen como cambia la percepción que los ciudadanos tienen del ministro año a
año. Por ejemplo si al comienzo de un año la percepción del ministro es Buena y el decide no hacer nada,
al comienzo del otro año su percepción es Promedio con probabilidad 1/6 o Buena con probabilidad 5/6.

M P B M P B M P B
     
M 1 0 0 M 3/4 1/4 0 M 1/2 1/2 0
P (R) = P  1/2 1/2 0  P (D) = P  1/3 1/3 1/3  P (N ) = P  1/5 2/5 2/5 
B 1/3 1/3 1/3 B 0 1/2 1/2 B 0 1/6 5/6

De acuerdo con la información presentada anteriormente, formule y resuelva un problema de decisión

markoviano (MDP) que le permita indicarle al ministro cuáles son las decisiones que debe tomar al
comienzo de cada año con el objetivo de maximizar los recaudos esperados descontados en el largo plazo.
Para esto
(a) Formule la situación anterior como un MDP. Defina claramente cada uno de los componentes del
modelo.
El espacio de estados es S = {M, P, B}. Para cualquier estado i el conjunto de posibles acciones es
A(i) = {R, D, N }. Las ganancias inmediatas del modelo son c(B, R) = 10, c(B, D) = 7, c(B, N ) = 3,
c(P, R) = 6, c(P, D) = 5, c(P, N ) = 2, c(M, R) = 3, c(M, D) = 2 y c(M, N ) = 1. Las matrices de
probabilidades de transición asociadas a cada acción son las matrices P (R), P (D) y P (N ) mostradas
en el enunciado para las acciones R, D y N respectivamente.

(b) A partir del modelo desarrollado en el numeral anterior, formule el programa lineal que le permite
obtener la polı́tica óptima. Suponga que la tasa de descuento anual es de 0.9. Como el problema de
decisión es de maximización, el problema lineal es de minimización. Teniendo en cuenta que la tasa
de descuento anual es de 0.9 el progama lineal que permite obtener la polı́tica óptima es

min VB + VP + VM

sujeto a las siguientes restricciones:

18
 • Estado B:
0.9
VB ≥ 10 + (VB + VP + VM )
3
0.9
VB ≥ 7 + (VB + VP )
2
0.9
VB ≥ 3 + (5VB + VP )
6
• Estado P :
0.9
VP ≥ 6 + (VP + VM )
2
0.9
VP ≥ 5 + (VB + VP + VM )
3
0.9
VP ≥ 2 + (2VB + 2VP + VM )
5
• Estado M :

VM ≥ 3 + 0.9VM
0.9
VM ≥ 2 + (VP + 3VM )
4
0.9
VM ≥ 1 + (VP + VM )
2
∗
(c) Suponiendo que los valores óptimos del programa lineal del numeral anterior son VM = 39.12,
∗ ∗
VP = 45.59 y VB = 50.59, obtenga la polı́tica óptima y los máximos recaudos esperados descontados
en el largo plazo. (Ayuda: (0.3)(39.12+45.59+50.59)=40.59 y además (0.45)(39.12+45.59)=38.12).

Al remplazar los valores óptimos en las ecuaciones queda que en el estado B la restricción que queda
de igualdad es la asociada a la decisión R, en el estado P es la de la decisión D y en el estado M es
la de la decisión N . Se concluye que
• Al comienzo de un año el ministro debe hacer una reforma tributaria si los ciudadanos tienen
una buena percepción de su gestión.
• Al comienzo de un año el ministro debe hacer pasar un par de decretos si los ciudadanos tienen
una percepción promedio de su gestión.
• Al comienzo de un año el ministro no debe hacer nada si los ciudadanos tienen una percepción
mala de su gestión.
Adicionalmente si en un año cualquiera los ciudadanos tienen una buena percepción de la gestión del
ministro y él sigue la polı́tica óptima, entonces se recaudaran en promedio 50.59 millones de dólares
en el largo plazo. Si la percepción que tienen de su gestión es promedio y él ministro sigue la polı́tica
óptima, entonces se recaudarán 45.59 millones de dólares en promedio en largo plazo. Por último, si
la percepción que tienen los ciudadanos de su gestión es mala y el ministro sigue la polı́tica óptima,
se esperan recaudar 39.12 millones de dólares en el largo plazo.

13. La mafia YaKazi ha estado envuelta en varios delitos últimamente, por lo que la Policı́a ha enviado a
uno de sus mejores detectives, Leo DeCabra, a infiltrarse en esta peligrosa organización. La misión de
Leo es lograr capturar a la mayor cantidad de mafiosos, por lo que cada vez que haya un crimen él in-
tentará capturar a uno de estos. (Asuma que cada crimen lo comete solo un mafioso a la vez.) La mafia
YaKazi se conoce por cometer los siguientes delitos atroces: posesión de alucinógenos (Leche Kleem),
tráfico de animales en vı́a de extinción (ositos de felpa) y prevaricato (robo de M&M estatales). De-
pendiendo del delito que se esté cometiendo en el momento, Leo tiene la opción de llamar refuerzos o
proceder a hacer la captura él solo. Cuando Leo llama refuerzos durante el delito i, la probabilidad de
capturar al criminal es δi . Por otro lado, cuando Leo hace la captura él solo, la probabilidad de éxito es αi .

A Leo le es asignado un tipo de delito en particular dependiendo de la gravedad del crimen inmediatamente
anterior. La gravedad se mide como la cantidad (entera) de gramos de Leche Kleem (ΩK ), ositos de felpa
(ΩO ) o M&M (ΩM ) que Leo logre recuperar, para cada tipo de delito, respectivamente. La distribución
de Ωi es Poisson con media σi . Se considera que un delito i es grave si Ωi es mayor a un nivel de referencia
φi . Si un delito es catalogado como grave, a Leo le será asignado el mismo delito para el próximo crimen
o de lo contrario le será asignado cualquiera de los otros delitos con igual probabilidad.

19
(a) Formule un Proceso de Decisión Markoviano (MDP) para determinar qué decisiones deberı́a tomar
Leo DeCabra para maximizar el número esperado mafiosos capturados. Debe especificar claramente:
etapas de decisión, variable y espacio de estados, espacio de decisiones, costos/ganancias inmediatas
esperadas y probabilidades de transición. Asuma que habrá un número indeterminado de crı́menes
y que cada crimen es independiente del anterior.

En primer lugar se deben identificar las etapas de decisión. Note que Leo DeCabra debe tomar una
decisión cada vez que hay un crimen que está investigando. Por lo tanto, E = {1, 2, 3, 4, ...} donde
t ∈ E representa el t-ésimo crimen que Leo está investigando.

Ahora identificamos los posibles estados para cada etapa. Recuerde que un estado es información del
sistema, la cual es relevante para tomar las decisiones. Del problema podemos deducir que Leo decide
qué hacer de acuerdo al tipo de crimen que está investigando (es decir, qué delito está investigando).
Por lo tanto defina:

Xt : Delito que Leo está investigando en el t-ésimo crimen

SX = {K, O, M }
donde K, O y M representan posesión de Leche Klim, tráfico de osos de felpa y robo de M&M,
respectivamente. Luego, procedemos a identificar las posibles decisiones. Las posibilidades que tiene
Leo son llamar refuerzos para hacer la captura o hacer la captura él solo. Es decir:

A(i) = {B, A} i ∈ SX

donde B corresponde a llamar refuerzos, y A corresponde a realizar la captura él solo. Ahora
identificamos las ganancias inmediatas esperadas. Note que las ganancias en este contexto representan
número de criminales o mafiosos capturados. Esto quiere decir que una probabilidad ω de capturar
a un mafioso, equivale a ω mafiosos capturados en promedio. Expresamos las ganancias inmediatas
esperadas en términos de las variables del problema.
(
δi i ∈ SX , a = B
c(i, a) =
αi i ∈ SX , a = A

Para completar la formulación del modelo solo necesitamos las probabilidades de transición p(j|i, a).
Estos valores nos dicen cuál es la probabilidad de que Leo sea asignado a un delito j para el siguiente
crimen dado que en el crimen actual, está investigando el delito i. Note que estas probabilidades no
dependen de la decisión tomada por Leo, sino de la gravedad del delito del crimen actual. Si el delito
es grave, Leo será asignado al mismo delito con probabilidad 1, y si el delito no es grave, Leo será
asignado a cualquiera de los otros dos delitos con probabilidad 1/2. La probabilidad de que el delito
i ∈ SX sea grave es:

Ωi : Número de elementos recuperados para el delito i

Ωi ∼ Poisson(σi )

P [Ωi > φi ] = 1 − P [Ωi ≤ φi ]

φi
X e−σi σ j i
P [Ωi > φi ] = 1 −
j=0
j!

Entonces tenemos que las probabilidades de transición están dadas por:

K O M
 
K P [ΩK > φi ] P [ΩK ≤ φi ]/2 P [ΩK ≤ φi ]/2
Pa=B = O  P [ΩO ≤ φi ]/2 P [ΩO > φi ] P [ΩO ≤ φi ]/2 
M P [ΩM ≤ φi ]/2 P [ΩM ≤ φi ]/2 P [ΩM > φi ]
Note que Pa=B = Pa=A ya que las transiciones no dependen de la decisión tomada sino de la gravedad
del delito.

20
 (b) Formule un programa lineal que le permita encontrar la polı́tica de decisión óptima. Escriba clara-
mente la función objetivo y las restricciones asociadas a su programa. Asuma que la condición mental
de Leo se va deteriorando a medida que presencia crı́menes y por lo tanto sus decisiones tienen un
β% de efectividad con relación al crimen inmediatamente anterior.

Como se quieren maximizar ganancias (número esperado de criminales anotados), la función objetivo
del programa lineal debe ser de minimización. Las restricciones están dadas por las Ecuaciones de
Bellman para cada estado y cada decisión. Ya que las probabilidades de transición no dependen de
las decisiones tomadas sino solo del estado inicial, por brevedad, definimos para cada i ∈ SX :
 
X P [Ni ≤ φi ] 
V̄i = P [Ni > φi ]Vi + Vj
2
j∈SX \{i}

El programa lineal es entonces:

min VK + VO + VM

s.a.
VK ≥ δi + β V̄K
VK ≥ αL + β V̄K
VO ≥ δO + β V̄O
VO ≥ αO + β V̄O
VM ≥ δM + β V̄M
VM ≥ αM + β V̄M

14. (40 puntos) En una empresa de manufactura, se tienen las máquinas L, P y H. La empresa contrató
a Hugo, Paco y Luis para operar las máquinas (un operario por máquina). Aunque todos los operarios
pueden operar todas las máquinas, Hugo está especializado en la máquina H, Paco en la P y Luis en la
L. Se sabe que la productividad de cada máquina aumenta a su valor máximo cuando es operada por el
especialista correspondiente. En cada turno de trabajo el gerente de producción decide cómo ordenará a
sus operarios y para eso tiene dos posibles acciones:

I En cada turno de trabajo, el gerente de producción escoge con la misma probabilidad a uno de los
tres operarios. El operario escogido permanece en la máquina que está operando y los otros dos son
intercambiados.
II En cada turno de trabajo, el gerente de producción asigna los operarios a las máquinas de manera
aleatoria, donde cualquier combinación tiene la misma probabilidad de ser escogida.

Se sabe que cuando la productividad de una máquina es la máxima, entonces la máquina genera unas
ganancias de 100 por turno, pero si la productividad de la máquina es inferior a la máxima, entonces sólo
genera unas ganancias de 50. Usted debe tener en cuenta que la decisión tomada por el gerente tiene efecto
al inicio del turno inmediatamente siguiente. Es decir, que si se está operando con la combinación A
al inicio de cierto turno y se cambió a la combinación B, se opera durante todo el turno actual con A y
al inicio del siguiente turno se empieza con B.

(a) (25 puntos) Defina este problema como un MDP en donde se escoge cómo debe organizar el gerente
a sus operarios para maximizar las ganancias. Asumiendo una tasa de descuento de 0.9, defina clara-
mente las épocas de decisión, la variable de estado, el espacio de estados, el espacio de decisiones, las
ganancias inmediatas y las matrices de probabilidades de transición a un paso

Se define la variable Xt : como el número de máquinas operadas por el especialista correspondiente

en el turno de trabajo t. Entonces el espacio de estados es S = {0, 1, 3}. Note que el estado 2 no
existe porque si 2 operarios están en la máquina correcta, el tercero también lo estará. Las decisiones
están relacionadas con cómo organizar a los operarios, método 1 (cambiar 2) o método 2 (asignación
aleatoria). Por lo tanto, el espacio de decisiones es A(i) = {1, 2}, ∀i ∈ S. De esta forma, la matriz
de probabilidades de transición para el método 1 serı́a:

21
 0 1 3
 
0 0 1 0
2 
1 
P(1) = 1  3 0

3 
 
3 0 1 0

Y para el método 2 serı́a:

0 1 3
1 1 1

0 3 2 6
1 1 1

P(2) = 1  3
 
2 6 
3 13 1 1
 
2 6

Las ganancias inmediatas dependen de cuántos operarios están asignados a su máquina de espe-
cialidad. Si tomamos que las ganancias se reciben al principio de cada turno (antes de realizar la
asignación de operarios), podemos calcular las ganancias inmediatas como c(i, a) = 100·i+50·(3−i),
∀a ∈ A(i).

(b) (5 puntos) Escoja un estado de su modelo de MDP y escriba la función de recursión (ecuación de
Bellman) que corresponde a ese estado.

La función de recursión de forma general está dada por:

  
 X 
Vλ∗ (i) = max c(i, a) + 0.9  p(j|i, a)Vλ∗ (j)
a∈A(i)  
j∈S

Para el estado 0 la ecuación de Bellman es:

(
∗ 150 + 0.9Vλ∗ (1) a=1
Vλ (0) = max
150 + 0.9 13 Vλ∗ (0) + 12 Vλ∗ (1) + 16 Vλ∗ (3)


a=2
Para el estado 1 la ecuación de Bellman es:
(
2 ∗
+ 13 Vλ∗ (3)


∗ 200 + 0.9 3 Vλ (0) a=1
Vλ (1) = max 1 ∗
+ 12 Vλ∗ (1) + 16 Vλ∗ (3)


200 + 0.9 3 Vλ (0) a=2
Para el estado 3 la ecuación de Bellman es:
(
300 + 0.9Vλ∗ (1) a=1
Vλ∗ (3) = max
300 + 0.9 13 Vλ∗ (0) + 12 Vλ∗ (1) + 16 Vλ∗ (3)


a=2
(c) (10 puntos) Escriba el programa lineal que le permite encontrar la polı́tica óptima de su modelo de
MDP.
Como se va a maximizar el MDP entonces tenemos que la función objetivo serı́a min V0 + V1 + V3 ,
sujeto a:

V0 ≥ 150 + 0.9(V1 )
 
1 1 1
V0 ≥ 150 + 0.9 V0 + V1 + V3
3 2 6
 
2 1
V1 ≥ 200 + 0.9 V0 + V3
3 3
 
1 1 1
V1 ≥ 200 + 0.9 V0 + V1 + V3
3 2 6
V3 ≥ 300 + 0.9V1
 
1 1 1
V3 ≥ 300 + 0.9 V0 + V1 + V3
3 2 6

22
15. Un grupo reconocido de Rock lanza álbumes cada 2 años. Estos álbumes pueden ser: soundtrack de
pelı́culas, recopilaciones de grandes éxitos o un lanzamiento con canciones nuevas. La disquera desea
generar los mayores ingresos posibles, pero sabe que dependiendo de álbum que lanza el grupo, los fans
se comportan de forma [Link]ı́, ellos se han dado cuenta que existen dos tipos de fans diferentes:
nuevos fans y fans antiguo, los cuales normalmente con probabilidad de 21 cada fan compra un álbum.
Pero si el grupo saca un soundtrack, la probabilidad que nuevos fans compren aumenta en un 50% y la
de viejos fans baja en un 50%. Si sacan un álbum de grandes éxitos, la probabilidad original ( 12 ) de los
nuevos fans se mantiene y de los viejos fans aumenta en un 50%. Finalmente si sacan un álbum con nuevas
canciones, la probabilidad original ( 12 ) de compra de nuevos fans baja un 50% y de viejos fans sube un
50%.
Por otro lado la disquera ha notado que si en un año el grupo lanza un álbum del mismo tema de hace 2
años (Soundtrack, recopilaciones, nuevas), la probabilidad original de compra baja a 14 para ambos tipos
de clientes y no se tienen en cuenta los efectos anteriores. La disquera le ha pedido a usted que haga un
estudio para encontrar cuál es la polı́tica de lanzamientos de álbumes que debe seguir el grupo de Rock.
Para esto le ha pedido que utilice 2 fans nuevos y 2 fans viejos para hacer el estudio y encuentre la polı́tica
que maximice el número de álbumes vendidos entre estas 4 personas.

(a) (20 puntos) Defina las épocas, la o las variables, el espacio de estados, las decisiones, las probabili-
dades y los costos o ganancias inmediatas para este problema.

Para este problema se definen las épocas cada dos años, que es cuando el grupo de Rock decide que
álbum lanzar. Para lograr tomar esta decisión se tiene que la variable es Xt = El disco que lanzó
hace 2 años.

Teniendo en cuenta la variable de decisión entonces el espacio de estados es S = {Soundtrack,

Recopilaciones, Nuevo}. Que al mismo tiempo se tiene que las decisiones son A = {Soundtrack,
Recopilaciones, Nuevo}. En este problema las probabilidades del enunciado no afectan la transición
entre cada época. Por lo que se tiene que para la decisión a en el estado i la p(a|i, a) = 1 y p(j|i, a) = 0
para j 6= a.

Las ganancias inmediatas c(i, a) en este caso representa el número de álbumes que se venden en cada
periodo en el estado i y tomando la decisión a. En este caso, las ganancias están representadas en la
siguiente matriz donde las filas representan los estados y las columnas las decisiones:

S R N
 
S 1 2.5 2
C(i, a) = R  2 1 2
N 2 2.5 1

(b) (10 puntos) Determine y formule con que metodologı́a solucionarı́a este problema. Debe ser lo más
explı́cito posible y según la metodologı́a escogida, mostrar la o las fórmulas que utilizarı́a para solu-
cionarlo.

Este problema es un MDP dondes se puede solucionar ya sea por Value Iteration, Policy Iteration
o Programación Lineal. Pero para los tres casos hay definir una tasa de descuento β entre 0 y 1
para que el problema tenga solución. Como ejemplo se tiene que se puede resolver por programación
linean donde la función objetivo es:

min VS + VR + VN
s.a.

23
 VS ≥ 1 + βVS (S)
VS ≥ 2.5 + βVR (R)
VS ≥ 2 + βVN (N )
VR ≥ 2 + βVS (S)
VR ≥ 1 + βVR (R)
VR ≥ 2 + βVN (N )
VN ≥ 2 + βVS (S)
VN ≥ 2.5 + βVR (R)
VN ≥ 1 + βVN (N )

16. Un taxista se mueve en tres localidades: A, B y C. Cuando el taxi va sin pasajero por las calles de la
localidad i, se queda en ella hasta recoger el próximo pasajero. Las personas que están en la calle llaman
al taxi y el taxista se detiene para recoger el pasajero. Dependiendo del destino del pasajero el taxista
decide si llevarlo o no. Si el taxista decide llevar al pasajero, lo lleva a su destino y si decide no llevarlo,
sigue deambulando por la misma localidad hasta que otro pasajero lo llame.

Si un taxista está deambulando por la localidad i, con probabilidad pij el próximo pasajero que lo llame
se dirige a la localidad j.

En la Tabla 1, se muestran estas probabilidades para todo i, j ∈ {A, B, C}. Adicionalmente, las ganacias
esperadas que recibe por viaje y las distancias promedio que el taxista recorre en un viaje de la localidad
i a la localidad j se resumen en las Tablas 2 y 3 respectivamente.

Origen/Destino A B C
A .1 .5 .4
B .3 .2 .5
C .2 .5 .3

Table 5: Probabilidades pij

Origen/Destino A B C
A $20 $30 $50
B $25 $10 $70
C $55 $90 $5

Table 6: Ganancias promedio gij generadas por un viaje que se origina en la localidad i con destino a la localidad
j

Origen/Destino A B C
A 1000 2000 5000
B 3600 800 6000
C 4000 8000 500

Table 7: Distancias promedio rij generadas por un viaje que se originan en la localidad i con destino a la
localidad j (metros)

Por otro lado, apenas el taxista deja un pasajero en la localidad i, o decide no llevar a una pesona que lo
llamo en la localidad i, recorre una distancia promedio de di metros hasta que otra persona lo llama. En
la Tabla 4, se presentan los valores de di .

Localidad A B C
di 500 300 200

Table 8: Valores de las distancias di (metros)

24
 1
Por último tenga en cuenta que por motivos de gasolina cada metro recorrido le cuesta $
200
(a) (28 puntos). Suponiendo que cada vez que el taxista sale a trabajar, trabaja una cantidad arbitrari-
amente grande de tiempo, modele el problema de decisión del taxista como un proceso de decisión
Markoviano (MDP). El objetivo es maximizar las ganancias esperadas descontadas en el largo plazo.
Se define cada t ∈ E como el t-ésimo pasajero que llama al taxista. Sea Xt =localidad en la que se
encuentra el taxista cuando se detiene a recoger el llamado del pasajero t, y Yt =destino al que se
dirige el pasajero t. Entonces

S = {(A, A), (A, B), (A, C), (B, A), (B, B), (B, C), (C, A), (C, B), (C, C)}.

Para cada (i, j) ∈ S, las decisiones que puede tomar el taxista es si decider llevar al pasajero o no.
Ası́ pues A(i, j) = {N, V }, donde N significa que no decide llevarlo y V que decide hacer el viaje.

Para calcular las ganancias inmediatas hay que tener en cuenta que si la decisión es llevar al pasajero,
las ganancias inmediatas son la resta de las ganancias promedio generadas por un viaje con los costos
generados por recorrer la diistancia del viaje. Si la decisión es no llevar al pasajero, se considera
solo el costo de recorrer la distancia promedio hasta recoger al próximo pasajero. Ası́ pues se tiene que:
1 1
c((i, j), V ) = gij − rij − dj .
200 200
donde gij es la ganancia promedio de hacer un viaje de i a j y rij es la distancia promedio de hacer
un viaje de i a j. Por otro lado, si la decisión es no llevar al pasajero,
1
c((i, j), N ) = − di .
200

Con esta información se obtienen en la siguiente tabla las ganancias inmediatas

Estado (A,A) (A,B) (A,C) (B,A) (B,B) (B,C) (C,A) (C,B) (C,C)
(N) -2.5 -2.5 -2.5 -1.5 -1.5 -1.5 -1 -1 -1
(V) 12.5 18.5 24 4.5 4.5 39 32.5 48.5 1.5

Table 9: Ganancias inmediatas en $ por estado y acción

Por último las probabilidades de transición dependen de la acción. Si el taxista decide no recoger un
pasajero en la localidad i, va a seguir en esta localidad y la probabilidad de transición a otro estado
depende del destino de la próxima persona que recoja. Por otro lado si decide llevar a su destino
al pasajero, con probabilidad 1 la próxima persona que recoja se va a encontrar en el destino del
pasajero, ası́ que las probabilidades de transición dependeran de la localidad a donde llegue. Ası́
pues se tienen las siguientes matrices de probabilidades de transición:

(A, A) (A, B) (A, C) (B, A) (B, B) (B, C) (C, A) (C, B) (C, C)

 
(A, A) 0.1 0.5 0.4 0 0 0 0 0 0
(A, B) 
 0.1 0.5 0.4 0 0 0 0 0 0  
(A, C) 
 0.1 0.5 0.4 0 0 0 0 0 0  
(B, A) 
 0 0 0 0.3 0.2 0.5 0 0 0  
P(N ) = (B, B) 
 0 0 0 0.3 0.2 0.5 0 0 0  
(B, C) 
 0 0 0 0.3 0.2 0.5 0 0 0  
(C, A) 
 0 0 0 0 0 0 0.2 0.5 0.3  
(C, B)  0 0 0 0 0 0 0.2 0.5 0.3 
(C, C) 0 0 0 0 0 0 0.2 0.5 0.3

25
 y

(A, A) (A, B) (A, C) (B, A) (B, B) (B, C) (C, A) (C, B) (C, C)

 
(A, A) 0.1 0.5 0.4 0 0 0 0 0 0
(A, B) 
 0 0 0 0.3 0.2 0.5 0 0 0  
(A, C) 
 0 0 0 0 0 0 0.2 0.5 0.3  
(B, A) 
 0.1 0.5 0.4 0 0 0 0 0 0  
P(V ) = (B, B) 
 0 0 0 0.3 0.2 0.5 0 0 0  
(B, C) 
 0 0 0 0 0 0 0.2 0.5 0.3  
(C, A) 
 0.1 0.5 0.4 0 0 0 0 0 0  
(C, B)  0 0 0 0.3 0.2 0.5 0 0 0 
(C, C) 0 0 0 0 0 0 0.2 0.5 0.3

(b) (12 puntos). Formule el programa lineal que le permitirı́a hallar la polı́tica óptima. Suponga un
factor de descuento por periodo de β y solo presente las restricciones asociadas a dos estados. Como
el problema de decisión dinámico es de maximizar, el LP es de minimización. Ası́ pues la función
objetivo es

min z = V(A,A) + V(A,B) + V(A,C) + V(B,A) + V(B,B) + V(B,C) + V(C,A) + V(C,B) + V(C,C)

Las restricciones son: Para los estados que inician en A,

VA,A ≥ − 2.5 + (1/10)VA,A + (1/2)VA,B + (2/5)VA,C

VA,A ≥12.5 + (1/10)VA,A + (1/2)VA,B + (2/5)VA,C
VA,B ≥ − 2.5 + (1/10)VA,A + (1/2)VA,B + (2/5)VA,C
VA,B ≥18.5 + (3/10)VB,A + (1/5)VB,B + (1/2)VB,C
VA,C ≥ − 2.5 + (1/10)VA,A + (1/2)VA,B + (2/5)VA,C
VA,C ≥24 + (1/5)VC,A + (1/2)VC,B + (3/10)VC,C .

Para los estados que inician en B,

VB,A ≥ − 1.5 + (3/10)VB,A + (1/5)VB,B + (1/2)VB,C

VB,A ≥4.5 + (1/10)VA,A + (1/2)VA,B + (2/5)VA,C
VB,B ≥ − 1.5 + (3/10)VB,A + (1/5)VB,B + (1/2)VB,C
VB,B ≥4.5 + (3/10)VB,A + (1/5)VB,B + (1/2)VB,C
VB,C ≥ − 1.5 + (3/10)VB,A + (1/5)VB,B + (1/2)VB,C
VB,C ≥39 + (1/5)VC,A + (1/2)VC,B + (3/10)VC,C .

Y para los estados que inician en C,

VC,A ≥ − 1 + (1/5)VC,A + (1/2)VC,B + (3/10)VC,C

VC,A ≥32.5 + (1/10)VA,A + (1/2)VA,B + (2/5)VA,C
VC,B ≥ − 1 + (1/5)VC,A + (1/2)VC,B + (3/10)VC,C
VC,B ≥48.5 + (3/10)VB,A + (1/5)VB,B + (1/2)VB,C
VC,C ≥ − 1 + (1/5)VC,A + (1/2)VC,B + (3/10)VC,C
VC,C ≥1.5 + (1/5)VC,A + (1/2)VC,B + (3/10)VC,C .

17. a (5 puntos) Sea Xn , n ≥ 0 una CMTD con matriz de probabilidad de transición a un paso P . Suponga que
el proceso estocástico se encuentre en estado estacionario y que Xh = i. ¿Cuál es P [Xh+2 = j|Xh = i]?
2
La probabilidad que se busca es Pi,j .

b (5 puntos) Un centro de servicio que cuenta con 3 servidores recibe usuarios que llegan de acuerdo a un
proceso de Poisson con tasa λ. Cada usuario es atendido por un servidor en un tiempo exponencial de
promedio µ. Los usuarios que no encuentran un servidor disponible esperan en cola. Asuma que la cola
es infinita y proporcione una expresión general para la tasa de transición entre cada pareja de estados
del proceso estocástico X(t), donde X(t) representa el número de usuarios en el centro de servicio en
el tiempo t, t ≥ 0. El espacio de estados S es el conjunto de naturales, el sistema es equivalente a una

26
 cola M/M/3/GD/∞/∞. Sea µ = 1/4min−1 = 15 llamadas por hora, la tasa de servicio y sea λ = 10
llamadas por hora la tasa de arribos. Ası́ que la tasa rij , por cada i, j ∈ S, i 6= j, se expresa como:

 λ si j = i + 1, ∀i ∈ S

i
krij k = si j = i − 1 y 0 < i ≤ 3
 µ3
µ si j = i − 1 y 3 < i

c (10 puntos) Un restaurante que vende únicamente perros calientes tiene en frente un competidor que
vende hamburguesas y perros calientes. En el segundo restaurante, h% de los clientes pide hamburguesa
y (1 − h)% pide perros calientes. En ambos restaurantes, el tiempo promedio necesario para entregar el
pedido se distribuye exponencial con tasa α, y los clientes llegan de acuerdo a un proceso de Poisson con
tasa λ a cada restaurante. Usted quiere urgentemente comer un perro caliente y los dos restaurantes
son los únicos en el área. ¿Qué deberı́a tener en cuenta para elegir uno de ellos? En promedio, ¿cuánto
le tocará esperar para comprar su perro caliente?
Dado que es indiferente el tipo de comida pedida dado que ambas son entregadas según la misma
distribución, las filas tienen el mismo comportamiento. El criterio que deberı́a tenerse en cuenta es el
tamaño de la fila en el momento. El tiempo en fila promedio en cada restaurante es aproximadamente:
λ
WqM/M/1 =
α(α − λ)

d (10 puntos) Defina y demuestre la propiedad de no memoria de las variables aleatorias con distribución
exponencial.
La propiedad de no memoria indica que el tiempo pasado es irrelevante y para determinar cambios en
la variable. Es decir:

X ∼ exp(λ)
⇒ (i)P (X ≥ t + s|X > s) = P (X ≥ t) (ii)P (X ≤ t + s|X > s) = P (X ≤ t)∀t, s > 0

Basta con demostrar (i) ó (ii) para que se compruebe la condición.

Demonstración: Sea X ∼ exp(λ)

P (X ≥ t + s) e−λ(t+s)
P (X ≥ t + s|X > s) = =
P (X > s) e−λs
= e−λt = P (X ≥ t)
P (s < X ≤ t + s) P (X ≤ t + s) − P (X < s)
P (X ≤ t + s|X > s) = =
P (X > s) P (X > s)
(1 − e−λ(t+s) ) − (1 − eλs ) e−λs − e−λ(t+s)
= =
e−λs e−λs
−λt
= 1−e = P (X ≤ t)

e (10 puntos) El espacio de estados S de una CMTD está conformado por tres conjuntos S1 , S2 y S3 tales
que S1 ∪ S2 ∪ S3 = S y Si ∩ Sj = ∅ ∀i 6= j , i, j = 1, 2, 3. La matriz de probabilidades de transición a
un paso del proceso tiene la siguiente forma:

S1 S2 S3
 
S1 I 0 0
P = S2  R1 Q R2 
S3 0 0 I
Tome en cuenta que I, R1 , R2 y Q son matrices.
Explique cómo calcular la probabilidad que en el largo plazo del proceso esté en un estado cualquiera
de S1 , dado que al paso inicial está en un estado de S2 . En este caso, serı́a necesario calcular la matriz
de probabilidades de absorción. Tenemos:

B = (I − Q)−1

Con esta matriz calculamos la matriz de absorbsión:

U = BR

27
 Partiendo del supuesto que buscamos desde un estado i ∈ S2 esta probabilidad serı́a:
X
Ui,j
j∈S1

18. a) Un paciente hospitalizado puede estar en una de tres condiciones: Buena (B), Estable (E) o Crı́tica
(C) al principio de cada dı́a. Las probabilidades de transición entre estas condiciones se muestran a
continuación:
B E C
 
B 0.65 0.20 0.05
E  0.5 0.3 ? 
C 0.51 0.25 0.2
El hospital deja salir a los pacientes de acuerdo a su condición y basado en tres categorı́as: Mejora
(M ), Igual (I), o Muerto (U ) al principio de cada dı́a. La probabilidad de que un paciente salga del
hospital en una de estas tres categorı́as se muestra a continuación:

M I U
 
B 0.06 ? 0.01
E  0.03 0.02 0.03 
C ? 0.01 0.02
Encuentre los valores faltantes en las matrices de arriba.
Note que la primera matriz muestra las transiciones entre estados transitorios, siendo los estados
transitorios las condiciones de cada paciente al inicio de cada dı́a. Llame a esta matriz Q. La segunda
matriz muestra las transiciones entre estados transitorios y absorbentes, ya que se asume que cuando
un paciente sale del hospital no vuelve a entrar. Llame a esta matriz R. Si consideramos estos todos
los estados en un modelo de CMTD, se necesita que la matriz de probabilidades de transición sea
estocástica (es decir, que todas sus filas sumen 1). Por lo tanto, si S = {B, E, C, M, I, U }, necesitamos
que
X
Qij + Rij = 1 ∀i ∈ S
j∈S

Por ello, los valores faltantes son PE,C = 0.12, PB,I = 0.03 y PC,I = 0.01.
b) Defina el proceso de Nacimiento y Muerte descrito por la Figura 4 usando la notación Kendall-Lee.

5β 4β 3β 2β β

0 1 2 3 4 5

µ 2µ 2µ 2µ 2µ

Figure 4: Proceso de Nacimiento y Muerte

Este proceso representa una cola M/M/R/GD/K/K con R = 2 y K = 5. Este modelo aplica para el
problema del reparador de máquinas con 5 máquinas y 2 reparadores.
c) El tiempo entre arribos de dos estudiantes consecutivos a un horario atención de Modelos Proba-
bilı́sticos se distribuye exponencial con media 2 minutos. ¿Cuál es la distribución, la media y la
varianza del número total de estudiantes que llegan al horario si este dura 1 hora y media?
Sea N (t) la variable aleatoria que indica cuántos estudiantes han llegado al horario de atención hasta
el tiempo t. Note que N (t) ∼Poisson(λt) con λ = 1/2 estudiantes/minuto, ya que los tiempos entre
arribos se distribuyen exponencial. Por lo tanto, la distribución de estudiantes que llegan al horario de
atención completo es Poisson(45), con media E[N (45)] = 45 estudiantes y varianza var[N (45)] = 45
estudiantes2 .
d) ¿Cuál es el número esperado de carros en cola en un autolavado de un único servidor cuya utilización es
del 90%? Asuma distribuciones exponenciales para los tiempos entre arribos y los tiempos de servicio.
Se pregunta por el número promedio de carros en cola en el autolavado, es decir Lq . Note que este es
9
un sistema M/M/1/GD/∞/∞ con Utilización= ρ = 10 y por lo tanto:

ρ2 (9/10)2 81
Lq = = =
1−ρ 1/10 10

28
19. a) (5 puntos) Responda Verdadero o Falso y justifique únicamente si su respuesta es Falso. Todo problema
de decisión en el tiempo puede ser resuelto a optimalidad usando programación dinámica.

Falso. El problema debe satisfacer ciertas condiciones. Por ejemplo, si el problema no cumple con el
Principio de Optimalidad, programación dinámica no es un método de solución.

b) (5 puntos) Responda Verdadero o Falso y justifique en ambos casos. Para un sistema M/M/2/GD/∞/∞
se define ν = π0 + 12 π1 . Se puede afirmar que en estado estable ν es igual al valor de la utilización.
Puede justificar su respuesta formalmente o con palabras. Ayuda: Piense en lo que representa ν.

Falso. ν corresponde a la probabilidad de que el servidor 1 (o 2) en particular esté desocupado, y por

lo tanto, ν es igual a 1-utilización. Esto se debe a que ν se refiere a que el servidor particular esté
desocupado y la utilización se refiere a que el servidor esté ocupado.

c) (Bono 10 puntos) En cierto sector de Bogotá el clima es muy variable. Se sabe que un periodo de
lluvia dura un tiempo exponencial con media 1/γ minutos. Por otro lado, el tiempo entre lluvias se
distribuye exponencial con tasa α min−1 . Por este sector, pasan automóviles de acuerdo a un Proceso
de Poisson con tasa λ, de los cuales un porcentaje p son convertibles. Dé una expresión que le permita
calcular la probabilidad de que en estado estable algún carro convertible que pase por este sector se
moje debido a la lluvia. Su expresión debe estar únicamente en términos de α, γ, λ y p. Ayuda: Use
una CMTC que modele el estado del clima.

En primer lugar, note que el estado del clima es una CMTC que se puede describir como {X(t), t ≥ 0}
con X(t) el estado del clima en el tiempo t. El espacio de estados de esta cadena es SX = {LL, N LL},
donde LL es lluvioso y N LL no lluvioso. El diagrama de tasas de transición se muestra en la Figura
5.

LL N LL

Figure 5: CMTC Estado del Clima

Un carro solo se puede mojar si esta lloviendo, y por lo tanto debemos calcular πLL :

γπLL = απN LL
πLL + πN LL = 1
γπLL = α(1 − πLL )
πLL (γ + α) = α
α
πLL =
α+γ

Ahora, la probabilidad de que un carro convertible se moje (mientras llueve) es la misma probabilidad
de que ese tipo de automóvil pase antes de que pare de llover. Si denotamos esta probabilidad como
P [M ], obtenemos:

pλ
P [M ] = πLL ·
pλ + γ
α pλ
P [M ] = ·
α + γ pλ + γ

29
20. (a) (8 puntos) Responda Verdadero o Falso y justifique su respuesta en caso de ser Falso. Un banco
al que llegan personas de acuerdo a un Proceso de Poisson, cuyo servidor tarda un tiempo expo-
nencial en atender a cada cliente. Además, este servidor debe contestar el teléfono cada cierto
tiempo. Si el tiempo entre llamadas se distribuye exponencial, este sistema corresponde a un modelo
M/M/1/GD/∞/∞.

Falso. Aunque el tiempo de servicio natural se distribuye exponencial, las paradas que interrumpen
el servicio generan que el tiempo de servicio efectivo ya no sea exponencial. Esto ocurre independi-
entemente de la distribución del tiempo entre paradas (salidas a fumar).

(b) (12 puntos) Hay dos tiendas de video en su barrio (Blackbuster y Whitebuster) de las que puede
alquilar Blu-Ray de colecciones similares. Usted está considerando pagar la membresı́a de una de
estas tiendas. Usted sabe que a ambas tiendas llegan el mismo número de personas y que cada tienda
tiene dos personas en la caja. Sin embargo, Blackbuster tiene una sola fila tal que todas las personas
esperan en la misma cola y son atendidas apenas uno de los cajeros se desocupe. Por el otro lado,
Whitebuster tiene una fila separada para cada cajero. Ya que usted no tiene mucha información sobre
los tiempos entre arribos y de servicio, es razonable asumir que estos tiempos siguen distribuciones
exponenciales con tasas iguales para los dos cajeros de ambas tiendas. ¿Cuál membresı́a deberı́a
adquirir? Justifique su respuesta matemáticamente.

Como no se nos da ningún criterio para comparar los dos sistemas, optaremos por usar el tiempo en
cola promedio (por cliente), ya que este nos permite realizar una comparación objetiva. Llamaremos
al sistema 1 a la tienda Whitebuster, la cual tiene dos filas M/M/1/GD/∞/∞. El sistema 2 será
entonces la tienda Blackbuster que tiene una cola M/M/2/GD/∞/∞.

Note que para el sistema 1, es razonable asumir que la mitad de los clientes van para cada fila, por
lo que si la tasa de arribos es λ, la tasa de entrada efectiva para cada cola será λ/2. Para cualquiera
de las colas de este sistema tenemos que:

ρ2
Lq1 =
1−ρ
λ
ρ=
2µ
Lq
Wq1 = 1
λ/2
2ρ2
Wq1 =
λ(1 − ρ)

Para el sistema 2 tenemos que la tasa de entrada efectiva es λ ya que solo hay una fila. Sin embargo,
en este caso tenemos 2 servidores para la cola, por lo que la tasa de servicio máxima es 2µ.

P [j ≥ 2]ρ
Lq2 =
1−ρ
λ
ρ=
2µ
Lq
Wq2 = 2
λ
P [j ≥ 2]ρ
Wq2 =
λ(1 − ρ)

Para comparar ambos Wq los dividimos y ası́ obtenemos:

30
 2ρ2
 

Wq1 λ(1 − ρ)
= 
Wq2 P [j ≥ 2]ρ
λ(1 − ρ)
Wq1 2ρ
=
Wq2 P [j ≥ 2]

Note que P [j ≥ s] para algún s > 1 siempre va a ser menor a ρ, independientemente de los valores de
λ y µ. Por lo tanto la razón Wq1 /Wq2 será mayor a 1 y es mejor adquirir la membresı́a del sistema
2 (Blackbuster). Note que llegamos a la misma conclusión si el criterio de comparación es el número
promedio de personas en cola.
21. a (5 puntos) Sea S el conjunto S = {1, 2, 3} y A la siguiente matriz (3×3)
 
−1 1 0
A =  0 −1 1 
1 0 −1

Considere la Cadena de Markov de Tiempo Continuo definida como {X(t), t ≥ 0}, donde X(t) es
el estado del proceso estocástico at tiempo t, el espacio de los estados es S y la matriz de transiciones
es A. Calcule limt→∞ P [X(t) = 3|X(0) = 1].

La probabilidad estacionaria que se busca es 1/3.

b (5 puntos) Considere una Cadena de Markov de Tiempo Discreto {Xn , n ≥ 0} donde el espacio
de los estados y la matriz de las probabilidades de transición a un paso son S = {1, 2, 3} y A la siguiente
matriz (3×3)  
0 1 0
A= 0 0 1 
1 0 0
Calcule limn→∞ P [Xn = 3|X0 = 1].

La probabilidad que se busca no existe, ya que el proceso es periódico.

c (10 puntos) La empresa Merm&Co recibe frutas que pasan primero por una operación de lavado y
segundo por una desinfección. La máquina de lavado en promedio procesa 6Kg/min de fruta, y el
equipo de desinfección procesa 5Kg/min. En promedio llegan 240Kg/h de frutas, según un proceso de
Poisson. El tiempo de servicio de la máquina de lavado se distribuye exponencial, mientras el tiempo del
tratamiento igienizante es general, con desviación estandar igual a 0.2 min. Calcule el tiempo promedio
de procesamiento en estado estacionario para cada kilogramo de fruta.

Primera pregunta Es una red tandem, con un primer nodo M/M/1 y un segundo nodo M/G/1 (ya que
el primero es estable). Dada la topologı́a, se pueden sumar los tiempos. El tiempo en la primera etapa
de procesamiento es
1 1
= 6 − 240/60 = 1/2min
µ−λ /
El tiempo en la segunda es (Lq + Ls )/λ. Lq se obtiene de la formula de K&P:

λ 2 σ 2 + ρ2 16/25 + 16/25
Lq = = = 16/5Kg
2(1 − ρ) 2 ∗ 1/5
El Ls es 4/5, ası́ que el L es 4. El W del segundo nodo es 1min. El W total es 1.5min.

d (10 puntos) Proporcione una expresión para la utilización de un sistema

M/M/s/GD/∞/∞ en términos de las probabilidades en estado estable πj y s.

31
 s ∞ s−1
X j X X s−j
Utilización = πj + πj = 1 − πj
j=0
s j=s+1 j=0
s

22. (a) (10 puntos) Un supermercado cuenta con varios cajeros donde cada uno tiene su propio operario y
propia fila. Dos de ellos (cajeros A y B) son para clientes Premium. Dichos clientes llegan a los
cajeros Premium de acuerdo a un PP(λ) y escogen cualquiera de estos dos cajeros con igual proba-
bilidad. El cajero A tiene capacidad para albergar a cualquier número de clientes, mientras que el
B solamente puede tener a x clientes en espera. Se sabe que el número promedio de clientes en los
sistemas A y B es el mismo. Los clientes Premium que llegan al cajero B y ven que está lleno deciden
hacer fila en algún cajero que no sea Premium (distinto al A y al B). Suponiendo que ambos sistemas
son estables y que los tiempos de servicio de los dos cajeros son independientes y exponenciales, en
cuál de las dos filas el tiempo promedio que permanece una entidad en el sistema es menor? Justifque
su respuesta.

Se tienen dos sistemas con la misma tasa de arribos y misma cantidad de entidades promedio en el
sistema, sin embargo el sistema B tiene capacidad, por lo que se tiene que:

LA = LB
λeA WA = λeB WB
1 1
λWA = λ(1 − πC )WB
2 2
WA = (1 − πC )WB

Dado que 1 − πC < 1, WA < WB . Por lo tanto en el sistema sin capacidad en promedio las entidades
se demorarán menos.

(b) (12 puntos) Calcule los siguientes valores teniendo en cuenta la siguiente matriz de probabilidades
de transición de una CMTD:

1 2 3 4 5 6 7 8 9
1 1 1 1
 
1 0 3 3 0 6 0 0 6 0
2
0 1 0 0 0 0 0 0 0
3
0 0 0 1 0 0 0 0 0
4
0 0 1 0 0 0 0 0 0
1 1 1

P = 5
0 0 0 0 4 2 4 0 0
6
0 0 0 0 0 0 1 0 0
7
0 0 0 0 1 0 0 0 0
1 1 

80 0 0 0 0 0 0 2 2
9 14 0 0 0 1
4 0 0 1
2 0
• limt→∞ P (Xt = 5|X0 = 7)
• limt→∞ P (Xt = 4|X0 = 4)
• P (X200 = 8|X198 = 9)
• limt→∞ P (Xt = 8|X0 = 1)
• limt→∞ P (Xt = 5|X0 = 7) = 49
Los estados 5, 6 y 7 forman una clase comunicante cerrada ergódica. Por lo tanto, esta proba-
bilidad en estado estable se puede calcular resolviendo π5 = 14 π5 +π7 , π6 = 12 π5 yπ5 +π6 +π7 = 1.

• limt→∞ P (Xt = 4|X0 = 4) :

Los estados 3 y 4 forman una clase comunicante cerrada periódica con k=2. Por lo tanto, esta
probabilidad en estado estable no se puede calcular.

7
• P (X200 = 8|X198 = 9) = 24
Para hallar esta probabilidad, hay que tener en cuenta que partiendo de 9 hay dos caminos para
llegar a 8 en dos pasos. El primero pasando de 9 a 8 y de nuevo a 8. El segundo pasando a 1

32
 primero y luego a 8. Por lo tanto:
1 1 1 1 7
P (X200 = 8|X198 = 9) = · + · =
2 2 4 6 24
• limt→∞ P (Xt = 8|X0 = 1) = 0
(c) (13 puntos) Usted diseña un sistema cuyos tiempos entre arribos se distribuyen exponencial con
tasa λ. Tiene la posibilidad de contratar a dos trabajadores, los cuales son idénticos y atienden en
promedio a λ personas/minuto siguiendo una distribución exponencial, o contratar a un trabajador
capacitado que atiende a una tasa de 2λ. Si le interesa reducir el tiempo promedio en cola, ¿cuál
deberı́a ser la varianza del tiempo de atención del trabajador capacitado para que los dos sistemas
sean equivalentes?

Primero examinamos la opción de los dos servidores (trabajadores en entrenamiento), para la cual
usaremos el subı́ndice 1. Esta fila se puede modelar como una M/M/2/GD/∞/∞. Para obtener el
tiempo promedio en cola, primero calculamos el número promedio de personas en cola. La expresión
que nos permite calcular Lq para una M/M/2 es:

P (j ≥ s)ρ1
Lq1 =
1 − ρ1
donde ρ1 = λ/sµ donde µ es la tasa de servicio de cada servidor, la cual es λ. Por lo tanto ρ1 = 0.5.
En este caso P (j ≥ s) = 0.33 = 13 por lo que Lq1 = 13 . Finalmente, usando ley de Little obtenemos:

Lq1 1
Wq1 = =
λ 3λ
Ahora examinamos el sistema del trabajador capacitado como único servidor, referenciado por el
subı́ndice 2. Para este sistema no conocemos la distribución de probabilidad del tiempo de servicio,
por lo que podemos usar el modelo M/G/1/GD/∞/∞ para hallar las medidas de desempeño rele-
vantes. Usando la fórmula de Pollaczek-Khinchin tenemos:

λ2 σ 2 + ρ22
Lq2 =
2(1 − ρ2 )
Como el servidor atiende con tasa 2λ, tenemos ρ2 = 0.5. Incluyendo esto dentro de la expresión de
Lq2 obtenemos:

λ2 σ 2 + 1/4
Lq2 = = λ2 σ 2 + 1/4
2(1 − 1/2)
Como buscamos que los dos sistemas sean equivalentes en cuanto al tiempo promedio en cola, quer-
emos que:

Lq2 1
Wq1 = Wq2 = =
λ 3λ
De esta forma, la expresión que nos permite encontrar la varianza deseada del tiempo de servicio del
sistema 2 (σ 2 ) es:

λ2 σ 2 + 1/4 1
=
λ 3λ
Despejando para σ 2 obtenemos:

1
σ2 =
12λ2

33