我们可以先通过一个常识来理解“对偶”的含义和特征：

矩形中，周长一定，正方形的面积最大；面积一定，正方形的周长最小。

在许多课本中，都用如下的例子来引出对偶理论：

​ 企业A拥有m种资源（有m 个约束），可以消耗资源生产n 种产品（有n 个变量），目标是最大化总收入；那么对偶问题就是，企业B想要收购这些资源，需要确定m 种资源的报价（有m 个变量），目标是最小化总成本，但企业A只有在卖资源的收益不低于卖产品的时候才会同意卖资源（n个约束）。

而从数学角度，对偶问题可以被理解为寻找原问题目标函数上界或下界的问题。

原问题约束多、变量少时，求解对偶问题能够降低计算时间 使用单纯形法时，如果原问题约束多变量少，转换成对偶问题，就是约束少变量多。回顾单纯形法的原理，约束的减少能够有效降低计算时间。

帮助证明原问题无解 类似“证明无罪比证明有罪更难”，要证明原问题有解，只需要找出一个满足约束的点，但是想证明原问题无解，总不能遍历所有的点来证明吧？而对偶问题的出现为证明原问题无解提供了思路。

便于进行敏感度分析 除了得到最优解，我们可能还关注"如果某些已知条件发生变化，对最优解的影响程度如何"，这就是敏感度分析。对偶问题和敏感性分析息息相关。一是增加敏感度分析的直观程度（例如，对偶问题的最优解就是原问题约束的影子价格），二是在改变某些条件导致原问题无可行解时，可以借助仍然有可行解的对偶问题来分析。

