文档介绍：第二章线性规划的对偶理论
北京物资学院李珍萍
2013年3月
北京物资学院运筹学教学课件
1
本章主要内容
第一节、原问题与对偶问题
第二节、对偶问题的基本性质
第三节、影子价格
第四节、对偶单纯形方法
第五节、灵敏度分析
第六节、线性规划的求解软件
2
第一节、原问题和对偶问题
一、引例
二、对称形式的对偶规划
三、非对称形式的对偶规划
四、一般形式的对偶规划
3
一、引例
A
B
C
D
原料拥有量（单位）
含量（单位/公斤）
糖
5
2
4
2
60
蛋白质
3
2
1
4
40
脂肪
3
1
2
5
35
单价
（元/公斤）
15
7
9
12
建立其数学模型。
例1 甲食品厂用糖、蛋白质和脂肪三种原料生产四种复合食品A、B、C、D，复合食品中含有各种原料的数量、复合食品的单价、三种原料的拥有量分别如下表所示，问甲厂如何安排生产才能使总产值达到最大？
x1
x2
x3
x4
4
解：设甲厂安排A、B、C、D的产量分别为x1、 x2、x3、 x4 公斤，总产值为z 元。于是，例1的数学模型为：
5
例2. 假设乙食品厂欲将甲厂的原料收买过来，问乙厂至少应付出多少代价，才能使甲厂放弃生产活动，出让原料？
建立该问题的数学模型。
A
B
C
D
原料拥有量（单位）
含量（单位/公斤）
糖
5
2
4
2
60
蛋白质
3
2
1
4
40
脂肪
3
1
2
5
35
单价
（元/公斤）
15
7
9
12
y1
y2
y3
6
解：设y1,y2和y3（元/单位）分别代表乙厂收购糖、蛋白质和脂肪的单价，乙厂收购原料付出的总费用为w元，于是例2的数学模型为：
7
例1和例2的数学模型比较
令
8
以上两个线性规划分别称为线性规划的原问题和对偶问题。
9
若两个线性规划分别是
和
则称它们是一对对称形式的对偶规划。
二、对称形式的对偶规划
10