动态规划模型在指派问题中的应用

毕业论文

（ 2012 届本科）

题 目： 动态规划模型在指派问题中的应用 学 院： 数学与统计学院 专 业： 数学与应用数学 作者姓名： 景诚 指导教师： 李拓 职称： 副教授 完成日期： 2012 年 5 月 30 日

二○一二年 五 月

动态规划模型在指派问题中的应用

景诚 指导教师:李拓

(河西学院 数学与应用数学专业 2012届3班13号 甘肃张掖 734000)

摘 要 本文利用动态规划的基本理论和方法, 考虑了两类一般的非标准指派问题, 对它们进行了总结和归纳, 得出了一类更一般的非标准指派问题. 通过实例, 运用所建立的动态规划模型对其进行了求解.

关键词 动态规划; 多阶段决策问题; 指派问题; 目标函数. 中图分类号 O224

Application of the Dynamic Programming Model in Assignment

problem

Jing Cheng Instructor Li Tuo

(NO.13,Class 3 of 2012.Specialty of Mathematics and Applied Mathematics ,

Hexi University,Zhangye,Gansu,734000)

Abstract: This paper using the basic theory and the Dynamic programming method considers the two kinds of generally non-standard assignment problem,summarizes and concludes them, finally it draws the conclusion that reaches a class of more general than standard assignment problem.Throughout the example, using the dynamic programming model gets its conclusion. Keywords: The Dynamic Programming Model; Multi stage decision problem; The Assignment problem; Objective function.

1 引言

动态规划是解决多阶段决策过程最优化的一种方法, 它是由美国数学家贝尔曼（Richard Bellman)等人在1951年提出来的, 他们针对多阶段决策问题的特点, 提出了解决这类问题的最优化原理, 并成功解决了生产管理、工程技术中遇到的许多决策问题.在现代社会中, 动态规划已经成为企业管理中的一种重要决策方法, 人们用它能解决很多棘手的问题, 如最优路径的选择、资源的最优分配、生产计划的最优决策等等. 在现实生活中, 我们还经常会遇到这种情况: 有m项工作, 每一项工作可以由一人完成, 同时有n个人, 每一个人可以完成一项工作. 要确定完成m项工作效率最高

1

