对偶问题与原问题的关系(优化 | 如何写对偶问题)

对偶问题。『运筹OR帷幄』原创

作者：翁欣 （中科院管理科学与工程研究生在读）

编者按：

作者在上一期的文章中给我们解释了「为何引入对偶问题」，可见对偶问题对原问题的求解有很大的帮助。那么，如何写出对偶问题呢？这篇文章介绍的方法能帮助你快速准确无误地写出任意线性规划的对偶问题。

我们先以一般形式的对偶问题写法入手，给出表格法写对偶问题的思路；至于非一般形式线性规划可以先转换成一般形式，再写对偶问题。最后，我们将其中的技巧整理成一张表格，方便查询。

一般形式的对偶问题写法

以目标函数最大化问题为例，原问题的一般形式指的是变量全部非负、约束全部为小于等于约束的线性规划，向量形式如 (1)：

根据上一节内容，其对偶问题的含义是：在原问题目标函数的所有上界中，找到最小的一个（推导过程见上一节「为何引入对偶问题」）。相应对偶问题的一般形式，指的是变量全部非负、约束全部为大于等于约束的线性规划，向量形式如：

在向量形式中，可以直观看出原问题和对偶问题的系数存在对应关系，例如：原问题目标函数的系数向量的转置

，是对偶问题约束的右侧向量；原问题约束的系数矩阵的转置

，是对偶问题约束的系数矩阵。

我们也可以通过上一节企业出售产品和收购资源的实例，让对应的感受更直观一些：

如果我们面对的是一般形式问题，可以使用表格法便捷地写出对偶问题。图 1[1]中，由上至下按行读是原问题的约束和目标函数，由左至右按列读是对偶问题的约束和目标函数。

图 1 表格法写对偶问题（图片摘自[1]）

简单标示如下：

图 2 表格法写对偶问题（标示max问题）

图 3 表格法写对偶问题（标示min问题）

非一般形式的对偶问题写法

上一节阐述了原问题是一般形式时，如何写出对偶问题。实际中我们常常会遇到非一般形式的线性规划问题，在应用表格法之前需要先对变量和约束的形式进行转化（仍以目标函数最大化问题为例）：

①如果有 ≥ 约束，则左右同乘- 1，转化为 ≤ 约束；

②如果有 = 约束，则先转换为一个 ≤ 约束和一个 ≥ 约束，再按①把 ≥ 约束转换为 ≤ 约束。例如，如果存在约

，等价于同时满足

和

，后者再写

。

③如果有无符号限制(unrestricted in sign, urs) 的变量，用两个符号限制为 ≥0 的变量相减表示，转换关系为

。

总结

根据前两节，可以将「写对偶问题」的通用步骤归纳如下：

①将原问题转换为一般形式；

②由上至下逐行写原问题一般形式的变量及符号限制、约束和目标函数；

③根据对应关系表确定对偶问题的约束符号和变量符号；

④由左至右逐列读，得到对偶问题的变量及符号限制、约束和目标函数。

表格法中，原问题和对偶问题的符号对应关系可参考表 1。

（由于对偶的对偶是原问题，所以当原问题是最小化问题时，对应关系同样适用）：

表 1 原问题和对偶问题对应关系

本文是电子书线性规划专题的约稿文。继上回探讨为何引入对偶问题后，本文讲述了如何写对偶问题。接下来，我们将继续针对对偶原理，回答「为什么原问题和对偶问题具有相同的最优解（在有最优解的前提下）」，在证明的过程中，也会发现线性规划的一些其他性质。希望大家继续关注【优化】板块，电子书线性规划专题的科普文。

参考文献：

[1] L Winston, Wayne & B Goldberg, Jeffrey. (2004). Operations research: applications and algorithms