利用最大元素求解最大化指派問題
2012-04-29 02:51:02李承耕劉波
數(shù)學學習與研究 2012年9期
李承耕 劉波
【摘要】針對指派問題中最小化問題的匈牙利解法，通過最大元素法來處理最大化指派問題.
【關(guān)鍵詞】指派問題；匈牙利法；最小元素；最大元素
【中圖分類號】0223
【文獻標識碼】獳オ
1.指派問題的數(shù)學模型
求解n個資源分配到n個任務的活動中，為使得總成本最小，如何完成對資源的分配.
設C﹊j為分配資源i到j任務所消耗的成本，則：
玀inz=А苙[]i=1ИА苙[]j=1c﹊j獂﹊j.其中x﹊j=0 i資源不給 j活動，
1 i資源分給 j活動，お﹊=1,2,…,n,j=1,2,…，n.
А苙[]i=1x﹊j=1(j=1,2,…，n) А苙[]j=1x﹊j=1(i=1,2,…，n)
2.匈牙利法處理指派問題的基本步驟
（1)使指派問題的系數(shù)矩陣在各行各列都出現(xiàn)0元素.①從系數(shù)矩陣的每行都減去該行的最小元素.②再從系數(shù)矩陣的每列減去該列的最小元素.
(2）若效率矩陣的行列數(shù)為n,想辦法找到n個不同行，不同列的0元素，即n個獨立的0元素，用最少的直線將所有的0元素劃去，若直線數(shù)量剛好等于n個，則n個獨立的0元素就找到，否則就轉(zhuǎn)入下一步.
(3）在直線沒有劃去的元素中，選一個最小的，在沒有劃去的元素的各行中均減去這個最小元素，為保持原來的0元素不變，在0元素對應的列中加上該元素.
3.最大化問題的兩種處理方法
（1）將最大化問題轉(zhuǎn)化為最小化問題，設原來的效益矩陣為C=(C﹊j)，我們可以作一個新的效益矩陣C′=M-C﹊j，這里M比C中的最大元素要大，則C′的最小指派即為C的最大指派.
（2）直接在每行或每列中減去該行列的最大元素，然后在效益矩陣中找到n個獨立的0元素，這里的0元素即是最大元素，注意n個獨立的0元素所在位置是處在不同行、不同列的位置，一旦找到n個獨立的0元素，也就找到對應的最大指派.
4.基本案例分析
假定有四項工作A1,A2,A3,A4要分配到四部機器B1,B2,B3,B4上，其產(chǎn)生的效益如下表所示.問如何分配工作效益最好.
[]B1[]B2[]B3[]B4
A1[]11[]8[]6[]9
A2[]3[]5[]2[]3
A3[]8[]7[]1[]5
A4[]4[]5[]4[]7
（1） 方法一
對于效益矩陣C=11[]8[]6[]9
3[]5[]2[]3
8[]7[]1[]5
4[]5[]4[]7
，C′=12-C=1[]4[]6[]3
9[]7[]10[]9
4[]5[]11[]7
8[]7[]8[]5
，
則C′的最小化解即為C的最大化解.通過尋求C′的最小解得到C的最大解.
最優(yōu)決策方案為：X11=X23=X32=X44=1，最大收益為：玬ax玈=А4[]i=1ИА4[]j=1c﹊j獂﹊j=11+2+7+7=27.
（2） 方法二
直接利用最大元素來處理，對于效益矩陣C=11[]8[]6[]9
3[]5[]2[]3
8[]7[]1[]5
4[]5[]4[]7
，我們作如下變換：
11[]8[]6[]9
3[]5[]2[]38[]7[]1[]54[]5[]4[]7
-11-5-8-7
→0[]-3[]-5[]-2
-2[]0[]-3[]-2
0[]-1[]-7[]-3
-3[]-2[]-3[]0
オ
+30[]-3[]-2[]-2
-2[]0[]0[]-2
0[]-1[]-4[]-3
-3[]-2[]0[]0
+1おおおお+1お
→(0)[]-2[]-1[]-1
-3[]0[](0)[]-2
0[](0)[]-3[]-2
-4[]-2[]0[](0)
おお
-1
プ鈑啪霾呔卣笪：1[]0[]0[]0
0[]0[]1[]00[]1[]0[]00[]0[]0[]1
.
最優(yōu)決策方案為：X11=X23=X32=X44=1，最大收益為：玬ax玈=А4[]i=1ИА4[]j=1c﹊j獂﹊j=11+2+7+7=27.
5.結(jié)束語
從以上兩種方法的比較我們可以看出，用最大元素來處理這類問題，就不必建立新的系數(shù)矩陣，所以在編寫程序時，可以用實參代替形象的方法，用同一段代參數(shù)的程序去解決最大化、最小化兩個不同的問題.
ァ靜慰嘉南住開オ
［1］羅榮桂.新編運籌學題解［M］.武漢：華中科技大學出版社，2002.
［2］胡運權(quán).運籌學基礎與應用［M］.北京：高等教育出版社，2004.
［3］程叢電，唐恒永.一類資源分配與排序問題［J］.數(shù)學實踐與認識，2006（1）.
