一、对称理论

---

参考 【运筹学】对偶理论 : 对称形式 ( 对称形式 | 对偶模型转化实例 | 对偶问题规律分析 ) 写出原问题线性规划的对偶问题线性规划 ,

原问题的线性规划模型 : 注意原问题的线性规划 目标函数求最大值 , 约束方程都是 小于等于不等式 ;

$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=\mathrm{C}\mathrm{X}\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}\mathrm{A}\mathrm{X}\le \mathrm{b}\\ \\ \mathrm{X}\ge 0\end{array}\end{array}$

如果原问题是求最大值 , 约束方程有大于等于不等式 , 需要在这些大于等于不等式 左右两边乘以 $-1$ , 将 大于等于不等式 转为 小于等于不等式 ;

如果进行了上述操作 , 则最终求出对偶问题后 , 系数矩阵肯定不互为转置矩阵 , 还要进行一次代换 , 令 ${\mathrm{y}}^{\prime }=-\mathrm{y}$ 吗使用 $-{\mathrm{y}}^{\prime }=\mathrm{y}$ 替换对偶问题中的变量 ;

对偶问题的线性规划模型 : 对偶问题 目标函数求最小值 , 约束方程都是 大于等于不等式 ;

$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}={\mathrm{b}}^{\mathrm{T}}\mathrm{Y}\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}{\mathrm{A}}^{\mathrm{T}}\mathrm{Y}\ge {\mathrm{C}}^{\mathrm{T}}\\ \\ \mathrm{Y}\ge 0\end{array}\end{array}$

矩阵转置 : 第 $1$ 列变第 $1$ 行 , $\cdots$ , 第 $\mathrm{n}$ 列变第 $\mathrm{n}$ 行 ;

二、对偶理论示例

---

对偶示例 : 给出如下线性规划 ,

$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=2{\mathrm{x}}_1+{\mathrm{x}}_2\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}{\mathrm{x}}_1-2{\mathrm{x}}_2\le 8\\ \\ {\mathrm{x}}_1,{\mathrm{x}}_2\ge 0\end{array}\end{array}$

上述线性规划原问题 ① 目标函数求最大值 ② 约束方程是小于等于不等式 , ③ 约束变量大于等于 $0$ , 符合标准 ;

写出其对偶问题 :

( 1 ) 目标函数求最小 , 且目标函数的系数是原方程的约束方程常数 ;

$\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{Z}=8{\mathrm{y}}_1$

( 2 ) 约束条件 :

对偶问题约束方程系数 : 约束方程矩阵是 $\left(\begin{array}{cccc}& 1& -2& \end{array}\right)$ 的转置矩阵 $\left(\begin{array}{ccc}& 1& \\ & -2& \end{array}\right)$ ;

对偶问题变量个数 : 约束方程的变量个数是矩阵的列数 , 这里只有 $1$ 列 , 则只有 $1$ 个变量 ${\mathrm{y}}_1$ ;

约束方程中间符号 : 约束条件的符号是由 原问题 变量符号决定 ( 都是 $\ge 0$ ) , 因此对偶问题的约束方程符号也是 $\ge$ ;

约束方程右侧常数 : 是原问题目标函数的系数转置 , 分别是 $2,1$ ;

变量符号 : 对偶问题变量符号与原问题约束方程符号相反 ; 原问题约束方程是小于等于符号 , 对偶问题的变量是大于等于 $0$ 的 ;

最终的对偶问题是 :

$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}=8{\mathrm{y}}_1\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}{\mathrm{y}}_1\ge 2\\ \\ -2{\mathrm{y}}_1\ge 1\\ \\ {\mathrm{y}}_1\ge 0\end{array}\end{array}$

三、对偶理论示例 2

---

如果给出的原问题目标函数是求最小值 :

$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{Z}=2{\mathrm{x}}_1+{\mathrm{x}}_2\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}{\mathrm{x}}_1-2{\mathrm{x}}_2\le 8\\ \\ {\mathrm{x}}_1,{\mathrm{x}}_2\ge 0\end{array}\end{array}$

上述线性规划的对偶问题的目标函数是求最大值 ;

参考下图列表 :

写出其对偶问题 ( 上述表格中的右侧 ) :

( 1 ) 目标函数求最大 , 且目标函数的系数是原方程的约束方程常数 ;

$\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}=8{\mathrm{y}}_1$

( 2 ) 约束条件 :

对偶问题约束方程系数 : 约束方程矩阵是 $\left(\begin{array}{cccc}& 1& -2& \end{array}\right)$ 的转置矩阵 $\left(\begin{array}{ccc}& 1& \\ & -2& \end{array}\right)$ ;

对偶问题变量个数 : 约束方程的变量个数是矩阵的列数 , 这里只有 $1$ 列 , 则只有 $1$ 个变量 ${\mathrm{y}}_1$ ;

约束方程中间符号 : 约束条件的符号是由 原问题 变量符号决定 ( 都是 $\ge 0$ ) , 这里如果目标函数求最小值时原问题 , 其对偶问题约束方程符号 与 原问题变量符号相反 , 因此对偶问题的约束方程符号也是 $\le$ ;

约束方程右侧常数 : 是原问题目标函数的系数转置 , 分别是 $2,1$ ;

变量符号 : 对偶问题变量符号与原问题约束方程符号相同 ; 原问题约束方程是小于等于符号 , 对偶问题的变量是小于等于 $0$ 的 ;

最终的对偶问题是 :

$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=8{\mathrm{y}}_1\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}{\mathrm{y}}_1\le 2\\ \\ -2{\mathrm{y}}_1\le 1\\ \\ {\mathrm{y}}_1\le 0\end{array}\end{array}$

