基于匈牙利资源分配法保障农村资金限额的最优决策

○张胜喜刘艳

（1、湖北轻工职业技术学院湖北武汉430070 2、武汉理工大学湖北武汉430070）

基于匈牙利资源分配法保障农村资金限额的最优决策

○张胜喜1刘艳2

（1、湖北轻工职业技术学院湖北武汉430070 2、武汉理工大学湖北武汉430070）

匈牙利法是一种指派问题的解法，将最小元素法引入匈牙利法中，减少了繁锁的计算过程，它是一种重要的资源分配手段。本文的应用表明这种方法具有较强的稳定性、可行性和有效性，对农村资金分配工作更有针对性。

匈牙利法0元素法指派问题农村资金限额最优分配决策

在探求工程投资、城乡建设投资、银行对企业贷款限额、投标公司申报承担工程项目费用限额、任务或工程的耗料、耗成本、耗能、耗工期量及人力资源消耗的最小化预想目标的竞争中，运筹科学地分配资源问题，又称为指派问题（Assignment Problem），是一种特殊的整数规划问题。这种问题在社会应用领域，尤其在经济领域会经常遇到。运筹分配资源的主流解法是由匈牙利数学家康尼格Kuhn. H.W提出的，称为匈牙利法，基于最小元素的匈牙利法是袁迁、刘舒燕在匈牙利法基础上提出的改进解法。本文针对分配给农村各类资金的建议资金限额方案甲、乙、丙、丁对各种类型农村资金A、B、C、D的提供进行最优决策，采用了这种最小元素匈牙利法。

一、分配给农村资金的用途

参照2011年国务院举行的中央经济工作会议中六大任务涉及农业和农村内容和文献武汉城市圈城乡一体化水平综合评价研究，特提出以下分配给农村资金的用途内容，也符合建设两型社会的需求。

1、城乡联接交通建设资金的用途

中央经济工作会议强调要千方百计确保主要农产品供给安全及其供应农产品的交通网建设，包括农村与城市联通的高速公路和一般公路交通圈建设、农村内部公路马路建设、交通基础设施建设、农村破损路改建工程、照明网设施改造项目、节能灯网改造项目以及排水管网和排污管网建设工程等。

2、农村基本建设资金的用途

中央经济工作会议中六大任务强调要加快构建覆盖城乡的公共文化服务保障。农村基建资金用于相关服务项目：金融服务、医疗服务、信息通讯服务、邮电服务、教育服务、水利服务、防灾抗旱服务、文化服务、提高农村绿化覆盖率、进行产业结构的固定资产投资、进行农村镇政府及社区管理机构建设等。

3、农业粮食蔬菜生产基金的用途

中央经济工作强调，要千方百计确保稳定粮食播种面积，增加农业生产补贴，加大粮食生产与投入和利益补贴

式中，Pij为一个方案i规定给j种资金的限额值，如7000万元。力度，加强农产品质量的安全管理机制的构建。要推进发展现代化农业技术，确保农产品有效供给，扩大农业耕地面积，发展蔬菜耕作基地，提高农业产值包括一产产值、二产产值和三产产值的农业增加值，同时发展农村的手工业和工业产业结构。

4、改善农村生活、文化水平资助金的用途

我国建设两型社会要促进城乡一体化水平，改善农村人口、农民的生活水平，提高农村对金融机构的贷款额度，提高农村金融服务水平，改善农村生态环境，提高农村生活垃圾无害化处理率和工业手工业废物利用处理达标率。

二、匈牙利法的数学模型

匈牙利库恩提出了资源分配问题的解法，引用了匈牙利数学家康尼格Kuhn.H.W的一个关于0元素定理。0元素定理要求在资源分配的效能矩阵中独立0元素的最多个数要等于能覆盖所有0元素的最少直线数目（参见案例阐明），这种方法称为匈牙利法。最小元素法是将效能矩阵中，每行元素值或每列元素值减去此行或此列的最小元素值，就获得有0元素的效能矩阵，当符号⊙的数目（只有一个0的行，列的0可变为⊙）等于效能矩阵的阶数（行数），就不进行对0元素的划直线工作，采用0元素划线的目的是解除同时出现2个最小元素值的冲突；当符号⊙的数目小于矩阵行数，就要进行划线处理（参见案例阐明），再按伏格尔原理来获得决策结论。

