Capítulo 2

Programación Dinámica

Programación dinámica es una paradigma de modelamiento que facilita la formulación de proble-

mas de decisión secuenciales bajo incertidumbre en general, particularmente en el caso donde
la decisión puede adaptarse a la información que se recibe durante la operación del sistema bajo
estudio. Para clarificar esto, consideremos el prototipo de problema de decisión que queremos
estudiar; aquel donde la función objetivo (que asumiremos queremos maximizar) corresponde
a la contribución recolectada secuencialmente desde un número contable de períodos. Esto es,
queremos resolver el problema
N
( " #)
X
máx E gn (an , ω) : a ∈ A . (2.1)
n=1

Por ahora basta con suponer que N < ∞, veremos el caso contrario más adelante en el apunte.
Como se menciono en el capítulo anterior, cuando se consideran políticas de decisión dinámi-
cas, se debe tener cuidado en representar adecuadamente el conjunto A de acciones posibles.
Programación dinámica nos ayuda a resolver este dilema. Para entender a esto, veamos primero
la formulación del problema cuando nos limitamos a implementar decisiones estáticas o open
loop.

2.1. Decisiones open-loop

Estas son decisiones que se calculan al comienzo del horizonte de planificación, y que NO se
modifican a medida que transcurre el tiempo, independiente de la información que se recolecte
durante la operación del sistema.

Dentro de nuestra formulación prototípica (2.1) tenemos que una acción a := (an , n ≤ N ) incluye
una acción a tomar en cada período n. Una acción open-loop es aquella que se decide antes del
horizonte de planificación y no se cambia después. En términos técnicos, a puede corresponder
a un secuencia de elementos aleatorios (esto posibilita considerar políticas donde el tomador
de decisiones deja espacio para el azar), sin embargo toda aleatoriedad solo puede depender
de la información disponible al comienzo del horizonte de planificación. En el lenguaje de la
Observación 1.1, A contiene a todos los vectores aleatorios a que para cada periodo asignan la

23
misma acción a todos los ω que pertenecen al mismo conjunto en F1 (la información disponible
en el periodo ficticio 0): esto se denota como a ∈ F1 . Consideremos un ejemplo concreto.

Ejemplo 2.1. Inventario multi-período - Open Loop

Retomemos el problema del Newsvendor multiperíodo, pero considerando decisiones estáticas.

Esto es, se debe decidir desde un comienzo cuanto se ordena para cada periodo, independiente
de la realización observada de la demanda. Si no permitimos aleatoriedad en las ordenes,
tenemos que A consiste simplemente en todos los vectores a no negativos de dimensión N tal
que an ∈ N para todo n. Definiendo Sn como la cantidad de unidades disponibles (pre-orden)
al comienzo del periodo n, el problema de optimización a resolver es
( "N #)
X
máx E p mı́n{an + Sn , Dn } − c an − h máx{0, an + Sn − Dn } ,
a∈NN
+ n=1

donde an representa cuanto ordenar al comienzo del período n. En esta formulación es nece-
sario linkear la decisión de orden y la demanda en un período con el inventario al comienzo
del siguiente período. Esto es,

Sn+1 (ω) = máx{0, an + Sn (ω) − Dn (ω)}.

2.2. Decisiones closed-loop

Estas son decisiones que se calculan lo más tarde posible, i.e. justo antes de tener que implemen-
tarse. Esto es, la acción correspondiente al periodo n puede depender de la situación en que se
encuentra el sistema al comienzo de dicho periodo. En términos técnicos, a puede corresponder
a un secuencia de elementos aleatorios, donde la aleatoriedad asociada a an puede depender de
la información disponible al comienzo de dicho período. En el lenguaje de la Observación 1.1, A
contiene a todos los vectores aleatorios a que para cada periodo n asignan la misma acción an
a todos los ω que pertenecen al mismo conjunto en Fn (la información disponible en el periodo
n): esto se denota como an ∈ Fn , y decimos que a ∈ F.

En el caso de decisiones closed-loop, a veces no es fácil escribir/implementar el problema de

optimización asociado. Veamos esto en un ejemplo.

Ejemplo 2.2. Inventario multi-período - Closed Loop

En este caso se decide cuanto ordenar en el periodo n considerando la información disponible

al comienzo de ese periodo. Tal como antes, definimos Sn (ω) como la cantidad de unidades
disponibles (pre-orden) al comienzo del periodo n (denotamos la dependencia en ω para

24
 explicitar que esta cantidad es una variable aleatoria). En este caso, el problema a resolver es
( "N # )
X
máx E p mı́n{an + Sn , Dn } − c an − h máx{0, an + Sn − Dn } : an ∈ Fn , n ≤ N ,
n=1

donde Sn+1 (ω) = máx{0, an (ω) + Sn (ω) − Dn (ω)}. Vemos que, sin supuestos adicionales,
caracterizar el conjunto A = {a ∈ NN
+ , an ∈ Fn , n ≤ N } puede ser díficil.

A continuación presentamos una técnica de modelamiento (programación dinámica) que permite

especificar de manera simple el conjunto A.

2.3. Programación Dinámica Estocástica

Para resolver (2.1) necesitamos buscar entre las política de decisión (i.e. secuencias aleatorias
adaptados a la historia del proceso), por lo que es necesario entender que significa que an ∈ Fn .
Para simplificar la representación del conjunto A, definiremos una variable de estado Sn que
representa la información relevante para tomar la decisión en el período n. (Formalmente, esto
es Fn = σ(Sn ).) Con esto, relegamos la incertidumbre al estado del sistema Sn y representamos
una política factible como un vector de funciones

µ = (µ1 (·), . . . , µN (·)),

donde µn (Sn ) representa la acción a tomar cuando uno se encuentra en el estado Sn al comienzo
del período n.

Ejemplo 2.3. Inventario multi-período - Variable de estado

Si no permitimos aleatoriedad en las ordenes, y consideramos el supuesto de demandas inde-

pendientes, entonces tenemos que Fn simplemente contiene la información acerca del numero
de unidades en inventario al comienzo del periodo n (es decir, Sn ). Entonces, en este caso
A consiste en todos los vectores a no negativos de dimensión N tal que an (ω) ∈ N depende
solamente de Sn (ω) para todo n. De esta forma, para especificar una solución al problema
debemos determinar el valor de an (x) para todo x ∈ N, para todo n.

Considerando esta nueva representación, haremos explícita la dependencia de la función de ganan-

cia en el estado del sistema. Normalmente omitiremos las dependencias en ω, donde se entiende
que la variable de estado es aleatoria (y por lo tanto, también lo es la decisión - pero tan solo
como consecuencia de la aleatoriedad del estado). En esta linea, denotaremos por Wn (ω) a toda
la incertidumbre que afecte la evolución del sistema durante el periodo n: en el caso del pro-
blema de inventario multi-período, esta incertidumbre corresponde a la demanda por el producto
durante un período. De esta forma, consideramos que para acciones a ∈ A (admisibles)

gn (an (ω), ω) ≡ gn (µn (Sn (ω)), Sn (ω), Wn (ω)).

25
Con esto, para un estado inicial S1 dado, podemos reescribir (2.1) de la siguiente forma.
( "N # )
X
J1 (S1 ) = máx E gn (µ(Sn ), Sn , Wn ) : µ ∈ U , (2.2)
n=1

donde, U = (Un , n ≤ N ), con Un el conjunto de funciones µn : Sn → An , representa el conjunto

de políticas factibles (aquí Sn representa todos los posibles estados del sistema al comienzo del
periodo n, y An representa el conjunto de acciones factibles durante el periodo n, de forma que
siempre (con probabilidad 1) se tiene que Sn ∈ Sn y an = µ(Sn ) ∈ An . Observamos que ahora
la optimización es sobre un conjunto de funciones. Normalmente consideraremos sistemas donde
tanto el número de estados como el de acciones son finitos.

Observación 2.1. Elección de la variable de estado

Es importante notar que existen muchas formas de definir las variables de estado que son
suficientes para tomar la decisión en el período n: siempre trataremos de escoger aquella
con mínimos requerimientos de memoria. También es importante notar que la condición
de suficiencia es importante. Por ejemplo, si las demandas no fuesen independientes en el
ejemplo de arriba, entonces sería necesario agregar información acerca de las ventas en todos
los períodos anteriores a n a la variable Sn , dado que esta información ayudaría a estimar de
mejor forma la demanda futura.

Supongamos que µ∗ denota la solución óptima a la formulación base (2.2). La técnica de resolución
que estudiaremos a continuación se basa en el siguiente principio: la política óptima µ∗ también
resuelve el problema de optimización cuando el horizonte de planificación comienza ahora en el
periodo n, con un estado inicial Sn cualquiera.

Definición 2.1. Principio de Optimalidad

Sea µ∗ la política óptima del problema base, y supongamos que un estado Sn ocurre con
probabilidad positiva cuando usamos la política µ∗ . Consideremos el sub-problema donde
acumulamos ganancias solo a partir del período n, partiendo desde el estado Sn , i.e.
( ( N ) )
X
Jn (Sn ) = máx E gk (µk (Sk ), Sk , Wk ) : (µn , . . . , µN ) ∈ (Un , . . . , UN ) .
k=n

La política óptima para el sub-problema es µ̃∗ = (µ∗n , µ∗n+1 , . . . , µ∗N ) para todo estado inicial
Sn .

Para modelar la dinámica temporal del estado del sistema, consideraremos un recurrencia de
estados que establece la relación entre la variable de estado en un período y aquella en el
siguiente período, como función de la decisión tomada en un período y la incertidumbre en el
sistema. Esto es, planteamos que existe un mapa fn (·) tal que

Sn+1 = fn (µn (Sn ), Sn , Wn ), ∀ n.

26
La función de recurrencia esta determinada por la elección de la variable de estado. Notamos
que Sn+1 es un objeto aleatorio, dado que depende de la incertidumbre Wn .

Ejemplo 2.4. Inventario multi-período - recursión de estados

En el caso del Newsvendor multiperíodo, notamos que Wn = Dn , con lo que tenemos que la
recurrencia de estados esta dada por

Sn+1 (ω) = máx{0, µn (Sn ) + Sn − Dn (ω)).

El algoritmo de Programación Dínamica que presentamos a continuación se basa en las siguientes

observaciones:

Cuando enfrentamos la decisión del período n, no nos importa la historia del proceso más
allá de aquella información contenida en Sn .

Para resolver el problema partiendo en el periodo 1 en el estado S1 (nuestro objetivo final),

podemos utilizar el principio de optimalidad para recuperar µ∗ con una inducción inversa
en el tiempo: primero descubrimos el valor de µ∗N resolviendo un problema (normalmente
muy simple) con un periodo de duración (el periodo N ). En la práctica este paso lo hacemos
planteando la existencia de un periodo final N + 1 ficticio, y definiendo la condición de
borde JN +1 (·) = 0. (Dependiendo del problema, esta condición de borde puede tomar otra
forma.)

Para calcular µ∗n (Sn ) resolvemos el problema de optimización que parte en el periodo n
desde el estado Sn , apoyandonos en el hecho que ya conocemos (µ∗n+1 , . . . , µ∗N ). Esto implica
que podemos recuperar la política óptima resolviendo una secuencia de sub-problemas que
buscan maximizar las ganancias acumulativas, optimizando solo sobre la acción a tomar
en el periodo actual, asumiendo que a partir del próximo periodo conocemos las acciones
óptimas para cualquier estado en el que nos encontremos en el futuro.

Para realizar el paso anterior, utilizamos la definición de Jn (Sn ) como las ganancias óptimas
acumuladas desde el periodo n hasta el periodo N cuando el estado inicial en el periodo
n es Sn . De esta forma, calculamos µ∗ (Sn ) resolviendo la Ecuación de Bellman, que
relaciona las ganancias óptimas acumuladas desde el periodo n con aquellas acumuladas
desde el periodo n + 1, la recurrencia de estados, mediante una optimización.

Jn (Sn ) = máx {E [gn (an , Sn , Wn ) + Jn+1 (fn (an , Sn , Wn )]} .

an ∈An

Es importante notar que en la ecuación de Bellman, la optimización es directamente sobre

una acción, no sobre una función.

27
 Definición 2.2. El Algoritmo de Programación Dínamica

Para cada condición inicial S1 , la ganancia óptima J1 (S1 ) asociada al problema base (2.2)
esta dada por el siguiente algoritmo recursivo, que parte en el período (ficticio) N + 1, y se
mueve hacia atrás en períodos, desde el período final N hasta llegar al período inicial 1:

JN +1 (SN +1 ) = 0, (2.3)
Jn (Sn ) = máx {E [gn (an , Sn , Wn ) + Jn+1 (fn (an , Sn , Wn ))]} , n≤N (2.4)
an ∈An

donde el valor esperado se toma respecto a la incertidumbre asociada a cada periodo (Wn , n ≤
N ). Adicionalmente, sea µ∗ la política tal que µ∗n (Sn ) = a∗n , donde a∗n denota la solución a
(2.4), para n ≤ N , entonces µ∗ es una solución óptima a (2.2).

2.3.1. Elementos de un modelo de programación dinámica

Considerando lo anterior, y a modo de resumen, para definir un modelo de programación dinámica

es necesario especificar los siguientes elementos.

Periodos. El modelo de optimización prototípico asume i) una función objetivo que acu-
mula ganancias a través de los periodos; y ii) la toma de decisión se hace en forma secuen-
cial, con las implicancias para la recolección de información que esto trae. Normalmente,
cuando tratamos con problemas de toma de decisión a través del tiempo, la secuencia es
la temporal. Sin embargo, es posible modelar mediante programación dinámica problemas
donde no existe una secuencia temporal. (Ver el ejemplo del problema de la mochila mas
abajo). En dicho caso, la definición de la secuencia de las decisiones es parte del trabajo
de modelamiento.

Decisiones. Es importante que las decisiones no están restringidas a priori a ser valores
reales, o vectores. Pueden corresponder a conjuntos, funciones, etc. Es una decisión de
modelamiento cual es la representación más efectiva de la decisión.

Estados. Tal como las decisiones, las decisiones no están restringidas a priori. Como se
menciono anteriormente, el estado debe contener información suficiente para caracterizar
la situación actual y la evolución probabilista del sistema. En términos prácticos, tam-
bién es deseable que dicha información sea solamente aquella necesaria para cumplir esa
función. Si bien, el paradigma de programación dinámica permite modelar, y en teoría
resolver, cualquier problema de toma secuencial de decisiones bajo incertidumbre con las
características descritas, en la practica el principal obstáculo que impide el uso masivo de
la programación dinámica es la maldición de la dimensionalidad: dependiendo del pro-
blema, es posible que n |Sn | (el número total de estados posibles durante la ejecución del
P

problema) crezca exponencialmente con N ; como el algoritmo de programación dinámica

necesita guardar Jn (Sn ) para todo Sn , es posible que no sea posible almacenar en memoria
( de un computador) dicha información.

28
 Incertidumbre. Esta corresponde a la aleatoriedad que afecta i) las ganancias recolectadas
en un periodo, y ii) la evolución del estado de un sistema. Por lo mismo, su representación
depende de la elección de la variable de estado, y la decision.

Recurrencia de estados. Esto es normalmente una consecuencia de la elección de repre-

sentación de la decisión, el estado y la incertidumbre.

Ecuación de Bellman. Si bien la forma general esta dada por (2.4), en general su forma
puede variar dependiendo del problema. Por ejemplo, consideraremos situaciones donde el
horizonte es infinito, o otros donde con cierta probabilidad el problema termina y no se
avanza al siguiente periodo (en este caso, Jn+1 debiese estar ponderar por la probabilidad
de avanzar en el tiempo, la cual puede depender de la acción, el estado, y la incertidumbre).
Parte de la tarea de modelamiento consiste en detectar e incorporar estas modificaciones.

Condición de borde. Normalmente corresponde a aquella asociada al periodo final fic-

ticio. Sin embargo existen variaciones. Por ejemplo, en algunas circunstancias uno puede
indicar que en cualquier periodo, si se llega a alguna clase de estados Zn , el problema
termina (en cuyo caso imponemos la condición de borde Jn (Sn ) = 0 para todo Sn ∈ Zn ).
Tal como en el caso de Bellman, parte de la tarea de modelamiento consiste en detectar e
incorporar estas modificaciones.

2.4. Programación Dinámica Determinista

En esta sección se considera el caso particular cuando no existe incertidumbre en una formulación.
Siendo un caso especial, el principio de optimalidad sigue aplicando, por lo que también lo hace
el algoritmo de programación dinámica. En este caso, la función de ganancia es determinista,
por lo que tenemos que
gn (an (ω), ω) ≡ gn (µn (Sn (ω)), Sn (ω)).

Notamos que la aleatoriedad en la ecuación de arriba esta dada exclusivamente por aquella aso-
ciada a la acción a tomar (puede ser que el tomador de decisiones este aleatorizando su decisión).
Si restringimos nuestra atención a políticas deterministas, entonces esta aleatoriedad desaparece.
Adicionalmente, la recurrencia de estados se transforma en la relación determinista

Sn+1 = fn (µn (Sn ), Sn ), n ≤ N.

Entonces, dado que no existe incertidumbre alrededor de que valor tomara Sn (dadas las acciones
en los periodos 1 a n − 1), µ(·) solo es relevante en el valor que asigna a µn (Sn ) ≡ an . Esto tiene
sentido dado que, sin incertidumbre, no existe información que no sea anticipable (y se incorpore
a la filtración), por lo que en este caso open loop = closed loop. Esto implica que el problema
base que queremos resolver toma la forma
N
( )
X
J1 (S1 ) = máx gn (an , Sn ) : µ ∈ U , (2.5)
an ∈An , n≤N
n=1

donde Sn+1 = fn (an , Sn ). En este caso, Bellman toma la forma a continuación

29
 Definición 2.3. Programación Dínamica Determinista

Para cada condición inicial S1 , la ganancia óptima J1 (S1 ) asociada al problema base está
dada por el siguiente algoritmo recursivo, que parte en el período (ficticio) N + 1, y se mueve
hacia atrás en períodos hasta llegar al período 1:

JN +1 (SN +1 ) = 0,
Jn (Sn ) = máx {gn (an , Sn ) + Jn+1 (fn (an , Sn ))} , n ≤ N.
an ∈An

Observación 2.2. Elementos de una programación dinámica determinista

Los elementos de un modelo en el caso determinista son los mismos que en el caso estocástico,
con la excepción que no se especifica la incertidumbre Wn asociada a cada periodo. Esto es,
es necesario especificar los periodos del problema, las decisiones, estados en cada periodo,
y la recursión de estados, además de las condiciones de borde y la forma de la ecuación de
Bellman.

El ejemplo más famoso de aplicación del algoritmo de programación dinámica a problemas de-
terministas es sin lugar a dudas el problema del camino más corto. Este ejemplo muestra como
es posible que no sea necesario explicitar la temporalidad de la decisión.

Pregunta 2.1. Camino más corto

Considere el problema de encontrar el camino más corto entre dos nodos s y t en un grafo
dirigido G = (V, E), cuando el costo asociado a utilizar un arco a está dado por ca . (Con V el
conjunto de nodos y E el conjunto de arcos del grafo G.) En esta aplicación, nos imaginaremos
que periodo a periodo viajando de un nodo a nodo en el grafo. Definimos el estado del sistema
como el nodo en el que nos encontramos actualmente. El número de periodos es a priori infinito
(si existe un ciclo de costo negativo la solución sera quedarse en el grafo recorriendo ese ciclo
para siempre, por lo que asumiremos que no existe este tipo de ciclo), por lo que se necesitan a
los más N periodos para hacer cualquier recorrido no obviamente suboptimo. Dado el estado
Sn , la decisión an a tomar es cual es el siguiente nodo a visitar. En este caso el conjunto
de acciones posibles (que depende de Sn ) esta dado por An = {j ∈ V : (Sn , j) ∈ E}. La
recurrencia de estados es simplemente fn (an , Sn ) = an , y Bellman toma la

Jn (Sn ) = mı́n {cSn ,an + Jn+1 (an )}, ∀Sn ∈ V \ {t}

an ∈An
Jn (t) = 0 n ≤ N, JN +1 (Sn ) = ∞.

Notamos que las condiciones de borde son: i) el problema termina vez alcanzamos el nodo t;
y ii) penalizamos cualquier solución que no llega al nodo t en al menos N + 1 periodos (note
que Bellman esta expresada como un problema de minimización).

