运筹学对偶理论.ppt

《运筹学对偶理论.ppt》由会员分享，可在线阅读，更多相关《运筹学对偶理论.ppt（104页珍藏版）》请在三一办公上搜索。

1、对偶理论Dual Theory,2.1 线性规划的对偶模型 Dual Model of LP2.2 对偶性质 Dual property 2.3 对偶单纯形法 Dual Simplex Method2.4 灵敏度与参数分析 Sensitivity and Parametric Analysis,运筹学Operations Research,2.1 线性规划的对偶模型 Dual Model of LP,在线性规划问题中，存在一个有趣的问题，即每一个线性规划问题都伴随有另一个线性规划问题，称它为对偶线性规划问题。,【例2.1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：,建立

2、总收益最大的数学模型。,2.1 线性规划的对偶模型 Dual model of LP,【解】设x1，x2，x3分别为产品A，B，C的产量，则线性规划数学模型为：,现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。,2.1 线性规划的对偶模型 Dual model of LP,设y1，y2，y3及y4分别表示四种资源的单位增值价格（售价成本增值），总增值最低可用,mi

3、n w=500y1+450y2+300y3+550y4,表示。企业生产一件产品A用了四种资源的数量分别是9，5，8和7个单位，利润是100,企业出售这些数量的资源所得的利润不能少于100，即,同理，对产品B和C有,价格不可能小于零，即有yi0,i=1,4.从而企业的资源价格模型为,2.1 线性规划的对偶模型 Dual model of LP,这是一个线性规划数学模型，称这一线性规划模型是前面生产计划模型的对偶线性规划模型,这一问题称为对偶问题。生产计划的线性规划问题称为原始线性规划问题或原问题。,2.1 线性规划的对偶模型 Dual model of LP,上面两种形式的线性规划称为规范形式。

4、,原问题和对偶问题是互为对偶的两个线性规划问题，已知一个问题就可写出另一个问题。,规范形式（Canonical Form）的定义：目标函数求极大值时，所有约束条件为号，变量非负；目标函数求极小值时，所有约束条件为号，变量非负。规范形式的线性规划的对偶问题亦是规范形式。,以上是依据经济问题推导出对偶问题，还可以用代数方法推导出对偶问题。,2.1 线性规划的对偶模型 Dual model of LP,原始问题Max z=CTXs.t.AX bX 0,对偶问题Min w=bT ys.t.AT y C y 0,max,b,A,CT,C,AT,bT,min,m,n,m,n,对偶的定义,规范对偶问题,表2

5、-2,表23,2.1 线性规划的对偶模型 Dual model of LP,设线性规划模型是式（2.1）的规范形式由表2-3知，当检验数,时得到最优解，是 的检验数,和,令,由 得,在 两边有乘b,则有,又因Y0无上界,从而只存在最小值，得到另一个线性规划问题,2.1 线性规划的对偶模型 Dual model of LP,即是原线性规划问题式（2.1）的对偶线性规划问题，反之，式（2.3）的对偶问题是式（2.1）原问题和对偶问题是互为对偶的两个线性规划问题，规范形式的线性规划的对偶仍然是规范形式，参数矩阵的对应关系参看表2-4因此已知一个规范形式问题就可写出另一个对偶问题,2.1 线性规划的对

6、偶模型 Dual model of LP,【例2.2】写出下列线性规划的对偶问题,【解】这是一个规范形式的线性规划，设Y=（y1，y2），则有,2.1 线性规划的对偶模型 Dual model of LP,从而对偶问题为,对偶变量yi也可写成xi的形式。,2.1 线性规划的对偶模型 Dual model of LP,【例2.3】写出下列线性规划的对偶问题,【解】这是一个规范形式的线性规划，它的对偶问题求最小值，有三个变量且非负，有两个“”约束，即,2.1 线性规划的对偶模型 Dual model of LP,若给出的线性规划不是规范形式，可以先化成规范形式再写对偶问题。也可直接按表2-1中的对

