对偶规划与灵敏度分析（课件）.ppt

1、1对偶规划与灵敏度分析对偶规划与灵敏度分析p 对偶线性规划对偶线性规划p 对偶定理对偶定理p 对偶单纯形法对偶单纯形法p 灵敏度分析灵敏度分析2 对偶理论对偶理论是线性规划的重要内容之一。对应是线性规划的重要内容之一。对应于每个线性规划问题都伴生一个相应的线性规划于每个线性规划问题都伴生一个相应的线性规划问题。问题。原问题和对偶问题紧密关联原问题和对偶问题紧密关联,它们不但有它们不但有相同的相同的数据集合数据集合,相同的最优目标函数值相同的最优目标函数值,而且在而且在求得一个求得一个线性规划的最优解的同时线性规划的最优解的同时,也同步得到对偶线性规划也同步得到对偶线性规划的最优解的最优解。由对

2、偶问题引伸出来的对偶解还有着重要的由对偶问题引伸出来的对偶解还有着重要的经经济意义济意义,是研究经济学的重要概念和工具之一。是研究经济学的重要概念和工具之一。3n对偶问题的提出对偶问题的提出例例1 1、某工厂生产甲、某工厂生产甲,乙两种产品乙两种产品,这两种产品需要在这两种产品需要在A,B,CA,B,C三种不同三种不同设备上加工。每种甲、乙产品在不同设备上加工所需的台时设备上加工。每种甲、乙产品在不同设备上加工所需的台时,它们它们销售后所能获得的利润销售后所能获得的利润,以及这三种设备在计划期内能提供的有限以及这三种设备在计划期内能提供的有限台时数均列于表。试问如何安排生产计划台时数均列于表。

3、试问如何安排生产计划,即甲即甲,乙两种产品各生产乙两种产品各生产多少吨多少吨,可使该厂所获得利润达到最大。可使该厂所获得利润达到最大。p对偶线性规划对偶线性规划设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 4 假设计划期内甲乙两种产品各生产假设计划期内甲乙两种产品各生产 吨，吨，1212121212maxZ=32x+30 x3x+4x365x+4x409x+8x76x0,x012x,x设备设备每吨产品的加工台时每吨产品的加工

4、台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 用图解法或单纯形法可求得最优解用图解法或单纯形法可求得最优解 (元元)即在计划期内甲产品生产即在计划期内甲产品生产 吨，乙产品生产吨，乙产品生产8 8吨，可以使总利润达吨，可以使总利润达到最大，为到最大，为 元元。4*X=(,8)32maxZ=282322823435 现在从另一个角度来考虑该工厂的生产问题现在从另一个角度来考虑该工厂的生产问题:假设该厂的决策者打算不再自己生产甲假设该厂的决策者打算不再自己生产甲,乙产

5、品乙产品,而是把各种而是把各种设备的有限台时数租让给其他工厂使用设备的有限台时数租让给其他工厂使用,这时工厂的决策者应该这时工厂的决策者应该如何确定各种设备的租价。如何确定各种设备的租价。设设 分别为设备分别为设备A A，B B，C C每台时的租价，每台时的租价，约束条件：约束条件：把设备租出去所获得的租金不应低于利用这些设备自把设备租出去所获得的租金不应低于利用这些设备自行生产所获得的利润行生产所获得的利润目标函数：所获租金总额尽量少目标函数：所获租金总额尽量少123y,y,y1231231233y+5y+9y324y+4y+8y30y0,y0,y0123minW=36y+40y+76y6由

6、此可得两个对称的线性规划：由此可得两个对称的线性规划：1212121212maxZ=32x+30 x3x+4x365x+4x409x+8x76x0,x04*X=(,8)3T2maxZ=2823123123123123minW=36y+40y+76y3y+5y+9y324y+4y+8y30y0,y0,y0719*Y=(,0,)662minW=28237123123123yminW=(36,40,76)yyy35932y44830yyy0y121212xmaxZ=(32,30)x3 436x5 440 x9 876x0 x矩阵形式矩阵形式：8可以得到另一个线性规划可以得到另一个线性规划:称之为原线

7、性规划问题的对偶问题称之为原线性规划问题的对偶问题,n对偶线性规划对偶线性规划TminZ=C XAXbX0TTmaxW=bACY0YY考虑如下具有不等式约束的线性规划问题考虑如下具有不等式约束的线性规划问题9101112若令若令线性规划标准型线性规划标准型的对偶规划为的对偶规划为:n线性规划问题标准型的对偶问题线性规划问题标准型的对偶问题TminZ=C XAbX-A-bX01TTT1221TTT12211YmaxW=(b,-b)=b(Y-Y)YY(A,-A)=A(Y-Y)CYY0,Y012Y=Y-YTminZ=C XAX=bX0TTmaxW=bACYYY无约束考虑一个标准形式的线性规划问题考虑

