李 冉

(荊楚理工學(xué)院 計(jì)算機(jī)工程學(xué)院，湖北 荊門 448000)

基于Liangze Zhou變換的n-n型指派計(jì)算的實(shí)現(xiàn)

李 冉

(荊楚理工學(xué)院 計(jì)算機(jī)工程學(xué)院，湖北 荊門 448000)

文章主要在研究周良澤的指派求解理論和周良澤-張立昂算法的基礎(chǔ)上，利用Liangze Zhou變換法則，設(shè)計(jì)一種n-n型指派問題求解的實(shí)現(xiàn)方案，最后用Java語言實(shí)現(xiàn)一個(gè)可視化的通用計(jì)算工具，并調(diào)試運(yùn)行。結(jié)果證明，該實(shí)現(xiàn)方案效率高，結(jié)果易于理解。

指派問題； Liangze Zhou變換； 實(shí)現(xiàn)方案

0 引言

指派問題是一個(gè)經(jīng)典的運(yùn)籌學(xué)問題，在實(shí)際的工作生產(chǎn)中經(jīng)常用到。n-n型指派是指派問題中的一種，比如n人n事最低耗費(fèi)的指派、最大效益的指派等，數(shù)學(xué)模型表示如下：

設(shè)指派矩陣A=(aij)n×n,aij是矩陣中的一個(gè)元素，表示第i個(gè)人做第j件事的耗費(fèi)值；指派矩陣中存在一組元素，分別為ai1j1、ai2j2、…、ainjn，它們不同行不同列，該組元素滿足：

則該組元素為指派矩陣中的一種最優(yōu)的任務(wù)指派。

文獻(xiàn)[1]中周良澤提出并證明了兩個(gè)定理，構(gòu)成指派問題求解的完備理論，內(nèi)容如下：

文獻(xiàn)[2]中張立昂提出的算法是基于以上指派求解理論所設(shè)計(jì)的一種求解算法，大致思想是對指派矩陣A=(aij)n×n逐行求行最小元。設(shè)已求得k個(gè)不同行不同列的行最小元ai1j1，ai2j2,…,aikjk，對A關(guān)于行最小元ai1j1，ai2j2,…,aikjk進(jìn)行同解變換，然后得到k+1個(gè)不同行不同列的行最小元；重復(fù)上述步驟，直到求得A的n個(gè)不同列的行最小元為止。

本文對指派問題求解的研究基于文獻(xiàn)[1]中周良澤提出的指派理論，利用文獻(xiàn)[2]中提到的周良澤-張立昂算法，抽象出通用的指派計(jì)算模型，實(shí)現(xiàn)一個(gè)快速計(jì)算不同規(guī)模的n-n型最低耗費(fèi)指派的工具。

1 指派計(jì)算工具的功能需求和設(shè)計(jì)

1.1 功能需求

本文研究并實(shí)現(xiàn)的計(jì)算工具是一個(gè)智能化的工具，除了根據(jù)用戶的需求輸入任務(wù)規(guī)模、原始耗費(fèi)矩陣，進(jìn)行計(jì)算并展示計(jì)算結(jié)果外，還能夠展示計(jì)算過程、保存或打開計(jì)算數(shù)據(jù)、一步一步展示計(jì)算細(xì)節(jié)等。該計(jì)算工具可用于科學(xué)研究、實(shí)驗(yàn)分析、教學(xué)等。

1.2 功能邏輯結(jié)構(gòu)設(shè)計(jì)

為了實(shí)現(xiàn)展示詳細(xì)的計(jì)算過程，本工具將計(jì)算模塊、展示模塊和數(shù)據(jù)存儲(chǔ)分開，計(jì)算和展示共用一個(gè)公共數(shù)據(jù)區(qū)。在計(jì)算模塊中，每一計(jì)算步驟的中間數(shù)據(jù)都存入公共數(shù)據(jù)區(qū)；展示模塊根據(jù)原始矩陣和計(jì)算過程數(shù)據(jù)生成計(jì)算過程展示板，也保存在公共數(shù)據(jù)區(qū)中。用戶選擇全部展開、上一步、下一步等功能時(shí)，工具只是將相應(yīng)的展示板展示出來。

