【管理运筹学】运筹学“背诵手册”（二）

用矩阵形式表示原问题和对偶问题： max ⁡ z = C X s . t . { A X ≤ b X ≥ 0 \max z=\pmb{CX}\\ s.t.\begin{cases} \pmb{AX\leq b} \\ \pmb{X}\geq\pmb{0} \end{cases} maxz=CXs.t.{AX≤bX≥0​ 其中 C = ( c 1 , c 2 , ⋯   , c n ) , X = ( x 1 , x 2 , ⋯   , x n ) T , A m × n , b = ( b 1 , b 2 , ⋯   , b m ) T \pmb{C}=(c_1,c_2,\cdots,c_n),\pmb{X}=(x_1,x_2,\cdots,x_n)^T,\pmb{A}_{m\times n},\pmb{b}=(b_1,b_2,\cdots,b_m)^T C=(c1​,c2​,⋯,cn​),X=(x1​,x2​,⋯,xn​)T,Am×n​,b=(b1​,b2​,⋯,bm​)T 。

其对偶问题为： min ⁡ w = Y b s . t . { A T Y T ≥ C T Y T ≥ 0 \min w=\pmb{Yb}\\ s.t.\begin{cases} \pmb{A^TY^T\geq C^T} \\ \pmb{Y^T}\geq\pmb{0} \end{cases} minw=Ybs.t.{ATYT≥CTYT≥0​ 其中 Y = ( y 1 , y 2 , ⋯   , y m ) \pmb{Y}=(y_1,y_2,\cdots,y_m) Y=(y1​,y2​,⋯,ym​) 。

对偶理论的几个定理：

弱对偶定理： 若互为对偶问题的线性规划问题分别有可行解 X , Y \pmb{X},\pmb{Y} X,Y ，则原问题的目标函数值不大于对偶问题的目标函数值。

有推论：若原问题可行，则其目标函数无界的充要条件为对偶问题没有可行解。

最优准则性定理： 当 C X = Y b \pmb{CX=Yb} CX=Yb 时，两个问题均达到最优。

对偶定理： 若原问题有最优解，则对偶问题也有最优解，且目标函数值相同。

互补松弛定理： 若 X ‾ , Y ‾ \pmb{\overline{X},\overline{Y}} X,Y 分别为原问题和对偶问题的可行解，那么当且仅当 X ‾ , Y ‾ \pmb{\overline{X},\overline{Y}} X,Y 为最优解时，有 Y ‾ X s = 0 , X ‾ Y s = 0 \pmb{\overline{Y}X_s=0,\overline{X}Y_s=0} YXs​=0,XYs​=0 ，其中 X s , Y s \pmb{X_s,Y_s} Xs​,Ys​ 分别为对应线性规划问题添加的松弛变量所构成的向量。

当原问题的最优解 X \pmb{X} X 非零时，对偶问题添加的松弛变量一定为 0 ，也就是说对偶问题的约束条件是等式约束。同理，对偶问题的最优解非零时，原问题的约束条件就取严格等式。

需要注意的情况是，当原问题某个最优解取值为 0 时，不能说明对偶问题对应的约束就是等式，因为其是非等式时，即 Y s ≠ 0 Y_s\ne0 Ys​=0 ，还是有 X Y s = 0 XY_s=0 XYs​=0 。

对偶问题的经济解释 —— 影子价格。对偶问题的最优解所代表的就是单位资源对企业的价值，也就是资源所对应的影子价格。一般用增加一个单位该资源来描述，即若某资源的影子价格为 k k k ，若增加一个单位该资源，最优目标函数值增加 k k k 。不过，不能说增加 5 个单位，目标函数就增加 5 k 5k 5k ，因为，如果加了超过 1 个单位资源的话，有可能最优解就改变了。

对偶理论一个应用就是，原问题最优单纯形表中，松弛变量所对应的 z j z_j zj​ 就是对偶问题的最优解，即影子价格。

若 B \pmb{B} B 是 A \pmb{A} A 中的一个基，当 B \pmb{B} B 对应的基解是可行解时，称 B \pmb{B} B 为可行基，当 B \pmb{B} B 对应的基本可行解为最优解时，称 B \pmb{B} B 为最优基。若 C B − 1 \pmb{CB}^{-1} CB−1 是对偶问题的可行解，则称 B \pmb{B} B 为对偶可行基。

B \pmb{B} B 是线性规划问题的最优基的充要条件是， B \pmb{B} B 是可行基，同时是对偶可行基。在单纯形法中，我们从一个初始基可行解出发（假设还未达到最优解），它保证了原问题可行，却并未保证对偶问题可行。对偶问题可行需要 Y \pmb{Y} Y 非负，对应于原问题单纯形表中就是非基变量的 z j ≥ 0 z_j\geq0 zj​≥0 ，那检验数就应该是小于等于 0 的。因此，只有原问题达到了最优解，即检验数都小于等于 0 ，对偶问题才是可行的。

因此，我们可以对称考虑，就是，先让对偶问题可行（原问题就最优），通过不断迭代，使得对偶问题最优（原问题就可行）。对偶单纯形法应用的前提便是，需要初始单纯形表中的检验数行全部非正（保证了原问题最优，也就是对偶问题可行）和基变量取值有负值（原问题不可行）。

对偶单纯形法的步骤为：