运筹学--对偶理论课件.ppt

1、1,第二章 LP的对偶理论(dual theory),1 对偶问题的提出 2 原问题与对偶问题 3 对偶问题的基本性质 4 对偶问题的经济意义影子价格 5 对偶单纯形法 6 灵敏度分析 7 参数线性规划,2,1 对偶问题的提出 一、对偶问题的提出 在理论上和实践上，对偶理论都是LP中一个十分重要和有趣的概念。支持对偶理论的基本思想是，每一个LP问题都存在一个与其对偶的问题，原问题与对偶问题对一个实际问题从不同角度提出来，并进行描述，组成一对互为对偶的LP问题。在求出一个问题解的时候，也同时可以得到另一个问题的解。下面通过一个例子看一下对偶问题的经济意义。,【例1】：美佳公司计划制造甲乙两种产品

2、。已知各制造一件产品时分别占用设备A,B的台时，每天可用于这两种产品的能力，各售出一件时的获利能力如下表。问该公司应制造两种产品各多少件，获取的利润最大？,4,MAX Z= 2X1+X2 满足条件： X1+5X2 17 6X1+2X2 24 X10, X20,列出线性规划模型为：,现从另一个角度提出问题：假定东方公司想把美佳公司 （的资源)收买过来，它至少应付出多大代价（底线）， 才能使美佳公司愿意放弃生产活动，出让自己的资源？ 显然，该企业愿意出让的条件是，出让的价格不应低 于同等数量资源由自己组织生产活动时获取的利润。 分析：设y1 , y2 分别表示单位时间（h）设备A 、设备B 的出让

3、代价，则从东方公司来看，希望用最小的代价把全 部资源收买过来， 故有： min w=17 y1 +24 y2 因生产一件甲产品需两种设备分别为1、6小时，盈利2 元，生产一件乙产品需两种设备分别为5、2小时，盈利1 元。从美佳公司来看，出让资源获得的利润应不少于自己 组织生产获得的利润。因此有： y1 + 6y2 2 5 y1 +2 y2 1,要使收买成功，双方的要求都必须满足，于是得到出让资源问题的线性规划数学模型： min w=17 y1 +24 y2 y1 + 6y2 2 5 y1 +2 y2 1 y1 0, y2 0,于是，我们得到两个线性规划：,原问题： LP1: maxZ=2X1+

4、X2 X1 +5X2 17 6X1+2X2 24 X1 0, X2 0,对偶问题： LP2： min w=17 y1 +24 y2 y1 + 6y2 2 5 y1 + 2y2 1 y1 0, y2 0,我们把LP2称为LP1的对偶问题；若把LP2看成原问题，则LP1就是LP2的对偶问题。 比较两者，看有什么规律？,1）目标函数的目标互为相反(max,min)； 2）目标函数的系数是另一个约束条件右端的向量； 3）约束系数矩阵是另一个的约束系数矩 阵的转置； 4）约束方程的个数与另一个的变量的个数相等； 5）约束条件在一个问题中为“ ”，在另一个问题中为 “”。,9,二、对偶问题的一般提法（对称

5、形式下对偶问题的一般提法） 看书P41 原问题：m种资源bi(i=1m)生产n种产品xj(j=1n)，获利分别为cj (j=1n)元，aij为工艺系数，则原问题为 Maxz=cjxj aijxjbi(i=1m) xj0 (j=1n) 对偶问题：设将上述资源出售定价为yi（i=1m），使获得收益不低于原企业生产产品出售获得的收益，则应满足 Minw=biyi aijyi cj (j=1n) yi0 (i=1m),10,三、LP的对偶问题也可以从数学的角度引出来 （了解） 检验数为B=CB-CBB-1B (1) N=CN-CBB-1N (2) -Y= -CBB-1 (1) (2)合到一起，检验数一

