"战略家& quot原来的

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

编者按：

在上一篇文章中，作者向我们解释了& quot为什么引入对偶问题& quot，说明对偶问题对原问题的解决有很大的帮助。那么，对偶问题怎么写呢？本文介绍的方法可以帮助你快速准确地写出任意线性规划的对偶问题。

首先从对偶问题写作的一般形式入手，给出用表格法写作对偶问题的思路；至于非一般线性规划，可以先转化为一般形式，然后再写出对偶问题。最后，我们将技能组织成一个表格，以便于查询。

一般形式的对偶问题写法

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

根据上一节的内容，对偶问题的意义是在原问题的目标函数的所有上界中寻找最小的一个(推导过程见上一节& quot为什么要引入对偶问题& quot).对应的对偶问题的一般形式是指所有变量都是非负的，所有约束都大于等于约束的线性规划。向量形式如下：

在向量形式中，我们可以直观地看到原问题和对偶问题的系数之间存在对应关系，例如原问题目标函数的系数向量的换位。

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

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

我们还可以通过上一节企业销售产品和采购资源的例子，让对应的感受更加直观：

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

图1以表格形式写出对偶问题(图片取自[1])

简单标签如下：

图2表写对偶问题(标记为最大问题)

图3表写对偶问题(标为最小问题)

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

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

(1)若有约束，则左右乘以-1，换算成约束；

如果有=约束，先将其转换为约束和约束，然后按将约束转换为约束。例如，如果有大约

，相当于同时满足了。

和

，后者再来写。

(3)如果有一个变量有或没有unrestrictedinsign，urs)，则用两个符号极限0的变量相减来表示，转换关系为。

总结

根据前两节，& quot写对偶问题"可以总结如下：

将原问题转化为一般形式；

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

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

(4)从左到右逐列阅读，得到对偶问题的变量和符号约束、约束和目标函数。

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

(因为对偶的对偶是原问题，所以原问题是极小化问题时对应关系也适用):

表1原始问题和对偶问题之间的对应关系

这篇文章是为电子书线性规划.的题目写的草稿，在上次讨论了为何引入对偶问题之后，这篇文章讲述了如何写对偶问题。接下来，我们将继续回答& quot为什么原问题和对偶问题具有相同的最优解（在有最优解的前提下）"根据对偶原理。在证明的过程中，我们还会发现线性规划的其他一些性质。希望大家继续关注电子书线性规划专题的科普文【优化】板块。

参考文献：