对偶单纯形法(共4页).doc

精选优质文档-倾情为你奉上6 对偶单纯形法在介绍对偶单纯形法之前，让我们先利用对偶理论来重温一下单纯形法的基本思想，以便给单纯形法一种新的解释。考虑线性规划（LP）和其对偶规划（DP）： (LP) s.t (DP) s.t 我们已经知道，（LP）的单纯形表为 基变量 x1 x2 x n xB B-1 A B-1b f cBT B-1 A cT cBT B1b定理1 设(LP)的任一基本解为x0，它对应于基B，并作(w0 )T= cBT B1。若x0 和w0 分别是(LP)和（DP）的可行解，则x0 和w 0 也分别是(LP)和（DP）的最优解。证明 因w0 是（DP）的可行解，即 (w0 )T A cT 从而有