最优化LP对偶单纯形法-

对偶单纯形法设是一个基，满足约束的对偶向量称为对偶基本解。若对偶基本解也是可行的，即松弛向量，称为对偶基本可行解。若的所有分量均不为零，称是非退化的。若对应的原始基本解和对偶基本解都是非退化的，称为非退化基。定理(最优条件)若对应的原始基本解和对偶基本解都是可行的，则这两个基本解分别是原始问题和对偶问题的最优解，为最优基。证明：原始单纯形方法分析在算法中，当前基保持原始基本解可行。在该方法中，对偶基本解仅在算法停止时才变成可行的。算法中的检验数就是松弛向量。在任一基，总是互补的。当算法停止时，成为原始最优解，成为对偶可行，因此也是对偶最优的，二者最优值相等。对偶单纯形主要思想原始单纯形：保持原始基本解可行和互补松弛条件可行; 对偶单纯形：保持原始基本解可行和互补松弛条件可行。s.t.注意到：对偶单纯形分析给定基，写出LP的典式，则有：(1) ,最优解，停止。(2) 且，原问题不可行。 (3) ,但。根据算法思想，需要保持对偶可行性：选择这些负数之一为转轴中心，为出基变量。为进基变量第一个对偶基本可行解的求法s.t.第一个对偶基本可行解的求法