30
Ejercicio Propuesto: Problema de las 4 reinas Suponga que usted desea posicionar 4 reinas
en un tablero de Ajedrez de 4×4 de forma que las reinas no se ataquen entre ellas. Encuentre
dichas posiciones mediante programación dinámica determinista.

Ejemplo 2.5. Problema de la mochila

Considere el clásico problema de la mochila. Una formulación del problema de la mochila es

(N N
)
X X
máx cn an : wn an ≤ K, an ∈ N, n ≤ N
n=1 n=1

Donde an es la cantidad de unidades incluidas del ítem n, cn es el beneficio obtenido por cada
unidad de n en la mochila, wn es el volumen de n, y K es el volumen total de la mochila.
Modele el problema utilizando programación dinámica determinista.

Solución. El modelo es el siguiente.

Períodos: ítems n ∈ {1, . . . , N }

Variable de estado: Sn , el volumen disponible al momento de evaluar el ítem n

Variable de decisión: an , la cantidad del item n que incluimos en la mochila (an ∈ N)

Evolución del estado:

Sn+1 = Sn − an wn ≥ 0.

Condiciones de borde:

JN +1 (SN +1 ) = 0, ∀SN +1 , S1 = K.

Beneficio en la etapa n:
gn (an , Sn ) = an cn .

