指派問題的等價問題研究

鮑培文

（特警學院教學科研部，北京102211）

指派問題的等價問題研究

鮑培文

（特警學院教學科研部，北京102211）

任何一個指派問題有多個解決問題的渠道，每種渠道都對應一個新指派問題，這個新指派問題與原指派問題等價，即指派問題有多個等價問題.本文系統(tǒng)研究了每一指派問題的等價問題及其解法，找出不同解法之間的關系，有利于決策者快速準確進行指派問題的最優(yōu)分配.

指派問題；等價問題；研究

在日常管理工作中，往往會碰到這樣的人員分配問題：有n項任務（或工作）A1，A2，…An，需要給n個人B1，B2，…，Bn去完成，每人只能執(zhí)行一項任務.由于每個人完成每一項任務的時間（或效率）不盡相同，所以對不同的分配方案，完成任務的總時間（或總效率）也不同.如何分配某人去完成某項任務，才能使完成n項任務的時間最少（或總效率最高），這就是指派問題，它包括標準指派問題和非標準指派問題.標準指派問題是人數(shù)與事數(shù)相等、一人一事及一事一人的最小費用問題.日?；顒又幸膊环θ藬?shù)與事數(shù)可以不等、一人多事及一事多人的情形，這類事務呈現(xiàn)了指派問題非標準的實際背景.非標準指派問題是人數(shù)與事數(shù)不等，或指定一人某事、某人一事，或一人多事、一事多人，或最大效益的指派問題.由于指派問題種類繁多，模型特殊，任何一個指派問題有多個解決問題的渠道，每種渠道都對應一個新指派問題，這個新指派問題與原指派問題等價，即指派問題有多個等價問題.本文系統(tǒng)研究了每一指派問題的等價問題及其解法，找出不同解法之間的關系，有利于決策者快速準確進行指派問題的最優(yōu)分配.

1 指派問題及其解法

1.1 問題及其模型

任務分配與工作指派問題簡稱為分配問題或指派問題（Assignment Problem）.標準指派問題是：每項工作只能分配給一個單位（人或武器）去完成；每個單位（人或武器）只能接受其中一項任務的最小費用問題.標準指派問題的數(shù)學模型為：

這時稱目標函數(shù)的系數(shù)所構成的矩陣為費用矩陣或系數(shù)矩陣；滿足約束方程的解xij（i，j=1，2，…，n）構成的矩陣X=（xij）n×n為解矩陣.

從以上模型可見，指派問題是一類特殊的線性規(guī)劃和運輸問題，正是由于其模型的特殊性，求解這類問題的方法才有其特殊的方法.

1.2 標準型的匈牙利解法

匈牙利法是庫恩（W.W.Kuhn）于1955年提出的求解指派問題的算法，由于這種算法的理論根據(jù)是匈牙利數(shù)學家考尼格（D.Konig）提出的并證明了兩個定理（證明略），因此得名匈牙利法.

1.2.1 匈牙利法基本思想

定理1設指派問題的系數(shù)矩陣為A=（aij）n×n，則從A的第i行各元素中分別減去一個常數(shù)ui（i=1，2，…，n），從第j列中各元素分別減去一個常數(shù)vj（j=1，2，…，n），得到一個新的效益矩陣B=（bij）n×n，其中bij=aij-（ui+vj）（i，j=1，2，…，n），那么以B為系數(shù)矩陣求得的最優(yōu)解與原問題最優(yōu)解相同.

定理2若一個方陣中的一部分元素為0，一部分非0，則覆蓋方陣內(nèi)所有0元素的最少直線數(shù)恰好等于那些位于不同行、不同列的0元素的最多個數(shù).