6、般形式为 ：=C-CBB-1A 令Y= CBB-1 ，称为单纯形乘子 当所有j 0时， YA C Y 0 又Z=CX=CBb = CBB-1b=Yb= W,所以： min w=Yb st. YA C Y 0,11,从例子看到，原问题为求max ，对偶问题为求min ，因为： （1）对偶问题的可行解（Y= CBB-1 ）满足原问题的最优化条件（ 0）； （2）因此对原问题来说，只有最优解（X=B-1b）才是其对偶问题的可行解。 （3）也即原问题的最优解目标函数值是它的对偶问题可行解目标函数值最小的一个。(注意对偶问题求min)( Z=CX=CBb= CBB-1b=Yb= W) （4）由此可知，原

7、问题目标函数的最大值对应于对偶问题的目标函数的最小值。 （具体见第三节基本性质）,12,一、对偶关系（对称形式）,2 原问题与对偶问题,原问题 对偶问题 max z=CX min w=Yb st. AX b st. YA C X 0 Y 0 1、看书上表2.1，验证对应关系 2、看教材例1。写出最大化问题的对偶问题 3、对称性：LP的原问题与对偶问题之间存在对称关系， 即LP对偶问题的对偶是原问题。 看例2，通过例子得出结论 第一步，化为对称形式下的原问题形式；第二步，根据对 应关系写出其对偶问题；第三步，做一变换，得到原问题 结论：LP对偶问题与原问题互为对偶。,二、非对称形式原问题与对偶问

8、题之间的关系 看例3，是一个最小化问题 第一步，化为对称形式下的对偶问题形式（min， ，变量非负）； 第二步，引入对偶变量（根据原问题约束条件符号来 设），根据对应关系写出其对偶问题； 第三步，变换为一般形式。 设原问题的三个约束条件的对偶变量分别为y1、y2、 y3(每一个约束条件对应一个对偶变量) 由此，对于非对称形式原问题与对偶问题之间的关 系可用下表反映：,14,15,【例2】：给出下列线性规划的对偶问题： MAX Z=X1+ 2 X2 + X3 X1+ X2 X3 2 y1 X1 X2 + X3 =1 y2 st. 2X1+ X2 + X3 2 y3 X1 0, X2 0, X3

9、无约束,16,【例2】：给出下列线性规划的对偶问题： MAX Z=X1+ 2 X2 + X3 X1+ X2 X3 2 y1 X1 X2 + X3 =1 y2 st. 2X1+X2 + X3 2 y3 X1 0, X2 0, X3 无约束 其对偶问题为： min w=2 y1 + y2 +2 y3 y1 + y2 +2y3 1 X1 st. y1 - y2 + y3 2 X2 -y1 +y2 + y3 =1 X3 y1 0, y2 无约束，y3 0,17,【例3】：给出下列线性规划的对偶问题： min Z=2X1+ 8 X2 -4X3 X1+3X2 3X3 30 y1 -X1 +5X2 + 4X

10、3 =80 y2 st. 4X1+ 2X2 - 4X3 50 y3 X1 0, X2 0, X3 无约束,18,【例3】 ：给出下列线性规划的对偶问题： min Z=2X1+ 8 X2 -4X3 X1+3X2 3X3 30 y1 -X1 +5X2 + 4X3 =80 y2 st. 4X1+ 2X2 - 4X3 50 y3 X1 0, X2 0, X3 无约束 其对偶问题为： MAX w=30 y1 +80 y2 +50y3 y1 - y2 + 4y3 2 x1 st. 3 y1 +5y2 +2y3 8 x2 -3y1 +4y2 - 4y3 =-4 x3 y1 0, y2 无约束，y3 0,19