Ecuación de Bellman:

Jn (Sn ) = máx {gn (an , Sn ) + Jn+1 (Sn+1 ) : an wn ≤ Sn , an ∈ N} .

Veamos como se ejecuta el algoritmo de programación dinámica en una instancia del problema
de la mochila. (Si bien esto normalmente lo programaríamos y ejecutaríamos en un computador,
vale la pena ver la ejecución paso a paso al menos una vez.) Supongamos valores K = 6, c1 =
4, c2 = 3, c3 = 7, y v1 = 3, v2 = 2, v3 = 4. Una aplicación manual del algoritmo de programación
dinámica (determinista) se vería como sigue: comenzando con la última etapa,

31
 S3 /a3 0 1 a∗3 J3 (S3 )
0 0 - 0 0
1 0 - 0 0
2 0 - 0 0
3 0 - 0 0
4 0 7 1 7
6 0 7 1 7

Etapa n = 3

Notamos que el estado S3 = 5 no es factible, ya que ningún objeto tiene volumen 1.

S2 /a2 0 1 2 3 a∗2 J2 (S2 )

0 (1) - - - 0 0
3 0 3 - - 1 3
6 (2) (3) 6 9 1 10

Etapa n = 2

Podemos calcular, consultando la tabla anterior, los valores (1), (2) y (3):

(1) : 0 + J3 (S3 = 0) = 0
(2) : 0 + J3 (6) = 7
(3) : 3 + J3 (4) = 10

Procedemos de la misma forma para la etapa que falta:

S1 /a1 0 1 2 a∗1 J1 (S1 )

6 (4) (5) 8 0 10

Etapa n = 1

(4) : 0 + J2 (6) = 10
(5) : 4 + J2 (3) = 7

Por lo tanto, la solución a esta instancia del problema de la mochila es

J1 (S1 ) = 10; a∗1 = 0, a∗2 = 1, a∗3 = 1

32
2.5. Caso Horizonte Infinito Descontado
En esta sección estudiaremos problemas de horizonte infinito. Consideremos la formulación base
(2.2); si simplemente tomamos N → ∞, típicamente tendremos que existen múltiples políticas
que consiguen ganancias acumuladas infinitas. Con esto en mente, haremos dos simplificaciones:
i) primero, asumiremos que existe una tasa de descuento (similar a la que usan al momento
de evaluar proyectos de largo plazo), que representa un riesgo financiero, o alternativamente la
probabilidad que el horizonte de planificación acabe (de forma aleatoria); y ii) supondremos que
los beneficios, las recurrencias de estado, y las fuentes de incertidumbre son estacionarios (no
dependen del período). Con esto en mente, tendremos que la ganancia asociada al periodo n esta
dada por
gn (an , ω) ≡ αn g(an , ω),