或者总工时最小的分配工作方案, 此问题被称为是标准指派问题, 即当mn时的指派问题. 但我们在解决实际问题时常常还会遇到下列情况, 即人们在工作的分配过程中, 有以下特征之一的指派问题: (1)工作项目数与人数不相等; (2）某人不能做某项工作（某事不能由某人做, 无法接受的指派）; (3)某人可以同时被指派多个任务; (4)某事可以由多人共同完成; (5)目标函数是与指派有关的总效用最大或最小的函数. 该类指派问题被称为是非标准指派问题. 由于指派问题也是属于多阶段决策问题, 所以本文主要利用动态规划的基本原理和方法解决一类较一般的非标准指派问题, 即有m项工作欲指派n个人去做,当mn时, 要求每项工作只能由一个人去做, 第i个人可以同时做bi项工作（某人可以同时被指派多个任务）, 其中bi是待求未知数, 满足dibiei (ei,di为第i个人所需工作数的上下限) 及bim(即每个工作都有人做), ei,di为已

i1n知常数(i1,2,...,n); 当mn时, 要求每个人只做一项工作,第i项工作可以由bi个人共同去做（某事可以由多人共同完成）, 其中bi是待求未知数,满足dibiei(ei,di为第i项工作所需人数的上下限)及bin(即每个人都有工作), ei,di为已知常数

i1m(i1,2,...,n); 第i个人做第j项工作所用的工作时间或工作效益为cij0, (i1,2,...,n;j1,2,...,m). 确定使总耗用时间最少或使总效益最大的指派问题. 记上述

问题为P. 当mn且1dieim时, 问题P便是[1,2]中的问题. 当mn且

1diein时, 问题P便是[3,4]中的问题. 所以问题P是一类更一般的非标准指派问

题, 在经营管理实践中更有意义. 本文将应用所总结归纳的动态规划模型对这一类非标准指派问题进行求解, 并用匈牙利法[5]对其进行检验, 说明本文所运用方法的正确性.

2 预备知识

定义2.1[6,7,8] （多阶段决策过程）多阶段决策过程是一类特殊的活动过程, 这个过程可以按时间顺序分解成若干相互联系的阶段, 我们把它称之为“时段”, 在每一个时段上都要作出决策, 全部过程的决策构成了一个决策序列. 多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优. 由于各阶段决策间有机地联系着, 一个阶段决策的执行将影响到下一阶段的决策, 以至于影响总体效果, 所以决策者在每个阶段决策时不应仅考虑单个阶段最优, 还应考虑对最终目标的影响, 从而作出对全局来讲是最优的决策. 而动态规划就是符合这种要求的一种决策方法. 动态规划方法与“时间”关系很紧密, 随着时间过程的发展而决定各时段的决策, 产生一个决策序列,

2

这就是“动态”的意思. 然而它也可以处理与时间无关的静态问题, 只要在问题中人为地引进“时段”因素, 将问题看成多阶段的决策过程即可.

用动态规划方法解决多阶段决策问题,首先要将实际问题写成动态规划模型, 此时要用到以下概念: 1、阶段; 2、状态; 3、决策; 4、策略; 5、状态转移方程; 6、阶段指标函数; 7、过程指标函数; 8、最优指标函数. 这里用一个最短路的简单例子来说明这些概念.

下图是给定是一个线路网状图, 选择从A地到D地去的最短路线. 如图1所示.

图1

定义2.2[6,7,8] （阶段）将所给问题的过程, 按时间或空间特征分解为若干相互联系的阶段, 以便按照次序去求解每阶段的解, 每个阶段就是一个子问题, 常用字母k表示阶段变量. 上例中, 从A到D可以分成A到B, B到C, C到D三个阶段. 即

k1,2,3.

定义 2.3[6,7,8] （状态）状态是我们所研究的问题在各个阶段的初始形态或客观条件, 而描述各阶段状态的变量称为状态变量, 常用xk表示第k阶段的状态变量, 状态变量xk的取值集合称为状态集合, 用Xk表示. 在上例中,

X1A,X2B1,B2,B3,X3C1,C2,C3,X4D.

动态规划中的状态应具有如下性质: 当某阶段状态给定以后, 在这阶段以后过程的发展不受这一阶段以前各阶段状态的影响. 也就是说, 当前状态是过去历史的一个完整总结, 过程的过去历史只能通过当前状态去影响它未来的发展, 这称之为无后效性. 如果选择的变量不具备无后效性, 就不能作为状态变量来构造动态规划模型. 当某一阶段的初始状态已选定某个点时, 从这个点以后的路线只与该点有关, 不受以前路线的影响,所以满足状态的无后效性.

定义2.4[6,7,8] （决策和策略）当各段的状态取定以后, 就可以作出不同的决策,从而确定下一阶段的状态, 这种决策的变量, 称之为决策变量, 常用uk(xk)表示第k阶段当状态为xk时的决策变量. 在实际问题中, 决策变量的取值往往限制在一定的范围

3

内, 我们称这个范围为允许决策集合, 常用Uk(xk)表示第k阶段从状态xk出发的允许决策集合,显然, ukUk(xk). 在上例中, 从第二阶段的状态B2出发, 可以选择下一阶段的C1,C2. 即允许决策集合为

U2(B2)C1,C2.

如果决定选择C2, 则可表示为

u2(B2)C2.

各阶段决策确定以后, 整个问题的决策序列就构成一个策略. 对于每一个实际问题而言, 可供选择的策略也有一定的范围, 称之为允许策略集合, 记作p1,n, 使整个问题达到最优效果的策略就是最优策略.

定义2.5[6,7,8] （状态转移方程）动态规划中一个阶段的状态往往是上一个阶段的状态和决策的结果. 如果给定了第k阶段的状态xk, 本阶段决策为uk(xk), 则第k1段的的状态xk1也就完全确定. 它们的关系可表示为

xk1Tk(xk,uk),

由于它表示了由k段到k1段的状态转移规律,所以称之为状态转移方程. 在上例中,状态转移方程为

xk1uk(xk).

定义2.6[6,7,8] （阶段指标函数）假设第k阶段的状态为xk, 当执行了决策uk时,除带来系统状态的转移之外,还产生第k阶段的局部效益,它是所求总效益的一部分, 称之为阶段指标函数, 记作gk(xk,uk).

定义2.7[6,7,8] （指标函数）用于衡量所选定策略优劣的数量指标称为指标函数.一个n阶段决策过程, 从1到n叫作问题的原过程, 对于任意一个给定的k(1kn), 从第k阶段到第n阶段的过程称为原过程的一个后部子过程. v1,n(x1,p1,n)表示在第1阶段,状态为x1采用策略p1,n时原过程的指标函数值, 而vk,n(xk,pk,n)表示在第k阶段,状态为xk采用策略pk,n时后部子过程的指标函数值. fk(xk)表示从第k阶段状态xk采用

*最优策略pk,n到过程终止时的最优值函数. fk(xk)与vk,n(xk,pk,n)间的关系为

*fk(xk)vk,n(xk,pk,n)optvk,n(xk,pk,n),(opt意为最优).

pk,npk,n当k1时, f1(x1)就是从初始状态x1到全过程结束的整体最优函数.

在所给例子中, 指标函数用来衡量策略优劣的数量指标就是距离. 求解最小距离就是所要解决的问题.

综上所述, 我们在运用动态规划解决问题的时候可以采取的方法步骤[6,7,8]为 <1>将多阶段决策过程划分阶段, 恰当地选取状态变量、决策变量,定义最优指标

4

函数, 从而把问题化成一簇同类型的子问题,然后逐个求解.

<2>求解时从最后阶段开始, 逆过程方向行进,逐段递推寻优, 在每一个子问题求解时, 都要使用它前面已求出的子问题的最优结果, 最后一个子问题的最优解, 就是整个问题的最优解.

定理2.1[8,9] （最优化原理）对于最优策略过程中的任意状态而言, 无论其过去的状态和决策如何, 余下的诸决策必构成一个最优子策略.

3 所讨论非标准指派问题的动态规划模型的建立和求解步骤

对于问题P而言, 由于分配的过程是顺序进行的, 所以它具有可分性,因此可以对其建立动态规划模型.

建立动态规划模型如下

(1)阶段变量: k1,2,,n,表示给n个人指派工作的顺序;

(2)状态变量: xk (xk为整数, 这里以工作为状态)表示第k阶段初剩余的工作数, 亦即给第k个人指派工作前剩余的工作数. 假定全体工作按1,2,...,m编号, 记sk(xk)表

1,2,...,m, 示为第k阶段初工作数为xk对应xk项工作的编号集, 则s1(x1)sn1(xn1). 记Tk(xk)sk(xk)表示在第k阶段初工作数为xk时, xk项工作所有可

能的编号集, 则T1(x1)s1(x1).

(3)决策变量: uk (uk为整数)表示指派给第k(k1,2,,n)阶段的工作数; 即uk为指派给第k人的工作数.

(4)允许决策集合: Uk(k1,2,,n) 表示第k阶段决策变量可能的取值; 显然,

1,2,,n . 根据决策变量的定义易得: U1(5)状态转移方程

x1mxk1xkuk(k1,2,...,n1). (1) x0n1 因为从第k阶段到第n阶段至少应有di个工作数, 从第1阶段到第k1阶段至

ikn少可剩余mei个工作数, 从第k阶段到第n阶段至多安排ei个工作数, 从第1阶

i1k1nik段到第k1阶段至多可剩余mdi个工作数, 因此:

i1k1(6)状态集合

5

X1x1x1mk1nk1nXxmaxme,dxminmd,e,x为整数kk,k2,3,...,n.(2) iikiiki1iki1ikXxx0n1n1n1(7)允许决策集合

nnU(x)umaxd,xeumine,xd,u为整数kkkkkikkikkik1ik1 (3)

Un(xn)undnunxn,k1,2,...,n1.***和工作,u2,...,un记策略Wu1,u2,...,un, 则最优指派即是确定最优策略W*u1的具体分配方案, 使biu, 满足biui*m且保证使总耗时最少或者总效用最

*inni1i1大.

(8)指标函数: 用vk(uk,sk(xk))表示从第k阶段的决策变量为uk且工作编号集为

sk(xk)时从第k阶段到第n阶段的最优指标, 即从sk(xk)中指派ukUk(xk)项工作给

第k个人时, 从第k个人至第n个人完成所指派的工作所耗用的时间或所得到的效用.

(9)最优值函数fk(sk(xk))optvk(uk,sk(xk))表示在第k阶段工作编号集为

sk(xk)时, 从第k阶段到第n阶段对应最优策略时的总耗用时间或者总效用

(kn,n1,...,2,1). 因此, f1(s1(x1))f1(s1(m))即表示n个人完成全部指派工作所耗用

的最少时间或者最大效用. 故只需求出f1(s1(x1)), 并给出相应的工作分派即可. 由动态规划的最优性原理, 可以建立如下的动态规划方程

fk(sk(xk))optvk(uk,sk(xk)) , (4) ukUk(xk)(k1,2,...,n)f(s(x))0n1n1n1其中,vk(uk,sk(xk))是下列问题的最优值

vk(uk,sk(xk))optckjxkjfk1(sk1(xk1))xkjuk . (5) jsk(xk)其中xk1xkukx1第k个人做第j项工作，j1,2,...,m;k1,2,...,nkj0第k个人不做第j项工作.记Ik(xk)表示分派给第k个人的工作编号(kn,n1,...,2,1). 由动态规划方程(4), (5)逆推可求得最小耗用时间或者最大工作效用f1(s1(x1)), 再沿计算过程反向查找可

***), 则Ik(xk)即为分派给第得第k阶段的最佳状态变量xk及对应的最佳工作编号sk(xk**(sk(xk))即为第k阶段的最优分派工作数. k个人的最佳工作, bkuk 6

综上分析问题P的计算步骤如下 Ⅰ、kn;

Ⅱ、①写出xk的所有可能值②对每一个xkXk给出Uk(xk)和Tk(xk)③对每个

sk(xk)Tk(xk)由公式(4), (5)求fk(sk(xk));

Ⅲ、若k1, 转Ⅳ, 否则kk1转Ⅱ;

*Ⅳ、最小耗用时间或最大工作效用为f1(s1(x1)), 最佳状态变量值为xk, 第k个人***), 工作数bkuk(sk(xk))(kn,n1,...,2,1). 分派的最佳工作为Ik(xk

4 动态规划在解决非标准指派问题中的应用

4.1 问题描述

某公司拟将四名技术员工分配到甲、乙、丙三个工作点工作, 每个人在各个工作点的效用如表1所示, 已知第一个人工作数b1满足1bi2, 问该公司如何分配员工才能使得三个工作点的总效用为最大？

表一

工作 技术员工 0 1 2 3 4

问题分析

甲 0 4 9 7 10 乙 0 7 6 3 11 丙 0 5 3 8 13 这个问题属于问题p范畴. 已知条件是必须保证每个人都有工作, 对此需要做出三个相关的决策, 即有多少个技术员工分配到三个工作点中的每一个. 工作的分派过程具有明显的顺序性, 因此可以用已建的动态规划模型求解. 以人员为状态变量, 并

1,2,3,4, 记为sk(xk). 对人员进行编号题目是使最大化效用的指派问题, 所以在已建模型中, 方程(4)应变为 fk(sk(xk))maxvk(uk,sk(xk)). ukUk(xk)(k1,2,...,n)f(s(x))0n1n1n1方程(5)应变为

7

vk(uk,sk(xk))maxckjxkjfk1(sk1(xk1))xkjuk. jsk(xk)其中xk1xkukx1第k个人做第j项工作，j1,2,...,m;k1,2,...,nkj0第k个人不做第j项工作.求解过程

该指派问题的效用矩阵为

475963. 738101113C(cij)nm解 (1) k3, X3x3x31或2, U3(1)u3u31, U3(2)u3u31或2.

1,2,3,4, ①x31,u31, T3s3(x3) *u3(s3(x3)) v3(u3,s3(x3)) f3(s3(x3)) I3(x3) 1 2 3 4

5 3 8 13 5 3 8 13 1 1 1 1 1 2 3 4 1,2,1,3,1,4,2,3,2,4,3,4. ②x32,u32, T3(2)s3(x3) v3(u3,s3(x3)) f3(s3(x3)) *u3(s3(x3)) I3(x3) 1,2 1,3 1,4 2,3 2,4 3,4

8 13 8 13 2 2 18 18 2 2 11 16 11 16 2 2 21 21 1,2 1,3 1,4 2,3 2,4 3,4 (2)k2, x2x2x21或2, U2(1)u2u21, U2(2)u2u22.

1,2,1,3,1,4,2,3,2,4,3,4, ①x22, u21, T2(2)s2(x2) v2(u2,s2(x2)) f2(s2(x2)) *u2(s2(x2)) I2(x2) 1,2

11 11 1 2 8

1,3 1,4 2,3 2,4 3,4

15 15 1 20 20 1 1 14 19 19 14 19 19 1 1 1 1 2 2 4 1,2,3,1,2,4,1,3,4,2,3,4. ②x23, u21或2, T2(3)s2(x2) v2(u2,s2(x2)) u21 u22 f2(s2(x2)) *u2(s2(x2)) I2(x2) 1,2,3 1,2,4 1,3,4 2,3,4

19 23 28 27 21 26 26 25 21 26 28 27 2 2 1 1 1,2 1,2 1 2 1,2,3,4. (3)k1, x1x1x14, U1(4)u1u11或2, T1(4)s1(x1) v1(u1,s1(x1)) u11 u22 f1(s1(x1)) *u1(s1(x1)) I1(x1) 1,2,3,4 37 36 37 1 2 由上述过程反查表得

****s1(x1)1,2,3,4时, b1u1(s1(x1))1, I1(x1)2; ****(s2(x2))1, I2(x2)1; s2(x2)1,3,4时, b2u2****(s3(x3))2, I3(x3s3(x3)3,4时, b3u3)3,4.

成效评价

由上述分析可以得知, 最优分配方案为: 第2个人做甲工作, 第1个人做乙工作, 第3个人和第4个人去做丙工作, 这时的效用37为最大.

问题检验 匈牙利法检验过程

当第一个工作点必须由两人来做时（见图2）

9

图2

最大效用为: 9+7+7+13=36

当第一个工作点由一人来做, 第二个工作点由两人来做时（见图3）

图3

最大效用为: 9+7+11+8=35

当第一个工作点由一人来做, 第三个工作点由两人来做时（见图4）

图4

最大效用为: 9+7+8+13=37

综上所述最大效用为37, 这跟题目所得结果相同, 所以解法正确.

10

4.2 问题描述

某有色金属公司欲派出三名专家A、B、C将对所属五家冶炼厂（编号为1厂、2厂、3厂、4厂、5厂）进行技术改造,由于人手不够, 该公司只能根据每位专家对各个冶炼厂进行技术改造的时间来加快整体工作进程. 要求人员分配时第一个人的工作数

bi必须满足2bi3, 问怎样安排人员才可以使得整体工作进程加快? 已知各个专家

对每个厂技术改造时所用的时间矩阵如下所示

5971312. C(cij)nm67161410681297问题分析

很显然, 该问题属于问题p范畴, 因此可以运用已建的动态模型来对该问题进行求解. 这里以工作为状态变量, 按三个专家的分为三个阶段. 用sk(xk)表示第k阶段初工作数为xk时对应xk项工作的编号集, Tk(xk)sk(xk)表示在第k阶段初工作数为

xk时, xk项工作所有可能的编号集.

题目是使所耗时间最少的指派问题, 所以在已建模型中, 方程(4)应变为

fk(sk(xk))minvk(uk,sk(xk)). ukUk(xk)(k1,2,...,n)f(s(x))0n1n1n1方程(5)变为

vk(uk,sk(xk))minckjxkjfk1(sk1(xk1))xkjuk. jsk(xk)其中xk1xkukx1第k个人做第j项工作，j1,2,...,m;k1,2,...,nkj0第k个人不做第j项工作.求解过程

解 (1)k3, x3x3x31或2, U3(1)u3u31, U3(2)u3u32.

1,2,3,4,5, ①x31, u31, T3s3(x3) *u3(s3(x3)) v3(u3(x3)) f3(s3(x3)) I3(x3) 1 2 3 4 5

6 8 6 8 1 1 1 1 1 12 9 12 9 7 7 11

1 2 3 4 5

1,2,1,3,1,4,1,5,2,3,2,4,2,5,3,4,3,5,4,5. ②x32, u32, T3(2)s3(x3) v3(u3(x3)) f3(s3(x3)) *u3(s3(x3)) I3(x3) 1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5

14 18 15 13 20 14 18 15 13 20 2 2 2 2 2 2 2 2 2 2 17 15 17 15 21 19 16 21 19 16 1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5 (2)k2, x2x2x22或3, U2(2)u2u21, U2(3)u2u21或2.

1,2,1,3,1,4,1,5,2,3,2,4,2,5,3,4,3,5,4,5, ①x22, u21, T2(2)s2(x2) v2(u2(x2)) f2(s2(x2)) *u2(s2(x2)) I2(x2) 1,2 1,3 1,4 1,5 2,3 2,4 2,5 3,4 3,5 4,5

13 18 15 13 19 16 13 18 15 13 19 16 1 1 1 1 1 1 1 14 25 14 25 1 1 22 19 22 19 1 2 1 1 1 2 2 2 3 5 5 ②x23u21或2,

T2(3)1,2,3,1,2,4,1,2,5,1,3,4,1,3,5,1,4,5,2,3,4,2,3,5,2,4,5,3,4,5. s2(x2)

v2(u2(x2)) f2(s2(x2)) 12

*u2(s2(x2)) I2(x2)

u21 u22 1,2,3 1,2,4 1,2,5 1,3,4 1,3,5 1,4,5 2,3,4 2,3,5 2,4,5 3,4,5

25 25 25 1或2 1或2 1或2 22 20 27 25 22 20 31 28 25 32 29 26 35 22 20 27 25 1 1 1 1 1 1 1 22 28 26 23 31 22 28 26 23 31 1，2或2 1，2或2 1，2或2 1 1 1 2 2 2 5 1,2,3,4,5. (3)k1, x1x1x15, U1(5)u1u12或3, T1(5)s1(x1) v1(u1(x1)) u12 u13 f1(s1(x1)) *u1(s1(x1)) I1(x1) 1,2,3,4,5

35 39 35 2 1,3 由上述过程反查表得

****s1(x1)1,2,3,4,5时, b1u1(s1(x1))2,I1(x1)1,3; ****s2(x2)2,4,5时, b2u2(s2(x2))1,I2(x2)2; ****(s3(x3))2,I3(x3)4,5. s3(x3)4,5时, b3u3成效评价

由上述分析可以知道最优的安排方案为: 把专家A指派到1厂和3厂; 把专家B指派到2厂; 把专家C指派到4厂和5厂; 这样的分派可使工作时间最短, 为35. 其结果可以有效的加快公司的工作进程.

问题检验 匈牙利法检验过程

当第一个人的工作数为两个, 第二个人的工作数为两个时（见图5）

13

图5

最小工作时间为: 5+7+7+10+9=38

当第一个人的工作数为两个, 第三个人的工作数为两个时（见图6）

图6

最小工作时间为: 5+7+7+9+7=35 当第一个人工作数为三时（见图7）

14

图7

最小工作时间为: 5+7+13+7+7=39

综上所述最小工作时间为35, 这与本题动态规划解法所求结果一致, 所以正确. 致谢 衷心的感谢李拓老师在我论文写作时给予的精心指导.

参 考 文 献

[1]王吉波,王明坤.一类最优指派问题的动态规划算法[J].沈阳师范学院学报(自然科学版),2002,20(4):266-270.

[2]李苏北.一类最优指派问题的动态规划解法[J].运筹与管理,2000,9(1):69-73.

[5]秦学志,王雪华.一类最优指派问题的动态规划模型[J].数学的实践与认识,1996,26(3):212-216. [4]王雪华.关于“一类最优指派问题的动态规划模型”的注记[J].数学的实践与认识,2000,30(2):147-149.

[5]孙麟平.运筹学[M].北京:科学出版社,2006. [6]孔造杰.运筹学[M].北京:机械工业出版社,2006. [7]杨文鹏,贺兴时,杨选良.新编运筹学教程---模型、解法及计算机实现[M].西安:陕西科学技术出版社,2005.

[8]吴祈宗.运筹学[M].北京:机械工业出版社,2006.

[9](美)弗雷德里克.S.希利尔,杰拉尔德.J.利伯曼.运筹学导论[M].北京:清华大学出版社,2007.

15