【word】 最大权完美匹配的“原始-对偶”算法

【word】 最大权完美匹配的“原始-对偶”算法 最大权完美匹配的“原始-对偶”算法 第26卷第1期 2008年O1月 佳木斯大学(自然科学版) JournalofJiamusiUniversity(NaturalScienceEdition) Vo1.26No.1 Jan.2008 文章编号:1008一la02(20os}ol一0100—02 最大权完美匹配的”原始一对偶”算法 沙元霞,任静 (1.大庆师范学院数学系,黑龙江大庆163712;2.大庆二十二中高中部,黑龙江大庆163712) 摘要:给出了利用”互补松弛原理”以及”原始一对偶原理”在一个完全赋权二部图G=(X, y,层,c,,),c,,?0,II=IyI=中寻找最大权完美匹配的算法和过程. 关键词:原始一对偶;完美匹配;互补松弛;修正;完全赋权二部图 中图分类号:O157文献标识码:A 0引言 寻找图的最大权完美匹配的应用是极其广泛 的.最着名的如人员的最优选派问:某公司准备 分派个工人做件工作,这些工人中每人都胜任 一 件或几件工作,同时把工人对各种工作的效率考 虑进去,求使所有工人都分派做一件他胜任的工作 并使总效率最大. 本文利用以互补松弛为核心的原始一对偶算 法,构造完全赋权二部图G=(,Y,E,?)的线性 规划(LP)模型,去寻求此线性规划问题的最优解, 从而求得最大权的完美匹配. 1预备知识 定义1:匹配(matching):设是E的一个子 集,它的元素是图G中的连杆,并且这些连杆中的 任意鼯个在G中均不相邻,则称为G的匹配. 定义2:饱和(saturated):若匹配的某条边 与顶点关联,则称饱和顶点. 定义3:完美匹配:若G的每个顶点均为 饱和的,则称为G的完美匹配. 定义4:Kuhn—Munkres算法【l】:是在一个赋 权图中寻找一个有最大权的完美匹配的一种方法, 主要是构造子图Gj,不断修改可行顶点标号,再按 新标号()去找匹配,重复进行,最后可得中顶 点均为饱和的,即得到最大权完美匹配. 定理1:互补松弛定理:(ComplementmT Slackne88‰煳).】: 设,7r分别是和对偶的可行解,则, 是最优解的充分必要条件是 = (dlx—b)=O(对任意的); = (q一7r,)=O(对任意的.『) 225?c,,.在t2,),t3,)式q-,?==一=厶??仕,厶f_1=1=1 1,:,21i12,…,,:1,.『:1,2,…,分另日表,=,,…,,=,.『=,,…,分另H表 示在,y部中每个顶点处只选取一条边.=1 表示此边在匹配中出现,=O表示此边在匹配中 不出现. ?收稿日期”-2007—12—25 作者简介:沙元霞(tgso一),女,黑龙江大庆人,硕士,主要从事组合优化和图论方面研究. 第1期沙元霞,等:最大权完美匹配的”原始一对偶”算法101 三个约束条件限制了按权重选边后形成完美 匹配.得到模型. (二)构造的对偶 设(P)中的约束条件(4)为,i=I,2,…,n; (5)为竹,’『=I,2,…,n.有f+竹? inax?+? 得对偶问题(D): c.A i,丢?2’… 变量对偶以后所得到的与,实际上代表 了与y部中各点的标号. (三)由互补松弛原理[2]可知, 对Vi,有{},{,竹}分别是(P)与(D)的 最牌营+.. ? . ? 表示图G的完美匹配中的边.最优 解中有>0.又,[?一(+竹)]=0,故i+ ,=?.又??0,构造(D)的一个初始可行解 0 . XY ? jY. 满L =V??……”‘ +=?的(i,)构成允许可列集J={(i,)I +=?}.此过程为给顶点,进行标号,, 即赋予初始可行解时得到的匹配.但允许可列集’, = {(i,)Ii+f=?}是否为一个完美匹配? (四)构造(RP)问题,验证是否找到完美匹配 2 min=?%i=l ?+=1=1 ?+:+=1i:L %?0 %=0 ?0 如果=0,则原问题已经达到最优解.如果 >0,说明还存在X中的标号为的点未饱和. 故构造(D冗P)去修正与. (五)构造(DRP) 由(RP)求解得{要(,_『隹,可求得 (DRP)为?+? Ii+?1’,’,=1,2,…,n 【,,无限制 根据[1一(+)]=0以及 {薹来求c+). (六)修正(,),由 i 故( t儿+,J (,)=(i,,u/)+(f+竹) +mln ,{}( = (,)+(min,一(,)}(6) 且?(,)(rllln一(,竹)} 事实上(6)式中0?(,)起到的作用与 Kuhn—Munkres方法中的口的作用是相同的,从这 个方面我们可以看到经过上述(一)一(六)的原始 一 对偶算法的正确性. (,,uj)=(,所)+(rain一(,)} =f+(f,ll~ln , {?一(i,竹)},竹+ (, {?一(i, 竹)} 其实质是把权第二大的边找出来. (七)将(,,uj)代人(D)中求+=?的 项,并添加到J中. 进行上述(D)一(RP)一(DRP)步骤,直到 (RP)中=0为止,即完美匹配找到. 3结束语 原始一对偶算法是一种在组合优化中很重要 的方法,适用于线性规划等问题.从上述过程中可 以看到,我们对最大权完美匹配问题所构造的原始 一 对偶算法在某些修正的参数上与Kulm—Munk~ 方法达到了一致的效果,从而也从另一角度验证了 我们这个算法的正确性. 参考文献: [1]tk~ndyJ.A,Mutt],USR.GraphTheoryandApplieatiom[M].New Y0d【:Academicpress.1976:70—75. [2]clmIsr0S,KENNE3~,CombinatorialOptimization[M].Mineola, NewYork:DOVERPI?jICAT【0.137—142.71—81. [3]谢政,戴丽.组合图论[M].长沙:国防科技大学出版社,2OO3: 71—8o. (下转105页) ?隹一 ))2..,,,1.’. ((= ? 第1期边文莉,等:煤矿瓦斯和煤尘的控制研究105 由瓦斯涌出不均衡通风系数调节后进风量为: 1311.1×1.192=1562.8(1). 4结语 该模型的解题步骤简单,思路清晰,便于应用. 另外如果有条件应尽量再多考虑一些有关瓦斯涌 出过程的变量,用统计理论来描述解决此类问题会 更深刻一些. 参考文献: [1]王沫然.Matlal】6.0与科学计算[M].北京:电子工业出版社, 2001年9月. [2]王家文,曹宇.MIB6.5图形图像处理[M].北京:国防工 业出版社,2OO4年. [3]数学模型编写组编.数学模型[M].广2fIf:华南理工大学出版 社,2001年8月. [4]现代应用数学手册.运筹学与最优化理论[M].北京:清华大 学出版社,1998年4月. [5]姜启源.数学建模[M].北京:高等教育出版社,1993年8月. [6]邰淑彩.应用数理统计[M],武汉:武汉大学出版社,加喳年7月. AResearchOilGasandDustControlinCoa1..mine B/ANWen一//,CA/J/an—pl, (z~il.ngWalterc【憷灌ncyI|3血呷佣材Qge;珏q蛳I310018,) AIJ~xact-Intlfispaper,basedOilaprogrammedmodel,theautho~tliedtofindthebestventilationofthecoal — mille.Accordingtothesafeproductionz~-lulafion8,therelationshipbetweenthewindsp剃andthedemityofgas anddustwasdetermined.ThedensityofgasanddustWO,8expressedintheformoffunctionofwindquantity.Accord- ingtothelimitationofthedensityofgasanddust,thelimitationtowindquantityWO,8calculated,andthen,alinear programmingmodelwasconstructedandabestventilationandcontrollingwayn8obtained. Keywords_.ventilation;linearregression;linearpmgrammm’g;relativepouringquantityofgas;ah6olutepOUr- ingquantityofgas (上援101页) Primal--dualAlgorithnlsforMax--weightPerfectMatching SHAYuan一’,REN.//,lg (1?Malhcuit~csD’嘲蛐t,IlaqingNorm~UdV黼 sily,I1wllng163712,Clmlna,2.n.qIngNo.22MiddleSclao~,I)目 Iqh163712,Chh-) Abstract:InthisI~per,thedetailandalgoriflamfor~lJinweightptbctmatchin ginacompleteweighted bipartite,G=(,Y,E,),CO?0,II:IYI=tl,,wstudied.Themainmethodsacomple mentary— slaeknessatheomlaandprimal—dualalgorithn~. Keywords:pdmal—dual;perfectmatehing~complementary—slackness;e uler-function;repair;complete weiO,tedbipartite