窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象

Presentation on theme: "窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象"— Presentation transcript:

1 窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象
第四章　对偶原理 窗含西岭千秋雪，门泊东吴万里船 对偶是一种普遍现象

2 甲　乙　丙　丁 材料 产品 ３　２　１　１ ４　１　３　２ ２　２　３　４ A B C 每台 收益 2000 4000 3000 限额 x1 x2 x3 y1　y2　y3　y4 假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业，工厂希望给这些资源定出一个合理的价格，即使别的单位愿意购买，又使本工厂能得到生产这些产品所能获得的最大收益。

3 二、对偶问题的表达 （1）对称LP问题的定义 第一类对称形式 第二类对称形式 （2）对称LP问题的对偶问题 (D) (L)

4 例1：写出下列LP问题的对偶问题 对偶

5 （3）对偶问题的对偶 推导过程 (D) 变形

6 对偶 变形 (DD) 结论：对偶问题的对偶为原问题。

7 例2： 写出下列LP问题的对偶问题：

8 写出对称形式的对偶规划的要点： (1) min变成max (2) 价值系数与右端向量互换 (3) 系数矩阵转置 (4) ≥ 变 ≤
(2) 价值系数与右端向量互换 (3) 系数矩阵转置 (4) ≥ 变 ≤ 原问题中约束条件的个数=对偶问题中变量的个数 原问题中变量的个数=对偶问题中约束条件的个数

9 非对称形式的对偶 写成对称形式 对偶问题为：

10 例 min 5x1+4x2+3x3 s.t. x1+x2+x3=4 3x1+2x2+x3 =5 x1 ≥ 0, x2 ≥0, x3 ≥0 对偶问题为 max 4w1+5w2 s.t. w1+3w2≤5 w1+2w2 ≤ 4 w1+w2 ≤ 3

11 一般情形LP问题的对偶问题 min cx s.t. A1x ≥b1 A1 为m1×n , b1为m1×1
引入松弛变量 s.t. A1x –xs =b1 xs为m1×1 A2x =b2 A3x xt = b3 xt为m3×1 x, xs , xt ≥0

12 min cx s.t. A1x –xs =b xs为m1×1 A2x =b2 A3x xt = b xt为m3×1 x, xs , xt ≥0 对偶问题为 max w1b1+ w2b2 + w3b3 s.t. w1A1+ w2A2 + w3A3 ≤c – w1Is ≤0 w3It ≤0 w1 ≥ 0, w3 ≤0

13 min max 变 ≥ ≤ 约 量 ≤ ≥ 束 无限制 = 方 程 约 ≥ ≥0 束 ≤ ≤ 变 方 = 无限制 量

14

15 直接写出LP问题的对偶问题 例3

16

17 第二节 对偶问题的基本性质 原问题(L) 对偶问题(D) min cx max wb s.t. Ax ≥ b s.t. wA ≤ c x ≥ w ≥ 0

18 定理1：弱对偶定理

19 例： （LP） 1）原问题任一可行解 x=(1, 1)T 目标值 =40 40是DLP问题最优目标值的上界. 2）对偶问题任一可行解 w=（ ） 目标值 =10 10是LP问题最优目标值的下界.

20 推论1： 若LP(或DLP)问题有无界解，则其对偶问题(或原问题)无可行解； 若LP (或DLP)问题无可行解，则对偶问题(或原问题)或者无可行解,或者目标函数值趋于无穷。 推论2： 极大化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的下界。 推论3： 极小化问题的任何一个可行解所对应的目标 函数值都是其对偶问题的目标函数值的上界。

21 定理2：最优性准则 证明：

22 例5

23 若(L),(D)均有可行解,则(L),(D)均有最 优解,且(L),(D)的最优目标函数值相等.
定理3：强对偶定理 若(L),(D)均有可行解,则(L),(D)均有最 优解,且(L),(D)的最优目标函数值相等. 证明：

24 (L) 引入剩余变量，把(L)化为标准形．

25

26 推论： 在用单纯形法求解LP问题（L）的最优单纯 形表中松弛变量的检验数的相反数(单纯形 乘子w=cBB-1)就是其对偶问题（D）的最优解

27 方法 由于(L) 化成标准形式时,松弛变量xn+j对应的列为-ej，它在目标函数中的价格系数＝０，所以，
判别数＝cBB-1(-ej)-0=-wj 则松弛变量对应的判别数均乘以(-1)，变得到单纯形乘子w=(w1,…,wm). 当原问题达最优时,单纯形乘子即为对偶问题的最优解.

28 例5 求下列问题对偶问题的最优解 解：化为标准型

29 x x x x x5 x3 x4 x5 8 16 12 4 /2 /4 /4 x3 x4 x2 2 16 3 9 1

30 x x x x x5 /2 /4 /4 x1 x4 x2 2 8 3 13 2 / / / / / / x1 x5 x2 4 2 14 此时达到最优解。x*=(4,2), MaxZ=14。

31 (L) (DL)

32 小结 原问题(min) 对应关系 对偶问题(max) 有最优解 有最优解 不可行 无界解 无界解 不可行

33 x1 x2 l1 l2 （无可行解） w1 w2 l2 l1 （无可行解）

34 l2 x1 x2 l1 z （无界解） y1 y2 l1 l2 （无可行解）

35 定理4：互补松驰定理

36 证明：（必要性）

37 证明：（充分性）　

