第6章__单纯形法的灵敏度分析与_....ppt

《第6章__单纯形法的灵敏度分析与_....ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、上节回顾人工变量法（两阶段法）单纯形法的几种特殊情况1.无可行解（人工变量不为零）2.无界解（存在大于零的检验数，并且该列的系数向量的每个元素aij都小于或等于零，由于建模错误,遗漏约束条件所致）3.无穷多最优解（对于某个最优的基本可行解，如果存在某个非基变量的检验数为零，则此线性规划问题有无数最优解）1上节回顾4.退化问题（求出基变量过程中存在两个以上的最小比值，这样在下一次迭代就有一个或多个基变量等于零，造成的后果是：最优值在经过了一次或几次迭代而没有改善，降低了单纯型算法的效率）5.针对退化问题，讲解了一个迭代循环

2、的例子，引出了勃兰特法则：按照决策变量、松弛变量、人工变量顺序排序。不管是检验数相等，还是比值相等，都选下标最小的为入基变量或出基变量。时间问题，习题没有做。2第六章单纯形法的灵敏度分析与对偶问题§1单纯形表的灵敏度分析§2线性规划的对偶问题§3对偶规划的基本性质§4对偶单纯形法3单纯形表4§1单纯形表的灵敏度分析一、目标函数中变量系数Ck灵敏度分析（在什么范围内变化，最优解不变，与第二章，第三章联系起来）在线性规划的求解过程中，目标函数系数的变动将会影响检验数的取值，但是，当目标函数的系数的变动不破坏最优判别准则时，原

3、最优解不变，否则，原最优解将发生变化，要设法求出新的最优解。下面我们具体的分析1.在最终的单纯形表里，Xk是非基变量由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，所以当Ck变成Ck+Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变成了Ck+Ck。这时K=Ck-Zk就变成了Ck+Ck-Zk=K+Ck。要使原来的最优解仍为最优解，只要K+Ck≤0即可，也就是Ck的增量Ck≤-K。52.在最终的单纯形表中，X

4、k是基变量当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’Kj6§1单纯形表的灵敏度

5、分析根据上式可知检验数J(J=1,2,…..,M)变成了’J,只要当JK时，有’J=CJ-Z’J=J-CKa’Kj。要使最优解不变，’J<=07§1单纯形表的灵敏度分析例：目标函数：Maxz=50X1+100X2约束条件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最优单纯形表如下迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-508§1单纯形表的灵敏度分析对非基

6、变量目标函数系数：C3我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。这里δ3=-50，所以当c3的增量Δc3≤-（-50），最优解不变。对基变量目标函数系数：c1再对基变量x1的目标函数的系数c1进行灵敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和a13’大于0，a15’小于0，可知，有同样有。这样可以知道当-50≤Δc1≤50时，也就是x1的目标函数c1’在0≤c1’≤100时最优解不变。9§1单纯形表的灵敏度分析迭代次数基变量CBX1X2S1S2S3bC’11000002

7、X11010-150S2000-21150X210001001250ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-100从δ3≤0，得到-c1’≤0,即c1’≥0，并且从δ5≤0，得到c1’≤100。那么如果c1’取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。另外一种求最优解不变的C’1变化范围方法在最终的单纯形表中，用C’1代替原来的C1=50,计算得表10常数项灵敏度分析之前的一点补充知识：11补充知识12补充知识13补充知识14补充知识15补充知识16§1单

8、纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析（使对偶价格不变的b的变化范围）回想一下：第2章例一各个约束的对偶价格：从上表我们可以发现各个松弛变量的Zj值，正好等于相应变量的对偶价格。迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X21000100125