运筹学第2章1：线性规划的对偶理论及其应用

1、第二章线性规划的对偶理论及其应用,窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象,2,2.1 线性规划的对偶理论 2.1.1 线性规划原问题与对偶问题的表达形式,任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义,假设有商人要向厂方购买资源A和B，问他们谈判原料 价格的模型是怎样的？,3,例2.1.1,设A、B资源的出售价格分别为 y1 和 y2 显然商人希望总的收购价越小越好 工厂希望出售资源后所得不应比生产产品所得少,目标函数 min g(y)=25y1+15y2,4,2.1.1 线性规划原问题与对偶问题的表达形式,5,2.1.1 线性规划原问题与对偶问题的表达形式,6,2.1

2、.2 标准(max,)型的对偶变换,目标函数由 max 型变为 min 型 对应原问题每个约束行有一个对偶变量 yi，i=1,2,m 对偶问题约束为 型，有 n 行 原问题的价值系数 C 变换为对偶问题的右端项 原问题的右端项 b 变换为对偶问题的价值系数 原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵 原问题与对偶问题互为对偶 对偶问题可能比原问题容易求解 对偶问题还有很多理论和实际应用的意义,2.1.3 非标准型的对偶变换,8,表2.1.1 对偶变换的规则,约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的,9,2.2 线性规划的对偶定

3、理,2.2.1 弱对偶定理 定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值,为了便于讨论，下面不妨总是假设,10,弱对偶定理推论,max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限 如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解 如果原max(min)问题有可行解，其对偶 min (max)问题无可行解，则原问题为无界解 注：存在原问题和对偶问题同时无可行解的情况,11,2.2.2 最优解判别定理,定理 若原问题的某个可

4、行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解 证：由弱对偶定理推论1，结论是显然的。 即CX0 = Y0b CX, Y0b = CX0 Yb 。 证毕。,2.2.3 主对偶定理 定理 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。 证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。 现证明定理的后一句话。,12,主对偶定理的证明,证：现证明定理的后一句话。 设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B1 b，则其检验数满足 C CBB1A 0 令 Y0= C

5、BB1，则有 Y0 A C。 显然Y0为对偶问题的可行解。因此有对偶问题目标函数值， g(Y0)=Y0b= CBB1 b 而原问题最优解的目标函数值为 f(X0)=CX0= CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。 该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本 即对偶变量的最优解是原问题资源的影子价格,13,2.2.4 互补松弛定理,定理 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 =

6、 0 证：由定理所设，可知有 A X0 + U0 = b X0, U0 0 (1) Y0 A V0 = C Y0, V0 0 (2) 分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0 + V0 X0 = Y0 b C X0 若 Y0 U0 + V0 X0 = 0，根据最优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。 证毕。,14,2.2.5 原问题检验数与对偶问题的解,在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值 容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验

7、数的绝对值 由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。 更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余) 的检验数对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。,15,例2.2.3 原问题检验数与对偶问题的解,16,17,18,2.3 对偶单纯型算法 2.3.1 基本思路,原单纯型迭代要求每步都是基础可行解 达到最优解时，检验数 cjzj 0 (max) 或 cjzj 0 (min) 但对

8、于(min, )型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决 大M法和二阶段法较繁 能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件， cjzj 0 (max) 或 cjzj 0 (min) 每步迭代保持检验数满足最优条件，但减少非可行度 如何判断达到最优解 如何保证初始基础解满足最优条件 为什么叫对偶单纯型法,19,2.3.2 迭代步骤,确定出变量 找非可行解中最小者，即 min bi | bi0，设第 i*行的最负，则i*行称为主行，该行对应的基变量为出变量，xi* 确定入变量 最大比例原则,设 j* 列满足(2.3.1)式， j* 列称为主列，x

9、j* 为出变量 以主元 ai*j* 为中心迭代 检查当前基础解是否为可行解 若是，则当前解即为最优解 否则，返回 步骤 1,20,例2.3.1 对偶单纯型解法,解：化原问题为适合对偶解法的标准型,21,表2.3.1 对偶单纯型法的单纯型表(min),答：最优解为x1=14, x3=8, x2=x4=0, OBJ=14,习 题 课,学而时习之，不亦乐乎 论语,23,第 1 题,解：设车间 1 生产x1A单位A、生产x1B单位B； 设车间 2 生产x2A单位A、生产x2B单位B； 设车间 3 生产x3A单位A、生产x3B单位B； 则有生产安排最优化的模型如下：,24,第 2 题,解： 设 x1A 为饮料甲中A的总含量 (升) 设 x2A 为饮料乙中A的总含量 (升) 设 x3A 为饮料丙中A的总含量 (升) 设 x1B 为饮料甲中B的总含量 (