8、一个标准形式的线性规划问题 由于任何一个等式约束都可以用两个不等式约束等价地表示由于任何一个等式约束都可以用两个不等式约束等价地表示,所所以标准形线性规划问题可等价表示为以标准形线性规划问题可等价表示为:它的对偶规划为它的对偶规划为:13n对偶线性规划的求法对偶线性规划的求法从任何一个线性规划出发从任何一个线性规划出发,都可以求出相应的对偶规划都可以求出相应的对偶规划,在实在实际求解过程中际求解过程中,通常不通过求标准型通常不通过求标准型,而是利用如下反映原始问题而是利用如下反映原始问题与对偶问题对应关系的原始与对偶问题对应关系的原始对偶表对偶表:目标函数变量系数目标函数变量系数约束条件右端项

9、约束条件右端项 约束条件右端项约束条件右端项目标函数变量系数目标函数变量系数 约束条件约束条件个数个数:n n个个 变量变量个数个数:n n个个 变量变量个数个数:m m个个 约束条件约束条件个数个数:m m个个 目标函数目标函数minWminW 目标函数目标函数maxZmaxZ 对偶问题对偶问题(或原问题或原问题)原问题原问题(或对偶问题或对偶问题)(1,2,)iim第 个 约 束 条 件0y01 2 iiim第 个变量（，）无约束0 x012 jjjn第 个变量（，）无约束1 2jjn第 个 约 束 条 件（，）141231213123123123maxZ=5x+4x+6x x +2x 2

10、 x +x3-3x+2x+x-5 x -x +x =1x0,x0,x无约束123412341342341234minW=2y+3y-5y+y y +y-3y+y52y +2y -y4 y +y +y6y0,y0,y0,y无约束解解:对偶规划对偶规划:例例2 2 写出下列线性规划的对偶问题写出下列线性规划的对偶问题15例例3 3 写出下列线性规划的对偶问题写出下列线性规划的对偶问题123123123123123minZ=9x+6x-3x 2x+x-4 x4-3x -x +x=-2 2x +2x +x6x,x ,x0123123123123123maxW=4y-2y+6y 2y 3 y2y9 y

11、y +2y 6y y +y3y0,y,y04 自由变量解解:上述问题的对偶规划上述问题的对偶规划:16本节讨论几条重要的对偶定理本节讨论几条重要的对偶定理,这些定理揭示了原始问题的解和对这些定理揭示了原始问题的解和对偶问题的解之间的基本关系。偶问题的解之间的基本关系。定理定理1 1:(:(对合性对合性)对偶问题的对偶是原问题。对偶问题的对偶是原问题。证明证明:设原问题为对偶问题为设原问题为对偶问题为改写对偶问题为对偶问题的对偶为改写对偶问题为对偶问题的对偶为p对偶定理对偶定理TminZ=C XAXbX0TTmaxW=b YACY0YTTmin-W=-b Y-A Y-CY0Tmax-Z=-C X

12、-AX-bX0TminZ=C XAXbX017 定理定理2 2:弱对偶定理弱对偶定理 若是原若是原(极小化极小化)问题的可行解问题的可行解,是对偶是对偶(极大化极大化)问题的可行解问题的可行解,那么那么 TC XYTbYX证明：因为是对偶问题的可行解，所以满足约束条件证明：因为是对偶问题的可行解，所以满足约束条件 又因为是原问题的可行解，可得，又因为是原问题的可行解，可得，,所以所以 。YY0YCT，AXX0AXbTTTTC XY AXY b=b Y注注:原原(极小化极小化)问题的最优目标函数值以对偶问题任一可问题的最优目标函数值以对偶问题任一可行解的目标函数值为下界。行解的目标函数值为下界。

13、对偶对偶(极大化极大化)问题的最优目标函数值以原问题任一问题的最优目标函数值以原问题任一可行解的目标函数值为上界。可行解的目标函数值为上界。推论推论1:1:如果原问题没有下界如果原问题没有下界(即即minZminZ),),则对偶问题不则对偶问题不可行。可行。如果对偶问题没有上界如果对偶问题没有上界(即即maxWmaxW),),则原问题不则原问题不可行。可行。若原问题与对偶问题之一无界若原问题与对偶问题之一无界,则另一个无可行解。则另一个无可行解。18证明证明:由弱对偶定理由弱对偶定理,对于原始问题的对于原始问题的所有可行解所有可行解,都都有有 因此是原问题的因此是原问题的最优解最优解。同理同理