若原问题为   L P 1 ~LP_1  LP1​ m a x   z = C X s . t . { A X ≤ b X ≥ 0 \begin{aligned} max~z=CX\\s.t. \left\{\begin{aligned} AX\le b\\X\ge0 \end{aligned}\right. \end{aligned} max z=CXs.t.{AX≤bX≥0​​ 则其对偶问题定义为   L P 2 ~LP_2  LP2​ m i n   w = Y T b s . t . { A T Y ≥ C T Y ≥ 0 \begin{aligned} min~w=Y^Tb\\s.t. \left\{\begin{aligned} &A^TY\ge C^T\\&Y\ge0 \end{aligned}\right. \end{aligned} min w=YTbs.t.{​ATY≥CTY≥0​​ 若原问题并非   L P 1   ~LP_1~  LP1​ 形式，则我们可以首先将其转化为   L P 1   ~LP_1~  LP1​ 形式，然后按照前面定义即可计算出其对偶问题。

∑ i = 1 n a i j x j = b i    ⇒    { ∑ i = 1 n a i j x j ≤ b i ∑ i = 1 n − a i j x j ≤ − b i ∑ i = 1 n a i j x j ≥ b i    ⇒    ∑ i = 1 n − a i j x j ≤ − b i \sum_{i=1}^{n} a_{ij}x_j= b_i~~\Rightarrow~~\left\{\begin{aligned}\sum_{i=1}^{n} a_{ij}x_j\le b_i\\\sum_{i=1}^{n} -a_{ij}x_j\le -b_i\end{aligned}\right.\\ \displaystyle\sum_{i=1}^{n} a_{ij}x_j\ge b_i~~\Rightarrow~~\sum_{i=1}^{n} -a_{ij}x_j\le -b_i i=1∑n​aij​xj​=bi​  ⇒  ⎩⎪⎪⎪⎪⎨⎪⎪⎪⎪⎧​i=1∑n​aij​xj​≤bi​i=1∑n​−aij​xj​≤−bi​​i=1∑n​aij​xj​≥bi​  ⇒  i=1∑n​−aij​xj​≤−bi​

也可以用如下方法进行变换：

举个例子:

原问题 m i n   z =         7 x 1 + 4 x 2 − 3 x 3 s . t . = { − 4 x 1 + 2 x 2 − 6 x 3 ≤ 24 − 3 x 1 − 6 x 2 − 4 x 3 ≥ 15              5 x 2 +    x 3 = 30 x 1 ≤ 0 , x 2 无 约 束 , x 3 ≥ 0 \begin{aligned} min~z=&~~~~~~~7x_1+4x_2-3x_3\\ s.t.=&\left\{ \begin{matrix} -4x_1+2x_2-6x_3\le24\\ -3x_1-6x_2-4x_3\ge15\\ ~~ ~~ ~~ ~~ ~~ ~~5x_2+~~x_3=30\\ x_1\le0,x_2无约束,x_3\ge0 \end{matrix} \right. \end{aligned} min z=s.t.=​       7x1​+4x2​−3x3​⎩⎪⎪⎨⎪⎪⎧​−4x1​+2x2​−6x3​≤24−3x1​−6x2​−4x3​≥15            5x2​+  x3​=30x1​≤0,x2​无约束,x3​≥0​​ 首先把   C   ~C~  C 和   b   ~b~  b 互换， A   A~ A 转置 m a x   w =       24       15     30 s . t . { − 4 − 3 0 7 2 − 6 5 4 − 6 − 4 1 − 3 \begin{aligned} max~w=&~~~~~24~~~~~15~~~30\\ s.t.&\left\{ \begin{matrix} -4&-3&0&&7\\ 2&-6&5&&4\\ -6&-4&1&&-3 \end{matrix} \right. \end{aligned} max w=s.t.​     24     15   30⎩⎨⎧​−42−6​−3−6−4​051​​74−3​​ 因为是最小化转为最大化问题，所以约束条件和原问题变量的符号相反（也就是表格中从右往左），变量和原问题约束条件符号相同： m a x   w =         24 y 1 + 15 y 2 + 30 y 3 s . t . { − 4 y 1 − 3 y 2          ≥ 7 2 y 1 − 6 y 2 + 5 y 3 = 4 − 6 y 1 − 4 y 2 + y 3 ≤ 3 y 1 ≤ 0 , y 2 ≥ 0 , y 3 无 约 束 \begin{aligned} max~w=&~~~~~~~24y_1+15y_2+30y_3\\ s.t.&\left\{ \begin{matrix} -4y_1-3y_2~~~~~~~~\ge7\\ 2y_1-6y_2+5y_3=4\\ -6y_1-4y_2+y_3\le3\\ y_1\le0,y_2\ge0,y_3无约束 \end{matrix} \right. \end{aligned} max w=s.t.​       24y1​+15y2​+30y3​⎩⎪⎪⎨⎪⎪⎧​−4y1​−3y2​        ≥72y1​−6y2​+5y3​=4−6y1​−4y2​+y3​≤3y1​≤0,y2​≥0,y3​无约束​​ 如果原问题改为最大化，那么相应的对偶问题是： m i n   w =         24 y 1 + 15 y 2 + 30 y 3 s . t . { − 4 y 1 − 3 y 2          ≤ 7 2 y 1 − 6 y 2 + 5 y 3 = 4 − 6 y 1 − 4 y 2 + y 3 ≥ 3 y 1 ≥ 0 , y 2 ≤ 0 , y 3 无 约 束 \begin{aligned} min~w=&~~~~~~~24y_1+15y_2+30y_3\\ s.t.&\left\{ \begin{matrix} -4y_1-3y_2~~~~~~~~\le7\\ 2y_1-6y_2+5y_3=4\\ -6y_1-4y_2+y_3\ge3\\ y_1\ge0,y_2\le0,y_3无约束 \end{matrix} \right. \end{aligned} min w=s.t.​       24y1​+15y2​+30y3​⎩⎪⎪⎨⎪⎪⎧​−4y1​−3y2​        ≤72y1​−6y2​+5y3​=4−6y1​−4y2​+y3​≥3y1​≥0,y2​≤0,y3​无约束​​

1.弱对偶性：如果 X X X是原问题的可行解， Y Y Y是对偶问题的可行解，则   C X ≤ Y T b ~CX\le Y^Tb  CX≤YTb

证明：（注意这些矩阵乘积都是标量） Y T b ≥ Y T A X = ( Y T A X ) T = X T A T Y ≥ X T C T = C X Y^Tb\ge Y^TAX=(Y^TAX)^T=X^TA^TY\ge X^TC^T=CX YTb≥YTAX=(YTAX)T=XTATY≥XTCT=CX

推论：

最优性：如果 X X X是原问题的可行解， Y Y Y是对偶问题的可行解, 且   C X = Y T b ~CX=Y^Tb  CX=YTb，则 X X X和 Y Y Y分别为原问题和对偶问题的最优解.

无界性：如果原问题(对偶问题) 具有无界解, 则其对偶问题(原问题) 无可行解.

2.强对偶性：如果原问题有最优解，则其对偶问题也一定具有最优解，且   m a x   z = m i n   w ~max~z=min~w  max z=min w

证明：设 B B B为原问题标准形式的可行解基，且其基解为最优解，则由最优性条件应有检验数全部小于零：

  − C B B − 1 ≤ 0 , θ = C − C B B − 1 A ≤ 0 ~-C_BB^{-1}\le0, \theta=C-C_BB^{-1}A\le0  −CB​B−1≤0,θ=C−CB​B−1A≤0，

从而可得

  A T B − T C B T ≥ C T , B − T C B T ≥ 0 ~A^TB^{-T}C_B^T\ge C^T,B^{-T}C_B^T\ge0  ATB−TCBT​≥CT,B−TCBT​≥0，

所以   B T C B T ~B^TC_B^T  BTCBT​是对偶问题的一个可行解，且

( B − T C B T ) T b = C B B − 1 b = m a x   z (B^{-T}C_B^T)^Tb=C_BB^{-1}b=max~z (B−TCBT​)Tb=CB​B−1b=max z

由最优性可知， B − T C B T B^{-T}C_B^T B−TCBT​为对偶问题的最优解，且   m a x   z = m i n   w ~max~z=min~w  max z=min w。

3.互补松弛性：在线性规划问题的最优解中，如果某一约束条件的对偶变量值非零，则该约束条件严格取等，反之，如果约束条件取不等式，则对应的对偶变量一定为0，可以表示为   Y T ( b − A X ) = 0 ~Y^T(b-AX)=0  YT(b−AX)=0。

证明：由强对偶性可知   C X = Y T b ~CX=Y^Tb  CX=YTb，又因为   C X = X T C T ≤ X T A T Y = Y T A X ≤ Y T b ~CX=X^TC^T\le X^TA^TY=Y^TAX\le Y^Tb  CX=XTCT≤XTATY=YTAX≤YTb

可得 Y T A X = Y b Y^TAX=Y^b YTAX=Yb，于是   Y T ( b − A X ) = 0 ~Y^T(b-AX)=0  YT(b−AX)=0

4.基解互补性 原问题及其对偶问题之间存在一对互补的基解，其中原问题的松弛变量对应对偶问题的变量对偶问题的剩余变量对应原问题的变量.这些互相对应的变量如果在一个问题的解中是基变量则在另一个问题的解中是非基变量；将这对互补的集解分别带入原问题和对偶问题的目标函数中有   z = w   ~z=w~  z=w 

我们考查如下对偶问题： m a x   z = C X m i n   w = Y T b P { A X ≤ b X ≥ 0 D { A T Y ≤ C T Y ≥ 0 \begin{aligned} &max~z=CX&&min~w=Y^Tb\\ &P\left\{\begin{aligned} &AX\le b\\&X\ge0 \end{aligned}\right. &&D\left\{\begin{aligned} &A^TY\le C^T\\&Y\ge0 \end{aligned}\right. \end{aligned} ​max z=CXP{​AX≤bX≥0​​​min w=YTbD{​ATY≤CTY≥0​​ ​ 定义：若 P P P 的某个约束条件的右端项常数 b i b_i bi​ (第 i 种资源的拥有量）增加一个单位时，所引起目标函数最优值 z ∗ z^* z∗ 的改变量称为第 i i i 种资源的影子价格，其值等于 D D D 问题中对偶变量 y i y_i yi​

假设 ( x 1 ∗ , x 2 ∗ , … , x n ∗ ) (x_1^*,x_2^*,\dots,x_n^*) (x1∗​,x2∗​,…,xn∗​) 和 ( y 1 ∗ , y 2 ∗ , … , y n ∗ ) (y_1^*,y_2^*,\dots,y_n^*) (y1∗​,y2∗​,…,yn∗​) 分别为原问题和对偶问题的最优解，由对偶问题的基本性质有 z ∗ = ∑ c j x j ∗ = ∑ b i y i ∗ z^*=\sum c_jx_j^*=\sum b_iy_i^* z∗=∑cj​xj∗​=∑bi​yi∗​，因为某个 Δ b i = 1 \Delta b_i=1 Δbi​=1，所以最优解的的变化 Δ z ∗ = y i ∗ \Delta z^*=y_i^* Δz∗=yi∗​，也就是对偶变量 y i y_i yi​就是第 i i i 个产品的影子价格 ∂ z ∗ ∂ b i = y i ∗ \displaystyle\frac{\partial z^*}{\partial b_i}=y_i^* ∂bi​∂z∗​=yi∗​

影子价格是在资源最优利用条件下对单位资源的估价，这种估价不是资源实际的市场价格。影子价格是一种机会成本。

我们假设某种资源的单位市场价是   m i ~m_i  mi​，则

当产值小于隐含成本时，即 θ j < 0 \theta_jarj​θj​​∣∣∣∣​ arj​