基于Liangze Zhou变换的n-n型指派计算的实现

李 冉

(荆楚理工学院 计算机工程学院，湖北 荆门 448000)

基于Liangze Zhou变换的n-n型指派计算的实现

李 冉

(荆楚理工学院 计算机工程学院，湖北 荆门 448000)

文章主要在研究周良泽的指派求解理论和周良泽-张立昂算法的基础上，利用Liangze Zhou变换法则，设计一种n-n型指派问题求解的实现方案，最后用Java语言实现一个可视化的通用计算工具，并调试运行。结果证明，该实现方案效率高，结果易于理解。

指派问题； Liangze Zhou变换； 实现方案

0 引言

指派问题是一个经典的运筹学问题，在实际的工作生产中经常用到。n-n型指派是指派问题中的一种，比如n人n事最低耗费的指派、最大效益的指派等，数学模型表示如下：

设指派矩阵A=(aij)n×n,aij是矩阵中的一个元素，表示第i个人做第j件事的耗费值；指派矩阵中存在一组元素，分别为ai1j1、ai2j2、…、ainjn，它们不同行不同列，该组元素满足：

则该组元素为指派矩阵中的一种最优的任务指派。

文献[1]中周良泽提出并证明了两个定理，构成指派问题求解的完备理论，内容如下：

文献[2]中张立昂提出的算法是基于以上指派求解理论所设计的一种求解算法，大致思想是对指派矩阵A=(aij)n×n逐行求行最小元。设已求得k个不同行不同列的行最小元ai1j1，ai2j2,…,aikjk，对A关于行最小元ai1j1，ai2j2,…,aikjk进行同解变换，然后得到k+1个不同行不同列的行最小元；重复上述步骤，直到求得A的n个不同列的行最小元为止。

本文对指派问题求解的研究基于文献[1]中周良泽提出的指派理论，利用文献[2]中提到的周良泽-张立昂算法，抽象出通用的指派计算模型，实现一个快速计算不同规模的n-n型最低耗费指派的工具。

1 指派计算工具的功能需求和设计

1.1 功能需求

本文研究并实现的计算工具是一个智能化的工具，除了根据用户的需求输入任务规模、原始耗费矩阵，进行计算并展示计算结果外，还能够展示计算过程、保存或打开计算数据、一步一步展示计算细节等。该计算工具可用于科学研究、实验分析、教学等。

1.2 功能逻辑结构设计

为了实现展示详细的计算过程，本工具将计算模块、展示模块和数据存储分开，计算和展示共用一个公共数据区。在计算模块中，每一计算步骤的中间数据都存入公共数据区；展示模块根据原始矩阵和计算过程数据生成计算过程展示板，也保存在公共数据区中。用户选择全部展开、上一步、下一步等功能时，工具只是将相应的展示板展示出来。

整个计算工具功能模块逻辑结构如图1所示：

图1 总体功能模块逻辑结构

2 工具的实现

该计算工具用面向对象的Java语言进行了全部功能的实现，并打包生成了能独立运行的桌面应用程序。其中指派计算功能的实现是本工具的核心部分，主要依据周良泽的指派理论和周良泽-张立昂算法。本节以下部分重点讲述指派计算的实现方法。

2.1 相关术语

为了实现周良泽-张立昂算法，并能形象地展示计算过程，本文约定了一些基本术语：

1)框元：指派矩阵的一行中被选定的行最小元，本文实现的计算工具中用红色方框标记，称为框元。

2)计算阶段：在周良泽-张立昂算法中，对已求得的k个不同行不同列的框元进行Liangze Zhou同解变换后，从而求得k+1个不同行不同列的框元的计算过程称为一个计算阶段。

3)非框元矩阵：在n-n指派矩阵中，假如已经求得了前k(0

4)A(k)矩阵：表示已标记k个框元的同解矩阵。

2.2 计算并展示结果的运算流程

本计算工具是可视化的计算工具，用户通过数据输入模块输入矩阵规模和耗费矩阵后，即可计算并展示结果。当用户重新输入矩阵规模及耗费矩阵后，本工具重新计算并展示。计算及结果展示的流程如图2所示：

图2 计算及结果展示流程图

2.3 公共数据区模块的实现

公共数据区是本工具的数据仓库，存储着原始耗费矩阵、中间同解变换矩阵列表、变换过程中每个同解矩阵的框元列表、展示板列表等。公共数据区中的数据能被其他模块访问，所以本工具中定义了PublicData.java类，用类的静态成员来实现，主要成员如表1所示：

