文档介绍：1
第三章 线性规划问题的对偶与灵敏度分析
线性规划的对偶问题概念、理论及经济意义
线性规划的对偶单纯形法
线性规划的灵敏度分析
本章内容重点
2
对偶原理
对偶问题定义——线性规划问题写出其对偶问题,要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。
对偶定理——只需了解原问题与对偶问题解的关系,证明从略。
3
: ,工厂收取加工费。试问:设备 A、B、C 每工时各如何收费才最有竞争力? 设 y1 ,y2 ,y3 分别为每工时设备 A、B、C 的收取费用。
4
线性规划原问题
:某工厂拥有A、B、C三种类型的设备,生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数,每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。
产品甲
产品乙
设备能力(h)
设备A
3
2
65
设备B
2
1
40
设备C
0
3
75
利润(元/件)
1500
2500
5
Max z = 1500x1 + 2500x2
. 3x1 + 2x2 ≤ 65
2x1 + x2 ≤ 40 原问题
3x2 ≤ 75
x1 ,x2 ≥ 0
Min f = 65y1+ 40y2 + 75y3
. 3y1+2y2 ≥1500
(不少于甲产品的利润)
2y1+y2+3y3 ≥2500 对偶问题
(不少于乙产品的利润)
y1, y2 , y3 ≥ 0
6
2、对偶定义
对称形式: 互为对偶
(LP) Max z = cT x (DP) Min f = bT y
. Ax ≤ b . AT y ≥ c
x ≥ 0 y ≥ 0
“Max -- ≤”“Min-- ≥”
7
一对对称形式的对偶规划之间具有下面的对应关系。
(1)若一个模型为目标求“极大”,约束为“小于等于”的不等式,则它的对偶模型为目标求“极小”,约束是“大于等于”的不等式。即“max,≤”和“min,≥”相对应。
8
(2)从约束系数矩阵看:一个模型中为A,则另一个模型中为AT。一个模型是m个约束,n个变量,则它的对偶模型为n个约束,m个变量。
(3)从数据b、C的位置看:在两个规划模型中,b和C的位置对换。
(4)两个规划模型中的变量皆非负。
9
非对称形式的对偶规划
一般称不具有对称形式的一对线性规划为非对称形式的对偶规划。
对于非对称形式的规划,可以按照下面的对应关系直接给出其对偶规划。
(1)将模型统一为“max,≤”或“min,≥”的形式,对于其中的等式约束按下面(2)、(3)中的方法处理;
(2)若原规划的某个约束条件为等式约束,则在对偶规划中与此约束对应的那个变量取值没有非负限制;
10
(3)若原规划的某个变量的值没有非负限
制,则在对偶问题中与此变量对应的那个
约束为等式。
下面对关系(2)作一说明。对于关系(3)
可以给出类似的解释。
设原规划中第一个约束为等式:
a11x1 + …+ a1nxn = b1
那么,这个等式与下面两个不等式等价