7、应关系写出非规范形式的对偶问题。,将上述原问题与对偶问题的对应关系列于表2-1,例如，原问题是求最小值，按表2-1有下列关系：,1.第i个约束是“”约束时，第i个对偶变量yj0,2第i个约束是“=”约束时，第i个对偶变量yi无约束；,3当xj0时，第j个对偶约束为“”约束，当xj无约束时，第j个对偶约束为“=”约束。,2.1 线性规划的对偶模型 Dual model of LP,表2-4,2.1 线性规划的对偶模型 Dual model of LP,当原问题为求极小值时，对偶问题为求极大值。原始问题中目标函数的系数变成对偶问题中约束条件的右端；原始问题中约束条件的右端变成对偶问题中目标函数的系

8、数。原始问题约束条件系数矩阵的转置对应对偶问题中约束条件的系数矩阵。原始问题的约束条件个数决定对偶问题变量的个数；原始问题变量个数，决定对偶问题的约束个数。原始问题的约束方程的匹配形式决定对偶问题变量的符号；原始问题决策变量的符号决定所对应对偶问题的约束方程的匹配形式。,【例2.4】写出下列线性规划的对偶问题,【解】目标函数求最小值，应将表24的右边看作原问题，左边是对偶问题，原问题有3个约束4个变量，则对偶问题有3 个变量4个约束，对照表21的对应关系，对偶问题为：,2.1 线性规划的对偶模型 Dual model of LP,=,y10，,y20，,y3无约束,min z=2x1+4x2-

9、x3s.t.3x1-x2+2x3 6-x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15,max w=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y4 2-y1+2y2+y3+3y4 4 2y1-3y2+2y3-y4-1 y1 0,y2,y3 0,y4 0,=,unr,=,x10,x20,x3:unr,练习,1.本节以实例引出对偶问题;,2.介绍了如何写规范与非规范问题的对偶问题;,作业：教材P61 T 1、2,2.1 线性规划的对偶模型 Dual model of LP,下一节：对偶性质,2.2 对偶性质Dual property,对偶问题是（

10、记为DP）：,这里A是mn矩阵X是n1列向量，Y是1m行向量。假设Xs与Ys分别是（LP）与（DP）的松驰变量。,【性质1】对称性 对偶问题的对偶是原问题。,【证】设原问题是,设原问题是（记为LP）：,2.2 对偶性质Dual property,2.2.1 对偶性质,它与下列线性规划问题是等价的：,再写出它的对偶问题。,它与下列线性规划问题是等价的,即是原问题。,由表2-4知，它的对偶问题是,2.2 对偶性质Dual property,【证】因为X、Y是可行解，故有AXb,X0及YAC，Y0,将不等式 AXb,【性质2】弱对偶性 设X、Y分别为LP(max)与DP(min)的可行解，则,两边左

11、乘Y，得Y0AXY0b,再将不等式YAC两边右乘X，得C XYAX,故 C XYAXYb,这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。,2.2 对偶性质Dual property,由这个性质可得到下面几个结论：,（1）（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界；,（2）在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；,(3)若原问题可行且另一个问题不可行，则原问题具有无界解。,注意上述结论（2）及

12、（3）的条件不能少。一个问题无可行解时，另一个问题可能有可行解（此时具有无界解）也可能无可行解。,2.2 对偶性质Dual property,例如：,无可行解，而对偶问题,有可行解，由结论（3）知必有无界解。,2.2 对偶性质Dual property,【性质3】最优准则定理 设X0与Y0分别是（LP）与（DP）的可行解，则当X0、Y0是（LP）与（DP）的最优解当且仅当C X0=Y0b.,【证】若X0、Y0为最优解，B为（LP）的最优基，则有Y0=CBB1，并且,当C X0=Y0b时，由性质1，对任意可行解 有,即Y0b是（DP）中任一可行解的目标值的下界，C X0是（LP）中任一可行解的目

13、标值的上界，从而X0、Y0是最优解。,2.2 对偶性质Dual property,【性质4】若互为对偶的两个问题其中一个有最优解，则另一个也有最优解，且最优值相同。,【证】设（LP）有最优解X0,那么对于最优基B必有C-CBB-1A0与CBB-10，即有YAC与Y0，这里Y=CBB-1，从而Y是可行解，对目标函数有,由性质3知Y是最优解。,由性质 4 还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。,2.2 对偶性质Dual property,【性质5】互补松弛定理 设X0、Y0分别为（LP）与（DP）的可行解，XS和YS是它的松弛

