求解LP问题的部分基变量算法

一般形式的线性规划问题在找不到基本可行解或对偶问题的基本可行解时,无法用传统的单纯形法或对偶单纯形法求解,即"两看一算"算法.为了解决这个问题,结合两种"两看一算"算法,提出了一种新的算法--部分基变量算法.该算法首先从部分基变量出发,由初等行变换将LP问题转化为准典式,然后由初等行变换找到全部可行基变量,最后用对偶单纯形法得到最优解.对算法的正确性和可行性进行了严格证明,提出算法的实现方式并举例进行了说明,对算法的特点进行了讨论.分析表明所提出的算法是实现线性规划问题求解的较为理想的算法.

Algorithm of partial basic variables to solve LP problem

A new algorithm,algorithm of partial basic variables was brought forward: using the two kinds of algorithm of 'two-view-one-operation',it could solve this problem.The algorithm started with partial basic variables,LP problem was changed to similar typical equation using elementary row operators;then all basic variables can be detected by using elementary row operators;finally,optimization solution could be obtained by using dual simplex method.Correctness and feasibility of the algorithm was proved.Realizing mode of the algorithm was brought forward,and an example was given to explain the realizing mode.Finally it was discussed that this algorithm was a more effective one in algorithms solving LP problem with computer.