四、求对偶技巧 ★★

---

写出对偶定理的标准对称形式 ★ : 记住下面的标准形式

原问题 :

$$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=\mathrm{C}\mathrm{X}\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}\mathrm{A}\mathrm{X}\le \mathrm{b}\\ \\ \mathrm{X}\ge 0\end{array}\end{array}$$

对偶问题 :

$$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}={\mathrm{b}}^{\mathrm{T}}\mathrm{Y}\\ \\ \mathrm{s}.\mathrm{t}\{\begin{array}{l}{\mathrm{A}}^{\mathrm{T}}\mathrm{Y}\ge {\mathrm{C}}^{\mathrm{T}}\\ \\ \mathrm{Y}\ge 0\end{array}\end{array}$$

查看 约束变量的符号 与 其另外一个对偶问题的 约束方程的符号 一致性 , 来确定对偶问题的约束方程符号 ;

约束方程符号 :

如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 $\ge$ , 因此 对偶问题的约束方程符号 与 原问题变量 符号一致 ;

如果当前线性规划问题 目标函数是求最小值 , 原问题就是下面的问题 , 其对偶问题 ( 上面的 ) 的约束方程符号是 $\le$ , 因此 对偶问题的约束方程符号 与 原问题变量 符号相反 ;

变量符号 :

如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 $\ge$ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号相反 ;

如果当前线性规划问题 目标函数是求最大值 , 原问题就是上面的问题 , 其对偶问题 ( 下面的 ) 的约束方程符号是 $\ge$ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号一致 ;

平面图定义：

图存在一种形式，所有的边只在顶点处相交，那么这个图就是平面图。

对偶图定义：

对于每一个平面图， 都有与其相对应的对偶图. 我们假设上面的例图是图G， 与其对应的对偶图G*， 那么对于G*来说， G*上面的每一个点， 对应的是G里面的每一个面. 比如说下面就是G*.

上面的点就是对偶图G里的点.  
那么关于对偶图G*里的边呢 ? 对于G中本来的每条边e， 他是两个面(比如说面f1和f2)的交边， 那么在对偶图里， 我们对这两个面(f1， f2)所映射在G*里的点连线(f1* 连向f2*). 如果f1 == f2(比如说G中5， 6这条边， 边的两侧都是同一个面， 那我们就建一条回边. 
图就长这样(回边在5， 6那里).

求网络流的最小割或最大流时，如果时平面图，就可以转化成对偶图，然后对对偶图求s',t'的最短路，就是原网络的最大流和最小割。就是对偶图的点需要自己对应好。。

1.对偶问题

随着线性规划应用的逐步深入，人们发现一个线性规划问题往往伴随着与之配对的、两者有着密切的联系的另一个线性规划问题，将其中一个称为原问题，另外一个称之为对偶问题。

对偶理论深刻揭示了原问题与对偶问题的内在联系，由对偶问题引申出来的对偶解有着重要经济意义，是经济学中重要的概念工具之一，对偶理论充分显示线性规划理论逻辑上的严谨性与结构上的对称性，它是线性规划的重要成果。

原问题的例子

某家具厂木器车间生产木门和木窗的两种产品，加工木门收入56\扇，加工木窗收入30\扇，生产一扇木盟需要木工4小时、油漆工需要2小时，生产一扇木窗需要木工3小时、油漆工1小时，该车间每日可用木工总工时120小时，油漆工总工时50小时，问该车间应该如何安排生产才能使得每日收入最大？

解 令该车间每日安排生产木门x1扇，木窗x2扇，则数学模型为：

使用图解法或者单纯形表方法，可以求得最优解：

对偶问题

现在从另外一个角度来考虑该车间的生产问题，假若有一个个体经营者，手中有一批木器家具生产订单，他想利用该车间的木工与油漆工来完成他的订单，他就要事先考虑付给该车间每个工时的价格
需要考虑的问题：

1. 木器车间觉得有利可图从而愿意替他加工这批订单；
2. 他自己所付时费用总数最小；
   设W1为付给木工每个工时的价格，W2为付给油漆工每个工时的价格，则该个体经营者的目标函数每日所付工时总费用最小：
   
   但是个体经营者所付的价格不能太低，至少不能低于该车间生产木门、木窗时候所得到的收入，否则该车间觉得无利可图就不会替他加工这批订单，因此w1、W2取值应该满足：
   
   那么经过上面的问题梳理，我们把两个问题放在一起看
   
   左边是车间老板的角度来看，右边的对偶问题是从个体经营者来看，一个求最大值，另外一个求最小值，我们来看一下原问题的max 式子的系数，在右边的对偶问题变成了 下面约束条件的值，而左边的约束条件的值变成了右边对偶问题的min式子的系数

从最后的结果可以看到，虽然最优解的结果不一样，但是最这个最优解的框架下，相应的目标函数的结果都是1440，说明这个订单一定是成功的完成了

转换到一般情况

LP我们定义就是原问题，DP是对偶问题，Max和Min的式子的系数称之为价值系数，下面的公式称之为约束条件

可以看出：

1. 原问题的价值系数在对偶问题提中成为约束条件的右端项，而原问题的约束条件的右端项在对偶问题成了价值系数；
2. 原问题中约束不等式左端的决策变量的系数，在对偶问题中成为对偶问题决策变W1和W2的系数列向量P1，P2；
3. 原问题中Xi的系数列向量Pi，在对偶问题中就是第i个约束不等式做端对偶变量前的系数

如何迅速的从一个线性规划问题提出对偶问题

写出对偶问题的例子