求解指派问题的伏格尔方法

《求解指派问题的伏格尔方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、求解指派问题的伏格尔方法微1,申卯兴2,歆2,程智峰2叶高(1西安交通大学理学院,陕西西安710049;2空军工程大学导弹学院,陕西三原713800)摘要:通过对指派问题和运输问题的数学模型及其求解方法的分析比较,指出了作为运输问题特类的指派问题的特征及通常求解方法的弱点,在此基础上给出了求解指派问题的伏格尔(Vogel)方法的思想和步骤,并利用文献的数据给出具体的例证.关键词:指派问题;运输问题;数学模型;求解法;伏格尔方法中图分类号:O221.1文献标识码:A在运筹学中,指派问题通常是作为一类特殊的0-1规划问题来认识的,它有简

2、明的独特解法(如匈牙利法等).然而,在实际应用中不难发现,对于指派问题不仅在理论上可以用求解运输问题的方法求解,而且解法清晰明了,特别是利用求解运输问题的伏格尔(Vogel)方法来求解指派问题,会显示出更多的优点.运输问题和指派问题的比较指派问题是指在有n项任务要n个人员完成,而第i个人员做第j项工作的花费时间(效率)为cij(i,j=1,2,⋯,n)的情况下,如何进行人员和任务的指派方可以使所花费的总时间最短(或效率最高);运输问题是在已知产量分别为ai的m个产地和销量分别为bj的n个销地,而从第i个产地到第j个销地的单位运价为c

3、ij(i=1,2,⋯,m;j=1,2,⋯,n)的情况下,如何进行调运以获得总运费最省的运输方案(决策变量xij是指从第i个产地调运到第j个销地的调运量).这两个问题是运筹学中既古典又基本且具有广泛应用的问题,对此问题及其拓展问题的求解方法的研究仍然是运筹学界的一个热点.为了对指派问题和运输问题有一个清晰的认识,我们从分析其数学模型出发,从而得出适宜的求解方法和步骤.1.1数学模型的比较指派问题的数学模型为[1,2]1nn∑∑cijxij,minz=i=1j=1nn∑xij∑xij=1,xij=1或0,i,j=1,2,⋯,n.s.t.

4、D=xij

5、=1,i=1j=1收稿日期:2002210210基金项目:国家高等学校骨干教师资助计划(GG2110529003921004);空军工程大学导弹学院拔尖人才基金资助项目作者简介:叶微(1961—),男,陕西西安人,西安交通大学讲师,博士研究生运输问题的数学模型为[1,3]mn∑∑cijxij,minz=i=1j=1mn∑xij∑xijs.t.D=xij

6、=ai,≥0,i=1,2,⋯,m;j=1,2,⋯,n.=bj,xiji=1j=1x=(x11,x12,⋯,x1n,x21,⋯,x2n,⋯,xmn)T,c=(c11,c12

7、,⋯,c1n,c21,⋯,c2n,⋯,cmn)T,b=(a1,a2,⋯,am,b1,b2,⋯,bn)T,A=(P11,P12,⋯,P1n,P21,⋯,P2n,⋯,Pmm),其中=ej+em+j=(0,⋯,0,1,0,⋯,0,1,0,⋯,0)T,ei为单位矩阵I(m+n)×(m+n)的第i列.若记Pij则运输问题的数学模型就变为minz=cTx,Ax=b,s.t.(1)x≥0.模型明确表明指派问题是运输问题的特例,即mn=n,ai=bj=1,i,j=1,2,⋯n;且由n于∑ai=∑bj=n.这就是说,指派问题是产销量都是n的产销平衡的

8、运输问题;决策变量i=1j=1xij全部是0-1变量(xij=0,1),cij表示第i个人员做第j个工作的花费时间(或效率),xij=1表示指派第i个人员做第j个工作,xij=0表示不指派第i个人员做第j个工作.若采用前述向量矩阵记号,并令m=n,则指派问题的数学模型就可简记为z=cTx,Ax=1,x∈{0,1}.mins.t.(2)其中x∈{0,1}表示向量x的分量都是0或1,在(1)和(2)中A都是以0或1为元素的0-1矩阵.1.2指派问题解的特性在指派问题中,由其背景要求知道它的解中所含元素1的个数必须是n.又由于这里i,j的

9、取值都是从1到n,由运输问题基本解的特性知道,对于这样的问题,它的解中所含非空格的个数应该是2n-1,这中间所差的n-1个非空格的值都应以0来补充.这就说明,指派问题的解是运输问题的退化解,当然也可以认为指派问题是一类退化的运输问题.1.3求解方法的比较这里以求解指派问题的匈牙利方法和求解运输问题的伏格尔方法来进行比较.指派问题的匈牙利解法虽然步骤较少,但记忆起来容易混淆.特别是在作最少的直线覆盖所有的0元素时,主观性比较大,难以掌握规律.运输问题的伏格尔方法虽然计算量大,但很容易计算,而且它所给出的初始解很接近最优解,有时候用伏格

10、尔方法给出的初始解就是最优解.若考虑用伏格尔方法求解指派问题,可以运用划去行列的办法取代添零的麻烦.1.4注意问题如果用伏格尔方法给出的初始解不是最优解,在闭回路调整时,因指派问题不存在给甲加上多少,给乙减去多少的说法,即要么是甲,要