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

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

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

2、划问题来认识的，它有简明的独特解法（如匈牙利法等）.然而，在实际应用中不难发现，对于指派问题不仅在理论上可以用求解运输问题的方法求解，而且解法清晰明了，特别是利用求解运输问题的伏格尔（Vogel）方法来、々紹垠派问挪么屁5屮雨欠的件占1运输问题和指派问题的比较指派问题是指在有a；项任务要个人员完成，而第/个人员做第y项工作的花费时间（效率）为c.aj=1，2,…，w的情况下，如何进行人员和任务的指派方可以使所花费的总时闾最短（或效率最高），•运输问题是在已知产量分别为的w个产地和销量分别为么的个销地而从第个产地

3、到第y个销地的单位运价为什（/=1,2，…，爪;j=,n）的情况下，如伺逬行调运以获得总运费最省的运输方案（决策变量是指从第/个产地调运到第y个销地的调运量）.这两个问题是运筹学中既古典又基本且具有广泛应用的问题，对此问题及其拓展匝题的求解方法的研究仍然是运筹学界的一个热点.为了对指派问题和运输问题有一个清晰的nnminz=^cuxu>s.t.D=[xuIVXij=1,VXij=1,=1或0，/，y=1，2，•••，4•收稿日期：2002210210基金项目：国家高等学校骨干教师资助计划（GC21105290

4、03921004）;空军工程大学导弹学院拔尖人才基金资助项目运输问题的数学模型为s.t.若记minz=巧，Tx=fXll,X12，…,Xln,X21,•••,X2",•••,Xmn)?b=(9a2f,atn,b],A=(Pii，P】2，…，Pl",其中p'y=ef+em+i=(0,•••，0，l,0,…则运输问题的数学模型就变为办2,…，W「，?21，…，P2w，…，Pmm)9,0,1,0,…，0)T,q为单位矩阵…⑽幻n的第/列.minz=cTx,JAx=b，s.t.),2,…«，•且由Lx>0.模型明确表明

5、指派问题是运输问题的特例，即〃7=«，《,=/?/=1,/,7。.这就是说，指派问题是产销量都是〃的产销平衡的运输问题，•决策变量全部是0-1变量=0，U,G:,■表示第/个人员做第J个工作的花费时间(或效率厂~=1表示指派第/个人员做第y个工作，~=0表示不指派第/个人员做第j个工作.若采用前述向量矩阵记号，并令〃/=〃，则指派问题的数学模型就可简记力minz=c1x,fAx=1,s.t.)(2)其中xE{0，l}表示向量X的分量都是0或1，在(1)和(2)中A都是以0或1为元素的0-1矩阵.Lxe/0,1厂

6、1.2指派问题解的特性在指派问题中，由其背景要求知道它的解中所含元素1的个数必须是。.又甶于这里/,、的取值都是从I到。，由运输问题基本解的特性知道，对于这样的问题，它的解中所含非空格的个数应该是2/7-1，这中间所差的1个非空格的值都应以0来补充.这就说明，指派问题的解是运输问题的退化解，当然也可以认为指派问题是一类退化的运输问题.1.3求解方法的比较这里以求解指派问题的匈牙利方法和求解运输问题的伏格尔方法来逬行比较.指派问题的匈牙利解法虽然步骤较少，但记忆起来容易混淆.特别是在作最少的直线覆盖所有的0元素时

7、，主观性比较大，难以掌握规律.运输问题的伏格尔方法虽然计算量大，但很容易计算，而且上多少，给乙减去多少的说法，即要么是甲，要么是乙，二者不可并存（产量和销量均为1厂闪此，在采用闭回路调整法调优时，应把握是以较小花费的元素代替较大花费的元素，以闭回路中的调入空格代替闭回路中花费最大的元素，并始终以其运量1作为调入调出量，这样就达至I、优化的目的.在运价表上得到/7个1,便得到了使得总花费为最小的指派方案.1.5求解指派间题的伏格尔方法根据上述分析，我们可以给出求解指派问题的思想方法.•按照求解运输问题伏格尔方法的

8、基本步骤逬行，每步填写运量1,同时划去行列，得出初始方案.在对初始方案的调整过程中应■^t^mTzTtr1/I士音iHl師岭屮士甴：吒1刊目帀的伴议亡;土的牛fl昭hnT.（1）在指派H题的效率矩阵上分别计算出各行和各列的最低效率和次最低效率的差额.•行差额W,•和列差额vy,并添加表的最右列（行差额）和最下列（列差额），苏中Ui=min/djiinf