匈牙利法的基本思想是：基于標準型（1），利用定理1不斷變換效益矩陣，使其含有盡可能多的“0”元素，并且始終保持所有元素非負，直到能從變換后的矩陣中找到n個位于不同行、不同列的“0”元素（簡稱為獨立0元素）為止.設最后得到的效益矩陣（bij）n×n，則以（aij）n×n為效益矩陣的指派問題與原問題同解.在（bij）n×n對應問題的解矩陣n×n中，對應這n個獨立的0元素的變量xij取值為1，其他變量取值為0，則其目標函數(shù)值為0，它是最小值，從而得到以（bij）n×n為系數(shù)矩陣的指派問題的最優(yōu)解，也是原問題的最優(yōu)解.

1.2.2 匈牙利法的計算步驟

通過舉例說明匈牙利法的具體步驟.

例1某任務有四項工作，需四個單位完成，因時間限制，每單位只能完成其中一項，單位Bj完成項目Ai所需時間如表1所示.

表1

求使總完成時間最少的分配方案.

第一步：效益矩陣的初始變換——0元素的獲得

①從系數(shù)矩陣的每行元素減去該行的最小元素；

②再從系數(shù)矩陣的每列元素中減去該列的最小元素.

若某行（列）已有0元素，那就不必再減了，在例1中，

第二步：最優(yōu)性檢驗

進行試指派，尋求最優(yōu)解.為此，按以下步驟進行.

經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；但需找出n個獨立的0元素，若能找出，解矩陣（xij）中，與這些獨立0元素對應的元素xij為1，其他為0，這就得到最優(yōu)解.當n較小時，可用觀察法、試探法去找出n個獨立0元素，若n較大時，就必須按一定的步驟去找，常用的步驟為：

①從只有一個0元素的行（列）開始，給這個0元素加圈，記作薜.這表示對這行所代表的人，只有一項任務可指派，然后劃去薜所在的列（行）的其他0元素，記作準.這表示這列所代表的任務已派完，不必再考慮別人了.

②給出只有一個0元素列（行）的0元素加圈，記作薜，然后劃去薜所在的行的0元素，記作準.

③反復進行①、②兩步，直到所有0元素都被圈出或劃掉為止.

④若仍有沒有劃去的0元素，且同行（列）的0元素至少有兩個（表示對這兩項任務中指派其一，可用不同的方案去試探），從剩余的0元素最少的行（列）開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈（表示選擇性多的要讓選擇性少的），然后劃掉同行同列的其他0元素，可反復進行，直到所有的0元素都已圈出和劃掉為止.

對B進行①~④操作后得

⑤若薜元素的數(shù)目m等于矩陣的階數(shù)n，那么指派問題的最優(yōu)解已得到.若m

由于上面的矩陣中0元素的數(shù)目m=3

第三步：找出能覆蓋非最優(yōu)的變換陣中所有0元素的最少直線集合

即作最少的直線，覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到的最多的獨立0元素數(shù).按以下步驟進行：

①對無準的行打“√”號；

②對已打“√”號的行中所有含0元素的列打“√”；

③再對打“√”號的列中含有0元素的行打“√”；

④重復②、③直到得不到新的打“√”號的行、列為止；

⑤對未打“√”號的行畫一橫線，打“√”的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù).令這些直線數(shù)為l.

若l＜n，說明必須再變換當前的系數(shù)矩陣，才能找到獨立的0元素，為此轉入第四步；若l=n，而m＜n，應回到第二步中的④，另行試探.

本例中，對矩陣（3）按以下序次進行操作：

由于l=3

第四步：非最優(yōu)陣的變換——0元素的移動

在未被直線覆蓋的所有元素中，找出最小元素；

所有未被直線覆蓋的元素都減去這個最小元素；

覆蓋線十字交叉處元素都加上這個最小元素，其余元素不變.

即在沒有被覆蓋的元素中找出最小者，然后在打√列的各元素都加上這最小元素，以保證原來獨立0元素不變，這樣得到新系數(shù)矩陣（與原問題最優(yōu)解相同）.若得到n個獨立0元素，則已得到最優(yōu)解，否則重復第三步.

