○張勝喜劉艷

（1、湖北輕工職業(yè)技術(shù)學(xué)院湖北武漢430070 2、武漢理工大學(xué)湖北武漢430070）

基于匈牙利資源分配法保障農(nóng)村資金限額的最優(yōu)決策

○張勝喜1劉艷2

（1、湖北輕工職業(yè)技術(shù)學(xué)院湖北武漢430070 2、武漢理工大學(xué)湖北武漢430070）

匈牙利法是一種指派問(wèn)題的解法，將最小元素法引入匈牙利法中，減少了繁鎖的計(jì)算過(guò)程，它是一種重要的資源分配手段。本文的應(yīng)用表明這種方法具有較強(qiáng)的穩(wěn)定性、可行性和有效性，對(duì)農(nóng)村資金分配工作更有針對(duì)性。

匈牙利法0元素法指派問(wèn)題農(nóng)村資金限額最優(yōu)分配決策

在探求工程投資、城鄉(xiāng)建設(shè)投資、銀行對(duì)企業(yè)貸款限額、投標(biāo)公司申報(bào)承擔(dān)工程項(xiàng)目費(fèi)用限額、任務(wù)或工程的耗料、耗成本、耗能、耗工期量及人力資源消耗的最小化預(yù)想目標(biāo)的競(jìng)爭(zhēng)中，運(yùn)籌科學(xué)地分配資源問(wèn)題，又稱為指派問(wèn)題（Assignment Problem），是一種特殊的整數(shù)規(guī)劃問(wèn)題。這種問(wèn)題在社會(huì)應(yīng)用領(lǐng)域，尤其在經(jīng)濟(jì)領(lǐng)域會(huì)經(jīng)常遇到。運(yùn)籌分配資源的主流解法是由匈牙利數(shù)學(xué)家康尼格Kuhn. H.W提出的，稱為匈牙利法，基于最小元素的匈牙利法是袁遷、劉舒燕在匈牙利法基礎(chǔ)上提出的改進(jìn)解法。本文針對(duì)分配給農(nóng)村各類資金的建議資金限額方案甲、乙、丙、丁對(duì)各種類型農(nóng)村資金A、B、C、D的提供進(jìn)行最優(yōu)決策，采用了這種最小元素匈牙利法。

一、分配給農(nóng)村資金的用途

參照2011年國(guó)務(wù)院舉行的中央經(jīng)濟(jì)工作會(huì)議中六大任務(wù)涉及農(nóng)業(yè)和農(nóng)村內(nèi)容和文獻(xiàn)武漢城市圈城鄉(xiāng)一體化水平綜合評(píng)價(jià)研究，特提出以下分配給農(nóng)村資金的用途內(nèi)容，也符合建設(shè)兩型社會(huì)的需求。

1、城鄉(xiāng)聯(lián)接交通建設(shè)資金的用途

中央經(jīng)濟(jì)工作會(huì)議強(qiáng)調(diào)要千方百計(jì)確保主要農(nóng)產(chǎn)品供給安全及其供應(yīng)農(nóng)產(chǎn)品的交通網(wǎng)建設(shè)，包括農(nóng)村與城市聯(lián)通的高速公路和一般公路交通圈建設(shè)、農(nóng)村內(nèi)部公路馬路建設(shè)、交通基礎(chǔ)設(shè)施建設(shè)、農(nóng)村破損路改建工程、照明網(wǎng)設(shè)施改造項(xiàng)目、節(jié)能燈網(wǎng)改造項(xiàng)目以及排水管網(wǎng)和排污管網(wǎng)建設(shè)工程等。

2、農(nóng)村基本建設(shè)資金的用途

中央經(jīng)濟(jì)工作會(huì)議中六大任務(wù)強(qiáng)調(diào)要加快構(gòu)建覆蓋城鄉(xiāng)的公共文化服務(wù)保障。農(nóng)村基建資金用于相關(guān)服務(wù)項(xiàng)目：金融服務(wù)、醫(yī)療服務(wù)、信息通訊服務(wù)、郵電服務(wù)、教育服務(wù)、水利服務(wù)、防災(zāi)抗旱服務(wù)、文化服務(wù)、提高農(nóng)村綠化覆蓋率、進(jìn)行產(chǎn)業(yè)結(jié)構(gòu)的固定資產(chǎn)投資、進(jìn)行農(nóng)村鎮(zhèn)政府及社區(qū)管理機(jī)構(gòu)建設(shè)等。

3、農(nóng)業(yè)糧食蔬菜生產(chǎn)基金的用途

中央經(jīng)濟(jì)工作強(qiáng)調(diào)，要千方百計(jì)確保穩(wěn)定糧食播種面積，增加農(nóng)業(yè)生產(chǎn)補(bǔ)貼，加大糧食生產(chǎn)與投入和利益補(bǔ)貼

