线性规划灵敏度分析的一个应用
第29卷第4期（上）
2013年4月赤峰学院学报（自然科学版）JournalofChifengUniversity（NaturalScienceEdition）Vol.29No.4
Apr.2013
线性规划灵敏度分析的一个应用
杨大勇
（陇东学院
数学与统计学院，甘肃庆阳
745000）
摘要：本文利用线性规划单纯形法、对偶单纯形法,分析讨论了当减少一个约束条件时最优解如何变化的问题,并给出了简明有效的方法步骤.最后列举了相关的应用实例,更有效地说明了本文的实用性.
关键词：线性规划；约束条件；单纯形法；对偶单纯形法；最优解；灵敏度分析中图分类号：Ｏ２２１．１
文献标识码：A
文章编号：1673-260X（2013）04-0006-02
线性规划模型如下(LP)maxz=Σcjxjst.
j=1n
Σ
ΣΣΣΣΣjΣΣΣΣΣ
在前面的最终表T(B)中,最优基B的逆矩阵为B-1,线性
Σax≤b
ijj-1
n
规划模型(LP)的原m×n阶系数矩阵为A,在最终表T(B)中
(i=1,2,Λ,m;j=1,2,Λ,n)
为，即-1A.要将第i个方程去掉,就须使第i个约束条件失灵.处理方法可在第i个约束条件左边添加两个非负虚拟变量的差xn+m+1-xn+m+2.[4]
i
xj≥0
对偶规划为
(DLP)minw=Σbiyist.
i=1m
≥
ΣΣΣΣΣjΣΣΣΣΣ
Σaijyi≥cj
-1
n
因为B-1(A,Pi,-Pi)=-1pi,-B-1,Pi),σn+m+1=-CBB-1pi,
(i=1,2,Λ,m;j=1,2,Λ,n)
σn+m+2=CBB-1pi,其中Pi是第i个分量为1的单位向量.所以对最终表进行修改处理时,应在系数矩阵的右边添加最优基的逆阵B-1的第i列向量B-1Pi和-B-1Pi.第二,计算相应的检验数-CBB-1Pi和CBB-1Pi并添加到目标函数检验数行中，得到新的单纯形表.再次，若CBB-1Pi=0时,将约束系数矩阵的第i行删掉即可得到所求最优解；若CBB-1Pi≠0时，则xn+m+1和
yi≥0
现在对线性规划问题(LP)化成标准型(LP')可运用单纯形法得到最优表,设T(B)为对应的最终单纯形表,简记为：
≥CBB-1b
T(B)=≥≥-1
≥Bb
C-CBB-1A≥
≥.≥
B-1A
≥
≥≥B-1b≥=≥≥≥≥≥0
≥≥,maxz=≥≥
≥XB*≥问题(LP')的最优解为X=≥
XN≥
CBBb.依据强对偶性
-1
[3]
xn+m+2中必有其一需要进基，迭代后xn+m+1和xn+m+2对应的系数列变为P1和-P1.这时,要去掉的约束条件对其它约束条件及目标函数的影响失灵,删除变量xn+m+1和xn+m+2对应的系数列向量,采用单纯形法继续迭代来求最优解.
因此,现将去掉第i个约束条件的灵敏度分析的基本思
知,(DLP)的最优Y=(y1,y2,K,ym),
minw=maxz=CBBb.
-1
同时,还可以看出,C-CBBA,-CBB是对线性规划问题
-1
-1
路及步骤归纳如下：
1）确定B-1的第i列向量B-1Pi;
2）在最优表中系数矩阵的最后添加B-1Pi和-B-1Pi;）计算相应的检验数-CBB-1Pi和CBB-1Pi,并添加到T(B)3
相应检验数行中;
的解进行最优性检验的标志.当C-CBBA≤0时,即说明基
-1
可行解达到最优,不妨通过一系列初等变换,将A化为A=(P1,P2,K,Pj,K,Pn,Pn+1,K,Pn+m),其中Pj(j=1,2,K,n)是单位向量.于是知,σj=Cj-CBBPj=Cj-ΣCiaij.
-1
i=1m
对线性规划模型(LP)在增加约束条件的情况中做了详
[1]
4）判断最优性：若CBB-1Pi=0,删掉xn+m+1或xn+m+2对应的系数行（第i行）得到所求最优解;若CBB-1Pi≠0,则转入第5步;
）删掉xn+m+1和xn+m+2对应的系数列,则得到新的单纯形5
表，采用单纯形法继续迭代.
例1
细的说明.而对线性规划模型(LP)在减少约束条件时进行灵敏度分析,教材中提的较少.因为迭代过程已将要去掉的约束条件经过行初等变换作用于其它约束条件以及目标函数中,对整个迭代过程都产生了影响.－６－
如下线性规划模型：maxz=-5x1+5x2+13x3
st.
→→→→→→→→→→→→→→→
-x1+x2+3x3≤20运用单纯形法进行迭代求解,可得最终单纯形表.于是知道X*=(0,，，０，１５，０）Ｔ,z*=95.现在要将第原问题的最优解为：
三个设备约束条件去掉,需要经过以下步骤来实现：
由于要将第三个设备约束条件去掉,从最终单纯形表中可以得出,B-1P3=(-１,-１，３）Ｔ,CB=(13,0,5),从而有-CBB-1P3=
１.则修改原问题的最终单纯形表,得表
13x31000
0x43/41/2-5/4-34/6
0x50100
0x6-1/4-1/23/4-1/2
0x7[1/4]1/2-3/41/2
0x8-1/4-1/23/4-1/2
12x1+4x2+10x3≤902x1+3x2+5x3≤50x1,x2,x3≥0
用单纯形法求解并回答：若在原问题中减少第三个约束条件,这对于最优解有何影响？
解
先将原问题化为标准型，则可列出初始单纯形表,
Cj→
CB1305
基
-5
b5/21525/2
x1-5/427/211/4-5/2
5x20010
x3x5x2σj→
判别最优性,不符合条件,则x7进基,x3出基,主元素为
，采用单纯形法继续迭代,得13x34-23-2
0x43-11-43/6
（6）:12-13.
〔3〕李苏北.运筹学基础[M].成都：四川大学出版社,2003.1.〔4〕解心江.线性规划模型减少约束时的灵敏度分析[J].农业
系统科学与综合研究.2002,18（3）：178-179.
〔5〕徐渝,贾涛.运筹学（上册）[M].北京：清华大学出版社,
Cj→
CB005
基
-5
b101020
x1-516-10
5x20010
0x50100
0x6-1000
0x71000
0x8-1000
x7x5x2σj→
删去表中基变量x7对应的系数行及x7和x8对应的系数列,显然,松弛变量x6对应的系数列也可被同时删去了,再判别最优性,已经符合条件,迭代停止.最优解为:X*=(0,20,0,0,10)T,z*=100.
本文主要针对减少约束条件的情形来对如何求最优解进行了讨论,最后给出了实例,将方法讨论中的理论付诸于实践,更有效地说明了理论的可行性和实用性.———————————————————
参考文献：
〔1〕胡运权.运筹学[M].北京：清华大学出版社,2003.5.〔2〕杨桂元.影子价格及其灵敏度分析[J].运筹与管理,2002,11
2005.2.
〔6〕刘满凤,傅波,聂高辉.运筹学模型与方法教程例题分析与
题解[M].北京：清华大学出版社,2001.2.
〔7〕傅家良.运筹学方法与模型[M].上海：复旦大学出版社,
2006.1.
－
７－