14、,对于对偶问题的对于对偶问题的所有可行解所有可行解 ,都有都有 所以所以 是对偶问题的是对偶问题的最优解最优解。YXTTC XY=C XTbX推论推论2 2：最优性定理最优性定理若是原问题的可行解，是对偶问题的可行解，而若是原问题的可行解，是对偶问题的可行解，而且两者的目标函数值相等，即，则和且两者的目标函数值相等，即，则和分别是原问题和对偶问题的最优解。分别是原问题和对偶问题的最优解。TTC X=b YXXYYTY=C XYTTbbY19证明证明:设是原问题设是原问题(min)(min)的最优解的最优解,则对应的基则对应的基必有必有。若定义若定义,则则 ,因此为对偶问题的可行解因此为对偶问题

15、的可行解,而且而且 ,由由最优性定理最优性定理,是对偶问题的最优解。是对偶问题的最优解。XTT-1BC-CB A0T-1BY=CBYCTAT-1BY=CBTTT-1BC X=CB b=Y bT-1BY=CB 定理定理3 3:强对偶定理强对偶定理 如果原问题如果原问题(min)(min)与对偶问题与对偶问题(max)(max)之一有最优解之一有最优解,那么另一个也有最优解那么另一个也有最优解,而且目标函数值而且目标函数值相等相等。20证明证明:设满足原问题设满足原问题(min)(min)的最优性条件的最优性条件,则对应的基则对应的基必有必有。若定义若定义 ,则则 ,因此为对偶问题的基本可行解。因

16、此为对偶问题的基本可行解。XTT-1BC-CB A0TT-1BY=CBTY ACTT-1BY=CB定理定理4:4:设满足原问题设满足原问题(min)的的最优性条件最优性条件的一个的一个基本解基本解,则其对应的线性规划问题则其对应的线性规划问题(min)(min)的的检验数检验数对应对应对偶问题对偶问题的一的一个个基本可行解基本可行解。X21原问题与对偶问题可能出现的情况(1)两者都有最优解,且最优值相等;(2)一个有可行解,但无界,则另一个无可行解;(3)两者都无可行解。22定理定理5 5：互补松弛定理互补松弛定理如果如果 分别是原问题分别是原问题(min)(min)和对偶问题（和对偶问题（m

17、ax)max)的可行解，的可行解，那么那么 和和 为最优解的充要条件是为最优解的充要条件是 通常称通常称 为互补松弛条件。为互补松弛条件。X,YXYTTTY(AX-b)=0 ,(A Y-C)X=0TTTY(AX-b)=0 ,(A Y-C)X=0TTTTTTTY(AX-b)=0 ,Y AX=Y b(Y A-C)X=0,Y AX=C X证明：充分性证明：充分性TTTY bY AXC XTTTTTTTTTTY b=Y AX=C XY AX=Y b,Y(AX-b)=0 Y AX=C X,(Y A-C)X=0必要性必要性23例例5 5、已知线性规划问题、已知线性规划问题:其对偶问题的最优解。其对偶问题的

18、最优解。试用试用互补松弛定理互补松弛定理找出原问题的最优解。找出原问题的最优解。12121212121212maxZ=4x3x x+2x2 x-x32x+3x5 x +x23x +x3x,x0Y=(1,0,0,0,1),min W5解：原问题的对偶问题为：解：原问题的对偶问题为：由对偶问题最优解可知，由对偶问题最优解可知，由互补松弛定理，由互补松弛定理，解方程组解方程组 所以原问题最优解所以原问题最优解123451234512345iminW=2y+3y+5y+2y+3y y+y+2y+y+3y42y -y+3y+y+y3y0,i=1,2,3,4,5Y=(1,0,0,0,1)15y0,y012

19、1212x+2x=243x=,x=,3x+x=355*43X=(,),maxZ=55524 假设计划期内甲乙两种产品各生产假设计划期内甲乙两种产品各生产 吨，吨，1212121212maxZ=32x+30 x3x+4x365x+4x409x+8x76x0,x012x,x设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 用图解法或单纯形法可求得最优解用图解法或单纯形法可求得最优解 (元元)即在计划期内甲产品生产即在计划期内甲产品生

