资源描述：
《单纯形法和对偶问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第六章单纯形法的灵敏度分析与对偶问题§1单纯形表的灵敏度分析§2线性规划的对偶问题§3对偶规划的基本性质§4对偶单纯形法1单纯形表2§1单纯形表的灵敏度分析一、目标函数中变量系数Ck灵敏度分析（在什么范围内变化，最优解不变，与第二章，第三章联系起来）在线性规划的求解过程中，目标函数系数的变动将会影响检验数的取值，但是，当目标函数的系数的变动不破坏最优判别准则时，原最优解不变，否则，原最优解将发生变化，要设法求出新的最优解。下面我们具体的分析1.在最终的单纯形表里，Xk是非基变量由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，所以当
2、Ck变成Ck+Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变成了Ck+Ck。这时K=Ck-Zk就变成了Ck+Ck-Zk=K+Ck。要使原来的最优解仍为最优解，只要K+Ck≤0即可，也就是Ck的增量Ck≤-K。32.在最终的单纯形表中，Xk是基变量当Ck变成Ck+Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数CB变了，则ZJ(J=1,2,…..,N)一般也变了，不妨设CB=(CB1,CB2。。。,Ck,…，CBm),当CB变成=(CB1,CB2
3、。。。,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,只要当JK时，有’J=CJ-Z’J=J-CKa’Kj。要使最优解不变，’J<=05§1单纯形表的灵敏度分析例：目标函数：Maxz=50X1+100X2约束条件：X1+X2≤3002X1+X2≤400X2≤250X
4、1，X2≥0最优单纯形表如下迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-506§1单纯形表的灵敏度分析对非基变量目标函数系数：C3我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。这里δ3=-50，所以当c3的增量Δc3≤-（-50），最优解不变。对基变量目标函数系数：c1再对基变量x1的目标函数的系数c1进行灵敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和a13’大于0，a
5、15’小于0，可知，有同样有。这样可以知道当-50≤Δc1≤50时，也就是x1的目标函数c1’在0≤c1’≤100时最优解不变。7§1单纯形表的灵敏度分析迭代次数基变量CBX1X2S1S2S3bC’11000002X11010-150S2000-21150X210001001250ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-1008从δ3≤0，得到-c1’≤0,即c1’≥0，并且从δ5≤0，得到c1’≤100。那么如果c1’取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。另外一种求最优解不变的C’1变
6、化范围方法在最终的单纯形表中，用C’1代替原来的C1=50,计算得表常数项灵敏度分析之前的一点补充知识：9补充知识10补充知识11补充知识12补充知识13补充知识14§1单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析（使对偶价格不变的b的变化范围）回想一下：第2章例一各个约束的对偶价格：从上表我们可以发现各个松弛变量的Zj值，正好等于相应变量的对偶价格。15迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-50§1单
7、纯形表的灵敏度分析单纯形表中的Zj跟对偶价格的关系：对于含有小于等于号的约束条件，添加松弛变量转化为标准型。这时这个约束条件的对偶价格就和松弛变量的Zj有关。对偶价格应取松弛变量的Zj的值。对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时这个约束条件的对偶价格就和这个剩余变量的有关了。这时约束条件的对偶价格应取值的相反数-。对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的值。16§1单纯形表的灵敏度分析17最终单纯形表对于不同约束类型的对偶价格的取值。常数项的灵敏度分析-
8、》使对偶价格不变的bj灵敏度分析-》知道对偶价格Zj
