运筹学第三版刁在筠课后答案( 2-4章 ).doc

第二章对偶理论与灵敏度分析
目录
§ 线性规划的对偶问题
§ 单纯形法的矩阵描述
§ 对偶问题的基本性质
§ 影子价格
§ 对偶单纯形法
§ 灵敏度分析
教学要求:
了解LP对偶问题的实际背景
了解对偶问题的建立规则与基本性质
掌握对偶最优解的计算及其经济解释
掌握LP的灵敏度分析
重点:对偶单纯形法计算步骤及对偶单纯形法应用范围;灵敏度分析。
§ 线性规划的对偶问题
一、对偶问题的提出
二、如何将一般问题转化为对偶问题
回本章目录
某工厂拥有A、B、C三种类型的原料,生产甲、乙两种产品。每件产品在生产中消耗的原料数量,每件产品的价格以及三种原料可利用的数量如下表所示:
产品
原料
甲
乙
原料数量
(吨)
A
1
1
300
B
2
1
400
C
0
1
250
价格(元/件)
50
100
一、对偶问题的提出
问题:工厂应如何安排生产可获得最大的总收益?
解:设变量xi为第i种(甲、乙)产品的生产件数(i=1,2)。则有
目标函数 Max z = 50x1 + 100x2
. x1 + x2 ≤300
2x1 + x2 ≤ 400
x2 ≤ 250
x1 ,x2 ≥ 0
现在考虑若三种原料都用于转让,试问:三种原料应如何收费才能既保证本厂的利益,又可以使转让实现?
分析问题:
1、每种资源收回的费用不能低于自己生产时的可获利润;
2、定价不能太高,要使对方能够接受。
设 y1 ,y2 ,y3 分别为每种资源每单位的转让费用,则有:
Min f = 300y1+ 400y2 + 250y3
+2y2 ≥ 50(不少于甲产品的利润)
y1+y2+y3 ≥100(不少于乙产品的利润)
y1,y2 ,y3 ≥ 0
Min f = 300y1+ 400y2 + 250y3
. y1+2y2 ≥ 50
y1+ y2+ y3 ≥100 ()
y1, y2 , y3 ≥ 0
Max z = 50x1 + 100x2
. x1 + x2 ≤300
2x1 + x2 ≤ 400 ()
x2 ≤ 250
x1 , x2 ≥ 0
对偶问题
购买者模型
原问题
管理者模型
一对互为对偶的模型
一个问题中的约束条件,对应于另一个问题的决策变量,反之亦然。
检查()的产生过程可以发现,它的变量个数与()的技术约束个数相同,它的第i个变量yi与()的第i个技术约束对应;()的技术约束的个数与()的变量的个数相同,而且它的第j个技术约束与()的第j个变量xj对应。()的目标函数系数正好是()的右端常数,它的右端常数正好是()的目标函数系数,它的系数矩阵是()的系数矩阵的转置矩阵。线性规划()称为()的对偶线性规划。
对偶问题的定义: (对称形式)
(LP ) max Z=c1 x1 + c2 x2 + ... + cn xn
. a11x1 + a12 x2 + ... + a1nxn  b1
. . . . . . ()
am1x1 + am2x2 + ...+ amn xn  bm
x1 , x2 , ... , xn  0
(DP) min W=b1 y1+ b2 y2+ ... + bm ym
. a11y1+ a21 y2+ ... + am1 ym  c1
. . . . . . ()
a1ny1+ a2n y2+ ... + amnym  cn
y1 , y2 , ... , ym  0
LP()有m个技术约束和n个决策变量,LP()有m个决策变量和n个技术约束,把()的第i个技术约束与()的第i个变量的符号约束yi≥0称为对偶约束,把()的第j个变量的符号约束xj≥0与()的第j个技术约束
称为对偶约束。