摘要
本文研究了线性规划单纯形法和对偶单纯形法主元规则的性质.利用直观的几何方法,结合对偶理论和灵敏度分析,得到了主元规则的特点,针对针对三种最常见的主元规则构造出不同的二维和三维例子,以此说明对每种主元规则都容易构造出其不优的反例,以及迭代次数多于约束个数的例子.所得结果有助于对单纯形法和对偶单纯形法的理解和研究.
In this paper, the properties of pivot rules in simplex method and dual simplex method for linear programming are studied. By using the method of geometrical intuition, and combining it with the dual theory and sensitivity analysis, we analysis the characteristics of pivot rules and construct different 2d and 3d examples for three commonly used pivot rules. It is shown that for each rule the examples can larger than the number of constraints in the examples. The results are helpful to understand and study simplex method and dual simplex method.
出处
《数学杂志》
CSCD
北大核心
2013年第2期373-380,共8页
Journal of Mathematics
关键词
线性规划
单纯形法
对偶单纯形法
主元规则
几何分析
linear programming
simplex method
dual simplex method
pivot rule
geometry analysis
