摘要
西北角法、最小元素法和伏格尔法是运输问题求解初始基可行解的三个广泛流行的方法.虽然这三个方法已经采取了反退化的措施,但仍然存在缺陷.本文分别给出三个反例,说明退化问题的存在仍旧会使得三个方法无法得到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.
作者
韩伟一
王梓丞
孙童
万晶
HAN Wei-yi;WANG Zi-cheng;SUN Tong;WAN Jing(School of Economic and Management,Harbin Institute of Technology,Harbin 150001,China)
出处
《数学的实践与认识》
2023年第10期260-265,共6页
Mathematics in Practice and Theory
基金
国家自然科学基金(12171121)
哈尔滨工业大学研究生教育改革项目(22HX0901)。
关键词
运输问题
表上作业法
西北角法
最小元素法
伏格尔法
退化问题
transportation problem
transportation simplex method
northwest corner method
least cost method
Vogel's approximation method
degenerate problem
