一類指派問題的改進矩陣解法

　　摘 要： 本文介紹了求歷時最短的指派問題，給出了改進矩陣解法的求解步驟，論述了這種解法的合理性，最后舉例說明了這種解法的方便可行性。
　　關鍵詞： 指派問題 改進矩陣解法 整數規劃 效率矩陣
　　
　　1.引言
　　我們經常遇到這樣的問題：某單位需要完成某n項任務，恰好有n個人可承擔這些任務。由于每個人的專長不同，每個人完成某項任務的效率也不同，于是產生了應指派哪個人去完成哪項任務，才能使完成這n項任務的總效率最高，或者說是所用總時間最短的問題，這類問題被稱為指派問題或分派問題［１—２］。根據這類指派問題的特點，我們可以用匈牙利法等方法求解，但其過程非常復雜，容易出現錯誤。以下介紹一種求解這類指派問題的較為簡便的方法——改進矩陣解法。
　　2.改進矩陣解法的步驟
　　指派問題是整數規劃，是0—1規劃的特例，也是運輸問題的特例，因此當然可以用整數規劃、0—1規劃或運輸問題的解法求解，即可用枚舉法和表上作業法等方法求解，但這就如同用單純形法求解運輸問題一樣是不劃算的。我們通常利用指派問題的特點來求解指派問題，即匈牙利法。但這種方法的過程太過于繁瑣，且容易出錯。下面給出一種求解歷時最短的指派問題的新解法，即矩陣解法。具體的方法和步驟如下［3—5］。
　　第一步：利用最小—最大元素法給出初始指派。
　　1）找出效率矩陣中每一列元素的最小元素，記為，a，j=1，2，…，m，若有不止一個最小元素，可任選其一試行；
　　2）找出效率矩陣中每一列元素的最小元素中的最大者，記為θ，若有不止一個最大元素，亦可任選其一試行；
　　3）給元素θ加（?搖），同時將效率矩陣中其所在的行和列劃去；
　　4）重復以上三步，分別可得到θ，θ，…，θ。此時所有加（）者便構成一個初始指派。
　　第二步：檢驗初始指派，具體方法如下。
　　找出所有加（）中的最大者，記為θ，為了說明方便，我們不妨假設θ=θ，θ=a（a為效率矩陣中對角線上的元素，j=1，2，…，m），分別將θ與θ（j=2，…，m）所位于的行和列中交叉位置的四個元素取出構成一個二階方陣。
　　即：（a） aa （a）
　　1）若a≤max{a，a}（j=2，…，m），則初始指派即為所求指派，問題解決，結束。否則，進入下一步。
　　2）若a＞max{a，a}（j=2，…，m），則a將a和的括號去掉，并給對應的a和a加（）。返回第二步，重新檢驗，直到結束為止。
　　3）若通過檢驗條件1），確定了指派問題的解，此時如果所有加（）的元素中存在這樣兩個處于對角線位置的元素，其和與另一側對角線上的兩個元素之和相等，則可以去掉這兩個加（）元素的（），并給另一側對角線上的兩個元素加（），所得的新指派問題也是原指派問題的解。
　　另外，第二步中的3）是檢驗指派問題存在重解的一種情況。當條件滿足時，所求指派問題一定存在重解，且按照3）的方法即可求得一個重解，但當條件不滿足時，所求指派問題也有可能存在重解。
　　3.論述
　　求解歷時最短的指派問題，實質就是要解決兩個問題：（1）在n階系數矩陣中確定n個獨立元素；（2）保證所確定的指派中的的n個獨立元素之和是所有情況中最小的。（這里的獨立元素是指系數矩陣中既非同行又非同列的元素）
　　下面我們來逐一分析上述矩陣解法的步驟。
　　第一步是利用最小—最大元素法給出初始指派的過程，最小—最大元素法雖然不能保證所選初始指派中的元素之和最小，卻可以保證接近最小，這就在一定程度上減少了計算步驟，簡化了求解過程。通過對步驟3）的反復操作，保證了二維關系中一對一的關系，即：保證了所給出的初始指派中的元素為獨立元素。
　　第二步是檢驗初始指派的過程，其目的是在保證初始指派中的元素為獨立元素的基礎上，尋求其元素之和為最小的情況。當確定了指派問題的解后，如果存在上述步驟3）中的情況，就說明該指派問題一定存在重解，通過步驟3）的操作，既保證了不改變所有加（）元素的獨立性，又保證了新的指派所用時間或效率與原指派相同，因此新指派也是原指派問題的解。
　　4.例子
　　例1.現有一份中文資料需譯成英、日、德、俄4種文字，今讓甲、乙、丙、丁4人同時去完成，每人譯且僅譯一種文字。他們對這四種語言皆精通，但個人專長不同，因此翻譯同一種語言所用時間有別，具體情況如表1所示，試問如果四人同時開始翻譯，應如何安排工作可使翻譯歷時最短［１］？
　　表1
　　解：該指派問題的效率矩陣為：
　　A= 2 1513 410 4 1415 9 141613 7 8 11 9
　　（1）依據步驟一求初始指派如下：
　　A=［2］ 15 13 ［4］10 ［4］ 14 15 9 14 16 13 7 8 ［11］ 9→ 215 13 41041415 914 1613 7 8 （11）9→［2］ 15 13 ［4］10［4］14 15 9 14 16 13 7 8 （11）9→ 215 13410（4）14 15 914 16 13 7 8（11）9→［2］15 13 ［4］10 （4）1415 9 14 1613 78 （11）9→ 2 15 13 （4）10（4） 14 15 9 14 16 13 7 8 （11）9→215 13 （4）10 （4）1415（9）14 16137 8（11） 9
　　（2）依據步驟二檢驗初始指派如下：
　　此時θ=11=a，由于在二階方陣13（4）（11）9、（4）148（11）和（9）167（11）中均滿足檢驗條件1），問題解決，結束。即：甲→譯成俄文，乙→譯成日文，丙→譯成英文，丁→譯成德文。
　　例2.求表2所示效率矩陣的指派問題的最小解［１］。
　　表2解：該指派問題的效率矩陣為：
　　A=12 7 9 7 9 8 9 6 6 6 7 171214 91514 6 6 10 4 10 7 10 9
　　（1）依據步驟一求初始指派如下：
　　A=12［7］ 97 9 89 ［6］ ［6］ ［6］ 7 17 1214915 14 6 610［4］ 10 7 109→12（7）9 7 9 8 96 6 6 7 17 12 14915146 610 4 107109→12（7） 97 9 89 ［6］［6］［6］ 7 17 12 14 915 14 6 610［4］ 10 7109→12（7）9 79 8 96 66 71712 14 915 14（6）6 10 410 710 9→12（7） 97 9 89 （6） 6 6 7 17 12 14 ［9］15 14 6 ［6］ 10［4］ 10 7109→12（7） 979 8 9 （6） 6 6 717 12 14（9）15 146 610 4107109→12 （7） 9 79 8 9 （6）66 71712 14（9）15 14 6 ［6］ 10［4］10 7 10 9→12（7） 97 9 8 9 （6）6 6 717 12 14 （9）15 146（6）10 4107 109→12（7）9 79 89（6）66 7 171214（9）15 14 6（6）10（4） 10 7 10 9
　　（2）依據步驟二檢驗初始指派如下：
　　此時θ=9=a，由于在二階方陣（6）612（9）、14 （9）（6）10、7（9）（4）9和（7）917（9）中均滿足檢驗條件1），問題解決，結束。觀察可見有（6）66（6），可改為6（6）（6）6，即：存在重解，且可知原指派問題的最優指派方案為：甲→B，乙→C，丙→E，丁→D，戊→A或甲→B，乙→D，丙→E，丁→C，戊→A。
　　5.結語
　　本文主要介紹了求解歷時最短或效率最高的指派問題的一種新解法——改進矩陣解法，給出了它的具體步驟，并論述了這種方法的正確性，最后用例子說明了它的簡便可行性。它是一種較為簡單、快捷的求解歷時最短指派問題的方法，極大程度地簡化了求解過程，而且步驟清晰、容易操作，為從事這類問題的研究提供了極大的方便，也為促進相關問題的發展奠定了基礎。
　　
　　參考文獻：
　　［1］《運籌學》教材編寫組.運籌學［M］.北京：清華大學出版社，2005.
　　［2］吳振奎，王全文.運籌學［M］.北京：中國人民大學出版社，2006.
　　［3］王延臣，王全文，吳振奎.一個特殊指派問題及其解法［J］.天津商學院學報，2007，（06）：26-27.
　　［4］王全文，吳育華，吳振奎.整數規劃的一個線性規劃解法［J］.系統工程，2005，（07）：35-36.
　　［5］吳振奎，王全文，劉振航.運籌學中的轉化思想［J］.運籌與管理，2003，（01）：6-8.