11、,先相同，后相反；先相反，后相同 最大化问题找其对偶问题，约束条件与其对偶变量的符号相同，而其变量的符号与其对应约束条件的符号相反； 最小化问题找其对偶问题，约束条件与其对偶变量的符号相反，而其变量的符号与其对应约束条件的符号相同。,20,3 对偶问题的基本性质,原问题 对偶问题 max z=CX min w=Yb st. AX b st. YA C X 0 Y 0 可行解 X Y 本节讨论先假定原LP与对偶问题为对称形式的LP问 题，然后说明对偶问题的基本性质在非对称形式（一般形 式）时也适用。 性质是就对称形式提出的，可行平行的推广到一般 形式的问题中去，只不过叙述上也要有相应的变动。,2

12、1,1、弱对偶性：CXYb X，Y是可行解 （证明用到了上面两个约束条件） 性质含义：极大化问题的任一可行解的目标函数值，不大于对偶问题的任一可行解的目标函数值。 也即：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之，对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。 【例4】已知线性规划问题: maxZ=4 x1 + 7x2+2x3 s.t. 应用对偶理论证明该问题最优解的目标函数值不大于25.,22,2、最优性：当原问题与对偶问题均有可行解X、Y，且当 CX=Yb时， 则X、Y分别是原问题与对偶问题的最优解。（由性质1证明） （隐含：两者都存在可行解，则均存在最优解

13、） 【例5】已知线性规划问题： MAX Z = 3x1 + 2x2 -x1 +2x2 4 3x1 +2x2 14 x1 x2 3 x1，x2 0 （1）写出对偶问题；（2）利用对偶问题性质证明原问 题和对偶问题都存在最优解。,23,3、无界性：如果原问题（对偶问题）有无界解，则对偶问题（原问题）无可行解。 即原问题有可行解且目标函数值无界（可达正无穷），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界（可达负无穷），则其原问题无可行解。（性质1，CXYb，YbCX） 因此，如果原问题无可行解时，对偶问题无可行解或具有无界解 对偶问题无可行解时，原问题无可行解或具有无界解 （原问题有可

14、行解，对偶问题无可行解，则原问题有无界解）,24,【例6】已知线性规划问题 max Z = x1 - x2 +x3 x1 - x3 4 x1 x2 +2x3 3 x1 x2 x3 0 试应用对偶理论证明上述线性规划问题无最优解.（无界解属于无最优解）,25,4、强对偶性（对偶定理）：若原问题有最优解，则对偶问题也一定有最优解，且目标函数值相等。 证明： Z=CX=CBb= CBB-1b=Yb= W 根据性质2，Y是对偶问题最优解,26,小结： 1、原问题有可行解，则对偶问题： 有可行解，则两者均具有最优解； 无可行解，则原问题具有无界解。 2、原问题无可行解，则对偶问题可以无可行解或者无界解。

15、 3、原问题无界解，对偶问题无可行解。（无界性） 4、原问题有最优解，对偶问题有最优解，且CX=Yb。（对偶定理）,27,5、互补松弛性：变量为“0”时，其对应约束条件为“=”；约束条件为“”时，其对应对偶变量为“0” （线性规划问题的约束条件与对偶变量一一对应）(一个问题的约束条件和另一个问题的变量对应，一个问题的变量和另一个问题的约束条件对应) 【例7】已知线性规划问题 minZ =8X1+ 6X2 +3X3 +6X4 ST X1+ 2X2 + X4 3 3X1+ X2 + X3 +X4 6 X3 + X4 2 X1 + X3 2 Xj0 j=1,2,3,4 已知原问题最优解为：X=（1,

16、1,2,0）T 试利用对偶性质求对偶问题的最优解。,28,【例8】 :已知下列线性规划问题的对偶问题的最优解为(6/5, 1/5),求该线性规划问题的最优解. MAX Z=X1+ 2 X2 + 3X3 +4X4 X1+2X2 + 2X3 + 3X4 20 Y1 2 X1+ X2 + 3X3 + 2X4 20 Y2 X1, X2 , X3 ,X4 0,29,解:其对偶问题为: MIN W= 20Y1+20Y2+5Y3 Y1 +2Y21 1) X1 2Y1+Y2 2 2) X2 2Y1+3Y2 3 3) X3 3Y1+2Y2 4 4) X4 Y1 0,Y2 0,30,将解代入到对偶问题的四个约束条

