李承耕 劉波

【摘要】針對(duì)指派問(wèn)題中最小化問(wèn)題的匈牙利解法，通過(guò)最大元素法來(lái)處理最大化指派問(wèn)題.

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

【中圖分類號(hào)】0223

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

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

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

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

玀inz=А苙[]i=1ИА苙[]j=1c﹊j獂﹊j.其中x﹊j=0 i資源不給 j活動(dòng)，

1 i資源分給 j活動(dòng)，お﹊=1,2,…,n,j=1,2,…，n.

А苙[]i=1x﹊j=1(j=1,2,…，n) А苙[]j=1x﹊j=1(i=1,2,…，n)

2.匈牙利法處理指派問(wèn)題的基本步驟

（1)使指派問(wèn)題的系數(shù)矩陣在各行各列都出現(xiàn)0元素.①?gòu)南禂?shù)矩陣的每行都減去該行的最小元素.②再?gòu)南禂?shù)矩陣的每列減去該列的最小元素.

(2）若效率矩陣的行列數(shù)為n,想辦法找到n個(gè)不同行，不同列的0元素，即n個(gè)獨(dú)立的0元素，用最少的直線將所有的0元素劃去，若直線數(shù)量剛好等于n個(gè)，則n個(gè)獨(dú)立的0元素就找到，否則就轉(zhuǎn)入下一步.

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

3.最大化問(wèn)題的兩種處理方法

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

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

4.基本案例分析

假定有四項(xiàng)工作A1,A2,A3,A4要分配到四部機(jī)器B1,B2,B3,B4上，其產(chǎn)生的效益如下表所示.問(wè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） 方法一

對(duì)于效益矩陣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的最大化解.通過(guò)尋求C′的最小解得到C的最大解.

最優(yōu)決策方案為：X11=X23=X32=X44=1，最大收益為：玬ax玈=А4[]i=1ИА4[]j=1c﹊j獂﹊j=11+2+7+7=27.

（2） 方法二

直接利用最大元素來(lái)處理，對(duì)于效益矩陣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é)束語(yǔ)

從以上兩種方法的比較我們可以看出，用最大元素來(lái)處理這類問(wèn)題，就不必建立新的系數(shù)矩陣，所以在編寫(xiě)程序時(shí)，可以用實(shí)參代替形象的方法，用同一段代參數(shù)的程序去解決最大化、最小化兩個(gè)不同的問(wèn)題.

ァ靜慰嘉南住開(kāi)オ

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

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

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