对偶问题（必考点），要会把原问题的对偶问题写出来，知道对偶定理，会对偶单纯形法。 每一个线性规划问题，都有一个被称为对偶的线性规划问题与它相对应，二者可以看做是对同一个问题从不同的角度所进行的分析与研究。

我的理解是，只有不等式约束就是对称形式的对偶问题；有等式约束的（比如标准型）就是非对称形式的对偶问题。

{ m i n   f = c T x s . t .   A x ≥ b ,           x ≥ 0 (1) \begin{cases}min \,f=c^Tx \\ s.t.\,Ax \geq b, \\\,\,\,\,\,\,\,\,\,x \geq0 \end{cases} \tag{1} ⎩⎪⎨⎪⎧​minf=cTxs.t.Ax≥b,x≥0​(1) 问题(1)的对偶线性规划问题定义为： { m a x   f = b T λ s . t .   λ T A ≤ c T ,           λ ≥ 0 (2) \begin{cases}max \,f=b^T \lambda \\ s.t.\, \lambda^TA \leq c^T, \\ \,\,\,\,\,\,\,\,\,\lambda \geq0 \end{cases} \tag{2} ⎩⎪⎨⎪⎧​maxf=bTλs.t.λTA≤cT,λ≥0​(2) 从原始问题（1）构成对偶问题（2）的方法是（对称形式）：

考虑标准形式的线性规划问题： { m i n   f = c T x s . t .   A x = b ,           x ≥ 0 (3) \begin{cases}min \,f=c^Tx \\ s.t.\,Ax = b, \\\,\,\,\,\,\,\,\,\,x \geq0 \end{cases} \tag{3} ⎩⎪⎨⎪⎧​minf=cTxs.t.Ax=b,x≥0​(3) 其可以看作一种特殊的对称形式： { m i n   f = c T x s . t .   A x ≥ b ,        − A x ≥ b ,           x ≥ 0 ( 3 ′ ) \begin{cases}min \,f=c^Tx \\ s.t.\,Ax \geq b, \\\,\,\,\,\,\,-Ax \geq b,\\\,\,\,\,\,\,\,\,\,x \geq0 \end{cases} \tag{$3'$} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​minf=cTxs.t.Ax≥b,−Ax≥b,x≥0​(3′) 经过推导，（3）的最终对偶线性规划问题如下： { m a x   f = w T b s . t .   w T A ≤ c T (4) \begin{cases}max \,f=w^Tb \\ s.t.\,w^TA \leq c^T\end{cases} \tag{4} {maxf=wTbs.t.wTA≤cT​(4)（注意这里的变矢量 w w w已经是自由变量了）。

综合上面的，给出对偶的一般规则 从上面可以看到，对偶问题约束条件的符号取决于原问题变矢量符号，而对偶问题的变矢量符号取决于原问题约束条件的符号。 eg: 求线性规划的对偶问题： { m i n   f = c T x s . t .   A x = b ,           x ≥ a ( 5 ) \begin{cases}min \,f=c^Tx \\ s.t.\,Ax =b,\\\,\,\,\,\,\,\,\,\,x \geq a \end{cases} \tag{$5$} ⎩⎪⎨⎪⎧​minf=cTxs.t.Ax=b,x≥a​(5) 其中 a ≥ 0 a \geq 0 a≥0。 解：问题（5）的标准形如下： { m i n   f = c T x s . t .   A x = b ,           x − x n + 1 = a           x , x n + 1 ≥ 0 ( 5 ′ ) \begin{cases}min \,f=c^Tx \\ s.t.\,Ax =b,\\\,\,\,\,\,\,\,\,\,x-x_{n+1} = a \\\,\,\,\,\,\,\,\,\,x,x_{n+1}\geq 0\end{cases} \tag{$5'$} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​minf=cTxs.t.Ax=b,x−xn+1​=ax,xn+1​≥0​(5′)再化的更好看点： { m i n   f = c T x s . t .   [ A 0 1 − 1 ] [ x x n + 1 ] = [ b a ] ,           [ x x n + 1 ] ≥ 0 ( 5 ′ ′ ) \begin{cases}min \,f=c^Tx \\ s.t.\,\begin{bmatrix} A & 0 \\ 1&-1\end{bmatrix} \begin{bmatrix} x \\ x_{n+1}\end{bmatrix} =\begin{bmatrix} b \\ a\end{bmatrix},\\\,\,\,\,\,\,\,\,\, \begin{bmatrix} x \\ x_{n+1}\end{bmatrix} \geq 0\end{cases} \tag{$5''$} ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​minf=cTxs.t.[A1​0−1​][xxn+1​​]=[ba​],[xxn+1​​]≥0​(5′′) 所以其对偶问题为： { m a x   f = [ w 1 T , w 2 T ] [ b a ] = w 1 T b + w 2 T a s . t .   [ w 1 T , w 2 T ] [ A 0 1 − 1 ] ≤ [ c T , 0 ] ,           [ w 1 w 2 ] 无 限 制 ( 5 ′ ′ ′ ) \begin{cases}max \,f =[w_1^T,w^T_2]\begin{bmatrix} b \\ a\end{bmatrix}=w_1^Tb+w_2^Ta \\ s.t.\,[w_1^T,w^T_2]\begin{bmatrix} A & 0 \\ 1&-1\end{bmatrix} \leq [c^T,0],\\\,\,\,\,\,\,\,\,\,\begin{bmatrix} w_1 \\w_2\end{bmatrix} 无限制\end{cases} \tag{$5'''$} ⎩⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎧​maxf=[w1T​,w2T​][ba​]=w1T​b+w2T​as.t.[w1T​,w2T​][A1​0−1​]≤[cT,0],[w1​w2​​]无限制​(5′′′)进而展开得： { m a x   f = w 1 T b + w 2 T a s . t .   w 1 T A + w 2 T ≤ c T ,           w 2 T ≥ 0           w 1 无 限 制 ( 5 ′ ′ ′ ′ ) \begin{cases}max \,f =w_1^Tb+w_2^Ta \\ s.t.\,w_1^TA+w^T_2 \leq c^T,\\\,\,\,\,\,\,\,\,\,w_2^T\geq0 \\\,\,\,\,\,\,\,\,\,w_1 无限制\end{cases} \tag{$5''''$} ⎩⎪⎪⎪⎨⎪⎪⎪⎧​maxf=w1T​b+w2T​as.t.w1T​A+w2T​≤cT,w2T​≥0w1​无限制​(5′′′′)over~（感觉还是用一般规则直接写快呀！）

若 x x x和 w w w分别是原问题（3）和对偶问题（4）的可行解，则 c T x ≥ w T b c^Tx \geq w^Tb cTx≥wTb。 证明：(就利用是可行解证明就好啦~） w T b = w T ( A x ) = ( w T A ) x ≤ c T x w^Tb=w^T(Ax)=(w^TA)x\leq c^Tx wTb=wT(Ax)=(wTA)x≤cTx这个引理说明原问题的任一可行解所对应的目标函数值都是对偶问题目标函数值的上界，或者说对偶问题的任一可行解对应的目标函数值是原问题目标函数值的下界。那原问题要最小，对偶问题要最大，它们相等的时候不是互相达到了吗！！！

设 x ∗ x^* x∗和 w ∗ w^* w∗分别是原问题（3）和对偶问题（4）的可行解，且 c T x = w T b c^Tx = w^Tb cTx=wTb，则 x ∗ x^* x∗和 w ∗ w^* w∗分别是原问题（3）和对偶问题（4）的最优解。（证明的话，利用引理1反正就好了）

若（3）或（4）二者有一个有有限的最优解，则另一个也有有限的最优解，而且二者的（最优）目标函数数值相同。若任一个问题的目标函数值无界，则另一个问题没有可行解。

设 x , w x,w x,w分别为原问题（3）和对偶问题（4）的可行解，则 x , w x,w x,w分别是（3）和（4）的最优解的充要条件是： ( w T A − c T ) x = 0 (6) (w^TA-c^T)x=0 \tag{6} (wTA−cT)x=0(6)或者表述为： (1) 如果 x j > 0 x_j >0 xj​>0，就有 w T p j = c j w^Tp_j=c_j wTpj​=cj​ (2) 如果 w T p j < c j w^Tp_j0 xj​>0，就有 λ T p j = c j \lambda^Tp_j=c_j λTpj​=cj​ (2) 如果 λ T p j < c j \lambda^Tp_j0 λi​>0，就有 a i x = b i a_ix=b_i ai​x=bi​ (4) 如果 a i x > b i a_ix>b_i ai​x>bi​，就有 λ i = 0 \lambda_i=0 λi​=0 其中 p j p_j pj​是 A A A的第 j j j列， a i a_i ai​是 A A A的第 i i i行。 具体的证明这里不再给出，可详见陈宝林先生的《最优化理论与算法》P129。

下面重点来了哦~

对偶单纯形法是什么呢？ 对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。 没错，还是从原来的单纯形表出发，换一种方法求解原问题的最优解咯~ 还记得当线性规划存在有限最优解，上节单纯形法停止的条件吗？没错，所有的检验数 c B T B − 1 N − c N ≤ 0 → c B T B − 1 A − c ≤ 0 → w T A ≤ A c_B^TB^{-1}N-c_N \leq 0 \rightarrow c_B^TB^{-1}A - c \leq0 \rightarrow w^TA \leq A cBT​B−1N−cN​≤0→cBT​B−1A−c≤0→wTA≤A，其中 w T = c T B − 1 w^T=c^TB^{-1} wT=cTB−1为单纯形乘子，同时我们也看到她是对偶问题的一个可行解。 进一步来看 w T b = c B B − 1 b = c B ( B − 1 b ) = c B x b w^Tb=c_BB^{-1}b=c_B(B^{-1}b)=c_Bx_b wTb=cB​B−1b=cB​(B−1b)=cB​xb​即原问题的目标函数值与对偶问题的函数值相同，由引理1的推论知， x x x和 w w w为原问题和对偶问题的最优解，B是两问题的最优基。

定理： B是线性规划的最优基的充要条件是，B是 可行基，同时也是对偶可行基。

从原始问题（3）的一个对偶可行的基本解开始，逐次进行迭代，在保持对偶可行性的条件下，逐步使原始问题（3）的基本解的不可行性消失（即使 x = b ‾ = B − 1 b ≥ 0 ） x=\overline{b}=B^{-1}b \geq 0） x=b=B−1b≥0），直到获得（3）的一个基本可行解为止，而它即为原始问题的最优解。 单纯形法的求解过程就是： 在保持原始可行的前提下（ b ‾ \overline{b} b列保持≥0），通过逐步迭代实现对偶可行（检验数行≤0）。 对偶单纯形法思想： 换个角度考虑LP求解过程： 保持对偶可行的前提下(检验数行保持≤0), 逐步迭代实现原始可行( b ‾ \overline{b} b列≥0)。

(1) 检验数全部 ≤ 0 \leq0 ≤0 (2) 解答列至少一个 b ‾ < 0 \overline{b}< 0 byrj​zj​−cj​​∣yrj​