动态规划人员分配算法研究

邓竞伟

（西北民族大学数学与计算机科学学院，兰州　730030）

动态规划人员分配算法研究

邓竞伟

（西北民族大学数学与计算机科学学院，兰州730030）

0　引言

近年来，突发事件频繁发生，对突发事件的应急管理也引起了国家的高度重视，例如，2014年，云南鲁甸6.5级地震灾害，9月重庆洪涝灾害，新疆和田7.3级地震灾害动态规划在许多领域中得到越来越广泛的应用，例如经济领域、工程技术领域、交通领域等，特别是在世界各地的资源分配中应用更为普遍。在资源分配中应用动态规划可以使资源得到充分的应用，可以得到更大的效益。用动态规划解决资源分配问题是把复杂的问题划分为若干个阶段，并逐步解决，最终达到全局最优［1］。Dechter等人分析了常用的Floyd-Warshall算法［2］，从二十世纪五十年代初美国数学家R.E.Bellman［3］等在研究多阶段决策过程的优化问题时，提出了著名的最优化原理。现实生活中已经证明许多问题用动态规划求解比用线性规划更有效［4］。经过多年的科研发展和实际应用，动态规划日益完善。近几年，在我国动态规划应用越来越普遍，例如：1991年，林学钛［5］等对平顶山市地表水和地下水的联合管理研究中，运用动态规划方法对白龟山水库进行优化调度，取得了良好的效果。实践证明，将最短路径问题、资源分配利用、排序等问题，运用动态规划比其他方法更为方便。我们研究资源分配应用中的优、缺点，能够使资源得到充分利用，提高资源利用率并创造更大的利润，可以为动态规划在其他领域的应用中提供了很好的帮助。

1　算法实现

在人工智能领域中，现实生活中的大多数问题可以转化为约束满足规划调度问题来解决［4-5］。动态规划应用十分广泛，本文主要研究动态规划在资源分配中的应用，建立模型是解决资源分配问题的方法之一。数学模型是指对于现实世界的一个特定对象，为了一个特定目标，根据特有的内在规律，做出一些很有必要的假设，运用适当的数学工具得到的一个数据结构［5-6］。

动态规划系统的最优化是用来解决具有一定序列的确定性系统和随机性系统等的最优化问题。最优化决策是不考虑初始状态的，根据最优化过程以相反的顺序进行的特点，因此，对系统的每个元素按同样的顺序进行编写号码。建立一个合理的动态规划模型，需要从以下几个方面进行考虑：

（1）把问题按时间的先后顺序划分为若干个阶段，选出阶段变量，这些阶段必须是有顺序的。

（2）选出状态变量，因为状态变量能够表示整个过程的状态转移规律。

（3）选出决策变量，然后，根据状态之间的递推关系得出最终的状态转移方程。

（4）建立指标函数和列出动态规划方程，给出最终条件；然后，用逆推的方法推出各个阶段的最优决策，再按顺序求出整个问题的最优决策，动态规划的基本方程的逆序形式为［6］：

在具体求解时，从边界条件n=k开始，从前向后逆推逐个阶段求出最优决策和每个过程的最优值，一直到求出f1（x1）的解就是计算具体问题的最优解。

2　具体实例

根据具体实例来分析动态规划在资源分配中的具体应用。例如，某一个公司有A、B、C，3个车间，现在此公司有4位员工要分配到3个车间，已知各个车间获得这种设备所能创造的利润，如表1所示：

表1　员工数与创造的利润

此时，考虑如何将这4位员工分配到3个车间才能使此公司得到最大的利润。

首先，假设3个车间分别为A、B、C，其中，x表示从第i个车间分配到第j个车间的员工数，xi表示分配到第i个车间的员工总数，由此可以得到，从第i+1个车间分配到第j个车间的员工总数为：xi+1=x-xi；fi（x）表示将x位员工从第i个车间分配到第j个车间所得到的利润；gi（xi）表示将xi位员工分配到第i个车间所得到的利润。因此，可以得出动态规划模型为：

