Analysis on history-based pivot rules of linear programming

单纯形法是求解线性规划的多种方法之一。单纯形法是丹齐格在1947年提出的。是否存在在多项式时间内求解线性规划的旋转算法是众所周知的。这个问题已经考虑了很多年了。在本研究中，我们重点研究了Zadeh提出的基于历史的旋转规则。(1)构造了一种描述旋转算法行为的Lp有向图的枚举方法；(2)分析了Lp有向图上基于历史的旋转规则；(3)验证了关于应用旋转规则的数量的一些猜想

The simplex method is one of various approaches to solve a linear program. The simplex method was developed by Dantzig in 1947. It is well known whether there exist pivoting algorithms to solve a linear program in polynomial time. This problem has been considered for years. In this research, we focused on history-based pivoting rules developed by Zadeh to attack the open problem.(1) Construction of a method to enumerate LP digraphs, which describes a behavior of pivoting algorithms; (2) Analysis of history-based pivoting rules on the LP digraphs; (3) Verification of some conjectures on the number of applying pivoting rules