式中，Pij為一個(gè)方案i規(guī)定給j種資金的限額值，如7000萬(wàn)元。力度，加強(qiáng)農(nóng)產(chǎn)品質(zhì)量的安全管理機(jī)制的構(gòu)建。要推進(jìn)發(fā)展現(xiàn)代化農(nóng)業(yè)技術(shù)，確保農(nóng)產(chǎn)品有效供給，擴(kuò)大農(nóng)業(yè)耕地面積，發(fā)展蔬菜耕作基地，提高農(nóng)業(yè)產(chǎn)值包括一產(chǎn)產(chǎn)值、二產(chǎn)產(chǎn)值和三產(chǎn)產(chǎn)值的農(nóng)業(yè)增加值，同時(shí)發(fā)展農(nóng)村的手工業(yè)和工業(yè)產(chǎn)業(yè)結(jié)構(gòu)。

4、改善農(nóng)村生活、文化水平資助金的用途

我國(guó)建設(shè)兩型社會(huì)要促進(jìn)城鄉(xiāng)一體化水平，改善農(nóng)村人口、農(nóng)民的生活水平，提高農(nóng)村對(duì)金融機(jī)構(gòu)的貸款額度，提高農(nóng)村金融服務(wù)水平，改善農(nóng)村生態(tài)環(huán)境，提高農(nóng)村生活垃圾無(wú)害化處理率和工業(yè)手工業(yè)廢物利用處理達(dá)標(biāo)率。

二、匈牙利法的數(shù)學(xué)模型

匈牙利庫(kù)恩提出了資源分配問(wèn)題的解法，引用了匈牙利數(shù)學(xué)家康尼格Kuhn.H.W的一個(gè)關(guān)于0元素定理。0元素定理要求在資源分配的效能矩陣中獨(dú)立0元素的最多個(gè)數(shù)要等于能覆蓋所有0元素的最少直線數(shù)目（參見(jiàn)案例闡明），這種方法稱為匈牙利法。最小元素法是將效能矩陣中，每行元素值或每列元素值減去此行或此列的最小元素值，就獲得有0元素的效能矩陣，當(dāng)符號(hào)⊙的數(shù)目（只有一個(gè)0的行，列的0可變?yōu)椤眩┑扔谛芫仃嚨碾A數(shù)（行數(shù)），就不進(jìn)行對(duì)0元素的劃直線工作，采用0元素劃線的目的是解除同時(shí)出現(xiàn)2個(gè)最小元素值的沖突；當(dāng)符號(hào)⊙的數(shù)目小于矩陣行數(shù)，就要進(jìn)行劃線處理（參見(jiàn)案例闡明），再按伏格爾原理來(lái)獲得決策結(jié)論。

匈牙利數(shù)學(xué)模型要點(diǎn)是求解i個(gè)方案（或資源i）規(guī)定對(duì)J個(gè)資助基金（或J個(gè)工程項(xiàng)目，企業(yè)）的分配資金限額，要使總的效能或效益（Z），即總提供的資金達(dá)到最小化，即最高的效能。

0，1為效能矩陣最后處理后的矩陣元素值，i=1，2，…n個(gè)方案，公司J為=1，2，…m資金類型（A，B，C，D）或工程項(xiàng)目或企業(yè)。

表1 方案規(guī)定提供的資金現(xiàn)金限額（單位：千萬(wàn)元)

表1列出方案甲、乙、丙、丁規(guī)定提供農(nóng)村A、B、C、D類型資金的限額。

三、將限額分配資金組成效能矩陣（BennfitMatrix）

（列）∑C=4，C∶1111（行）r∶r（MIN）

（列）C（MIN）6676（行）∑r=5

C為每列最小值的個(gè)數(shù)，寫(xiě)在矩陣外的上邊，其和∑C=C（SUM）是矩陣每列最小個(gè)數(shù)之和。R為每行最小值的個(gè)數(shù)，寫(xiě)在矩陣外的右邊，其和∑r=r（SUM）是矩陣生行最小個(gè)數(shù)之和。甲、乙、丙、丁為各種資助方案，寫(xiě)在矩陣外的左邊，A、B、C、D為農(nóng)村資金類型，寫(xiě)在矩陣的上邊。r（MIN）每行的最小值，寫(xiě)在矩陣外r的右邊，C（MIN）每列的最小值，寫(xiě)在矩陣外的下邊。

四、引入最小元素法的減法準(zhǔn)則，化簡(jiǎn)效能矩陣

