２０１４年３月 第８卷第１期 伊犁师范学院学报（自然科学版） Ｊｏｕｒｎａｌ ｏｆＹｉｌｉ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） Ｍａｒ．２０１４ Ｖ０１．８ Ｎｏ．１ 资源分配问题的动态规划及其Ｌｉｎｇｏ求解 徐芹 （定西师范高等专科学校数学系，甘肃定西７４３０００） 摘要：资源分配问题是将一种或几种资源，恰当地分配给若干个用户，而使目标函数为最 优．介绍了应用动态规划的方法解决资源分配问题时的一般策略，并通过实例应用Ｌｉｎｇｏ编程方 便地求解此类问题． 关键词：资源分配问题；动态规划；合理分配；Ｌｉｎｇｏ 中图分类号：Ｏ２２１．３ 文献标志码：Ａ 文章编号：１６７３－－９９９Ｘ（２０１４）０１—００２６—０４ １ 引言 动态规划【１】作为运筹学的一个非常重要的分支，其应用广泛．从２Ｏ世纪５０年代美国数学家理查德·贝 尔曼根据最优性原理提出动态规划的方法，至今五十多年的时间里，人们已经运用动态规划的方法解决了 工程技术、工农业生产、企业管理、军事等部门的许多多阶段决策问题，可以说它是现代企业管理中的一 种重要而有效的决策方法．根据多阶段决策过程时间的离散或连续性，动态规划的模型可分为离散决策过 程模型和连续决策过程模型．对于离散型的问题，由于解析数学无法涉及，所以运用动态规划的方法，往 往比线性规划或非线性规划更有成效． 在确定实际问题为多阶段决策问题后，可根据以下步骤构造动态规划的模型：（１）恰当地划分阶段．即 把所有问题的过程，按照一定的原则，划分为几个相互联系的阶段，常用ｋ表示阶段变量．（２）选择正确 的状态变量．状态变量即描述状态过程的变量，常用一个向量、一个数或一组数来描述，一般我们用Ｓ 表 示第ｋ个阶段的状态变量．（３）在允许决策集合中找出决策变量．决策变量就是确定下一阶段状态的变量， 常用“ （ ）表示第ｋ个阶段的决策变量．（４）在允许策略集合中找出按一定顺序排列的策略．常用 Ｐｋ， （ ）＝｛ （ ）， （ ），…， （ ））表示从第ｋ个阶段开始到终点的过程，称为ｋ子过程策略，则 Ｐｌ， （ ）＝｛“。（ ），“：（ ：），… （ ））即为问题的全策略．（５）确定状态转移过程．当 和Ｓ 的值确定后，Ｓ 的 值就完全确定，常用方程 ＋ｌ＝ （ ， ）来表示状态转移的过程．（６）指标函数和最优值函数的确定．指 标函数是用来衡量所实现过程优劣的一种数量指标，常用 ＝， ． 来表示，即 ， （ ， ，Ｓ ， ＋１，一’）＝ ，Ｕ ， ＋１， （ ＋１，…，Ｓ川）］，ｋ＝１，２，…，，ｚ． 收稿日期：２０１３．１０．３０ 作者简介：徐芹（１９８ ），女，在读硕士研究生，研究方向：图论及其应用 第１期 徐芹：资源分配问题的动态规划及其Ｌｉｎｇｏ求解 最优值函数是指标函数的最优值，记为 （ ），是我们采取最优策略所得到的指标函数值，即 ）＝ｏｐｔ （ ， ，…， ＋１），“ｏｐｔ”常取作ｒａｉｎ或ｍａｘ． ２用动态规划求解资源分解问题的一般方法 分配问题【 即将一定数量的一种或若干种资源（例如原材料、资金、机器设备、劳力、食品等），恰 用于Ｎ个生产项目，若分配数量 （决策变量）个单位的资源用于生产第ｋ种产品，其收益为ｇ （ ）， ＩｍａｘＺ：ｇｌ（ １）＋ｇ２（ ２）＋…＋ｇ （ ） ｛ ＋ｚｆ２＋…＋ｚ ＝Ａ 【 ≥０，ｋ＝１，２ ３一，Ⅳ 设状态变量 表示分配用于第ｋ个生产项目到第Ⅳ个生产项目的资源数量；决策变量 表示分配给 第ｋ个生产项目的资源数，则状态转移方程为 ＋ｌ＝ 一 ；决策为ｕｋ（ｓｋ），允许决策集合为 ｐ （ ）＝｛ ｌ ０ Ｕ Ｓｋ）；当数量为Ｓ 的资源分配给第七个生产项目至第Ｎ个生产项目所得的最大总 收入即为最优值函数 （ ），则可得动态规划的递推关系式为： ｆ （ ） 墨 ｛ （ ）＋ ＋ （ 一 ）），ｋ＝Ｎ一１，…，１ １ （ ）＝ｍ ｘａ｛ ｇⅣ（ ）） 利用这个递推关系式逐段计算，最后求得 ）即为问题的最优解． ３ Ｌｉｎｇｏ求解实例 ’ 设某公司购置了７台新设备，供给３个企业，已知各企业在分配设备量 下的效益函数为ｇ，（ ），ｉ＝１， ＼ ０ — —１ ２ ｌ５ ３ ４０ ４ ８０ ５ ９０ ６ ９５ ７ ｌ００ ｇｉｇＩ（ｕｋ） ０ ５ 根据题意，建立下列Ｌｉｎｇｏ模型： ｓｅｔｓ： ！用户： ｕｓｅｒ／１．．３／； ２８ 伊犁师范学院学报（自然科学版） ！设备量： ａｍｏｕｔ／１．．８／； ！分配方案： ａｒｃｓ（ｕｓｅｒ，ａｍｏｕｔ）：ｂｅｎｅｆｉｔ，ｓｔａｔｕｓ，ｓｅｌｅｃｔｉｏｎ； ｅｎｄｓｅｔｓ ｄａｔａ： ！效益； ｂｅｎｅｆｉｔ－＝０ ５ １５ ４０ ８０ ９０ ９５ １００ ０ ５ ｌ５ ４０ ６０ ７０ ７３ ７５ ０ ４ ２６ ４０ ４５ ５０ ５１ ５３； ！待定分配量： ｓｔａｔｕｓ＝０ ｌ ２ ３ ４ ５ ６ ７ ０ ｌ ２ ３ ４ ５ ６ ７ ０ １ ２ ３ ４ ５ ６ ７； ｅｎｄｄａｔａ ｍａＤ（ ＠ｓｕｍ（ａｒｃｓ（ｉ，ｊ）：ｂｅｎｅｆｉｔ（ｉ，ｊ）幸ｓｅｌｅｃｔｉｏｎ（ｉ，ｊ））； ＠ｆｏｒ（ａｒｃｓ：＠｝ｂｉｎ（ｓｅｌｅｃｔｉｏｎ））； ＠ｆｏｒ（ｕｓｅｒ（ｉ）：＠ｓｕｍ（ａｒｃｓ（ｉ，ｋ）：ｓｅｌｅｃｔｉｏｎ（ｉ，ｋ））＝１）； ＠ｓｕｍ（ａｒｃｓ（ｉ，ｊ）：ｓｔａｔｕｓ（ｉ，ｊ） ｓｅｌｅｃｔｉｏｎ（ｉ，ｊ））＝７： ｅｎｄ 求解上述模型，得到以下结果： Ｇｌｏｂａｌ ｏｐｔｉｍａｌ ｓｏｌｕｔｉｏｎ ｆｏｕｎｄ． Ｏｂｊｅｃｔｉｖｅ ｖａｌｕｅ： １２０．００００ Ｖ ｉａｂｌｅ Ｖａｌｕｅ Ｒｅｄｕｃｅｄ Ｃｏｓｔ ＢＩＮ（１，１ ０．０００００ ０．００００００ ＢＩＮ（１，２ ０．０００００ ．５．００００００ ＢＩＮ（１，３ ０．０００００ ．１ ５．００００００ ＢＩＮ（１，４ ０．０００００ —４０．００００００ Ｂ （１，５ １．０００００ ．８０．００００００ ＢＩＮ（２，１ ０．０００００ ０．００００００ ＢＩＮ（２，２ ０．０００００ ．５．００００００ ＢＩＮ（２，３ ０．０００００ ．１５．００００００ ＢＩＮ（２，４ １．０００００ ．４０．００００００ ａｒＮ（３，１ １．０００００ ０．００００００ ＢｒＮ（３，２ ０．０００００ ．４．００００００ ● ● Ｒｏｗ Ｓｌａｃｋ ｏｒ Ｓｕｒｐｌｕｓ Ｄｕａｌ Ｐｒｉｃｅ １ １ ２０．００００ １．００００ 可见将７台设备分别以４， ３，０的比例分配给３个企业，可得到最大效益为１２０． ２０１４生 第１期 徐芹：资源分配问题的动态规划及其Ｌｉｎｇｏ求解 ２９ ４结果分析与说明 通过对上述实际问题的求解，充分证明了在求解资源分配的动态规划问题时，采用Ｌｉｎｇｏ实现程序是 有效的、简便的，且可将这种方法推广到求解其他问题的动态规划中，同样可轻松地求得问题的最优解． 参考文献： ［１］ 清华大学运筹学课题组．运筹学［Ｍ］．北京：清华大学出版社，１９９０． ［２］ 吴庆斗．资源分配问题的动态规划求解方法［Ｊ］．淮北煤炭师范学院（自然科学版），２００８，２９（２）：３２—３４． ［３］ 姜启源．数学模型［Ｍ］．北京：高等教育出版社，２００３． ［责任编辑：张建国］ Ｄｙｎａｍｉｃ Ｐｒｏｇｒａｍｍｉｎｇ ａｎｄ Ｌｉｎｇｏ ｔｏ Ｓｏｌｖｅ Ｒｅｓｏｕｒｃｅ Ａｌｌｏｃａｔｉｏｎ Ｐｒｏｂｌｅｍ ｘＵ Ｑｉｎ （Ｄｅｐａｒｔｍｅｎｔ ｏｆＭａｔｈｅｍａｔｉｃｓ，Ｄｉｎｇｘｉ Ｔｅａｃｈｅｒｓ Ｃｏｌｌｅｇｅ，Ｄｉｎｇｘｉ，Ｇａｎｓｕ ７４３０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｅ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍ ｉｓ ｏｎｅ ｏｒ ｍｏｒｅ ｏｆ ｔｈｅ ｆｏｌｌｏｗｉｎｇ ｒｅｓｏｕｒｃｅｓ，ｐｒｏｐｅｒｌｙ ａｓｓｉｇｎｅｄ ｔｏ ａ ｎｕｍｂｅｒ ｏｆ ｕｓｅｒｓ，ａｎｄ ｍａｋｅｓ ｔｈｅ ｏｂｊｅｃｔｉｖｅ ｆｕｎｃｔｉｏｎ ｆｏｒ ｔｈｅ ｏｐｔｉｍａ１．Ｔｈｉｓ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ａｐｐｌｉｃａｔｉｏｎ ｏｆ ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ ｍｅｔｈｏｄ ｔｏ ｓｏｌｖｅ ｔｈｅ ｐｒｏｂｌｅｍ ｏｆ ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｉｎ ｔｈｅ ｇｅｎｅｒａｌ ｓｔｒａｔｅｇｙ．Ａｎｄ ｔｈｒｏｕｇｈ ｔｈｅ Ｌｉｎｇｏ ｐｒｏｇｒａｍｍｉｎｇ ｃｏｎｖｅｎｉｅｎｔ，ａｎ ａｐｐｌｉｃａｔｉｏｎ ｅｘａｍｐｌｅ ｔｏ ｓｏｌｖｅ ｔｈｅｓｅ ｐｒｏｂｌｅｍｓ，ｔｏ ｇｕｉｄｅ ｅｎｔｅｒｐｒｉｓｅｓ ｔｏ ｂｅｔｔｅｒ ａｌｌｏｃａｔｉｏｎ ｏｆ ｒｅｓｏｕｒｃｅｓ ｈａｓ ａ ｃｅｒｔａｉｎ ｒｅｆｅｒｅｎｃｅ ｖａｌｕｅ． Ｋｅｙ ｗｏｒｄｓ：ｒｅｓｏｕｒｃｅ ａｌｌｏｃａｔｉｏｎ ｐｒｏｂｌｅｍｓ；ｄｙｎａｍｉｃ ｐｒｏｇｒａｍｍｉｎｇ；ｒａｔｉｏｎａｌ ｄｉｓｔｒｉｂｕｔｉｏｎ；Ｌｉｎｇｏ