| 线性规划的最钝角松弛算法 |
| |
| 引用本文： | 周志娟,潘平奇,陈森发.线性规划的最钝角松弛算法[J].运筹与管理,2009,18(6):7-10. |
| |
| 作者姓名： | 周志娟 潘平奇 陈森发 |
| |
| 作者单位： | 1. 东南大学经济管理学院,江苏,南京,210096
2. 东南大学数学系,江苏,南京,210096 |
| |
| 基金项目： | 国家自然科学基金资助项目，教育部博士点基金资助项目 |
| |
| 摘 要： | 本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题，用原始单纯形算法解之；再添加所略去的约束恢复原问题，若此时全部约束条件均满足则已获得一个基本最优解，否则用对偶单纯形算法继续求解。初步的数值试验表明，新算法比传统两阶段单纯形算法快得多。
|
| 关 键 词： | 线性规划 单纯形法 松弛 最钝角 主元标 |
A Most-obtuse-angle Relaxation Algorithm for Linear Programming |
| |
| ZHOU Zhi-juan,PAN Ping-qi,CHEN Sen-fa.A Most-obtuse-angle Relaxation Algorithm for Linear Programming[J].Operations Research and Management Science,2009,18(6):7-10. |
| |
| Authors: | ZHOU Zhi-juan PAN Ping-qi CHEN Sen-fa |
| |
| Abstract: | 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. |
| |
| Keywords: | linear programming simplex method relaxation problem the most obtuse angle pivoting index |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
