简表法解决的一类资源分配问题

李承耕，刘 波

(韩山师范学院 数学与统计系,广东 潮州 521041)

简表法解决的一类资源分配问题

李承耕，刘 波

(韩山师范学院 数学与统计系,广东 潮州 521041)

针对宏观管理与系统规划中的设点问题,给出将静态规划转化为动态规划的思路,并提出用简表法完成阶段寻优问题,并由此获得资源分配问题的最优结果．

设点决策;静态规划;动态规划;最优策略;阶段寻优

动态规划也称多阶段决策,是一种重要的算法设计思想,在算法设计中具有广泛的应用,动态规划具有空间换时间(空间消耗大,时间效率高)的特点,当然也有一部分时间效率不高,仍然存在优化的余地,本文通过将动态规划用简表法来实现来达到空间换时间,以节省大量计算量的目的．

1 经济背景与数学模型

在社会经济活动中,作为生产宏观管理部门会经常遇到资源的分配问题,在资源有限的情况下,如何将资源分配到各个项目子系统,从而使得系统的总收益最大或总投入最小．根据以上经济问题,我们可以作如下假设

1.设目标函数的最大收益为maxz,或最小开支为minz.

2.第i个 项目投入的资源量为xi,设资源总数m.

3.已知资源函数与收益函数分别为gi(xi).

2 基本算法讨论

我们可以用动态规划的方法来处理这类问题．

1)将每个项目的投资看成是动态规划的一个阶段．

2)将每个项目的投资数x确定为状态变量．

3)将收益函数(或投入函数)gk(y)看作阶段指标,前k-1个区位上x-y个项目所产生的最大收益(或最小投入)fk(x-y)即为最优指标函数．

4)显然原俩问题是要求fn(m)．

由此,我们得到动态规划的递Bellman推式(依顺序解法)

求fn(m)

3 应用举例

(1)利润最大化问题

实例1:设有某种资源5个单位,可以投入4种生产,可以获得利润如下表1所示:

表1 各单位利润

问如何分配资源,使得总利润最大．

有f0(y)=0,所以f1(x)=g1(y)由以下递推式得阶段寻优表．

表2 利润最大化

从表2可以得出最大利润为f4(5)=14,最优解为x1=3,x3=2,x2=x4=0;

或x1=4,x3=1,x2=x4=0;

所以最优决策为投资第一项目3个资源,第三个项目2个资源,其他项目0个资源,或第一个项目4个资源,第三个项目1个资源,其它项目0个资源,最大利润为14．

(2)最小化问题

实例2某一警卫部门工有九支巡逻队,负责A,B,C三个要害部门的巡逻,对每个部门可以派出2～4支巡逻队,其中预期损失如下表3所示,问如何分派巡逻队可以使得总损失最小．

表3 预期损失 (单位为:万元)

设xk为第k个部门所派的巡逻队的数目,sk为前k-1个部门的巡逻队的数目,则有sk=sk+1-xk用顺序解法我们有如下递推式:

表4 最小损失

由表4我们可以知道最小损失为f3(s4)=69(万元)

最优决策为x1=3,x2=4,x3=2或x1=4,x2=3,x3=2,即警卫部门应该在A区派3支巡逻队,在B区派4支巡逻队,在C区派2支巡逻队,或在A区派4支巡逻队,在B区派3支巡逻队,在C区派2支巡逻队．这样才能使得预期损失最小．

4 结束语

简表法实际上是将动态规划的问题在表上实现,对于状态变量是自然数的这一类整点问题,利用简表法较Bellman递推式法,在处理数据方面更加有条理,由阶段最优点寻找整体最优决策更方便．总之,简表法对于很多种资源分配问题和设点问题都是行之有效的．

[1] 罗荣桂.新编运筹学题解[M].武汉:华中科技大学出版社,2002

[2] 胡运权.运筹学基础与应用[M].北京:高等教育出版社,2004

[3] 程丛电,唐恒永.一类资源分配与排序问题[J].数学实践与认识,2006(1):5-28

[4] 徐玖平,胡知能,李 军.运筹学[M].北京:科技出版社,2004

A Type of Resourse Allocation Problem with Abridged Table to Deal with

Li Chenggeng, Liu Bo

(Department of Mathematics and Applied Mathematics,Hanshan Normal University,Chaozhou 521041, China)

To aim at the problem of set-point in the macro-management and systems organization, give a thought which transform the problem of static progromming to the problem of dynamic progromming. furthermore,we can resovle the problem of stage optimization with the method of abridged table, so we also can obtain the optimum solution of resourse allocation problem.

set-point decision;static programming;dynamic programming;optimal strategy;stage optimization

2014-11-25 基金项目:韩山师范学院2013年“创新强校工程”科研与学科建设项目．

李承耕(1969-),男,湖北云梦人，硕士,韩山师范学院讲师,主要从事非线性泛函理论研究．

1672-2027(2015)01-0017-03

O221.3

A