donde α ∈ (0, 1) es una tasa de descuento. De esta forma, el siguiente problema base toma la
forma
N
( " ))
X
n
VN (S) := J1 (S) = máx E α g(µn (Sn ), Sn , W ) ,
µ∈U
n=1

sujeto a la condición que Sn+1 = f (an , Sn , W ), con S1 = S, donde α ∈ (0, 1] denota un factor de
descuento (i.e. representa el hecho que una unidad monetaria hoy vale más que la misma unidad
mañana).

Observación 2.3. Indexación de periodos

Notamos que VN (S) denota la ganancia óptima acumulada en N periodos de operación cuando
el sistema parte en el estado S. Esto es posible dado que la ganancia solo depende del periodo
a traves del descuento aplicado, a que la recurrencia de estados es la misma para todos los
periodos, y que la incertidumbre W distribuye igual en todos los periodos.

Un ejemplo del problema que estudiamos esta sección es el problema de inventario multi-periodo,
cuando las demandas forman una secuencia independiente e idénticamente distribuida, e incor-
poramos una tasa de descuento para contabilizar las ganancias.

Aplicando el algoritmo de programación dinámica, suponiendo que el conjunto de acciones posi-

bles tampoco dependen del tiempo, poniendo atención a la indexación de periodos tenemos que
la ecuación de Bellman toma la forma

Vn (S) = máx E {g(a, S, W ) + α Vn−1 (f (a, S, W ))} , n ≥ 1, ∀ S (2.6)

a∈A

con condición de borde J0 (S) = 0 para todo estado S. Con esta notación el problema de horizonte
infinito se define como
V (S) := lı́m Vn (S).
n→∞

Notamos que esta definición no especifica la política de acción que resuelve el problema de
horizonte infinito. Normalmente, impondremos condiciones sobre los párametros del problema
para que el límite de arriba exista. Por ejemplo, cuando α < 1, es suficiente tener que |g(·)| < K

33
para alguna constante finita K 1 Para el caso de α = 1, es suficiente imponer que existe al menos
un estado absorbente (esto es, un estado tal que si alguna vez el sistema ingresa a él, no es posible
escapar en el futuro), que genera ganancia nula, al cual se puede acceder con probabilidad positiva
desde cualquier otro estado, bajo cualquier política.

Notamos que de existir el límite, este debe ser tal que (2.6) se mantiene válida, pero ahora como
una ecuación de punto fijo. Esta ecuación es la versión de horizonte infinito de la ecuación de
Bellman. El siguiente resultado formaliza esto, y nos dice que la política óptima es una política
estacionaria (esto es, la acción que aplica depende solamente del estado en el que se encuentra
en el sistema, independiente de cuando esto ocurre).

Teorema 2.1. Horizonte infinito descontado - Ecuación de Bellman

Cuando existe, el límite V (·) es la única solución al sistema

V (S) = máx E {g(S, u, ω) + α V (f (S, u, ω))} , n ≥ 1, ∀ S

u∈U

Adicionalmente, la política óptima es cualquier política estacionaria µ∗ (·) que satisfaga la

condición
µ∗ (S) ∈ arg máx E {g(S, u, ω) + α V (f (S, u, ω))} , ∀S
u∈U

En lo que resta de esta sección describiremos tres métodos numéricos para resolver los problemas
de horizonte infinito descontado. En lo que sigue dejamos S ser el espacio de estados posibles del
sistema.

2.5.1. Value Iteration.

Para una función W (·) : S → R, definimos el mapa T como sigue:

(T W )(S) = máx E {g(S, u, ω) + α W (f (S, u, ω))} , S ∈ S.

u∈U

Notamos que V , la solución a la ecuación de Bollan, es tal que (T V ) = V . Es posible probar que
el mapa (T ·) es una contracción; es decir, para dos funciones W y W ′ , se tiene que

máx |(T W )(S) − (T W ′ )(S)| ≤ α máx |W (S) − W ′ (S)|,

S∈S S∈S

Lo anterior implica que la distancia entre (T k W ) y (T k+1 W ) converge a 0 independiente del

valor de W (aquí, (T k ·) denota la composición de (T ·) consigo misma, k veces). Entonces, por
construcción, el límite de la secuencia {(T k W ) : k = 1, 2, . . .} converge a V , la solución a la
ecuación de Bellman. Esto nos entrega el siguiente algoritmo.

1
Notamos que bajo estas condiciones el valor absoluto de la ganancia óptima acumulada como función de n
1
no puede diverger, dado que se encuentra acotada superiomente por K 1−α , para todo n.

34
Algorithm 1 Value Iteration
Fije V 0 arbitrariamente.
Calcule V 1 = (T V 0 ), y fije k = 0.
while máxS∈S |V k+1 (S) − V k (S)| < ϵ do
k =k+1
V k+1 = (T V k )
end while

Notamos que el algoritmo funciona partiendo desde cualquier condición inicial. En particular,
si se parte con V 0 = 0, entonces se tiene que V k = Jk . La cantidad ϵ > 0 en la condición de
término representa un margen de tolerancia a la convergencia.

2.5.2. Policy Iteration.

Para una política estacionaria µ(·), definimos la función Vµ (·) como el beneficio acumulado aso-
ciado a implementar dicha política, como función del estado inicial. Dicha función se puede
calcular mediante la recursión

Vµ (S) = E [g(µ(S), S, W ) + α Vµ (f (µ(S), S, W ))] , S ∈ S.

(Este es un sistema de ecuaciones lineales, el que debiese ser “fácil” de resolver). El siguiente
algoritmo opera en el espacio de las políticas estacionarias.

Algorithm 2 Policy Iteration

Fije k = −1, µ0 y µ−1 arbitrariamente, de forma que µ0 ̸= µ−1 .
Calcule Vµ0 .
while µk+1 ̸= µk do
Fije k = k + 1 y calcule µk (·) mediante

µk (S) ∈ arg máx E g(a, S, W ) + α Vµk−1 (f (a, S, W )) ,

 
S ∈ S.
a∈A

end while

La convergencia de {µk (·) : k = 1, . . .} a µ∗ está asegurada por los mismos argumentos que
aseguran la convergencia del algoritmo de Value Iteration.

2.5.3. Programación Lineal.

El siguiente algoritmo se basa en una representación alternativa de la función de valor, la cual

se basa a su vez el siguiente resultado de monotonicidad.

35
 Teorema 2.2. Monotonicidad

Para dos funciones cualquiera W y W ′ , se tiene que

W (S) ≥ W ′ (S) S∈S ⇒ (T W )(S) ≥ (T W ′ )(S) S ∈ S.

Supongamos que se tiene una función W tal que W (·) ≥ (T W )(·) de forma puntual, entonces
aplicación reiterada del mapa T más la convergencia del algoritmo del algoritmo de Value Itera-
tion garantizan que W ≥ V . Esto, en conjunto con la ecuación de Bellman nos dice que V es el
vector W más “pequeño” que satisface la condición W ≥ (T W ). Con esto, podemos escribir V
como la única solución a un programa de programación lineal, lo que nos da un tercer algoritmo
de resolución.

Algorithm 3 Programación Lineal

Formular y resolver
X
mı́n xS
S
X
s.t. xS ≥ E [g(a, S, W )] + P(f (a, S, W ) = S ′ ) xS ′ ∀ a ∈ A, S ∈ S.
S′

Notamos que el número de restricciones en esta formulación de programación lineal es igual al

número de estados multiplicado por el número de acciones posibles y que el número de variables
es igual al número de estados. En la solución óptima a este problema, el valor de la variable xS
representa el valor de V (S).

36
2.6. Ejercicios Resueltos

Pregunta 2.2. Tarea 1 - Otoño 2018

El profesor de un curso se encuentra buscando un ayudante de investigación, y ha decidido

entrevistar (secuencialmente) a todos los estudiantes del curso para llenar esta posición. La
calidad de un estudiante cualquiera es una variable aleatoria que toma valores entre 1 y 7
(solo con valores enteros), cada nota tiene igual probabilidad. La calidad de un estudiante se
revela durante la entrevista. Al final de cada entrevista, el profesor debe decidir si contratar al
estudiante o no. Si lo contrata, las entrevistas restantes se suspenden (hay solo una posición de
ayudante de investigación); si no lo contrata, el estudiante inmediatamente toma otro trabajo
incompatible con la posición de ayudante de investigación (todo esto antes del comienzo de la
entrevista al siguiente estudiante). El profesor sabe que un estudiante de calidad i cumple su
labor de investigación con probabilidad i/7, i = 1, . . . , 7. Modele el problema de maximizar la
calidad esperada del estudiante contratado mediante un modelo de programación dinámica.

Solución: Claramente las etapas están dadas por los alumnos, por lo que

período n = entrevista con el n-ésimo estudiante.

Sea Qn la variable aleatoria que representa la calidad del estudiante n. Sabemos que

P(Qn = k) = 1/7, k ∈ {1, . . . , 7}.

Nuestra decisión es si contratamos o no al estudiante n una vez que conocemos su calidad.


1 contratamos al estudiante n,
un =
0 ∼ .

Dado que estado debe representar la información necesaria para tomar dicha decisión, tenemos
que
Sn = Qn (calidad observada del estudiante n.)

Con esta definición de estado, la dinámica de la variable de estado está dada por2

Sn+1 = Qn+1 (ω) (calidad aleatoria del próximo estudiante.)

La recursión de Bellman esta dada por:

JN +1 (·) = 0
7
( )
1X
Jn (Sn ) = máx Sn , Jn+1 (k) .
7
k=1

Notamos que el primer término en el máximo arriba representa la decisión de contratar al estu-
diante n, mientras que el segundo representa la decisión de pasar a la entrevista del estudiante
n + 1.
2
Notemos que fn (un , Sn , ω) = Qn+1 (ω) calza con la estructura para la recursión, dado que Qn+1 es una
variable aleatoria, por lo que es precisamente una función de ω.

37
 Pregunta 2.3. Control 1 - Primavera 2018

Suponga que usted se encuentra asesorando a un grupo de N senadores del congreso esta-
dounidense durante la votación para confirmar al próximo juez de la corte suprema. Durante
la votación, los senadores son llamados a votar en el piso del senado en orden aleatorio. Al
ser llamado, cada senador pronuncia si está a favor o en contra de la confirmación.

Sus empleadores (los N senadores en cuestión) están interesandos en votar a favor de la

opción ganadora, por lo que le han encargado a usted decirles por qué opción deben votar
al momento de ser llamados.

Usted sabe que cada senador (excluyendo a sus empleadores) votará por confirmar al juez,
independientemente del resto y del resultado parcial de la votación, con probabilidad p.
Suponga que el número total de senadores es impar, y que gana la opción más votada.

De esta forma, los senadores comienzan a ser llamados en orden aleatorio; si no es el turno
de uno sus empleadores, el senador vota por confirmar al juez con probabilidad p; si es el
turno de uno de los N senadores, usted decide por que opción votará el senador en función
del conteo parcial de votos, como han votado sus empleadores hasta el momento, y cuantos
de sus empleadores quedan por votar.

Considerando que el senado esta compuesto por M senadores (incluyendo a sus empleadores,
con M > N ), defina un problema de programación dínamica que maximize la esperanza del
número de sus empleadores que vota por la opción ganadora.

(Hint: defina como etapas cada una de las ocasiones de voto, M en total, independiente de
si el voto es dado por uno de sus empleadores.)

Solución #1.

Etapas: las ocasiones de voto: en la etapa n le toca votar al n-esimo senador llamado a
votar.

Estado: Sn = (Sn1 , Sn2 , Sn3 )

• Sn1 = votos registrados a favor de la confirmación justo antes que vote el n-esimo
senador

• Sn2 = cuantos de sus empleadores quedan por votar

• Sn3 = cuantos votos han dado sus empleadores a la opción de confirmación.

Decisión: 
1 si voto va para opción de confirmar
Xn =
0 ∼ .

Notar que la variable de decisión solo es relevante en el caso que el siguiente en votar es

38
 uno de los empleadores.

Incertidumbre:

1 si le toca votar a un senador de los empleadores
Wn =
0 ∼ .


1 si el voto n-esimo va para la opción de confirmar
Zn =
0 ∼ .

2
Sn
Notar que Wn se distribuye Bernoulli con parámetro M −n+1 , y que Zn se distribuye Ber-
noulli con parámetro p, pero solo es relevante en el caso que el voto no es dado por un
empleador.

Recurrencia:

1
Sn+1 = Sn1 + Wn Xn + (1 − Wn )Zn
2
Sn+1 = Sn1 − Wn
3
Sn+1 = Sn3 + Wn xn .

Bellman:

Jn (Sn ) = máx E {Jn+1 (Sn+1 )} .

Xn ∈{0,1}

Condición de borde:

3 1 3 1


JN +1 (SN +1 ) = SN +1 1{SN +1 > M/2} + N − SN +1 1{SN +1 < M/2}

S1 = (0, N, 0).

Solución #2. La siguiente es una forma alternativa de modelar el problema. Su ventaja es que
no requiere definir aleatoriedad ni decisión, ni tampoco recurrencia de estados, dado que todas
estas componentes se explicitan en la ecuación de Bellman:

Etapas: las ocasiones de voto: en la etapa n le toca votar al n-esimo senador llamado a
votar.

Estado: Sn = (Sn1 , Sn2 , Sn3 )

• Sn1 = votos registrados a favor de la confirmación justo antes que vote el n-esimo
senador

• Sn2 = cuantos de sus empleadores quedan por votar

• Sn3 = cuantos votos han dado sus empleadores a la opción de confirmación.

39
 Bellman:
Sn2
 
p Jn+1 (Sn1 + 1, Sn2 , Sn3 ) + (1 − p) Jn+1 (Sn1 , Sn2 , Sn3 )


Jn (Sn ) = 1−
M −n+1
Sn2
 
máx Jn+1 (Sn1 + 1, Sn2 − 1, Sn3 + 1), Jn+1 (Sn1 , Sn2 − 1, Sn3 ) .

+
M −n+1

Condición de borde:

3 1 3 1


JN +1 (SN +1 ) = SN +1 1{SN +1 > M/2} + N − SN +1 1{SN +1 < M/2}

S1 = (0, N, 0).

Pregunta 2.4. Examen Otoño - 2019

Usted se dispone a disputar la final mundial de Cachipún competitivo. La final consiste una
serie de juegos, donde usted y su rival, simultáneamente eligen y muestran un símbolo de
piedra (r), papel (p) o tijera (s). Las reglas de cada juego son: p vence a r, r vence a s, y s
vence a p. Si ambos jugadores despliegan el mismo símbolo, el juego termina en empate. La
serie de juegos termina cuando usted o su rival alcanzan un total de N juegos ganados.

Su rival en la final es Boris, quien adopta una estrategia de juego Markoviana: la secuencia
de símbolos que muestra forma una cadena de Markov en tiempo discreto, caracterizada por
una matriz de transición P y una distribución inicial π0 .
1. Muestre que la política (“greedy”) que maximiza la probabilidad de ganar cada juego
(ej. partir jugando p en el primer juego), sin considerar el futuro, no es óptima para el
caso N = 2, π0 = (0,7, 0,2, 0,1) y
 
1 0 0
 
P =
 0 1 0 .

1/3 1/3 1/3

(Hint: muestre que la probabilidad de ganar la final es estrictamente menor que uno en
ese caso, y que existe otra política que gana la final con probabilidad 1.)

1. Plantee un modelo de programación dinámica estocástica que permita maximizar la

probabilidad de ganar la final.

Solución parte 1. Jugando primero papel, existe la posibilidad que Boris juegue tijera, lo que
lo dejaría con ventaja de un juego, y después, la probabilidad de que Boris gane la final es un
tercio, independiente de lo que decidamos mostrar. Por lo tanto, la probabilidad de ganar la fina
les estrictamente menor a 1.

Si jugamos primero piedra, pueden pasar 3 cosas. Primero, si Boris juega piedra o papel, no-
sotros podremos anticipar con seguridad sus jugadas en el futuro, por lo tanto le ganamos con

40
probabilidad 1. Si Boris juega tijeras, le ganamos, quedamos con ventaja, y en la próxima ron-
da nuevamente jugamos piedra, y el ciclo se repite (si ganamos, la final terminar, si perdemos,
podemos anticipar todas las jugadas futuras de Boris, y le ganamos con probabilidad 1).

Plantee un modelo de programación dinámica estocástica que permita maximizar la probabilidad

de ganar la final.

Solución parte 2.

Etapas. Cada uno de los juegos, indexados por n

Decisión. xn ∈ {r, p, s}: símbolo a mostrar en el juego n.

Estado. yn : símbolo mostrado por Boris en el juego n − 1; (y1,n , y2,n ) : par ordenado con
el número acumulado de victorias propias y de Boris, respectivamente.

Aleatoriedad. wn : símbolo mostrado por Boris en el juego n.

P(wn+1 = i|wn = j) = Pi,j , n ≥ 1 P(w1 = i) = π0 (i).

Recurrencia. yn+1 = wn ;
 
z1,n + 1 si gano juego n z2,n + 1 si Boris gana juego n
z1,n+1 = z2,n+1 =
z
1,n∼ z
2,n ∼

Bellman.

J(yn , (z1,n , z2,n )) = máx{Ewn {J(yn+1 , zn+1 )}}, z1,n , z2,n < N
xn
J(yn , (N, z2,n ))) = 1, z2,n < N
J(yn , ((z1,n , N ))) = 0, z1,n < N.

