运筹学 Operational Research 数学科学学院 许成.

Presentation on theme: "运筹学 Operational Research 数学科学学院 许成."— Presentation transcript:

1 运筹学 Operational Research 数学科学学院 许成

2 第二章 线性规划的对偶理论及其应用

3 2.1 线性规划的对偶理论 2.1.1 线性规划原问题与对偶问题的表达形式
2.1 线性规划的对偶理论 线性规划原问题与对偶问题的表达形式 任何线性规划问题都有其对偶问题 对偶问题有其明显的经济含义 假设有商人要向厂方购买资源A和B，问他们谈判原料 价格的模型是怎样的？

4 例2.1.1 设A、B资源的出售价格分别为 y1 和 y2 显然商人希望总的收购价越小越好 工厂希望出售资源后所得不应比生产产品所得少 目标函数 min g(y)=25y1+15y2

5 2.1.1 线性规划原问题与对偶问题的表达形式

6 2.1.1 线性规划原问题与对偶问题的表达形式

7 2.1.2 标准(max,)型的对偶变换 目标函数由 max 型变为 min 型 对应原问题每个约束行有一个对偶变量 yi，i=1,2,…,m 对偶问题约束为  型，有 n 行 原问题的价值系数 C 变换为对偶问题的右端项 原问题的右端项 b 变换为对偶问题的价值系数 原问题的技术系数矩阵 A 转置后成为对偶问题的技术系数矩阵 原问题与对偶问题互为对偶 对偶问题可能比原问题容易求解 对偶问题还有很多理论和实际应用的意义

8 2.1.3 非标准型的对偶变换

9 表2.1.1 对偶变换的规则 约束条件的类型与非负条件对偶 非标准的约束条件类型对应非正常的非负条件 对偶变换是一一对应的

10 2.2 线性规划的对偶定理 为了便于讨论，下面不妨总是假设 2.2.1 弱对偶定理 定理 对偶问题(min)的任何可行解Y0，其目标函数值总是不小于原问题(max)任何可行解X0的目标函数值

11 弱对偶定理推论 max问题的任何可行解目标函数值是其对偶min问题目标函数值的下限； min问题的任何可行解目标函数值是其对偶max问题目标函数值的上限 如果原max(min)问题为无界解，则其对偶 min (max)问题无可行解 如果原max(min)问题有可行解，其对偶 min (max)问题无可行解，则原问题为无界解 注：有可能存在原问题和对偶问题同时无可行解的情况

12 2.2.2 最优解判别定理 定理 若原问题的某个可行解X0的目标函数值与对偶问题某个可行解Y0的目标函数值相等，则X0, Y0分别是相应问题的最优解 证：由弱对偶定理推论1，结论是显然的。 即CX0 = Y0b  CX, Y0b = CX0  Yb 。 证毕。 2.2.3 主对偶定理 定理 如果原问题和对偶问题都有可行解，则它们都有最优解，且它们的最优解的目标函数值相等。 证：由弱对偶定理推论1可知，原问题和对偶问题的目标函数有界，故一定存在最优解。 现证明定理的后一句话。

13 证：现证明定理的后一句话。 主对偶定理的证明
设 X0 为原问题的最优解，它所对应的基矩阵是 B， X0= B1 b，则其检验数满足 C  CBB1A  0 令 Y0= CBB1，则有 Y0 A  C ；而对原问题松弛变量的检验数有 0  CBB1I  0，即 Y0  0 。 显然Y0为对偶问题的可行解。因此有对偶问题目标函数值， g(Y0)=Y0b= CBB1 b 而原问题最优解的目标函数值为 f(X0)=CX0= CBB1 b 故由最优解判别定理可知Y0 为对偶问题的最优解。证毕。 该定理的证明告诉我们一个非常重要的概念：对偶变量的最优解等于原问题松弛变量的机会成本 即对偶变量的最优解是原问题资源的影子价格

14 2.2.4 互补松弛定理 定理 设X0, Y0分别是原问题和对偶问题的可行解，U0为原问题的松弛变量的值、V0为对偶问题剩余变量的值。X0, Y0分别是原问题和对偶问题最优解的充分必要条件是 Y0 U0 + V0 X0 = 0 证：由定理所设，可知有 A X0 + U0 = b X0, U0  (1) Y0 A  V0 = C Y0, V0  (2) 分别以Y0左乘(1)式，以X0右乘(2)式后，两式相减，得 Y0 U0 + V0 X0 = Y0 b  C X0 若 Y0 U0 + V0 X0 = 0，根据最优解判别定理， X0, Y0分别是原问题和对偶问题最优解。反之亦然。 证毕。

