线性规划的最钝角松弛算法  

A Most-obtuse-angle Relaxation Algorithm for Linear Programming

作　　者：周志娟[1] 潘平奇[2] 陈森发[1] 

机构地区：[1]东南大学经济管理学院,江苏南京210096 [2]东南大学数学系,江苏南京210096

出　　处：《运筹与管理》2009年第6期7-10,共4页Operations Research and Management Science

基　　金：国家自然科学基金资助项目(10871043);教育部博士点基金资助项目(20060286005)

摘　　要：本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。Based on the most-obtuse-angle principle, a relaxation algorithm is proposed in this paper to solve linear programming problems. Some constraints are selected, and omitted according to the most-obtuse-angle principle. The smaller problem is solved with the simplex method. Then the omitted constraints are added to restore the original problem. If all the constraints are satisfied, then a basic optimal solution is reached. In the other case, the dual simplex method is used to obtain the basic optimal solution. Our preliminary computational tests demonstrate that the new algorithm is much faster than the conventional two-phase simplex algorithm.

关 键 词：线性规划 单纯形法 松弛 最钝角 主元标 

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