匈牙利数学模型要点是求解i个方案（或资源i）规定对J个资助基金（或J个工程项目，企业）的分配资金限额，要使总的效能或效益（Z），即总提供的资金达到最小化，即最高的效能。

0，1为效能矩阵最后处理后的矩阵元素值，i=1，2，…n个方案，公司J为=1，2，…m资金类型（A，B，C，D）或工程项目或企业。

表1 方案规定提供的资金现金限额（单位：千万元)

表1列出方案甲、乙、丙、丁规定提供农村A、B、C、D类型资金的限额。

三、将限额分配资金组成效能矩阵（BennfitMatrix）

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

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

C为每列最小值的个数，写在矩阵外的上边，其和∑C=C（SUM）是矩阵每列最小个数之和。R为每行最小值的个数，写在矩阵外的右边，其和∑r=r（SUM）是矩阵生行最小个数之和。甲、乙、丙、丁为各种资助方案，写在矩阵外的左边，A、B、C、D为农村资金类型，写在矩阵的上边。r（MIN）每行的最小值，写在矩阵外r的右边，C（MIN）每列的最小值，写在矩阵外的下边。

四、引入最小元素法的减法准则，化简效能矩阵

减法准则是比较∑r和∑C孰小，就先从矩阵的行或列减去该行或该列的最小元素值，来化简矩阵。本案例∑C=4＜∑r=5，故要先从“列”减去MIN值求得以下左边矩阵，再从左边矩阵找出行的MIN值，再按行减去MIN值，获得以下右边矩阵，再由行转入列处理，此矩阵此时每列MIN值全为0，故此矩阵无法再转换化简了，则作以下处理。

五、矩阵每行、列0变为⊙的处理

a.先从上转为列无法处理开始，先从列找只有一个0元素开始，第2列将0变为⊙，对应的行中0变为φ，再从第3列只有一个0变为⊙，剩下第1列有2个元素，故转入行的处理。

b.再按行中只有一个0元素转为⊙，对应列0元素变为φ。

六、当⊙数目小于矩阵阶数，⊙变1，其它变0的转换准则

本案例矩阵中⊙数目=3＜矩阵行数（阶数）=4，要按以下转换准则处理：

a.对一些行，列打“√”处理：

a-1.先对没有⊙的第4行打“√”；

a-2.对打“√”第4行有φ的第1列也打“√”；

a-3.对打“√”的第1列中的⊙的行也在第2行打“√”。

b.划水平、垂直线处理：

b-1.对没有打“√”行中，第1行⊙划水平线，第3行⊙与φ也划水平联线；

b-2.对已打“√”的列中⊙与φ也划一垂直线。

c.求联线数目L=3：

如果L值＜矩阵行数4，按伏格尔原理，就在最后打“√”的第2行中找出最小元素值2。

d.对打“√”行列±2：

对打“√”行的元素-2，对打“√”列的元素+2，对所有⊙与φ不±2保持⊙与φ。

e.再将只有一个0元素的行中0变为⊙，对应列中0变为φ，再将列只有个一0变为φ。

f.复查⊙数目=4=矩阵阶数行数4，于是⊙变为1，其它φ及其元素数变为0，获得资源分配结论矩阵。

七、最优决策结论

A农村交通建设资金按丁方案规定提供6000万元；B农村基本建设资金按乙方案规定提供9000万元；C农村粮食蔬菜生产资金按甲方案提供7000万元；D改善农村生活水平补助金按丙方案提供6000万元。共计分配28000万元。

八、结语

最小元素匈牙利法是资源分配的一种国外应用的主流解法，如果只按某一规划方案A、B、C、D方案之一分配资金，则甲方案42000万元，乙方案47000万元，丙方案33000万元，丁方案34000万元。而采用最小元素匈牙利法只要提供28000万元，所以采用这种方法是一种最优决策，可供上一级决策者参考应用。

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

[2]袁迁、刘舒燕：关于匈牙利法的优化[J]．武汉理工大学学报，2007，29（3）．

[3]向云、苏华、余斌等：武汉城市圈城乡一体化水平综合评价研究[J]．华中师范大学生学报（自然科学版），2010，44（3）．

[4]张秀生、杨刚强：武汉城市圈一体化的功能及其发展路径选择[J]．科技进步及对策，2008（12）．

[5]两型社会实践行[N]．武汉晚报，2011-06-11．

[6]刘舒燕：运筹学[M]．人民交通出版社，1999．

（责任编辑：刘冰冰）