例1中，在（4）中找出（第一、第二行，第一列）未畫線部分的最小元素為1，第一、二行各元素分別減去“1”，第一列各元素加“1”得矩陣（5）

由于出現(xiàn)未被劃去的0元素，且所在行、列有多于一個0元素的，按第二步中的④的操作得

此時，矩陣（7）中，薜元素數(shù)目與直線數(shù)目相等，將（7）式中的薜元素換為“1”，其余元素換為“0”，則得到指派問題最優(yōu)解

即x13=1，x21=1，x32=1，x44=1，其余xij＝0，目標函數(shù)最優(yōu)值：

f*=39+31+41+39=150（小時）

2 指派問題的等價問題類型及其解法

匈牙利法只適用于指派問題的標準型，而實際的指派問題不一定是標準的，必須加以處理.針對目標函數(shù)是最大或最小、人數(shù)與任務數(shù)不等、定人定任務，提出了虛擬任務或人的方法，將問題轉化為能夠用匈牙利算法求解的等價指派問題.由于指派問題屬于線性規(guī)劃中的運輸問題的特例，可以等價于線性規(guī)劃和運輸問題.此外，指派問題從對偶問題、對立問題的角度出發(fā)，也有等價問題，這些等價問題有的可轉為標準型，有的不轉標準型的方法也比較簡單、易于計算，有很高的應用價值.

2.1 最大問題與最小問題的等價

當目標是極大化的指派問題時，即

則令：cij=M-aij，M充分大，以至于所有cij叟0（如取aij中的最大者為M），f=-Z，則上述問題可轉化為極小指派問題：

且Zmax=nM-fmin

2.2 人數(shù)與任務數(shù)不等時虛增人或任務使得人數(shù)與任務數(shù)一致的等價

舉例說明這種情況的處理.

例2某作戰(zhàn)單位有三種火器擬分配給A、B、C、D四名射手，各射手使用不同的火器的命中概率如表2所示，問如何安排，使得總射擊效果最好？

表2

解：設

令

該問題求最大值，先將極大化問題轉化為極小化.取M=0.9，修正原效益矩陣

火器數(shù)比射手少1，增加一件虛擬火器M4，得效益矩陣

這樣便得到一個標準指派問題模型，用匈牙利法求解，可得最優(yōu)分配方案：第一種火器分配給B，第二種火器分配給A，第三種火器分配給D.

2.3 指定任務時的等價

n人n項工作，要求每人只能做一項工作，但指定某項工作必須由某人完成，問如何指派使完成任務的總時間最短?

例3分配甲、乙、丙、丁、戊去完成四項任務，每人完成各項任務的時間如表3.由于人多，規(guī)定其中有一任務可由兩人共同完成，其中，丁不完成任務4，甲必須完成四項任務中的一項，試確定總花費時間最少的分派方案.

表3

虛增任務5，根據(jù)條件丁不完成任務3，甲必須完成四項任務中的一項，確定甲完成任務5的時間為很大值M，丁完成任務4的時間為M，在此基礎上進行指派.

表4

這個問題和原問題等價.當然，虛增任務5，時間如下：

表5

在此基礎上進行指派，根據(jù)定理1，這個問題也與原問題等價.

2.4 等價的對偶問題

在標準型指派問題匈牙利解法中，尋找獨立0元素的個數(shù)最大值等價于尋找覆蓋所有0元素的最少直線數(shù)，這就是對偶問題.對偶性體現(xiàn)在以下五個方面：

（1）一個問題求最大值，另一個問題求最小值.

（2）求最大值問題，約束條件為“=”，求最小問題，約束條件為“=”.

（3）原問題中有n個變量，對偶問題就有n個約束條件，原問題有n個約束條件，對偶問題中就有n個變量（稱為對偶變量）.

（4）原問題的目標函數(shù)中變量的系數(shù)就是對偶問題約束條件的常數(shù)項.原問題中約束條件的常數(shù)項就是對偶問題目標函數(shù)中變量的系數(shù).