20、产 吨，乙产品生产吨，乙产品生产8 8吨，可以使总利润达吨，可以使总利润达到最大，为到最大，为 元元。4*X=(,8)32maxZ=28232282343例例:对偶最优解的经济解释对偶最优解的经济解释影子价格影子价格 251212121212maxZ=32x+30 x3x+4x365x+4x409x+8x76x0,x04*X=(,8)3T2maxZ=2823123123123123minW=36y+40y+76y3y+5y+9y324y+4y+8y30y0,y0,y0719*Y=(,0,)662minW=282326由强对偶定理可知，如果原问题有最优解，那么对偶由强对偶定理可知，如果原问题有最

21、优解，那么对偶问题也有最优解问题也有最优解，而且它们的目标函数值相等，即有：，而且它们的目标函数值相等，即有：其中是线性规划原问题约束条件的右端其中是线性规划原问题约束条件的右端数据向量，它代表各种资源的拥有量。数据向量，它代表各种资源的拥有量。为对偶问题最优解，它代表在资源最优为对偶问题最优解，它代表在资源最优利用条件下对各种单位资源的估价，这种估计不是资源的市场利用条件下对各种单位资源的估价，这种估计不是资源的市场价格，而是根据价格，而是根据资源在生产中所作出的贡献资源在生产中所作出的贡献（如创造利润，产（如创造利润，产值等）而作出估价，为区别起见，称之为值等）而作出估价，为区别起见，称之

22、为影子价格影子价格(shadow(shadow price)price)。T*T*1122mmZ=C X=Yb=y by by b12mb=(b,b,b)T*T12mY=(y,y,y)*iizyb *X*Y27影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。影子价格的大小客观地反映了各种不同资源在系统内的稀缺程度。如果如果第第i i种资源供大于求种资源供大于求，即在达到最优解时，该种资源没有用完，或，即在达到最优解时，该种资源没有用完，或松弛变量，由互补松弛定理，在对偶最优解中，第松弛变量，由互补松弛定理，在对偶最优解中，第i i种资源种资源的影子价格。反之如果第的影子价格。反之如果

23、第i i种资源的影子价格，那么由互种资源的影子价格，那么由互补松弛定理，原问题的第补松弛定理，原问题的第i i个约束为严格等式，即，这表明个约束为严格等式，即，这表明第第i i种种资源已经用完资源已经用完，成为稀缺资源。，成为稀缺资源。iu0*iy0iu0*iy0*Y资源的资源的影子价格影子价格同时也是一种机会成本同时也是一种机会成本,在市场经济的条件下在市场经济的条件下,当某种资源的当某种资源的市场价格低于影子价格市场价格低于影子价格时时,企业应买进这种资源用于扩大企业应买进这种资源用于扩大生产生产;相反当某种资源的相反当某种资源的市场价格高于影子价格市场价格高于影子价格时时,企业应卖出这种

24、资源。企业应卖出这种资源。随着资源的买进卖出随着资源的买进卖出,企业资源的影子价格也将随之发生变化企业资源的影子价格也将随之发生变化,一直到一直到影影子价格与市场价格保持同等水平子价格与市场价格保持同等水平时时,才处于才处于平衡状态平衡状态。2812123124125jmaxZ=32x+30 x3x+4x+x =365x+4x +x =409x+8x +x=76x0,j=1.5设备设备每吨产品的加工台时每吨产品的加工台时 可供台时数可供台时数 甲甲 乙乙 A AB BC C 3 35 59 9 4 44 48 8 3636404076 76 利润（元利润（元/吨）吨）32 32 30 30 例

25、例:4*X=(,8)3T2maxZ=2823对偶最优解对偶最优解其中为其中为设备设备A A的影子价格的影子价格，在资源最优利用的条件下，设备在资源最优利用的条件下，设备A A每每增加增加一个单位台时一个单位台时，可以使，可以使总利润增加总利润增加元。元。若设备可供台时数，则若设备可供台时数，则719*Y=(,0,)66*17y=67623*X=(,8)34T5maxZ=283629p对偶单纯形法对偶单纯形法单纯形法是以单纯形法是以保持原问题可行保持原问题可行为条件，即不论进行怎样的基为条件，即不论进行怎样的基变换，常数列必须保持非负。变换，常数列必须保持非负。利用对偶问题的对称性，我们从另一个

