利用最大元素求解最大化指派問題

李承耕 劉波

【摘要】針對指派問題中最小化問題的匈牙利解法，通過最大元素法來處理最大化指派問題.

【關(guān)鍵詞】指派問題；匈牙利法；最小元素；最大元素

【中圖分類號】0223

【文獻(xiàn)標(biāo)識碼】獳オ

1.指派問題的數(shù)學(xué)模型

求解n個資源分配到n個任務(wù)的活動中，為使得總成本最小，如何完成對資源的分配.

設(shè)C﹊j為分配資源i到j(luò)任務(wù)所消耗的成本，則：

玀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個獨(dú)立的0元素，用最少的直線將所有的0元素劃去，若直線數(shù)量剛好等于n個，則n個獨(dú)立的0元素就找到，否則就轉(zhuǎn)入下一步.

(3）在直線沒有劃去的元素中，選一個最小的，在沒有劃去的元素的各行中均減去這個最小元素，為保持原來的0元素不變，在0元素對應(yīng)的列中加上該元素.

3.最大化問題的兩種處理方法

（1）將最大化問題轉(zhuǎn)化為最小化問題，設(shè)原來的效益矩陣為C=(C﹊j)，我們可以作一個新的效益矩陣C′=M-C﹊j，這里M比C中的最大元素要大，則C′的最小指派即為C的最大指派.

（2）直接在每行或每列中減去該行列的最大元素，然后在效益矩陣中找到n個獨(dú)立的0元素，這里的0元素即是最大元素，注意n個獨(dú)立的0元素所在位置是處在不同行、不同列的位置，一旦找到n個獨(dú)立的0元素，也就找到對應(yīng)的最大指派.

4.基本案例分析

假定有四項(xiàng)工作A1,A2,A3,A4要分配到四部機(jī)器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í)參代替形象的方法，用同一段代參數(shù)的程序去解決最大化、最小化兩個不同的問題.

ァ靜慰嘉南住開オ

［1］羅榮桂.新編運(yùn)籌學(xué)題解［M］.武漢：華中科技大學(xué)出版社，2002.

［2］胡運(yùn)權(quán).運(yùn)籌學(xué)基礎(chǔ)與應(yīng)用［M］.北京：高等教育出版社，2004.

［3］程叢電，唐恒永.一類資源分配與排序問題［J］.數(shù)學(xué)實(shí)踐與認(rèn)識，2006（1）.