14、变量的可行解，则X0和Y0是最优解当且仅当,YSX0=0和Y0XS=0,【证】设X和Y是最优解,由性质3，C X0=Y0b，由于XS和YS是松弛变量，则有,A X0XSbY0AYS=C,将第一式左乘Y0，第二式右乘X0得,Y0A X0Y0XSY0bY0A X0YS X0=C X0,2.2 对偶性质Dual property,显然有,Y0XS=YS X0,又因为Y、Xs、Ys、X0，所以有,YXS=0和YS X=0,成立。,反之，当YXS=0和YS X=0时，有,YA XYbYA X=C X,显然有Y0b=C X,由性质3知Y与X是（LP）与（DP）的最优解。证毕。,2.2 对偶性质Dual p

15、roperty,性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。,Y*XS=0和YS X*=0,两式称为互补松弛条件。将互补松弛条件写成下式,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：,2.2 对偶性质Dual property,(1)当yi*0时，,反之当 时yi*=0；,利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。性质5的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质5的结论仍然有效。,2.2 对偶性质Dual property,互补松弛关系,max z=

16、CTXs.t.AX+u=b X,u0,min w=bTys.t.ATy-v=C y,v0,max z=CTXs.t.AX b X 0,min w=bTys.t.ATy C y0,互补松弛关系,max z=CTXs.t.AX+u=bX,u 0,min w=bTys.t.ATy-v=Cy,v 0,XTv=0yTu=0,m,n,=,y,v,AT,-I,C,n,=,A,u,I,b,n,m,m,X,y1 yi ym vm+1 vm+j vn+m,x1 xj xn un+1 un+i un+m,对偶问题的变量 对偶问题的松弛变量,xjvm+j=0yiun+i=0(i=1,2,m;j=1,2,n)在一对变量

17、中，其中一个大于0，另一个一定等于0,【例2.5】已知线性规划,的最优解是 求对偶问题的最优解。,2.2 对偶性质Dual property,【解】对偶问题是,因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。,2.2 对偶性质Dual property,【例2.6】已知线性规划,的对偶问题的最优解为Y=（0，2），求原问题的最优解。,【解】对偶问题是,2.2 对偶性质Dual property,解方程组得：x 1=5,x 3=1,所以原问题的最优解为X=（5，0，1），最优值Z=12

18、。,因为y20，所以原问题第二个松弛变量=0，则y1=0、y2=2知，松弛变量 故x2=0，则原问题的约束条件为线性方程组：,2.2 对偶性质Dual property,【例2.7】证明下列线性规划无最优解：,【证】容易看出X=（4，0，0）是一可行解，故问题可行。对偶问题,将三个约束的两端分别相加得而第二个约束有y21，矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。,2.2 对偶性质Dual property,【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解.其中第j个决策变量xj的检验数的相反数对应于（DP）中第j个松弛变量 的解，第i个松弛变量 的检

19、验数的相反数对应于第i个对偶变量yi的解。反之，（DP）的检验数（注意：不乘负号）对应于（LP）的一组基本解。证明略。,2.2 对偶性质Dual property,【例2.8】线性规划,（1）用单纯形法求最优解；（2）写出每步迭代对应对偶问题的基本解；（3）从最优表中写出对偶问题的最优解；（4）用公式Y=CBB-1求对偶问题的最优解。,【解】（1）加入松弛变量x4、x5后，单纯形迭代如表2-2所示。,2.2 对偶性质Dual property,表2-2,2.2 对偶性质Dual property,最优解X=（4，6，0），最优值Z=6426=12；,（2）设对偶变量为y1、y2,松弛变量为y3

20、、y4、y5,Y=（y1、y2、y3、y4、y5），由性质6得到对偶问题的基本解（y1、y2、y3、y4、y5）=（4，5，1，2，3），即,表22（1）中=（6，2，1，0，0），则Y（1）=（0，0，-6，2，1）,表22（2）中=（0，1，5，3，0），则Y（2）=（3，0，0，1，5）,表22（3）中=（0，0，11，2，2），则Y（3）=（2，2，0，0，11）,2.2 对偶性质Dual property,（3）因为表22（3）为最优解，故 Y（3）=（2，2，0，0，11）为对偶问题最优解；,（4）表22（3）中的最优基 B-1 为表22（3）中x4，x 5两列的系数，即,CB=（

