马锦娟， 姚晓鹏， 郑 挺

(浙江工商大学 统计与数学学院，杭州 310018)

1 引 言

1951年美国学者Richard.Bellman提出了动态规划,用以解决各类多阶段决策问题[1]. 其基本原理是Bellman的最优性定理并由此导出的最优性原理[2]. 其求解步骤:首先建立问题的动态规划模型(划分阶段,选择问题的状态变量和决策变量,列出状态转移方程,描述问题的指标体系,列出动态规划方程).其次,递推计算(按所列出的动态规划方程分阶段逐一计算).最后,以递推计算结果为基础,以状态转移方程为纽带,按与递推计算相反方向寻找最优策略[3].对一类资源平行分配问题,文献[4]给出一种匈牙利方法.由资源平行分配的特点,我们根据人数少于任务数的指派模型(非标准指派模型[3])给出一种求解的方法.

2 人数少于任务数的指派模型

设有n人,m项工作(n≤m),每人可做多项工作,每项工作只被一人做.效率(或损失)矩阵为

问如何安排可使总的效率达到最大(或损失最小).

设

则该问题的线性规划模型:

3 资源平行分配问题的“人数少于任务数的指派模型”求解方法

为了叙述方便,首先给出

定义[5]设n,n1,n2,…,nk均为正整数,称n=n1+n2+…+nk为整数n的一个k分部的分拆.若该分拆与n1,n2,…,nk的顺序有关,则称为有序分拆;否则称为无序分拆.另外,若对ni(i=1,2,…,k)有限制,则称为有限制分拆,否则称为无限制分拆.

在资源平行分配中,正整数n的分拆中允许ni=0(i=1,2,…,k).

对于资源总量为n,被分配的部门数量为k及效率(或收益或损失等)矩阵为A=(aij)(aij表示第j部门分配到第i种资源的数量……