第六章单纯形法的灵敏度分析与对偶 §1单纯形表的灵敏度分析 §2线性规划的对偶问题 ·§3对偶规划的基本性质 s4对偶单纯形法 管理蓦
管 理 运 筹 学 1 第六章 单纯形法的灵敏度分析与对偶 • §1 单纯形表的灵敏度分析 • §2 线性规划的对偶问题 • §3 对偶规划的基本性质 • §4 对偶单纯形法
§1单纯形表的灵敏度分析 目标函数中变量C系数灵敏度分析 1.在最终的单纯形表里,Xk是非基变量 由于约東方程系数增广矩阵在迭代中只是其本身的行的初等变换与C没有任何关系, 所以当C变成C+ΔAC时,在最终单纯形表中其系数的增广矩阵不变,又因为X是非 基变量,所以基变量的目标函数的系数不变,即CB不变,可知Z也不变,只是C变 成了C+ΔCk。这时δk=Ck-Z就变成了C计+△CkZ=x+△Ck。要使原来的最优解 仍为最优解,只要δx+△C≤0即可,也就是C的增量△C≤-6k 2在最终的单纯形表中,Ⅹk是基变量 当Ck变成Ck+ΔC时,最终单纯形表中约束方程的增广矩阵不变,但是基变量的目 标函数的系数C变了,则Z(J=1,2,…N)一般也变了,不妨设CB=(CB,CB.,Ck ,Cm),当Cn变成=(CB,CB.C+△Ck2…,Cm),则: Z=(CBI, CB2., Ck,..., CBm)(a a Z=(CBI, CB2 Cx+△C,,CBn)(a,a2,,a”'m)T=Z+ACka 运莓
管 理 运 筹 学 2 §1 单纯形表的灵敏度分析 一、目标函数中变量Ck系数灵敏度分析 1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系， 所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非 基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变 成了Ck+ Ck。这时 K= Ck-Zk就变成了Ck+ Ck- Zk= K+ Ck。要使原来的最优解 仍为最优解，只要 K+ Ck≤0即可，也就是Ck的增量 Ck≤- K。 2.在最终的单纯形表中， X 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 + Ck a’Kj T T
§1单纯形表的灵款度分析 根据上式可知 检验数δ(J=1,2,,M变成了δ’,有 δC-Z=δ- Cka'k。要使最优解不变,只要当J时,o”<=0 6:-△C,a'≤0.△Cal1≥6 当a>0时,△C≥,这里≤0 a 当a'<O时,△C1≤,这里≥0 当j=k时,8=Ck+△Ck-Zk=Ck+△Ck-Z-△Cka,因为Xk是基变量, 知δ=0,a1t=1,可知δ=0 要使得最优解不变,对于除了al以外的所有大于0的as,满足△Ck≥x,所有小于0的a 满足△Ck≤,所以可知△C的变化范围为 Max >0}≤△C≤M 管理蓦
管 理 运 筹 学 3 §1 单纯形表的灵敏度分析 根据上式可知 检验数 J (J=1,2,…..,M)变成了 ’ J,有 J=CJ-Z’J= J- CK a’Kj 。要使最优解不变，只要当J K时， ’ J <=0 ' = = = = = + − = + − − − a' 0 a' δ a' 0 ΔC Min a' δ Max ΔC a' δ ΔC 0 a' a' δ a' 0 a' ΔC δ 0 a' 1 δ ' 0 j k δ ' C ΔC Z ' C ΔC Z ΔC a' , X 0; a' δ , a' δ a' 0 ,ΔC 0; a' δ , a' δ a' 0 ,ΔC δ ΔC a' 0,ΔC a' δ k j k j j k j k k j j k k j j k k j k j j k k k j k k k k k k k k k k k k k k k K k j j k j j k j k k j j k j j k j k j k k j k k j j 满足 ，所以可知 的变化范围为 要使得最优解不变，对于除了 以外的所有大于 的 ，满足 ，所有小于 的 知 ， ，可知 。 当 时， 因为 是基变量， 当 时 这里 当 时 这里
§1单纯形表的灵敏度分析 例: 目标函数:Maxz=50X1+100X2 约束条件:X1+X2≤300 2X1+X2≤400 X,≤250 X1,X2≥0 最优单纯形表如下 迭代次数基变量axx2Sss 50100000 50 0 10 50 0 0 0-21 50 X 1000 00 250 50 10050C 50 27500 CJ-Z 0 500-50 运筹 4
管 理 运 筹 学 4 §1 单纯形表的灵敏度分析 例： 目标函数：Max z=50X1+100X2 约束条件：X1+X2≤300 2X1+X2≤400 X2≤250 X1，X2≥0 最优单纯形表如下 迭代次数 基变量 CB X1 X2 S1 S2 S3 b 50 100 0 0 0 2 X1 50 1 0 1 0 -1 50 S2 0 0 0 -2 1 1 50 X2 100 0 1 0 0 1 250 ZJ 50 100 50 0 50 27500 CJ -ZJ 0 0 -50 0 -50
§1单纯形表的灵款度分析 我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。 这里δ3=50,所以当c3的增量△c3≤50,最优解不变 再对基变量x1的目标函数的系数c1进行灵敏度分析。 在a1,a12,a3,a1,a15中,除了知道a1’和a13大于 0,a5小于0,可知4=-50,有m1p厘=3同样有 m(m(9这样可以知道半50≤≤50时,也就是 x1的目标函数1’在0≤c1’≤10时最优解不变。 在最终的单纯形表中,用C1代替原来的C1=50,计算得表 运筹
管 理 运 筹 学 5 §1 单纯形表的灵敏度分析 我们先对非基变量S1的目标函数的系数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,计算得表 50 1 50 13 3 = − − = a 0 max 50 50 ' max 1 ' 1 = − = − j j j a a 0 min 50 ' min 15 5 1 ' 1 = = a a a j j j