整個(gè)計(jì)算工具功能模塊邏輯結(jié)構(gòu)如圖1所示：

圖1 總體功能模塊邏輯結(jié)構(gòu)

2 工具的實(shí)現(xiàn)

該計(jì)算工具用面向?qū)ο蟮腏ava語言進(jìn)行了全部功能的實(shí)現(xiàn)，并打包生成了能獨(dú)立運(yùn)行的桌面應(yīng)用程序。其中指派計(jì)算功能的實(shí)現(xiàn)是本工具的核心部分，主要依據(jù)周良澤的指派理論和周良澤-張立昂算法。本節(jié)以下部分重點(diǎn)講述指派計(jì)算的實(shí)現(xiàn)方法。

2.1 相關(guān)術(shù)語

為了實(shí)現(xiàn)周良澤-張立昂算法，并能形象地展示計(jì)算過程，本文約定了一些基本術(shù)語：

1)框元：指派矩陣的一行中被選定的行最小元，本文實(shí)現(xiàn)的計(jì)算工具中用紅色方框標(biāo)記，稱為框元。

2)計(jì)算階段：在周良澤-張立昂算法中，對已求得的k個(gè)不同行不同列的框元進(jìn)行Liangze Zhou同解變換后，從而求得k+1個(gè)不同行不同列的框元的計(jì)算過程稱為一個(gè)計(jì)算階段。

3)非框元矩陣：在n-n指派矩陣中，假如已經(jīng)求得了前k(0

4)A(k)矩陣：表示已標(biāo)記k個(gè)框元的同解矩陣。

2.2 計(jì)算并展示結(jié)果的運(yùn)算流程

本計(jì)算工具是可視化的計(jì)算工具，用戶通過數(shù)據(jù)輸入模塊輸入矩陣規(guī)模和耗費(fèi)矩陣后，即可計(jì)算并展示結(jié)果。當(dāng)用戶重新輸入矩陣規(guī)模及耗費(fèi)矩陣后，本工具重新計(jì)算并展示。計(jì)算及結(jié)果展示的流程如圖2所示：

圖2 計(jì)算及結(jié)果展示流程圖

2.3 公共數(shù)據(jù)區(qū)模塊的實(shí)現(xiàn)

公共數(shù)據(jù)區(qū)是本工具的數(shù)據(jù)倉庫，存儲(chǔ)著原始耗費(fèi)矩陣、中間同解變換矩陣列表、變換過程中每個(gè)同解矩陣的框元列表、展示板列表等。公共數(shù)據(jù)區(qū)中的數(shù)據(jù)能被其他模塊訪問，所以本工具中定義了PublicData.java類，用類的靜態(tài)成員來實(shí)現(xiàn)，主要成員如表1所示：

表1 公共數(shù)據(jù)區(qū)主要成員列表

2.4 指派計(jì)算

指派計(jì)算是對周良澤-張立昂算法的具體實(shí)現(xiàn)，本文中定義了Calcuator.java類用于實(shí)現(xiàn)這個(gè)功能。

2.4.1 指派計(jì)算模型

