优化理论之对偶单纯形法

对偶单纯行法

• 前期准备
• 对偶单纯形法的基本思想

前期准备

线性规划标准形式 \[ \begin{aligned} \min \; &\sum_{j=1}^n c_jx_j\\ \mathop{s.t.}\; &\sum_{j=1}^n \alpha_{ij}x_j=b_i,\ &i=1,\dotsb,m\\ &x_j\geq 0,\ &j=1,\dotsb,n\\ \end{aligned} \] 用矩阵表示为： \[ \begin{aligned} \min \; &\boldsymbol c^T \boldsymbol x\\ \mathop{s.t.}\; &\boldsymbol A \boldsymbol x = \boldsymbol b\\ &\boldsymbol x \geq \boldsymbol 0\\ \end{aligned}\tag{2.1} \]

对偶单纯形法的基本思想

前面用单纯形法求解问题\((2.1)\)时，往往需要引进人工变量，通过解一阶段问题求初始基本可行解。现在利用对偶性质给出一种不需引进人工变量的求解方法，这就是对偶单纯形法。为介绍这种方法的基本思想，先引入对偶可行的基本解的概念。

对偶可行的基本解:设\(\boldsymbol{x^{(0)}}\)是\((2.1)\)式的一个基本解（不一定是可行解），它对应的基矩阵为\(\boldsymbol{B}\)，若其对应的单纯性乘子\(\boldsymbol{w^T=c^T_B B^{-1}}\)是\((2.1)\)式的对偶问题的可行解，即对所有\(j\)，\(\boldsymbol{w^T p_j}-c_j\leq 0\)成立，则称\(\boldsymbol{x^{(0)}}\)为原问题的‘对偶可行’的基本解。

显然，对偶可行的基本解不一定是原问题的可行解。当对偶可行的基本解是原问题的可行解时，由于判别数均小于或等于零，因此它就是原问题的最优解。即对偶可行的基本解如果是原问题的可行解，那么它是最优解。

对偶单纯形法的基本思想是，从原问题的一个对偶可行的基本解出发，求改进的对偶可行的基本解，当得到的对偶可行的基本解是原问题的可行解时，就达到最优解。那么现在有两个问题

1. 如何先找到一个对偶可行的基本解（解扩充问题）
2. 如何改进这个对偶可行的基本解使得其在原问题可行（改进对偶问题）