21、6，2），因而,2.2 对偶性质Dual property,本节您学了六个对偶性质；这些性质是研究原问题与对偶问题解的对应关系；表26也许对您了解这些性质有帮助。,表26,2.2 对偶性质Dual property,影子价格(Shadow price):原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，即对偶问题中的决策变量yi的值。,2.2.2 影子价格,因为原问题和对偶问题的最优值相等，将线性规划的目标函数表达成资

22、源的函数，故有,即yi是第 i 种资源的变化率，说明当其它资源供应量bk(ki)不变时，bi增加一个单位时目标值Z增加yi个单位,2.2 对偶性质Dual property,在例2.8中，,2.2 对偶性质Dual property,Y=（2，2，0，0，11）为对偶问题最优解,第一种资源的影子价格为y1=2，第二种资源的影子价格为y2=2，即当第一种资源增加一个单位时，Z增加2个单位，当第二种资源增加一个单位时，Z增加2个单位,正确理解影子价格，利用影子价格作下列经济活动分析（1）调节生产规模例如，目标函数Z表示利润（或产值），当第i种资源的影子价格大于零（或高于市场价格）时，表示有利可图，

23、企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模（2）生产要素对产出贡献的分解通过影子价格分析每种资源获得多少产出例如，企业获得100万元的利润，生产过程中产品的直接消耗的资源有材料A、材料B、设备和工时，这些资源各产生多少利润，由影子价格可以大致估计出来（3）由性质2.5知，第i个松弛变量大于零时第i个对偶变量等于零，并不能说明该资源在生产过程中没有作出贡献，只能理解为第i种资源有剩余时再增加该资源量不能给企业带来利润或产值的增加,2.2 对偶性质Dual property,例如，第一种资源的影子价格为y1=2，第二种资

