对偶规划问题

对偶问题（Dual Problem）是运筹学中一个很重要的概念，是基于原问题的约束条件和目标函数为基础构造而来。每一个线性规划的问题都存在一个与之对应的对偶问题。

知乎上有个人通俗解释了[为什么要研究对偶问题](https://www.zhihu.com/question/26658861/answer/53394624)：

> 对偶问题有时比原问题更简单确实是一个很吸引人的答案。但最重要的不是这个。线性规划的对偶理论没出现的时候，线性规划是不知道能不能解的！！！而且那时候也还没有计算机。解线性规划最常用的方法是哪个?单纯形法。单纯形法第一步是什么？找一个起始点。我问你，起始点找不到怎么办？！！或者换一个问法：我现在只问你，给你的这个线性规划问题有没有可行解，你怎么回答我？

> ……

> 对偶问题是解决这个事情的。这个就联系到Farkas lemma和其他一系列定理。全讲清楚就很花时间了。大概来讲就是说，有牛人找到一个跟原问题的对偶问题密切相关的问题，如果这个问题有解，原问题就没解。这样就提供了一个简单的证明原问题没解的途径。

在这里我们举个例子，来说明一下怎么改写原问题成对偶问题。案例来自[某个学校老师的材料](http://netedu.xauat.edu.cn/jpkc/netedu/jpkc/ycx/kcjy/kejian/pdf/02.pdf)。

原问题（线性规划问题，Linear Program, LP）:某公司计划产出甲、乙两种产品，使用d1、d2和d3三种生产因素，其数量限制和例如如下图所示，我们的问题是这两种产品分别生产多少才能最大化例如：

<center>![](http://www.datalearner.com/resources/blog_images/89dda912-ca8e-4184-8d8b-42a0b3b0bcc0.png)</center>

假设两种产品生产的数量分别是$x\_1$和$x\_2$，那么，可以目标函数如下：

```math
\max Z = 5x_1+4x_2
```

限制条件是（subject to， s.t.）：

```math
\text{s.t.}

\begin{cases}
   x_1+3x_2 &\leq 90 \\
   2x_1+x_2 &\leq 80 \\
   x_1+x_2 &\leq 45 \\
   x_1,x_2 &\geq 0
\end{cases}
```

这个问题也可以求解，但是假如是一个复杂的线性规划问题，求解复杂，且不知道是否有可行解的时候，可以通过求该问题的对偶问题（dual program）来解决。如何求对偶问题呢，我们可以这样思考：假设我们希望该公司放弃生产这两种产品，把这三种原材料卖给我们，那么我们应当如何出价才能是该公司愿意这样做。不考虑其他非利润因素，首先需要使该公司卖出三种原材料的总利润要高于用其来生产产品的利润，但我们希望最低和它一样就可以了。同时，我们给出的价格也要比他们用来生产甲乙两种产品得到的利润高，不然也不划算。因此，假设我们给每种材料的价格是$w\_1$、$w\_2$和$w\_3$。那么新的目标函数是：

```math
\min G = 90w_1 + 80w_2 + 45 w_3
```

限制条件是：
```math
\text{s.t.}

\begin{cases}
   w_1+2w_2 +w_3 &\geq 5 \\
   3w_1+w_2 + w_3 &\geq 4 \\
   w_1,w_2,w_3 &\geq 0
\end{cases}
```
那么，这个问题就是原问题的对偶问题。可以看到，这个问题的限制条件比之前少了。

下面我们来描述一下标准的变化形式。假设有如下的线性规划问题（Linear Programming, LP）：

```math
\max Z = CX
```
```math
\text{s.t.}

\begin{cases}
   AX &\leq b \\
   X &\geq 0
\end{cases}
```

那么该问题的对偶规划问题（Dual Programming，DP）是：
```math
\min Z = b^TW
```
```math
\text{s.t.}

\begin{cases}
   A^TW &\geq C \\
   W &\geq 0
\end{cases}
```

相关博客

最热博客