一類指派問題的改進(jìn)矩陣解法

摘要本文紹了求歷時最短指派問題，給出了改進(jìn)矩陣解法的求解步驟，論述了這種解法的合理性，最后舉例說明了這種解法的方便可行性。關(guān)鍵詞：指派題改進(jìn)矩陣解整數(shù)劃效率矩陣1.引言我們經(jīng)常遇到這樣的問題需要完成某n項(xiàng)任有n個可承擔(dān)這些任務(wù)。由于每個人的專長不同，每個人完成某項(xiàng)任務(wù)的效率也不同，于是產(chǎn)生了應(yīng)指派哪個人去完成哪項(xiàng)任務(wù)，才能使完成這n項(xiàng)務(wù)的總效率最高，或者說是所用總時間最短的問題，這類問題被稱為指派問題或分派問１―２這類指派問題的特點(diǎn)我們可以用匈牙利法等方法求解，但其過程非常復(fù)雜，容易出現(xiàn)錯誤。以下介紹一種求解這類指派問題的較為簡便的方法――改進(jìn)矩陣解法。2.改進(jìn)矩陣解法的步驟指派問題是整數(shù)規(guī)劃0―規(guī)的特例是運(yùn)輸問題的特例因當(dāng)然可以用整數(shù)規(guī)劃、0―規(guī)或運(yùn)輸問題的解求解，即可用枚舉法和表上作業(yè)法等方法求解，但這就如同用單純形法求解運(yùn)輸問題一樣是不劃算的常利用指派問題的特點(diǎn)來求解指派問題，即匈牙利法。但這種方法的過程太過于繁瑣，且容易出錯。下面給出一種求解歷時最短的指派問題的新解法，即矩陣解法。具體的方法和步驟如下―第一步：利用最小―最大元素法給出初始指派。1）找出效率矩陣中每一列元素的最小元素，記為j=12，…m，若有不止一個最小元素，可任選其一試行；2效矩陣中每一列元素的小元素中的最大者不一個最大元素，亦可任選其一試行；3）給元素加（搖時將效率矩陣中其所在的行和列劃去4重復(fù)以上三步分別可得到θθ…θ此所有（者便構(gòu)成一個初始指派。第二步：檢驗(yàn)初始指派，具體方法如下。找出所有加（）中的最大者，記θ，為了說明方便，我們不妨假θ=θθ=a（為效率矩陣中對角線上的元素，j=1，…，別將θ與θ（j=2…，）所位于的行和列中交叉位置的四個元素取出構(gòu)成一個二階方陣。即）aa（）1若a≤max{a（…m始派即為所求指派問題解決結(jié)否，進(jìn)入下一步。2）若a＞max{a（，…ma和的括號去掉，并給對應(yīng)的a和a加返回第二步，重新檢驗(yàn)，直到結(jié)束為止。3）若通過檢驗(yàn)條件1定指派問題的解，此時如果所有加（）的元素中存在這樣兩個處于對角線位置的元素，其和與另一側(cè)對角線上的兩個元素之和相等，則可以去掉這兩個加（）元素的（給一對角線上的兩個元素加（得的新指派問題也是原指派問題的解。另外，第二步中的3）是檢驗(yàn)指問題存在重解的一種情況。當(dāng)條件滿足時，所求指派問題一定存在重解，且按照3）方法即可求得一個重解，但當(dāng)條件不滿足時，所求指派問題也有可能存在重解。3.論述求解歷時最短的指派問題，實(shí)質(zhì)就是要解決兩個問題在n階數(shù)矩陣中確定n個獨(dú)立元素證確定的指派中的的個獨(dú)元素之和是所有情況中最小的的獨(dú)

立元素是指系數(shù)矩陣中既非同行又非同列的元素）下面我們來逐一分析上述矩陣解法的步驟。第一步是利用最小―最大元素法給出初始指派的過程，最小―最大元素法雖然不能保證所選初始指派中的元素之和最小以證接近最小在定程度上減少了計算步驟，簡化了求解過程。通過對步驟3的反復(fù)操作，保證了二維關(guān)系中一對一的關(guān)系，即：保證了所給出的初始指派中的元素為獨(dú)立元素。第二步是檢驗(yàn)初始指派的過程的是在保證初始指派中的元素為獨(dú)立元素的基礎(chǔ)上，尋求其元素之和為最小的情況確定了指派問題的解后果存在上述步驟3中的情況，就說明該指派問題一定存在重解，通過步驟）的操作，既保證了不改變所有加（）元素的獨(dú)立性證新的指派所用時間或效率與原指派相同指也是原指派問題的解。4.例子例1.現(xiàn)有一份中文資料需譯成、日、德、俄文字，今讓甲、乙、丙、丁4人時去完成，每人譯且僅譯一種文字。他們對這四種語言皆精通，但個人專長不同，因此翻譯同一種語言所用時間有別，具體情況如表1所示試問如果四人同時開始翻譯，應(yīng)如何安排工作可使翻譯歷時最短［１］？表1解：該指派問題的效率矩陣為：a=21513410491416138119（）據(jù)步驟一求初始指派如下：a=［2］1513［4］10［］1415141613711→21541041415914161378（11）→［2］1513［］10［］15916137（）→21513410（）1591416137（）→［］15134］10（）141591478（）9→1513（）10（）141591416138（11→21513（）10（）1415（）16137（11）9（）據(jù)步驟二檢驗(yàn)初始指派如下：此時=11=a，由于在二階方陣13（））（）9）（11）中均滿足檢驗(yàn)條件1題解決，結(jié)束。即：甲→譯成俄文，乙→譯成日文，丙→譯成英文，丁→譯成德文。例2.求表2所效率矩陣的指派問題的最小解［１表2解：該指派問題的效率矩陣：a=1279798966671712149151461047109（）據(jù)步驟一求初始指派如下：a=12［7］97989［］［］［6］7171214915146610［4］107109→（）7989667171214915146610412797989［］7171214915146［］10710912（797989666717129156104107109→12（）97989（）67171214［］15146［］［］107109→12（）97989（）667171214915146→（7）9798（6）6671712（）146［］104］1010（）97989（）67171214（）146（）104107109→（）979896）171214（）146（）10（）107109（）據(jù)步驟二檢驗(yàn)初始指派如下：此時=9=a由于在二階方陣6612（（10（9917（）均滿足檢驗(yàn)條件1題決，結(jié)束。觀察可見有）66（改6（）6，：存在重解，且可知原指問題的最優(yōu)指派方案為：甲，乙c，丙e，丁d，戊

→或→，乙→，→，→，戊。5.結(jié)語本文主要介紹了求解歷時最短或效率最高的指派問題的一