论线性规划的原始—对偶单纯形算法

从一个既不是原始可行也不是对偶可行的初始基出发,提出了求解线性规划问题的原始—对偶单纯形算法.首先,将等式约束右手边向量取负值的项置为零,用原始单纯形算法求解相应的线性规划问题,如果存在最优解,则是原问题的一个正则解.在原始单纯形迭代过程中,一旦原问题右手边向量取负值的项转化为非负项,则恢复其原来的约束条件参与迭代计算,可使获得的正则解距原问题的最优解(如果存在)更近.接着,从所获得的正则解出发,用对偶单纯形算法求解原问题,直到获得原问题的最优解或无可行解的结论.最后,为了验证该算法的计算性能,通过MATLAB编程在计算机上进行大规模数值试验,结果表明,与经典单纯形算法相比,该算法在大部分问题上使用更少的迭代次数和执行时间,具有更高的计算效率.

A Primai-dual Simplex Algorithm for Linear Programming