26、角度来考虑求解原问利用对偶问题的对称性，我们从另一个角度来考虑求解原问题最优解的方法，这种方法以题最优解的方法，这种方法以保持对偶问题可行保持对偶问题可行为条件，即不论为条件，即不论进行何种基变换，必须保持所有的检验数非负，同时取消原问题进行何种基变换，必须保持所有的检验数非负，同时取消原问题必须可行的要求，即取消常数列的非负限制，通过基变换使原问必须可行的要求，即取消常数列的非负限制，通过基变换使原问题在非可行解的基础上题在非可行解的基础上逐步转换成基本可行解逐步转换成基本可行解，一旦原问题的基，一旦原问题的基本解可行，则该基本可行解也就是最优解，这就是对偶单纯形法本解可行，则该基本可行解也

27、就是最优解，这就是对偶单纯形法的基本思想。的基本思想。单纯形法：单纯形法：可行性可行性最优性最优性对偶单纯形法：对偶单纯形法：最优性最优性可行性可行性-1Bb30例例6 求解下列线性规划 min z=5x1+2x2+6x32x1+4x2+8x3 244x1+x2+4x38x1、x2,x30解解 min z=5x1+2x2+6x32x1+4x2+8x3-x4 =244x1+x2+4x3 -x5=8x1、x2,x3,x4,x50 min z=5x1+2x2+6x32x1 4x2 8x3+x4 =244x1 x2 4x3 +x5=8x1、x2,x3,x4,x5031Cj52600bCBXBx1x2x

28、3x4x50 x4-2-4-810-240 x5-4-1-401-85260005/-22/-46/-80032对偶单纯形法基变换的次序和一般单纯形法不同对偶单纯形法基变换的次序和一般单纯形法不同:一般一般单纯形法单纯形法首先由最大减少原则确定首先由最大减少原则确定换入变量换入变量,然而用最小比值原则确定然而用最小比值原则确定换出变量换出变量 。对偶单纯形法对偶单纯形法则是先将具有负分量的基变量则是先将具有负分量的基变量 取出取出,作为作为换出变量换出变量,然后确定某个非基变量作为然后确定某个非基变量作为换入变量换入变量。其变换目的是在保持对偶问题可行性的前提下其变换目的是在保持对偶问题可行性

29、的前提下,使原问题使原问题的基本解向可行解靠拢。的基本解向可行解靠拢。xlxlkxkx33对偶单纯形法对偶单纯形法的计算步骤如下的计算步骤如下:（4 4）以）以 为为主元主元进行旋转变换，得新的单纯形表，返进行旋转变换，得新的单纯形表，返回（回（2 2）。）。alk（2 2）确定）确定换出变量换出变量 根据根据 ，确定基变量，确定基变量 作为作为换出变量换出变量。检验所在行各元素检验所在行各元素若所有若所有,则则无可行解无可行解，停止计算。否则转入，停止计算。否则转入().).-1-1-1iimin(B b)/(B b)0(B b)lxlja0lja,j=1,2,n,lxl（3 3）确定）确定

30、换入变量换入变量按按最大比值最大比值原则，若原则，若确定非基变量确定非基变量 为为换入变量换入变量。jkjjkmax/a0,jaalll为非基变量下标kx(1)(1)根据原始线性规划根据原始线性规划,列出初始单纯形表列出初始单纯形表,检查检查b b列数字列数字,若若b b列数字全部非负列数字全部非负,则已经则已经求得最优解求得最优解,停止计算。若停止计算。若b b列列中至少有一个负分量中至少有一个负分量,则转入则转入(2 2).).34例例6 用对偶单纯形法求解下列线性规划 min z=5x1+2x2+6x32x1+4x2+8x3 244x1+x2+4x38x1、x2,x30解解 将问题改写成