15 若(Y0 )i >0，则 (U0 )i =0，意味着原问题第 i 约束行必须为 = 约束；对(X0 )i >0 亦如此
2.2.4 互补松弛定理 Y0 U0 + V0 X0 = 0 有什么应用 若(Y0 )i >0，则 (U0 )i =0，意味着原问题第 i 约束行必须为 = 约束；对(X0 )i >0 亦如此 可用来简化问题的求解 线性规划的高级算法：利用互补松弛定理，原问题与对偶问题同时解 原问题为基础可行解，对偶问题为非可行解，但满足互补松弛条件；则当对偶问题为可行解时，取得最优解

16 2.2.5 原问题检验数与对偶问题的解 在主对偶定理的证明中我们有：对偶(min型)变量的最优解等于原问题松弛变量的机会成本，或者说原问题松弛变量检验数的绝对值 容易证明，对偶问题最优解的剩余变量解值等于原问题对应变量的检验数的绝对值 由于原问题和对偶问题是相互对偶的，因此对偶问题的检验数与原问题的解也有类似上述关系。 更一般地讲，不管原问题是否标准，在最优解的单纯型表中，都有原问题虚变量(松弛或剩余) 的机会成本对应其对偶问题实变量 (对偶变量)的最优解，原问题实变量(决策变量) 的检验数对应其对偶问题虚变量 (松弛或剩余变量)的最优解。因此，原问题或对偶问题只需求解其中之一就可以了。

17 例2.2.3 原问题检验数与对偶问题的解

18

19

20 2.3 对偶单纯型算法 2.3.1 基本思路 原单纯型迭代要求每步都是基础可行解
2.3 对偶单纯型算法 基本思路 原单纯型迭代要求每步都是基础可行解 达到最优解时，检验数 cj–zj 0 (max) 或 cj–zj 0 (min) 但对于(min, )型所加的剩余变量无法构成初始基础可行解，因此通过加人工变量来解决 大M法和二阶段法较繁 能否从剩余变量构成的初始基础非可行解出发迭代，但保证检验数满足最优条件， cj–zj 0 (max) 或 cj–zj 0 (min) 每步迭代保持检验数满足最优条件，但减少非可行度 如何判断达到最优解 如何保证初始基础解满足最优条件 为什么叫对偶单纯型法 b=B1b0

21 设 j* 列满足(2.3.1)式， j* 列称为主列，xj* 为出变量 以主元 ai*j* 为中心迭代 检查当前基础解是否为可行解
2.3.2 迭代步骤 确定出变量 找非可行解中最小者，即 min{ bi | bi<0}，设第 i*行的最负，则i*行称为主行，该行对应的基变量为出变量，xi* 确定入变量 最大比例原则 设 j* 列满足(2.3.1)式， j* 列称为主列，xj* 为出变量 以主元 ai*j* 为中心迭代 检查当前基础解是否为可行解 若是，则当前解即为最优解 否则，返回 步骤 1

22 令 xr 为出变量，在第i*行；若选非基变量 xj* 为入变量
最大比例原则 令 V=C -CBB-1A 为检验数向量 对 min 问题，V  0 称为正则，即满足最优判定条件 可以证明，V 的迭代也满足四角运算法则 令 xr 为出变量，在第i*行；若选非基变量 xj* 为入变量 必须满足什么条件才能保证迭代后的解仍为正则的？ 若 xj 仍为基变量，则可知 ai*j =0 , 因此只需考虑 非基变量 xj 观察出变量 xr 对应的检验数变化，因为有 ai*r =1，故 由于 vj*  0，故必有 ai*j* < 0，即主元必须为负值

23 最大比例原则 若 xj 为非基变量，则当ai*j > 0 时，显然有 若 ai*j < 0 时，则要求 vj - vj* ai*j / ai*j*  0, 可解出 结合上述的几个条件，则得到最大比例原则 注：这里的 aij 都表示当前单纯性表中的技术系数

24 例2.3.1 对偶单纯型解法 解：化原问题为适合对偶解法的标准型

25 表2.3.1 对偶单纯型法的单纯型表(min) 答：最优解为x1=14, x3=8, x2=x4=0, OBJ=14

26 习 题 课 学而时习之，不亦乐乎 — 《论语》

27 第 1 题 解：设车间 1 生产x1A单位A、生产x1B单位B； 设车间 2 生产x2A单位A、生产x2B单位B； 设车间 3 生产x3A单位A、生产x3B单位B； 则有生产安排最优化的模型如下：

28 第 2 题 解： 设 x1A 为饮料甲中A的总含量 (升) 设 x2A 为饮料乙中A的总含量 (升) 设 x3A 为饮料丙中A的总含量 (升) 设 x1B 为饮料甲中B的总含量 (升) 设 x2B 为饮料乙中B的总含量 (升) 设 x3B 为饮料丙中B的总含量 (升) 设 x1C 为饮料甲中C的总含量 (升) 设 x2C 为饮料乙中C的总含量 (升) 设 x3C 为饮料丙中C的总含量 (升) 则有模型如下：

29

30 第 3、4 题 标准型： 原问题： 对偶问题：