当i=3时，就是把4位员工都分给第3车间，

同理，当i=2时，就是把4位员工分给第2和3车间，

那么当x=0时，

此时最优决策方案为：d2（x2）=0。

当x=1时，

此时最优决策方案为：d2（x2）=1。

当x=2时，

此时最优决策方案为：d2（x2）=2。

当x=3时，

此时最优决策方案为：d2（x2）=0。

当x=4时，

此时最优决策方案为：d2（x2）=1。

当i=1时，即将公司员工分配给第1和2车间；

同理可得：

此时最优决策方案为：d2（x2）=0。

此时最优决策方案为：d2（x2）=0。

此时最优决策方案为：d2（x2）=0。

此时最优决策方案为：d2（x2）=0或1。

此时最优决策方案为：d2（x2）=2。

因此，可以看出最优分配方案有两种：

第一种：第1个车间不分配员工，4位员工分别分配给第2和3车间，当i=2时，发现f2（4）的最优规划决策方案所得利润最高。所以，应分配1位员工到第2车间，分配3位员工到第3车间。

第二种：第3个车间不分配员工，4位员工分别分配给第1和2车间，当i=1时，发现f1（4）的最优规划决策方案所得利润最高。所以，应分配2位员工到第1车间，分配2位员工到第2车间。

从上面分析可以看出，在这两种分配方案中，A、B、C，3个车间的总效益都是15。

3　结语

动态规划在资源分配中已经被广泛应用，这说明动态规划是在解决资源分配这类问题的有效方法。在资源的分配决策中，动态规划使得资源的利用率最高，避免了资源的浪费，从而可以使有限的资源创造出最大的经济利润。动态规划的应用为我们解决了很多实际问题，对如何建立应急资源管理机制也具有很好理论基础和现实意义。

［1］徐瑞，徐晓飞，崔平远.基于时间约束网络的动态规划调度算法.计算机集成制造系统-CISM［J］，2004.10（1）：188-194.

［2］Muscettola N，Nayak P P，Pell B，Williams B.Remote agent：to boldly go where no AI system has gone before［J］.Artificial Intelligence.1998.103（1-2）：5-47.

［3］滕宇，梁方楚.动态规划原理及应用［M］.西南交通大学出版社.2011.12.

［4］袁佳乐，黄兆华，曹玉红.动态规划在资源分配上的应用.西安文理学院学报：自然科学版［J］，2008，11（3）：66-69.

［5］卢向南.应用运筹学［M］.浙江大学出版社，2005.

［6］孙宝，王希云.基于MATLAB的动态规划常用算法的实现.太原师范学院学报（自然科学版），2008，7（4）：26-30.

Dynamic Algorithm；Policy Decision；Planning and Scheduling；Resource Allocation

Research on Dynamic Planning Assignment Algorithm

DENG Jing-wei

（School of Mathematics and Computer Science，Northwest University for Nationalities，Lanzhou 730124）

教育部人文社会科学研究青年基金项目（No.13YJCZH029、No.12YJCZH027）、中央高校基本科研业务费专项资金项目（No.31920150039）

1007-1423（2015）26-0046-03

10.3969/j.issn.1007-1423.2015.26.012

邓竞伟（1980-），女，甘肃兰州人，硕士，研究方向为最优化理论、算法设计与分析

2015-08-04

2015-09-08

如何快速准确地进行资源调度是突发事件应急资源的重要研究问题，并且及时有效的资源供给促进救援工作的顺利进行。动态规划在许多领域中都得到十分广泛的应用。介绍动态规划方法、最优化原理和动态规划模型，并通过实例进行分析和讨论。

动态算法；决策；规划调度；资源分配

How to carry out resource scheduling is the important research problem of the emergency resources，and the timely and effective resources supply to promote the smooth progress of the rescue work.Dynamic programming is widely used in many fields.Introduces the dynamic programming method，the optimization principle and the dynamic programming model，analyzes and discusses the examples.