17、件可得 1*1.2+2*0.21; 2*1.2+0.21; 2*1.23*0.2=3; 3*1.2+2*0.2=4 那么由互补松驰性得，x1=0; x2=0。再由y1, y20得，原问题的两个约束条件均取等号，这样联立方程 从而:原问题的约束变为: 2X3 + 3X4 =20 3X3 + 2X4 =20 解此方程得: X3 = X4 =4 于是原问题的最优解为:(0,0,4,4)目标函数值z=28.,31,【例9】已知线性规划问题 min W=2X1+3X2+5X3 +2X4+3X5 ST X1 + X2+2X3+X4+3X54 2X1X2+3X3+X4+ X53 Xj0 j=1,2,3,4,

18、5 已知对偶问题最优解为：Y1=4/5 Y2=3/5 Z=5 试利用对偶性质求原问题的最优解。,32,解：由互补松弛定理可得方程： 3X1+X5=4 2X1+X5=3 解此方程组可得：X1=1，X5=1 所以原问题的最优解是： X=（1,0,0,0,1）T Z=5,33,. 【例10】已知线性规划问题： 其最优解为 （a）求k的值； （b）写出并求其对偶问题的最优解。,34,解：先写出其对偶问题如下： 由及互补松弛性质得 解得,35,小结： 给出原问题的最优解，其不等于0的变量对应对偶问题的约束条件取“=”，代入原问题约束条件，为“”时，其对应对偶变量为“0”； 给出对偶问题的最优解，其不等于

19、0的变量对应对原问题的约束条件取“=”，代入对偶问题约束条件，为“”时，其对应对偶变量为“0”；,36,6、a、单纯形法迭代每一步同时，其检验数行的相反数得到其对偶问题的一个基解（不一定基可行解）；b 、松弛变量、剩余变量与变量的对应关系；c、互相对应的变量在一个LP中为基变量，在另一个LP中为非基变量；d、Z=W。 （这个定理在非对称形式下有所不同）,37,w1 wi wm wm+1 wm+j wn+m,x1 xj xn xn+1 xn+i xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjwm+j=0wixn+i=0(i=1,2,m; j=1,2,n)

20、在一对变量中，其中一个大于0，另一个一定等于0,38,39,4 影子价格DP的经济解释,上节性质6，在单纯形法的每步迭代中有目标函数 对偶变量 yi的意义代表对一个单位第i种资源的估价，称为影子价格（shadow price）。,40,1、影子价格不同于市场价格:b代表资源的拥有量, yi代表在资源最优利用条件下对单位资源的估价，但不是市场价，而是对资源在生产中做出的贡献的估价，一般称为影子价格。市场价格是已知的，而影子价格则与资源的利用情况有关，利用的好，影子价格就高，反之亦然。（用到不同地方，价值不一样）,41,2、影子价格是一种边际价格（对偶变量 yi在经济上表示原问题第i种资源的边际价

21、值）。将z对bi求偏导得 ，这说明yi的值相当于在给定 的生产条件下，bi每增加一个单位的资源时，目标函数z的增量。 对偶问题最优解y的经济意义：在其它条件不变的情况下，单位资源的变化所引起的目标函数最优值的变化。 在最优条件下,Z =Yb,目标函数是资源量的函数。,42,3、影子价格又是一种机会成本。当市场价大于影子价格，卖出资源；当市场价小于影子价格，买入资源，组织生产。 4、互补松弛性的解释。aijbi时，yi=0,当yi0时，有aij=bi，表明生产过程中如果某种资源没有得到充分利用，该种资源的影子价格为0;当该种影子价格不为零时，表示该种资源已消耗尽。 判断题： （1）若某种资源的影