Pregunta 2.5. Examen - Primavera 2019

Boris recibió como regalo una versión generalizada del juego del gato: se juega sobre un tablero
de N × N celdas (N filas y N columnas), las cuales son marcadas una a una y de manera
alternada por ambos jugadores, cada uno con un símbolo diferente al de su rival, hasta que
uno de ellos haya marcado k celdas contiguas dentro de una misma fila, una misma columna,
o incluso en diagonal. El primero en lograr esto, gana. Una celda que ya ha sido marcada no
puede volver a ser marcada por ninguno de los dos jugadores.

Boris desea desafiar a su mejor amigo, a quien conoce tan bien que considera saber exacta-
mente qué casillero marcaría éste ante cualquier escenario posible. Proponga un modelo de
programación dinámica mediante el cual Boris pueda decidir si comenzar o ceder el primer
turno, suponiendo que solamente valora ganar.

41
Solución. En la jugada n de Boris, el estado es un par ordenado (Sbn , San ) donde Sbn es el conjunto
de casillas marcadas por Boris y San son las casillas marcadas por su amigo, antes de la jugada
n. La decisión de Boris es que casilla jugar.

Respecto al conocimiento de Boris acerca su amigo, supondremos que conocemos una función
f (Sb , Sa ) que entrega la casilla que marca el amigo cuando se enfrenta al estado (Sb , Sa ). Su-
pondremos que esta función entrega el conjunto vacío si el juego ya ha terminado en el estado
(Sb , Sa ).

