运输问题初始基可行解算法退化问题的解决  

Degenerate Problem on the Transportation Problem for Obtaining the Initial Basic Feasible Solution

作　　者：韩伟一[1] 王梓丞 孙童 万晶 HAN Wei-yi;WANG Zi-cheng;SUN Tong;WAN Jing(School of Economic and Management,Harbin Institute of Technology,Harbin 150001,China)

机构地区：[1]哈尔滨工业大学经济与管理学院,黑龙江哈尔滨150001

出　　处：《数学的实践与认识》2023年第10期260-265,共6页Mathematics in Practice and Theory

基　　金：国家自然科学基金(12171121);哈尔滨工业大学研究生教育改革项目(22HX0901)。

摘　　要：西北角法、最小元素法和伏格尔法是运输问题求解初始基可行解的三个广泛流行的方法.虽然这三个方法已经采取了反退化的措施,但仍然存在缺陷.本文分别给出三个反例,说明退化问题的存在仍旧会使得三个方法无法得到m+n-1个基变量.不仅如此,别的算法也同样存在上述问题.在此种情形下,可以使用补零方法加以事后补救,但非常麻烦.为此,本文分别对三种主流方法进行了改进,改进后的算法不仅简单方便,而且总能获得m+n-1个基变量,完美解决了退化问题.Northwest corner method,least cost method and Vogel's approximation method are three popular methods to obtain the initial basis feasible solution of transportation problem.Although three methods have taken anti-degeneration measures,they still have defects.In the paper,three counter examples are given to ilustrate that three methods can't still obtain m+n-1 base variables in degenerate cases.Furthermore,other algorithms can also exist same degenerate problem.Generally,we can remedy afterwards by adding zero cells to solve the above problem,but it is very troublesome.Therefore,we improve these three methods,which are not only simple and convenient,but also can always obtain m+n-1 base variables.So we perfectly solve the above degenerate problem.

关 键 词：运输问题 表上作业法 西北角法 最小元素法 伏格尔法 退化问题 

分 类 号：O221.1[理学—运筹学与控制论]