基于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

寸曉非]