INVESTIGACIÓN DE OPERACIONES
Grupo 2
Diego Andrés Romero Blanco - 20161020114
Kevin Fernando Rocha Santamaría - 20161020086
Brandon Steven Henríquez -20152020056
EJERCICIO TÍPICO PROGRAMACIÓN DINÁMICA PROBABILÍSTICA (PDP)
Objetivo: Analizar y explicar paso por paso un problema típico de programación dinámica
probabilística.
Enunciado:
Usted tiene $ 5.000 para invertir y tiene la oportunidad de hacerlo en cualquiera de dos opciones de
inversión (A o B), al principio de cada uno de los próximos años. Existe incertidumbre respecto al
rendimiento de ambas inversiones. Si se invierte en A, se puede perder todo el dinero o (con
probabilidad más alta) obtener $10.000 (una ganancia de $ 5.000) al final del año. Si se invierte en
B, se pueden obtener los mismos $5.000 o (con probabilidad más baja) $10.000 al terminar el año.
Las probabilidades para estos eventos son las siguientes:
Inversión Cantidad obtenida ($) Probabilidad
A 0 0.3
10000 0.7
B 5000 0.9
10000 0.1
Se le permite hacer (a lo sumo) una inversión al año y sólo puede invertir $5000 cada vez. (Cualquier
cantidad de dinero acumulada queda inútil).
● Utilice programación dinámica para encontrar la política de inversión que maximice la cantidad
de dinero esperada que tendrá después de los tres años.
Conceptos clave:
La programación dinámica probabilística (PDP) es una técnica matemática útil para la toma de
decisiones interrelacionadas, se presenta cuando el estado en la siguiente etapa no está
determinado por completo por el estado y la política de decisión de la etapa actual. En su lugar existe
una distribución de probabilidad para determinar cuál será el siguiente estado. Sin embargo, esta
distribución de probabilidad sí queda bien determinada por el estado y la política de decisión en la
etapa actual. Por otro lado, cabe resaltar, qué; cuando el estado en la siguiente etapa está
determinado por completo por el estado y la política de decisión de la etapa actual, entonces este
problema corresponde a programación dinámica determinística (PDD).
A continuación, se ilustra la estructura básica de la PDP:
En la Programación dinámica (Sea PDD ó PDP), se utiliza una relación recursiva que identifica la
política óptima para la etapa n, dada la política óptima para la etapa n + 1. La forma precisa de la
relación recursiva difiere de un problema a otro de PD (Sea PDD ó PDP).
Para explicar lo anterior, con relación a la ilustración de la PDP, se supone que el objetivo es
minimizar la suma esperada de las contribuciones de las etapas individuales.
En consecuencia:
Donde la minimización se toma sobre todos los valores factibles de xn+1.
Solución:
Pasos Procedimiento
● Sea Xn la inversión realizada en el año nj, esto es, Xn = 0, A, B.
1. Definir las
● Sea Sn la cantidad de dinero en la mano al inicio del año.
variables a
● Sea fn(Sn,Xn) la cantidad máxima prevista de dinero al final del
utilizar.
tercer año, dado Sn y Xn en el año n.
2. Definir
restricciones
necesarias.
En cada etapa debemos identificar los posibles casos de Sn.
En donde para la primera etapa (tercer año de inversión), puede ser que
tenga entre $0 y $5000, o más de $5000, posteriormente,
basándonos en las restricciones del paso 2, debemos hallar el valor de
f*n(Sn), que para Sn:
● 0 ≤ S3 ≤ 5000, f*3(S3) = S3, que sería la misma cantidad que tiene
para invertir en ese año, ya que este sería en caso de no invertir en
ninguna opción es decir x*3 = 0.
● Para el caso S3 ≥ 5000, f*3(S3) = S3 + (0.3(-5000) + 0.7(5000))
lo cual daría que f*3(S3) = S3 + (-1500 + 3500) = S3 + 2000, que
sería el caso de invertir en la opción A donde x*3 = A.
3. Comenzar el
procedimiento de
cada etapa,
iniciando con la
última.
4. Plantear la
solución del
Así, la política óptima es invertir siempre en A, con una fortuna de
problema
espera después de tres años de $ 9800.
teniendo en
cuenta las etapas.
Conclusión:
La programación dinámica probabilística es una técnica muy útil para tomar una serie de decisiones
interrelacionadas. Requiere la formulación de una relación recursiva apropiada para cada problema
individual. Sin embargo, proporciona grandes ahorros computacionales en comparación con la
enumeración exhaustiva para encontrar la mejor combinación de decisiones, en especial cuando se
trata de problemas grandes.
BIBLIOGRAFÍA:
Ejercicio propuesto 11.4-2 del libro Investigación de operaciones - Hiller, Frederick S. Lieberman,
Gerald J.