24、源的影子价格为y2=2，即当第一种资源增加一个单位时，Z增加2个单位，当第二种资源增加一个单位时，Z增加2个单位。,企业可利用影子价格调节生产规模。例如，目标函数Z表示利润（或产值)，当第i种资源的影子价格大于零(或高于市场价格）时，表示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零（或低于市场价格），企业不能增加收益，这时应将资源卖掉或出让，缩小生产规模。应当注意，是在最优基B不变的条件下有上述经济含义，当某种资源增加或减少后，最优基B可能发生了变化，这时yi的值也随之变化。,2.2 对偶性质Dual property,在例2.1中，原问题的最优解X（24.24，0，46.96）,

25、对偶问题的最优解Y（10.6，0.91，0，0）,最优值z=w=5712.12,分析：1.y1=10.6说明在现有的资源限量的条件下，增加一个单位第一种资源可以给企业带来10.6元的利润；如果要出售该资源，其价格至少在成本价上加10.6元。,2.y3=0说明增加第三种资源不会增加利润，因为第三种资源还 没有用完。,问题：1.第三、四种资源的售价是多少，是否不值钱？,2.如果要增加利润，企业应增加哪几种资源，各增加多少后再进行调整？,2.2 对偶性质Dual property,（4）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念同一种资源在不同的

26、企业、生产不同的产品或在不同时期影子价格都不一样 例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产值是不一样的（5）影子价格是一个变量由 的含义知影子价格是一种边际产出，与bi的基数有关，在最优基B不变的条件下yi不变，当某种资源增加或减少后，最优基B可能发生了变化，这时yi的值也随之发生变化,2.2 对偶性质Dual property,作业：教材P62 T3、4、5,2.2 对偶性质Dual property,1.本节介绍的6个性质都是原问题与对偶问题的有关解的对应关系；2.性质5和性质6可用来已知一个问题的最优解求另一个问题的最优解；3

27、.第2章的大部分概念都集中在这一节。,下一节：对偶单纯形法,4.深刻领会影子价格的含义，学会用影子价格作经济活动分析。,2.3 对偶单纯形法Dual Simplex Method,单纯形表最优基必须同时满足两个条件,右端列中的所有i0,可行性条件,全部检验数j0,最优性条件,（1）,（2）,单纯形法的迭代过程,i 0 j0,i0 j 0,i0 j0,对偶单纯形法的迭代过程,i0 j0,设原问题是（记为LP）：,对偶问题是（记为DP）：,根据对偶性质6，可以构造一个求线性规划的另一种方法，即对偶单纯形法。,对偶单纯形法的计算步骤：,对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题时j0，

28、极小化问题时j0。,2.3 对偶单纯形法Dual Simplex Method,(1)将线性规划的约束化为等式，求出一组基本解，因为对偶问题可行，即全部检验数j0（max）或j0（min）,当基本解可行时，则达到最优解；若基本解不可行，即有某个基变量的解bi0，则进行换基计算；,(2)先确定出基变量。l 行对应的变量x出基；,(3)再选进基变量。求最小比值,(4)求新的基本解，用初等变换将主元素alk化为l,k列其它元素化为零，得到新的基本解，转到第一步重复运算。,2.3 对偶单纯形法Dual Simplex Method,【例2.9】用对偶单纯形法求解,【解】先将约束不等式化为等式，再两边同

29、乘以（1），得到,x4、x5 为基变量，用对偶单纯形法，迭代过程如表2-7所示。,2.3 对偶单纯形法Dual Simplex Method,表2-7,2.3 对偶单纯形法Dual Simplex Method,最优解：X(4，1，0)T；Z=17,应当注意：,（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；,（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；,（3）最小比值中 的绝对值是使得比值非负，在极小化问题时j0，分母aij0 这时必须取绝对值。在极大化问题中，j0分母aij0，总满足非负，这时绝对值符号不起作用，可以去掉。如在本例中将目

30、标函数写成,这里j0在求k时就可以不带绝对值符号。,2.3 对偶单纯形法Dual Simplex Method,（6）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样,（4）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；,（5）普通单纯形法的最小比值是其目的是保证下一个原问题的基本解可行，对偶单纯形法的最小比值是,其目的是保证下一个对偶问题的基本解可行；,2.3 对偶单纯形法Dual Simplex Method,【例2.10】用对偶单

31、纯形法求解,【解】取x3、x4为初始基变量，用对偶单纯形法迭代如表2-8所示。,表28,第二张表中x 4=60且第二行的系数全部大于等于零，说明 原问题无可行解。,2.3 对偶单纯形法Dual Simplex Method,例2.10可用性质2.6及性质2.2来说明，表（2）的第2行对应于对偶问题的第2列（相差一个负号），检验数行对应于对偶问题的常数项（相差一个负号），比值 对应于对偶问题的比值 失效，也说明 即对偶问题具有无界解，由性质2.2知原问题无可行解,2.3 对偶单纯形法Dual Simplex Method,本节利用对偶性质6：原问题的检验数与对偶问题的基本解的对应关系，介绍了一种

32、特殊线性规划的求解方法对偶单纯形法。,1.对偶单纯形法的应用条件；,2.出基与进基的顺序；,3.如何求最小比值；,4.最优解、无可行解的判断。,作业：教材P62 T6,2.3 对偶单纯形法Dual Simplex Method,下一节：灵敏度分析与参数分析,2.4 灵敏度与参数分析 Sensitivity and Parametric Analysis,线性规划的灵敏度分析也称为敏感性分析，它是研究和分析参数（cj，bi，aij）的波动对最优解的影响程度，主要研究下面两个方面：,（1）参数在什么范围内变化时，原最优解或最优基不变；,（2）当参数已经变化时，最优解或最优基有何变化。（3）价值系数

33、和资源限量系数附带一个参数，分析的变化对最优解的影响。,当模型的参数发生变化后，可以不必对线性规划问题重新求解，而用灵敏度分析方法直接在原线性规划取得的最优结果的基础上进行分析或求解.,2.4 灵敏度与参数分析 Sensitivity and Parametric Analysis,线性规划的参数分析(Parametric Analysis)是研究和分析目标函数或约束中含有参数在不同的波动范围内最优解和最优值的变化情况这种含有参数的线性规划也称为参数线性规划,设线性规划,其中Amn，线性规划存在最优解，最优基的逆矩阵为,检验数为,价值系数cj的变化分析,为使最优解不变，求cj的变化范围。,2.

34、4 灵敏度与参数分析 Sensitivity and Parametric Analysis,(1)cj是非基变量xj的系数,即cj的增量 不超过cj的检验数的相反数时，最优解不变，否则最优解就要改变。,所以,2.4 灵敏度与参数分析 Sensitivity and Parametric Analysis,(2)ci是基变量xi的系数,令,因ciCB，所以每个检验数j中含有c i,当c i变化为c ici 后j同时变化，这时令,2.4 灵敏度与参数分析 Sensitivity and Parametric Analysis,【例2.11】线性规划,（1）求最优解；,（2）分别求c1,c2,c3

35、的变化范围，使得最优解不变。,要使得所有，则有,2.4 灵敏度分析Sensitivity Analysis,只要求出上限2及下限1就可以求出ci的变化区间,【解】（1）加入松弛变量x4,x5,x6，用单纯形法求解，最优表如表29所示。,表29,最优解X=（5，0，15）;最优值Z=50。,2.4 灵敏度分析Sensitivity Analysis,x2为非基变量，x 1、x 3为基变量，则,c2变化范围是：,(2)对于c1：表29是x 1对应行的系数只有一个负数,有两个正数,c1的变化范围是：,2.4 灵敏度分析Sensitivity Analysis,c3无上界，即有c32，c3的变化范围是

36、。,对于c3：表2-9中x3对应行,2.4 灵敏度分析Sensitivity Analysis,对c3的变化范围，也可直接从表29推出，将c3=3写成,2.4 灵敏度分析Sensitivity Analysis,分别计算非基变量的检验数并令其小于等于零。,得c32，同理，用此方法可求出c2和c1的变化区间。,2.4.2 资源限量bi变化分析,为了使最优基B不变，求bi的变化范围。,设br的增量为br，b的增量为 原线性规划的最优解为X，基变量为XB=B1b，要使最优基B不变，即要求,要使 同时小于等于零，解不等式组,2.4 灵敏度分析Sensitivity Analysis,因为,2.4 灵敏

37、度分析Sensitivity Analysis,所以,令,2.4 灵敏度分析Sensitivity Analysis,因而要使得所有 必须满足,这个公式与求 的 上、下限的公式类似，比值的分子都小于等于零，分母是B1中第r列的元素，大于等于比值小于零的最大值，小于等于比值大于零的最小值。当某个 时，可能无上界或无下界。,【例2.12】求例2.11的b1、b2、b3分别在什么范围内变化时，原最优基不变。,2.4 灵敏度分析Sensitivity Analysis,【解】由表29知，最优基B、B1及分别为,对于b1：比值的分母取B1的第一列，这里只有11=1，而21=31=0，则,2.4 灵敏度分

38、析Sensitivity Analysis,b1无上界，即b15，因而b1在35,+)内变化时最 优基不变。,对于b2：比值的分母取B1的第二列，120，220，则,即b2在15，25上变化时最优基不变,2.4 灵敏度分析Sensitivity Analysis,对于b3：比值的分母取B1的第三列，有,故有15b35，b3在0，20上变化时最优基不变。,灵敏度分析方法还可以分析工艺系数aij的变化对最优解的影响，对增加约束、变量或减少约束、变量等情形的分析，下面以一个例子来说明这些分析方法。,若线性规划模型是一个生产计划模型，当求出cj或bi的最大允许变化范围时，就可随时根据市场的变化来掌握生