Finalmente definimos el conjunto de estados B como aquellos en los cuales Boris gana el juego,
y C el conjunto de estados donde el juego aun no termina. Con esto, el modelo es

Período: n, la jugada de Boris.

Estado: (Sbn , San ), las casillas marcadas antes de n por Boris y su amigo.

Decision: xn , la casilla que Boris marca en la jugada n.

Recursión: (Sbn+1 , San+1 ) = (Sbn ∪ xn , San ∪ f (Sbn ∪ xn , San )).

Ecuación de Bellman:

Jn (Sbn , San ) = 1{(Sbn , San ) ∈ B} + {1{(Sbn , San ) ∈ C} máx Jn+1 (Sbn+1 , San+1 ).
xn ∈(Sbn ∪San )c

Para ver si le conviene partir a Boris simplemente comparamos J1 (∅, ∅) con J1 (∅, f (∅, ∅)). Si
ambos son 0, entonces concluimos que el juego siempre concluye en empate (piense en el caso de
N = 3). Si J1 (∅, ∅) = 1 entonces escogemos partir; si J1 (∅, f (∅, ∅)) = 1 escogemos que parta el
amigo; si ambas son positivas, el amigo no cacha mucho como jugar, le ganamos siempre.

Obs: Notar que no necesitamos indexar las funciones usando n, dado que esto esta implícito en
las cardinalidades de los conjuntos Sb y Sa .

Pregunta 2.6. Control 1 - Primavera 2021

En el contexto de la pandemia, considere la política de testeo grupal de dos etapas, bajo la

cual las muestras nasofaríngeas de un grupo de k individuos son mezcladas y sometidas a un
examen PCR: si el examen resulta negativo, se concluye que cada uno de los k individuos no
están infectados con SARS-CoV-2, por lo que son dados de alta; si el resultado es positivo,
se concluye que al menos un individuo se encuentra contagiado, por lo que se testea a los k
individuos con k exámenes PCR individuales, los individuos que arrojan un resultado negativo
son dados de alta, el resto es derivado a personal de salud. En resumen, cuando se testea un
grupo de tamaño k mediante testeo grupal de dos etapas, un resultado negativo al examen
grupal requiere tan solo un examen PCR para diagnosticar a todo el grupo, y un resultado
positivo requiere k + 1 examenes PCR para diagnosticar a todo el grupo.

En esta pregunta usted esta a cargo de testear a un total de K individuos utilizando la

política de testeo grupal de dos etapas. Para esto usted puede formar sub-grupos de individuos

42
 cualquier tamaño, y testear dichos subgrupos de forma grupal siguiendo la política descrita en
el párrafo anterior. Para su beneficio, usted puede testear los sub-grupos de forma secuencial,
por lo que al momento de decidir el tamaño del subgrupo n + 1 de individuos a testear, usted
ya cuenta con el diagnostico de cada uno de los individuos pertenecientes a los n sub-grupos
anteriores.

Respecto a la prevalencia de SARS-CoV-2 en la población, supondremos cada uno de los K

individuos se encuentra contagiado con probabilidad P , independiente del resto, y que el test
PCR es perfecto: no existen falsos positivos ni falsos negativos, de forma que cada persona
contagiada testea positivo, y cada persona no contagiado testea negativo. Sin embargo, debido
a falta de información previa, usted no conoce el valor de P , por lo que supondrá que P es
una variable aleatoria distribuida U [0, 1].

Plantee el problema de minimizar el numero esperado de exámenes PCR necesarios para

diagnosticar a toda la población (K individuos). Para esto:

a) Muestre que si P ∼ Beta(α, β), y si condicional en {P = p}, X ∼ Binom(k, p), entonces

P |{X = i} ∼ Beta(α + i, β + k − i), 0 ≤ i ≤ k.

Nota: decimos que Z ∼ Beta(α, β) si la función de densidad f (z) de Z es tal que

f (z) = B(α, β)−1 z α−1 (1 − z)β−1 , z ∈ [0, 1],

donde B(·, ·) denota la función Beta.

b) Utilice lo anterior para mostrar que condicional en el resultado de los primeros I in-
dividuos diagnosticados, P se distribuye Beta(1 + i, 1 + I − i), donde i representa el
número de individuos (entre estos I totales) diagnosticados con el virus.

c) Calcule P(X = i) cuando X|{P = p} ∼ Binom(k, p), y P ∼ Beta(α, β).

d) Entregue una formulación de programación dinámica del problema.

e) Suponga ahora que usted tan solo cuenta con presupuesto para realizar a lo más Q
exámenes PCR: modifique su formulación para maximizar la probabilidad de alcanzar
a diagnosticar a toda la población.

Solución parte a) Sea fi (·) la densidad de P condicional en X = i. Utilizando Bayes, tenemos

que
P(X = i|P = p)f (p)
fi (p) =
P(X = i)
 
k i
∝ p (1 − p)k−i · pα−1 (1 − p)β−1
i
∝ pα+i−1 (1 − p)β+k−i−1 .

Concluimos que fi (·) es la densidad de una variable aleatoria distribuida Beta(α + i, β + k − i).

43
Solución parte b) Notamos que la distribución uniforme (0, 1) corresponde a una distribución
Beta con parámetros α = 1 y β = 1. Notamos además que condicional en la prevalencia P = p, el
número de individuos diagnosticados con el virus entre los primeros I individuos diagnosticados
distribuye Binomial(p, I). El resultado entonces sigue de la aplicación directa del resultado en
la parte a).

Solución parte c) Utilizando probabilidades totales, tenemos que

ˆ p
−1
P(X = i) = B(α, β) P(X = i|P = p)pα−1 (1 − p)β−1
0
ˆ p 
−1 k α+i−1
= B(α, β) p (1 − p)β+k−i−1
0 i
 
B(α + i, β + k − i) k
= .
B(α, β) i

Solución parte d)

Periodos: (n) - un periodo comienza cuando definimos el tamaño del próximo subgrupo a
testear, y termina cuando recibimos el diagnostico de dicho grupo.

