Programación Dinámica
Problema de Inversión
Hernandez Leyva Diego Antonio
Ledesma García Alejandro
Ramírez Reséndiz Cecilia
Reyes Maya Karla
La programación dinámica es una técnica matemática que se
utiliza para la solución de problemas en los cuales se toma una
serie de decisiones en forma secuencial.
El matemático Richard
Bellman inventó la
programación dinámica
en 1953.
CONCEPTOS.
La programación dinámica es un enfoque general para la solución de problemas en los que es
necesario tomar decisiones en etapas sucesivas. Las decisiones tomadas en una etapa condicionan
la evolución futura del sistema, afectando a las situaciones en las que el sistema se encontrará
en el futuro, y por tanto a las decisiones que se tomarán.
Etapa: Son las subdivisiones del problema general. Estos subproblemas poseen un conjunto de
alternativas mutuamente excluyentes; de las cuales se seleccionará la mejor alternativa.
Estado: es el que refleja la condición o estado de
las restricciones que enlazan las etapas.
Representa el enlace entre etapas: así cuando cada
etapa se optimiza por separado la decisión
resultante es automáticamente factible para el
problema completo.
SUSTENTO.
Para resolver un problema complejo se tiende a dividir este en
subproblemas. Esto se sustenta en el PRINCIPIO DE OPTIMALIDAD que
sugiere que existe una solución adecuada para el problema si se puede
resolver cada subproblema utilizando cálculos recursivos
Independientemente de las decisiones tomadas para llegar a un
estado particular, en una etapa particular, las decisiones restantes
deben constituir una vía óptima para poder cambiar ese estado
NO calcular dos veces lo mismo, sino en utilizar tablas o registro de
resultados, los cuales se van rellenando a medida que se resuelven los
subproblemas, anotando las decisiones y el Estado al que este nos
lleva.
CARACTERÍSTICAS.
Los problemas que se resuelven con Programación
dinámica se pueden dividir en etapas
(Subproblemas). Las cuales requieren una solución
optima (Política) 𝒙𝒊
Cada una de estas etapas tiene cierto número de estados asociados 𝒒𝒊 a ella, las cuales se
relacionan directamente con las posibles soluciones. 𝒙𝒊
El objetivo de la política de decisión en cada etapa es:
transformar el estado actual en un estado asociado
con la siguiente etapa.
CARACTERÍSTICAS.
Es un método ascendente recursivo. Se resuelven
primero los subproblemas más pequeños. Combinando
las soluciones se obtienen las soluciones del problema
inmediato anterior hasta llegar al ejemplar original. El
procedimiento de solución se inicia al encontrar el optimo
de la última etapa
A diferencia de la programación lineal, el modelado de
problemas de programación dinámica no sigue una
forma estándar. Por lo que las ecuaciones específicas
que se usan se deben desarrollar para que representen
cada situación individual.
Modelo de inversión
En este grupo de problemas existe sólo una clase de recursos (material, dinero,...) que deben
asignarse a un cierto número de actividades o inversiones. El objetivo es determinar cómo distribuir
el recurso entre las actividades de la manera más efectiva.
Definimos:
𝑏 : inversión total.
𝑢: variable de estado.
𝑓(𝑥𝑖 ): ganancia al invertir 𝑥𝑖 .
𝑚𝑗 (𝑢): rendimiento optimo en etapa j en estado 𝑢.
𝑑𝑗 (𝑢): decisión en etapa j en estado 𝑢
Entonces para la etapa N, se tiene.
𝑚𝑁 𝑢 = max 𝑓𝑁 (𝑥) con 𝑢 = 0: 𝑏
0≤𝑥≤𝑢
Para las 𝑁 − 1 etapas restantes.
𝑚𝑗 𝑢 = max 𝑓𝑗 𝑥 + 𝑚𝑗+1 (𝑢 − 𝑥) con 𝑢 = 0: 𝑏
0≤𝑥≤𝑢
El valor de 𝑚𝑗 que genere el máx., se toma como 𝑑𝑗 (𝑢) optimo.
Luego la solución optima para el estado, esta dada por
𝑍 ∗ = 𝑚1 (𝑏)
con
𝑥1 = 𝑑1 𝑏
𝑥2 = 𝑑2 𝑏 − 𝑥1
⋮
𝑁−1
𝑥𝑁 = 𝑑𝑁 𝑏 − 𝑥𝑖
𝑖=1
𝒖𝟎 /𝒙𝟎 𝒖𝟏 /𝒙𝟏 𝒖𝟐 /𝒙𝟐 𝒖𝟑 /𝒙𝟑
Etapa 1 𝒇𝟏 (𝒙𝟎 ) 𝒇𝟏 (𝒙𝟏 ) 𝒇𝟏 (𝒙𝟐 ) 𝒇𝟏 (𝒙𝟑 )
Etapa 2 𝒇𝟐 (𝒙𝟎 ) 𝒇𝟐 (𝒙𝟏 ) 𝒇𝟐 (𝒙𝟐 ) 𝒇𝟐 (𝒙𝟑 )
Etapa 3 𝒇𝟑 (𝒙𝟎 ) 𝒇𝟑 (𝒙𝟏 ) 𝒇𝟑 (𝒙𝟐 ) 𝒇𝟑 (𝒙𝟎 )
Problema de inversión
Un inversionista posee $3000 dólares para invertir en tres proyectos diferentes. Cada proyecto
requiere un deposito de $1000 dólares donde podemos colocar el dinero entre los tres
proyectos. El valor presente neto esperado se presenta en la siguiente tabla.
Inversión
E Valor Presente Neto 0 $1000 $2000 $3000
t
a Proyecto 1 0 $1000 $4000 $5000
p
Proyecto 2 0 $3000 $5000 $7000
a
s Proyecto 3 0 $2000 $6000 $8000
Etapa 3
𝑚á𝑥 𝑧 = 𝑓1 𝑥1 + 𝑓2 𝑥2 + 𝑓3 𝑥3 VPN 0 1 2 3
P1 0 1 4 5
𝑠. 𝑎. 𝑥1 + 𝑥2 + 𝑥3 ≤ $3000
P2 0 3 5 7
P3 0 2 6 8
𝒎𝑵 (u)= máx 𝒇𝑵 (𝒙) 0<x<u Valor óptimo Decisiones
𝒎𝟑 (0)= máx 𝒇𝟑 (𝒙𝟎 ) Máx{ 0 } 0 𝒅𝟑 (𝟎)= 0
𝒎𝟑 (1)= máx{𝒇𝟑 (𝒙𝟎 ), 𝒇𝟑 (𝒙𝟏 )} Máx{ 0, 2 } 2 𝒅𝟑 (𝟏)= 1
𝒎𝟑 (2)= máx 𝒇𝟑 (𝒙𝟎 ), 𝒇𝟑 (𝒙𝟏 ), 𝒇𝟑 (𝒙𝟐 ) Máx{ 0, 2, 6 } 6 𝒅𝟑 𝟐 = 2
𝒎𝟑 (3)= máx 𝒇𝟑 (𝒙𝟎 ), 𝒇𝟑 (𝒙𝟏 ), 𝒇𝟑 (𝒙𝟐 ), 𝒇𝟑 (𝒙𝟑 ) Máx{ 0, 2, 6, 8} 8 𝒅𝟑 (𝟑)= 3
Etapa 2
VPN 0 1 2 3 𝒎𝟑 (𝟎) 0
P1 0 1 4 5 𝒎𝟑 (𝟏) 2
P2 0 3 5 7 𝒎𝟑 (𝟐) 6
P3 0 2 6 8 𝒎𝟑 (𝟑) 8
𝒎𝒋 (u)= máx 𝒇𝒋 𝒙 + 𝒎𝒋+𝟏 (𝒖 − 𝒙) 0<x<u Valor Decisiones
óptimo
𝒎𝟐 (0)= máx 𝒇𝟐 𝒙𝟎 + 𝒎𝟑 (𝒖 − 𝒙𝟎 ) Máx{ 0 } 0 𝒅𝟐 (𝟎)= 0
𝒎𝟐 (1)= máx{𝒇𝟐 𝒙𝟎 + 𝒎𝟑 𝒖 − 𝒙𝟎 , 𝒇𝟐 𝒙𝟏 + 𝒎𝟑 (𝒖 − 𝒙𝟏 )} Máx{ 0+2, 3+0 } 3 𝒅𝟐 (𝟏)= 1
𝒎𝟐 (2)= máx{𝒇𝟐 𝒙𝟎 + 𝒎𝟑 𝒖 − 𝒙𝟎 , 𝒇𝟐 𝒙𝟏 + 𝒎𝟑 (𝒖 − 𝒙𝟏 ), 𝒇𝟐 (𝒙𝟐 ) + Máx{ 0+6, 3+2, 5+0 } 6 𝒅𝟐 𝟐 = 0
𝒎𝟐 (3)= máx{𝒇𝟐 𝒙𝟎 + 𝒎𝟑 𝒖 − 𝒙𝟎 , 𝒇𝟐 𝒙𝟏 + 𝒎𝟑 (𝒖 − 𝒙𝟏 ), 𝒇𝟐 (𝒙𝟐 ) + Máx{ 0+8, 3+6, 5+2, 7+0} 9 𝒅𝟐 (𝟑)= 1
Etapa 1
VPN 0 1 2 3 𝒎2 (𝟎) 0
P1 0 1 4 5 𝒎2 (𝟏) 3
P2 0 3 5 7 𝒎2 (𝟐) 6
P3 0 2 6 8 𝒎2 (𝟑) 9
𝒎𝒋 (u)= máx 𝒇𝒋 𝒙 + 𝒎𝒋+𝟏 (𝒖 − 𝒙) 0<x<u Valor Decisiones
óptimo
𝒎𝟏 (0)= máx 𝒇𝟏 𝒙𝟎 + 𝒎𝟐 (𝒖 − 𝒙𝟎 ) Máx{ 0+0 } 0 𝒅𝟏 (𝟎)= 0
𝒎𝟏 (1)= máx{𝒇𝟏 𝒙𝟎 + 𝒎𝟐 𝒖 − 𝒙𝟎 , 𝒇𝟏 𝒙𝟏 + 𝒎𝟐 (𝒖 − 𝒙𝟏 )} Máx{ 0+3, 1+0 } 3 𝒅𝟏 (𝟏)= 0
𝒎𝟏 (2)= máx{𝒇𝟏 𝒙𝟎 + 𝒎𝟐 𝒖 − 𝒙𝟎 , 𝒇𝟏 𝒙𝟏 + 𝒎𝟐 (𝒖 − 𝒙𝟏 ), 𝒇𝟏 (𝒙𝟐 ) + Máx{ 0+6, 1+3, 4+0 } 6 𝒅𝟏 𝟐 = 0
𝒎𝟏 (3)= máx{𝒇𝟏 𝒙𝟎 + 𝒎𝟐 𝒖 − 𝒙𝟎 , 𝒇𝟏 𝒙𝟏 + 𝒎𝟐 (𝒖 − 𝒙𝟏 ), 𝒇𝟏 (𝒙𝟐 ) + Máx{ 0+9, 1+6, 4+3, 5+0} 9 𝒅𝟏 (𝟑)= 0
Conclusión
Puesto que u=3 genera el valor optimo en
𝒎𝟏 (3) se toma el 𝒅𝟏 (𝟑) como optimo. Decisiones Decisiones
Decisiones
Así la solución optima es:
𝒅𝟏 (𝟎)= 0 𝒅𝟐 (𝟎)= 0 𝒅𝟑 (𝟎)= 0
𝑧 ∗ = 𝑚1 3 =$9000 dólares
𝒅𝟏 (𝟏)= 0 𝒅𝟐 (𝟏)= 1 𝒅𝟑 (𝟏)= 1
𝑥1 = 𝑑1 𝑏 = 𝑑1 3 = 0
𝑥2 = 𝑑2 𝑏 − 𝑥1 = 𝑑2 3 = $1000 𝒅𝟏 𝟐 = 0 𝒅𝟐 𝟐 = 0 𝒅𝟑 𝟐 = 2
𝑥3 = 𝑑3 𝑏 − 𝑥1 − 𝑥2 = 𝑑3 2 = $2000
𝒅𝟏 (𝟑)= 0 𝒅𝟐 (𝟑)= 1 𝒅𝟑 (𝟑)= 3
De modo que, en el proyecto 1 se invierten 0
pesos, en el segundo proyecto $1000 y, por
ultimo, $2000 en el tercero.
EJERCICIO
Una corporación recibe propuestas de sus cuatro plantas respecto a la posible expansión de las
instalaciones. La corporación tiene un presupuesto de 3 millones para asignarlo a las plantas en unidades
de 1 millón. En la tabla se muestran los rendimientos en millones de pesos.
Inversión
E $0 $1 $2 $3
t
a Proyecto 1 0 $1.28 $2.45 $3.65
p
Proyecto 2 0 $1.25 $2.41 $3.55
a
s Proyecto 3 0 $1.15 $2.25 $3.40
Proyecto 4 0 $1.20 $2.33 $3.42
Etapa 4 0 $1 $2 $3
P1 0 $1.28 $2.45 $3.65
P2 0 $1.25 $2.41 $3.55
𝑚á𝑥 𝑧 = 𝑓1 𝑥1 + 𝑓2 𝑥2 + 𝑓3 𝑥3 + 𝑓4 𝑥4
P3 0 $1.15 $2.25 $3.40
𝑠. 𝑎. 𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 ≤ $3000000
P4 0 $1.20 $2.33 $3.42
𝒎𝑵 (u)= máx 𝒇𝑵 (𝒙) 0<x<u Valor óptimo Decisiones
𝒎𝟒 (0)= máx 𝒇𝟒 (𝒙𝟎 ) Máx{ 0 } 0 𝒅𝟒 (𝟎)= 0
𝒎𝟒 (1)= máx{𝒇𝟒 (𝒙𝟎 ), 𝒇𝟒 (𝒙𝟏 )} Máx{ 0, 1.2 } 1.2 𝒅𝟒 (𝟏)= 1
𝒎𝟒 (2)= máx 𝒇𝟒 (𝒙𝟎 ), 𝒇𝟒 (𝒙𝟏 ), 𝒇𝟒 (𝒙𝟐 ) Máx{ 0, 1.2, 2.33 } 2.33 𝒅𝟒 𝟐 = 2
𝒎𝟒 (3)= máx 𝒇𝟒 (𝒙𝟎 ), 𝒇𝟒 (𝒙𝟏 ), 𝒇𝟒 (𝒙𝟐 ), 𝒇𝟒 (𝒙𝟑 ) Máx{ 0, 1.2, 2.33, 3.42} 3.42 𝒅𝟒 (𝟑)= 3
0 $1 $2 $3
Etapa 3 P1 0 $1.28 $2.45 $3.65 𝒎𝟒 (0)=0
𝒎𝟒 (1)=1.2
P2 0 $1.25 $2.41 $3.55
𝒎𝟒 (2)=2.33
P3 0 $1.15 $2.25 $3.40
𝒎𝟒 (3)=3.42
P4 0 $1.20 $2.33 $3.42
𝒎𝒋 (u)= máx 𝒇𝒋 𝒙 + 𝒎𝒋+𝟏 (𝒖 − 𝒙) 0<x<u Valor Decisiones
óptimo
𝒎𝟑 (0)= máx 𝒇𝟑 𝒙𝟎 + 𝒎𝟒 (𝒖 − 𝒙𝟎 ) Máx{ 0 } 𝒅𝟑 (𝟎)= 0
0
𝒎𝟑 (1)= máx{𝒇𝟑 𝒙𝟎 + 𝒎𝟒 𝒖 − 𝒙𝟎 , 𝒇𝟑 𝒙𝟏 + 𝒎𝟒 (𝒖 − 𝒙𝟏 )} Máx{ 1.2, 1.15 }
𝒅𝟑 (𝟏)= 0
1.2
𝒎𝟑 (2)= máx{𝒇𝟑 𝒙𝟎 + 𝒎𝟒 𝒖 − 𝒙𝟎 , 𝒇𝟑 𝒙𝟏 + 𝒎𝟒 (𝒖 − 𝒙𝟏 ), 𝒇𝟑 (𝒙𝟐 ) + Máx{ 2.33, 2.35, 2.25 }
2.35 𝒅𝟑 𝟐 = 1
𝒎𝟑 (3)= máx{𝒇𝟑 𝒙𝟎 + 𝒎𝟒 𝒖 − 𝒙𝟎 , 𝒇𝟑 𝒙𝟏 + 𝒎𝟒 (𝒖 − 𝒙𝟏 ), 𝒇𝟑 (𝒙𝟐 ) + Máx{ 3.42, 2.35, 3.25,3.40}
3-48 𝒅𝟑 (𝟑)= 1
Etapa 2 0 $1 $2 $3
P1 0 $1.28 $2.45 $3.65 𝒎𝟑 (0)=0
𝒎𝟑 (1)=1.2
P2 0 $1.25 $2.41 $3.55
𝒎𝟑 (2)=2.35
P3 0 $1.15 $2.25 $3.40
𝒎𝟑 (3)=3.48
P4 0 $1.20 $2.33 $3.42
𝒎𝒋 (u)= Valor óptimo Decisiones
𝒎𝟐 (0)= Máx{ 0 } 0 𝒅𝟐 (𝟎)= 0
𝒎𝟐 (1)= Máx{ 0, 1.2, 1.25 } 1.25 𝒅𝟐 (𝟏)= 1
𝒎𝟐 (2)= Máx{ 2.35, 2.45, 2.41 } 2.45 𝒅𝟐 𝟐 = 1
𝒎𝟐 (3)= Máx{ 3.48, 3.6, 3.61, 3.55} 3.61 𝒅𝟐 (𝟑)= 2
Etapa 1 0 $1 $2 $3
𝒎𝟐 (0)=0
P1 0 $1.28 $2.45 $3.65
𝒎𝟐 (1)=1.25
P2 0 $1.25 $2.41 $3.55
𝒎𝟐 (2)=2.45
P3 0 $1.15 $2.25 $3.40
𝒎𝟐 (3)=3.61
P4 0 $1.20 $2.33 $3.42
𝒎𝒋 (u)= Valor óptimo Decisiones
𝒎𝟏 (0)= Máx{ 0 } 0 𝒅𝟏 (𝟎)= 0
𝒎𝟏 (1)= Máx{ 0, 1.25, 1.28 } 1.28 𝒅𝟏 (𝟏)= 1
𝒎𝟏 (2)= Máx{ 2.45, 2.53, 2.45 } 2.53 𝒅𝟏 𝟐 = 1
𝒎𝟏 (3)= Máx{ 3.61, 3.73, 3.70, 3.65} 3.73 𝒅𝟏 (𝟑)= 1
Conclusión
Puesto que u=3 genera el valor optimo en
𝒎𝟏 (3) se toma el 𝒅𝟏 (𝟑) como optimo.
Decisiones Decisiones Decisiones Decisiones
Así la solución optima es:
𝒅𝟒 (𝟎)= 0 𝒅𝟑 (𝟎)= 0 𝒅𝟐 (𝟎)= 0 𝒅𝟏 (𝟎)= 0
𝑧 ∗ = 𝑚1 3 =$3.73mil
𝒅𝟒 (𝟏)= 1 𝒅𝟑 (𝟏)= 0 𝒅𝟐 (𝟏)= 1 𝒅𝟏 (𝟏)= 1
𝑥1 = 𝑑1 𝑏 = 𝑑1 3 = $1 𝒅𝟒 𝟐 = 2 𝒅𝟑 𝟐 = 1 𝒅𝟐 𝟐 = 1 𝒅𝟏 𝟐 = 1
𝑥2 = 𝑑2 𝑏 − 𝑥1 = 𝑑2 2 = $1
𝒅𝟒 (𝟑)= 3 𝒅𝟑 (𝟑)= 1 𝒅𝟐 (𝟑)= 2 𝒅𝟏 (𝟑)= 1
𝑥3 = 𝑑3 𝑏 − 𝑥1 − 𝑥2 = 𝑑3 1 = $0
𝑥4 = 𝑑4 𝑏 − 𝑥1 − 𝑥2 − 𝑥3 = 𝑑4 1 = $1
.
