管理运筹学-03-对偶问题与灵敏度分析3

管理运筹学,每个章节的ppt,管理数学,工商管理系

管理运筹学

管理运筹学,每个章节的ppt,管理数学,工商管理系

第三讲

对偶问题与灵敏度分析

管理运筹学,每个章节的ppt,管理数学,工商管理系

对偶问题

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

一、问题的提出

一般性的资源交易问题，见P70。

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

二、对称形式下对偶问题的一般形式

定义: 满足下列条件的LP问题称为具有对称形式。

目标函数取最大时，约束条件为小于等于0,变量均为非负； 目标函数取最小时，约束条件为大于等于0,变量均为非负。

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

二、对称形式下对偶问题的一般形式

一般地，将求最大目标的LP问题称为原问题；将求最小目标的LP问题称为对偶问 题。对称形式下LP问题的一般形式为: 原问题: 对偶问题:

max z = c1 x1 + c2 x2 + ... + cn xn a11 x1 + a12 x2 + ... + a1n xn ≤ b1 a x + a x + ... + a x ≤ b 2n n 2 21 1 22 2 ...... a x + a x + ... + a x ≤ b mn n m m1 1 m 2 2 x j ≥ 0 ( j = 1,2,..., n)

min w = b1 y1 + b2 y2 + ... + bm ym a11 y1 + a21 y2 + ... + am1 ym ≥ c1 a y + a y + ... + a y ≥ c m2 m 2 12 1 22 2 ...... a y + a y + ... + a y ≥ c mn m n 1n 1 2 n 2 yi ≥ 0 (i = 1,2,..., m)

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

二、对称形式下对偶问题的一般形式

原问题:

对偶问题:

max z = CX

min w = bT Y

AX ≤ b X ≥ 0

AT Y ≥ C T Y ≥ 0

min z ' = CX max w' = bT Y

AX ≤ C X ≥ 010/22/2011

AT Y ≤ C T Y ≥ 0

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

三、非对称形式下对偶问题的一般形式

非对称形式的转换见P72

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

三、非对称形式下对偶问题的一般形式

[例]Max 3 2 6 0 1

Min 7 4 2≥ ≤ 7 4

2 1

1 4 0 2 0

1

3

2

1

1

≤ ≤ ≥ =

3 2 0 1

1 0 4 1

1 3

= 2

x1 , x2 , x3 ≥ 0; x4 ≤ 0; x5 free

1 0 3 4 2 0 1 1 4 3 0 1

≤ 6

≥ ≤

free

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

四、LP问题的矩阵表达

设经过若干次迭代之后，基变量为XB,XB在初始单纯型中对应的矩阵为B。

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

B 1b = B 1 AXC B B 1b = C B B 1 AXCB

cj 基 b XB

CXN

0Xs

Z C B B 1b = CX C B B 1 AX = (C C B B 1 A) XZ = C B B 1b + (C C B B 1 A) XB E

cj-zj

B 1b

E

B 1 N

B 1

z * = C B B 1b10/22/2011

cj-zj

C C B B 1 A

C B B 111

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

cj CB 0 0 0 基 x4 x5 x6 cj-zj b (b) 15 20

3 x1 1 (a) 2 3

2 x2 1 1 (c) 2 ……

2 x3 1 2 1 2

0 x4 1 0 0 0

0 x5 0 1 0 0

0 x6 0 0 1 0

0 3 2

x4 x1 x2 cj-zj

5/4 25/4 5/2

0 1 0 0

0 0 1 (k)

(d) (e) (f) (g)

(l) 0 0 0

-1/4 3/4 (h) -5/4

-1/4 (i) 1/2 (j)

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

四、对偶问题的基本性质

[1

.对称性]--对偶问题的对偶问题是原问题

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

四、对偶问题的基本性质 [2. 弱对偶性]若 X 为原问题的可行解， Y 为对偶问题的可行解，则恒有 CX ≤ bT Y 原问题： 原问题：

AX ≤ b

Y

T

AX ≤ Y T b

对偶问题： 对偶问题：

AT Y ≥ C T

YTA≥C

Y

T

AX ≥ CX

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

四、对偶问题的基本性质 [3. 最优性]若 X 为原问题的可行解， Y 为对偶问题的可行解，如 CX = bT Y ,此时两个可行 解同时达到最优。 设X* 为原问题的最优解，显然也是可行解，则：

CX * ≥ CX又：

CX * ≤ bT Y

CX = b T Y

CX * ≤ CX

CX * = CX

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

四、对偶问题的基本性质 [4. 强对偶性-(对偶定理)]若原问题有最优解，则对偶问题也有最优解，且目标函数最优值相等。

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

四、对偶问题的基本性质 [5. 无界性]若原问题(对偶问题)为无界解，则其对偶问题(原问题)为无可行解。

CX → +∞ 若其对偶问题有可行解，则:

CX ≤ b T Y

故原问题必将小于某个值，与原问题无界矛盾。

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

[6. 互补性] [例] 已知LP问题:

Min w = 2 x1 + 3 x2 + 5 x3 + 2 x4 + 3 x5

x1 + x2 + 2 x3 + x4 + 3 x5 ≥ 4 2 x1 x2 + 3 x3 + x4 + 3 x5 ≥ 3 xj ≥ 0该问题的对偶问题的最优解为:

4 * 3 y = , y2 = , z = 5 5 5* 1

求原LP问题的最优解？

10/22/2011

廣東金融學院工商管理系

管理运筹学,每个章节的ppt,管理数学,工商管理系

Min w = 2 x1 + 3x2 + 5 x3 + 2 x4 + 3 x5

Max 4 31 2 1 1 2 1 3 3 1 1 ≤ 2 ≤ 3 ≤ 5 ≤ 2 ≤ 3y1 , y2 ≥ 0

x1 + x2 + 2 x3 + x4 + 3 x5 ≥ 4 2 x1 x2 + 3 x3 + x4 + 3 x5 ≥ 3 xj ≥ 0

10/22/2011

廣東金融學院工商管理系