运筹学课件ch2 对偶与灵敏度分析

运筹学课件

第三节 对偶问题与灵敏度分析一、对偶问题及其模型例7:回顾例1 这时有另一家厂商 提出要购买其煤、电、 油全部资源，并希望花 费尽量少。试建立购买 者的线性规划模型。解：设其购买三种资源1 2 3

甲1

乙2

Maxz 7 x 12 x 9 x 4 x 360 4 x 5 x 200 s .t . 3 x 10 x 300 x , x 0 1 2 1 2 1 2 1 2

煤 电 油

的价格Minw

煤1

电2

油

360 y 200 y1 2

300 y

分别为 y , y , y , 总花费为

w ,则

3

例7称为例1的对偶问题，记为 (D),例1称为例7的原问题, 记为(P)。

9 y 4 y 3 y s .t . 4 y 5 y 10 y y ,y , y 0 1 2 1 2

7 121

甲 乙

运筹学课件

对偶模型的一般式以例7为例，原问题为max z CX记Y ( y , y , y ), 则对偶问题为1 2 3

min w Yb

(P)

AX b s .t . X 0

(D)

YA C s .t . Y 0

这是最常见的对偶模型形式，称为对称式对偶模型。二者间 具有十分对称的对应关系：原问题(P) 目标max型 对偶问题 (D) 目标min型

有n个变量(非负)有m个约束 (小于等于) 价格系数 资源向量 技术系数矩阵

有n个约束(大于等于)有m个变量(非负) 资源向量 价格系数 技术系数矩阵的转置2

运筹学课件

此外，还有一种情形原问题(P) 对偶问题 (D)

第j个变量为自由变量第i个约束为等式约束

第j个约束为等式约束第i个变量为自由变量

例8:写出下面线性规划的对偶规划模型：max z 2 x 1 3 x2

x 1 2x 2 3 2 x 1 x 2 5 s .t . x 1 3x 2 1 x 0 13

运筹学课件

例8:写出下面线性规划的对偶规划模型：max z 2 x 3 x x 2x 3 2 x x 5 s .t . x 3x 1 x 0 解：设对偶变量为 y , y , y , 对偶目标为 w ,则3

min w 3 y 5 y1 1 2

2

y

y 2y y 2 s .t . 2 y y 3 y 3 y , y 0 3 1 2 3 1 2

运筹学课件

二、对偶的性质考虑 (P)max z CX AX b s .t . X 0 min z Yb

(D)

YA C s .t . Y 0

1 .对称性2 .弱对偶性

(P)与(D)互为对偶。设 X , Y 分别是( P ),( D )的可行解，则C X Y AX

CX Yb .

证：由(P)、(D)的约束可得 几何意义：3. 解的最优性 则X

Yb

CX若 X 与 Y 分别是(

YbP )与( D )的可行解，且 C X Y b,

X ,Y

Y.X ,由弱对偶性，

证：对任可行解

CX

Y b CX .5

故X X

.同理， Y

Y

.

运筹学课件

例 9: 设 线 性 规 划 问 题 1为 M a x z 1 C X , Y 是 其 对 偶 问 题 的 最 优 解 ； AX b s .t . X 0 又 设 线 性 规 划 问 题 2为 M a x z 2 C X AX b k s .t. X 0 求 证 ： M a x z

2 M a x z1 Y k。证：问题 1与问题 2 的对偶问题分别是 ( ) Minw Yb ( ) Minw Yb Yk

,其 中 k是 已 知 常 向 量 。

YA C s .t . Y 0

YA C s .t . Y 0

( )与( )的约束相同，故(由弱对偶性， Maxz Y

)的最优解

Y

是( )的可行解。Y

b Y

k ,而由解的最优性，

b Maxz6

,

得证。

运筹学课件

4.对偶定理 若(P)有最优解，则(D)也有最优解， 且最优值相同。Maxz CX

证：对(P)增加松弛变量Xs,化为

AX IX b s .t . X , X 0C 0 XA

设其最优基为B,终表为C B

XbB 1

B

1

I

C C B

A 1

0 C B

I

其检验数为 Y A C Y 0

C C B 0 C B

A 0 I 0

取Y

C B

, 则 Y 满足

即 Y 是( D )的可行解，且由性质 3, Y Y

Y b C B b z 1

.

运筹学课件

问题：(1) 由性质4可知，对偶问题最优解的表达式 Y* =? —— CBB-1 (2) 求Y*是否有必要重新求解( D)? —— 不必。可以从原问题(P)的单纯形终表获得。 例如，在前面的练习中已知 Maxz 2.5 x x1 2

的终表为

3 x 5 x 15 s .t . 5 x 2 x 10 x , x 0 1 2 1 2 1 2

0 2.5

x x

3

9 2

0 1

19 5 2 5

1 0

-

3 5 1 5

X

( 2,

0,

9,

0)

1

zY

5 ( 0 ,0 .5 )8

0

0

0

- 0.5

请指出其对偶问题的最优解和最优值。

w 5

运筹学课件

5.互补松弛定理若 X 与 Y 分别是 ( P )、D )的可行解，则 ( 最优解的充要条件是 YXs

X 和 Y 是 ( P )、D ) (

Y X 0。s

证：将 ( P )、D )的约束化为等式： ( 因为 X 、 Y 是最优解，所以s s

AX IX

s

b , YA Y I C ,s

C X Y b,即s s

( Y A Y I ) X Y ( A X I X ), 而 Y X , Y X 0 , 故只有 Y X (自证)。s

Y Xs

0。

运筹学课件

直观上

原始问题的变量

原始问题的松弛变量

x1 …

xj …

xn

xn+1…xn+i…xn+m

y1… yi… ym对偶问题的变量

ym+1 … ym+j

…

yn+m

对偶问题的松弛变量

xjym+j=0

yixn+i=0

(i=1,2,…,m; j=1,2,…,n)10

在一对变量中，其中一个大于0,另一个一定等于0

运筹学课件

6. 对偶问题的经济解释 (1)对偶最优解的经济解释——资源的影子价格(Shadow Price) CBB-1————

对偶问题的最优解 —— 买主的最低出价；原问题资源的影子价格 —— 当该资源增加1单 位时引起的总收入的增量——卖主的内控价格。

例10:例1(煤电油例)的单纯形终表如下：0 7 12

x x xz

3

84 20 24 428

0

0 0 1

1

- 3.12

1.16

1

0

0.4

- 0.2

1

2

0

0

- 0.12

0.16

0

0

0

- 1.36

- 0.52

(1)请指出资源煤电油的影子价格，并解释其经济意义。 (2)由单纯形终表还可得

到哪些有用的信息？11

运筹学课件

例10:例1(煤电油例)的单纯形终表如下：0 7 12

x x xz

3

84 20 24 428

0

01 0

1

- 3.12

1.16

0 1

0 0

0.4 - 0.12

- 0.2 0.16

1

2

0

0

0

- 1.36

- 0.52

(1)请指出资源煤、电、油的影子价格，并解释其经济意义。 (2)由单纯形终表还可得到哪些有用的信息？ 解：(1)煤、电、油的影子价格分别是0、1.36、0.52; 其经济意义是当煤、电、油分别增加1单位时可使总 收入分别增加0 、1.36、0.52。 (2)由单纯形终表还可得到：原 …… 此处隐藏：2512字，全部文档内容请下载后查看。喜欢就下载吧 ……