下载掌阅APP，畅读海量书库
立即打开
对偶理论是线性规划的重要组成部分，其主要内容是：每一个线性规划问题都伴随着一个被称为其对偶问题的线性规划问题，它们之间有着十分密切的关系，并具有一些很有价值的性质。由对偶问题引申出来的对偶最优解是进一步揭示线性规划模型经济含义的重要工具。
例 1 对偶问题的提出。
在第 2 章例 1 中讨论了工厂生产计划问题，该问题从使用有限资源组织生产，以追求最大利润的角度得到了下列线性规划模型:
现在从另一角度来讨论问题。假设该工厂的厂主决定不生产产品A和B,而将其所有资源出租或出售，这时，厂主就要考虑每种资源应如何定价的问题，为此，他可以构造如下的数学模型。
设 y 1 、 y 2 、 y 3 分别表示出租单位劳动力、单位设备台时的租金、出让单位原材料的附加额(附加额=出售价格-成本）。厂主在作定价决策时，会考虑到出租和出让资源所得到的收入应不低于用这些资源进行生产所得到的利润。具体来说，若用 9 个单位劳动力、4 个单位设备台时和 3 个单位原材料可以生产一单位产品A而获利 70 元，那么就应有:
同理，对产品B作类似分析也应有:
把工厂所有的资源都出租和出售，其总收入为 ω = 360 y 1 + 200 y 2 + 300 y 3 ,表面上看, ω 越大越好，但实际上定价太高会失去竞争能力。在保证出租出售资源不会比自己生产获利少的前提下，为了使工厂的竞争能力达到最大，应该极小化总收入 ω 。为此需解如下线性规划问题:
(3.1)与(3.2)这两个问题都是为了提高工厂的经济效益，但从两个不同角度出发而形成的一对线性规划问题。我们称(3.2)为(3.1)的对偶(Dual)问题，称(3.1)为原(Primal)问题。
从上面的例子可以看出，原问题和对偶问题在形式上有着密切的关系：其中一个问题为求max且约束条件是“≤”形式，另一个问题为求min且约束条件是“≥”形式；两者的目标函数系数与约束条件的右端项以及约束条件与变量之间是相对应的，而约束条件的系数矩阵互为转置(这里所说的约束条件不包含变量非负条件)。
一般来说，给定线性规划问题:
则其对偶问题为:
原问题和对偶问题还可写为较简洁的矩阵形式:
其中 Y = ( y 1 ,…, y m ),其余符号的意义如第 2 章所述。
需要强调的是，当我们讨论对偶问题时一定是指一对问题，而原问题和对偶问题的界限也无严格划分，实际上，它们互为对偶，谁都可以是原问题，也可以是对偶问题。下一小节给出的对偶问题的对称性说的就是这个道理。
求一个任意给定的线性规划问题的对偶问题，原则上可以先将它等价地转化为(3.3)的形式，再按(3.4)的形式写出其对偶问题，然后化简。但这样做太麻烦，更简便的办法是按表3 -1 所示的对应关系直接写出给定问题的对偶问题。这里不对表 3 -1 作详细推导。
表 3 -1对偶关系对应表
例 2 写出下列问题的对偶问题。
解：设对应于约束条件的对偶变量分别为 y 1 , y 2 , y 3 ,则由表3 -1 (注意这里的原问题是求min,故使用表3 -1 时应从表的右边部分对应到左边部分）可以得到所求的对偶问题为:
进一步思考 :应用表 3 -1 求最小化问题的对偶问题要特别注意什么问题?
下面介绍对偶问题的一些基本性质，这些性质的证明除了对偶定理和互补松弛性以外都比较简单，有兴趣的读者可参考有关书籍。
在一对对偶问题中，存在以下的关系:
(1)对称性：对偶问题的对偶是原问题。
(2)弱对偶性：求max问题的可行解的目标值不可能超过求min问题的可行解的目标值。
(3)无界性：若其中一个问题无界，则另一个问题不可行。
(4)对偶定理：若其中一个问题有最优解，则另一个问题也有最优解，并且它们目标函数的最优值相等。特别是若原问题的最优基为 B ,则其对偶问题的最优解为 Y ∗ = C B B - 1 。
(5)互补松弛性(松紧定理）：设 X (0) 和 Y (0) 分别是问题(P)和(D)的可行解，则它们都是最优解的充分必要条件是：对于 j = 1,2,…, n 和 i = 1,2,…, m ,有:
请读者注意
≥
c
j
和
j
≤
b
i
分别为问题(D)和(P)的约束条件。
如果一个不等式约束成为严格等式，则称它是紧的，否则称为松的。这样，互补松弛性表明，一对对偶问题达到最优当且仅当：松约束(或变量）对应的对偶变量(或约束）必定是紧的。
例 3 给定线性规划问题。
试通过求解其对偶问题找出原问题的最优解。
解：对偶问题为:
由于对偶问题只有两个变量，可以用图解法(第 2 章 2.1.2 小节）求出其最优解
,
和最优值
ω
∗
= 5。
将
,
代入约束条件，可见第 2、第 3 和第 4 个约束条件是松的，由互补松弛性得
=
=
= 0。又因
,
> 0,故原问题的两个约束应取等式，即有
+
= 4 和
+
= 3,从而解得
= 1,
= 1。因此，原问题的最优解为
X
∗
= (1,0,0,0,1)
T
,最优值
z
∗
= 5。
下面介绍如何从原问题的最优单纯形表直接找到对偶问题的最优解。记某标准线性规划问题的初始基变量组为 X IB , X IB 在目标函数中的各系数为 C IB ,在最优单纯形表中 X IB 的各检验数为 σ IB ,则经过计算可得到对偶问题的最优解为 Y ∗ = C IB - σ IB 。
以第 2 章例 1 来说明(见表 2 -4),在该例中,
X
IB
= (
x
3
,
x
4
,
x
5
),
C
IB
= (0,0,0),
σ
IB
= (0,-13.6,-5.2),由此可得到对偶问题最优解为
Y
∗
= (0,13.6,5.2),即
= 0,
= 13.6,
= 5.2。
最后简单谈谈对偶问题在计算上的应用。由对偶问题的性质我们发现，对于一对对偶问题，只要求出其中的一个解，另一个的解也就求出来了。因此，如果你要求的问题比较复杂，而它的对偶问题比较简单，那么你可以去求解后者，同样能得到原问题的解。这里要提到实际计算中的一个经验，即解一个线性规划所需的时间更多的是取决于约束条件的数目而不是变量的数目。如果原问题有 m 个约束条件和 n 个变量，则对偶问题有 n 个约束条件和 m 个变量。所以，一般来说，你应当选择约束条件少的问题来进行求解。下面举一例说明。
例 4 求解下列线性规划问题。
解：如果直接解这个问题则需引入 6 个剩余变量和 6 个人工变量，求解较烦琐。但若解它的对偶问题:
很明显就简单得多了。
我们用计算机直接解原问题要迭代 7 次，但解其对偶只需迭代 4 次，而且前者的单纯形表的规模比后者大。本例的最优解为 X ∗ = (1.513,0.026,0.239 ) T ,最优值 z ∗ = 24.684。
另外，借助对偶理论还可以设计出两种新的算法——对偶单纯形法和原始对偶算法，我们主要是使用计算机求解问题，故不作介绍。
考虑使用 m 种资源生产 n 种产品以获得最大利润的生产计划问题。这个问题可用(3.3)式的线性规划来表示，其中 c j 为第 j 种产品的单位利润, b i 为第 i 种资源的限额, a ij 是每生产单位产品 j 所消耗的资源 i 的数量，决策变量 x j 表示产品 j 的产量(假定产品畅销)。
该问题的最优解
X
∗
= (
,…,
)
T
表示最优生产方案，最优值
z
∗
=
为相应的最大利润。一般来说，资源限额
b
i
的变化将引起目标最优值
z
∗
的变化。在其他条件不变的情况下，第
i
种资源的限额
b
i
增加一个单位所引起的目标最优值的改变量称为该资源的影子价格。从数学上来说，资源
i
的影子价格等于
z
∗
对
b
i
的变化率，即
由对偶定理
其中
Y
∗
= (
,…,
)为对偶问题最优解。在(3.5)式中求
z
∗
对
b
i
的偏导数得:
,
i
= 1,…,
m
。
所以，对偶最优解是各资源的影子价格。
影子价格是当系统达到最优状态时对资源价格的一种估价。例如，现实中的影子银行的资金成本才是市场对资金价值的真实估价。对于同一种资源来说，不同的企业因各自的工艺、技术和管理水平不同，会有不同的影子价格。就某一个企业而言，其内部生产情况的变化也会引起资源影子价格的变化。影子价格的大小客观地反映资源的稀缺程度，在最优利用条件下如果某资源有剩余，尽管它有实实在在的市场价格，但它的影子价格必定为零。这一事实表明，增加该资源的供应量无助于总收益的提高。如果某资源是稀缺资源，其影子价格必然大于零。影子价格越高，资源就越稀缺，对生产活动的制约性就越强。当某种资源的影子价格高于其市场单价时，企业应买进资源扩大生产；相反，应该减少该资源的供应量。
以第 2 章例 1 来说明，劳动力工时、设备台时和原材料的影子价格分别为 0、13.6、5.2 元。这说明在其他条件不变的情况下，若设备增加一台时，该厂按最优计划安排生产可多获利 13.6 元；原材料增加 1 千克，可多获利 5.2 元；而增加劳动力对获利无影响。因此，如果工厂能以每台时低于 13.6 元的租金借用额外的设备台时来扩大生产，将会增加其总利润，至于租借的台时数应根据影子价格的有效范围来确定。所谓资源
i
的影子价格
的有效范围，是指在这个范围内，若资源
i
的限额增加(或减少)
Δ
个单位，则目标最优值增加(或减少）的量为
×
Δ
,这个问题将在下一节灵敏度分析中讨论。
两点说明:
(1)在一般线性规划模型中，并非所有的约束都是资源约束，但每个约束条件对应的对偶解分量
都可以解释为目标最优值
z
∗
对右端项
b
i
的变化率，即
b
i
增加一个单位时
z
∗
的改变量。
的符号可为正，也可为负，故随着
b
i
的增加,
z
∗
可能增加，也可能减少。
(2)大多数的计算机软件打印输出中的影子价格是当右端项增加时目标最优值的改进率而不是变化率。改进的意思在最大化模型中是增加的，在最小化模型中则是减少的。由此不难看出，对于max问题，打印输出的影子价格=对偶解；对于min问题，打印输出的影子价格= -对偶解。