下载文档原格式
16.对偶理论（三）对偶单纯形法⼉童节快乐呀这⼀部分我们考虑原问题是标准型的问题，并且介绍对偶单纯形法。
在上⼀节的强对偶定理的证明中，对标准型问题使⽤单纯形法，定义了对偶变量p为p T=c T B B−1。
然后由原问题最优性条件c T−c T B B−1A≥0T得到了等价表达的对偶可⾏性条件p T A≤c T。
那么我们之前介绍的单纯形法可以看作是在保证原问题可⾏的前提下去寻找对偶可⾏的解。
那么反过来，我们也可以从对偶可⾏的前提下去寻找原问题可⾏的解，这种算法称为对偶算法。
在接下来，将介绍对偶单纯形法。
并且说明这个算法事实上求解了对偶问题，更近⼀步，它是从对偶问题的⼀个基本可⾏解移动到另⼀个。
对偶单纯形法考虑⼀个标准型的线性规划问题，假设矩阵A是⾏满秩（为什么这个假设具有⼀般性，可参考线性规划中的⼏何（三））。
记B为基本矩阵，它包含了矩阵A的m个线性⽆关的列。
考虑下表(与之前介绍的单纯形法中的表⼀样)更详细的有不过，在这⾥不再要求B−1b是⾮负的，那就说明此时的解是⼀个原问题的基本解但不⼀定是可⾏解。
但是，我们要求¯c≥0成⽴，也相当于p T A≤c T成⽴（具体见上⼀节强对偶定理证明）。
这说明现在有了⼀个对偶问题的可⾏解，并且对偶问题的⽬标函数值为p T b=c T B B−1b=c T B x B，这恰好就是上表中的左上⾓元素的相反数。
如果不等式B−1b≥0也成⽴，那么这个解也将是⼀个原问题的可⾏解，并且⽬标函数值相同，这说明我们找到了原问题和对偶问题的最优解。
如果不等式B−1b≥0并不成⽴，那么我们将寻找下⼀个基矩阵。
找到满⾜x B(l)<0的l，考虑表中的第l⾏为pivot ⾏(x B(l)),v1,⋯,v n)，其中v i为B−1A i的第l个元素。
对于满⾜v i<0的所有i（如果存在的话），我们计算⽐率¯c i/|v i|，然后记j为这些⽐率中最⼩的那个的下标（为什么这么选呢，后⾯会说），也就是说v j<0且¯cj|v j|=min{i∣v i<0}¯ci|v i|.称v j为pivot 元素。
