最大权完美匹配的“原始-对偶”算法.pdf.pdf

第26卷第1期2008年O1月佳木斯大学学报(自然科学版)JournalofJiamusiUniversity(NaturalScienceEdition):1008一la02(20os}ol一0100—02最大权完美匹配的“原始一对偶"算法沙元霞,任静(,黑龙江大庆163712;,黑龙江大庆163712)摘要:给出了利用“互补松弛原理”以及“原始一对偶原理”在一个完全赋权二部图G=(X,y,层,c￡,),c￡,≥0,II=IyI=:原始一对偶;完美匹配;互补松弛;修正;完全赋权二部图中图分类号:O157文献标识码::某公司准备分派个工人做件工作,这些工人中每人都胜任件或几件工作,同时把工人对各种工作的效率考虑进去,,构造完全赋权二部图G=(,Y,E,∞)的线性规划(LP)模型,去寻求此线性规划问题的最优解,:匹配(matching):设是E的一个子集,它的元素是图G中的连杆,并且这些连杆中的任意鼯个在G中均不相邻,:饱和(saturated):若匹配的某条边与顶点关联,:完美匹配:若G的每个顶点均为饱和的,:Kuhn—Munkres算法【l】:是在一个赋权图中寻找一个有最大权的完美匹配的一种方法,主要是构造子图Gj,不断修改可行顶点标号,再按新标号()去找匹配,重复进行,最后可得中顶点均为饱和的,:互补松弛定理:(ComplementmTSlackne88‰煳)。】:设,7r分别是和对偶的可行解,则,是最优解的充分必要条件是(dlx—b)=O(对任意的);(q一7r,)=O(对任意的.『)2主要结果下面给出求最大权的完美匹配的原始一对偶算法(一)构造最大权完美匹配的模型maxz=∑∑∞(1)∑=1i=1,2,?,(2)∑=1.『=1,2,?,(3)≥0i,j=1,2,?,n(=0,1)()=nfinz'=∑∑∞i=1』=1∑=1i=1,2,?,∑=1.『=1,2,?,≥0(5)首先把(1)':lnl‘n—:一25∑c￡,.在t2、),t3、)式q-,∑==一=厶∞·仕,厶1,:,21i12,?,,:1,.『:1,2,?,分另日表,=,,?,,=,.『=,,?,分另H表示在,y部中每个顶点处只选取一条边.=1表示此边在匹配中出现,=O表示此边在匹配中不出现.①收稿日期"-2007—12—25作者简介:沙元霞(tgso一),女,黑龙江大庆人,硕士,,等:最大权完美匹配的“原始一对偶”.(二)构造的对偶设(P)中的约束条件(4)为,i=I,2,?,n;(5)为竹,’『=I,2,?,+竹≤∑+∑得对偶问题(D):c。A丢∞2'?变量对偶以后所得到的与,实际上代表了与y