线性规划的原有松弛-对偶单纯形算法  

A primal relaxation and dual simplex algorithm for linear programming

作　　者：高培旺[1] 

机构地区：[1]闽江学院数学系,福建福州350121

出　　处：《高师理科学刊》2015年第7期10-13,共4页Journal of Science of Teachers＇College and University

基　　金：广西省自然科学基金资助项目(桂科自0728260)

摘　　要：针对线性规划的单纯形算法中出现不可行基的情形,提出了一种原有松弛-对偶单纯形算法.忽略不可行基变量相应的约束构造一个原有可行的松弛子问题,根据最钝角原理作了进一步松弛,用原有单纯形法求解该子问题,然后用对偶单纯形法求解原问题.通过大规模数值试验对这种算法进行计算检验.结果表明,与经典单纯形算法相比,提出的算法简便且具有更高的计算效率.For the situation that an infeasible basis is generated in the simplex pivotal process, proposes a primal relaxation-dual simplex algorithm. The constraints with feasible basic variables are selected to construct a primal feasible relaxation subproblem. On this basis, the subproblem is furtber relaxed in terms of the most-obtuse-angle principle, and solved with the primal simplex algorithm. Then the dual simplex algorithm is applied to find the solution to the original problem. It is found that the algorithm presented is convenient and efficient in computation, compared with the classical primal simplex method by the numerical test on some large-scale examples.

关 键 词：线性规划 基本可行解 单纯形法 对偶单纯形法 松弛 

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