LP问题进阶 Part 2 | 对偶理论
这一部分对应书上第七章（P45-P51），难度和第四章差不多。由于引用了一些非数学的概念，所以学习的时候难免会遇到一些看似无所根据的概念或者假设。建议大家不要在各种花里胡哨的假设上浪费时间，要把精力留给数学。
虽然线性规划的对偶理论在线性代数和数学模型中都没怎么被提到，但其理论本身有趣而且有用。对偶理论将原LP问题转化为其对偶LP问题，从而使与原问题相关的一些复杂的性质（如解是否为最优）变为对偶问题中较为简单的性质（对应地，解是否可行）。
第五章和第六章暂时没有讲。 第五章主要是线性代数的内容，在此默认大家都学过。需要看一眼的是最后提到的用矩阵表示LP问题的方法。第六章是敏感性分析，我打算留到最后和算法复杂度一起讲。
为方便查阅，再link一下教材。
基本概念
为方便理解我们引入一个例子：
例1： 现有一工厂可以生产小人偶和小火车这两种玩具。生产一个小人偶需要1单位木材和2单位颜料，产生3单位收益。生产一辆小火车需要1单位木材和1单位颜料，产生2单位收益。工厂现有80单位木材和100单位颜料，问如何分配火车与人偶的生产量可以使得收益最大？（见下图左侧）
为方便理解对偶性而引入的一个简单的例子
先补充几个前几章出现过但我没有提到的简单概念。由于没有了解过中文版教材所以翻译可能不太准确。
- 对象(Item)是LP问题中的“名词”，即收益和材料。在此问题中，对象有三个，即：收益、木材、颜料。对象对应着LP问题中的行。在此问题中，收益、木材与颜料分别对应着第一到第三行。
-
行为(Activity)是LP问题中的“动词”，对应着标准表示中的列。通俗地讲，行为就是将材料转化为产品(收益)的过程。在本问题中，制造小火车与制造小人偶就是两种行为。上图中，
所在的列对应着制造小人偶的行为，
所在的列对应着制造小火车的行为。
回忆上一次在基本概念中讲到的基本解与字典的概念，结合线性代数的知识，我们可以将LP问题写为：
LP问题的矩阵表示
不要被上图中复杂的形式迷惑，其实推导过程非常简单。式中各个符号的定义见教材第32页。需要强调的两点是：
-
是由非基本变量构成的向量，在具体取值的时候即为0向量。详见之前对非基本变量的定义。注意不要将非基本变量理解为0变量。非基本变量只是在考虑对应基本解时取值为0。
- 此处假设
是可逆的，但我无法证明
可有
表示，而联系二者的只有等式
。如果
- 基本解对应的目标函数的取值为
，当
的各项系数小于0时取最优解。此时基本变量的取值为
目标函数的值(
)这两个矩阵表示非常重要，建议各位同学自己推导一遍并记下来。
现在假设在市场上有以价格与
售卖的木材与颜料，如上图右侧所示。市场是一个很有趣的概念，可惜我不怎么懂，只知道本章许多内容都与之多多少少地相关。接下来介绍一个比较重要的概念。
-
影子价格(百度百科): 某种材料的影子价格通俗地讲就是该种材料增加1单位所带来的额外的收益。
当某种材料过剩时，其影子价格即为0，因为该材料本来就多于所需，所以它的增加不带来额外收益。 关于影子价格，需要注意以下两点：- 影子价格的定义严格地讲是收益关于某种材料的变化率，但由于我们考虑的是线性问题所以干脆说成是“由于增添1单位某材料所带来的额外收益”。影子价格是一个局部的概念，不要钻牛角尖。
- 书上没有任何解释地给出了影子价格的矩阵表示：
。其实这就是一个简单的求导运算。对比目标函数的值：
变成了一个变向量。在某种意义上，目标函数其实本来就是材料的函数，只不过材料的多少会影响函数的形式（
也会随材料改变。）
影子价格
基本概念大概就是这些，接下来就是神奇的部分了。
对偶性理论
这一部分有许多条件并不是一般的，比如我们只讨论了最大值问题而没研究最小值问题。不过方法的本质都是一样的。
1. 基本假设与直观理解
对偶(Dual)不论是单词还是翻译都和泛函分析中函数空间的那种对偶一样。事实上对偶是数学中一种非常常见的思想方法。通过配合地研究原问题(Primal)和对偶问题(Dual)我们可以得到很多性质颇好的结论。首先，我们引入一个假设：
假设1： 生产一件产品所需的材料的价格不小于出售该件产品所带来的收益。
之后我们简称生产某件产品所需的材料的价格为该产品的材料成本。对于该假设我们可以作如下理解：
- 首先，我们引入的所有假设的目的都是为了解原LP问题，故引入新的变量不能改变原LP问题的最大值。只对数学模型感兴趣的同学可以直接跳过之后的三点。
- 假设在此问题中，工厂本来就有一定数量的各种材料。生产一件产品的成本不包括材料成本。
- 在此假设下，购入更多的原材料只会使总收益变少，所以原LP问题的最大值不变。
- 如果该假设不成立，那么该工厂就可以从市场中无限地买入原材料进而获得无限的利益。由于市场存在竞争，这种情况是不允许出现的。
其实在思考本假设的意义时我也有很多疑问，当然可能我现在对于此问题的理解仍然是错误的。我们不妨先默认这些看似不合理直观的假设，推得我们想要的理论，之后再严谨地用数学方法证明理论的合理性即可。当然，感兴趣的同学也可以参考经济学领域的相关书籍。
不论如何，我们不应在直观理解上浪费太多时间。我们现在引出原问题与对偶问题的形式：
原问题与对偶问题
左边为原问题，右边为对偶问题。首先可以注意到的是对偶问题的限制条件即假设1。此时有显然的关系式：左边的不等号对应于对偶问题的限制条件，右边的不等号则对应原问题的对偶条件。因此两边目标函数存在关系：
是显然的。这其实就是待会要提到的弱对偶性。
原问题与对偶问题的矩阵表示如下图所示：
原问题与对偶问题的矩阵表示
由此可知对偶问题的对偶问题就是原问题。即两问题互为对偶。
2. 弱对偶性与强对偶性定理
关于对偶性，最关键的理论就是以下两个重要的定理：
定理1 （弱对偶性） 假设
与
分别是原问题与对偶问题的可行解，则：
证明：由限制条件可知：
证明完毕。
由弱对偶性可知：
- 若原问题的目标函数无界，则对偶问题必无可行解；同理若对偶问题的目标函数无界，则原问题必无可行解。注意前者的无界是无上界而后者的无界是无下界。若产品的收益都为正，则目标函数无界等价于可行域无界。
- 书上说原问题和对偶问题都无可行解的情况是存在的。不过我还没有想到这样的例子。
定理2 （强对偶性） 假设
且满足
其中
与
分别对应着原问题与对偶问题中的松弛变量。
我们现在还无法证明这个定理。
3. 原问题与对偶问题的性质
为了证明强对偶性定理并得到一些我们需要的性质，在此先叙述一些相对简单的概念与结论。由于原问题与对偶问题实际上互为对偶，故不失一般性地可以只叙述原问题的性质。
性质1： 原问题中每一个等号-限制条件都对应一个无符号限制的对偶变量。
此处“等号-限制条件”的含义应该是清晰的。原问题中的每一条限制条件都对应着一个对偶变量，这一点大家也需要牢记。强调以下几点：
- 如果原问题中采用的是
-限制条件，则无符号限制的对应对偶变量会导致弱对偶性定理失效。因为负号会使不等式转向。对于
-限制条件也一样。现考虑例1中木材的限制条件对应的对偶变量（即木材的价格
）：
如果不要求
的话显然无法推出
。
- 如果原问题中的某条限制条件是等号-限制条件，则称该限制条件为紧(tight)的。这个概念之后还会用到。
- 若原问题中某条限制是等号-限制条件则不论对应的对偶变量如何取值，弱对偶性仍然成立。依然考虑例1中的木材，但此时将其限制条件改为等号-限制条件，则有：
即仍满足弱对偶性。
- 类比地可以总结出规律：对于一个求最大值的LP问题，
接下来介绍互补松弛的概念。
定义1：称向量
与
是互补的(complementary)，若：
关于互补，有如下性质：
- 强对偶性说明原问题的最优解与对偶问题的解是互补的。
- 对于互补的向量
则原问题的第i个限制条件为紧的。同理若
则对偶问题的第i个限制条件是紧的。
-
对于任意基本解
与之互补。证明如下：
命题1：对于LP问题的任意基本解
证明：明天再说！
关于互补松弛性，有以下几点重要的性质。先不加证明地列出：
设
- 若
- 若
- 存在对偶问题的可行解
结合命题1可知：
若
如本文开头所言，判断最优性的问题被巧妙地转化为了判断可行性地问题。