對于給定的源耗費(fèi)矩陣A=(aij)n×n，求解思路是逐行求解框元，求得n個(gè)不同行不同列的框元時(shí)，求解結(jié)束。根據(jù)周良澤-張立昂算法，對于已求得的k(0

計(jì)算過程中，框元用Point類對象來描述，記錄所在的行號和列號，每一步變換所得的k個(gè)框元(0

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

{

if(i==1) { // 表明第1個(gè)計(jì)算階段

由源指派矩陣A中第1行，找到最小元為框元，保存該階段的框元列表；

將A(1)矩陣保存到公共數(shù)據(jù)區(qū)pdDatas中;

}elseif(i==n) { // 表明是第n個(gè)計(jì)算階段(最后1個(gè)計(jì)算階段)

對第n-1個(gè)計(jì)算階段所保存的A(n-1)矩陣進(jìn)行Liangze Zhou變換，求解A(0);

由A(0)獲取第n個(gè)框元，檢測沖突，并進(jìn)行調(diào)整，使得n個(gè)框元不同行不同列；

保存過程數(shù)據(jù)；

求解結(jié)束；

}else{ // 表明為第i個(gè)計(jì)算階段

由第i-1個(gè)計(jì)算階段所保存的A(i-1)矩陣進(jìn)行Liangze Zhou變換，求解A(0);

由A(0)獲取第i個(gè)框元，檢測沖突，并進(jìn)行調(diào)整，使得i個(gè)框元不同行不同列；

保存過程數(shù)據(jù)；

}

}

2.4.2 Liangze Zhou變換

Liangze Zhou變換為周良澤教授提出的矩陣同解變換法則。一次Liangze Zhou變換是第k(k≤n)個(gè)計(jì)算階段的計(jì)算內(nèi)容，使得矩陣中已求得的每個(gè)框元所在行中至少存在一個(gè)與框元等值的元，目的是在矩陣前k+1行中能夠找到k+1個(gè)不同行不同列的框元，即找到k+1個(gè)行最小元。

變換思想為由A(k)逐個(gè)消除框元，變換過程為求解A(k-1),A(k-2)，…，A(0)。Calculator.java類中的delOneKy(int[][] src, ArrayList kyList)方法用于實(shí)現(xiàn)由A(m)求解A(m-1)，同時(shí)保存過程數(shù)據(jù)。求解方法為：

1)由A(m)對應(yīng)的框元列表求解非框元矩陣；

2)求解每個(gè)框元與對應(yīng)的非框元矩陣中行的最小元的差值；

3)找到第(2)步中求得的m個(gè)差值最小值α及所在的行號i(非框元矩陣中的行號)；

4)將第i個(gè)框元所在列每個(gè)元素都加上α；

5)消除第i個(gè)框元得矩陣A(m-1)及其剩余的框元列表，加入公共數(shù)據(jù)區(qū)。

圖3～4為對一個(gè)4階矩陣求解過程中，通過delOneKy方法，由A(3)求解A(2)的模擬圖。

圖3 A(3)矩陣及框元?jiǎng)h除方法

圖4 A(2)矩陣

2.5 展示計(jì)算模塊

本文中對指派計(jì)算的過程和結(jié)果，都是將數(shù)據(jù)畫在Panel對象中，然后展示在窗體上。其中計(jì)算過程的展示是重中之重，主要通過公共數(shù)據(jù)區(qū)中的中間過程矩陣pdDatas對象和對應(yīng)的框元數(shù)組列表kyPosList對象，將計(jì)算過程模擬出來，每一步的數(shù)據(jù)畫在一個(gè)Panel對象上，所有的Panel對象構(gòu)成一個(gè)列表，存儲(chǔ)在公共數(shù)據(jù)區(qū)中。上一步、下一步和全部展開功能只需從公共數(shù)據(jù)區(qū)中調(diào)取對應(yīng)的Panel對象展示在窗體上就可以了。

3 編碼與調(diào)試運(yùn)行

本指派計(jì)算工具的編碼在eclipse中完成，JDK版本為1.6，調(diào)試運(yùn)行效果如圖5所示。

圖5 指派計(jì)算工具運(yùn)行效果圖

4 總結(jié)

本文是對一個(gè)指派計(jì)算工具實(shí)現(xiàn)的研究，所研究開發(fā)的工具能夠計(jì)算不同n值的n-n型指派問題，并展示計(jì)算過程。該工具計(jì)算速度快，使用方便、易懂，也易于根據(jù)周良澤的理論將其擴(kuò)展為求解n-2n甚至是n-kn的指派計(jì)算工具。

[1] 周良澤.消高排除法求解指派問題[J].系統(tǒng)工程學(xué)報(bào),1992，7(2)：97-105.

[2] 張立昂.指派問題的新算法[C]//理論計(jì)算機(jī)科學(xué)進(jìn)展.北京：國防大學(xué)出版社,1994：63-65.

2014-06-19

荊楚理工學(xué)院校級科研項(xiàng)目：指派計(jì)算工具的實(shí)現(xiàn)(ZR201309)

李冉(1979-)，男，河南潢川人，荊楚理工學(xué)院講師，碩士。研究方向：程序設(shè)計(jì)、軟件開發(fā)、分布式計(jì)算等。

TP311.56;O22

A

1008-4657(2014)04-0027-05

寸曉非]