任務四　指派問題及其求解方法

指派問題又稱分配問題，是一類特殊的0—1規劃，也是一類特殊的整數規劃。指派問題研究如何進行最優安排，使花費的時間、資源最少，或取得的收益最高。

4.1　指派問題的數學模型

n個人被分配去做n件工作，已知第i個人去做第j件工作的效率為cij（i＝1，2，…，n；j＝1，2，…，n）并假設cij≥0。問應如何分配才能使總效率（時間或費用）最高？

設決策變量

那么

例3-4-1　有一份中文說明書，需翻譯成英、日、德、俄四種文字，分別記作E、J、G、R，現有甲、乙、丙、丁四人，他們將中文說明書翻譯成英、日、德、俄四種文字所需時間如表3-4-1所示，問應該如何分配工作，使所需總時間最少？

解：建立模型：引入0—1變量，xij＝1表示分配第i人去完成第j項任務，xij＝0表示不分配第i人去完成第j項任務。

4.2　匈牙利法

1955年，庫恩提出了指派問題的解法，他引用了匈牙利數學家康尼格一個關于矩陣中0元素的定理：系數矩陣中獨立0元素的最多個數等于能覆蓋所有0元素的最少直線數，這個解法也就成了匈牙利法。

匈牙利法的解題步驟如下。

第一步：使分配問題的系數矩陣經變換，在各行各列中都出現0元素。

（1）從系數矩陣的每行元素減去該行的最小元素。

（2）再從所得系數矩陣的每列元素減去該列的最小元素。若某行或某列已經有0元素，就不必再減了。

第二步：進行試分配，以尋找最優解。

（1）從只有一個0元素的行（或列）開始，給這個0元素加括號，然后劃去它所在的列（或行）的其他0元素。

（2）給只有一個0元素的列（或行）的0元素加括號，然后劃去它所在的行（或列）的其他0元素。

反復進行上述兩步，直到所有的0元素都被加了括號或者被劃掉為止。

（3）若還有沒有加括號的0元素，且同行（或列）的0元素至少有兩個，從剩有0元素最少的行（或列）開始，比較這行各0元素所在列中0元素的數目，選擇0元素少的那列的0元素加括號，然后劃掉同行同列的其他0元素，可反復進行，直到所有的0元素都加了括號或者劃掉為止。

（4）若加括號的0元素的數目m等于矩陣階數n，那么這分配問題的最優解已得到。若m＜n，則轉下一步。

第三步：作最少的直線覆蓋所有的0元素，以確定該系數矩陣中能找到最多的獨立元素數。

（1）對沒有加括號0元素的行，打。

（2）對已打行中所有含0元素的列打。

（3）再對打列中含加括號的0元素的行打。

（4）重復上述兩步，直到得不出新的打行列為止。

（5）對沒有打行畫橫線，有打列畫縱線，就得到覆蓋所有0元素的最少直線數。

第四步：在沒有被直線覆蓋的部分中找出最小元素，所有未被直線覆蓋的元素都減去該最小元素，位于水平直線與鉛直直線交叉處的元素都加上這個最小元素，其余元素保持不變，這樣就可以得到新的系數矩陣（它的最優解和原問題相同）。返回第二步，繼續尋找最優解，若得到n個加括號的0元素，則已經得到最優解。否則回到第三步重復進行。

下面通過例子來具體說明匈牙利法的解題步驟。

用匈牙利法求解例3-4-1。

從只有一個0元素的行（或列）開始，給這個0元素加括號，先給b22加括號，然后給b31加括號，劃掉b11和b41，給b14加括號，劃掉b44，給b43加括號。

可見m＝n＝4，得到最優解，最優解為

因此，最后的任務分配為甲譯俄文、乙譯日文、丙譯英文、丁譯德文，用以上方案進行任務的分配所需時間最少，最少時間z＝28小時。

例3-4-2　表3-4-2中數據表示不同的人承擔不同的任務所需要的時間，求該指派問題總時間最少的方案。

解：按照匈牙利法的第一步，對系數矩陣進行變換。

經一次運算即得每行每列都有0元素的系數矩陣，再按第二步進行試分配，先給b12加括號，劃掉b14，然后給b25加括號，劃掉b23和b24，給b31加括號，劃掉b51，給b44加括號，劃掉b43得到以下矩陣

加括號的0元素的個數m＝4，而n＝5，m＜n，轉第四步。

在沒有被直線覆蓋的部分中找出最小元素2，所有未被直線覆蓋的元素都減去該最小元素，位于水平直線與鉛直直線交叉處的元素都加上這個最小元素，其余元素保持不變，這樣就可以得到新的系數矩陣（它的最優解和原問題相同）。

再根據第二步對上述系數矩陣進行試分配，先給b12加括號，劃掉b14，然后給b51加括號，劃掉b31，給b35加括號，劃掉b25，給b23加括號，劃掉b43，給b44加括號，劃掉b24，得到以下矩陣

可見m＝n＝5，得到最優解，最優解為

因此，最后的任務分配為甲完成任務B，乙完成任務C，丙完成任務E，丁完成任務D，戊完成任務A，用以上方案進行任務的分配所需時間最少，最少時間z＝32。

除此之外，有的時候要面對的指派問題是要求最大的利潤等最大化問題，但匈牙利法只能求解最小化問題。這時，可以在系數矩陣中找到一個最大的數M，用M減去原矩陣里的每一個元素，得到一個新矩陣，這個矩陣的最小化分配就相當于原矩陣的最大化分配，我們可以在新矩陣中直接使用匈牙利法，這里就不再一一舉例了。