1/27
文档分类:高等教育

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


下载后只包含 1 个 PPT 格式的文档,里面的视频和音频不保证可以播放,查看文件列表

特别说明:文档预览什么样,下载就是什么样。

下载所得到的文件列表
运筹学 ( 对偶问题及性质).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
CB CN
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
运筹学 ( 对偶问题及性质)
例2.1 写出线性规划问题的对偶问题
解:首先将原问题变形为对称形式
运筹学 ( 对偶问题及性质)
内容来自淘豆网www.taodocs.com转载请标明出处.