管理运筹学（第三版）第六章.ppt

127管理运筹学第六章单纯形法的灵敏度分析与对偶§1§2§3§4单纯形表的灵敏度分析线性规划的对偶问题对偶规划的基本性质对偶单纯形法128管理运筹学§1单纯形表的灵敏度分析一、目标函数中变量系数ck 灵敏度分析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 ≤?σ?§,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)(a1′?j , a2′?j ,, akj′?,, amj′?)T 就变成了zj=(cB1, cB2,…, ck+ Δck ,…, cBm)(a1′?j , a2′?j ,, akj′?,, amj′?)T =zj +Δck akj′130理管学筹运§1单纯形表的灵敏度分析2 jj???(σ?′???cz′???c ′??????????????????????????????′????????????????????′z ??Δck akj ) ??(c j ??z j ) ??Δck akj ??σ?j ??Δck akj′σ?jakj′σ?jakj′σ?jakj′σ?jakj′这样检验数σ(j ??1,,, m)变成了σ?′,有要使最优解不变,只要当j ≠?k时,σ?′≤ 0,也就是σ?j ??Δck akj′?≤ 0,Δck akj′?≥σ?j≤0;≥0.,这里,这里当akj ??0时,Δck ≥当a′kj ??0时,Δck ≤′???????????????????????????????????????′σ?jakj′σ?jakj′????????????????????????????????????????????????????????????????????????????????????????????????????????????????而当j ??k时,σ?′??ck ??Δck ??zk′???ck ??Δck ??zk ??Δck ×?akk′?,因为xk 是基变量,可知σ?k ??0, akk′????1, 故知σ?'k ??,对于除了akk 外的所有的小于零的akj,满足Δck ≤,对于所有大于零的akj′?,满足Δck ≥,所有可知Δck的变化范围为131管理运筹学§1单纯形表的灵敏度分析例:目标函数:max z=50x1+100x2约束条件:x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0最优单纯形表如表6-1 所示。表6-1cB500100迭代次数2基变量x1s2x2zjcj?zjx150100500x21000011000s101?2050?50s2001000s30?11150?50b505025027 500可知a ????1 ???50 ,有max ?a '???????????????????????????????????????σ?j ??????????????????132管理运筹学§1单纯形表的灵敏度分析′???′????′????′????′??????????????′?????????′?????????′我们先对非基变量s1 的目标函数的系数c3 进行灵敏度分析。这里σ?3 =?50,所以当c3的增量Δc3≤50 时,最优解不变。再对基变量x1 的目标函数的系数c1 进行灵敏度分析。在a11 , a12 , a13 , a14 , a15中, 已知a11 ≥ 0, a13 ≥ 0, a15 ≤ 0,σ?3 ?50 ?σ?j13