39、产计划的调整。,2.4 灵敏度分析Sensitivity Analysis,【例2.13】考虑下列线性规划,求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。,（1）改变右端常数为:,2.4 灵敏度分析Sensitivity Analysis,2.4.3 综合分析,（2）改变目标函数x3的系数为c3=1;,（3）改变目标函数中x2的系数为c2=2；,（4）改变x2的系数为,（5）改变约束（1）为,（6）增加新约束,（7）增加新约束,2.4 灵敏度分析Sensitivity Analysis,【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如210所示。,表210,2

40、.4 灵敏度分析Sensitivity Analysis,最优解X=（1，0，2，0，0，1）T，最优值Z=10,2.4 灵敏度分析Sensitivity Analysis,最优基矩阵及其逆,（1）基变量的解为,基本解不可行，将求得的XB代替表210中的常数项，用对偶单纯形法求解，其结果见表211所示。,表211,2.4 灵敏度分析Sensitivity Analysis,最优解,（2）由表210容易得到基变量x3的系数c3的增量变化范围是,而c3=1在允许的变化范围之外，故表210的解不是最优解。非基变量的检验数,x4进基，用单纯形法计算，得到表212,2.4 灵敏度分析Sensitivit

41、y Analysis,表212,最优解为X=（3，0，0，14，0，1)T，最优值z=6。,2.4 灵敏度分析Sensitivity Analysis,（3）c2是非基变量x2的系数，由表27知，由 1变为2时，或直接求出x2的检验数,从而最优解不变，即X=(1，0，2，0，0，1)T。,2.4 灵敏度分析Sensitivity Analysis,(4)这时目标函数的系数和约束条件的系数都变化了，同样求出2判别最优解是否改变。,x2进基，计算结果如表213所示,2.4 灵敏度分析Sensitivity Analysis,表213,最优解,2.4 灵敏度分析Sensitivity Analysi

