运筹学 ( 对偶问题及性质).ppt

Chapter2 对偶理论( Duality Theory )
线性规划的对偶模型
对偶性质
对偶问题的经济解释-影子价格
对偶单纯形法
灵敏性分析
本章主要内容:
线性规划的对偶模型
设某工厂生产两种产品甲和乙,生产中需4种设备按A,B,C,D顺序加工,每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表:
产品数据表
设备
产品
A
B
C
D
产品利润
(元/件)
甲
2
1
4
0
2
乙
2
2
0
4
3
设备可利用机时数(时)
12
8
16
12
问:充分利用设备机时,工厂应生产甲和乙型产品各多少件才能获得最大利润?
1. 对偶问题的现实来源
解:设甲、乙型产品各生产x1及x2件,则数学模型为:
反过来问:若厂长决定不生产甲和乙型产品,决定出租机器用于接受外加工,只收加工费,那么4种机器的机时如何定价才是最佳决策?
在市场竞争的时代,厂长的最佳决策显然应符合两条:
 (1)不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则,便构成了新规划的不等式约束条件。
(2)竞争性原则。即在上述不吃亏原则下,尽量降低机时总收费,以便争取更多用户。
设A、B、C、D设备的机时价分别为y1、y2、y3、y4,则新的线性规划数学模型为:
2. 原问题与对偶问题的对应关系
原问题
(对偶问题)
对偶问题
(原问题)
线性规划的对偶模型
(1)对称形式
特点:目标函数求极大值时,所有约束条件为≤号,变量非负;目标函数求极小值时,所有约束条件为≥号,变量非负.
已知(LP),写出(DP)
单纯形法计算的矩阵描述(n>m)
项目
非基变量
基变量
XB XN
Xs
0 Xs b
B N
I
cj-zj
0
项目
基变量
非基变量
XB
XN Xs
CB XB B-1b
I
B-1N B-1
cj-zj
0
CN-CBB-1N -CBB-1
若初始矩阵中变量 xj的系数向量为Pj, 迭代后为P’j, 则有
P’j=B-1 Pj
当B为最优基时,应有
令Y=CBB-1, 则
项目
基变量
非基变量
XB
XN Xs
CB XB B-1b
I
B-1N B-1
cj-zj
0
-Ys1
CN-CBB-1N -CBB-1
-Ys2 -Y
写出线性规划问题的对偶问题
解:首先将原问题变形为对称形式