表1 公共数据区主要成员列表

2.4 指派计算

指派计算是对周良泽-张立昂算法的具体实现，本文中定义了Calcuator.java类用于实现这个功能。

2.4.1 指派计算模型

对于给定的源耗费矩阵A=(aij)n×n，求解思路是逐行求解框元，求得n个不同行不同列的框元时，求解结束。根据周良泽-张立昂算法，对于已求得的k(0

计算过程中，框元用Point类对象来描述，记录所在的行号和列号，每一步变换所得的k个框元(0

for(inti=1 ;i<=n;i++)

{

if(i==1) { // 表明第1个计算阶段

由源指派矩阵A中第1行，找到最小元为框元，保存该阶段的框元列表；

将A(1)矩阵保存到公共数据区pdDatas中;

}elseif(i==n) { // 表明是第n个计算阶段(最后1个计算阶段)

对第n-1个计算阶段所保存的A(n-1)矩阵进行Liangze Zhou变换，求解A(0);

由A(0)获取第n个框元，检测冲突，并进行调整，使得n个框元不同行不同列；

保存过程数据；

求解结束；

}else{ // 表明为第i个计算阶段

由第i-1个计算阶段所保存的A(i-1)矩阵进行Liangze Zhou变换，求解A(0);

由A(0)获取第i个框元，检测冲突，并进行调整，使得i个框元不同行不同列；

保存过程数据；

}

}

2.4.2 Liangze Zhou变换

Liangze Zhou变换为周良泽教授提出的矩阵同解变换法则。一次Liangze Zhou变换是第k(k≤n)个计算阶段的计算内容，使得矩阵中已求得的每个框元所在行中至少存在一个与框元等值的元，目的是在矩阵前k+1行中能够找到k+1个不同行不同列的框元，即找到k+1个行最小元。

变换思想为由A(k)逐个消除框元，变换过程为求解A(k-1),A(k-2)，…，A(0)。Calculator.java类中的delOneKy(int[][] src, ArrayList kyList)方法用于实现由A(m)求解A(m-1)，同时保存过程数据。求解方法为：

1)由A(m)对应的框元列表求解非框元矩阵；

2)求解每个框元与对应的非框元矩阵中行的最小元的差值；

3)找到第(2)步中求得的m个差值最小值α及所在的行号i(非框元矩阵中的行号)；

4)将第i个框元所在列每个元素都加上α；

5)消除第i个框元得矩阵A(m-1)及其剩余的框元列表，加入公共数据区。

图3～4为对一个4阶矩阵求解过程中，通过delOneKy方法，由A(3)求解A(2)的模拟图。

图3 A(3)矩阵及框元删除方法

图4 A(2)矩阵

2.5 展示计算模块

本文中对指派计算的过程和结果，都是将数据画在Panel对象中，然后展示在窗体上。其中计算过程的展示是重中之重，主要通过公共数据区中的中间过程矩阵pdDatas对象和对应的框元数组列表kyPosList对象，将计算过程模拟出来，每一步的数据画在一个Panel对象上，所有的Panel对象构成一个列表，存储在公共数据区中。上一步、下一步和全部展开功能只需从公共数据区中调取对应的Panel对象展示在窗体上就可以了。

3 编码与调试运行

本指派计算工具的编码在eclipse中完成，JDK版本为1.6，调试运行效果如图5所示。

图5 指派计算工具运行效果图

4 总结

本文是对一个指派计算工具实现的研究，所研究开发的工具能够计算不同n值的n-n型指派问题，并展示计算过程。该工具计算速度快，使用方便、易懂，也易于根据周良泽的理论将其扩展为求解n-2n甚至是n-kn的指派计算工具。

[1] 周良泽.消高排除法求解指派问题[J].系统工程学报,1992，7(2)：97-105.

[2] 张立昂.指派问题的新算法[C]//理论计算机科学进展.北京：国防大学出版社,1994：63-65.

2014-06-19

荆楚理工学院校级科研项目：指派计算工具的实现(ZR201309)

李冉(1979-)，男，河南潢川人，荆楚理工学院讲师，硕士。研究方向：程序设计、软件开发、分布式计算等。

TP311.56;O22

A

1008-4657(2014)04-0027-05

寸晓非]