Programación Dinámica 2
Ingeniería Industrial y
de Sistemas
Problema original
¿Cumple principio de optimalidad de Bellman?
x0 Fn xn
t = t0 desconocida t= tn
xn = Fn (x0)
Aplicamos el principio
de descomposición:
Donde
cada etapa: Finalmente, se resuelve en una secuencia recursiva que parte en el vector de salida
y termina en el vector de entrada del problema original
Dn Dn-1 Dk D2 D1
xn xn-1 xn-2 xk xk-1 x2 x1 x0
fn fn-1 fk f2 f1
Rk = rk(xk-1 , Dk) Rn Rn-1 Rk R2 R1
entrada
salida
…buscando optimizar la función recursiva: gn(x0) = Opt D1,D2, …,Dn [R1*R2*…*Rn]
Sujeto a: XK = fK (XK-1, DK) K = 1, 2, ……., n
Universidad de Piura
Para todos los problemas,
se puede obtener una tabla
como la siguiente para cada etapa n
Universidad de Piura
Tipos de problemas de Programación Dinámica
Un problema usual de programación dinámica es el de distribución o asignación de
recursos o esfuerzos entre un conjunto de actividades alternativas. Cada actividad
lleva asociada una medida relacionada con un coste o beneficio, que es la
magnitud que se buscaría optimizar en al repartir del recurso
Algunos ejemplos:
❑Distribución de capital entre inversiones alternativas
❑Distribución de fuerza de trabajo entre varias tareas o áreas
❑Distribución de un presupuesto entre varias partidas de gasto
❑Distribución de tiempo entre varias actividades
Universidad de Piura
Ejemplo de distribución de capital
Un inversionista tiene $6000 para invertir en tres
acciones. Se puede invertir en unidades de $1000. El
retorno potencial a partir de la inversión en
cualquier acción depende de la cantidad invertida
con base en a la siguiente tabla:
Cantidad invertida Retorno potencial en miles $
A B C
Si tengo que invertir todo mi capital: 0 0 0 0
1 0.5 1.5 1.2
2 1.0 2.0 2.4
a) ¿Cuál sería el retorno potencial máximo 3 3.0 2.2 2.5
4 3.1 2.3 2.6
de mi inversión? 5 3.2 2.4 2.7
a) ¿Cuánto invertiría y en que acciones? 6 3.3 2.5 2.8
Universidad de Piura
Ejemplo de planificación
Una empresa sabe que la demanda de su producto durante cada uno de los 4
siguientes meses será: 1, 3, 2 y 4 unidades. Al principio de cada mes la empresa
debe determinar cuánto se debe producir para ese mes. Cada mes que hay
producción se incurre en un costo de preparación de $3. El costo por cada unidad
producida es de $1. Al final de cada mes se incurre en un costo de $0.50 por cada
unidad en inventario. Las limitaciones de capacidad permiten la producción de un
máximo de 5 unidades cada mes. El tamaño de los almacenes de la empresa
restringe el inventario final de cada mes a 4 unidades como máximo.
La empresa desea determinar un calendario de producción para cada mes, de tal
manera que se cumpla a tiempo con las demandas y se reduzca al mínimo los
costos totales durante los 4 meses. Se asume que el inventario inicial y final es
cero
Universidad de Piura
Universidad de Piura
