第23卷第2期2009年4月
济南大学学报(自然科学版)
J OURNA L O F UN IVERS I TY OF JI NAN (Sc. i &T ech 1)
Vo. l 23No . 2
Ap r . 2009
文章编号:1671-3559(2009) 02-0212-03
一种求解动态规划模型的新方法
苗丽安, 韩静轩
a
b
(济南大学a . 理学院; b. 管理学院, 山东济南250022)
摘 要:动态规划模型及求解方法是运筹学和现代管理科学中进行投资决策分析的重要手段。针对动态规划中资源分配问题模型, 提出一种新的动态规划表解方法。相对于已有的表解方法更为直观和简单易行, 也简化了解题过程中的计算和语言表述过程。新的表解方法可推广到其他的动态规划求解问题中去。
关键词:动态规划; 表解法; 资源分配中图分类号:O 1-22
文献标志码:A
A New M ethod of Solvi ng the D yna m ic Progra mm i ng M odel
M IAO L-i an a , HAN J i n g -xuan b
(a . School of Science ; b . Schoo l ofM an age m en t , U n i versit y of J i nan, Ji nan 250022, Ch i na)
Abstrac t :Dyna m ic prog ramm i ng m ode l i s an i m po rtan t co m ponent of operationa l research and m ode rn managem ent sc ience . It is an i m po rtant too l and a basis to carry on i nvest m ent dec i sion ana l y si s . T he dyna m ic progra mm ing si m ple so l uti on i s an i m po rtant dom ain o fm anage m ent sc i ence research . Th i s arti c l e , i n v ie w of the resource distributi on m ode l of the dyna m ic prog ramm i ng , has proposed a new tab le so l uti on . Co m pa red w it h t he ex isti ng tab l e so luti ons , it is m ore i ntuiti v e and si m p l e . In additi on , this m ethod can be used i n other dyna m ic progra mm i ng so l u ti ons .
K ey word s :dyna m ic progra mm i ng ; tab le so l uti on ; resource distri buti on
表1 动态规划问题的表解法一
S k
V k (Sk , x k ) +f k +1(S k +1)
x k 1x k 2, , x k n
f k (S k )
x *k
1 问题的提出
动态规划是运筹学和现代管理科学的一个重要组成部分, 在企业财务决策问题中发挥着重要作用。有关财务投资分配问题的动态规划求解法一直是研
究的热点。
许多学者从Be ll m an 最优性原理出发相继提出了很多简化解法, 其中表解法应用较为广泛, 该方法适用于离散状态变量及决策变量的投资分配问题。
[1]
目前表解法主要有两种计算表, 见表1和表2(采用逆序法) 。
上述两种计算表解法可以简化计算过程, 使得计算过程清晰明了。但是这两种方法同样也存在一
S k
表2 动态规划问题的表解法二
x k k (S k , x k )
S k +1=
f k +1
V k (Sk , x k ) +f k +1(S k +1)
f k (Sk ) x *
k
T (S k , x k ) (Sk +1)
些弊端。如对于计算表1, 在进行分析和求解时, 表格中反映的计算关系不明晰, 必须辅助以大量的文字说明才能够使得解题过程被人们所理解, 且计算过程中没有V k (Sk , x k ), S k +1, f k +1(S k +1) 等值, 容易出错; 对于计算表2, 虽然计算过程比较直观, 但是收稿日期:2008-05-04
作者简介:苗丽安(1964-), 女(锡伯族), 黑龙江齐齐哈尔人, 副
第2期苗丽安, 等:一种求解动态规划模型的新方法
[2-3]
213
x k >10) 时, 计算量相当大。另外经过近一时期
[4]
投资的资金总额;
决策变量x k 表示对k (k =1, 2, 3) 项目的投资数(0[x 1[4, 1[x 2[S 2, 1[x 3[S 3);
状态转移方程为
S k +1=S k -x k 递推方程为
f k (S k ) =m ax {V k (S k , x k ) +f k +1(S k +1) }
f 4(S 4) =0, S 4=0求解过程如下(逆推法):
(1) 对阶段k =3进行分析和计算。
对于项目三, 有1[S 3[4, 1[x 1[S 3, 计算表如
下表5。
对动态规划(投资分配) 问题的研究况。
, 发现这两种
方法在有些问题处理上也存在一些应用不便的情
2 一种求解动态规划的表解新方法
鉴于上述两种表解法的优点以及其中存在的弊端, 我们结合计算表1和计算表2提出一种新的表解方法(见表3) 。它既保留了表1的节省空间和简化计算的特点, 又兼顾了表2直观明了的特点, 同时避免了表1的操作复杂和表2计算繁琐的问题。可以说表3是综合表1和表2的优点而构建起来的。
表3 动态规划问题表解新方法
S k +1
f k +1
(Sk +1) k
V k (S k , x k ) +f k +1(Sk +1) x k 1
x k 2
,
x kn
f k (S k ) x *k
V k (Sk , x k )
3 例证
为了说明这种表解法的使用方法, 我们以中国
科学院2004年博士生入学考试试题第三题为例, 来说明其求解过程。
实例:某投资人现有资金500万元, 可对3个项目进行投资, 投资额均为整数(单位为百万元) 。其中项目二投资不得超过300万元, 项目一和三的投资均不得超过400万元, 项目三不得少于100万元, 各个项目的收益见表4。问如何投资收益最大?
表4 投资收益分配表
投收益额k , k x k )
项目一项目二项目三
000-1354
26108
说明:
¹由V 3(S 3, x 3) +f 4(S4) 表左边的f 4(S4) 和表最底层的V 3(S3, x 3) 之和求得;
ºV 3(S3, x 3) +f 4(S4) 对应的矩阵为三角矩阵, 因为1[S 3[4, 1[x 1[S 3; »比较表中斜线部分数值的大小, 其中数值最大者, 写入斜线数据最底端值所在行的右端f 3(S3) 栏下, 其数值所在列的x 值则对应与最优值x 。这一方法的理论依据是由状态转移方程得出的, 即S k =S k +1+x k 。
如表5中右侧斜线对应的一组数据:4, 8, 11, 15; 其中最大值为15, 且斜线最底端所在的行是S 3=4, 所以将15写在f 3(S 3) 对应于S 3=4的位置, 而且15所在的列对应的x 为4, 所以相应的x 为4。
表5中第二条斜线对应的一组数据:4, 8; 其中最大值为8, 且斜线最底端所在的行是S 3=2, 所以将8写在f 3(S 3) 对应于S 3=2的位置, 而且8所在的列对应的x 为2, 所以相应的x 为2。
(2) 对阶段进行分析和计算。
对于项目二, 有1[S 2[5, 1[x 2[S 2, 计算表如下表6。
*
**
单位:百万元
3101211
412-15
解:可把这个问题视作一个多阶段决策问题, 根
据题意和表中数据可知(或假设):
阶段变量k =1, 2, 3;
状态变量S 1=5, 表示可向第一、第二和第三个项目投资的资金总额;
状态变量S 2(1[S 2[5) 表示可向第二和第三个项目投资的资金总额;
(3
214济南大学学报(自然科学版) 第23卷
S 1=x 1+S 2(该题只是一种特例, 利润全为正值) 。当然也可以把三角矩阵补齐。
所以, 由上面的表1、表2和表3, 可以方便的找出最优方案:
f 1(S1) =f 1(5) =21;
x 1=0或1;
当x 1=0时, y f 2(S 2) =21, S 2=5, x 2=2y f 3(S 3) =11, S 3=3, x 3=2
当x 1=1时, y f 2(S 2) =18, S 4=4, x 2=2
说明:
表6与表5有所不同, 主要是对应于S 2=5的行没有数值, 对于这一情况, 我们可以补足一个数
Q, 在该例中Q 值可取为
Q =m i n {V 2(S 2, x 2) +f 3(S3) }=4
其他同阶段k =3的计算过程。
(3) 对阶段k =1进行分析和计算。
对于项目一, 有S 1=5, 1[x 1[S 1, 计算表如下表7
。
y f 3(S 3) =8, S 3=2, x 3=2
*
*
*
*
*
*
*
4 结束语
这里所引的例证也可以用表1和表2的解法进行求解(参见文献[1]和[5]), 经过对比可以发现
表3的算法克服了表1和表2计算中存在的问题。对于k 较大和x k 的值较多时就显得更加方便了。另外也可以证明这种计算方法可以方便的推广到求解其他问题的动态规划中去。
参考文献:
[1] 吴育华, 杜 刚1管理科学基础[M]1天津:天津大学出版社,
20021
[2] 吴庆丰, 刘兵兵. 利用动态规划求解资源分配问题[J].安庆师
范学院学报:自然科学版, 2008, 14(2):74-75.
[3] 伍 勇, 刘 春. 动态规划模型在组合投资理论中的应用[J ].
北京机械工业学院学报, 2008, 23(2):62-66.
[4] 李 端, 钱富才. 动态规划问题研究[J].系统工程理论与实
践, 2007(8):56-64.
[5] 清华大学运筹学课题组1运筹学[M]1北京:清华大学出版
社, 19901
说明:
在表7中, 主要是由于S 1=5, 1[x 1[S 1, 并且
(责任编辑:刘建亭, 校对:隋 肃)
第23卷第2期2009年4月
济南大学学报(自然科学版)
J OURNA L O F UN IVERS I TY OF JI NAN (Sc. i &T ech 1)
Vo. l 23No . 2
Ap r . 2009
文章编号:1671-3559(2009) 02-0212-03
一种求解动态规划模型的新方法
苗丽安, 韩静轩
a
b
(济南大学a . 理学院; b. 管理学院, 山东济南250022)
摘 要:动态规划模型及求解方法是运筹学和现代管理科学中进行投资决策分析的重要手段。针对动态规划中资源分配问题模型, 提出一种新的动态规划表解方法。相对于已有的表解方法更为直观和简单易行, 也简化了解题过程中的计算和语言表述过程。新的表解方法可推广到其他的动态规划求解问题中去。
关键词:动态规划; 表解法; 资源分配中图分类号:O 1-22
文献标志码:A
A New M ethod of Solvi ng the D yna m ic Progra mm i ng M odel
M IAO L-i an a , HAN J i n g -xuan b
(a . School of Science ; b . Schoo l ofM an age m en t , U n i versit y of J i nan, Ji nan 250022, Ch i na)
Abstrac t :Dyna m ic prog ramm i ng m ode l i s an i m po rtan t co m ponent of operationa l research and m ode rn managem ent sc ience . It is an i m po rtant too l and a basis to carry on i nvest m ent dec i sion ana l y si s . T he dyna m ic progra mm ing si m ple so l uti on i s an i m po rtant dom ain o fm anage m ent sc i ence research . Th i s arti c l e , i n v ie w of the resource distributi on m ode l of the dyna m ic prog ramm i ng , has proposed a new tab le so l uti on . Co m pa red w it h t he ex isti ng tab l e so luti ons , it is m ore i ntuiti v e and si m p l e . In additi on , this m ethod can be used i n other dyna m ic progra mm i ng so l u ti ons .
K ey word s :dyna m ic progra mm i ng ; tab le so l uti on ; resource distri buti on
表1 动态规划问题的表解法一
S k
V k (Sk , x k ) +f k +1(S k +1)
x k 1x k 2, , x k n
f k (S k )
x *k
1 问题的提出
动态规划是运筹学和现代管理科学的一个重要组成部分, 在企业财务决策问题中发挥着重要作用。有关财务投资分配问题的动态规划求解法一直是研
究的热点。
许多学者从Be ll m an 最优性原理出发相继提出了很多简化解法, 其中表解法应用较为广泛, 该方法适用于离散状态变量及决策变量的投资分配问题。
[1]
目前表解法主要有两种计算表, 见表1和表2(采用逆序法) 。
上述两种计算表解法可以简化计算过程, 使得计算过程清晰明了。但是这两种方法同样也存在一
S k
表2 动态规划问题的表解法二
x k k (S k , x k )
S k +1=
f k +1
V k (Sk , x k ) +f k +1(S k +1)
f k (Sk ) x *
k
T (S k , x k ) (Sk +1)
些弊端。如对于计算表1, 在进行分析和求解时, 表格中反映的计算关系不明晰, 必须辅助以大量的文字说明才能够使得解题过程被人们所理解, 且计算过程中没有V k (Sk , x k ), S k +1, f k +1(S k +1) 等值, 容易出错; 对于计算表2, 虽然计算过程比较直观, 但是收稿日期:2008-05-04
作者简介:苗丽安(1964-), 女(锡伯族), 黑龙江齐齐哈尔人, 副
第2期苗丽安, 等:一种求解动态规划模型的新方法
[2-3]
213
x k >10) 时, 计算量相当大。另外经过近一时期
[4]
投资的资金总额;
决策变量x k 表示对k (k =1, 2, 3) 项目的投资数(0[x 1[4, 1[x 2[S 2, 1[x 3[S 3);
状态转移方程为
S k +1=S k -x k 递推方程为
f k (S k ) =m ax {V k (S k , x k ) +f k +1(S k +1) }
f 4(S 4) =0, S 4=0求解过程如下(逆推法):
(1) 对阶段k =3进行分析和计算。
对于项目三, 有1[S 3[4, 1[x 1[S 3, 计算表如
下表5。
对动态规划(投资分配) 问题的研究况。
, 发现这两种
方法在有些问题处理上也存在一些应用不便的情
2 一种求解动态规划的表解新方法
鉴于上述两种表解法的优点以及其中存在的弊端, 我们结合计算表1和计算表2提出一种新的表解方法(见表3) 。它既保留了表1的节省空间和简化计算的特点, 又兼顾了表2直观明了的特点, 同时避免了表1的操作复杂和表2计算繁琐的问题。可以说表3是综合表1和表2的优点而构建起来的。
表3 动态规划问题表解新方法
S k +1
f k +1
(Sk +1) k
V k (S k , x k ) +f k +1(Sk +1) x k 1
x k 2
,
x kn
f k (S k ) x *k
V k (Sk , x k )
3 例证
为了说明这种表解法的使用方法, 我们以中国
科学院2004年博士生入学考试试题第三题为例, 来说明其求解过程。
实例:某投资人现有资金500万元, 可对3个项目进行投资, 投资额均为整数(单位为百万元) 。其中项目二投资不得超过300万元, 项目一和三的投资均不得超过400万元, 项目三不得少于100万元, 各个项目的收益见表4。问如何投资收益最大?
表4 投资收益分配表
投收益额k , k x k )
项目一项目二项目三
000-1354
26108
说明:
¹由V 3(S 3, x 3) +f 4(S4) 表左边的f 4(S4) 和表最底层的V 3(S3, x 3) 之和求得;
ºV 3(S3, x 3) +f 4(S4) 对应的矩阵为三角矩阵, 因为1[S 3[4, 1[x 1[S 3; »比较表中斜线部分数值的大小, 其中数值最大者, 写入斜线数据最底端值所在行的右端f 3(S3) 栏下, 其数值所在列的x 值则对应与最优值x 。这一方法的理论依据是由状态转移方程得出的, 即S k =S k +1+x k 。
如表5中右侧斜线对应的一组数据:4, 8, 11, 15; 其中最大值为15, 且斜线最底端所在的行是S 3=4, 所以将15写在f 3(S 3) 对应于S 3=4的位置, 而且15所在的列对应的x 为4, 所以相应的x 为4。
表5中第二条斜线对应的一组数据:4, 8; 其中最大值为8, 且斜线最底端所在的行是S 3=2, 所以将8写在f 3(S 3) 对应于S 3=2的位置, 而且8所在的列对应的x 为2, 所以相应的x 为2。
(2) 对阶段进行分析和计算。
对于项目二, 有1[S 2[5, 1[x 2[S 2, 计算表如下表6。
*
**
单位:百万元
3101211
412-15
解:可把这个问题视作一个多阶段决策问题, 根
据题意和表中数据可知(或假设):
阶段变量k =1, 2, 3;
状态变量S 1=5, 表示可向第一、第二和第三个项目投资的资金总额;
状态变量S 2(1[S 2[5) 表示可向第二和第三个项目投资的资金总额;
(3
214济南大学学报(自然科学版) 第23卷
S 1=x 1+S 2(该题只是一种特例, 利润全为正值) 。当然也可以把三角矩阵补齐。
所以, 由上面的表1、表2和表3, 可以方便的找出最优方案:
f 1(S1) =f 1(5) =21;
x 1=0或1;
当x 1=0时, y f 2(S 2) =21, S 2=5, x 2=2y f 3(S 3) =11, S 3=3, x 3=2
当x 1=1时, y f 2(S 2) =18, S 4=4, x 2=2
说明:
表6与表5有所不同, 主要是对应于S 2=5的行没有数值, 对于这一情况, 我们可以补足一个数
Q, 在该例中Q 值可取为
Q =m i n {V 2(S 2, x 2) +f 3(S3) }=4
其他同阶段k =3的计算过程。
(3) 对阶段k =1进行分析和计算。
对于项目一, 有S 1=5, 1[x 1[S 1, 计算表如下表7
。
y f 3(S 3) =8, S 3=2, x 3=2
*
*
*
*
*
*
*
4 结束语
这里所引的例证也可以用表1和表2的解法进行求解(参见文献[1]和[5]), 经过对比可以发现
表3的算法克服了表1和表2计算中存在的问题。对于k 较大和x k 的值较多时就显得更加方便了。另外也可以证明这种计算方法可以方便的推广到求解其他问题的动态规划中去。
参考文献:
[1] 吴育华, 杜 刚1管理科学基础[M]1天津:天津大学出版社,
20021
[2] 吴庆丰, 刘兵兵. 利用动态规划求解资源分配问题[J].安庆师
范学院学报:自然科学版, 2008, 14(2):74-75.
[3] 伍 勇, 刘 春. 动态规划模型在组合投资理论中的应用[J ].
北京机械工业学院学报, 2008, 23(2):62-66.
[4] 李 端, 钱富才. 动态规划问题研究[J].系统工程理论与实
践, 2007(8):56-64.
[5] 清华大学运筹学课题组1运筹学[M]1北京:清华大学出版
社, 19901
说明:
在表7中, 主要是由于S 1=5, 1[x 1[S 1, 并且
(责任编辑:刘建亭, 校对:隋 肃)