可行下降视角下退化运输问题的最优性条件  

The Optimality Conditions of Degenerate Transportation Problems from the Perspective of Feasible Descending Direction

作　　者：宋春玲 SONG Chun-ling(School of Mathematics and Big Data,Foshan University,Foshan Guangdong 528000,China)

机构地区：[1]佛山科学技术学院数学与大数据学院

出　　处：《大学数学》2019年第5期5-8,共4页College Mathematics

基　　金：佛山科学技术学院数学与大数据学院高建项目

摘　　要：运输问题是一类特殊的线性规划问题,通常用特殊的单纯形法—运输单纯形法(也叫表上作业法)进行求解,其最优性条件为所有非基变量的检验数大于等于零.针对实际算例中出现的某个非基变量的检验数小于零,却已经达到最优的情况,从可行下降方向的角度进行了探讨.结论表明:一般情况下非基变量的检验数大于等于零仅是运输问题最优解的充分条件;而问题非退化时,该判别条件成为充要条件.Transportation problems belong to a special class of linear programming problems.A special simplex method is devoted to these problems,which is called transportation simplex method or table dispatching method.For the method if the reduced cost for any non-basic variable is nonnegative,then the optimality solution is founded.In this paper,the case that the reduced cost of a non-basic variable is less than zero,but it has reached the optimal value is discussed from the view of feasible descent direction.The result shows: in general,nonnegative reduced cost is a sufficient optimality condition for transportation problems.Only when the transportation problem is non-degenerate,such condition is necessary and sufficient.

关 键 词：运输问题 检验数 退化 单纯形法 基方向 

分 类 号：O29[理学—应用数学]