（5）兩個互為對偶問題約束條件的系數(shù)矩陣互為轉置矩陣.

當找到了覆蓋所有0元素的最少直線數(shù)等于獨立0元素的個數(shù)（等于任務數(shù)和人數(shù)）時，即在直線上找到的不同行不同列的0元素，就是最優(yōu)分配方案.

2.5 等價的對立問題

由于查找非標準型指派問題的最優(yōu)分配方案，首先要進行標準型的轉換，然后再利用匈牙利解法，多次循環(huán)，步驟較為繁瑣.為了便于操作，我們可以考慮原指派問題的對立問題.對立問題就是通過梳理原問題（最小值）每行每列的（n-3）個對立（最大）值，在此基礎上逐步找出最優(yōu)分配方案.具體步驟如下：

第一步，若任務數(shù)和人數(shù)不一致，采用虛增任務或人轉變?yōu)槿蝿諗?shù)和人數(shù)一致；

第二步，判斷指派問題為最小問題還是最大問題，若為最小問題，則在費用矩陣中找最大值；若為最大問題，則在效益矩陣中找最小值；

第三步，判斷矩陣的維度（設行列數(shù)為n，n>3），則需要找出對立深度為（n-3）的最值.當同一行或同一列除某元素外，皆為不同深度的最值，則該元素即為指派問題中一項最優(yōu)解.重復以上過程，直至找出所有最優(yōu)解.以例1為例.

對立深度4-3=1

Min問題等價于max問題，1c代表列最值，1r代表行最值，

在上面4×4的矩陣中，第二列除了40，第四列除了39外，這兩列其余皆為不同深度的最值，根據(jù)對立等價性，第二列40與第四列39這兩元素可能為最優(yōu)解.通過比較這兩個非深度最值，39較40更小，因此39為指派問題第四項任務的最優(yōu)分配，劃去39所在的行或列，在此基礎上再用匈牙利法找出其它的最優(yōu)解.

2.6 等價于運輸問題

指派問題是一類特殊的運輸問題，求解這類問題可等價于運輸問題.即類似交通等情況，制定合理運輸方案，使總的運輸代價（運費或噸千米數(shù)）最小.運輸問題可以用比單純形法更有效的方法——表上作業(yè)法求解.建立運輸圖表；最小元素法尋求初始運輸方案；用位勢法判別初始運輸方案是否最優(yōu)；閉回路法尋求改進方案，回到第二步，計算改進方案檢驗數(shù)σ′ij.在求解運輸問題過程中，有時會碰到非零數(shù)字格的個數(shù)小于m+n-1的情況，這時，在數(shù)字格中任選幾個作為數(shù)字格，而使得數(shù)字格個數(shù)恰為m+n-1個，從而保證基變量個數(shù)為m+ n-1個，從而確定出最優(yōu)分配方案.

2.7 等價于線性規(guī)劃問題

指派問題是一類特殊的線性規(guī)劃問題，求解這類問題可等價于線性規(guī)劃問題，采用圖解法，QSB軟件法，單純形法等方法尋找最優(yōu)分配方案.在用圖解法求解線性規(guī)劃問題時可知，如果線性規(guī)劃有最優(yōu)解存在的話，則一定可以在可行域（凸多邊形）的頂點上找到.這個方法可以推廣到多個變量的線性規(guī)劃問題.我們知道由多個變量所組成的不等式組成的可行域在n維空間內(nèi)是一個凸多面體，與多邊形一樣，凸多面體的每一個頂點均是一個基本可行解.我們只需要從可行域（凸多面體）的頂點中去找，按照問題的標準形式，從可行域中一個基本可行解（一個頂點）開始，轉換到另一個基本可行解（頂點），并且使目標函數(shù)的值逐步減少；當目標函數(shù)達到最小值時，問題就得到了最優(yōu)解.當圖解法使用困難時，可采用QSB軟件法，單純形法，matlab，lindo等方法.