Decisión: (kn ) - el tamaño del n-esimo subgrupo a testear.

Estado: (Kn , In ) - el número de individuos diagnosticados antes del comienzo del período
n, y el número de individuos diagnosticados con el virus antes del comienzo del período n.

Incertidumbre: wn - el número de individuos diagnosticados con el virus durante el período

n.

Recursión de estado:
Kn+1 = Kn + kn , In+1 = In + wn .

Bellman: definiendo  
α,β B(α + i, β + k − i) k
qk,i := ,
B(α, β) i
tenemos que Bellman toma la siguiente forma:
kn
( )
 
1+In ,1+Kn 1+In ,1+Kn
X
Jn (Kn , In ) = máx 1 + 1 − qkn ,0 kn + qkn ,i Jn+1 (Kn + kn , Ii + i) .
1≤kn ≤K−Kn
i=0

Condición de borde:
Jn (K, ·) = 0, ∀ n.

Solución parte e)

Periodos: (n) - un periodo comienza cuando definimos el tamaño del próximo subgrupo a
testear, y termina cuando recibimos el diagnostico de dicho grupo.

Decisión: (kn ) - el tamaño del n-esimo subgrupo a testear.

44
 Estado: (Kn , In , Qn ) - el número de individuos diagnosticados antes del comienzo del pe-
ríodo n, el número de individuos diagnosticados con el virus antes del comienzo del período
n, y el número de tests utilizados para diagnosticar a los individuos antes del comienzo del
período n.

Incertidumbre: wn - el número de individuos diagnosticados con el virus durante el período

n.

Recursión de estado:

Kn+1 = Kn + kn , In+1 = In + wn , Qn+1 = Qn + 1 + kn · 1{wn > 0}.

Bellman: definiendo  
α,β B(α + i, β + k − i) k
qk,i
:= ,
B(α, β) i
tenemos que Bellman toma la siguiente forma:
(k )
n

qk1+I n ,1+Kn
X
Jn (Kn , In , Qn ) = máx n ,i
Jn+1 (Kn + kn , Ii + i, Qn + 1 + kn 1{i > 0}) .
kn ≤K−Kn
i=0

Condición de borde:

1 Qn ≤ Q
Jn (K, In , Qn ) = ∀ n.
0 ∼

Pregunta 2.7. Examen - Primavera 2021

Considere el comportamiento de un turista que desea conocer el metro de Santiago. Partiendo

desde una estación dada (e.j. Los Héroes), este turista desea visitar todas las estaciones de la
red de metro en el menor tiempo posible. Para esto, considere que el tiempo de viaje entre
las estaciones i y j, adyacentes en la red de metro, esta dado por ti,j . Plantee un modelo de
programación dinámica que permita al turista planificar sus acciones.

Solución. Suponemos que la red de metro consiste en un grafo dirigido G = (N, A).

Períodos: No necesitamos especificar periodos.

Estado: (S, i), donde S representa el conjunto de estaciones que ya han sido visitadas, y i
representa la ubicación actual del turista.

Decisión: j, el siguiente destino del turista. Notar que j ∈ {h ∈ N : (i, h) ∈ A}.

Recurrencia de estado: (S, i) → (S ∪ {j}, j)

Bellman:

V (S, i) = máx {ti,j + V (S ∪ {j}, j)}, ∀ S ⊂ N, i ∈ N

j:(i,j)∈A
V (N, i) = 0, ∀ i ∈ N.

45
 Pregunta 2.8. Control 1 - Otoño 2022

Usted está a cargo de construir la estrategia de paradas a Pit de un piloto de Formula 1. Al

comienzo de cada una de las vueltas, los pilotos deben decidir si pasar o no a Pit a cambiar
neumáticos. Consideraremos que existen tres tipos de neumáticos: duros, medios, y blandos.

El tiempo que demora un piloto en dar una vuelta al circuito utilizando un neumático tipo
i depende del número de vueltas que ya se han completado utilizando ese neumático (el
cual sirve como un proxy del porcentaje de desgaste del neumático): si el número de vueltas
completadas con un neumático es n, entonces el tiempo que demora en completar la siguiente
vuelta es f (i, n). De forma similar, realizar una vuelta con neumáticos usados en las n vueltas
previas resulta en una ruptura de algún neumático con probabilidad r(i, n), con lo cual el
piloto debe abandonar la carrera (y por lo tanto el tiempo de carrera es ∞). Considere que
una parada en Pit suma p segundos al tiempo de la vuelta en que se realiza la parada.

Al comienzo de cada una de las N vueltas de la próxima carrera, usted debe decidir si pasar
o no a Pit. Para esto considere que por regla, cada piloto debe utilizar por lo menos dos
tipos de neumáticos diferentes en cada carrera (es decir, no es valido usar el mismo tipo de
neumático toda la carrera, independiente de cuantas veces se entre a Pit). Adicionalmente
asuma que la entrada y salida de Pit se encuentran inmediatamente después de la linea de
meta.

Formule un problema de programación dinámica que maximice la probabilidad de terminar

la carrera en menos de T segundos.

Solución. En esta formulación asumiremos que el pinchazo de neumáticos termina la carrera

inmediatamente, asignando un tiempo de carrera mayor a T . Esto se verá reflejado en la ecuación
de Bellman.

Períodos: Las N vueltas de la carrera, indexadas por n.

Decisión: (x1n , x2n ) donde

• x1n = 1 si se entra a pit al comienzo de la vuelta n, x1n = 0 de otra forma, y

• x2n ∈ {duro, medio, blando} es el tipo de neumático a utilizar, si es que se entra a pit.

Estado: (Sn1 , Sn2 , Sn3 , Sn4 ) donde

• Sn1 es el tipo de neumático utilizado para dar la vuelta n − 1,

• Sn2 es el número de vueltas que se han completado con dichos neumáticos,

• Sn3 = 1 si ya se utilizo más de un tipo de neumático, Sn3 = 0 de otra forma, y

• Sn4 es el tiempo de carrera al comienzo de la vuelta n.

Incertidumbre: Wn = 1 si se pincha un neumático durante la vuelta n, Wn = 0 de otra

46
 forma. (No es necesario definirla en esta formulación, esto se ve directamente en la ecuación
de Bellman)

Recursión de estado:
 
1
x2
n si x1n =1 2
1 si x1n = 1
Sn+1 = , Sn+1 = ,
S 1 ∼ S 2 + 1 ∼
n n

3
1 si x1n = 1 ∩ x2n ̸= Sn1 4
Sn+1 = , Sn+1 = Sn4 + p · x1n + f (Sn+1
1 2
, Sn+1 − 1).
S 3 ∼
n

Bellman:
1 2


Vn (Sn ) = máx{ 1 − r(Sn+1 , Sn+1 − 1) Vn+1 (Sn+1 )}.
xn

Condición de borde:
4 3
VN +1 (SN +1 ) = 1{SN +1 ≤ T ∩ SN +1 = 1}.

Pregunta 2.9. Examen - Otoño 2022

Considere el problema del vendedor viajero, donde un vendedor debe decidir el orden en el
que se deben recorrer N ciudades de forma de minimizar la distancia total recorrida. Como
restricción el viajero parte y termina su recorrido en una ciudad fija (arbitraria). Defina di,j
como la distancia entre las ciudades i y j.

a) Plantee una formulación de programación dinámica del problema.

Suponga adicionalmente que el tiempo de viaje entre las ciudades i y j es aleatorio y distri-
buido de acuerdo a Fi,j .

b) Plantee una formulación de programación dinámica para encontrar el itinerario (adap-

tativo) que maximiza la probabilidad de terminar el recorrido en menos de T horas.

Solución parte a).

Períodos: n ∈ {1, . . . , N − 1}, equivalente al número de ciudades visitadas

Estado: Sn , ciudades que faltan visitar; in , cuidad donde está el vendedor.

Decisión: sn siguiente ciudad a visitar.

Transición: Sn+1 = Sn \ {sn }; in+1 = sn .

Bellman y condición de borde:

Vn (Sn , in ) = mı́n {din ,sn + Vn+1 (Sn \ {sn }, sn )}

sn ∈Sn
VN (SN , iN ) = diN ,i1 .

Notar que i1 es fija y/o arbitraria, y S1 = N \ {i1 }.

47
Solución parte b).

Períodos: n ∈ {1, . . . , N − 1}, equivalente al número de ciudades visitadas