22、子价格等于k，在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数最大值将增加5k吗？（其它资源的拥有量还足够用时） （2）已知yi为某线性规划问题的对偶问题最优解中第i个分量，若yi=0，能否肯定在有优生产计划中第i种资源一定有剩余。,43,5、单纯形法中检验数的经济意义。 j=cj-ciaij=cj-aijyi cj aijyi cj aijyi 6、解的应用。利用影子价格可以有效控制和使用资源，例如对紧缺资源的控制(择优分配);作为同类企业经济效益的评估标准;通过帮助企业提高工艺和管理水平,降低资源的耗费来提高资源的影子价格;确定内部结算价格；确定上交的利润额。,44,7、影

23、子价格说明了不同资源对总的经济效益产生的影响，因此对企业经营管理提供一些有价值的信息： 增加哪一种资源最有利。影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益； 花多大代价增加该资源才最有利； 衡量资源使用是否合理； 告诉经营者补给紧缺资源的数量，不要盲目大量补给； 产品价格变动对资源的影响； 售价多少。提示设备出租或原材料转让的基价。,45,8、理解时注意几点： 影子价格是针对约束条件而言的，约束条件可以为资源约束，也可以为产量约束，这时产品的产量不超过市场需求量，影

24、子价格含义为：扩大销售对总产值的影响。 若原问题的价值系数Cj表示单位产值，则yi 称为影子价格；若原问题的价值系数Cj表示单位利润，则yi 称为影子利润。 影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。 本节分析的是在最优解的最优基没有变化的前提下进行的（其它资源够用）。即影子价格的经济含义，是指资源在一定范围内增加时的情况，当某种资源的增加超过了这个“一定的范围”时，总利润的增加量则不是按照影子价格给出的数值线性地增加。更进一步分析结合灵敏度分析来讨论。 注意：影子价格的重点是对它的理解和在实践中的应用。,1、原始问题是利润最大化的生产计划问题,单位产

25、品的利润（元/件）,产品产量（件）,总利润（元）,资源限量（吨）,单位产品消耗的资源（吨/件）,剩余的资源（吨）,消耗的资源（吨）,补充理解内容：对偶的经济解释,2、对偶问题,资源限量（吨）,资源价格（元/吨）,总利润（元）,对偶问题是资源定价问题，对偶问题的最优解w1、w2、.、wm称为m种资源的影子价格（Shadow Price）,原始和对偶问题都取得最优解时，最大利润 max z=min y,3、资源影子价格的性质,影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于0,w1 w2 wm,4、产品的机会

26、成本,机会成本 表示减少一件产品所节省的资源可以增加的利润,增加单位资源可以增加的利润,减少一件产品可以节省的资源,机会成本,利润,差额成本,5、产品的差额成本（Reduced Cost）,差额成本=机会成本 - 利润,6、互补松弛关系的经济解释,在利润最大化的生产计划中 （1）边际利润大于0的资源没有剩余 （2）有剩余的资源边际利润等于0 （3）安排生产的产品机会成本等于利润 （4）机会成本大于利润的产品不安排生产,52,5 对偶单纯形法 从DLP的性质和前面的例子我们知道：在原问题的最优单纯形表中，将松弛变量的检验数的相反数代入DLP的目标函数，可发现: 1)两个函数值相等，进而发现: 2

27、)检验数的相反数是DLP的最优解. 也就是在一个最优单纯形表中可以同时得到原问题和 DLP的最优解。,53,我们再进一步分析单纯形法： 单纯形法实质上是从原LP为可行解而DLP为不可行解向DLP为可行解转化，那么我们可否从DLP为可行解，原LP为不可行解向原LP为可行解转化呢？于是我们就得到一个新的方法：对偶单纯形法。 对偶单纯形法实质是单纯形法应用于对偶问题的计算。 对偶单纯形法基本思路：允许b列出现负数，而保持所有的检验数全都非正的情况下（对偶问题为可行解），进行换基迭代，使b列全化成非负数（原问题为可行解），而检验数保持全非正，从而得到原问题的最优解。,54,步骤：1、允许b列出现负数的

