小型微塑计算机系统
２００９年４月第４期
ＪｏｕｒｎａｌｏｆＣｈｉｎｅｓｅＣｏｍｐｕｔｅｒＳｙｓｔｅｍｓ
Ｖ０１．３０
Ｎｏ．４
２００９
任务分配问题的建模与求解
聂明泓１，杨丽英２，聂义勇２
１（沈阳神州数码有限公司，辽宁沈阳１１０００４）
２（中国科学院沈阳自动化研究所机器人学国家重点实验室．辽宁沈阳１１００１６）Ｅ－ｍａｉｌ：ｎｉｅｍｈ＠，ｄｉｇｉｔａｌｅｈｉｎａ．ｃｏｍ
摘要：建立了极大极小任务分配问题的混合整数线性规划模型，提出一种矩阵作业解答。并与穷举解及混合整数线性规划解的计算复杂度进行了比较．理论分析和数值试验表明矩阵作业法对两类任务分配问题。极大极小和总体极小任务分配问题，有效地提供最优解．
关键词：任务分配问题；穷举法；混合整数线性规划；松弛线性规划；矩阵作业法中图分类号：ＴＰｌ８
文献标识码：Ａ
文章编号：１０００—１２２０（２００９）０４．０７１０－０６
Ｍｏｄｅｌｌｉｎｇ
ａｎｄＳｏｌｕｔｉｏｎｆｏｒＡｓｓｉｇｎｍｅｎｔＰｒｏｂｌｅｍ
ＮＩＥ
Ｍｉｎｇ－ｈｏｎ９１，ＹＡＮＧＬｉ—ｙｉｎ９２，ＮＩＥＹｉ—ｙｏｎ９２
１（ＳｈｅｎｙａｎｇＤｉｇｉｔａｌＣＭｎａＬｉｍｉｔｅｄ。Ｓｈｃｎｙａｎｇ１１０００４，Ｃｈｉｎａ）ｚ（ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙ
ｏｆＲｏｂｏｔｗｓ。Ｓｈｅｎｙａｎｇ
Ｉｎｓｔｉｔｕｔｅ
ｏｆＡｕｔｏｍａｔｉｏｎ，Ｓｈｅｎｙａｎｇ１１００１６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｍｉｘｅｄｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ（ＭＩＬＰ）ｏｆｍｉｎｉｍａｘａｓｓｉｇｎｍｅｎｔｉｓｆｏｒｍｅｄ・ａｎｄａｓｏｌｕｔｉｏｎｃａｌｌｅｄ
Ｏｐｅｒａｔｉｏｎｓ
Ｏｎ
Ｍａｔｒｉｘｉｓｐｒｅｓｅｎｔｅｄａｎｄｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｓｏｌｕｔｉｏｎｓｏｆｅｘｈａｕｓｔｉｏｎａｎｄ
ＭＩＬＰ．Ｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｅｓａｎｄｎｕｍｅｒｉｃａｌ
ｔｅｓｔｓ
ｓｈｏｗｔｈａｔｔｈｅｏｐｅｒａｔｉｏｎｓ
ｏｎ
ｍａｔｒｉｘ
ａｒｅ
ｅｆｆｉｃｉｅｎｔｆｏｒｂｏｔｈｍｉｎｉｍａｘａｎｄｇｌｏｂａｌ－ｍｉｎｉｍｕｍａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍｓ．
Ｋｅｙｗｏｒｄｓ：ａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍｌｍｅｔｈｏｄｏｆｅｘｈａｕｓｔｉｏｎ；ｍｉｘｅｄｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ（ＭＩＩ，Ｐ），ｒｅｌａｘｅｄｌｉｎｅａｒｐｒｏｇｒａｍ－
ｍｉｎｇ（ＲＬＰ）Ｉｏｐｅｒａｔｉｏｎｓ
ｏｎ
ｍａｔｒｉｘ
１引言
划方法又是根据其松弛线性规划方法推导出来的，求解一次（１）的松弛线性规划的运算量通常是ｏ（（ｎ×７１）３』）＝Ｏ（ｎ７），总体极小任务分配问题［１］提法是：有７１项不同的任务，恰因此整数线性规划方法求解（１）不会比匈牙利算法［１］更好．
好７１个人分别承担这些任务Ｉ由于每个人专长不同，各人完成总代价极小的任务分配问题（１）也可以解决总利润极大不同任务所需的代价也不一样；问应该安排哪个人去完成哪的任务分配问题。这只要设一ＣｉＩ为第ｉ个人完成第ｊ项任务所项任务，使完成咒项任务所需总代价最小？
获得的利润就够了．这样。Ｃ＝（ｃｏ）表示负利润矩阵，求解负利总体极小任务分配问题可以用７１２个决策变量描述．令ｏ“润矩阵的总体极小任务分配问题．其目标函数反号就是极大为。一１决策变量，即Ｘｉｊ＝１表示安排第ｉ个人去完成第Ｊ项任总利润．
务，霸ｊ＝０表示不安排第ｉ个人去完成第Ｊ项任务，用ｃｕ表示如果把“代价”理解为成本消耗，那么总体极小任务分配第ｉ个人完成第Ｊ项任务所需的代价（实数），则ｃｔＪ构成已知问题的提法，即（１）的目标函数，是合理的．但若把“代价”理解的刀Ｘ一代价矩阵．我们有
为时间，那么（１）的目标函数就不一定合理了．因为任务分配ｒａｉｎ石＝∑∑Ｃ‘∥廿
好以后．大家在同一时刻开始干活，所以这里的总“时间”统计ｉ－ＩＪｌｌ
＾
已不重要．重要的是挖个人作为一个团队去完成ｎ项任务（每ｓ．ｔ．∑ｚｉｊ＝１，（＿『＝１，…，ｎ）
人完成且只完成一项任务）．要求最后完成全部任务的时间最∑Ｘｉｊ＝ｌ，（ｆ＝ｌ，…，疗）
短．这样，（１）的目标函数应该有所修改。即
ｉ－－ｌ
ｍｉｎ
Ｘｉｊ＝０
ｏｒ
１，ｉ，Ｊ∈Ｎ＝｛１，…，行）
（１）
２一ｍａｘ｛ｃｉｊｘｏ）
ｌ・Ｊ
＾
这是一个整数线性规划问题．如果在（１）中去掉工ｕ一０
ｏｒ
１的
，．ｔ．∑ｘｉｊ＝ｌ，（＿ｆ＝ｌ，．．・，疗）
ｆ－ｌ
约束条件而代之以ｏ≤ｚ，Ｊ≤ｌ，则它就是松弛线性规划问题．■
人们自然可以用整数线性规划的方法，如等量面法［纠．求解
∑Ｘｉｊ＝ｌ，（ｆ＝１，…，行）
ｉ－Ｉ
（１）．但由于这里有恕２个Ｏ一１决策变量柳，而所有整数线性规勘＝０
ｏｒ
１，ｉ，Ｊ∈Ｎ暑｛１，…，ｎ｝
（２）
收穑日期：２００８—０１．２４收修改稿日期：２００８—０５—１３作者简介：聂明泓．男．１９７５年生。研究方向为管理信息系统（ＭＩＳ）和后勤支持系统等，杨丽英，女．１９７９年生．博士研究生，研究方向为动态环境下多移动机器人自治规划和混合线性整数规划等；聂义勇，男，１９３９年生．研究员，研究方向为应用数学和计算机辅助工程等．
万
方数据
４期聂明泓等：任务分配问题的建模与求解
７１ｌ
这就是所谓极大极小任务分配问题的数学模型，它是一个整数规划问题。其中目标函数是非线性的，问题（２）与（１）的解之间无明显联系。直接求解（２）的现成软件很难找到．
本文先分析求解（２）的穷举法；然后将极大极小任务分配问题（２）改进成混合整数线性规划模型并讨论其等量面解法，在此基础上提出求解（２）的矩阵作业法；同时也分析了矩阵作业法对求解（１）的应用；最后用计算复杂度的比较和数值试验表明矩阵作业法求解这两类任务分配问题的高效性．
２求解（２）的穷举法
穷举法的基本思想就是直接或间接比较全部可行解的目标函数，比较完成后自然就找到了全局最优解．可惜一般的整数规划或混合整数规划问题的全部可行解数量随同题规模增长太快（指数次增长），以至任何计算机都无法接受．
以极大极小任务分配问题（２）为例．满足其约束条件的可行解是在，ｌ×恕零元索矩阵中不同行列任置一个元素为ｌ所构成的（五个１所对应的）任务分配ｒ．每个任务分配ｒ的目标函数：是代价矩阵Ｃ一（ｃｄ）中对应于ｌ的极大者．目标函数：最小的任务分配ｒ就是（２）的一个解．解答可能不惟一，但解答的目标函数（最优目标函数）值是惟一的．
令｛ｊｔ，ｊ：，…．＾｝是｛ｌ，２ｔ．．・，刀｝的一个排列．在行×ｎ零元素矩阵的第一行取Ｊ，号元素为１，第二行取ｊｚ号元素为１，…．第一行取＾号元素为１，这样就构成一个可行的任务分配ｒ，其目标函数ｚｒ＝ｍａｘｋｌ，，，‘编，…，‘叽）．
每一个排列｛，．，歹：，…．五｝对应着一个任务分配ｒ，因此任务分配的总数目是ｎ！．按斯特林（Ｓｔｉｆｌｉｎｇ）阶乘公式，当ｎ
足够大时，砣！≈√２，ｒ甩（ｎ／ｅ）‘，表明任务分配的总数随行的增
大而指数次增长．
只要ｎ超过ｌｏ．在ＰＣ机上就不宜用穷举法求解（２）．
一个混合整数线性规划模型
引进一个实变量曲＋ｔ。就可以将极大极小任务分配问题
（２）改进成混合整数线性规划．等价于（２）的混合整数线性规划问题是：
ｒａｉｎｚ＝ｊ，疗＋ｌ
＾
＾ｆ．∑工ｏ＝１，（歹＝１＇．．・，对）
ｉ—ｌ
■
∑ｚ“＝１，（ｆ＝１，…，挖）
ｊ－１
弘＋ｌ一‘玎％≥０。（ｆ。Ｊ＝１＇．．・。靠）
Ｘｉｊ一０
ｏｒ
１。ｉ，Ｊ∈Ｎ兰｛ｌ，…．行）
（３）
求解整数线性规划的等量面法［２］也适合于求解混合整数ｍａｘ：；一弘＋ｌ
ｔ
＾
，．ｆ．∑．劭≥０．８５。一∑工。≥一１．１５（．『＝１＇．．・，露）
万
方数据∑．％≥０．８５，一∑Ｘｉｊ≥一１．１５（ｉ＝ｌ，…。疗）
Ｊ一１
ｊ－－］
儿＋｜－ＣｔｊＸｉｊ≥０，（ｉ，Ｊ＝１，…，７／）
霸，＝０
ｏｒ
１，ｉ，ｊ∈Ｎ兰｛ｌ，…，理）
（４）
等量面法求解（４）的基础也是求解其松弛线性规划（５），（５）中的变量数是ｎ２＋１，约束不等式数目是３ｎ２＋４ｎ・２，因此求解一次松弛线性规划（５）的运算量大于Ｏ（ｎ７）．对于混合整数线性规划（４）．一般要做ｎ２次割平面．即要解７／２次松弛线性规划（５），才能求得一个最优解．用等量面法求解混合整数线性规划（４）的运算量通常为Ｏ（ｎ９），其效率不会太高．我们应该寻找更有效的方法来求解特殊整数规划（２）．
ｊ．ｔ．∑工ｕ≥０．８５。一∑ｚ。≥・１．１５，（歹＝ｌ，…，砣）
ｉ掌ｌ
ｌ—ｌ
＾
■
∑工巧≥０．８５。一∑Ｘｉｊ≥一１．１５（ｉ＝１＇．．・，，ｌ一１）ｙ．＋ｌ－ＣｉｊＸｉｊ≥０，（ｉｔＪ＝１’．．・，雄）．ｒｉｊ≥０，一Ｘｉｊ≥一１．０，（ｉ，Ｊ一１，…，咒）
（５）
更不幸的是，确定松弛线性规划（５）最优解的起２＋１个超平面组成坏条件线性方程组，无论采用ＭＡＴＬＡＢ单纯形法或等高面法Ⅲ，一般都得不到正确答案，因而很难用于等量面法求解混合整数线性规划（４）．由此可见。不是任何决策问题建成整数线性规划模型或混合整数线性规划模型后就可以顺利求解．
４求解（２）的矩阵作业法
针对极大极小任务分配问题（２）的矩阵作业法直接从代价矩阵Ｃ。＝（ｃｎ）和目标函数出发寻求解答．这里代价矩阵Ｇ的下标ｎ表示矩阵阶数．
我们把行２个代价Ｃｉｊ按由小到大的顺序排成一行，其中可
能有相等者。因此这厄２个代价由小到大为ｒ（１≤，．≤恕２）个不同级别的实数Ｒ，，Ｒ：，…，尼，（Ｒｌ＜飓＜…＜尼），等于风（１≤
ｒ
五≤ｒ）的代价Ｃｉｊ有“个．显然ｍ≥１且∑“一疗２．又记Ｒ为一个不小于忌的数．它也可以看作ｏｏ符号．如果ｒ一１，即所有∞＝尺，。则（２）显然有恕！个解．每个解的目标函数都是见．因此不妨设ｒ＞１．
容易看出，风＝ｍａｘｍａｘ｛ｃ“）＝ｍａｘｍ
Ｒ
ｒａｉｎｒａｉｎ｛ｃｆｊ）＝ｒａｉｎｒａｉｎ｛Ｃｉｊ｝．但如下两个数：尺‰＝ｍａｘ
ｒａｉｎ｛ｃｆ』）和Ｒ‰＝ｍａｘ
ｍｉｎ｛ｃ玎｝，彼此有可能不相等．令％。
ｊ
Ｊ
ｉ
＝ｍａｘ｛Ｒ‰，Ｒ‰）．我们有：
命韪１．极大极小任务分配问题（２）的最优目标函数值
名。≥‰。．
证明：按（２）的题意。每个人完成且只完成一项任务．最后
完成任务的代价不小于‰。，也不小于娲。，从而不小于
Ｒｏ眦．口
在代价矩阵Ｇ＝（ｃｕ）中将所有大于Ｒ＝：ＩＩＩ的元素用Ｒ覆
盖，叫做Ｇ的基本覆盖．由命题１知，Ｇ基本覆盖后Ｒ缸为最
３
混合整数线性规划（３）显然与问题（２）等价。其中只有一个实变量曲＋．，但与（２）相比增加了行２个约束不等式．
线性规划［“．为了利用等量面法求解混合整数线性规划（３），应将（３）变成其标准形：
７１２
小型微型计算机系统２００９钽
大非覆盖元素且每行每列至少有一个非覆盖元素．在所有非覆盖元素中的任何一个可行任务分配ｒ（如果存在的话）都是（２）的一个最优解．
命题２．Ｇ基本覆盖后．如果每行每列有不少于ｓ个Ｇ≥２）非覆盖元素，则划去某一个非覆盖元素所在的行和列。余下的珂一１阶子代价矩阵Ｇ．，中每行每列至少有ｊ—１个非覆盖元素．
证明：只需对ｌ＝２证明．假设Ｇ基本覆盖后第ｉ行有两个非覆盖元素‘峨和ｑ，（ｃｑ，，‘啦≤Ｒｏ眦）．由于ａ的第Ｊ－和Ｊ２列除第ｉ行的非覆盖元素外还有非覆盖元素。故Ｇ划去第ｉ行第，。列或第Ｊ：列后，Ｃ，卜－中每行每列至少有一个不大于Ｒ‰。的非覆盖元素．
同理可证，如果Ｇ基本覆盖后第．『列有两个非覆盖元素ｏ，，和‘ｕ，Ｇ划去第Ｊ列第ｉ。行或第ｉ２行后余下的Ｃ＋。中每行每列至少有一个不大于Ｒｏ眦的非覆盖元素．口
开始时置ｔ：＝行。ｃｆ：一Ｇ，于是可对代价矩阵Ｇ＝（ｃｑ）做出基本覆盖．在序列尺ｔ，飓，…，Ｂ中找出尺缸，的序号，令Ｒ－
＝Ｒ‰．于是代价矩阵Ｇ中不小于膨＋，＝Ｒ¨，的元素都已用
Ｒ覆盖．求解极大极小任务分配问题（２）的矩阵作业算法分下面几个步骤完成：
①考察矩阵Ｇ中各行各列未被覆盖的元素，如果存在只有一个非覆盖元索的行或列，设所有这样的元素为ｆ～，记录其中最小的元素（单项最优分配）并划去矩阵ｃｌ的第Ｐ行第ｑ列。留下ｔ—ｌ阶矩阵Ｇｌ，置ｔ：＝ｔ一１，Ｃｔ：＝Ｇ．１转向步骤①或②；
②考察矩阵ｃｆ中各行各列未被覆盖的元素，如果每行每列至少有两个非覆盖元素，转向步骤③；
③Ｇ的最优目标函数为Ｒ：；Ｇ的每行每列至少有两个非覆盖元素。利用命题２将Ｇ降一阶，在降阶过程中可保留的非覆盖元素ｃ～有多种选择，依次按如下顺序选择：
（Ｉ）划去的Ｐ行ｇ列中不是Ｐ行就是ｑ列含有最少数量的非覆盖元素，
（Ｉ）在所有满足（Ｉ）的行列中，Ｐ行口列含有的非覆盖元素数量和最小。
（Ｉ）在所有满足（Ｉ）、（Ｉ）的行列中。记录一个最小的
ｆ～（单项最优分配），降阶后置ｔ：＝ｆ—ｌ，Ｇ：＝Ｇ。若ｆ≥２，转向
步骤①或②．
历次记录的ｃ。中最大者如大于Ｒ・＝Ｒ‰，说明凤覆盖
未做出可行的任务分配，此时必须考虑五：＝量＋１的风覆盖，重新执行下一轮覆盖的步骤①一③，直至最大ｃ～（最优目标函数值）等于凡为止．
命鹿３．设代价矩阵Ｇ的ｎ２个代价由小到大排成ｒ个（１≤，，≤挖２）不同级别的实数Ｒ。，Ｒｚ，．．・，尼，等于风的代价ｃ“有
矗个（ｉ一１，．．・，，．）．又设Ｃ基本覆盖后腺。在序列Ｒｌ，Ｒ２．…，
见中的序号是五（１≤志≤ｒ）．则用矩阵作业法求解极大极小任务分配问题（２）。不超过ｒ一是＋１轮覆盖定找到一个解．
证明：由于第一轮覆盖中每行每列至少有一个非覆盖元素，故第一轮覆盖至少记录两个非覆盖元素．如果第一轮覆盖
万
方数据记录了玎个非覆盖元素，那么矩阵作业法用基本覆盖求得问题（２）的一个最优解．否则。以后每增加一轮覆盖。如志：－－－－ｋ＋１，非覆盖元素数量级递增到凡＋．，非覆盖元素数个数递增
●＋ｌ
７
到∑趴由于∑矗＝挖：，故不超过ｒ－ｋ＋１轮覆盖总可以找到（２）
ｔＩｌ
ｌ’Ｉ
的一个解．口
下面来证明矩阵作业法按照良性隐式枚举给出问题（２）的最优解．所谓良性隐式枚举［５］，是指一个隐式枚举算法，在某种意义下只需要列举小部分可行解便实际上可获得最优解。其中“小部分”理解为被列举的可行解数量是解空间维数及约束数的多项式函数，而“实际上”理解为获得最优解的某种概率等于１．由命题３知矩阵作业法求解问题（２）只列举了小部分可行解．因此只需证明它给出最优解的某种概率等于１．有关的概率计算，需要两个基本而符合常理的假定：
（Ｕ１）代价矩阵Ｃ中每个元素分布位置是等机会的；（Ｕ２）Ｃ作尺覆盖后将元素分成被覆盖和非覆盖两类，每一类的元素之间没有区别．
命题４．若代价矩阵ｃ中每行每列至少有一个非覆盖元素．非覆盖元素数日为扰，则ｎ≤柳≤恕２，矩阵作业算法对Ｃ做出最优解的概率多（Ｚ１．ｍ）当川＝月或卵２一雅≤ｍ≤珂２时等于１．
证明：由于ｎ阶代价矩阵Ｃ的每行每列至少有一个非覆盖元素，所以显然有ｎ≤ｍ≤Ｈ２．如果ｍ一＂。则显然ｐ（Ｚ１，ｎ）一１．因为疗个非覆盖元素只能分布在不同行列而构成最优解．矩阵作业算法的步骤①即可求得解答．
又假若ｍ≥咒２一咒，也有户（ＺＩ，坍）＝１．这容易用归纳法证明．事实上，Ｐ（ｚｌ，ｍＩｎ２－ｎ≤ｍ≤疗２）＝１对至少有６个非覆盖元素的胆＝３阶代价矩阵显然成立．设该结论对万一＾的这种矩阵成立．令订一量＋１．若代价矩阵的某行或某列只有一个非覆盖元素，则用矩阵作业算法降阶后的七阶代价矩阵最多只有１个被覆盖元素，该结论显然成立．若代价矩阵的每行每列至少有两个非覆盖元素，则用矩阵作业算法降阶后的＾阶矩阵至少有（五＋１）ｚ－３（志＋１）＋２＝ｋＺ－ｋ个非覆盖元素，该结论也成立．口
对于ｎ＜ｍ＜ｎ２．行，代价矩阵ｃ基本覆盖确有不存在分配问题可行解的可能，因而也存在ｐ（Ｚ。，研）＜１的可能．
命题５．设代价矩阵Ｇ的非覆盖元素数目ｍ≥ｎ（砣＋１）／２，且矩阵作业算法在每次降阶过程中划去的非覆盖元素数目不大于被降阶矩阵的阶数ｔ（ｆ＝刀，挖一ｌ，…），则矩阵作业算法做出最优解的概率ｐ（Ｚ。，扰）＝１．
证明：采用归纳法证明．事实上，ｐ（２。，ｍＩｍ≥行（疗＋１）／２）＝１对刀＝２显然成立．设命题对行＝ｊ—ｌ成立，即Ｐ（Ｚｌ，研“Ｉ％．。≥５（Ｐ１）／２）＝１，其中研¨表示，一１阶矩阵的非覆盖元素数目．令行一ｓ，且ｓ阶矩阵的非覆盖元素数目ｍ，≥，（ｓ＋１＞／Ｚ．由于矩阵作业算法对５阶矩阵降阶时划去的非覆盖元素数目不大于ｊ，故降阶后的ｓ一１阶矩阵非覆盖元素数目ｍ，ｔ≥ｓ（ｓ＋１）／Ｚ—ｊ＝，（５一１）／２，从而ｐ（Ｚｌ，ｍ，Ｉ研，≥ｊ０＋１）／２）一１．口
易知，对于代价矩阵Ｇ的任何覆盖，不管它有无问题（２）的可行解，矩阵作业算法的出口总是步骤①．设代价矩阵的某一覆盖中每行每列至少有ｓ个非覆盖元素，从而非覆盖元素
４期
聂明泓等：任务分配问题的建模与求解
７１３
总数坍≥，拧。其中ｓ≥１．如果在矩阵作业算法的降阶过程中自始至终ｓ＝ｌ，那么其解答显然是正确的．如果在降阶过程中出现过ｓ＞ｌ的情况，所得解答就不一定正确了．例如：
１０００１０１００１
Ｃ＝
１１１１０１１１１００１００１
其中１表示非覆盖元素，０表示覆盖元素．矩阵Ｃ至少有一个可行解且非覆盖元素数目为１４，ｓ＝２，矩阵作业算法的步骤③划去４个非覆盖元素．有４种划法．如果划去的是１行５列，则矩阵作业算法得不出可行解．除此以外矩阵作业算法得出可行解．这就是说．当ｓ＞ｌ时．矩阵作业法可能将本来具有可行解的覆盖误判为没有可行解．
为了避免这种可能的误判，矩阵作业算法在遇到ｓ＞ｌ而又给出无解判断时应作特殊处理，即把当时被记录的元素人工地改为ｏ。，再重新对人工修改后的代价矩阵应用矩阵作业法．这就保证了矩阵作业法在任何情况下都给出问题（２）的正
确解答．
命题６．设代价矩阵ｃ＾的每行每列至少有ｓ个非覆盖元素．其中Ｊ≥１．如果矩阵作业算法在遇到５＞１而又给出无解结论时对代价矩阵做人工修改，则矩阵作业算法给出问题（２）正确解答的概率ｐ（Ｚｚ，所，５）＝１．
证明：每一次人工修改。被记录的元素变为ｏ。，从而它被覆盖，这就使人工修改后的代价矩阵中每行每列至少有ｓ一１个非覆盖元素．如果，一１＞１且矩阵作业算法仍给出无解结论，则再进行一次人工修改．因此，对某一次人工修改后的代价矩阵执行矩阵作业算法，其结果或者是得到一个可行解，或者在降阶过程中自始至终ｓ＝１而仍无可行解．矩阵作业算法总是给出确解答．即Ｐ（Ｚｚ．ｍ，５）＝１．口
命题７．具有人工修改代价矩阵的矩阵作业法是求解极大极小任务分配问题（２）的良性隐式枚举。不超过ｒ一七＋１轮覆盖肯定找到一个最优解。其中ｒ和ｋ如命题３所述．
证明：如果代价矩阵Ｃ基本覆盖中存在问题（２）的最优解，则由命题４－６知第一轮覆盖就做出最优解．否则进行下一轮覆盖的求解．每增加一轮覆盖，非覆盖元索的大小增加一个数量级别．由命题３知不超过ｒ一量＋１轮覆盖定找到一个可行解．设最早第ｊ轮覆盖找到可行解．则第ｊ轮覆盖以前的覆盖不存在可行解，即代价矩阵Ｒ覆盖的数量级必须在基本覆盖
数量级‰。的基础上再加户１个数量级才存在可行解，因而
最优目标函数值等于Ｒ口眦加产１个数量级．矩阵作业法第．『轮找到的解就是最优解．口
固定矩阵阶数ｔ。每执行一次步骤①一③．运算量为Ｏ（ｔ２）；ｔ从Ｉ＇１减至１为一轮覆盖，故执行一轮覆盖的运算量为Ｄ（恕。）．不超过ｒ一量＋１轮覆盖就可找到一个最优解．因此，不考虑人工修改代价矩阵的次数，用矩阵作业法求解极大极小型任务分配问题（２）的运算量最大为Ｏ（ｎ５），其计算复杂度远低于求解混合整数线性规划（４）的复杂度．
万
方数据５矩阵作业法对求解（１）的应用
由于记录非覆盖元素时采取了“单项最优分配”原则．所以矩阵作业法求解问题（２）得到的解答往往也是问题（１）的解．但倘若在实施覆盖之前不先将代价矩阵做一次变换．矩阵作业法未必能求解总体极小任务分配问题（１），因为变换前的代价是绝对代价．
在代价矩阵Ｇ＝（ｑ）中每行各元素减去该行的最小元素（行标志数）．然后每列各元素减去该列的最小元索（列标志数），如此变换后的新代价矩阵Ｂ。一（ｂｉ』）为非负矩阵且每行每列至少有一个最小级别的０元素．幻＝０的第ｉ行第Ｊ列标志数之和等于代价ｃｌｊ．由匈牙利算法［Ｉ］知，代价矩阵岛和Ｇ对于分配问题（１）是等价的，鼠中的元素表示相对代价．如果鼠中的０元素能构成一种可行的任务分配，那么该分配所对应的矩阵Ｃ。元素之和，即行列标志数之和．就是最优目标函数值．
对相对代价矩阵＆应用具有“单项最优分配”原则的矩阵作业法．其基本覆盖就是所有非０元素的覆盖．倘若鼠的基本覆盖能求得可行的任务分配，那么该分配就是问题（１）的解答；否则矩阵作业法用最低级别的正元素覆盖．对鼠做出问题（２）的一个解且解中尽可能多地含有非覆盖最小元素，由“单项最优分配”原则知道它一般也是问题（１）的解答．用矩阵作业法求解问题（１）的目标函数值等于对应的矩阵尻元素之和加行列标志数之和．
注意．矩阵作业法对相对代价矩阵鼠做出问题（２）的解不一定总是问题（１）的解．某些特殊情况下，两者的解答是不一样的．例如，某轮覆盖的降阶相对代价矩阵
３『３
２１
玩５
ｆ３ｌ
２
ｏＪ，Ｂｓ—Ｉ
３２ｕ
１１
Ｌ１
０
０Ｊ
矩阵作业法求得岛，鼠极大极小问题（２）的正确解答，其目标函数值为２；但此解答不是总体极小任务分配问题（１）的解答．
由于具有“单项最优分配”原则的矩阵作业法最终要应用于２阶相对代价矩阵，所以利用矩阵作业法求解总体极小任务分配问题（１）后应该对最后分配的两元素的绝对（矩阵Ａ）代价和作验证．即使这样，矩阵作业法求解问题（１）仍有出错的小概率．
为了估算矩阵作业法求解问题（１）出错这件事Ｅ发生的概率户（Ｅ）的一个上界，除假定（Ｕ１）和（Ｕ２）之外，再增加一个假定：
（Ｕ３）只要问题（２）的矩阵作业解不是由相对代价矩阵的基本覆盖做出。那么相对代价矩阵中就存在九个不全是非覆盖的元素，其和小于问题（２）解各元素之和，存在这种情况的数量不大于命题３给出的最多覆盖轮数ｒ－ｋ＋１．
假定（Ｕ３）夸大了事件Ｅ发生的概率但简化了其估算工作．
命题８．借助于相对代价矩阵，矩阵作业法是求解总体极小任务分配问题（１）的良性隐式枚举。不超过ｒ－ｋ＋１轮覆盖
７１４
小型微型计算机系统
２００９矩
找到一个最优解的概率随ｎ增加而趋于１．
证明：由命题７知，矩阵作业法应用于相对代价矩阵。不超过ｒ－七＋１轮覆盖找到极大极小任务分配问题（２）的一个最优解．当求解轮数大于１时，将此最优解当作总体极小任务分配问题（１）的最优解有出错的可能．
按假定（Ｕ３），只要相对代价矩阵基本覆盖０元素做不出问题（２）的解，就存在ｎ个不全是非覆盖的元素．其和小于问题（２）解各元素之和．存在的最多ｒ－五－ｔ－１种方式中，概率最大的是：此”个元素除一个被覆盖之外其它全为０．现在来计算此挖个元素能构成问题（１）可行解的概率．按假定（Ｕ１）和假定（Ｕ２），一个被覆盖正元素，起一１个０元素在髓中的分布方式共有种ｎＺＣ＂ｇ“，其中做出问题（１）不同可行解的方式有行！理种，因此这ｎ个元素能构成问题（１）解答的概率是ｒｚ＝挖！挖／（挖２Ｃ罾＋１）一（锄一１）！）２（ｎ２一行）！／（ｎ２—１）！．这样一来，事件Ｅ发生的概率ｐ（Ｅ）≤（ｒ－ｋ＋１）ｒ２．应用斯特林阶乘公式估算Ｐ（Ｅ）的右端（ｒ—ｋ＋１）ｒ２，当珂足够大时，（ｒ－ｋ＋１）ｒ２≤２，ｒ行２（以一１）
√石死ｉ币（（行一１）／（’ｌ＋１））一・（行／（理＋１））”“”／Ｐ“，故借助于
相对代价矩阵风．矩阵作业法求解问题（１）出错的概率户（Ｅ）随报增加而趋于０．口
６数值试验
由计算复杂度的比较可知．矩阵作业法对求解极大极小或总体极小任务分配问题远比穷举法和混合整数线性规划模型有效．因此只需对较大规模的同题（２）和（１）做矩阵作业法的数值试验．为了考察矩阵作业法对求解任务分配问题的效率，需要阶数稍高的代价矩阵，因此数值试验过程中的代价矩阵Ｇ以计算机生成．
矩阵作业法求解（２）和（１）的试验在ＰＣ机上完成，程序在ＷｉｎｄｏｗｓＸＰ环境下用ＭＡＴＩ，ＡＢ７．０运行．计算时间以秒计．ＭＡＴＬＡＢ统计１秒以内的计算时间是不准确的，只能以平均计算时间作为参考．
例１．矩阵元素为
ｃ；！ｆ＝１０＋５ｉ＋５ｊ（ｉ≠歹），跨＝５＋１０ｉ，
挖一１０。１５，２０，２５。３０，３５，４０，４５，５０
（６）
问题（２）的最优目标函数值显然是１５＋５ｎ，最优解至多两个（雄为偶数），而矩阵的左下至右上对角线分配总是一种最优任务分配．
对于元素为（６）的代价矩阵．问题（１）与（２）的解完全不一样．由相对代价矩阵知（１）的惟一解是矩阵的左上至右下对角线分配。其最优目标函数值为ｌ晚＋５挖２．
例２．矩阵元素为
矗＝１０＋５ｉ＋５歹（ｉ≠．『）。ｆ；＝１５＋１０ｉｆ
ｎ＝１０，１５。２０．２５，３０，３５，４０，４５，５０
（７）
问题（２）的最优目标函数值是１５＋５行（起为偶数）或２０＋５恕（珂为奇数）。疗为偶数时最优解是惟一的，恕为奇数时最优解有４对于元素为（７）的代价矩阵。由相对代价矩阵知问题（１）的解非常多，除对角元素之外的许多可行分配都是最优解，其
万
方数据最优目标函数值为１５ｎ＋５ｎ２．
例３．矩阵元素为
砰ｆ＝１０＋５ｉ＋５Ｊ；雄＝１０，１５。２０，２５，３０，３５。４０，４５，５０
（８）
问题（２）的最优目标函数值是１５＋跏，最优解是惟一的，即矩阵的左下至右上对角线分配．
对于元素为（８）的代价矩阵，由相对代价矩阵知问题（１）的解有，ｌ！个，即矩阵（８）的任何可行任务分配都是问题（１）的最优解。其最优目标函数值均为１５ｎ＋Ｓｎ２．
为了考察矩阵作业法对例ｌ～例３的求解情况．先令行＝５和ｎ一６，表１给出问题（２）解答的行列分配及其代价．注意疗＝６时例１有两种解答。咒＝５时例２有四种解答．表１给出的解答不是左下至右上对角线分配．而是符合“单项最优分配”原则，即在团队完成任务时间最短的前提下，还考虑单项任务用最小的代价去完成．当然，“单项最优分配”只能在问题（２）有多解时才会出现．通常，极大极小任务分配问题（２）存在多解．对例２和例３。矩阵作业法直接求解问题（２）得到的解答也是问题（１）的解，但例１不是这样．
表１问题（２）解答示例
Ｔａｂｌｅ１
Ｓｏｌｕｔｉｏｎｅｘａｍｐｌｅｓｏｆｔｈｅｐｒｏｂｌｅｍ（２）
ｎ＝５
ｎ＝６
．４０
４０３５４０４０４５４５
４５４５３５４５例１
５—１
４—２３—３２—４１—５６－１５—２
１—６２—５３—３４—４．．４０
４０４０３５４５４５４５４５４５４５４５例２
５—１
４一Ｚ１—５２—３３—４６・１５・２４—３３—４Ｚ一５１－６～
４０４０４０４０４０４５４５４５４５４５４５例３
５—１
４—２
３—３
２—４
１－５
６一ｌ
５—２
４—３
３—４
２—５
１—６
表２列出”＝１０一５０时对例１一例３求解问题（２）的全部计算时间．包括生成代价矩阵及显示结果的时间都统计在内．
用时最多的是行＝４５时例２．约花了０．１２５秒，原因是多运行
了一轮Ｒ。＝２４５的覆盖．由表２看出矩阵作业法的运算效率极高，它完全适合于极大极小任务分配问题与总体极小任务分配问题的在线求解．
继续增大ｎ，类似于表２的测试自然可以做下去．我们对例１做了行＝１００和１０００的测试，时间分别为０．２５０和１６１．８２８秒；又对例２做了起一１０１和１００１的测试，时间分别为０．４２２和２５３．７５０秒．行＝１０００阶的问题（２），矩阵作业法求解时间不超过５分钟．根据我们的经验，即使等量面法能求解混合整数线性规划（４），对于１０００阶的问题，在ＰＣ机上求得解答需要２０分钟以上［３］，而１０００阶的混合整数线性规划问题，只
相当于√１０００≈－３１阶任务分配问题．
表２问题（２）的求解时间
Ｔａｂｌｅ２
Ｔｉｍｅｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍ（２）
ｎ
１０１５２０
２５３０３５４０４５５０倒１０．０３１０．０３１０．０３１０．０６３
０．０６３０．０６３０．０７８０．１０９０．１０９倒２０．０３１０．０６３０．０３１０．０９４
０．０６３０．１０９０．０９４０．１２５０．０９４例３
０．０３１
０．０３１
０．０３１
０．０６３
０．０６３
０．０６３
０．０７８
０．０７８
０．０９４
表３是借助于相对代价矩阵，矩阵作业法给出问题（１）的
个，而矩阵的左下至右上对角线分配总是一种最优任务分配．
４期
聂明泓等：任务分配问题的建模与求解
７１５
解答元素及其行列分配，最优目标函数值为各元素之和．结果完全符合关于例ｌ一例３的注释．
将（８）的各元素反号而形成负利润矩阵，最优解也有死！个。最优目标函数值为一１５ｎ一５ｎ２．可见．对于元素为（８）的矩阵，任务分配的最小总代价或最大总利润是一样的．其实，只要矩
表３问题（１）解答示例
Ｔａｂｌｅ３
Ｓｏｌｕｔｉｏｎｅｘａｍｐｌｅｓｏｆｔｈｅ
ｐｒｏｂｌｅｍ（１）
阵每行（或列）元素为同一公差的等差级数，任务分配的最小万
方数据Ｒｅｆｅｒｅｎｃｅｓ：
［１］ＫｕｈｎＨＷ．Ｔｈｅ
ｈｕｎｇａｒｉａｎ
ｍｅｔｈｏｄｆｏｒｔｈｅ
ａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ
［Ｊ］．ＮａｖａｌＲｅｓｅａｒｃｈ
Ｌｏｇｉｓｔｉｃｓ
Ｑｕａｒｔ。１９５５。２：８３—９７．
［２］ＮｉｅＹＹ。ＳｕＬＪ，ＬｉＣ．Ａｎｉｓｏｍｅｔｒｉｃ
ｓｕｒｆａｃｅ
ｍｅｔｈｏｄｆｏｒ
ｉｎｔｅｇｅｒ
ｌｉｎｅａｒ
ｐｒｏｇｒａｍｍｉｎｇＥＪ］．Ｉｎｔｅｒ．Ｊ．ＣｏｍｐｕｔｅｒＭａｔｈ．・２００３，８０
（７）：８３５—８４４．
［３］ＹａｎｇＬ
Ｙ，ＨａｎＪＤ。ＳｕＬＪ。ｅｔａ１．Ｉｓｏｍｅｔｒｉｃｓｕｒｆａｃｅｍｅｔｈｏｄａｎｄ
ｉｔｓ
ｎｕｍｅｒｉｃａｌ
ｔｅｓｔｓ
ｆｏｒｍｉｘｅｄ—ｉｎｔｅｇｅｒ
ｌｉｎｅａｒ
ｐｒｏｇｒａｍｍｉｎｇ［Ｊ］．
ＩＳＡＳＴＴｒａｎｓａｃｔｉｏｎｓｏｎ
Ｃｏｍｐｕｔｅｒｓａｎｄ
Ｓｏｆｔｗａｒｅ
Ｅｎｇｉｎｅｅｒｉｎｇ，
２００８，２（１）：４Ｚ・４６．
［４］ＮｉｅＹｉ—ｙｏｎｇ，ＸｕＳＲ．Ａｎｉｓｏｍｅｔｒｉｃ
ｐｌａｎｅ
ｍｅｔｈｏｄｆｏｒｌｉｎｅａｒｐｒｏ－
ｇｒａｍｍｉｎｇｒＪ－Ｉ．ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔａｔｉｏｎａｌ．Ｍａｔｈ．．１９９１．９（３）：
２６２—２７２．
［５］ＮｉｅＹＹ，ＳｏｎｇＸｉａｎｇ，ＳｕＬｉ．ｊｉｅ。ｅｔａ１．Ｗｅｌｌ—ｉｍｐｌｉｅｄａｎｄ
ｎｅａｒ－
ｉｍｐｌｉｅｄ
ｅｎｕｍｅｒａｔｉｏｎｓ
ＣＪ］．ＩｎｆｏｒｍａｔｉｏｎａｎｄＣｏｎｔｒｏｌ，２００５。３４
（３）：２９６．３０２．
附中文参考文献：
［５］聂义勇，宋翔・苏丽杰，等・良性隐式枚举与近隐式枚举［Ｊ］・信息
与控制．２００５，３４（３）１２９６－３０２．
总代价或最大总利润就是一样．作为推论，此结果意味着对若干能力相当的人不必强行分配任务．
任务分配问题的建模与求解
作者：作者单位：
聂明泓， 杨丽英， 聂义勇， NIE Ming-hong， YANG Li-ying， NIE Yi-yong
聂明泓,NIE Ming-hong(沈阳神州数码有限公司,辽宁,沈阳,110004)， 杨丽英,聂义勇,YANGLi-ying,NIE Yi-yong(中国科学院,沈阳自动化研究所,机器人学国家重点实验室,辽宁,沈阳,110016)
小型微型计算机系统
JOURNAL OF CHINESE COMPUTER SYSTEMS2009,30(4)
刊名：英文刊名：年，卷(期)：
参考文献(5条)
1.Kuhn H W The hungarian method for the assignment problem 1955
2.Nie Y Y;Su L J;Li C An isometric surface method for integer linear programming[外文期刊] 2003(07)3.Yang L Y;Han J Do Su L J Isometric surface method and its numerical tests for mixed-integer linearprogramming 2008(01)
4.Nie Yi-yong;Xu S R An isometric plane method for linear programming 1991(03)5.聂义勇;宋翔;苏丽杰 良性隐式枚举与近隐式枚举[期刊论文]-信息与控制 2005(03)
本文读者也读过(6条)
1. 鄢超波.赵千川 任务分配问题的研究进展与算法比较[会议论文]-2008
2. 杨冬.王正欧 改进的蚂蚁算法求解任务分配问题[期刊论文]-天津大学学报2004,37(4)
3. 王灵霞.张远平.吴佩莉.WANG Ling-xia.ZHANG Yuan-ping.WU Pei-li 蚁群算法求解分布式系统任务分配问题[期刊论文]-计算机工程与设计2008,29(6)
4. 王雅琳.王宁.阳春华.桂卫华.WANG Ya-lin.WANG Ning.YANG Chun-hua.GUI Wei-hua 求解任务分配问题的一种离散微粒群算法[期刊论文]-中南大学学报（自然科学版）2008,39(3)
5. 王秀宏.王正欧.乔清理.WANG Xiu-hong.WANG Zheng-ou.QIAO Qing-li 用具有混沌特性的神经网络解任务分配问题[期刊论文]-系统工程学报2001,16(2)
6. 李大林.李杰.LI Da-lin.LI Jie 基于PSO算法的多巡飞器任务分配方法[期刊论文]-北京理工大学学报2010,30(12)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_xxwxjsjxt200904026.aspx
小型微塑计算机系统
２００９年４月第４期
ＪｏｕｒｎａｌｏｆＣｈｉｎｅｓｅＣｏｍｐｕｔｅｒＳｙｓｔｅｍｓ
Ｖ０１．３０
Ｎｏ．４
２００９
任务分配问题的建模与求解
聂明泓１，杨丽英２，聂义勇２
１（沈阳神州数码有限公司，辽宁沈阳１１０００４）
２（中国科学院沈阳自动化研究所机器人学国家重点实验室．辽宁沈阳１１００１６）Ｅ－ｍａｉｌ：ｎｉｅｍｈ＠，ｄｉｇｉｔａｌｅｈｉｎａ．ｃｏｍ
摘要：建立了极大极小任务分配问题的混合整数线性规划模型，提出一种矩阵作业解答。并与穷举解及混合整数线性规划解的计算复杂度进行了比较．理论分析和数值试验表明矩阵作业法对两类任务分配问题。极大极小和总体极小任务分配问题，有效地提供最优解．
关键词：任务分配问题；穷举法；混合整数线性规划；松弛线性规划；矩阵作业法中图分类号：ＴＰｌ８
文献标识码：Ａ
文章编号：１０００—１２２０（２００９）０４．０７１０－０６
Ｍｏｄｅｌｌｉｎｇ
ａｎｄＳｏｌｕｔｉｏｎｆｏｒＡｓｓｉｇｎｍｅｎｔＰｒｏｂｌｅｍ
ＮＩＥ
Ｍｉｎｇ－ｈｏｎ９１，ＹＡＮＧＬｉ—ｙｉｎ９２，ＮＩＥＹｉ—ｙｏｎ９２
１（ＳｈｅｎｙａｎｇＤｉｇｉｔａｌＣＭｎａＬｉｍｉｔｅｄ。Ｓｈｃｎｙａｎｇ１１０００４，Ｃｈｉｎａ）ｚ（ＳｔａｔｅＫｅｙＬａｂｏｒａｔｏｒｙ
ｏｆＲｏｂｏｔｗｓ。Ｓｈｅｎｙａｎｇ
Ｉｎｓｔｉｔｕｔｅ
ｏｆＡｕｔｏｍａｔｉｏｎ，Ｓｈｅｎｙａｎｇ１１００１６，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ｔｈｅｍｉｘｅｄｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ（ＭＩＬＰ）ｏｆｍｉｎｉｍａｘａｓｓｉｇｎｍｅｎｔｉｓｆｏｒｍｅｄ・ａｎｄａｓｏｌｕｔｉｏｎｃａｌｌｅｄ
Ｏｐｅｒａｔｉｏｎｓ
Ｏｎ
Ｍａｔｒｉｘｉｓｐｒｅｓｅｎｔｅｄａｎｄｃｏｍｐａｒｅｄｗｉｔｈｔｈｅｓｏｌｕｔｉｏｎｓｏｆｅｘｈａｕｓｔｉｏｎａｎｄ
ＭＩＬＰ．Ｔｈｅｏｒｅｔｉｃａｌａｎａｌｙｓｅｓａｎｄｎｕｍｅｒｉｃａｌ
ｔｅｓｔｓ
ｓｈｏｗｔｈａｔｔｈｅｏｐｅｒａｔｉｏｎｓ
ｏｎ
ｍａｔｒｉｘ
ａｒｅ
ｅｆｆｉｃｉｅｎｔｆｏｒｂｏｔｈｍｉｎｉｍａｘａｎｄｇｌｏｂａｌ－ｍｉｎｉｍｕｍａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍｓ．
Ｋｅｙｗｏｒｄｓ：ａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍｌｍｅｔｈｏｄｏｆｅｘｈａｕｓｔｉｏｎ；ｍｉｘｅｄｉｎｔｅｇｅｒｌｉｎｅａｒｐｒｏｇｒａｍｍｉｎｇ（ＭＩＩ，Ｐ），ｒｅｌａｘｅｄｌｉｎｅａｒｐｒｏｇｒａｍ－
ｍｉｎｇ（ＲＬＰ）Ｉｏｐｅｒａｔｉｏｎｓ
ｏｎ
ｍａｔｒｉｘ
１引言
划方法又是根据其松弛线性规划方法推导出来的，求解一次（１）的松弛线性规划的运算量通常是ｏ（（ｎ×７１）３』）＝Ｏ（ｎ７），总体极小任务分配问题［１］提法是：有７１项不同的任务，恰因此整数线性规划方法求解（１）不会比匈牙利算法［１］更好．
好７１个人分别承担这些任务Ｉ由于每个人专长不同，各人完成总代价极小的任务分配问题（１）也可以解决总利润极大不同任务所需的代价也不一样；问应该安排哪个人去完成哪的任务分配问题。这只要设一ＣｉＩ为第ｉ个人完成第ｊ项任务所项任务，使完成咒项任务所需总代价最小？
获得的利润就够了．这样。Ｃ＝（ｃｏ）表示负利润矩阵，求解负利总体极小任务分配问题可以用７１２个决策变量描述．令ｏ“润矩阵的总体极小任务分配问题．其目标函数反号就是极大为。一１决策变量，即Ｘｉｊ＝１表示安排第ｉ个人去完成第Ｊ项任总利润．
务，霸ｊ＝０表示不安排第ｉ个人去完成第Ｊ项任务，用ｃｕ表示如果把“代价”理解为成本消耗，那么总体极小任务分配第ｉ个人完成第Ｊ项任务所需的代价（实数），则ｃｔＪ构成已知问题的提法，即（１）的目标函数，是合理的．但若把“代价”理解的刀Ｘ一代价矩阵．我们有
为时间，那么（１）的目标函数就不一定合理了．因为任务分配ｒａｉｎ石＝∑∑Ｃ‘∥廿
好以后．大家在同一时刻开始干活，所以这里的总“时间”统计ｉ－ＩＪｌｌ
＾
已不重要．重要的是挖个人作为一个团队去完成ｎ项任务（每ｓ．ｔ．∑ｚｉｊ＝１，（＿『＝１，…，ｎ）
人完成且只完成一项任务）．要求最后完成全部任务的时间最∑Ｘｉｊ＝ｌ，（ｆ＝ｌ，…，疗）
短．这样，（１）的目标函数应该有所修改。即
ｉ－－ｌ
ｍｉｎ
Ｘｉｊ＝０
ｏｒ
１，ｉ，Ｊ∈Ｎ＝｛１，…，行）
（１）
２一ｍａｘ｛ｃｉｊｘｏ）
ｌ・Ｊ
＾
这是一个整数线性规划问题．如果在（１）中去掉工ｕ一０
ｏｒ
１的
，．ｔ．∑ｘｉｊ＝ｌ，（＿ｆ＝ｌ，．．・，疗）
ｆ－ｌ
约束条件而代之以ｏ≤ｚ，Ｊ≤ｌ，则它就是松弛线性规划问题．■
人们自然可以用整数线性规划的方法，如等量面法［纠．求解
∑Ｘｉｊ＝ｌ，（ｆ＝１，…，行）
ｉ－Ｉ
（１）．但由于这里有恕２个Ｏ一１决策变量柳，而所有整数线性规勘＝０
ｏｒ
１，ｉ，Ｊ∈Ｎ暑｛１，…，ｎ｝
（２）
收穑日期：２００８—０１．２４收修改稿日期：２００８—０５—１３作者简介：聂明泓．男．１９７５年生。研究方向为管理信息系统（ＭＩＳ）和后勤支持系统等，杨丽英，女．１９７９年生．博士研究生，研究方向为动态环境下多移动机器人自治规划和混合线性整数规划等；聂义勇，男，１９３９年生．研究员，研究方向为应用数学和计算机辅助工程等．
万
方数据
４期聂明泓等：任务分配问题的建模与求解
７１ｌ
这就是所谓极大极小任务分配问题的数学模型，它是一个整数规划问题。其中目标函数是非线性的，问题（２）与（１）的解之间无明显联系。直接求解（２）的现成软件很难找到．
本文先分析求解（２）的穷举法；然后将极大极小任务分配问题（２）改进成混合整数线性规划模型并讨论其等量面解法，在此基础上提出求解（２）的矩阵作业法；同时也分析了矩阵作业法对求解（１）的应用；最后用计算复杂度的比较和数值试验表明矩阵作业法求解这两类任务分配问题的高效性．
２求解（２）的穷举法
穷举法的基本思想就是直接或间接比较全部可行解的目标函数，比较完成后自然就找到了全局最优解．可惜一般的整数规划或混合整数规划问题的全部可行解数量随同题规模增长太快（指数次增长），以至任何计算机都无法接受．
以极大极小任务分配问题（２）为例．满足其约束条件的可行解是在，ｌ×恕零元索矩阵中不同行列任置一个元素为ｌ所构成的（五个１所对应的）任务分配ｒ．每个任务分配ｒ的目标函数：是代价矩阵Ｃ一（ｃｄ）中对应于ｌ的极大者．目标函数：最小的任务分配ｒ就是（２）的一个解．解答可能不惟一，但解答的目标函数（最优目标函数）值是惟一的．
令｛ｊｔ，ｊ：，…．＾｝是｛ｌ，２ｔ．．・，刀｝的一个排列．在行×ｎ零元素矩阵的第一行取Ｊ，号元素为１，第二行取ｊｚ号元素为１，…．第一行取＾号元素为１，这样就构成一个可行的任务分配ｒ，其目标函数ｚｒ＝ｍａｘｋｌ，，，‘编，…，‘叽）．
每一个排列｛，．，歹：，…．五｝对应着一个任务分配ｒ，因此任务分配的总数目是ｎ！．按斯特林（Ｓｔｉｆｌｉｎｇ）阶乘公式，当ｎ
足够大时，砣！≈√２，ｒ甩（ｎ／ｅ）‘，表明任务分配的总数随行的增
大而指数次增长．
只要ｎ超过ｌｏ．在ＰＣ机上就不宜用穷举法求解（２）．
一个混合整数线性规划模型
引进一个实变量曲＋ｔ。就可以将极大极小任务分配问题
（２）改进成混合整数线性规划．等价于（２）的混合整数线性规划问题是：
ｒａｉｎｚ＝ｊ，疗＋ｌ
＾
＾ｆ．∑工ｏ＝１，（歹＝１＇．．・，对）
ｉ—ｌ
■
∑ｚ“＝１，（ｆ＝１，…，挖）
ｊ－１
弘＋ｌ一‘玎％≥０。（ｆ。Ｊ＝１＇．．・。靠）
Ｘｉｊ一０
ｏｒ
１。ｉ，Ｊ∈Ｎ兰｛ｌ，…．行）
（３）
求解整数线性规划的等量面法［２］也适合于求解混合整数ｍａｘ：；一弘＋ｌ
ｔ
＾
，．ｆ．∑．劭≥０．８５。一∑工。≥一１．１５（．『＝１＇．．・，露）
万
方数据∑．％≥０．８５，一∑Ｘｉｊ≥一１．１５（ｉ＝ｌ，…。疗）
Ｊ一１
ｊ－－］
儿＋｜－ＣｔｊＸｉｊ≥０，（ｉ，Ｊ＝１，…，７／）
霸，＝０
ｏｒ
１，ｉ，ｊ∈Ｎ兰｛ｌ，…，理）
（４）
等量面法求解（４）的基础也是求解其松弛线性规划（５），（５）中的变量数是ｎ２＋１，约束不等式数目是３ｎ２＋４ｎ・２，因此求解一次松弛线性规划（５）的运算量大于Ｏ（ｎ７）．对于混合整数线性规划（４）．一般要做ｎ２次割平面．即要解７／２次松弛线性规划（５），才能求得一个最优解．用等量面法求解混合整数线性规划（４）的运算量通常为Ｏ（ｎ９），其效率不会太高．我们应该寻找更有效的方法来求解特殊整数规划（２）．
ｊ．ｔ．∑工ｕ≥０．８５。一∑ｚ。≥・１．１５，（歹＝ｌ，…，砣）
ｉ掌ｌ
ｌ—ｌ
＾
■
∑工巧≥０．８５。一∑Ｘｉｊ≥一１．１５（ｉ＝１＇．．・，，ｌ一１）ｙ．＋ｌ－ＣｉｊＸｉｊ≥０，（ｉｔＪ＝１’．．・，雄）．ｒｉｊ≥０，一Ｘｉｊ≥一１．０，（ｉ，Ｊ一１，…，咒）
（５）
更不幸的是，确定松弛线性规划（５）最优解的起２＋１个超平面组成坏条件线性方程组，无论采用ＭＡＴＬＡＢ单纯形法或等高面法Ⅲ，一般都得不到正确答案，因而很难用于等量面法求解混合整数线性规划（４）．由此可见。不是任何决策问题建成整数线性规划模型或混合整数线性规划模型后就可以顺利求解．
４求解（２）的矩阵作业法
针对极大极小任务分配问题（２）的矩阵作业法直接从代价矩阵Ｃ。＝（ｃｎ）和目标函数出发寻求解答．这里代价矩阵Ｇ的下标ｎ表示矩阵阶数．
我们把行２个代价Ｃｉｊ按由小到大的顺序排成一行，其中可
能有相等者。因此这厄２个代价由小到大为ｒ（１≤，．≤恕２）个不同级别的实数Ｒ，，Ｒ：，…，尼，（Ｒｌ＜飓＜…＜尼），等于风（１≤
ｒ
五≤ｒ）的代价Ｃｉｊ有“个．显然ｍ≥１且∑“一疗２．又记Ｒ为一个不小于忌的数．它也可以看作ｏｏ符号．如果ｒ一１，即所有∞＝尺，。则（２）显然有恕！个解．每个解的目标函数都是见．因此不妨设ｒ＞１．
容易看出，风＝ｍａｘｍａｘ｛ｃ“）＝ｍａｘｍ
Ｒ
ｒａｉｎｒａｉｎ｛ｃｆｊ）＝ｒａｉｎｒａｉｎ｛Ｃｉｊ｝．但如下两个数：尺‰＝ｍａｘ
ｒａｉｎ｛ｃｆ』）和Ｒ‰＝ｍａｘ
ｍｉｎ｛ｃ玎｝，彼此有可能不相等．令％。
ｊ
Ｊ
ｉ
＝ｍａｘ｛Ｒ‰，Ｒ‰）．我们有：
命韪１．极大极小任务分配问题（２）的最优目标函数值
名。≥‰。．
证明：按（２）的题意。每个人完成且只完成一项任务．最后
完成任务的代价不小于‰。，也不小于娲。，从而不小于
Ｒｏ眦．口
在代价矩阵Ｇ＝（ｃｕ）中将所有大于Ｒ＝：ＩＩＩ的元素用Ｒ覆
盖，叫做Ｇ的基本覆盖．由命题１知，Ｇ基本覆盖后Ｒ缸为最
３
混合整数线性规划（３）显然与问题（２）等价。其中只有一个实变量曲＋．，但与（２）相比增加了行２个约束不等式．
线性规划［“．为了利用等量面法求解混合整数线性规划（３），应将（３）变成其标准形：
７１２
小型微型计算机系统２００９钽
大非覆盖元素且每行每列至少有一个非覆盖元素．在所有非覆盖元素中的任何一个可行任务分配ｒ（如果存在的话）都是（２）的一个最优解．
命题２．Ｇ基本覆盖后．如果每行每列有不少于ｓ个Ｇ≥２）非覆盖元素，则划去某一个非覆盖元素所在的行和列。余下的珂一１阶子代价矩阵Ｇ．，中每行每列至少有ｊ—１个非覆盖元素．
证明：只需对ｌ＝２证明．假设Ｇ基本覆盖后第ｉ行有两个非覆盖元素‘峨和ｑ，（ｃｑ，，‘啦≤Ｒｏ眦）．由于ａ的第Ｊ－和Ｊ２列除第ｉ行的非覆盖元素外还有非覆盖元素。故Ｇ划去第ｉ行第，。列或第Ｊ：列后，Ｃ，卜－中每行每列至少有一个不大于Ｒ‰。的非覆盖元素．
同理可证，如果Ｇ基本覆盖后第．『列有两个非覆盖元素ｏ，，和‘ｕ，Ｇ划去第Ｊ列第ｉ。行或第ｉ２行后余下的Ｃ＋。中每行每列至少有一个不大于Ｒｏ眦的非覆盖元素．口
开始时置ｔ：＝行。ｃｆ：一Ｇ，于是可对代价矩阵Ｇ＝（ｃｑ）做出基本覆盖．在序列尺ｔ，飓，…，Ｂ中找出尺缸，的序号，令Ｒ－
＝Ｒ‰．于是代价矩阵Ｇ中不小于膨＋，＝Ｒ¨，的元素都已用
Ｒ覆盖．求解极大极小任务分配问题（２）的矩阵作业算法分下面几个步骤完成：
①考察矩阵Ｇ中各行各列未被覆盖的元素，如果存在只有一个非覆盖元索的行或列，设所有这样的元素为ｆ～，记录其中最小的元素（单项最优分配）并划去矩阵ｃｌ的第Ｐ行第ｑ列。留下ｔ—ｌ阶矩阵Ｇｌ，置ｔ：＝ｔ一１，Ｃｔ：＝Ｇ．１转向步骤①或②；
②考察矩阵ｃｆ中各行各列未被覆盖的元素，如果每行每列至少有两个非覆盖元素，转向步骤③；
③Ｇ的最优目标函数为Ｒ：；Ｇ的每行每列至少有两个非覆盖元素。利用命题２将Ｇ降一阶，在降阶过程中可保留的非覆盖元素ｃ～有多种选择，依次按如下顺序选择：
（Ｉ）划去的Ｐ行ｇ列中不是Ｐ行就是ｑ列含有最少数量的非覆盖元素，
（Ｉ）在所有满足（Ｉ）的行列中，Ｐ行口列含有的非覆盖元素数量和最小。
（Ｉ）在所有满足（Ｉ）、（Ｉ）的行列中。记录一个最小的
ｆ～（单项最优分配），降阶后置ｔ：＝ｆ—ｌ，Ｇ：＝Ｇ。若ｆ≥２，转向
步骤①或②．
历次记录的ｃ。中最大者如大于Ｒ・＝Ｒ‰，说明凤覆盖
未做出可行的任务分配，此时必须考虑五：＝量＋１的风覆盖，重新执行下一轮覆盖的步骤①一③，直至最大ｃ～（最优目标函数值）等于凡为止．
命鹿３．设代价矩阵Ｇ的ｎ２个代价由小到大排成ｒ个（１≤，，≤挖２）不同级别的实数Ｒ。，Ｒｚ，．．・，尼，等于风的代价ｃ“有
矗个（ｉ一１，．．・，，．）．又设Ｃ基本覆盖后腺。在序列Ｒｌ，Ｒ２．…，
见中的序号是五（１≤志≤ｒ）．则用矩阵作业法求解极大极小任务分配问题（２）。不超过ｒ一是＋１轮覆盖定找到一个解．
证明：由于第一轮覆盖中每行每列至少有一个非覆盖元素，故第一轮覆盖至少记录两个非覆盖元素．如果第一轮覆盖
万
方数据记录了玎个非覆盖元素，那么矩阵作业法用基本覆盖求得问题（２）的一个最优解．否则。以后每增加一轮覆盖。如志：－－－－ｋ＋１，非覆盖元素数量级递增到凡＋．，非覆盖元素数个数递增
●＋ｌ
７
到∑趴由于∑矗＝挖：，故不超过ｒ－ｋ＋１轮覆盖总可以找到（２）
ｔＩｌ
ｌ’Ｉ
的一个解．口
下面来证明矩阵作业法按照良性隐式枚举给出问题（２）的最优解．所谓良性隐式枚举［５］，是指一个隐式枚举算法，在某种意义下只需要列举小部分可行解便实际上可获得最优解。其中“小部分”理解为被列举的可行解数量是解空间维数及约束数的多项式函数，而“实际上”理解为获得最优解的某种概率等于１．由命题３知矩阵作业法求解问题（２）只列举了小部分可行解．因此只需证明它给出最优解的某种概率等于１．有关的概率计算，需要两个基本而符合常理的假定：
（Ｕ１）代价矩阵Ｃ中每个元素分布位置是等机会的；（Ｕ２）Ｃ作尺覆盖后将元素分成被覆盖和非覆盖两类，每一类的元素之间没有区别．
命题４．若代价矩阵ｃ中每行每列至少有一个非覆盖元素．非覆盖元素数日为扰，则ｎ≤柳≤恕２，矩阵作业算法对Ｃ做出最优解的概率多（Ｚ１．ｍ）当川＝月或卵２一雅≤ｍ≤珂２时等于１．
证明：由于ｎ阶代价矩阵Ｃ的每行每列至少有一个非覆盖元素，所以显然有ｎ≤ｍ≤Ｈ２．如果ｍ一＂。则显然ｐ（Ｚ１，ｎ）一１．因为疗个非覆盖元素只能分布在不同行列而构成最优解．矩阵作业算法的步骤①即可求得解答．
又假若ｍ≥咒２一咒，也有户（ＺＩ，坍）＝１．这容易用归纳法证明．事实上，Ｐ（ｚｌ，ｍＩｎ２－ｎ≤ｍ≤疗２）＝１对至少有６个非覆盖元素的胆＝３阶代价矩阵显然成立．设该结论对万一＾的这种矩阵成立．令订一量＋１．若代价矩阵的某行或某列只有一个非覆盖元素，则用矩阵作业算法降阶后的七阶代价矩阵最多只有１个被覆盖元素，该结论显然成立．若代价矩阵的每行每列至少有两个非覆盖元素，则用矩阵作业算法降阶后的＾阶矩阵至少有（五＋１）ｚ－３（志＋１）＋２＝ｋＺ－ｋ个非覆盖元素，该结论也成立．口
对于ｎ＜ｍ＜ｎ２．行，代价矩阵ｃ基本覆盖确有不存在分配问题可行解的可能，因而也存在ｐ（Ｚ。，研）＜１的可能．
命题５．设代价矩阵Ｇ的非覆盖元素数目ｍ≥ｎ（砣＋１）／２，且矩阵作业算法在每次降阶过程中划去的非覆盖元素数目不大于被降阶矩阵的阶数ｔ（ｆ＝刀，挖一ｌ，…），则矩阵作业算法做出最优解的概率ｐ（Ｚ。，扰）＝１．
证明：采用归纳法证明．事实上，ｐ（２。，ｍＩｍ≥行（疗＋１）／２）＝１对刀＝２显然成立．设命题对行＝ｊ—ｌ成立，即Ｐ（Ｚｌ，研“Ｉ％．。≥５（Ｐ１）／２）＝１，其中研¨表示，一１阶矩阵的非覆盖元素数目．令行一ｓ，且ｓ阶矩阵的非覆盖元素数目ｍ，≥，（ｓ＋１＞／Ｚ．由于矩阵作业算法对５阶矩阵降阶时划去的非覆盖元素数目不大于ｊ，故降阶后的ｓ一１阶矩阵非覆盖元素数目ｍ，ｔ≥ｓ（ｓ＋１）／Ｚ—ｊ＝，（５一１）／２，从而ｐ（Ｚｌ，ｍ，Ｉ研，≥ｊ０＋１）／２）一１．口
易知，对于代价矩阵Ｇ的任何覆盖，不管它有无问题（２）的可行解，矩阵作业算法的出口总是步骤①．设代价矩阵的某一覆盖中每行每列至少有ｓ个非覆盖元素，从而非覆盖元素
４期
聂明泓等：任务分配问题的建模与求解
７１３
总数坍≥，拧。其中ｓ≥１．如果在矩阵作业算法的降阶过程中自始至终ｓ＝ｌ，那么其解答显然是正确的．如果在降阶过程中出现过ｓ＞ｌ的情况，所得解答就不一定正确了．例如：
１０００１０１００１
Ｃ＝
１１１１０１１１１００１００１
其中１表示非覆盖元素，０表示覆盖元素．矩阵Ｃ至少有一个可行解且非覆盖元素数目为１４，ｓ＝２，矩阵作业算法的步骤③划去４个非覆盖元素．有４种划法．如果划去的是１行５列，则矩阵作业算法得不出可行解．除此以外矩阵作业算法得出可行解．这就是说．当ｓ＞ｌ时．矩阵作业法可能将本来具有可行解的覆盖误判为没有可行解．
为了避免这种可能的误判，矩阵作业算法在遇到ｓ＞ｌ而又给出无解判断时应作特殊处理，即把当时被记录的元素人工地改为ｏ。，再重新对人工修改后的代价矩阵应用矩阵作业法．这就保证了矩阵作业法在任何情况下都给出问题（２）的正
确解答．
命题６．设代价矩阵ｃ＾的每行每列至少有ｓ个非覆盖元素．其中Ｊ≥１．如果矩阵作业算法在遇到５＞１而又给出无解结论时对代价矩阵做人工修改，则矩阵作业算法给出问题（２）正确解答的概率ｐ（Ｚｚ，所，５）＝１．
证明：每一次人工修改。被记录的元素变为ｏ。，从而它被覆盖，这就使人工修改后的代价矩阵中每行每列至少有ｓ一１个非覆盖元素．如果，一１＞１且矩阵作业算法仍给出无解结论，则再进行一次人工修改．因此，对某一次人工修改后的代价矩阵执行矩阵作业算法，其结果或者是得到一个可行解，或者在降阶过程中自始至终ｓ＝１而仍无可行解．矩阵作业算法总是给出确解答．即Ｐ（Ｚｚ．ｍ，５）＝１．口
命题７．具有人工修改代价矩阵的矩阵作业法是求解极大极小任务分配问题（２）的良性隐式枚举。不超过ｒ一七＋１轮覆盖肯定找到一个最优解。其中ｒ和ｋ如命题３所述．
证明：如果代价矩阵Ｃ基本覆盖中存在问题（２）的最优解，则由命题４－６知第一轮覆盖就做出最优解．否则进行下一轮覆盖的求解．每增加一轮覆盖，非覆盖元索的大小增加一个数量级别．由命题３知不超过ｒ一量＋１轮覆盖定找到一个可行解．设最早第ｊ轮覆盖找到可行解．则第ｊ轮覆盖以前的覆盖不存在可行解，即代价矩阵Ｒ覆盖的数量级必须在基本覆盖
数量级‰。的基础上再加户１个数量级才存在可行解，因而
最优目标函数值等于Ｒ口眦加产１个数量级．矩阵作业法第．『轮找到的解就是最优解．口
固定矩阵阶数ｔ。每执行一次步骤①一③．运算量为Ｏ（ｔ２）；ｔ从Ｉ＇１减至１为一轮覆盖，故执行一轮覆盖的运算量为Ｄ（恕。）．不超过ｒ一量＋１轮覆盖就可找到一个最优解．因此，不考虑人工修改代价矩阵的次数，用矩阵作业法求解极大极小型任务分配问题（２）的运算量最大为Ｏ（ｎ５），其计算复杂度远低于求解混合整数线性规划（４）的复杂度．
万
方数据５矩阵作业法对求解（１）的应用
由于记录非覆盖元素时采取了“单项最优分配”原则．所以矩阵作业法求解问题（２）得到的解答往往也是问题（１）的解．但倘若在实施覆盖之前不先将代价矩阵做一次变换．矩阵作业法未必能求解总体极小任务分配问题（１），因为变换前的代价是绝对代价．
在代价矩阵Ｇ＝（ｑ）中每行各元素减去该行的最小元素（行标志数）．然后每列各元素减去该列的最小元索（列标志数），如此变换后的新代价矩阵Ｂ。一（ｂｉ』）为非负矩阵且每行每列至少有一个最小级别的０元素．幻＝０的第ｉ行第Ｊ列标志数之和等于代价ｃｌｊ．由匈牙利算法［Ｉ］知，代价矩阵岛和Ｇ对于分配问题（１）是等价的，鼠中的元素表示相对代价．如果鼠中的０元素能构成一种可行的任务分配，那么该分配所对应的矩阵Ｃ。元素之和，即行列标志数之和．就是最优目标函数值．
对相对代价矩阵＆应用具有“单项最优分配”原则的矩阵作业法．其基本覆盖就是所有非０元素的覆盖．倘若鼠的基本覆盖能求得可行的任务分配，那么该分配就是问题（１）的解答；否则矩阵作业法用最低级别的正元素覆盖．对鼠做出问题（２）的一个解且解中尽可能多地含有非覆盖最小元素，由“单项最优分配”原则知道它一般也是问题（１）的解答．用矩阵作业法求解问题（１）的目标函数值等于对应的矩阵尻元素之和加行列标志数之和．
注意．矩阵作业法对相对代价矩阵鼠做出问题（２）的解不一定总是问题（１）的解．某些特殊情况下，两者的解答是不一样的．例如，某轮覆盖的降阶相对代价矩阵
３『３
２１
玩５
ｆ３ｌ
２
ｏＪ，Ｂｓ—Ｉ
３２ｕ
１１
Ｌ１
０
０Ｊ
矩阵作业法求得岛，鼠极大极小问题（２）的正确解答，其目标函数值为２；但此解答不是总体极小任务分配问题（１）的解答．
由于具有“单项最优分配”原则的矩阵作业法最终要应用于２阶相对代价矩阵，所以利用矩阵作业法求解总体极小任务分配问题（１）后应该对最后分配的两元素的绝对（矩阵Ａ）代价和作验证．即使这样，矩阵作业法求解问题（１）仍有出错的小概率．
为了估算矩阵作业法求解问题（１）出错这件事Ｅ发生的概率户（Ｅ）的一个上界，除假定（Ｕ１）和（Ｕ２）之外，再增加一个假定：
（Ｕ３）只要问题（２）的矩阵作业解不是由相对代价矩阵的基本覆盖做出。那么相对代价矩阵中就存在九个不全是非覆盖的元素，其和小于问题（２）解各元素之和，存在这种情况的数量不大于命题３给出的最多覆盖轮数ｒ－ｋ＋１．
假定（Ｕ３）夸大了事件Ｅ发生的概率但简化了其估算工作．
命题８．借助于相对代价矩阵，矩阵作业法是求解总体极小任务分配问题（１）的良性隐式枚举。不超过ｒ－ｋ＋１轮覆盖
７１４
小型微型计算机系统
２００９矩
找到一个最优解的概率随ｎ增加而趋于１．
证明：由命题７知，矩阵作业法应用于相对代价矩阵。不超过ｒ－七＋１轮覆盖找到极大极小任务分配问题（２）的一个最优解．当求解轮数大于１时，将此最优解当作总体极小任务分配问题（１）的最优解有出错的可能．
按假定（Ｕ３），只要相对代价矩阵基本覆盖０元素做不出问题（２）的解，就存在ｎ个不全是非覆盖的元素．其和小于问题（２）解各元素之和．存在的最多ｒ－五－ｔ－１种方式中，概率最大的是：此”个元素除一个被覆盖之外其它全为０．现在来计算此挖个元素能构成问题（１）可行解的概率．按假定（Ｕ１）和假定（Ｕ２），一个被覆盖正元素，起一１个０元素在髓中的分布方式共有种ｎＺＣ＂ｇ“，其中做出问题（１）不同可行解的方式有行！理种，因此这ｎ个元素能构成问题（１）解答的概率是ｒｚ＝挖！挖／（挖２Ｃ罾＋１）一（锄一１）！）２（ｎ２一行）！／（ｎ２—１）！．这样一来，事件Ｅ发生的概率ｐ（Ｅ）≤（ｒ－ｋ＋１）ｒ２．应用斯特林阶乘公式估算Ｐ（Ｅ）的右端（ｒ—ｋ＋１）ｒ２，当珂足够大时，（ｒ－ｋ＋１）ｒ２≤２，ｒ行２（以一１）
√石死ｉ币（（行一１）／（’ｌ＋１））一・（行／（理＋１））”“”／Ｐ“，故借助于
相对代价矩阵风．矩阵作业法求解问题（１）出错的概率户（Ｅ）随报增加而趋于０．口
６数值试验
由计算复杂度的比较可知．矩阵作业法对求解极大极小或总体极小任务分配问题远比穷举法和混合整数线性规划模型有效．因此只需对较大规模的同题（２）和（１）做矩阵作业法的数值试验．为了考察矩阵作业法对求解任务分配问题的效率，需要阶数稍高的代价矩阵，因此数值试验过程中的代价矩阵Ｇ以计算机生成．
矩阵作业法求解（２）和（１）的试验在ＰＣ机上完成，程序在ＷｉｎｄｏｗｓＸＰ环境下用ＭＡＴＩ，ＡＢ７．０运行．计算时间以秒计．ＭＡＴＬＡＢ统计１秒以内的计算时间是不准确的，只能以平均计算时间作为参考．
例１．矩阵元素为
ｃ；！ｆ＝１０＋５ｉ＋５ｊ（ｉ≠歹），跨＝５＋１０ｉ，
挖一１０。１５，２０，２５。３０，３５，４０，４５，５０
（６）
问题（２）的最优目标函数值显然是１５＋５ｎ，最优解至多两个（雄为偶数），而矩阵的左下至右上对角线分配总是一种最优任务分配．
对于元素为（６）的代价矩阵．问题（１）与（２）的解完全不一样．由相对代价矩阵知（１）的惟一解是矩阵的左上至右下对角线分配。其最优目标函数值为ｌ晚＋５挖２．
例２．矩阵元素为
矗＝１０＋５ｉ＋５歹（ｉ≠．『）。ｆ；＝１５＋１０ｉｆ
ｎ＝１０，１５。２０．２５，３０，３５，４０，４５，５０
（７）
问题（２）的最优目标函数值是１５＋５行（起为偶数）或２０＋５恕（珂为奇数）。疗为偶数时最优解是惟一的，恕为奇数时最优解有４对于元素为（７）的代价矩阵。由相对代价矩阵知问题（１）的解非常多，除对角元素之外的许多可行分配都是最优解，其
万
方数据最优目标函数值为１５ｎ＋５ｎ２．
例３．矩阵元素为
砰ｆ＝１０＋５ｉ＋５Ｊ；雄＝１０，１５。２０，２５，３０，３５。４０，４５，５０
（８）
问题（２）的最优目标函数值是１５＋跏，最优解是惟一的，即矩阵的左下至右上对角线分配．
对于元素为（８）的代价矩阵，由相对代价矩阵知问题（１）的解有，ｌ！个，即矩阵（８）的任何可行任务分配都是问题（１）的最优解。其最优目标函数值均为１５ｎ＋Ｓｎ２．
为了考察矩阵作业法对例ｌ～例３的求解情况．先令行＝５和ｎ一６，表１给出问题（２）解答的行列分配及其代价．注意疗＝６时例１有两种解答。咒＝５时例２有四种解答．表１给出的解答不是左下至右上对角线分配．而是符合“单项最优分配”原则，即在团队完成任务时间最短的前提下，还考虑单项任务用最小的代价去完成．当然，“单项最优分配”只能在问题（２）有多解时才会出现．通常，极大极小任务分配问题（２）存在多解．对例２和例３。矩阵作业法直接求解问题（２）得到的解答也是问题（１）的解，但例１不是这样．
表１问题（２）解答示例
Ｔａｂｌｅ１
Ｓｏｌｕｔｉｏｎｅｘａｍｐｌｅｓｏｆｔｈｅｐｒｏｂｌｅｍ（２）
ｎ＝５
ｎ＝６
．４０
４０３５４０４０４５４５
４５４５３５４５例１
５—１
４—２３—３２—４１—５６－１５—２
１—６２—５３—３４—４．．４０
４０４０３５４５４５４５４５４５４５４５例２
５—１
４一Ｚ１—５２—３３—４６・１５・２４—３３—４Ｚ一５１－６～
４０４０４０４０４０４５４５４５４５４５４５例３
５—１
４—２
３—３
２—４
１－５
６一ｌ
５—２
４—３
３—４
２—５
１—６
表２列出”＝１０一５０时对例１一例３求解问题（２）的全部计算时间．包括生成代价矩阵及显示结果的时间都统计在内．
用时最多的是行＝４５时例２．约花了０．１２５秒，原因是多运行
了一轮Ｒ。＝２４５的覆盖．由表２看出矩阵作业法的运算效率极高，它完全适合于极大极小任务分配问题与总体极小任务分配问题的在线求解．
继续增大ｎ，类似于表２的测试自然可以做下去．我们对例１做了行＝１００和１０００的测试，时间分别为０．２５０和１６１．８２８秒；又对例２做了起一１０１和１００１的测试，时间分别为０．４２２和２５３．７５０秒．行＝１０００阶的问题（２），矩阵作业法求解时间不超过５分钟．根据我们的经验，即使等量面法能求解混合整数线性规划（４），对于１０００阶的问题，在ＰＣ机上求得解答需要２０分钟以上［３］，而１０００阶的混合整数线性规划问题，只
相当于√１０００≈－３１阶任务分配问题．
表２问题（２）的求解时间
Ｔａｂｌｅ２
Ｔｉｍｅｓｏｌｖｉｎｇｔｈｅｐｒｏｂｌｅｍ（２）
ｎ
１０１５２０
２５３０３５４０４５５０倒１０．０３１０．０３１０．０３１０．０６３
０．０６３０．０６３０．０７８０．１０９０．１０９倒２０．０３１０．０６３０．０３１０．０９４
０．０６３０．１０９０．０９４０．１２５０．０９４例３
０．０３１
０．０３１
０．０３１
０．０６３
０．０６３
０．０６３
０．０７８
０．０７８
０．０９４
表３是借助于相对代价矩阵，矩阵作业法给出问题（１）的
个，而矩阵的左下至右上对角线分配总是一种最优任务分配．
４期
聂明泓等：任务分配问题的建模与求解
７１５
解答元素及其行列分配，最优目标函数值为各元素之和．结果完全符合关于例ｌ一例３的注释．
将（８）的各元素反号而形成负利润矩阵，最优解也有死！个。最优目标函数值为一１５ｎ一５ｎ２．可见．对于元素为（８）的矩阵，任务分配的最小总代价或最大总利润是一样的．其实，只要矩
表３问题（１）解答示例
Ｔａｂｌｅ３
Ｓｏｌｕｔｉｏｎｅｘａｍｐｌｅｓｏｆｔｈｅ
ｐｒｏｂｌｅｍ（１）
阵每行（或列）元素为同一公差的等差级数，任务分配的最小万
方数据Ｒｅｆｅｒｅｎｃｅｓ：
［１］ＫｕｈｎＨＷ．Ｔｈｅ
ｈｕｎｇａｒｉａｎ
ｍｅｔｈｏｄｆｏｒｔｈｅ
ａｓｓｉｇｎｍｅｎｔｐｒｏｂｌｅｍ
［Ｊ］．ＮａｖａｌＲｅｓｅａｒｃｈ
Ｌｏｇｉｓｔｉｃｓ
Ｑｕａｒｔ。１９５５。２：８３—９７．
［２］ＮｉｅＹＹ。ＳｕＬＪ，ＬｉＣ．Ａｎｉｓｏｍｅｔｒｉｃ
ｓｕｒｆａｃｅ
ｍｅｔｈｏｄｆｏｒ
ｉｎｔｅｇｅｒ
ｌｉｎｅａｒ
ｐｒｏｇｒａｍｍｉｎｇＥＪ］．Ｉｎｔｅｒ．Ｊ．ＣｏｍｐｕｔｅｒＭａｔｈ．・２００３，８０
（７）：８３５—８４４．
［３］ＹａｎｇＬ
Ｙ，ＨａｎＪＤ。ＳｕＬＪ。ｅｔａ１．Ｉｓｏｍｅｔｒｉｃｓｕｒｆａｃｅｍｅｔｈｏｄａｎｄ
ｉｔｓ
ｎｕｍｅｒｉｃａｌ
ｔｅｓｔｓ
ｆｏｒｍｉｘｅｄ—ｉｎｔｅｇｅｒ
ｌｉｎｅａｒ
ｐｒｏｇｒａｍｍｉｎｇ［Ｊ］．
ＩＳＡＳＴＴｒａｎｓａｃｔｉｏｎｓｏｎ
Ｃｏｍｐｕｔｅｒｓａｎｄ
Ｓｏｆｔｗａｒｅ
Ｅｎｇｉｎｅｅｒｉｎｇ，
２００８，２（１）：４Ｚ・４６．
［４］ＮｉｅＹｉ—ｙｏｎｇ，ＸｕＳＲ．Ａｎｉｓｏｍｅｔｒｉｃ
ｐｌａｎｅ
ｍｅｔｈｏｄｆｏｒｌｉｎｅａｒｐｒｏ－
ｇｒａｍｍｉｎｇｒＪ－Ｉ．ＪｏｕｒｎａｌｏｆＣｏｍｐｕｔａｔｉｏｎａｌ．Ｍａｔｈ．．１９９１．９（３）：
２６２—２７２．
［５］ＮｉｅＹＹ，ＳｏｎｇＸｉａｎｇ，ＳｕＬｉ．ｊｉｅ。ｅｔａ１．Ｗｅｌｌ—ｉｍｐｌｉｅｄａｎｄ
ｎｅａｒ－
ｉｍｐｌｉｅｄ
ｅｎｕｍｅｒａｔｉｏｎｓ
ＣＪ］．ＩｎｆｏｒｍａｔｉｏｎａｎｄＣｏｎｔｒｏｌ，２００５。３４
（３）：２９６．３０２．
附中文参考文献：
［５］聂义勇，宋翔・苏丽杰，等・良性隐式枚举与近隐式枚举［Ｊ］・信息
与控制．２００５，３４（３）１２９６－３０２．
总代价或最大总利润就是一样．作为推论，此结果意味着对若干能力相当的人不必强行分配任务．
任务分配问题的建模与求解
作者：作者单位：
聂明泓， 杨丽英， 聂义勇， NIE Ming-hong， YANG Li-ying， NIE Yi-yong
聂明泓,NIE Ming-hong(沈阳神州数码有限公司,辽宁,沈阳,110004)， 杨丽英,聂义勇,YANGLi-ying,NIE Yi-yong(中国科学院,沈阳自动化研究所,机器人学国家重点实验室,辽宁,沈阳,110016)
小型微型计算机系统
JOURNAL OF CHINESE COMPUTER SYSTEMS2009,30(4)
刊名：英文刊名：年，卷(期)：
参考文献(5条)
1.Kuhn H W The hungarian method for the assignment problem 1955
2.Nie Y Y;Su L J;Li C An isometric surface method for integer linear programming[外文期刊] 2003(07)3.Yang L Y;Han J Do Su L J Isometric surface method and its numerical tests for mixed-integer linearprogramming 2008(01)
4.Nie Yi-yong;Xu S R An isometric plane method for linear programming 1991(03)5.聂义勇;宋翔;苏丽杰 良性隐式枚举与近隐式枚举[期刊论文]-信息与控制 2005(03)
本文读者也读过(6条)
1. 鄢超波.赵千川 任务分配问题的研究进展与算法比较[会议论文]-2008
2. 杨冬.王正欧 改进的蚂蚁算法求解任务分配问题[期刊论文]-天津大学学报2004,37(4)
3. 王灵霞.张远平.吴佩莉.WANG Ling-xia.ZHANG Yuan-ping.WU Pei-li 蚁群算法求解分布式系统任务分配问题[期刊论文]-计算机工程与设计2008,29(6)
4. 王雅琳.王宁.阳春华.桂卫华.WANG Ya-lin.WANG Ning.YANG Chun-hua.GUI Wei-hua 求解任务分配问题的一种离散微粒群算法[期刊论文]-中南大学学报（自然科学版）2008,39(3)
5. 王秀宏.王正欧.乔清理.WANG Xiu-hong.WANG Zheng-ou.QIAO Qing-li 用具有混沌特性的神经网络解任务分配问题[期刊论文]-系统工程学报2001,16(2)
6. 李大林.李杰.LI Da-lin.LI Jie 基于PSO算法的多巡飞器任务分配方法[期刊论文]-北京理工大学学报2010,30(12)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_xxwxjsjxt200904026.aspx