检验数替换价值系数单纯形法的若干讨论  

Discussions on the Simplex Method Based on Replacing Cost Coefficients with Reduced Costs

作　　者：韩伟一[1] 乔立新[1] 刘松崧 HAN Weiyi;QIAO Lixin;LIU Songsong(School of Economics and Management,Harbin Institute of Technology,Harbin 150001,China)

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

出　　处：《运筹与管理》2023年第10期83-87,共5页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(72071055);中央高校科研业务费专项资金项目(AUGA5710050220)。

摘　　要：用检验数替换价值系数来实施单纯形法是新近提出的一种方法,可以有效提高求解线性规划的计算效率,能够使单纯形法的一些性质和特征变得显而易见。本文将给出该方法的三个应用:(1)揭示原模型和对偶模型之间的直接联系,更深入地诠释对偶理论的无界性;(2)提出新的列消除规则,可有效降低单纯形法的计算规模,改进了计算大规模线性规划的列生成方法;(3)可以简化表上作业法之位势方法,使得其计算效率总可提升一倍。因此,这种新方法极大地丰富了单纯形法的理论,而且还可提高单纯形法的计算效率。Linear programming is a basic research field of operations research.Since 1947,numerous algorithms have been proposed,which are mainly divided into three categories:Simplex method,ellipsoid method and interior point algorithm.In view of the inherent warm start technique of simplex algorithm and its natural advantages in solving integer programming,it still has competitive advantages compared to the interior point algorithm.This shows that the improved simplex algorithm still has important theoretical and practical value.At present,simplex method mainly has three variants,namely,the primal simplex algorithm,the dual simplex method and the primal-dual simplex method.Compared with the traditional simplex algorithm,the newly simplex method based on replacing cost coefficients with reduced costs neither changes the computed results nor the number of iterations,but it improves the efficiency of computing reduced costs.In fact,as an improvement of simplex methods,this method doesn’t change existing pivoting rules,which is its prominent feature.It can also make some properties and characteristics of the simplex algorithm become obvious.Furthermore,the new algorithm helps to develop or improve algorithms for some operations research problems,and it can make the computational process simple.In the paper,the new algorithm will further be investigated.Firstly,the new algorithm can not only reveal the inner relationship between primal models and dual models more deeply,but also provide intuitive proof and explanation for the boundedness property of dual theory of linear programming,which is often proved by contradiction.Secondly,a new column elimination rule is proposed.For a variable,if its reduced cost is negative in the k-th simplex tableau and its column vector is non-negative in the r-th simplex tableau,we can eliminate the column of this variable from the model which make the new model with the column deleted have the same optimal solution as the original model.It can effectively reduce the computational scale of line

关 键 词：线性规划 单纯形法 列生成方法 列消除 表上作业法 

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