运筹学_8 对偶问题概念+转换方法

Home

Lec. 8 Operational Research 对偶问题 dualOct. 2012

ZHU Tong Chang’an University E-mail:zhutongtraffic@http://doc.guandang.net

Operational Research

2

提纲 引入对偶问题 对偶问题的实际意义 原问题如何转化为对偶问题

Operational Research

3

引入对偶问题前面的问题：自己用设备生产最大效益 对偶问题：把设备租赁出去最低费用

Operational Research

4

引入对偶问题 对偶问题不能从字面理解为镜像问题 更好的翻译方法是 伴随问题

Operational Research

5

引入对偶问题：举例某汽车配件厂生产甲、乙两种产品。两种产品都需要在A、B两种不同的设备上加工 ，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：甲A B利润(元/个)

乙6 9

有效工时540 405

15 9

200

150

每生产1个甲产品，需要A设备工作15个单位时间，B设备工作9个单位时间。 每生产1个乙产品，需要A设备工作6个单位时间，B设备工作9个单位时间。

1个甲产品利润200元/个；1个乙产品利润150元/个 A设备最多工作540小时; B设备最多工作405小时

Operational Research

6

引入对偶问题：举例某汽车配件厂生产甲、乙两种产品。两种产品都需要在A、B两种不同的设备上加工 ，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：

甲 A B利润(元/个)

乙 6 9 150

有效工时 540 405

max Z 200x1 150x2 15x1 6 x2 540 s.t. 9 x1 9 x2 405 x1 , x2 0

15 9 200

解为(30,15,0,0),最优值为8250

Operational Research

7

引入对偶问题：举例 第一个问题：生产问题 另一个问题：出租问题

将A、B设备出租，在合理的利润条件下，消耗的资源至少是？

(1)变量：y1、y2为A、B两种设备对外加工时，单位工时的价格。 (2)约束条件(生产者接受):“合理”的利润条件是指，如果把A、B设备租出去生产 甲，所得收入不应少于200元；把A、B设备租出去生产乙，所得收入不应小于150元。

(3)目标函数(收购方意愿):要租A、B设备，收购费用最少是多少。甲 A B利润(元/个)

乙 6 9 150

有效工时 540 405

15 9 200

15y1 9 y2 200 s.t. 6 y1 9 y2 150 y1 , y2 0 min w 540x1 405x2解为(50/9,350/27,0,0),值为8250

Operational Research

8

对偶问题的实际意义：影子价格

Y*为影子价格，用于估计设备资源转让的费用。

当某种资源的市场价格低于影子价格时，应该买进 当某种资源的市场价格高于影子价格时，可以卖出

Operational Research

9

对偶问题的形式

max Z c1 x1 c2 x2 cn xn

min w b1 y1 b2 y2 bn yn

a11 x1

a12 x2 a1n xn b1 a11 y1 a21 y2 am1 ym c1 a x a x a x b a y a y a y c 12 1 22 2 m2 m 2 21 1 22 2 2n n 2 s.t. s.t. a y a y a y c a x a x a x b 1n 1 2n 2 mn m n m1 1 m2 2 mn n m y j 0, 1 j m xi 0, 1 i n 总结： 优化目标大变小，常数-价值互相换， 系数矩阵要转置，约束-变量捉对变。

Operational Research

10

对偶问题的形式原问题 原目标函数 max Z 原约束条件变量个数 m 个 第 i 个约束 ≤ ≥ =

对偶问题 对偶目标函数 min w 对偶变量变量个数 m 个 第 i 个约束 yi ≥ 0 yi ≤ 0 yi 自由变量

原变量变量个数 n 个 第 j 个约束 Xj ≥ 0 Xj ≤ 0 Xj 自由变量

对偶约束条件变量个数 n 个 第 j 个约束 ≥ ≤ =

优化目标大变小，常数-价值互相换，系数矩阵要转置，约束-变量捉对变

Operational Research

11

练习一

max Z 70x1 30x2 3x1 9 x2 540 5 x 5 x 450 1 2 s.t. 9 x1 3 x2 720 x1 , x2 0

Operational Research

12

练习一

max Z 70x1 30x2 3x1 9 x2 540 5 x 5 x 450 1 2 s.t. 9 x1 3 x2 720 x1 , x2 0

max w 540y1 450y2 720y3 3 y1 5 y2 9 y3 70 s.t. 9 y1 5 y2 3 y3 30 y 0, i 1,2,3 i

Operational Research

13

练习二

max Z 3 x1 x2 2 x3 3 x1 2 x2 3 x3 6 s.t. x1 2 x2 x3 4 x 0, i 1,2,3 i

Operational Research

14

练习二

max Z 3 x1 x2 2 x3 3 x1 2 x2 3 x3 6 s.t. x1 2 x2 x3 4 x 0, i 1,2,3 i

min w 6 y1 4 y2 3 y1 y2 3 2 y 2 y 1 1 2 s.t. 3 y y 2 1 2 y1 , y2为自由变量

Operational Research

15

练习三

min Z 2 x1 3x2 5 x3 x4 x1 x2 3x 3 x4 5 2 x1 2 x2 x4 4 s.t. x x x 6 2 3 4 x 0 ; x , x 0 ; x 4 无约束 1 2 3 提示：min!!!

Operational Research

16

练习三

max Z 5 y1 4 y2 6 y3 y1 2 y2 2 y y 3 1 3 s.t. 3 y1 2 y2 y3 5 y1 y2 y3 1 y 0;y 0;y 无约束 2 3 1