31、如下形式 min z=5x1+2x2+6x32x1 4x2 8x3+x4 =244x1 x2 4x3 +x5=8x1、x2,x3,x4,x50显然,p4、p5可以构成现成的单位基,此时,非基变量在目标函数中的系数全为负数,因此p4、p5构成的就是初始正则基。35Cj52600bCBXBx1x2x3x4x50 x4-2-4-810-240 x5-4-1-401-85260005/-22/-46/-800-2x21/212-1/4060 x5-7/20-2-1/41-24021/20-1204/(-7/2)02/-2(1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1

32、/211/2001/40-3236最后一个单纯形表中最后一个单纯形表中,已得到一个可行的正则解已得到一个可行的正则解,因而得因而得到问题的最优解为到问题的最优解为 X*=(0,4,1)T最优值为最优值为z*=14(1)对于形如对于形如min z=CX,AXb,X0,且且C0的线性规划问的线性规划问题。因为将其改写为题。因为将其改写为max(z)=CX,AX+XS=b,X0,则立即可以得到则立即可以得到初始正则解初始正则解;(2)在在灵敏度分析灵敏度分析中中,有时需要用对偶单纯形法有时需要用对偶单纯形法,可使问题可使问题的处理简化。的处理简化。对偶单纯形法在以下情况下较为方便对偶单纯形法在以下情

33、况下较为方便。37例例7 7 用对偶单纯形法求解用对偶单纯形法求解1212121212m inW=3x+2x2x+3x18 x -x2 x+3x10 x0,x0解：先化为标准型解：先化为标准型 对偶单纯形允许约束方程右端为负，对偶单纯形允许约束方程右端为负，因此可将方程因此可将方程2 2，3 3两端同乘两端同乘-1-1，可得含单位矩阵的标准型：可得含单位矩阵的标准型：12123124125iminW=3x+2x2x+3x+x =18 x -x -x =2x+3x -x=10 x0,i=1,2,3,4,512123124125iminW=3x+2x2x+3x+x =18-x+x +x =-2-x

34、 -3x +x=-10 x0,i=1,2,3,4,538据此列出初始单纯形表据此列出初始单纯形表,并施行对偶单纯形法迭代步骤如下并施行对偶单纯形法迭代步骤如下:5/4 7/4 000-1/4 1/4 0102x2 2-1/4-3/4 0014x1 3 5/4 3/4 1004x3 0 2/3 0007/3-1/3 0011/3 10/3 x2 21/3 100-4/3-16/3 x4 0101018 x3 000023100-3-1-10 x5 00101-1-2 x4 00013218 x3 0 x5 x4 x3 x2 x1 b XB CB 0002 3 C可得最优解可得最优解 *X=(4,

35、2,4),minW=16T39例例8 用对偶单纯形法求解下列线性规划 min z=x1+2x2x1+x2 42x1+3 x218x1、x20解解 将问题改写成如下形式 min z=x1+2x2x1+x2+x3 =42x13x2 +x4=18x1、x2,x3,x40显然,p3、p4可以构成现成的单位基,此时,非基变量在目标函数中的系数全为负数,因此p3、p4构成的就是初始z正则基。40p灵敏度分析灵敏度分析 线性规划问题所对应的数据集合线性规划问题所对应的数据集合,b b,常常是通过常常是通过预测或估计所得到的统计数据预测或估计所得到的统计数据,在实际使用中在实际使用中,不免会有一不免会有一定的

36、定的误差误差。而且随着市场环境。而且随着市场环境,工艺条件和资源数量的改工艺条件和资源数量的改变变,这些数据完全这些数据完全可能发生变化可能发生变化。因此有必要来分析一下当这些因此有必要来分析一下当这些数据发生波动数据发生波动时时,对目对目前的最优解前的最优解,最优值或者最优基会产生什么最优值或者最优基会产生什么影响影响,这就是所这就是所谓的谓的灵敏度分析灵敏度分析。41灵敏度分析主要讨论如下二类问题灵敏度分析主要讨论如下二类问题:数据集合在数据集合在什么范围内波动什么范围内波动将不影响最优解或最优基？将不影响最优解或最优基？若最优解若最优解发生变化发生变化,应如何找到应如何找到新的最优解新的

37、最优解。CC1 C2 Cn CB XB b x1 x2 xn CB1 XB1 B-1b B-1A=B-1(P1，P2，Pn)CB2 XB2:CBm XBm C-CBTB-1A 列出标准型线性规划问题列出标准型线性规划问题最优单纯形表最优单纯形表:42TTTT-1TT-1TT-1NNNBBNBNBTT-1NNB=(C+C)-(C+C)B N=(C-CB N)+(C-CB N)=+(C-CB N)n价值向量价值向量C C的改变的改变当价值向量由当价值向量由 时时,检验行检验行应修改为应修改为:TTTTTTTTTBNBBNNC=(C,C)C=(C+C,C+C)C目标函数值应为目标函数值应为 。TT-

38、1BBZ=(C+C)B b 只要只要非基变量检验数非基变量检验数那么原最优解那么原最优解仍然为最优仍然为最优。至于目标函数值是否改变至于目标函数值是否改变,取决于取决于TT-1NNNB=+(C-CB N)0BC分别就价值系数对应分别就价值系数对应非基变量非基变量或或基变量基变量加以讨论加以讨论:43l若若是是非基变量非基变量的价值系数，为其改变量，在最的价值系数，为其改变量，在最优表中检验数优表中检验数 发生变化。发生变化。jjcjxjc若超出范围，那么若超出范围，那么 ，当前解已不是最优解。，当前解已不是最优解。此时以修改后的此时以修改后的最优单纯形表最优单纯形表出发，进行出发，进行单纯形迭

39、代单纯形迭代，直至求出新的最优解。直至求出新的最优解。j0 由由 只要只要 即即就可以就可以保持现行最优解保持现行最优解仍为最优。仍为最优。TT-1NNNB=+(C-CB N)0jjj=+c0jjc 44l若若是某是某基变量基变量的价值系数，的价值系数，为改变量，在为改变量，在最优表中所有的非基变量检验数均发生了变化最优表中所有的非基变量检验数均发生了变化.jcjxjc由上式可得到一个由上式可得到一个不等式组不等式组，求解该不等式组就可，求解该不等式组就可得到得到价值系数价值系数 的的可变动范围。可变动范围。jc由，只要检验数：由，只要检验数：或或则最优解仍然保持为最优则最优解仍然保持为最优.

40、TT-1NNNB=+(C-CB N)0j-1NNj=-c(B N)0j-1jNc(B N)45例例7 7、某工厂用甲乙、某工厂用甲乙两种原料两种原料生产生产A,B,C,DA,B,C,D四种产品四种产品,每种每种产品的利润产品的利润,现有原料数及每种产品消耗原料定额如表所现有原料数及每种产品消耗原料定额如表所示示:原料（公斤）原料（公斤）产品（万件）产品（万件）供应量供应量A B C DA B C D甲甲乙乙3 2 10 43 2 10 40 0 2 1/20 0 2 1/218183 3利润（万元利润（万元/万件）万件）9 8 50 199 8 50 19问应该怎样组织生产问应该怎样组织生产,

41、才能使才能使总利润最大总利润最大,若若产品或的产品或的利润利润产生波动产生波动,波动范围多大时波动范围多大时,原最优解保持不变？原最优解保持不变？解解：设生产，四种设生产，四种产品各万件，则此产品各万件，则此问题的线性规划模型为：问题的线性规划模型为：1234x,x,x,x123412341342jmaxZ=9x+8x+50 x+19x3x+2x+10 x+4x18 2x+x3x0,j=1,2,3,446标准化标准化,引入松弛变量引入松弛变量x x5 5,x,x6,6,利用单纯形表求解利用单纯形表求解:4 2/3 0 0 13/3 10/3 2 4/3 0 1 2/3 -10/3 -1/2 -

42、1/3 1 0 -1/6 4/321x4x3-19-50 0 -2 0 -2 3 1026 1 2/3 0 1/2 1/3 -5/3 0 0 1 1/4 0 1/213/2x1x3-9-50 -9 -8 0 -13/2 0 251-3 2 0 3/2 1 -5 0 0 1 1/4 0 1/233/2x5x30-50 -9 -8 -50 -19 0 09/53/2 3 2 10 4 1 0 0 0 2 1/2 0 1183x5x600 x1 x2 x3 x4 x5 x6bXBCB -9 -8 -50 -19 0 0C即最优生产方案是生产产品即最优生产方案是生产产品1 1万件万件,产品产品2 2万

43、件万件,不生产不生产,两种产品。可得最大利润为两种产品。可得最大利润为8888万元。万元。*X=(0,0,1,2),minZ=-88T47C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x5 x6-19-50 x4x321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最优表最优表:原最优解不变，最优利润值原最优解不变，最优利润值（万元）也不变。（万元）也不变。T-1BZ=CB b=88*X=(0,0,1,2)T(1)1)若若 有改变量有改变量。因为。因为为非基变量，为非基变量，由推得即