42、s,（5）第一个约束变为 实际上是改变了a12及b1，这时要求2及XB，判断解的情况。,因为 可行，所以最优解为,2.4 灵敏度分析Sensitivity Analysis,。,应当注意，当 且 时用单纯形法继续迭代，当 且 不可行时用对偶单纯形法继续迭代，当 且 不可行时，需加入人工变量另找可行基.,（6）引入松弛变量x7得,x1、x3是基变量，利用表27消去x1、x3，得,x7为新的基变量，基本解X=（1，0，2，0，0，1，2)T 不可行，将上式加入表210中用对偶单纯形法迭代得到表2-14。,2.4 灵敏度分析Sensitivity Analysis,表214,最优解,2.4 灵敏度分

43、析Sensitivity Analysis,（7）将原最优解代入约束 的左边有 5122=110，满足新约束，故最优解不变。,上述cj及bi的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。,2.4 灵敏度分析Sensitivity Analysis,灵敏度分析的关键在于线性规划某些参数或条件发生变化时，需要判断最优表中哪些数据发生了变化，如何求这些数据，如果不是最优解再用什么方法计算等问题前两个问题可以直接用1.5的矩阵公式判断和计算将这些问题简要综合在表2-15中,表2-15,2.4 灵敏度分析Sensitivit

44、y Analysis,2.4.4 参数分析(Parametric Analysis),参数分析是研究线性规划的价值系数与资源限量中附加了一个参数：,分析参数在不同取值区间内最优解的变化分析，是研究最优解对于参数摄动的一种灵敏度分析方法,2.4 灵敏度分析Sensitivity Analysis,【例2.14】线性规划,(1)求参数0时的最优解(2)讨论在区间(，)内的变化,2.4 灵敏度分析Sensitivity Analysis,【解】（1）0时就是普通线性规划，加入松弛变量x4、x5，最终单纯形表见表2-16 最优解X（8，9，0），目标值Z67,表2-16,2.4 灵敏度分析Sensit

45、ivity Analysis,(2)将约束条件右端分解成下列成的线性式,则带参数的单纯形表见表2-17,2.4 灵敏度分析Sensitivity Analysis,表2-17,(1)当18时表2-17(1)仍然是最优表,最优解是参数的函数 X（8，9+0.5，0）,目标值Z67+1.5(2)当18时最优解X（8，0，0），目标值Z40(3)当18时不可行，用对偶单纯形法，x2出基x5进基得到表2-17(2)，当3018时最优解X=（20+2/3，0，0），最优值Z100+10/3(4)当30时无可行解目标函数与参数的关系如图2.1所示,2.4 灵敏度分析Sensitivity Analysis

46、,同理，当目标函数中含有参数时，先令参数等于零，再用公式求出检验数，分析参数在不同区间解的关系,图2.1,The End of Chapter 2,1.注意最优解与最优基不变的区别；2.掌握某个参数变化后，最优表中哪些数据会发生变化，如何变化；3.模型发生变化后不是重新求解，而是在原模型的最优表中求出变化后的数据，根据变化条件，选择合适的方法继续计算。4.了解参数分析的思路。,5.利用WinQSB软件中的修改（Modify problem）和Perform Parametric Analysis功能，进行灵敏度分析和参数分析。,2.4 灵敏度分析Sensitivity Analysis,作业：P63 T 7、8,