○張勝喜劉艷
(1、湖北輕工職業(yè)技術(shù)學(xué)院湖北武漢430070 2、武漢理工大學(xué)湖北武漢430070)
基于匈牙利資源分配法保障農(nóng)村資金限額的最優(yōu)決策
○張勝喜1劉艷2
(1、湖北輕工職業(yè)技術(shù)學(xué)院湖北武漢430070 2、武漢理工大學(xué)湖北武漢430070)
匈牙利法是一種指派問題的解法,將最小元素法引入匈牙利法中,減少了繁鎖的計(jì)算過程,它是一種重要的資源分配手段。本文的應(yīng)用表明這種方法具有較強(qiáng)的穩(wěn)定性、可行性和有效性,對(duì)農(nóng)村資金分配工作更有針對(duì)性。
匈牙利法0元素法指派問題農(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é)地分配資源問題,又稱為指派問題(Assignment Problem),是一種特殊的整數(shù)規(guī)劃問題。這種問題在社會(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)決策,采用了這種最小元素匈牙利法。
參照2011年國務(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萬元。力度,加強(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)村生活、文化水平資助金的用途
我國建設(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)村生活垃圾無害化處理率和工業(yè)手工業(yè)廢物利用處理達(dá)標(biāo)率。
匈牙利庫恩提出了資源分配問題的解法,引用了匈牙利數(shù)學(xué)家康尼格Kuhn.H.W的一個(gè)關(guān)于0元素定理。0元素定理要求在資源分配的效能矩陣中獨(dú)立0元素的最多個(gè)數(shù)要等于能覆蓋所有0元素的最少直線數(shù)目(參見案例闡明),這種方法稱為匈牙利法。最小元素法是將效能矩陣中,每行元素值或每列元素值減去此行或此列的最小元素值,就獲得有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é)論。
匈牙利數(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)金限額(單位:千萬元)
表1列出方案甲、乙、丙、丁規(guī)定提供農(nóng)村A、B、C、D類型資金的限額。
(列)∑C=4,C∶1111(行)r∶r(MIN)
(列)C(MIN)6676(行)∑r=5
C為每列最小值的個(gè)數(shù),寫在矩陣外的上邊,其和∑C=C(SUM)是矩陣每列最小個(gè)數(shù)之和。R為每行最小值的個(gè)數(shù),寫在矩陣外的右邊,其和∑r=r(SUM)是矩陣生行最小個(gè)數(shù)之和。甲、乙、丙、丁為各種資助方案,寫在矩陣外的左邊,A、B、C、D為農(nóng)村資金類型,寫在矩陣的上邊。r(MIN)每行的最小值,寫在矩陣外r的右邊,C(MIN)每列的最小值,寫在矩陣外的下邊。
減法準(zhǔn)則是比較∑r和∑C孰小,就先從矩陣的行或列減去該行或該列的最小元素值,來化簡(jiǎn)矩陣。本案例∑C=4<∑r=5,故要先從“列”減去MIN值求得以下左邊矩陣,再從左邊矩陣找出行的MIN值,再按行減去MIN值,獲得以下右邊矩陣,再由行轉(zhuǎn)入列處理,此矩陣此時(shí)每列MIN值全為0,故此矩陣無法再轉(zhuǎn)換化簡(jiǎn)了,則作以下處理。
a.先從上轉(zhuǎn)為列無法處理開始,先從列找只有一個(gè)0元素開始,第2列將0變?yōu)椤?,?duì)應(yīng)的行中0變?yōu)棣?,再從?列只有一個(gè)0變?yōu)椤眩O碌?列有2個(gè)元素,故轉(zhuǎn)入行的處理。
b.再按行中只有一個(gè)0元素轉(zhuǎn)為⊙,對(duì)應(yīng)列0元素變?yōu)棣铡?/p>
本案例矩陣中⊙數(shù)目=3<矩陣行數(shù)(階數(shù))=4,要按以下轉(zhuǎn)換準(zhǔn)則處理:
a.對(duì)一些行,列打“√”處理:
a-1.先對(duì)沒有⊙的第4行打“√”;
a-2.對(duì)打“√”第4行有φ的第1列也打“√”;
a-3.對(duì)打“√”的第1列中的⊙的行也在第2行打“√”。
b.劃水平、垂直線處理:
b-1.對(duì)沒有打“√”行中,第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é)論矩陣。
A農(nóng)村交通建設(shè)資金按丁方案規(guī)定提供6000萬元;B農(nóng)村基本建設(shè)資金按乙方案規(guī)定提供9000萬元;C農(nóng)村糧食蔬菜生產(chǎn)資金按甲方案提供7000萬元;D改善農(nóng)村生活水平補(bǔ)助金按丙方案提供6000萬元。共計(jì)分配28000萬元。
最小元素匈牙利法是資源分配的一種國外應(yīng)用的主流解法,如果只按某一規(guī)劃方案A、B、C、D方案之一分配資金,則甲方案42000萬元,乙方案47000萬元,丙方案33000萬元,丁方案34000萬元。而采用最小元素匈牙利法只要提供28000萬元,所以采用這種方法是一種最優(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é)任編輯:劉冰冰)