Estado: Sn , ciudades que faltan visitar; in , cuidad donde está el vendedor; tn , tiempo que
resta para terminar el recorrido.

Decisión: sn siguiente ciudad a visitar.

Incertidumbre: τi,j ∼ Fi,j , tiempo que demora recorrer tramo (i, j).

Transición: Sn+1 = Sn \ {sn }; in+1 = sn ; tn+1 = tn − τin ,sn .

Bellman y condición de borde:

Vn (Sn , in , tn ) = máx {E[Vn+1 (Sn \ {sn }, sn , tn − τin ,sn )]}

sn ∈Sn
VN (SN , iN ) = P(τiN,1 ≤ tN ).

Notar que i1 es fija y/o arbitraria, S1 = N \ {i1 }, y t1 = T .

Pregunta 2.10. Control 1 - Primavera 2023

En un consultorio no muy lejos de aquí, en una sala de espera se encuentran N pacientes, a

quienes enumeramos desde el 1 al N de acuerdo a su orden de llegada. Estos pacientes deben
ser atendidos por un único médico, y recae en usted el decidir en que orden serán atendidos
los pacientes. Para esto, considere que el paciente i necesita un tiempo ti en ser atendido,
y que una vez atendido, este deja el consultorio de forma inmediata. Usted esta interesado
en minimizar el tiempo total de espera de los pacientes (es decir, la suma de los tiempos de
espera individuales de todos los pacientes). Sin embargo, cada vez que usted decide comenzar
a atender a un paciente, todo los otros pacientes que llegaron antes y aun no son atendidos
levantan un reclamo formal frente a la autoridad. Por otro lado, la autoridad le ha advertido
que en caso que se levanten un total de reclamos mayor a una cota K, usted será despedido.

Formule un modelo de programación dinámica para resolver el problema de decidir el orden

de atención de los pacientes que minimiza el tiempo total de espera sin resultar en su despido

Solución.

Periodos: n = 1 · · · , N : el periodo n comienza justo antes que comience la atención del

n1-esimo paciente en atenderse. Vemos que tendremos N periodos.

Decisión: xn ∈ {1, . . . , N } indica el índice del paciente que se atenderá durante el periodo
n.

Estados: Sn = (bn , Pn ), donde bn representa el número de reclamos presentados previo al

comienzo del periodo n, y Pn ⊆ {1, . . . , N } es el conjunto de pacientes que aun quedan por
atenderse al comienzo del periodo n.

48
 Recurrencia estados: Dados el estado Sn y la decisión xn , tenemos que

Sn+1 = (bn+1 , Pn+1 ) = (bn − |{i ∈ Pn : i < xn }|, Pn \ {xn }).

Bellman:
Vn (Sn ) = mı́n {txn · (N − n) + Vn+1 (Sn+1 )}.
xn ∈Pn

Condición de borde: 
0 bN +1 ≥ 0
VN +1 =
∞ ∼ .

Pregunta 2.11. Control 1 - Otoño 2024

Suponga que Usted está a cargo de la producción y comercialización de un nuevo producto

por las siguientes N semanas.

Al comienzo de cada semana usted decide cuantas unidades del producto fabricar. Considere
que el costo marginal de producir una unidad es c pesos (no existen costos fijos), que los
productos fabricados quedan disponibles de forma inmediata (al comienzo de la semana) en
la fabrica, y que debido a la naturaleza del producto, al cabo de una semana, todo inventario
sin vender se descarta. Tras finalizar la tarea de producción semanal, al inspeccionar los
productos para determinar su calidad, hay una probabilidad p ∈ (0, 1) que un producto
(independiente de todo lo demás) presente fallas. La empresa no vende productos fallidos, y
no produce más productos para reemplazar aquellos con fallas.

En términos comerciales, la demanda por el producto durante la semana n es Dn . Sin embargo,

usted puede decidir gastar parte de su presupuesto en publicidad, lo que aumenta la demanda.
En particular, se sabe que por cada peso que se gasta en publicidad durante una semana, la
demanda esa semana aumenta en d unidades. Suponga finalmente que el precio (unitario) de
venta del producto es r.

a) Plantee un modelo de programación dinámica que le ayuda a maximizar los ingresos

acumulados por concepto de ventas durante el horizonte de planificación, suponiendo
que su presupuesto total de operación total para gastar en producción y publicidad es
de B pesos.

Suponga ahora que la operación producción y comercialización se mantiene de forma indefi-

nida, que el presupuesto semanal de operación es de ∆ pesos que se puede acumular entre
semanas (partiendo desde el presupuesto inicial B) pero nunca puede ser negativo, y que
en cada semana existe una probabilidad α ∈ (0, 1) que la dirección de la empresa decida
descontinua el producto de forma irrevocable.

b) Plantee un modelo de programación dinámica que le ayuda a tomar las decisiones de

producción y publicidad mientras el producto se encuentra vigente.

49
Solución parte a)

Etapas: N semanas.

Variables de decisión. Pn : productos a producir en semana n, y Mn : cantidad a invertir

en marketing en semana n.

Estado. Kn : presupuesto disponible al inicio de semana n.

Incertidumbre. wn : productos defectuosos de la producción de semana n.

wn ∼ Binomial(Pn , p).

Recurrencia de estado: Kn+1 = Kn − c Pn − Mn .

Función Objetivo:

Vn (Kn ) = máx {E[r(mı́n{Dn + d Mn , Pn − wn }) + Vn+1 (Kn+1 )]} n = 1, 2, ..., N.

Pn , M n

Restricción: c Pn + Mn ≤ Kn .

Casos borde:
K1 = B, VN +1 (KN +1 ) = 0.

Solución parte b) Supondremos que la demanda tiene la misma distribución todas las sema-
nas.

Variables de decisión. P : producto a producir al comienzo de la semana, y M : cantidad

a invertir en marketing durante la semana.

Estado. K: presupuesto disponible al inicio de la semana.

Incertidumbre: w: tarros de defectuosos de la producción de la semana.

w ∼ Binomial(P, p).

Recurrencia de estado:
K ′ = K + ∆ − c P + M.

Función Objetivo:

V (K) = máx{E[r(mı́n{D + dM, P − w}) + (1 − α)V (K ′ )]}.

P,M

Restricción: 0 ≤ c P + M ≤ K.

50
 Pregunta 2.12. Examen - Otoño 2024

Usted cuenta con N unidades de un producto que puede vender a clientes que llegan a su
tienda durante los próximos T días. Cada día un cliente visita la tienda, e independiente de
todo, compra una unidad del producto con probabilidad f (p), donde p es el precio ofrecido
al cliente. Al comienzo de cada día usted debe escoger que precio cobrar por el producto,
entendiendo que solo existen dos precios posibles (p1 y p2 , donde p1 ̸= p2 ). Plantee un modelo
de programación dinámica que maximice la ganancia obtenida por la venta de productos,
considerando que durante el horizonte de planificación solamente se puede cambiar el precio
de un día al siguiente en a lo más C oportunidades.

Solución.

Periodos. Cada día, desde t = 1 hasta t = T .

Estado. St = (Nt , Ct , Pt−1 ) donde Nt representa el número de unidades del producto

disponibles al comienzo del periodo t, y Ct es el número de veces que se ha cambiado el
precio hasta el comienzo del periodo t, y Pt−1 es el precio utilizado en el periodo t − 1.

Decisión. Pt ∈ {p1 , p2 } el precio a cobrar durante el periodo t.

Incertidumbre. Sea Dt la demanda durante el periodo t, entonces,


1 con prob. f (Pt )
Dt =
0 ∼

Recursiones.
Nt+1 = Nt − Dt , Ct+1 = Ct + 1{Pt ̸= Pt−1 }.

Bellman.

Vt (St ) = máx {Pt · f (Pt ) + f (Pt )Vt+1 (Nt − 1, Ct+1 , Pt ) + (1 − f (Pt )Vt+1 (Nt , Ct+1 , Pt−1 ))} .
Pt ∈{p1 ,p2 }

Condiciones de borde.

• Vt (0, Ct , Pt−1 ) = 0, con N1 = N ,

• Vt (Nt , C + 1, Pt−1 ) = −∞, con C1 = −1 y P0 ∈

/ {p1 , p2 }.

• V (NT +1 , CT +1 , PT ) = 0.

51