44、由推得即 或时或时1x1c9 1c11c4 1c13 1c 13jjc 4833-133333c8c2111 42 13 10c(B N)c(,)(4,)c26236 33 334c10 C -9 -8 -50 -19 0 0CBXBbx1 x2 x3 x4 x5 x6-19-50 x4x321 2 4/3 0 1 2/3 -10/3 -1/2 -1/3 1 0 -1/6 4/3Z88 4 2/3 0 0 13/3 10/3最优表最优表:()若若 有改变量有改变量。因为。因为为基变量，为基变量，由推得由推得3c50 3c3xj-1jNc(B N)即当或时即当或时原原最优解不变最优解不变，最优利

45、润值，最优利润值 万元万元35c22 347.5c52 T-1B332Z=CB b=(19,50+c)=88+c1 49n右端项向量右端项向量b b的改变的改变当当右端项右端项向量向量时，改变的是表中时，改变的是表中右端常数列右端常数列。此时基变量此时基变量，目标函数值，目标函数值。而检验行的检验向量保持不变。而检验行的检验向量保持不变。T-1BZ=CB(b+b)-1BX=B(b+b)bb+b若若，可用，可用对偶单纯形法对偶单纯形法再次进行迭代，再次进行迭代，直到求得新最优解。直到求得新最优解。*-1XBb0 为了使为了使B B可行，只要可行，只要或或-1-1-1*-1BX=B(b+b)=B

