产销平衡运输问题的表上作业法解法的一个注记_谢凡荣
第14卷 第4期2005年8月运 筹 与 管 理
OPERATIONSRESEARCHANDMANAGEMENTSCIENCE
Vol.14,No.4Aug.2005
产销平衡运输问题的表上作业法解法的一个注记
谢凡荣
(南昌大学数学系,江西南昌330047)
摘 要:本文给出了用表上作业法求解产销平衡运输问题当出现退化时在相应空格填/00的更为明确的规则,利用该规则可以避免可能存在的多余计算。本文还给出了用改进后的表上作业法求解指派问题的方法和步骤,该方法与求解指派问题的常用方法/匈牙利法0相比,具有手工计算更为简便的优点。关键词:运筹学;运输问题;产销平衡运输问题;指派问题;表上作业法中图分类号:O157.6 文章标识码:A 文章编号:1007-3221(2005)04-0044-03
ANoteoftheTable-manipulationMethodforSolvingthe
TransportionProblemWithBalancedSupplyandDemand
XIEFan-rong
(MathematicsDepartment,NanchangUniversity,Nanchang330047,China)
Abstract:Whilethetable-manipulationmethodisusedtosolvethetransportionproblemwithbalancedsupplyanddemandandthereexisitsthecaseofdegeneration-solution,moreaccuraterules,whichcanavoidthepos-siblyexistingredundantcalculation,arepresentedforfillingzeroincorrespondingblanketofthebalancedtableinthepaper.Themethodandprocedure,bywhichtheimprovedtable-manipulationmethodisusedtosolvetheassignmentproblem,arealsopresentedinthepaper,andthemethodhastheadvantageofmoresim-plicityandconvenienceovertheHungaryMethodoftenusedforsolvingtheassignmentproblemwhilemanualcalculationisadopted.
Keywords:operationsresearch;thetransportationproblem;thetransportionproblemwithbalancedsupplyanddemand;theassignmentproblem;thetable-manipulationmethod
0 引言
本文未特别申明的有关概念和记号与文献[1]相同。文献[1]给出了产销平衡运输问题的表上作业法解法,还给出了把产销不平衡运输问题化为产销平衡运输问题的方法。手工计算时,表上作业法是求解运输问题的常用方法。求解产销平衡运输问题的表上作业法的步骤可用框图描述如图1。
文献[1](p89-90)指出:/用表上作业法求解产销平衡运输问题当出现退化时,在相应空格中一定要填一个-0.,以此表示为数字格。有以下两种情况:
收稿日期:2004-12-04
,,。
图1 求能产销平衡运输问题表上作业法框图
第4期 谢凡荣:产销平衡运输问题的表上作业法解法的一个注记45
(1)当确定初始解(初始可行方案)的各供需关系时,若在(i,j)格填入某数字后,出现Ai处的余量等于Bj处的需量。这时在产销平稳表上填一个数,而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格,这时需要添一个-0.,它的位置可在对应同时划去的那行或那列的任一空格处。
(2)在用闭回路法调整时,在闭回路上出现两个和两个以上的具有(-1)标记的相等的最小值。这时只能选择其中一个作为调入格。而经调整后,得到退化解。这时有一个数字格必填上一个0,表明它是基变量。当出现退化解后,并作改进调整时,可能在某个闭回路上有标记为(-1)的取值为0的数字格,这时应取调整量H=0。0可以看出,文献[1]并没指出在相应空格填/00的确切位置(相关文献也如此
[2,3]
),这种
不确定性有可能造成不必要的多余计算。下面举例加以说明。
例1 (取自文献[1]p89):有一个运输问题,产销平衡表、单位运价表分别如表1、表2所示。
表1 (产销表)
A1A2A3销量
33
66
5
6
B1
B2
B3
B4
产量749
A1A2A3
B13s7s1,
表2 (运价表)
B211s7s2,
10,
6
3
8
B34
B45
表3 (产销表)
A1
A2A3销量
33
66
5
B1
B2
B314
06B46
产量749
A1
A2A3销量
33B1
表4 (运价表)
B2
B31
066
54
06B46
产量749
用最小元素法确定初始基可行解(初始可行调运方案):因第一次划去运价表的第一列,剩下最小元素2,其对应的销地B2,需要量为6,而对应的产地A3未分配量也是6。这时在产销(3,2)交叉格中填入6,这时在单位运价表1中需同时划去B2列A3行。在表1的空格(1,2)、(2,2)、(3,3)、(3,4)中选一空格添加一个0,不难发现:(1)选空格(3,4)添加一个0时,得初始可行调运方案如表3,用位势法计算空格(非基变量)的检验数,知所有检验数满足最优准则(\0),推得表3给出的方案已是最优解(最优方案);(2)选空格(2,2)添加一个0时,得初始可行调运方案如表4,用位势法计算空格(非基变量)的检验数,空格(1,1)的检验数为R11=-4,不能推得表4给出的方案已是最优解,按表上作业法的步骤还需要对其调整。事实上,表3和表4给出的方案是相同的方案。(3)选空格(3,3)或(1,2)添加一个0时,出现的情况与(2)类似。究其原因,是空格(3,4)对应单位运价在(1,2)、(2,2)、(3,3)、(3,4)中最小。
于是,我们得到用表上作业法求解产销平衡运输问题当出现退化时在相应空格填/00的更为明确的规则如下:
规则1 当确定初始解(初始可行方案)的各供需关系时,若在(i,j)格填入某数字后,出现Ai处的余量等于Bj处的需量。这时在产销平稳表上填一个数,而在单位运价表上相应地要划去一行和一列。为了使在产销平衡表上有(m+n-1)个数字格,这时需要添一个-0.,它的位置是在对应这时同时划去的那行或那列的所有空格处中对应单位运价最小的任一空格。
规则2 在用闭回路法调整时,在闭回路上出现r(\2)个具有(-1)标记的相等的最小值。这时只能选择其中一个作为调出格。而经调整后,得到退化解。这时有(r-1)个数字格必填上0,它们的位置是在闭回路上具有(-1)标记的调运量为0的对应单位运价最小的(r-1)个的数字格,表明它们是基变量。当出现退化解后,并作改进调整时,可能在某个闭回路上有标记为(-1)的取值为0的数字格,这时应取调整量H=0;并把闭回路上标记为(-1)取值为0的数字格中对应单位运价最大的一个数字格变为调出格(,,
46
我们有以下结论:
运 筹 与 管 理 2005年第14卷
定理1 用表上作业法求解产销平衡运输问题当出现退化时,按规则1和规则2在相应空格填/00,可以避免可能存在的多余计算。
利用定理1和求解产销平衡运输问题的表上作业法,我们有对文献[4]作改进的求解极小化指派问题的表上作业法如下:
Step1 把指派问题看作产地数和销地数相等的产销平衡运输问题,人员对应于产地,任务对应于销地,指派问题的效率矩阵(表)对应于运输问题的单位运价矩阵(表),所有产地的产量以及所有销地的销量都为1。
Step2 按求解产销平衡运输问题的表上作业法的框图1和规则1和规则2求解Step1对应的运输问题。此时求得的最优解即对应于指派问题的最优解。
对于极大化指派问题,可先按文献[1]中的方法把它化为极小化指派问题,再用以上方法求解。
例2 (取自文献)[1]p131例8)求表5所示的指派问题的最小解。
表5
甲乙丙丁戊
A1287154
B79171410
C961267
D7614610
E969109
甲乙丙丁戊销量
11
1
101
1
10
A
B1
1
表6
C
D
E001
产量111111
解 按求解指派问题的表上作业法,先用最小元素法求得初始基可行解(初始可行调运方案)如表6,用位势法计算空格(非基变量)的检验数(见表7),只有空格(1,4)(即(甲,D))的检验数R14=-2
表7
甲乙丙丁戊vj
A128715¼6
B¿91714107
C9612¾¿9
D7¾14¾109
EÁ¾Á1099
ui
0-30-3-2
甲乙丙丁戊vjA128715¼4
表8
B¿91714107
C9612¾¿7
D¿¾14¾107
E9¾Á1097
ui0-12-10
参考文献:
[1]钱颂迪.运筹学[M].北京:清华大学出版社,1990.
[2]魏权龄,胡显佑,黄志民.运筹学简明教程[M].北京:中国人民大学出版社,1996.[3]韩伯棠.管理运筹学[M].北京:高等教育出版社,2000.
[4]高俊琦.指派问题的表上作业解法[J].运筹与管理,2000,9(1):64-68.