对偶规划问题

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

知乎上有个人通俗解释了为什么要研究对偶问题：

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

……

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

在这里我们举个例子，来说明一下怎么改写原问题成对偶问题。案例来自某个学校老师的材料。

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