一、对称理论

---

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

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

$\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$ , 因此 对偶问题的变量符号 与 原问题约束方程符号 符号一致 ;

一、原问题与对偶问题标准形式

---

原问题 $\mathrm{P}$ : $\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}$ ;              \ \ \ \ \ \ \ \ \ \ \,            对偶问题 $\mathrm{D}$ : $\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}$

等价方法 :

• 生产 : 目标函数追求 利润最大化 , 约束方程设备的使用时长受约束 , 小于等于 某个时间值 ;
• 出租设备 : 目标函数追求 租金最小化 , 约束方程设备产生的利润要 大于等于 生产的利润 , 不能亏钱 ;

二、互补松弛定理

---

${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 可行解 ,

这两个解各自都是对应 线性规划问题 的 最优解

的 充要条件是 : $\{\begin{array}{l}{\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}=0\\ \\ {\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0\end{array}$

其中 ${\mathrm{X}}_{\mathrm{s}},{\mathrm{Y}}_{\mathrm{s}}$ 是 松弛变量 或 剩余变量 ;

三、已知原问题最优解求对偶问题最优解

---

已知线性规划 :

$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=3{\mathrm{x}}_1+4{\mathrm{x}}_2+{\mathrm{x}}_3\\ \\ \{\begin{array}{l}{\mathrm{x}}_1+2{\mathrm{x}}_2+{\mathrm{x}}_3\le 10\\ \\ 2{\mathrm{x}}_1+2{\mathrm{x}}_2+{\mathrm{x}}_3\le 16\\ \\ {\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3\ge 0\end{array}\end{array}$

上述线性规划的最优解是 ${\mathrm{X}}^0=\left(\begin{array}{c}620\end{array}\right)$ , 求其对偶问题最优解 ;

四、使用单纯形法求解

---

方法一 : 写出上述线性规划的对偶问题 , 然后使用单纯形法求最优解 ,

首先写出 对偶问题 , 然后转为 标准形式 , 找 单位阵 作为基矩阵 , 然后得到基变量 , 假设非基变量为 $0$ 求出 基解 ,

在单纯形表中计算 检验数 , 如果 检验数都小于 $0$ 就是最优解 , 如果检验数都大于 $0$ , 则不是最优解 ;

根据检验数确定 出基变量 , 然后计算出 入基变量 , 进行下一次迭代 ;

方程组 同解变换, 构造单位阵 , 然后计算检验数 , 继续按照上述方法进行迭代 ;

该方法比较麻烦 ;

五、使用互补松弛定理公式一求解

---

方法二 : 利用 互补松弛定理 计算 ;

写出原问题的对偶问题 :

$\begin{array}{l}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{W}=10{\mathrm{y}}_1+16{\mathrm{y}}_2\\ \\ \{\begin{array}{l}{\mathrm{y}}_1+2{\mathrm{y}}_2\ge 3\\ \\ 2{\mathrm{y}}_1+2{\mathrm{y}}_2\ge 4\\ \\ {\mathrm{y}}_1+{\mathrm{y}}_2\ge 1\\ \\ {\mathrm{y}}_1,{\mathrm{y}}_2\ge 0\end{array}\end{array}$

给对偶问题的约束方程添加剩余变量 :

$\{\begin{array}{l}{\mathrm{y}}_1+2{\mathrm{y}}_2-{\mathrm{y}}_3=3\\ \\ 2{\mathrm{y}}_1+2{\mathrm{y}}_2-{\mathrm{y}}_4=4\\ \\ {\mathrm{y}}_1+{\mathrm{y}}_2-{\mathrm{y}}_5=1\\ \\ {\mathrm{y}}_1,{\mathrm{y}}_2,{\mathrm{y}}_3,{\mathrm{y}}_4,{\mathrm{y}}_5\ge 0\end{array}$

互补松弛定理 :

" ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 最优解 " $\iff$ $\{\begin{array}{l}{\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}=0\\ \\ {\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0\end{array}$

其中 ${\mathrm{X}}_{\mathrm{s}},{\mathrm{Y}}_{\mathrm{s}}$ 是 松弛变量 或 剩余变量 ;

原问题 $\mathrm{P}$ 线性规划最优解是 ${\mathrm{X}}^0=\left(\begin{array}{c}620\end{array}\right)$ ,

对偶问题的剩余变量是 ${\mathrm{Y}}_{\mathrm{s}}=\left(\begin{array}{c}{\mathrm{y}}_3\\ \\ {\mathrm{y}}_4\\ \\ {\mathrm{y}}_5\end{array}\right)$

互补松弛定理中 ${\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0$ , 将上述 ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}_{\mathrm{s}}$ 代入上述式子得到 :

${\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=\left(\begin{array}{c}620\end{array}\right)\times \left(\begin{array}{c}{\mathrm{y}}_3\\ \\ {\mathrm{y}}_4\\ \\ {\mathrm{y}}_5\end{array}\right)=6{\mathrm{y}}_3+2{\mathrm{y}}_4+0{\mathrm{y}}_5=6{\mathrm{y}}_3+2{\mathrm{y}}_4=0$

已知 ${\mathrm{y}}_3,{\mathrm{y}}_4\ge 0$ , 上述 $6{\mathrm{y}}_3+2{\mathrm{y}}_4=0$ , 因此 ${\mathrm{y}}_3=0,{\mathrm{y}}_4=0$ ;

将 ${\mathrm{y}}_3=0,{\mathrm{y}}_4=0$ 代入到约束方程 $\{\begin{array}{l}{\mathrm{y}}_1+2{\mathrm{y}}_2-{\mathrm{y}}_3=3\\ \\ 2{\mathrm{y}}_1+2{\mathrm{y}}_2-{\mathrm{y}}_4=4\\ \\ {\mathrm{y}}_1+{\mathrm{y}}_2-{\mathrm{y}}_5=1\\ \\ {\mathrm{y}}_1,{\mathrm{y}}_2,{\mathrm{y}}_3,{\mathrm{y}}_4,{\mathrm{y}}_5\ge 0\end{array}$ 中 ;

得到 $\{\begin{array}{l}{\mathrm{y}}_1+2{\mathrm{y}}_2=3\\ \\ 2{\mathrm{y}}_1+2{\mathrm{y}}_2=4\end{array}$ , 解上述方程 ,

① 变换 : $\{\begin{array}{l}2{\mathrm{y}}_1+4{\mathrm{y}}_2=6\\ \\ 2{\mathrm{y}}_1+2{\mathrm{y}}_2=4\end{array}$

② 求解 : $\{\begin{array}{l}{\mathrm{y}}_1=1\\ \\ {\mathrm{y}}_2=1\end{array}$

上述求出的值就是最优解 , 即 ${\mathrm{Y}}^0=\left(\begin{array}{c}11\end{array}\right)$ ;

六、使用互补松弛定理公式二求解 ( 无效方法 )

---

方法三 : 利用 互补松弛定理 计算 ;

互补松弛定理 :

" ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 最优解 " $\iff$ $\{\begin{array}{l}{\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}=0\\ \\ {\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0\end{array}$

其中 ${\mathrm{X}}_{\mathrm{s}},{\mathrm{Y}}_{\mathrm{s}}$ 是 松弛变量 或 剩余变量 ;

上面 " 五、使用互补松弛定理公式一求解 " 小节 使用的是 ${\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0$ 公式进行求解 , 在本小节中使用 ${\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}=0$ 公式进行求解 ;

原问题 $\mathrm{P}$ 线性规划最优解是 ${\mathrm{X}}^0=\left(\begin{array}{c}620\end{array}\right)$ , 将该最优解代入原问题的约束条件中 , 求出原问题的约束变量 ${\mathrm{X}}_{\mathrm{s}}$ ;

原问题 :

$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=3{\mathrm{x}}_1+4{\mathrm{x}}_2+{\mathrm{x}}_3\\ \\ \{\begin{array}{l}{\mathrm{x}}_1+2{\mathrm{x}}_2+{\mathrm{x}}_3\le 10\\ \\ 2{\mathrm{x}}_1+2{\mathrm{x}}_2+{\mathrm{x}}_3\le 16\\ \\ {\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3\ge 0\end{array}\end{array}$

原问题添加松弛变量后 :

$\begin{array}{l}\mathrm{m}\mathrm{a}\mathrm{x}\mathrm{Z}=3{\mathrm{x}}_1+4{\mathrm{x}}_2+{\mathrm{x}}_3\\ \\ \{\begin{array}{l}{\mathrm{x}}_1+2{\mathrm{x}}_2+{\mathrm{x}}_3+{\mathrm{x}}_4=10\\ \\ 2{\mathrm{x}}_1+2{\mathrm{x}}_2+{\mathrm{x}}_3+{\mathrm{x}}_5=16\\ \\ {\mathrm{x}}_1,{\mathrm{x}}_2,{\mathrm{x}}_3,{\mathrm{x}}_4,{\mathrm{x}}_5\ge 0\end{array}\end{array}$

将最优解 ${\mathrm{X}}^0=\left(\begin{array}{c}620\end{array}\right)$ 代入原问题 :

$\{\begin{array}{l}6+2\times 2+0+{\mathrm{x}}_4=10\\ \\ 2\times 6+2\times 2+0+{\mathrm{x}}_5=16\end{array}$

得到 : $\{\begin{array}{l}{\mathrm{x}}_4=0\\ \\ {\mathrm{x}}_5=10\end{array}$

${\mathrm{X}}_{\mathrm{s}}=\left(\begin{array}{c}0\\ \\ 0\end{array}\right)$

这个信息是无用的 , 根据这个 ${\mathrm{X}}_{\mathrm{s}}$ 乘以任意的 ${\mathrm{Y}}^0$ 值都是 $0$ , 求不出对偶问题的最优解 ;

七、总结

---

互补松弛定理 :

" ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 原问题 $\mathrm{P}$ 问题 和 对偶问题 $\mathrm{D}$ 的 最优解 " $\iff$ $\{\begin{array}{l}{\mathrm{Y}}^0{\mathrm{X}}_{\mathrm{s}}=0\\ \\ {\mathrm{Y}}_{\mathrm{s}}{\mathrm{X}}^0=0\end{array}$

其中 ${\mathrm{X}}_{\mathrm{s}},{\mathrm{Y}}_{\mathrm{s}}$ 是 松弛变量 或 剩余变量 ;

原问题 $\mathrm{P}$ 线性规划最优解是 ${\mathrm{X}}^0=\left(\begin{array}{c}620\end{array}\right)$ ,

对偶问题的剩余变量是 ${\mathrm{Y}}_{\mathrm{s}}=\left(\begin{array}{c}{\mathrm{y}}_3\\ \\ {\mathrm{y}}_4\\ \\ {\mathrm{y}}_5\end{array}\right)$

最优解中不等于 $0$ 的 , 对应的剩余变量中对应的一定为 $0$ ,

如果最优解中等于 $0$ , 那么剩余变量中的对应的值就不确定了 ;

若 $K$ 为一个锥，那么它的对偶锥的定义为：
K ∗ = { y ∣ x ⋅ y ≥ 0  for all  x ∈ K } K^\ast=\{y\mid x\cdot y\geq 0 \text{ for all } x\in K\} K∗={y∣x⋅y≥0 for all x∈K}

上式中的点表示内积。（两个矩阵的内积等于他们乘积的迹）

在几何意义上，对偶锥上的一条线 $y$ 一定属于 $K$ 其中一个支撑超平面的法线。例如下图


上图中的红色区域就是 $C$ 的对偶锥。

几个实例

• 子空间（线性子空间） $V$ 的对偶锥是它的正交补.
  V ∗ = V ⊥ = { y ∣ y T v = 0 } V^\ast=V^{\perp}=\{y\mid y^Tv=0\} V∗=V⊥={y∣yTv=0}
  利用了一个性质：若 $x\in V$，则 $-x\in V$.
• 非负象限的对偶锥是它自身.
• 半正定矩阵的对偶锥是它自身.
• 范式锥的对偶锥是它的对偶范式锥.