资源描述：
《第6章 单纯形法的灵敏度分析与对偶.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章单纯形法的灵敏度分析与对偶§1单纯形表的灵敏度分析§2线性规划的对偶问题§3对偶规划的基本性质§4对偶单纯形法1§1单纯形表的灵敏度分析一、目标函数中变量Ck系数灵敏度分析1.在最终的单纯形表里，Xk是非基变量由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，所以当Ck变成Ck+Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变成了Ck+Ck。这时K=Ck-Zk就变成了Ck+Ck-Zk=K+Ck。要使原来的最优解仍为最优解，只要K+Ck≤
2、0即可，也就是Ck的增量Ck≤-K。2.在最终的单纯形表中，Xk是基变量当Ck变成Ck+Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数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’Kj2
3、§1单纯形表的灵敏度分析根据上式可知检验数J(J=1,2,…..,M)变成了’J,有’J=CJ-Z’J=J+CKa’Kj。要使最优解不变，只要当JK时，’J<=03§1单纯形表的灵敏度分析例：目标函数：Maxz=50X1+100X2约束条件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最优单纯形表如下迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-504§1单纯形表的灵敏度分析我们先对非基变量S1的
4、目标函数的系数C3进行灵敏度分析。这里δ3=-50，所以当c3的增量Δc3≤50，最优解不变。再对基变量x1的目标函数的系数c1进行灵敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和a13’大于0，a15’小于0，可知，有。同样有。这样可以知道当-50≤Δc1≤50时，也就是x1的目标函数c1’在0≤c1’≤100时最优解不变。在最终的单纯形表中，用C’1代替原来的C1=50,计算得表5§1单纯形表的灵敏度分析迭代次数基变量CBX1X2S1S2S3b501000002X1C’11010-150S2000-21150X210
5、001001250ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-100从δ3≤0，得到-c1’≤0,即c1’≥0，并且从δ5≤0，得到c1’≤100。那么如果c1’取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。6§1单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中S2=50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增加利润的，A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为0。迭代次
6、数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-507§1单纯形表的灵敏度分析可以看出，上题中对于设备台时数约束来说，当其松弛变量在目标函数中从0变到Z3=50时，也就是只要当前余下一台时数设备从不能获利变成获利50元时，譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时这个约束条件的对
7、偶价格就和这个剩余变量的有关了。这将使得最优目标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取值的相反数-。对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的值。8下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。从对偶价格的定义,可以知道当对偶价格为正时它将改进目标函数的值，当对偶价格为负时它将使得目标函数朝着与最优化相反的方向前进。下面我们研究当右端项bj发生变化时，在什么范围内其对偶价格不变。由于bj的变化并不影响系数矩阵的迭代，故其最终单纯形表中的系数矩
8、阵没有变化。由此可见当bj变化时，要使原来的基不变得到的基本可行解