38 定理4’：互补松驰定理(非对称形式）

39 例6 考虑下面问题

40 解: 则， 好

41 考虑在最优解处,右端项bi的微小变动对目标函数值的影响.
对偶问题的经济学解释：影子价格 1、定义 2、含义 考虑在最优解处,右端项bi的微小变动对目标函数值的影响.

42 若把原问题的约束条件看成是广义的资源约束,则右端项的值表示每种资源的可用量.
对偶解的经济含义:资源的单位改变量引起目标函数值的增加量. 通常称对偶解为影子价格. 影子价格的大小客观地反映了资源在系统内的稀缺程度.资源的影子价格越高,说明资源在系统内越稀缺,而增加该资源的供应量对系统目标函数值贡献越大.

43 0 0 2 24 1440 木门 木窗 木工 4小时 3小时 120小时/日 油漆工 2小时 1小时 50小时/日 收入 56 30
木门 木窗 木工 小时 小时 小时/日 油漆工 小时 小时 小时/日 收入 解：设该车间每日安排 x1 x2 x3 x4 生产木门x1扇，木窗x2。 x max z=56 x1 +30 x x s.t x1 +3 x2≤ 2 x1 + x2 ≤ x x1 x2 ≥ x / / x x /2 -1/2 15 对偶问题的解为: w*=(2, 24)

44 3、影子价格的作用 （1）告诉管理者增加何种资源对企业更有利 （2）告诉管理者花多大代价购买进资源或卖出资源是合适的
（3）为新产品定价提供依据

45 对偶单纯形法 定义：设x(0)是(L)的一个基本解（不一定是可行解），它对应的矩阵为B，记w=cBB-1，若w是(L)的对偶问题的可行解，即对任意的j, wPj-cj ≤0，则称x(0)为原问题的对偶可行的基本解。 结论：当对偶可行的基本解是原问题的可行解时，由于判别数≤0，因此，它就是原问题的最优解。

46 基本思想： 从原问题的一个对偶可行的基本解出发； 求改进的对偶可行的基本解：每个对偶可行的基本解x=(xBT,0)T对应一个对偶问题的可行解w=cBB-1，相应的对偶问题的目标函数值为wb=cBB-1b，所谓改进的对偶可行的基本解，是指对于原问题的这个基本解，相应的对偶问题的目标函数值wb有改进（选择离基变量和进基变量，进行主元消去）； 当得到的对偶可行的基本解是原问题的可行解时，就达到最优解。

47 与原单纯形法的区别： 原单纯形法保持原问题的可行性，对偶单纯形法保持所有检验数wPj-cj ≤0，即保持对偶问题的可行性。 特点：先选择出基变量，再选择进基变 量。

48 步骤： 1. 化标准型,建立初始单纯形表 3、换基迭代 (若所有yrj≥0,则该LP无可行解） 4、回到第2步

49

50

51 x x x x x5 x4 x5 -1 -2 -4 -13/ / /4 -1/ / /4 -5/ / /4 x4 x2 -1/2 1/2 -13/4 / / /13 / / /13 / / /13 x1 x2 2/13 7/13 9/13

52 用对偶单纯形法求解下列LP问题 解：原问题变形为

53 x x x x x x6 x4 x5 x6 -4 8 -2 -1 x1 x5 x6 4 -2 -1 x1 x5 x2 6 2 10

54 关于初始对偶可行的基本解 min cx s.t. Ax=b x ≥0
若初始对偶可行的基本解不易直接得到，则解一个扩充问题，通过这个问题的求解，给出原问题的解答。

55 方法 附加人工约束

56

57

58 x x x x x5 x1 x2 x3 2 3 -2 显然， （2，3，-2，0，0） 不是对偶可行解， 所以加一个约束

59

60 方法一 x x x x x x6 x1 x2 x3 x6 2 3 -2 M 1 x1 x2 x3 x4 2-M 3+3M M-2 M -2M -1 最优解为 (0,9,0,2,0) 最优值=-4 -4 x6 x2 x3 x4 M-2 9 2

61 x1 x2 x3 x4 x5 x6 方法二 x1 x2 x3 x6 x1 x2 x3 x4 x5 x2 x3 x4
2 3 -2 M 1 x1 x2 x3 x4 -3 2-M 3+3M M-2 M -2M x5 x2 x3 x4 -1/ /3 (M-2)/3 17/3+5M/3 M-2 2/3+2M/3 -4/ /3 1/ /3 -4

62 扩充问题有最优解 最优值=-4 原问题最优解为 原问题最优值=-4 最优值=-4

63 用对偶单纯形法解下列问题

64 最优表为: 扩充问题的最优解是:

65 原始-对偶算法 基本思想： 从对偶问题的一个可行解开始，同时计算原问题和对偶问题，试图求出原问题的满足互补松弛条件的可行解。

66 原问题： 对偶问题：

67 限定原始问题 Restricted primal problem 人工变量

68 限定原始问题的对偶问题

69

70

71 由于对偶问题无上界，所以原问题无可行解。

72 计算步骤

73

74 限定原始问题目标函数值 对偶问题函数值f=wb 对偶问题可行解为w时所有的wpj-cj

75 用原始-对偶算法解下列问题 解：对偶问题为

76 限定原始问题为：

77 △

78 4 2 3 1 8 5 - y x △ 1

79 4 2 3 1 -2 -1 - y x △

80 △ １ △