目前，在研究过程中，需要通过求对偶来提高模型算法的求解效率，于是要学生对于建立的模型转化为对偶问题。但总感觉不得要领，于是就想着对研究过程中存在的线性规划求解对偶问题的基本过程进行记录，以便以后学生学习。

线性规划及其对偶问题

任何一个线性规划问题都存在与之伴随的另一个线性规划问题，它们组成一对互为对偶的线性规划问题。比如，已知资源，求最大利润生产计划的线性规划问题，其对应的对偶问题，可以是直接将原材料或者设备出租获取利润，即资源价格（或影子价格，Shadow Price），具体如下述例子所示：

生产计划问题及其对偶

假设某公司计划生成A、B两种产品，生产所需要的原材料、设备工时以及利润如表1所示，求出如何安排生产才能获得最大利润。
表1 某公司产品、生产资源、利润表

显然，该问题是一个已知资源，求最大利润的生产计划问题。假设两种产品的计划产量分别为$x_{1}$和$x_{2}$，那么根据表1可以建立如下数学模型：

$$ \begin{equation} \left\{ \begin{aligned} \max ~& \Pi_{1} = 2 x_{1}+ 3 x_{2} \\ S.t. ~& 2 x_{1} + 2 x_{2} \le 12 \\ ~& x_{1} + 2 x_{2} \le 8 \\ ~& 4 x_{1} \le 16 \\ ~& 4 x_{2} \le 12 \\ ~& x_{1},~x_{2} \ge 0 \\ \end{aligned} \right. \end{equation} $$

对于该问题的对偶问题，可以假设该公司是从另外一个角度思考这个问题的，即直接出售这些原材料或者将设备出租，但是需要注意的是：（i）如果公司直接出售原材料和出租设备，应该使得产生的利润不会降低，即不会低于生产产品的利润；（ii）为了确保资源可以被出售或者出租，资源的价格是越低越好；（iii）资源价格不能为负数。为此，对于上述设备和原材料，假设四种资源的单位利润分别为：$y_{1}$，$y_{2}$，$y_{3}$，$y_{4}$，则可以得到如下数学模型：

$$ \begin{equation} \left\{ \begin{aligned} \min~ & \Pi_{2} = 12 y_{1} + 8 y_{2} + 16 y_{3} + 12 y_{4} \\ S.t.~ & 2 y_{1} + y_{2} + 4 y_{3} + 0 y_{4} \ge 2 \\ ~ & 2 y_{1} + 2 y_{2} + 0 y_{3} + 4 y_{4} \ge 3 \\ ~ & y_{1},y_{2},y_{3},y_{4} \ge 0 \\ \end{aligned} \right. \end{equation} $$

此时，我们称模型（1）和模型（2）互为对偶模型。

线性规划对偶问题的一般写法

为便于描述，我们将上述模型转换过程写成一般形式,由于原线性规划模型的标准形式如下：

$$ \begin{equation} \left\{ \begin{aligned} \max ~ & \mathbf{Z} = \mathbf{C}^{T} \mathbf{X} \\ S.t. ~ & \mathbf{A} \mathbf{X} \le b \\ ~ & \mathbf{X} \ge 0 \\ \end{aligned} \right. \end{equation} $$

对应的对偶问题模型可以写成如下：

$$ \begin{equation} \left\{ \begin{aligned} \min ~ & \mathbf{W} = b^{T} \mathbf{Y} \\ S.t. ~ & \mathbf{A}^{T} \mathbf{Y} \ge \mathcal{C} \\ ~ & \mathbf{Y} \ge 0 \\ \end{aligned} \right. \end{equation} $$

线性规划与对偶问题的对应关系

根据上述一般形式，可以对线性规划及其对偶问题的对应关系进行如下总结，具体如表2所示。
表2 线性规划及其对偶问题转换对应关系表

线性规划和对偶问题转换练习

练习题~1

假设线性规划原问题为如下表达式：

$$ \begin{equation} \left\{ \begin{aligned} \max ~ & \Pi_{1} = 3 x_{1} + 5 x_{2} \\ S.t. ~ & x_{1} \le 4 \\ ~ & 2 x_{2} \le 12 \\ ~ & 3 x_{1} + 2 x_{2} \le 18 \\ ~ & x_{1} \ge 0,~x_{2} \ge 0 \\ \end{aligned} \right. \end{equation} $$

则根据上述对应关系，一步一步进行转化：
第一步 ：线性规划原问题目标函数是求最大值（$max$），则对偶问题目标函数为求最小值（$min$）;
第二步 ：线性规划原问题有2个变量，$x_{1}$和$x_{2}$，则对偶问题对应有2个约束条件，且由于原问题变量都是大于等于0，因此，对偶约束条件也是大于等于；
第三步 ：线性规划原问题目标函数中变量的系数分别为3和5，则对偶问题约束条件右边的常数项为3和5；
第四步 ：线性规划原问题约束条件中有3个约束条件，则对偶问题对应3个对偶变量；
第五步 ：线性规划原问题约束条件右边常数项分别是4，12，18，则对偶问题目标函数中变量的系数分别为4,12,18;
第六步 ：线性规划原问题约束条件左边的系数是矩阵[1,0;0,2;3,2]，则对偶问题约束条件左边的系数是该矩阵的转置，即[1,0,3;0,2,2]；
第七步 ：线性规划原问题约束条件为小于等于，则对偶问题变量分别为大于等于0.

根据上述七个步骤，便可以写出其对偶问题数学模型：

$$ \begin{equation} \left\{ \begin{aligned} \min ~ & \Pi_{2} = 4 y_{1} + 12 y_{2} + 18 y_{3} \\ S.t. ~ & 1 y_{1} + 0 y_{2} + 3 y_{3} \ge 3 \\ ~ & 0 y_{1} + 2 y_{2} + 2 y_{3} \ge 5 \\ ~ & y_{1} \ge 0,~y_{2} \ge 0,~y_{3} \ge 0 \\ \end{aligned} \right. \end{equation} $$

练习题~2

线性规划原问题如下所示：

$$ \begin{equation} \left\{ \begin{aligned} \max ~ & Z = c_{1}x_{1} + c_{2}x_{2} + c_{3}x_{3} \\ S.t. ~ & a_{11}x_{1} + a_{12}x_{2} + a_{13}x_{3} \le b_{1} \\ ~ & a_{21}x_{1} + a_{22}x_{2} + a_{23}x_{3} \ge b_{2} \\ ~ & a_{31}x_{1} + a_{32}x_{2} + a_{33}x_{3} = b_{3} \\ ~ & x_{1} \ge 0,~x_{2} \le 0,~ x_{3}无约束 \\ \end{aligned} \right. \end{equation} $$

则根据上述转化关系对应顺序进行转化，可以得到如下对偶问题模型：

$$ \begin{equation} \left\{ \begin{aligned} \min ~ & W = b_{1}y_{1} + b_{2}y_{2} + b_{3}y_{3} \\ S.t. ~ & a_{11}y_{1} + a_{21}y_{2} + a_{21} y_{3} \ge c_{1} \\ ~ & a_{12}y_{1} + a_{22}y_{2} + a_{32}y_{3} \le c_{2} \\ ~ & a_{13}y_{1} + a_{23}y_{2} + a_{33}y_{3} = c_{3} \\ ~ & y_{1} \ge 0,~y_{2} \le 0,~ y_{3}无约束 \\ \end{aligned} \right. \end{equation} $$

具体过程如图1所示。

图1 练习题~2的转化过程对应关系图解

总结：
1、原问题有几个约束，对偶问题就有几个变量；
2、原问题约束条件系数矩阵 转置 后就是对偶问题的约束条件系数矩阵；
3、原问题目标函数系数是对偶问题约束条件的常数，原问题约束条件常数项是对偶问题的目标函数系数；
4、原问题求最大，则对偶问题求最小；
5、原问题约束条件是小于等于，则对偶问题对偶变量为大于等于；原问题约束条件是大于等于，则对偶问题对偶变量是小于等于；原问题约束条件是等于，则对偶问题对偶变量是无约束；
6、原问题变量是大于等于，则对偶问题约束条件是大于等于；原问题变量是小于等于，则对偶问题约束条件是小于等于；原问题变量是无约束，则对偶问题约束条件是等于。

对偶问题的基本性质

考虑如下线性规划问题：

$$ \begin{equation} \left\{ \begin{aligned} \max ~ & \mathbf{Z} = \sum_{j=1}^{n}{c_{j}x_{j}} \\ S.t. ~ & \sum_{j}^{n}{a_{ij}x_{j}} \le b_{i},~\forall i \in \{1,2,\cdots,m\} \\ ~ & x_{j} \ge 0,~\forall j \in \{1,2,\cdots,n\} \\ \end{aligned} \right. \end{equation} $$

则根据上述转换步骤，可以将其对偶问题写成如下表达式：

$$ \begin{equation} \left\{ \begin{aligned} \min ~ & \mathbf{W} = \sum_{i}^{m}{b_{i}y_{i}} \\ S.t. ~ & \sum_{i=1}^{m}{a_{ij}y_{i}} \ge c_{j},~\forall j \in \{1,2,\cdots,n\} \\ ~ & y_{i} \ge 0,~\forall i \in \{1,2,\cdots,m\} \end{aligned} \right. \end{equation} $$

注意： 这里对偶问题约束条件对偶变化成了对$i$求和，即进行了 转置 。

弱对偶性

如果$\widetilde{x_{j}}$是原问题的可行解，$\widetilde{y_{i}}$是对偶问题的可行解，则恒有：

$$ \sum_{j=1}^{n}{c_{j}x_{j}} \le \sum_{i=1}^{m}{b_{i}y_{i}} $$

证明：

$$ \sum_{j=1}^{n}{c_{j}\widetilde{x_{j}}} \le \sum_{j=1}^{n}{(\sum_{i=1}^{m}{a_{ij}\widetilde{y_{i}}})\widetilde{x_{j}}} = \sum_{j=1}^{n}{\sum_{i=1}^{m}{a_{ij}\widetilde{x_{j}}\widetilde{y_{i}}}} $$

$$ \sum_{j}^{n}{b_{i}\widetilde{y_{i}}} \ge \sum_{i=1}^{m}{(\sum_{j=1}^{n}{a_{ij}\widetilde{x_{j}}})\widetilde{y_{i}}} = \sum_{j=1}^{n}{\sum_{i=1}{m}{a_{ij}\widetilde{x_{j}}\widetilde{y_{i}}}} $$

根据弱对偶性，可以得出下面的推论：
1、对于原问题是MAX问题的目标规划，其目标函数值是对其对偶问题的目标函数值的下界，反之对偶问题的目标桉树值是原问题的上界；
2、如果原问题具有可行解且目标函数无界，则其对偶问题无可行解，反之亦然；
3、如果原问题具有可行解而其对偶问题无可行解，则原问题的目标函数无界，反之亦然。

最优性

如果$\widehat{x_{j}}$（$j=1,2,\cdots,n$）是原问题的可行解，$\widehat{y_{i}}$（$i=1,2,\cdots,m$）是对偶问题的可行解，如果有

$$ \sum_{j}^{n}{c_{j}\widehat{x_{j}}} = \sum_{i}^{m}{b_{i}\widehat{y_{i}}} $$

则$\widehat{x_{j}}$（$j=1,2,\cdots,n$）是原问题的最优解，$\widehat{y_{i}}$（$i=1,2,\cdots,m$）是对偶问题的最优解。

强对偶性（或称对偶定理）

如果原问题及其对偶问题均有可行解，则两者均具有最优解，且最优解的目标函数值相等。

互补松弛性

如果$\widehat{x_{j}}$（$j=1,2,\cdots,n$）与$\widehat{y_{i}}$（$i=1,2,\cdots,m$）分别为原问题和对偶问题的可行解，则有：
1、原问题的最优解的充要条件为$(c_{j}-\sum_{i=1}^{m}{a_{ij}\widehat{y_{i}}})\widehat{x_{j}}=0$;
2、对偶问题的最优解的充要条件为$(b_{i}-\sum_{j}^{n}{a_{ij}\widehat{x_{j}}})\widehat{y_{i}}=0$;
3、当原问题取到最优解$\widehat{x_{j}}$（$j=1,2,\cdots,n$）与对偶问题取到最优解$\widehat{y_{i}}$（$i=1,2,\cdots,m$）时，一定有：

$$ \widehat{x_{sj}}*y_{i} = 0 $$

$$ \widehat{y_{si}}*x_{j} = 0 $$

参考资料：

1. https://zhuanlan.zhihu.com/p/564463114
2. https://www.cnblogs.com/xoslh/p/16777113.html