28、情况下，填初始单纯形 表，保持检验数行全非正。 2、如果b列出现某个或某几个负数，则进行换基 迭代： 1）先定出基变量： b列中负数绝对值最大的对应的变量（Xr ） ； 2）次定入基变量：用检验数行除以第r行对应的 负系数取比值最小者对应的变量（Xs）为入基变量; 3）以ars为主元素做行初等变换：将ars化为1，所在列，其他元素化为0，得到新的系数矩阵，填新的单纯形表。 3、重复2直到b列中无负数而所有j全非正从而得最优解。,55,【例11】用对偶单纯形法求解下列线性规划,min Z=5X1+ 2X2 +6X3 2X1+4X2 +8X3 24 st. 4X1 +X2 + 4X3 8 X1 0

29、, X2 0, X3 0 解:将问题改为如下形式: MAX(-Z)= -5X1- 2X2 -6X3+0X4 +0X5 -2X1-4X2 -8X3 +X4 = -24 st. -4X1 -X2 -4X3 +X5= -8 X1 , X2 , X3, X4 , X5, 0,56,最小,原始不可行,对偶可行,进基,出基,57,原问题的最优解为： X1 =0, X2 =4 , X3=1 ； 对偶问题的最优解为： y1= ，y2=1,58,注意几点： 1、对偶问题有可行解（为无界解），原问题无可行解的判断：当br0时，对j=1,2n有arj 0； 2、用对偶单纯形法求解时，当所有的约束条件为“”时，不必引

30、入人工变量使计算简化； 3、在初始单纯形表其对偶问题应是基可行解这点 （ j 0，目标函数系数皆为负 ）对多数LP很难 实现，因此，对偶单纯形法一般不单独使用，而 主要用于灵敏度分析及整数规划等有关问题中；,59,4、适用条件：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解） 因此，对偶单纯形法主要适合于解如下形式的线性规划问题：,60,在引入松弛变量化为标准型之后，约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最

31、好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。当然，在对线性规划进行灵敏度分析中也要用到对偶单纯形方法，可以简化计算。,61,5、规律： 1）看原问题如果原问题可行（ b 0 ），用单纯形法向对偶问题可行转换 2）看原问题如果对偶可行（ 0），用对偶单纯形法向原问题可行转换 3）如果两者都不可行，且线性规划是非对称的，如何做？ 我们看下列实例（作为参考）： 求下列线性规划及对偶问题的最优解。,62,min Z=3X1+ 2X2 -2X3 X1-X2 +X3 4 st. -2X1 +3X2 - X3 5 2X

32、1 -3X2 + X3 2 X1 0, X2 0, X3 =0 解:化为标准形 MAX(- Z)=-3X1- 2X2 +2X3 X1-X2 +X3 +X4 =4 st. 2X1 - 3X2 + X3 +X5 =-5 -2X1 + 3X2 - X3 +X6 =-2 X1 , X2 , X3 , X4 ,X5 ,X6 0,63,两者均不可行,可先让对偶可行 (让检验数0) ,再向原问题可行转换，用对偶单纯形法。,64,已对偶可行,再用对偶单纯形法,最优解(5,7,6),最优值为17 对偶问题的最优解为: (-7,5,10) 为什么?,65,6灵敏度分析,一、定义 灵敏度分析是指对系统或事物因周围条

