提示：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
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
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
解为（50/9，350/27，0，0），值为8250
Operational Research
8
对偶问题的实际意义：影子价格
Y*为影子价格，用于估计设备资源转让的费用。
• 当某种资源的市场价格低于影子价格时，应该买进 • 当某种资源的市场价格高于影子价格时，可以卖出
Operational Research
Operational Research
3
引入对偶问题
前面的问题：自己用设备生产最大效益 对偶问题：把设备租赁出去最低费用
Operational Research
4
引入对偶问题
对偶问题不能从字面理解为镜像问题 更好的翻译方法是 伴随问题
Operational Research
5
引入对偶问题：举例
原变量
变量个数 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
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
某汽车配件厂生产甲、乙两种产品。两种产品都需要在A、B两种不同的设备上加工 ，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：
甲
A B
利润（元/个）
乙
6 9
有效工时
540 405
15 9
200
பைடு நூலகம்150
每生产1个甲产品，需要A设备工作15个单位时间，B设备工作9个单位时间。 每生产1个乙产品，需要A设备工作6个单位时间，B设备工作9个单位时间。
7
引入对偶问题：举例
第一个问题：生产问题 另一个问题：出租问题
•
将A、B设备出租，在合理的利润条件下，消耗的资源至少是？
（1）变量：y1、y2为A、B两种设备对外加工时，单位工时的价格。 （2）约束条件（生产者接受）：“合理”的利润条件是指，如果把A、B设备租出去生产 甲，所得收入不应少于200元；把A、B设备租出去生产乙，所得收入不应小于150元。
Home
Lec. 8 Operational Research 对偶问题 dual
Oct. 2012
ZHU Tong Chang’an University E-mail:zhutongtraffic@
Operational Research
2
提纲
• 引入对偶问题 • 对偶问题的实际意义 • 原问题如何转化为对偶问题
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
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
练习二
总结： 优化目标大变小，常数－价值互相换， 系数矩阵要转置，约束－变量捉对变。
Operational Research
10
对偶问题的形式
原问题 原目标函数 max Z 原约束条件
变量个数 m 个 第 i 个约束 ≤ ≥ ＝
对偶问题 对偶目标函数 min w 对偶变量
变量个数 m 个 第 i 个约束 yi ≥ 0 yi ≤ 0 yi 自由变量
甲 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
1个甲产品利润200元/个；1个乙产品利润150元/个
A设备最多工作540小时; B设备最多工作405小时
Operational Research
6
引入对偶问题：举例
某汽车配件厂生产甲、乙两种产品。两种产品都需要在A、B两种不同的设备上加工 ，每种产品在不同的设备上加工的工时、设备工时限制、这些产品销售收入如下表：
（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