46、b+Bb=XBb0-1*BbX 50例例8 8、在例、在例7 7中中,若想增加甲种原料若想增加甲种原料,问增加多少时原最优问增加多少时原最优基不变？基不变？解：设甲种原料的改变量为解：设甲种原料的改变量为 ,则则由由 即即 1bb=02102b-1b23331=-01114-b16361b-1*BbX 最优目标函数值最优目标函数值 (万元万元)2b1133-1Z=C B(b+b)=88+(19,50)=88+bB113-b16由此可以推得，由此可以推得，即当即当 时，原最时，原最优基不变。此时最优解优基不变。此时最优解 或或13 b6 115 b244B322x-13X=B(b+b)=+b11

47、1x-61112X=(0,0,1-b,2+b)6351l约束矩阵约束矩阵A A的改变的改变 假设原线性规划问题假设原线性规划问题有一个最优解其中为最优基，有一个最优解其中为最优基，*-1X=B bA=(B,N)TminZ=C XAX=bX0TTBBNNBNBNminZ=CX+CXBX+NX=bX0,X0约束矩阵约束矩阵A A的改变可能导致不同的最优解和最优基的改变可能导致不同的最优解和最优基.以下只涉及两种较简单的情形以下只涉及两种较简单的情形:l增加一个变量增加一个变量,l增加一个约束条件增加一个约束条件。52l 增加一个变量增加一个变量增加增加一个新变量一个新变量，对应的价值系数为，对应的

48、价值系数为，对应的系数列向量为对应的系数列向量为，可得新的线性规划问题：，可得新的线性规划问题：Tn+1n+1n+1n+1n+1maxZ=C X+cxAX+Px=bX0,x0n+1xn+1cn+1P设，则设，则 为为新问题新问题的一个的一个可行解可行解。因此可在此基础上开始因此可在此基础上开始单纯形法单纯形法，求新的最优解。，求新的最优解。n+10 x*XX=0如果如果 ，则，则，是新问题的最优解。是新问题的最优解。否则以为换入变量进行基变换，继续使用否则以为换入变量进行基变换，继续使用单纯形算法单纯形算法为为新的线性规划寻求一个最优解。新的线性规划寻求一个最优解。n+10n+10 x*XX=

49、0n+1x-1TT-1n+1n+1n+1n+1Bn+1n+1Bn+1P=B P,=c-C P=c-C B p53l增加一个约束增加一个约束Tm+1m+1 minZ=C XAX=baXbX0如果加入一个新的约束条件，不妨假设此约束条件如果加入一个新的约束条件，不妨假设此约束条件为为不等式形式不等式形式，即，即m+1m+1aXbTminZ=C XAX=bX0在附加不等式约束左端加上一个在附加不等式约束左端加上一个松弛变量松弛变量 ,n+1xTTBBNNBNm+1 BBm+1 NNn+1m+1BNn+1minZ=CXCX B X+N X =b(a)X+(a)X+x=bX,X0,x0新的线性规划变成新

50、的线性规划变成 54由此可以在由此可以在原来最优基原来最优基的的基础上定义一个基础上定义一个新的基新的基,m+1 BB0B(a)1TTBBNNBNm+1 BBm+1 NNn+1m+1BNn+1minZ=CXCX B X+N X =b(a)X+(a)X+x=bX,X0,x0 是非奇异矩阵，是非奇异矩阵，B得到新问题的一个得到新问题的一个基本解基本解 在原最优解基础上对新问题作在原最优解基础上对新问题作初等行变换初等行变换,使基变量对使基变量对应的系数列向量为应的系数列向量为单位矩阵单位矩阵,该基本解该基本解不一定是可行解不一定是可行解,但是但是由于是原线性规划问题的由于是原线性规划问题的最优基最