《求解指派问题的伏格尔方法.doc》由会员分享，可在线阅读，更多相关《求解指派问题的伏格尔方法.doc（4页珍藏版）》请在三一办公上搜索。
1、求解指派问题的伏格尔方法微1 ,申卯兴2 ,歆2 ,程智峰2叶高(1 西安交通大学理学院 , 陕西 西安 710049 ; 2 空军工程大学导弹学院 , 陕西 三原 713800)摘要 :通过对指派问题和运输问题的数学模型及其求解方法的分析比较 ,指出了作为运输问题特类的指派问题的特征及通常求解方法的弱点 ,在此基础上给出了求解 指派问题的伏格尔 ( Vogel) 方法的思想和步骤 ,并利用文献的数据给出具体的例证 . 关键词 :指派问题 ; 运输问题 ; 数学模型 ; 求解法 ; 伏格尔方法中图分类号 :O221 . 1文献标识码 : A在运筹学中 ,指派问题通常是作为一类特殊的 0 - 1
2、 规划问题来认识的 ,它有简明的独特解法 (如匈牙利法等) . 然而 ,在实际应用中不难发现 ,对于指派问题不仅在理论上可以用求解 运输问题的方法求解 ,而且解法清晰明了 ,特别是利用求解运输问题的伏格尔 ( Vo gel) 方法来求解指派问题 ,会显示出更多的优点 .运输问题和指派问题的比较指派问题是指在有 n 项任务要 n 个人员完成 , 而第 i 个人员做第 j 项工作的花费时间 ( 效 率) 为 cij ( i , j = 1 , 2 , , n) 的情况下 , 如何进行人员和任务的指派方可以使所花费的总时间 最短 ( 或效率最高) ; 运输问题是在已知产量分别为 ai 的 m 个产地
3、和销量分别为 bj 的 n 个销地 , 而从第 i 个产地到第 j 个销地的单位运价为 cij ( i = 1 , 2 , , m ; j = 1 , 2 , , n ) 的情况下 , 如何 进行调运以获得总运费最省的运输方案 ( 决策变量 x ij 是指从第 i 个产地调运到第 j 个销地的 调运量) . 这两个问题是运筹学中既古典又基本且具有广泛应用的问题 , 对此问题及其拓展问 题的求解方法的研究仍然是运筹学界的一个热点 . 为了对指派问题和运输问题有一个清晰的 认识 , 我们从分析其数学模型出发 , 从而得出适宜的求解方法和步骤 .1 . 1数学模型的比较指派问题的数学模型为 1 ,
4、2 1nncij x i j ,min z =i = 1 j = 1nnx ijx i j= 1 , x i j = 1 或 0 , i , j = 1 , 2 , , n .s. t .D =x i j |= 1 ,i = 1j = 1收稿日期 :2002210210基金项目 :国家高等学校骨干教师资助计划 ( GG2110529003921004) ;空军工程大学导弹学院拔尖人才基金资助项目作者简介 :叶微 (1961 ) ,男 ,陕西西安人 ,西安交通大学讲师 ,博士研究生运输问题的数学模型为 1 , 3 mncij x i j ,min z =i = 1 j = 1mnx ijx ij
5、s. t . D = x ij |= ai , 0 , i = 1 , 2 , , m ; j = 1 , 2 , , n .= bj ,x iji = 1j = 1x = ( x 11 , x 12 , , x 1 n , x 21 , , x 2 n , , x m n ) T ,c = ( c11 , c12 , , c1 n , c21 , , c2 n , , cm n ) T ,b = ( a1 , a2 , , a m , b1 , b2 , , bn ) T ,A = ( P11 , P12 , , P1 n , P21 , , P2 n , , P m m ) ,其中= ej
6、 + em + j = ( 0 , , 0 , 1 , 0 , , 0 , 1 , 0 , , 0) T , ei 为单位矩阵 I ( m + n) ( m + n) 的第 i 列 .若记Pij则运输问题的数学模型就变为min z = c T x ,A x = b ,s. t .( 1)x 0 .模型明确表明指派问题是运输问题的特例 , 即 mn= n , ai = bj = 1 , i , j = 1 , 2 , n ; 且由n于 ai= bj = n . 这就是说 , 指派问题是产销量都是 n 的产销平衡的运输问题 ; 决策变量i = 1j = 1x ij 全部是 0 - 1 变量 ( x
7、 i j = 0 , 1) , cij 表示第 i 个人员做第 j 个工作的花费时间 ( 或效率) , x ij =1 表示指派第 i 个人员做第 j 个工作 , x i j = 0 表示不指派第 i 个人员做第 j 个工作. 若采用前述 向量矩阵记号 , 并令 m = n , 则指派问题的数学模型就可简记为z = c T x ,A x = 1 ,x 0 , 1 .mins. t .( 2)其中 x 0 , 1 表示向量 x 的分量都是 0 或 1 , 在 ( 1) 和 ( 2) 中 A 都是以 0 或 1 为元素的0 - 1矩阵.1 . 2指派问题解的特性在指派问题中 , 由其背景要求知道它
8、的解中所含元素 1 的个数必须是 n . 又由于这里 i , j 的取值都是从 1 到 n , 由运输问题基本解的特性知道 , 对于这样的问题 , 它的解中所含非空格 的个数应该是 2 n - 1 , 这中间所差的 n - 1 个非空格的值都应以 0 来补充. 这就说明 , 指派问题 的解是运输问题的退化解 , 当然也可以认为指派问题是一类退化的运输问题 .1 . 3求解方法的比较这里以求解指派问题的匈牙利方法和求解运输问题的伏格尔方法来进行比较 . 指派问题 的匈牙利解法虽然步骤较少 , 但记忆起来容易混淆 . 特别是在作最少的直线覆盖所有的 0 元素 时 , 主观性比较大 , 难以掌握规律
9、 . 运输问题的伏格尔方法虽然计算量大 , 但很容易计算 , 而且 它所给出的初始解很接近最优解 , 有时候用伏格尔方法给出的初始解就是最优解 . 若考虑用伏 格尔方法求解指派问题 , 可以运用划去行列的办法取代添零的麻烦.1 . 4注意问题如果用伏格尔方法给出的初始解不是最优解 , 在闭回路调整时 , 因指派问题不存在给甲加上多少 , 给乙减去多少的说法 , 即要么是甲 , 要么是乙 , 二者不可并存 ( 产量和销量均为 1) . 因此 , 在采用闭回路调整法调优时 , 应把握是以较小花费的元素代替较大花费的元素 , 以闭回路 中的调入空格代替闭回路中花费最大的元素 , 并始终以其运量 1
10、作为调入调出量 , 这样就达到 优化的目的 . 在运价表上得到 n 个 1 , 便得到了使得总花费为最小的指派方案.1 . 5 求解指派问题的伏格尔方法根据上述分析 , 我们可以给出求解指派问题的思想方法 :按照求解运输问题伏格尔方法的 基本步骤进行 , 每步填写运量 1 , 同时划去行列 , 得出初始方案 . 在对初始方案的调整过程中应 掌握前述 1 . 4 中的注意问题. 这样 , 给出指派问题的伏格尔方法的步骤如下 :( )在指派问题的效率矩阵上分别计算出各行和各列的最低效率和次最低效率的差额 :行差额 u i 和列差额 v j , 并添加表的最右列 ( 行差额) 和最下列 ( 列差额)
11、 , 其中u i = min cij min cij - min cij ,v j = min ci j min ci j - min ci j ,j( i , jj= 1 , 2 , , n) ;jiii( ) 从行或列差额中选出最大者 , 选择它所在行或列中的最小元素 , 在此最小元素处作, 并划去该元素所在的行和列 ( 因为指派问题的产量和销量都是 1) 4 , 相应的决策变记号量 ( 解) x ij 的值为 1 , 在处填 1 ( 如果行或列中的最大值相同 , 行优先) ;( ) 在剩余的行和列的缩减效率矩阵 ( 表) 中重复第一 、二步 , 直到全部的行和列划完而在表中添满 n 个
12、1 给出初始解为止 ;( ) 应运输问题的初始基本解的性质 1 的要求而人为地添加 n - 1 个 0 , 以使表中非空 格的个数为 2 n - 1 , 并应用位势法 3 进行最优性检验 ;( ) 检验后 , 若最优 , 停 , 得到最优指派方案 ; 否则 , 用闭回路法 1 , 3 进行调整 , 调整后再检验 , 直至得到最优指派矩阵 ( 理论上已经证明最优解必存在 3 ) .例证例 1求由表 1 所示效率矩阵的指派问题1 的最优解 (最小解) .解利用伏格尔方法求解 .第一步 :分别计算出行差额和列差额 ,并填入表 ,见表 2 (无划线者) .2表 1 指派问题的效率矩阵Ta b. 1 E
13、ff iciency matrix of the assignment problem表 2 求解的行列差额和划线表Ta b. 2 Ro w and column diff erence and solving cross任务任务人员人员行差额ABCDEABCDE甲1279798791761261469乙89666丙71712149丁15146610戊4107109列差额32003甲1乙 丙丁12 7 9 7 95 14 6 6 1000203戊410 7 10 9第二步 :从行或列差额中选出最大者为 3 ,相应的行表 3 初始解Ta b. 3In itial solution列 (戊 ,A)
14、 ,戊行的最小元素为 4 ,作记号,并划去该元任务素所在的行和列 ,在处填 1 . 见表 2 .人员ABCDE第三步 :在剩余的行和列的效率矩阵 ( 表) 中重复第一 、二步 ,直到全部的行和列划完并填满 5 个 1 ,从而给 出如表 3 的初始解 .经检验知 ,此初始解即为最优解 . 即指派方案为 :甲 B ,乙 C ,丙 E ,丁 D ,戊 A . 这种解法比匈牙 利法明显简单 .甲乙 丙 丁 戊11111结论从以上分析和例证可以看出 ,匈牙利方法和伏格尔方法都可以解决指派问题 ,在理论上各 有优缺点 . 在实际应用中 ,本文所给出的伏格尔方法具有思路清晰 、操作简便的特点 ,特别对于 有
15、些指派问题 ,本文给出的伏格尔方法比通常文献中所使用的匈牙利方法更简单易行 .参考文献 :3123运筹学教材编写组 . 运筹学 M . 北京 :清华大学出版社 ,1990 . 79 , 129133 .牛映武 . 运筹学 M . 西安 :西安交通大学出版社 ,1994 . 147150 .魏国华 ,傅家良 ,周仲良 . 实用运筹学 M . 上海 :复旦大学出版社 ,1987 . 93108 .4 Shen M X , Chen g Z F , Yang J J . Imp roved Vogel met hod for t ransportatio n p roblem A . Zhan g
16、Xiang2sun , Liu De2gang. Operatio ns research and it s applicatio nsC . Bei jing : World Publishing Corporatio n , 2002 . 268273 .5 Gui gnard M , Rosenwein M B . An imp roved dual based algorit hm for t he generalized assignment p roblem J .Oper Res , 1989 , 37 (4) : 658663 .6 Chu P C , Beasla y J E
17、. A genetic algorit hm for t he generalized assignment p roblem J . Co m p ut Oper Res ,1997 , 24 (1) : 1723 .7 Edwin Ro meijn H , Dolores Ro mero Morales. Generating experimental data for t he generalized assignmentp roblem J . O per Res , 2001 , 49 (6) : 866878 .责任编辑张惠民Vogel method of a ssign ment
18、 problemYE Wei1 , SH EN Mao2xing2 , GAO Xin2 , CH EN G Zhi2feng2(1 Facult y of Science , Xian J iaoto ng U niversit y , Xian 710049 , Shaanxi , China ;2 Missile Instit ute , Air Fo rce Engineering U niversit y , Sanyuan 713800 , Shaanxi , China) Abstract : By co mparing and analyzing t he characteri
19、stics in t he mo dels and t he solving way bet ween assignment p ro blem and t ranspo rtatio n p ro blem , so me weak point s of t he usual solving met ho d are pointed o ut . Based o n t his , a solving way and it s step s of assignment p ro blem are p resented , w hich is called Vogel met ho d of assignment p ro blem. And t wo examples are demo nst rated.Key words : assignment p ro blem ; t ranspo rtatio n p ro blem ; mat hematical mo del ; solving met ho d ;Vogel met ho d444
