资源描述：
《运筹学电子课件 第6章 单纯形法的灵敏度分析与对偶.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章单纯形法的灵敏度分析与对偶§1单纯形表的灵敏度分析§2线性规划的对偶问题§3对偶规划的基本性质§4对偶单纯形法1单纯形法的矩阵描述maxZ=CXmaxZ=CBXB+CNXNs.t.AX=bs.t.B·XB+N·XN=bX≥0XB,XN≥0则XB=B-1(b-NXN)=B-1b-B-1NXN代入Z=CBXB+CNXN=CB(B-1b-B-1NXN)+CNXN=CBB-1b+(CN-CBB-1N)XN令XN=0，则XB=B-1bZ=CBB-1b若B-1b≥0，则X=(B-1b,0)是一个基本可行解。2单纯形法的矩阵描述EX：已知线形规划问题：MaxZ=5x1+
2、2x2+3x3s.t.x1+5x2+2x3≤b1x1-5x2-6x3≤b2x1,x2,x3≥0对于给定的非负常数b1，b2，其最优单纯形表如下，请完成该表，并求出b1，b2。cjbxBcBx1x2x3x4x5x1x51-13010zjcj-zj3§1单纯形表的灵敏度分析一、目标函数中变量Ck系数灵敏度分析1.在最终的单纯形表里，Xk是非基变量CkCk+Ck，CB不变，Zk也不变，这时K’=Ck+Ck-Zk=K+Ck。要使原来的最优解仍为最优解，只要K+Ck≤0即可，也就是Ck的增量Ck≤-K2.在最终的单纯形表中，Xk是基变量当Ck变成Ck+Ck时，最终单纯形表
3、中约束方程的增广矩阵不变，但是基变量的目标函数的系数CB变了，则Zj(j=1,2,…..,n)一般也变了，不妨设CB=(CB1,CB2…,Ck,…，CBm),当CB变成=(CB1,CB2。。。,Ck+Ck,…,CBm),则：Zj=(CB1,CB2。。。,Ck,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)Z’j=(CB1,CB2。。。,Ck+Ck,…，CBm)(a’1j,a’2j,…,a’Kj,…,a’mj)=Zj+Cka’Kj4§1单纯形表的灵敏度分析根据上式可知检验数j(j=1,2,…..,m)变成了’j,有’j=Cj-Z’j=j-CKa’K
4、j。要使最优解不变，只要当jk时，’j<=05§1单纯形表的灵敏度分析例：目标函数：Maxz=50X1+100X2约束条件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最优单纯形表如下迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250Zj501005005027500Cj-Zj00-500-506§1单纯形表的灵敏度分析我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。这里δ3=-50，所以当c3的增量Δc3≤50，最优解不变。再对基变量x1的目标函数的系数
5、c1进行灵敏度分析。在a11’,a12’,a13’,a14’,a15’中，除a11’外,系数a13’大于0，a15’小于0，可知，有。同样有。这样可以知道当-50≤Δc1≤50时，也就是x1的目标函数c1’在0≤c1’≤100时最优解不变。在最终的单纯形表中，用C’1代替原来的C1=50,计算得表7§1单纯形表的灵敏度分析迭代次数基变量CBX1X2S1S2S3b501000002X1C’11010-150S2000-21150X210001001250ZjC’1100C’10-C’1+100Cj-Zj00-C’10C’1-100从δ3≤0，得到-c1’≤0,即c
6、1’≥0，并且从δ5≤0，得到c1’≤100。那么如果c1’取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。8§1单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析从上表我们可以发现各个松弛变量的Zj值，正好等于相应约束条件的对偶价格。在最优解中S2=50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增加利润的，A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为0。迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250Zj
7、501005005027500Cj-Zj00-500-509§1单纯形表的灵敏度分析可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时这个约束条件的对偶价格就和这个剩余变量的有关了。这将使得最优目标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取值的相反数-。对于含有等于号的约
8、束条件，其约束条件的对偶