減法準(zhǔn)則是比較∑r和∑C孰小，就先從矩陣的行或列減去該行或該列的最小元素值，來(lái)化簡(jiǎn)矩陣。本案例∑C=4＜∑r=5，故要先從“列”減去MIN值求得以下左邊矩陣，再?gòu)淖筮吘仃囌页鲂械腗IN值，再按行減去MIN值，獲得以下右邊矩陣，再由行轉(zhuǎn)入列處理，此矩陣此時(shí)每列MIN值全為0，故此矩陣無(wú)法再轉(zhuǎn)換化簡(jiǎn)了，則作以下處理。

五、矩陣每行、列0變?yōu)椤训奶幚?/h2>

a.先從上轉(zhuǎn)為列無(wú)法處理開(kāi)始，先從列找只有一個(gè)0元素開(kāi)始，第2列將0變?yōu)椤?，?duì)應(yīng)的行中0變?yōu)棣眨購(gòu)牡?列只有一個(gè)0變?yōu)椤?，剩下?列有2個(gè)元素，故轉(zhuǎn)入行的處理。

b.再按行中只有一個(gè)0元素轉(zhuǎn)為⊙，對(duì)應(yīng)列0元素變?yōu)棣铡?/p>

六、當(dāng)⊙數(shù)目小于矩陣階數(shù)，⊙變1，其它變0的轉(zhuǎn)換準(zhǔn)則

本案例矩陣中⊙數(shù)目=3＜矩陣行數(shù)（階數(shù)）=4，要按以下轉(zhuǎn)換準(zhǔn)則處理：

a.對(duì)一些行，列打“√”處理：

a-1.先對(duì)沒(méi)有⊙的第4行打“√”；

a-2.對(duì)打“√”第4行有φ的第1列也打“√”；

a-3.對(duì)打“√”的第1列中的⊙的行也在第2行打“√”。

b.劃水平、垂直線處理：

b-1.對(duì)沒(méi)有打“√”行中，第1行⊙劃水平線，第3行⊙與φ也劃水平聯(lián)線；

b-2.對(duì)已打“√”的列中⊙與φ也劃一垂直線。

c.求聯(lián)線數(shù)目L=3：

如果L值＜矩陣行數(shù)4，按伏格爾原理，就在最后打“√”的第2行中找出最小元素值2。

d.對(duì)打“√”行列±2：

對(duì)打“√”行的元素-2，對(duì)打“√”列的元素+2，對(duì)所有⊙與φ不±2保持⊙與φ。

e.再將只有一個(gè)0元素的行中0變?yōu)椤?，?duì)應(yīng)列中0變?yōu)棣眨賹⒘兄挥袀€(gè)一0變?yōu)棣铡?/p>

f.復(fù)查⊙數(shù)目=4=矩陣階數(shù)行數(shù)4，于是⊙變?yōu)?，其它φ及其元素?cái)?shù)變?yōu)?，獲得資源分配結(jié)論矩陣。

七、最優(yōu)決策結(jié)論

A農(nóng)村交通建設(shè)資金按丁方案規(guī)定提供6000萬(wàn)元；B農(nóng)村基本建設(shè)資金按乙方案規(guī)定提供9000萬(wàn)元；C農(nóng)村糧食蔬菜生產(chǎn)資金按甲方案提供7000萬(wàn)元；D改善農(nóng)村生活水平補(bǔ)助金按丙方案提供6000萬(wàn)元。共計(jì)分配28000萬(wàn)元。

八、結(jié)語(yǔ)

最小元素匈牙利法是資源分配的一種國(guó)外應(yīng)用的主流解法，如果只按某一規(guī)劃方案A、B、C、D方案之一分配資金，則甲方案42000萬(wàn)元，乙方案47000萬(wàn)元，丙方案33000萬(wàn)元，丁方案34000萬(wàn)元。而采用最小元素匈牙利法只要提供28000萬(wàn)元，所以采用這種方法是一種最優(yōu)決策，可供上一級(jí)決策者參考應(yīng)用。

[1]Kuhn．H．W．The Hungarian Method for The Assignment Problem[J]．Naval Res Logist Quart，1995，12（2）．

[2]袁遷、劉舒燕：關(guān)于匈牙利法的優(yōu)化[J]．武漢理工大學(xué)學(xué)報(bào)，2007，29（3）．

[3]向云、蘇華、余斌等：武漢城市圈城鄉(xiāng)一體化水平綜合評(píng)價(jià)研究[J]．華中師范大學(xué)生學(xué)報(bào)（自然科學(xué)版），2010，44（3）．

[4]張秀生、楊剛強(qiáng)：武漢城市圈一體化的功能及其發(fā)展路徑選擇[J]．科技進(jìn)步及對(duì)策，2008（12）．

[5]兩型社會(huì)實(shí)踐行[N]．武漢晚報(bào)，2011-06-11．

[6]劉舒燕：運(yùn)籌學(xué)[M]．人民交通出版社，1999．

（責(zé)任編輯：劉冰冰）