33、件变化显示出来的敏感程度的分析（灵敏度分析又称敏感性分析或优化后分析，这里就是研究最优解对数据变化的敏感程度） 敏感性太强，则说明最优解的稳定性程度较低。,66,二、为什么要进行灵敏度分析 线性规划研究的是一定条件下的最优化问题，采用优化方案可以达到节约资源、提高效益的目的，但是对“优化方案”必须要有全面的认识，不可机械地对待。 优化方案是建立在特定的资源环境和技术条件之上的，而环境和条件总是处在不断地变化之中，如产品价格、原材料成本、加工技术水平、资源消耗系数等时有波动，所以优化方案是个相对稳定的概念。当基础数据发生变化时，最优方案也就变了。 同时，基础数据往往是测算估计的数值，虽然在运算过

34、程中要求十分严格，但基础数据的误差是不可避免的。为了对优化结果有更全面的了解和恰当的运用，就需要进行灵敏度分析。,67,三、所要解决的问题：两个方面 1、这些参数中一个或几个发生变化时，问题的最优解会有什么变化； 2、这些参数在一个多大范围内变化时，问题的最优解不变 。 四、思路 将参数的变化直接反应到最终单纯形表中，看其是否为最优解，如果不是，从这个表开始，求最优解。,68,五、步骤 1、将参数的变化直接反应到最终单纯形表中，具体方法： XB= B-1b（b=B-1b） Pj = B-1Pj （ Pj =B-1Pj） j =Cj -CBB-1Pj （用定义求） 2、检查原问题是否仍为可行解：

35、b列 3、检查对偶问题是否仍为可行解:检验数行 4、得出结论或者决定继续计算的步骤,69,灵敏度分析的两把尺子： j =Cj-CBB-1pj 0； xB= B-1b 0 六、掌握五种变化 1、 分析Cj变化的影响-价值系数的灵敏度分析 价值系数Cj变化只影响检验数。更换价值系数，重新计算检验数即可。 （a）如果存在有检验数大于0，用单纯形法计算； （b）Cj变化到什么程度可以保持最优基不变？ 变化后的检验数 0，得到参数变化范围 。,71,2、分析bi变化的影响-资源系数的灵敏度分析 更新b列的值即可。两种方法：书上算的变化值；直接算B-1b的值也可以 （a）如果存在有b0，用对偶纯形法计算；

36、 （b）bi变化到什么程度可以保持最优基不变？ xB= B-1b 0，得到参数变化范围。,72,3、增加一个变量的分析 ：增加一个变量，在实际问题中反映为增加一种新产品。在资源结构没有变化的条件下，是否生产这种新产品，就看它的竞争力如何。 方法：增加一列即可。 （1）Pj = B-1Pj （2）检验数用定义求即可（可以不用教材上方法）： j =Cj-CBB-1pj = Cj-CBPj 如果存在大于0的检验数，用单纯形法,73,4、分析aij变化的影响： 若xj在最终单纯形表中为非基变量，分析与3相同； 若xj在最终单纯形表中为基变量，步骤： （1）列出新表。增加一列，算法同3，例子如表2.17

37、。 （2）换出原来变量。方法：按照表2.17换为表2.18的方法替换（注意：表2.17选择主元素时标准与以前不一样，为根据具体情况硬性规定）。 （3）引进人工变量（如何引？），将原问题转化为可行解（表2.18-2.19，变换了两行，增加了一列）。因为前面的变化将使相应的B和B-1发生变化，可能出现原LP与DLP都为非可行解的情况。 （4）再用单纯形法求解（表2.19-2.20）。,74,5、增加一个约束条件的分析：将原LP最优解变量取值代入这个新增的约束条件，如果满足，新增约束条件没有起到限制作用，最优解不变；否则，增加的约束条件起到作用，步骤： （a）将新增约束条件直接反映到最终单纯形表中（如表2.8变换到表2.21，增加了一行）; （b）新表变化为标准单纯形表（表2.21到表2.22，变了一行）; （c）对偶单纯形法或单纯形法求解。 思考：（a）为什么选择为 X6为基变量；（b）为什么表2-21要变为表2-22；（c）如何变化。 注意：本节由于涉及知识点较多，常作为考试题目,75,7 参数线