第六章单纯形法的灵敏度分析与对偶 §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时,△C≥,这里≤0 a 当a'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
§1单纯形表的灵款度分析 迭代次数基变量 C XI X2 SI S2 S C'1100000 X C'1 010 50 21 50 1000 0 250 C’1100C’10 C'1+100 CJ-Z 0-C’10C'1-100 从δ3≤0,得到-c1’≤0,即c1≥0,并且从δ5≤0,得 到c1’≤100。 那么如果c1’取值超出这个范围,必然存在一个检验数 大于0,我们可以通过迭代来得到新的最优解。 理蓦总 6
管 理 运 筹 学 6 §1 单纯形表的灵敏度分析 迭代次数 基变量 CB X1 X2 S1 S2 S3 b C’1 100 0 0 0 2 X1 C’1 1 0 1 0 -1 50 S2 0 0 0 -2 1 1 50 X2 100 0 1 0 0 1 250 ZJ C’1 100 C’1 0 -C’1+100 CJ -ZJ 0 0 - C’1 0 C’1-100 从δ3≤0，得到-c1’≤0,即c1’≥0，并且从δ5≤0，得 到c1’≤100。 那么如果c1 ’取值超出这个范围，必然存在一个检验数 大于0，我们可以通过迭代来得到新的最优解
§1单纯形表的灵款度分析 例】线性规划 maxz=x+x2+3x3 +x+2x,<40 x,+2x2+x,<20 +x,<15 x1xx,≥0 (1)求最优解; (2)分别求c1,C2,G3的变化范围,使得最优解不变。 管理蓦
管 理 运 筹 学 7 §1 单纯形表的灵敏度分析 【例】线性规划 1 2 3 1 2 3 1 2 3 2 3 1 2 3 max 3 2 40 2 20 15 , , 0 Z x x x x x x x x x x x x x x = + + + + + + + （1）求最优解； （2）分别求c1 ,c2 ,c3的变化范围，使得最优解不变
§1单纯形表的灵款度分析 【解】(1)加入松弛变量x4,x5,6,用单纯形法求解,最优表 如下表所示。 0 0 0 b CB XB X1 23 x4 6 0 2 0 X1 3x0 1000 0 15 入 0 3 最优解X=(5,0,15);最优值Z50
管 理 运 筹 学 8 §1 单纯形表的灵敏度分析 【解】（1）加入松弛变量x4,x5,x6，用单纯形法求解，最优表 如下表所示。 Cj 1 1 3 0 0 0 b CB XB x1 x2 x3 x4 x5 x6 0 x4 0 －2 0 1 －1 －1 5 1 x1 1 1 0 0 1 －1 5 3 x3 0 1 1 0 0 1 15 λj 0 －3 0 0 －1 －2 最优解X=（5，0，15） ; 最优值Z=50
§1单纯形表的灵款度分析 (2)对于c1:上是x1对应行的系数只有一个负数a26 有 两个正数a2=1及a23=1则有 s,=max 5 max n 1≤Ac1≤2 c1的变化范围是: C1+δ≤c1≤c1+62,0≤c1≤3或c1∈[0,3] x2为非基变量,x1、x3为基变量,则 e2变化范围是:C2≤c2+(-2)=1+3=4或c2∈(4 管理筹
管 理 运 筹 学 9 §1 单纯形表的灵敏度分析 x 2为非基变量，x 1、x 3为基变量，则 c 2变化范围是： ( ) 1 3 4 ( ,4 c2 c2 + −2 = + = 或c2 − (2) 对于c 1：上是x 1对应行的系数只有一个负数 ,有 两个正数 a26 = −1 a22 =1及a25 =1,则有 1 2 2 1 2 min 1 1 1 , 1 3 max max , 1 26 6 2 25 5 22 2 1 − = − = = = − − − = = c a a a － c 1的变化范围是： ,0 ' 3 [0,3] 1 2 1 1 ' c1 + 1 c1 c + c 或c
§1单纯形表的灵款度分析 对于c3:表29中x对应行 a2=,a36=1而a3=0,则有 S,=max 6 32036 3-2 max 2 △c3无上界,即有△c3≥-2,c3的变化范围是 c3≥或c3∈[+∞) 理蓦总 10
管 理 运 筹 学 10 §1 单纯形表的灵敏度分析 2 1 2 , 1 3 max max , 3 6 6 3 2 2 1 = − − − = = a a Δc 3无上界，即有Δc3≥－2，c3的变化范围是。 '1 1,+) 3 3 c 或c 对于c a32 =1，a36 =1,而a35 = 0,则有 3：表2-9中x3对应行