第三章对偶理论与灵敏度分析.ppt

第三章对偶理论与灵敏度分析
第1页，本讲稿共41页
§1 单纯形法的矩阵描述
设线性规划问题
设B是一个可行基，令（A，I）=（B，N，I），则：
第2页，本讲稿共41页
1. 检验数的矩阵描述：
性规划问题
max
其对偶问题的最优解为
试用对偶理论求原问题的最优解
解：
max
∵
∴
∴
∴
第20页，本讲稿共41页
7. 设原问题及对偶问题的标准型是
max z =CX， AX+XS=b， X， XS ≥0
minω=Yb， YA－YS=C Y， YS ≥0
则原问题单纯形表的检验数行对应其对偶问题的一个基解，对应关系如下表：
XB
XN
Xs
0
CN－CBB-1N
－CBB-1
－Ys1
－Ys2
－Y
证:
CBB-1A－(0，－CN+CBB-1N)
= CBB-1(B，N)－(0，－CN+CBB-1N)
=(CB， CN)=C
第21页，本讲稿共41页
§5 对偶问题的经济解释——影子价格
设B是线性规划问题的一可行基，这目标函数为
所以变量yi的经济意义是在其他条件不变的情况下，单位资源变化所引起的目标函数值的变化。
yi的值代表对第i种资源的估价。这种估价是针对具体工厂的具体产品而存在的一种特殊价格，称它为“影子价格”。
第22页，本讲稿共41页
Q2 (4, 2)
X2
X1
0 1 2 3 4 5
4
3
2
1
Q1(4, 0)
Q3(2, 3)
Q4(0, 3)
O
Q4
Q2
Q3
*
*
A增加4，利润增加4×1/8=1/2
设备增加2，利润增加2×3/2=3
Q (5, 3/2)
Q (4, 3)
第23页，本讲稿共41页
§6 对偶单纯形法
b
XB
XN
Xs
θ
XB
B-1b
I
B-1N
B-1
-z
CBB-1b
0
CN-CBB-1N
-CBB-1
-Ys1
-Ys2
-Y
XB
b
XB
XN
Xs
XB
B-1b
I
B-1N
B-1
-z
CBB-1b
0
CN-CBB-1N
-CBB-1
≤0
变为≤0
变为≥ 0
≥0
θ
单纯形法
对偶单纯形法
第24页，本讲稿共41页
对偶单纯形法的计算步骤：
1. 确定初始的基，使非基变量的检验数小于等于零。
2. 若b ≥0,则已求得最优解，停止计算，否则进行下一步。
3. 确定换出变量。计算
min{(B-1b)i| (B-1b)i<0}= (B-1b)l
则xl为换出变量。
4. 确定换入变量。若所有aij ≥0，则无可行解，停止计算；否则计算
θ=min{σj /alj| alj<0}= σk /alk
则xk为换入变量。
5. 以alk为主元素进行迭代。
6. 重复2—5步。
第25页，本讲稿共41页
例：
第26页，本讲稿共41页
-2 -3 -4 0 0
-3 -1 -2 -1 1 0
-4 -2 1 -3 0 1
-1 0 -5/2 1/2 1 -1/2
2 1 -1/2 3/2 0 -1/2
2/5 0 1 -1/5 -2/5 1/5
11/5 1 0 7/5 1/5 -