第四章灵敏度分析 线性规划中所使用的数据,大多是些估计值,有的不够准确,这就需要研究当对某些数据作稍许改变 时,最优解是否变化?如何变化?更何况实际情况还常有变动,特别经济问题是如此,象产品价格的变动,资 源限制数的增减,约東条件的增减,变量的增减等等。这势必影响最优解和最优值。可见充分利用原最优 表,分析最优解对某些数据变化的反应程度即灵敏度是十分必要的,同时也避免了因条件的些许改变而去 求解,故灵敏度的分析亦称最优化后分析。 §1一般分析 假定线性规划问题 AX=b X≥0 min CX 的最优表已经得到: xIx 基变量 mI CRB A-C CB b 不难看出,表中各块与参数(an,b,C)的关系为: 10B-1A与b,C无关 20XB=B-b与C无关 3°CB-A-C与b无关 4°日标函数值∫=CBb与b,C,A均有关 由此可知,当某些参数变化时,并不一定要重新计算整个单纯形表,而可以从原最优单纯形表出发, 作适当修改后再求新的最优解.现将灵敏度分析的步骤大致归纳如下: (I)修改原最优单纯形表来反映参数的变化。 (Ⅱ)考察上述修改是否使最优解有所变化 (i)检查表中最后一列基变量的值是否依旧非负,即验明解的可行性。 ⅱ)检査所有检验数是否非正,即验明解的最优性。 (Ⅲ)把修改后的表作为初始单纯形表,重新迭代求优 以下分别研究当参数an,b,cC之一发生变化时的情形。 (一)b,变化后的情况 设b→b+Mb,此时原最优单纯形表仅最后一列需要修改 X=Bb→Xn=B-(b+△b) f=CBb→f=CB-(b+Ab) (2) 显然,若X≥0,则对应的解仍为最优解,否则可用对偶单纯形法继续求解。 (二)c变化的情况 设C→C+△C,这时单纯形表中仅最后一行需要改变为: 丌=CB-→z=(CB+△C2)B 兀A-C→元A-(C+△C)
110 第四章 灵敏度分析 线性规划中所使用的数据,大多是些估计值,有的不够准确，这就需要研究当对某些数据作稍许改变 时，最优解是否变化?如何变化?更何况实际情况还常有变动，特别经济问题是如此,象产品价格的变动,资 源限制数的增减，约束条件的增减，变量的增减等等。这势必影响最优解和最优值。可见充分利用原最优 表，分析最优解对某些数据变化的反应程度即灵敏度是十分必要的，同时也避免了因条件的些许改变而去 从头求解，故灵敏度的分析亦称最优化后分析。 §1 一般分析 假定线性规划问题 = CX X AX b min 0 (1) 的最优表已经得到： 1 x 2 x … n x 基变量 B A −1 B b −1 min CB B A −C −1 CB B b −1 不难看出，表中各块与参数 ( , , ) ij i j a b c 的关系为： 1 0 B A −1 与b,C无关 2 0 XB B b −1 = 与C无关 3 0 CB B A −C −1 与b无关 4 0 目标函数值 f CB B b −1 = 与b,C,A均有关 由此可知，当某些参数变化时，并不一定要重新计算整个单纯形表，而可以从原最优单纯形表出发， 作适当修改后再求新的最优解.现将灵敏度分析的步骤大致归纳如下： (Ⅰ)修改原最优单纯形表来反映参数的变化。 （Ⅱ）考察上述修改是否使最优解有所变化： （ⅰ）检查表中最后一列基变量的值是否依旧非负，即验明解的可行性。 （ⅱ）检查所有检验数是否非正，即验明解的最优性。 （Ⅲ）把修改后的表作为初始单纯形表，重新迭代求优。 以下分别研究当参数 ij i j a ,b ,c 之一发生变化时的情形。 (一) i b 变化后的情况 设 b →b + b ，此时原最优单纯形表仅最后一列需要修改， ( ) 1 1 XB = B b → XB = B b + b − − ( ) 1 1 f = CB B b → f = CB B b + b − − (2) f = f − f = CB B b −1 显然，若 X B 0 ，则对应的解仍为最优解，否则可用对偶单纯形法继续求解。 (二) j c 变化的情况 设 C →C + C ，这时单纯形表中仅最后一行需要改变为： 1 1 ( ) − − = CB B → = CB + CB B A −C →A − (C + C) (3)
△ (4) 若由(3)所表示的新检验数全部≤0,则原来的最优解仍是最优解,仅目标函数有如(4)式的变化 若新检验数有的为正时,则依修改后的表为基础,用单纯形法迭代求解 (三)an变化后的情况 (i)非基变量x,的系数变化时,这时若=m(P+A1)-csn(a+△an)-c1≤0时, 则最优解与最优值均不变。若λ,>0,则需将原最优单纯形表中x,对应的列修改为 P→B(P CBP-c→CB(P+AP)-c 然后用单纯形法迭代求优 (i)当基变量x的系数发生变化时,仍按(5)修改x,对应的列,并从最左边去掉基变量x, 从联合算法的角度看,这是仅缺少一个基变量的情况,故可按第三章§5,针对未标出基变量这行,求 基变量,继之迭代求优。详见下一节 例1、设某线性规划问题的最优单纯形表为 x01000 x00010 x10000 /2 001 1/2-1/8 3/2-1/8 14 21 今将x1一列的值换为(44-288 )2,问最优解和最优值将发生怎样的变化? 9571121 将表中x1一列值换成(-,元 ,--),并去掉左边的基变量 实行联合算法的迭代步骤 44288 即可解决问题,具体如下: 1-1/4 0 0 -7/2 11/8 00010000 000100 1/2-1/8 0 -3/2-1/8 「-14 16 01/2 1000 2/30-1/6 14/3 0 0 5/31 5/6 38/3 1 010 000 1/3 0 2/3 5/6 1/3 32/3 故变化后的最优解为 111
111 = = − = n j j j f f f c x 1 (4) 若由（3）所表示的新检验数全部 0，则原来的最优解仍是最优解，仅目标函数有如（4）式的变化。 若新检验数有的为正时，则依修改后的表为基础，用单纯形法迭代求解。 （三） ij a 变化后的情况 （ⅰ）非基变量 j x 的系数变化时，这时若 ( ) ( ) 0 1 = + − = + − = m i j j j j i ij ij j P P c a a c 时， 则最优解与最优值均不变。若 j 0 ，则需将原最优单纯形表中 j x 对应的列修改为 B j j B j j j j j j C B P c C B P P c B P B P P − → + − → + − − − − ( ) ( ) 1 1 1 1 (5) 然后用单纯形法迭代求优。 （ⅱ）当基变量 j x 的系数发生变化时，仍按（5）修改 j x 对应的列，并从最左边去掉基变量 j x 。 从联合算法的角度看，这是仅缺少一个基变量的情况，故可按第三章§5 ,针对未标出基变量这行，求 一基变量，继之迭代求优。详见下一节. 例1、 设某线性规划问题的最优单纯形表为 x 1 2 x 3 x 4 x 5 x 6 x x3 x1 x6 x2 0 0 1 -1 -1/4 0 1 0 0 0 1/4 0 0 0 0 -2 1/2 1 0 1 0 1/2 -1/8 0 0 4 4 2 f 0 0 0 -3/2 -1/8 0 -14 今将 1 x 一列的值换为 T ) 8 21 , 8 11 , 2 7 , 4 5 , 4 9 (− − − ，问最优解和最优值将发生怎样的变化？ 将表中 1 x 一列值换成 T ) 8 21 , 8 11 , 2 7 , 4 5 , 4 9 (− − − ，并去掉左边的基变量 1 x ，实行联合算法的迭代步骤， 即可解决问题，具体如下： x 1 2 x 3 x 4 x 5 x 6 x x3 x6 x2 -9/4 0 1 -1 -1/4 0 5/4 0 0 0 1/4 0 -7/2 0 0 -2 1/2 1 11/8 1 0 1/2 -1/8 0 0 4 4 2 f -21/8 0 0 -3/2 -1/8 0 -14 x3 x5 x6 x2 -1 0 1 -1 0 0 5 0 0 0 1 0 -6 * 0 0 -2 0 1 2 1 0 1/2 0 0 4 16 -4 4 f -2 0 0 -3/2 0 0 -12 x3 x5 x1 x2 0 0 1 -2/3 0 -1/6 0 0 0 -5/3 1 5/6 1 0 0 1/3 0 -1/6 0 1 0 -1/6 0 1/3 14/3 38/3 2/3 8/3 f 0 0 0 -5/6 0 -1/3 -32/3 故变化后的最优解为
281438 ,0,-,0) 333 最优值mm/=32 此问题若以B2为主元实行Gaus元。其结果,得到的基本解,既不是基可行解,也不是正则解, 故以往只能靠引入人工变量和正参数大M来求解 §2增加或减少一个约束条件 (一)增加一个约束条件 设增加的一个约束条件为 m+ux1+am+2x2+.+am+nxn=b 则应在原问题的最优表中按(6)提供的数据,增加一行,然后用消去法,把这行中基变量的系数消 为0,从而化为仅缺少一个基变量且λ,≤0J=1,…,n的问题,故可用联合算法选代求优 (二)减少一个约束条件 当需要减少一个约束时,并不是将最优表中,与该约束相应的行去掉就可以的,因为此约束的影响已 通过 Gauss消元施加在其它各行里了。那么,如不重新求解,应如何利用最优表而达到去掉某些约束的目 设初始单纯形表中含有一个单位矩阵,不妨假定它是由辅助变量(松弛变量,剩余变量或人工变量等) 形成,而最优单纯形表为: y BB BB B1 B21B2 B2n B2 B2 BI B BB B 112 现在要去掉原约束条件AX=b中的一个约束,不妨设为第t个约束,则对上表应采取如下步骤 1°、考虑原第t个约束所加辅助变量y这一列,即(n+t)列,若y为基变量,则去掉最优表中第t 个约東行和(n+t)列即可(此时最优解与最优值均不变)。否则,若存在某βn<O,取 maxIM,,,, <OF B B 若B 。-|Bm>0 Pr 然后以Bn+为主元实行 Gaussi元,并去掉主元所在之/行与n+列 2°、考察新检验数是否仍非正,是,则已得去掉原第t个约束后的最优解;否,用单纯形法迭代 求优。 例2、某工厂去年根据市场需求和自身生产能力可以生产A,B两种产品,当时的条件如 资源可供应量 单位消耗 (千克) (千克)
112 = * x ,0) 3 38 ,0, 3 14 , 3 8 , 3 2 ( T 最优值 3 32 min f = − 。 此问题若以 21 为主元实行Gauss消元。其结果，得到的基本解，既不是基可行解，也不是正则解， 故以往只能靠引入人工变量和正参数大M来求解。 §2 增加或减少一个约束条件 （一） 增加一个约束条件 设增加的一个约束条件为 m+11 1 + m+12 2 + + m+1n n = bm+1 a x a x a x (6) 则应在原问题的最优表中按（6）提供的数据，增加一行，然后用消去法，把这行中基变量的系数消 为0，从而化为仅缺少一个基变量且 j 0 j = 1, , n 的问题，故可用联合算法迭代求优。 （二） 减少一个约束条件 当需要减少一个约束时，并不是将最优表中，与该约束相应的行去掉就可以的，因为此约束的影响已 通过Gauss消元施加在其它各行里了。那么，如不重新求解，应如何利用最优表而达到去掉某些约束的目 的呢？ 设初始单纯形表中含有一个单位矩阵，不妨假定它是由辅助变量（松弛变量，剩余变量或人工变量等） 形成，而最优单纯形表为： 1 x 2 x … n x 1 y … m y 1 i x 2 i x im x 11 12 … 1n 1n+1 … 1n+m 21 22 … 2n 2n+1 … 2n+m … … m1 m2 … mn mn+1 … mn+m 1 2 m f 1 2 … n n+1 … n+m 0 f 现在要去掉原约束条件AX=b中的一个约束，不妨设为第t个约束，则对上表应采取如下步骤： 1 0 、考虑原第t个约束所加辅助变量 t y 这一列，即（n+t）列，若 t y 为基变量，则去掉最优表中第t 个约束行和（n+t）列即可（此时最优解与最优值均不变）。否则，若存在某 in+t <0，取 l n t l i n t i n t i i + + + = , , , max{ | 0} (7) 若 i,n+t 0,i = 1, ,m ，则取 l n t l i n t i n t i i + + + = , , , min { | 0} (8) 然后以 l n+t 为主元实行Gauss消元，并去掉主元所在之 l 行与n+t列。 2 0 、考察新检验数是否仍非正，是，则已得去掉原第t个约束后的最优解；否，用单纯形法迭代 求优。 例2、 某工厂去年根据市场需求和自身生产能力可以生产A，B两种产品，当时的条件如 下表所示: 产品 单位消耗 资源 A B (千克) (千克) 资源可供应量
电(度) 517 3 210 设备(台时) 劳动力(小时) 流动资金(百元) 0.8 单位利润(百元) 据之可确定问题的初始单纯形表和最优表如下: XI X2 YI 3 YYYY 201 210 0 0 00010Y 630 0.80.3000 24 100-3/502 0108/50-2 32 000-99/5116 今年,由于人民储蓄的大幅度增加,银行表示可以取消对该厂流动资金供给量的限制。试问应如何 调整生产,才能获得最大利润? 由初始表知关于流动资金的约束方程是第4个,相应松驰变量是y4,故考虑最优表y 列,由(7)得 max 故应以B4为主元,实行Gaus消元后,并去掉4行,6列得 101/2-3/20 X2 01-1/25/20 271 00-1/2-3/20 这已经是最优表,按它进行调整,可增加利润180-168=12(百元) 注意:由(7)知,主元所在之行未必一定是原约束中要去掉的那一行,如在例2中,若因进口设备而 欲将第二个约束去掉,计算结果,主元是B,=-29,因而消元之后,去掉的却是第三行。此外,之所以 先考虑(7)式是因为去掉约束,一般将使目标函数值减少,但绝不会增大 方法的原理是很简单的,通过比较,不难看出,初始表中将要去掉的约束行所加辅助变量那一列仅有 个1而其余都是0,而在最优表中该列一般将发生变化,说明将要去掉的约束行的影响己经通过迭代施加 到别的行中.注意,若从一开始就去掉那个约束,则所加辅助变量那一列全为0,并且在迭代中保持不变;因 此,只有经过上面的处理,使所加辅助变量那一列又全变回为0,要去掉之约束在单纯形迭代中对其它约束 施加的影响(即指此行的若干倍加于其它诸行),才被消除。此外,按照(7)或(8)选主元是为了保证 所得解的可行性
113 电(度) 设备(台时) 劳动力(小时) 流动资金(百元) 5 3 1 1 7 15 0.8 0.3 210 50 630 24 单位利润(百元) 4 3 据之可确定问题的初始单纯形表和最优表如下： X1 X2 Y1 Y2 Y3 Y4 Y1 Y2 Y3 Y4 5 3 1 0 0 0 1 1 0 1 0 0 7 15 0 0 1 0 0.8 0.3 0 0 0 1 210 50 630 24 -f 4 3 0 0 0 0 0 X1 X2 Y1 Y2 Y3 Y4 X1 X2 Y3 Y1 1 0 0 -3/5 0 2 0 1 0 8/5 0 -2 0 0 0 -99/5 1 16 0 0 1 9/5 0 -4 * 18 32 24 24 -f 0 0 0 -12/5 0 -2 -168 今年，由于人民储蓄的大幅度增加，银行表示可以取消对该厂流动资金供给量的限制。试问应如何 调整生产，才能获得最大利润？ 由初始表知关于流动资金的约束方程是第4个，相应松驰变量是 4 y ，故考虑最优表 4 y 一 列，由（7）得： 4 24 } 4 24 , 2 32 max{ − = − − 故应以 46 为主元，实行Gauss消元后，并去掉4行，6列得 X1 X2 Y1 Y2 Y3 X1 X2 Y3 1 0 1/2 -3/2 0 0 1 -1/2 5/2 0 0 0 4 -27 1 30 20 120 -f 0 0 -1/2 -3/2 0 -180 这已经是最优表，按它进行调整，可增加利润180-168=12（百元） 注意：由（7）知，主元所在之行未必一定是原约束中要去掉的那一行，如在例2中，若因进口设备而 欲将第二个约束去掉，计算结果，主元是 5 99 34 = − ，因而消元之后，去掉的却是第三行。此外,之所以 先考虑(7)式是因为去掉约束，一般将使目标函数值减少，但绝不会增大。 方法的原理是很简单的，通过比较，不难看出，初始表中将要去掉的约束行所加辅助变量那一列仅有 一个1而其余都是0,而在最优表中该列一般将发生变化,说明将要去掉的约束行的影响已经通过迭代施加 到别的行中.注意,若从一开始就去掉那个约束,则所加辅助变量那一列全为0,并且在迭代中保持不变;因 此,只有经过上面的处理，使所加辅助变量那一列又全变回为0,要去掉之约束在单纯形迭代中对其它约束 施加的影响（即指此行的若干倍加于其它诸行），才被消除。此外，按照（7）或（8）选主元是为了保证 所得解的可行性
如果初始表中没有单位矩阵,注意到前面的分析只涉及辅助变量y一列,它由单位列向量最后变成 B-的第t列P-,检验数由0变为C,P-1.因此,这时只需在最优表中增加一辅助列 对该列重 复1°和2°的过程即可 当然,对于有限资源利用型的问题(如例2),亦可采用如下处理办法:将要去掉的约束之常数项b 换成M,按§1中有关常数项变化后的情形处理,最后令M,>+∞,不过这样作由于出现参数M,,给 上机运算带来困难,故还是采用前述办法好些。 至于增加或减少变量的情形,处理起来比较简单容易,这里不多叙而留作练习。 §3*基向量变化的灵敏度分析 1方法介绍 m 对于线性规划问题 AX= b St X≥0 设B是最优基,xk是一基变量,P是xk的系数构成的基向量。现在假定P变为P,xk的目标函数系数Ck 变为C,则对于式(9)的最优单纯形表中,用BF替换单位列向量BP4,用入=C2BF-C替换 相应的检验数0,然后实行一次uass消元,使BP重新变换为原来的单位列向量,λ1仍变为0。经上述 变动后的表简称为初始表,记号照旧。这时xk虽然仍为基变量,但因常数项和检验数都发生了变化,故解 的最优性及可行性都需加以检验并作相应的处理。以往的做法是:如果常数项仍非负,即可行性不变,则 用单纯形法迭代求优;若常数项出现负值,同时检验数出现正值,即可行性和最忧性都被破坏,则必须引 入人工变量及参数“大M”,建立新的单纯形表,重新计算,其中对引入参数“大M”,将导致很大的计算 量和严重的甚至使计算失败的误差。因此,人们都竭力避免在实际计算中引入参数“大M”,而只用其理 论成果进行某些分析推理。通常在寻找初始基可行解时,多采用“两阶段法”而不用“大M法”,其道理 也在于此。可见以往引入“大M”的处理方法乃是不得己的,迫切需要改进。通过分析研究,我们发现 对于可行性和最优性均遭破坏的情形,既不必引入人工变量,也不用借助参数“大M”,只需使用把单纯 形法和对偶单纯形法结合起来的联合算法,便可求出问题的最优解或断定无解,具体程序表述如下 (1)于初始表中,以-1乘常数项为负数的行,并去掉该行左边的基变量,这样的行以后简称为无基 行。若无基行有多个,可用下述方法使之只剩一个:取一无基行,比如常数项最小的,分别以该行的适当 倍数加于其他无基行,使后者的常数项变为0,然后相继(可按行从小到大的顺序)在每一常数为0的无基 行中取一非0元(如取列下标最小的)为主元,实行一次 Guass消元,该无基行即变为有基行。如此进行 直到常数项为0的那些无基行全变为有基行为止。这样最后只剩下一个无基行,设它的行号为r,则其常数 项b>0,然后转(2)或(3)。 (2)针对正检验数所在列按照通常的规则或最速下降规则确定主元实行单纯形迭代、求优。迭代中 若主元一直没能选在无基行(即该行元素不构成最小比值),且又遇到以下两情形之一,致使单纯形迭代 无法进行时,则分别处理。 (a)所有检验数均非正,说明已满足最优性条件,故可用对偶法的选主元规则于第r行选一基变量, 即取 max-a>0) (若式(10)中的集合为空集,结束,问题无可行解)然后以an为主元实行 Guass消元,便得一对偶可行 解,继用对偶单纯形法迭代求优 (b)虽有正检验数λ,>0,但该j列系数an≤0,i=1,2,…,m。这时若an=0,结束,问题无最优 解;否则必有an<0,故可采取下述所谓Q处理:令Q=max{-,/an,l},其中E是事先取定的一个适 当小的正数,然后把r行的Q倍加于目标函数行(此举使新检验数’≤0),其余不变,返回(2)
114 如果初始表中没有单位矩阵,注意到前面的分析只涉及辅助变量 t y 一列,它由单位列向量最后变成 −1 B 的第t列 −1 Pt ,检验数由0变为C B −1 Pt .因此,这时只需在最优表中增加一辅助列 − − 1 1 B t t C P P ,对该列重 复1 0和2 0的过程即可. 当然，对于有限资源利用型的问题（如例2），亦可采用如下处理办法：将要去掉的约束之常数项 i b 换成 Mi ，按§1中有关常数项变化后的情形处理，最后令 Mi → + ，不过这样作由于出现参数 Mi ，给 上机运算带来困难，故还是采用前述办法好些。 至于增加或减少变量的情形，处理起来比较简单容易，这里不多叙而留作练习。 §3*基向量变化的灵敏度分析 1方法介绍 对于线性规划问题 = = 0 . . min X AX b st f CX (9) 设B是最优基， k x 是一基变量， Pk 是 k x 的系数构成的基向量。现在假定 Pk 变为 Pk ， k x 的目标函数系数 Ck 变为 Ck ，则对于式（9）的最优单纯形表中，用 B Pk −1 替换单位列向量 B Pk −1 ，用 k = CBB Pk −Ck −1 替换 相应的检验数0，然后实行一次Guass消元，使 B Pk −1 重新变换为原来的单位列向量， k 仍变为0。经上述 变动后的表简称为初始表，记号照旧。这时 k x 虽然仍为基变量，但因常数项和检验数都发生了变化，故解 的最优性及可行性都需加以检验并作相应的处理。以往的做法是：如果常数项仍非负，即可行性不变，则 用单纯形法迭代求优；若常数项出现负值，同时检验数出现正值，即可行性和最忧性都被破坏，则必须引 入人工变量及参数“大M”，建立新的单纯形表，重新计算，其中对引入参数“大M”，将导致很大的计算 量和严重的甚至使计算失败的误差。因此，人们都竭力避免在实际计算中引入参数“大M”，而只用其理 论成果进行某些分析推理。通常在寻找初始基可行解时，多采用“两阶段法”而不用“大M法”，其道理 也在于此。可见以往引入“大M”的处理方法乃是不得己的，迫切需要改进。通过分析研究，我们发现， 对于可行性和最优性均遭破坏的情形，既不必引入人工变量，也不用借助参数“大M”，只需使用把单纯 形法和对偶单纯形法结合起来的联合算法，便可求出问题的最优解或断定无解，具体程序表述如下。 （1）于初始表中，以-1乘常数项为负数的行，并去掉该行左边的基变量，这样的行以后简称为无基 行。若无基行有多个，可用下述方法使之只剩一个：取一无基行，比如常数项最小的，分别以该行的适当 倍数加于其他无基行，使后者的常数项变为0，然后相继（可按行从小到大的顺序）在每一常数为0的无基 行中取一非0元（如取列下标最小的）为主元，实行一次Guass消元，该无基行即变为有基行。如此进行， 直到常数项为0的那些无基行全变为有基行为止。这样最后只剩下一个无基行，设它的行号为r，则其常数 项 br 0 ，然后转（2）或（3）。 （2）针对正检验数所在列按照通常的规则或最速下降规则确定主元实行单纯形迭代、求优。迭代中 若主元一直没能选在无基行（即该行元素不构成最小比值），且又遇到以下两情形之一，致使单纯形迭代 无法进行时，则分别处理。 （a）所有检验数均非正，说明已满足最优性条件，故可用对偶法的选主元规则于第r行选一基变量， 即取 rt t rj rj j a a a max{ | 0} = (10) （若式（10）中的集合为空集，结束，问题无可行解）然后以 rt a 为主元实行Guass消元，便得一对偶可行 解，继用对偶单纯形法迭代求优。 （b）虽有正检验数 j 0 ，但该j列系数 aij 0,i = 1,2, ,m 。这时若 arj = 0 ，结束，问题无最优 解；否则必有 arj 0 ，故可采取下述所谓Q-处理：令 max{ / ,} Q = − j arj ，其中 是事先取定的一个适 当小的正数，然后把r行的Q倍加于目标函数行（此举使新检验数 J 0 ），其余不变，返回（2）