3 巧用等價問題求解時應把握的問題

以上給出了指派問題的七類等價問題，它們是從不同視角分析的等價問題，拓展了指派問題的尋優(yōu)思路.七類等價問題雖然分類不同，但是它們之間有密切的關系，我們要根據(jù)每類問題的特點選擇使用.

3.1 理順各等價問題間的關系

指派問題問題按照是否標準分為標準型和非標準型兩類，非標準型與標準型的轉化就是一種大范圍的等價，其中，最大最小問題的等價、任務數(shù)與人數(shù)不等、特定人員的指派問題都屬于非標準型與標準型的等價問題，就是通過化非標準型為標準型，利用匈牙利法找出最優(yōu)解.等價對偶問題是換一種思維方式尋找指派問題的分配方案，思維轉換后再進行指派問題的分配.等價對立問題是從對立面思考，排除掉對立問題的方案，找出最優(yōu)方案，這類問題在轉型到任務數(shù)與人數(shù)一致的基礎上，對任何指派問題可以直接尋找最優(yōu)解，省去了很多中間步驟.指派問題是特殊的線性規(guī)劃和運輸問題，將指派問題等價于這兩類問題也是自然.等價運輸問題和等價線性規(guī)劃問題，是從已有的運輸問題和線性規(guī)劃方法出發(fā)，尋找最優(yōu)方案.

3.2 根據(jù)問題特點選擇等價類型

指派問題的匈牙利法和等價于線性規(guī)劃中的運輸問題的方法適用于任務數(shù)和人數(shù)較?。ㄐ∮诘扔?），當任務數(shù)和人數(shù)較多（大于4）時，可通過前三種等價問題，將非標準型指派問題轉化為標準型來尋找最優(yōu)分配方案.當對匈牙利法的兩個定理很熟悉時，可以通過等價對偶問題，尋找覆蓋所有0元素的最少直線數(shù)來判斷最優(yōu)分配方案.當指派問題基礎知識掌握較好時，可以通過等價對立問題來進行最優(yōu)分配.

3.3 利用不同類等價問題進行檢驗

以上七類等價問題都是原問題的等價問題，因此，它們之間可以進行相互檢驗.當手邊有QSB軟件包時，用指派問題等價于線性規(guī)劃、運輸問題、標準指派問題，查找最優(yōu)方案，此時檢驗速度較快.當利用匈牙利法查找最優(yōu)方案時，目測覆蓋所有0的最少直線數(shù)等于任務數(shù)和人數(shù)，則將指派問題等價于對偶問題，選擇對偶問題來進行尋找最優(yōu)解的檢驗.當熟練掌握了指派問題及其解法，在采用等價于最大最小問題、人數(shù)任務數(shù)不同問題、獨立0元素和覆蓋0的直線數(shù)的對偶問題，找出最優(yōu)解后，可以直接利用對立問題進行查找最優(yōu)解檢驗.

[1]張最良，李長生，張文志，等.軍事運籌學[M].北京：軍事科學出版社，2000.

[2]董樹軍，張慶捷.軍事運籌學教程[M].北京：藍天出版社，

2006.

The Research on Equivalence Problem of Assignment Problem

BAO Pei-wen
（The Teaching and Research Department，Special Police College,Beijing,102211）

Assignment problems usually involve more than one solution.And the solutions concerned also involve smaller assignment problems,the amount of which is equivalent to the original problem.In other words,an original assignment has many equivalent problems.In this paper,in order to discuss the optimization of the assignment,the solutions of an assignment problem as well as its equivalent problems are analyzed.With the relations between solutions figured out, it would be more efficient for decision makers to pass down the assignment.

assignment problem；equivalence problem；research

O22

A

1671－9743（2017）05－0023－05

2016－12－28

鮑培文，1968年生，女，江西南昌人，教授，研究方向：軍事運籌學、高等數(shù)學等.