第二章-对偶理论与灵敏度分析ppt课件.ppt

《第二章-对偶理论与灵敏度分析ppt课件.ppt》由会员分享，可在线阅读，更多相关《第二章-对偶理论与灵敏度分析ppt课件.ppt（134页珍藏版）》请在三一办公上搜索。

1、本章重点,1、掌握写出对偶问题的方法，原问题与其对偶问题的对应关系2、掌握对偶问题的基本理论和性质 3、理解影子价格的定义和意义4、理解并掌握对偶单纯形方法的思想和步骤5、掌握线性规划灵敏度分析(1)资源数量 bi 发生变化的分析(2)目标函数中价值系数 cj 发生变化的分析,难点,难点,了解-单纯形的矩阵描述,XS为松弛变量,单纯性法计算时，总选取单位矩阵 I 为初始基，对应基变量为XS,设迭代若干步后，基变量变为XB,XB 在初始单纯性表中的系数矩阵为 B。则该步的单纯性表中由 XB 系数组成的矩阵为单位矩阵 I，对应XS 的系数矩阵在新表中应为B-1,Y=CBB-1 称为单纯性乘子（对偶

2、变量）,2.3 对偶问题提出,例2.2：某公司在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A B两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？,举例2,Chapter 2 灵敏度分析,先根据图表来列出模型 Max Z=2X1+3X2 X1+2X2 8 4X1 16 4X2 12 X1,X2 0,举例,设用y1,y2,y3分别表示出租单位设备台时的租金和出让单位原材料A,B的附加额.,现在从另一个角度来考虑企业的决策问题。假如企业自己不生产产品，而将现有的资源转让或出租给其它企业，那么资源的

3、转让价格是多少才合理？合理的价格应是对方用最少的资金购买本企业的全部资源，而本企业所获得的利润不应低于自己用于生产时所获得的利润。这一决策问题可用下列线性规划数学模型来表示。,他在做定价决策时,作如下比较:若用一个单位设备台时和 4 个单位原材料 A 可以生产一件产品 I,可获利 2 元,那么生产每件产品 I 的设备台时和原材料出租和出让的所有收入应不低于生产一件产品 I 的利润,这就有 y1+4y22,同理将生产每件产品 II 的设备台时和原材料的出租和出让的所有收入应不低于生产一件产品II的利润,这就有2y1+4y3 3 把工厂所有设备台时和资源都出租和出让,其收入为 f=8y1+16y2

4、+12y3,从工厂决策者的角度来看，f当然是越大越好,但从接受者眼光来说f是越少越好,所以工厂决策者只可以在满足 所有产品的利润条件下,使其总收入尽可能的小.因此,我们称这个线性规划问题为线性规划问题（这称为原问题）的对偶问题。各模型中有关数据的“位置”示意图如下。,矩阵A,矩阵AT,对偶问题提出,例2.3 某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。,表2.3,不难得出下面一对对偶问题。原问题,对偶问题,不少于甲产品的利润,不少于乙产品的利润,例2.4：资源利用问题

5、考虑：资源拥有者为了实现一定的收入目标，将其所拥有的资源出售，给每一种资源如何定价？,解：表示出售单位数量的第i种资源的价格。资源拥有者在做出售资源的决策时，考虑出售资源的收入不应该低于生产所获得的收入，则有：,如果资源拥有者将所有资源出售，则他得到的总收入 f=,资源拥有者出售每一种资源的最低估价，可通过求解线性规划问题而得到。,对同一个资源利用问题，从不同的角度考虑，可以得到两个相互联系的线性规划模型，这就是线性规划的对偶问题。,由上面的例子我们可以知道原问题与对偶问题的关系1线性规划问题是对称形式 Max z=CX Min f=Yb s.t.Ax b s.t.YA c x 0 y 0“M

6、ax-”“Min-”,原问题与对偶问题的关系,列向量,行向量,n个变量,n个约束,例2.5 写出下述问题的对偶问题,解：上述问题的对偶问题为,(1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。,如上面例题所示一对对称形式的对偶规划之间具有下面的对应关系,(2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。(3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。(4)两个规划模型中的变量皆非负。,补充例子,原

7、问题：,对偶问题：,Chapter 2 灵敏度分析,2.线性规划问题是非对称形式 对于非对称形式的规划，可以按照下面的对应关系直接给出其对偶规划。（1）将模型统一为“max，”或“min，”的形式，对于其中的等式约束按下面（2）、（3）中的方法处理；,（2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；（3）若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应的那个约束为等式。综上所述，线性规划的原问题和对偶问题的关系，其变换形式归纳为表2.5,下面我们以一个例子说明上述关系,写出下述线性规划问题的对偶问题,为了写出对偶问题，思路是先将其转化

8、为对称形式，为此（1）约束条件（1a）两端同乘以-1；（2）约束条件（3a）变换为 和（3）令（4）,则线性规划变换成如下的对称形式,令对应上述4个约束的对偶变量分别为 写出对偶问题,再令 将（3b）和（4b）合并，（2b）两端同乘以-1，于是有,例2.6 写出下述线性规划问题的对偶问题,补充例题,写出下述线性规划问题的对偶问题,解：对偶问题为,小练习,写出下列问题的对偶问题,作业：2.1（1）（2）（3）,2.4 对偶问题的基本性质,【性质1】对称性 对偶问题的对偶是原问题。(P)(D)Max Z=CX Min f=Yb s.t.AX b s.t.YA C X 0 Y 0“Max-”“Min

9、-”,【证】因为 X*、Y*是可行解，故有AX*b,X*0及Y*AC，Y*0,将不等式 AX*b,两边左乘Y*，得Y*AX*Y*b,再将不等式Y*AC两边右乘X*，得C X*Y*AX*,故 C X*Y*AX*Y*b,这一性质说明了两个线性规划互为对偶时，求最大值的线性规划的任意目标值都不会大于求最小值的线性规划的任一目标值，不能理解为原问题的目标值不超过对偶问题的目标值。,【性质2】弱对偶性 设X*、Y*分别为LP(max)与 DP(min)的可行解，则,由这个性质可得到下面几个结论：,(1)（LP）的任一可行解的目标值是（DP）的最优值下界；（DP）的任一可行解的目标是（LP）的最优值的上界

10、；,(2)在互为对偶的两个问题中，若一个问题可行且具有无界解，则另一个问题无可行解；,(3)若原问题可行且另一个问题不可行，则原问题具有无界解。,【性质3】最优准则定理 设X*与Y*分别是（LP）与（DP）的可行解，则当X*、Y*是（LP）与（DP）的最优解当且仅当 C X*=Y*b.,【证】若X*、Y*为最优解，B为（LP）的最优基，则有Y*=CBB1，并且,当C X*=Y*b时，由性质1，对任意可行解 有,即Y*b是（DP）中任一可行解的目标值的下界，C X*是（LP）中任一可行解的目标值的上界，从而X*、Y*是最优解。,【性质4】线性规划的对偶原理（1）若原问题有最优解，那么对偶问题也有

11、最优解，而且二者最优值相等。（强对偶性）（2）若原问题（对偶问题）的解为无界解，则其对偶问题（原问题）无可行解。（无界性）注：这个问题的性质不存在逆。(看后面例子),【证】（1）设（LP）有最优解 X0,那么对于最优基B必有C-CBB-1A0与CBB-10，即有YAC与Y0，这里Y=CBB-1，从而Y是可行解，对目标函数有,由性质 3知 Y是最优解。,（2）由弱对偶性，显然得,注：这个问题的性质不存在逆,例如下述一对问题两者皆无可行解。原问题（对偶问题）对偶问题（原问题）min w=-x1-x2 max z=y1+y2 x1 x 2 1 y1-y2-1-x1+x 2 1-y1+y2-1 x1,

12、x 2 0 y1,y2 0,由性质 4 还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。,【性质5】互补松弛定理 设 X0、Y0 分别为（LP）与（DP）的可行解，XS 和 YS 分别是（LP）与（DP）对应的松弛变量向量，则 X0 和 Y0 是最优解当且仅当,YSX0=0 和 Y0XS=0,【证】设X和Y是最优解,由性质3，CX0=Y0b，由于XS和YS是松弛变量，则有,A X0XSbY0AYS=C,将第一式左乘Y0，第二式右乘X0得,Y0A X0Y0XSY0bY0A X0YS X0=C X0,显然有,Y0XS=YS X0,又因为

13、Y、Xs、Ys、X0，所以有,YXS=0和YS X=0,成立。,反之，当YXS=0和YS X=0时，有,YA XYbYA X=C X,显然有Y0b=CX,由性质3知 X 与 Y是（LP）与（DP）的最优解。证毕。,性质5 告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知 Y*求 X*或已知 X*求 Y*。,Y*XS=0和YS X*=0,两式称为互补松弛条件。将互补松弛条件写成下式,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：,其中,(1)当 yi*0 时，,反之当 时 yi*=0；,利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为

14、最优解。性质5的结论和证明都是假定（P）与（D）为对称形式，事实上对于非对称形式，性质5的结论仍然有效。,注：上述针对对称形式证明的对偶问题的性质，同样适应于非对称形式。,【补充例题】已知线性规划,的最优解是 求对偶问题的最优解。,【解】对偶问题是,下面举例说明互补松弛条件的应用,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为Y=（1，1），最优值w=26。,因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即,【性质6】假设原问题是：max z=CX;AX+Xs=b;X=0它的对偶问题是：min f=Yb;YA-Ys=C;Y=0 则原问题单纯形表的检验数行对应其对

15、偶 问题的一个基解。其对应关系见如下表,-,-,这里 是对应于原问题中基变量XB 剩余变量，是对应于原问题中非基变量XN剩余变量.,-,对于这六个对偶性质，这些性质是研究原问题与对偶问题解的对应关系；下表也许对您了解这些性质有帮助。,例2.7：判断下例说法是否正确，为什么？A 如果线性规划的原问题存在可行解，则其对偶 问题也一定存在可行解 B 如果线性规划的对偶问题无可行解，则原问题也一定无可行解。C 在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。,解：A不对。因为原问题为无界解时（它当然有可行解），其对偶问题

16、无可行解。B此句为A的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。,例2.8 已知线性规划问题,试用对偶理论证明上述线性规划问题有无界解（即有可行解但无最优解）。,证明：所给问题的对偶问题为,显然约束条件中与 矛盾，即此对偶问题无可行解，因此所给原问题无最优解，它只可以是无界解或者无可行解。然而X=（0，0，0）显然是它的可行解，因此它必定有无界解。,补充例题,给出线性规划,（1）写出对偶问题（2）用对偶理论证明上述线性规划目标函数值无界,解：（1）对偶问题为,上述对偶问题中,则,与对偶问题的第一个约束条件矛盾，所以对偶问题无可行解，因而原问题无最优解，

17、它只可以是无界解或者无可行解，然而x=(10,4,2)显然是他的可行解，因而它必定有无界解。,例 2.9 已知线性规划问题,已知其对偶问题的最优解为试用对偶理论找出原问题的最优解。,解：先写出它的对偶问题,将 的值代入约束条件，得到(2),(3),(4)为严格不等式;由互补松弛性得到 因为;原问题的两个约束条件的松弛变量由互补松弛性得到为 0，因此两个约束条件应该取等式,所以有,求解后得到所以原问题的最优解为X=(1,0,0,0,1)T,补充例题:已知原问题的最优解为 X*=（0,0,4），Z=12,试求对偶问题的最优解。,解:对偶问题为,将X*=（0,0,4）代入原问题中，有下式：,Chap

18、ter 2 灵敏度分析,所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题约束（3）式，y3=3。因此，对偶问题的最优解为 Y*=（0,0,3），W=12。,因为原问题和对偶问题的最优值相等，将线性规划的目标函数表达成资源的函数，故有,即 yi 是第 i 种资源的变化率，称 yi 是第 i 种资源的边际价格，说明当其它资源供应量bk(ki)不变时，bi 增加一个单位时目标值 Z 增加 yi个单位,2.5 影子价格,影子价格(Shadow price):原始线性规划问题考虑的是充分利用现有资源，以产品的数量和单位产品的收益来决定企业的总收益，没有考虑到资源的价格，但实际在构成产品的收益

19、中，不同的资源对收益的贡献也不同，它是企业生产过程中一种隐含的潜在价值，经济学中称为影子价格，即对偶问题中的决策变量 yi 的值。对偶变量 yi 就是第 i 个约束的影子价格（边际价格）,Chapter 2 灵敏度分析,影子价格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。若x*,y*分别为（LP）和（DP）的最优解，那么，cT x*=bT y*。根据 f=bTy*=b1y1*+b2y2*+bmym*可知 f/bi=yi*yi*表示 bi 变化1个单位对目标 f 产生的影响，称 yi*为 bi 的影子价格。注意：若 B 是最优基，y*=CBB-1 为影子价格向量。,Chapt

20、er 2 灵敏度分析,影子价格的经济含义(1)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。,Chapter 2 灵敏度分析,（2）影子价格表明资源增加对总效益产生的影响。根据推论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系 因此，可以将z*看

21、作是bi,i=1,2，,m的函数，对bi求偏导数可得到 这说明，如果右端常数增加一个单位，则目标函数值的增量将是,Chapter 2 灵敏度分析,（3）根据对偶问题的互补松弛性质中 时；当 时，这表明生产过程中如果某种资源 未得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。,（4）影子价格是企业生产过程中资源的一种隐含的潜在价值，表明单位资源的贡献，与市场价格是不同的两个概念同一种资源在不同的企业、生产不同的产品或在不同时期影子价格都不一样 例如，某种钢板市场价格是每吨8000元，一个企业用来生产汽车，另一个企业用来生产空调外壳，每吨钢板的产

22、值是不一样的（5）影子价格是一个变量由 的含义知影子价格是一种边际产出，与 bi 的基数有关，在最优基B不变的条件下 yi不变，当某种资源增加或减少后，最优基 B 可能发生了变化，这时 yi 的值也随之发生变化,根据对偶问题的性质，因为,当,即有,即其对偶问题的解为可行解，由此对偶问题和原问题均为最优解。反之，如果存在一个对偶问题的可行基B，即对这时只要有即原问题的解也为可行解，即两者均为最优解。否则，保持对偶可行性，进行迭代,2.6 对偶单纯形法,设原问题是（记为LP）：,对偶问题是（记为DP）：,对偶单纯形法的条件是：初始表中对偶问题可行，即极大化问题 时，极小化问题时。,对偶单纯形法的基

23、本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。,Chapter 2,对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。,这样的优点在于，一是当问题的模型中存在“=”

24、的约束条件时，不需要引入人工变量，只要在约束条件方程的两边乘以“-1”后加入松弛变量，再按单纯形法求解。二是当约束条件方程个数m大于变量个数n的时候，将原问题变换成对偶问题求解，计算量一般会小些。,Chapter 2,对偶单纯形法求解线性规划问题步骤：1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2；2.若b0,则得到最优解,停止;否则,若有bi0,3.换出变量：设min bi|bi0=bk，则选k 行的基变量为换出变量.,4.若所有akj0(j=1,2,n)，则原问题无可行解,停止;否则,若有 akj0 则选=minj/akjakj0=r/akr 那么 xr 为换入变量,转5

25、；5.以akr为主元,作矩阵行变换使其变为1,该列其他元变为0（旋转变换）,转2。,例2.10 求线性规划,解：引入松弛变量 将上述问题转化为,得对偶单纯形表2.7,表2.7,此时基本解为X=(0,0,0,0,-2,-3),不可行，转第二步。因为min-2,-3=-3,所以x6为换出变量，又因为Min-2/-2,-5/-1=1,所以x1为换入变量。得到新的单纯形表2.8,表2.8,此时基本解为X=(3/2,0,0,0,-1/2,0),不可行，转第二步。因为-1/20,所以x5为换出变量，又因为Min-4/(-5/2),-4/(-5/2),-9/(-5/2),-1/(-1/2)=8/5,所以 x

26、2 和 x3 都可以作为换入变量。任选其中一个 x2，做线性变换得到新的单纯形表2.9,表2.9,得到一个基本解为X=(8/5,1/5,0,0,0,0)T,因解是可行的，所以满足最优检验下的基本可行解因而也是最优解。,Chapter 2,从以上求解过程中我们可以看到，对偶单纯形法有以下的优点：1)初始解可以是非可行解，当检验数都为负数时，就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。2)当变量多于约束条件，对于这样的线性规划问题，用对偶单纯形法计算可以减少计算工作量，因此对于变量较少，而约束条件很多的线性规划问题，可以首先将它变换成为对偶问题，然后用对偶单纯形法来求解。,3)在

27、灵敏度分析中，有时需要使用对偶单纯形法，这样可以使问题处理简化。对偶单纯形法的局限在于：对于大多数的线性规划问题，很难找到一个初始可行基，因而这个方法在求解线性规划问题时很少单独应用。,从几何图形上看单纯性和对偶单纯性的区别已知Q2为最优解点,B,C,单纯形法：O Q1 O2 或 O Q4 O3 O2 对偶单纯性法：A B Q2 或 B Q2 注意：对偶单纯形对迭代点的要求-对偶可行性,（1）用对偶单纯形法求解线性规划是一种求解方法，而不是去求对偶问题的最优解；,（2）初始表中一定要满足对偶问题可行，也就是说检验数满足最优判别准则；,（3）对偶单纯形法与普通单纯形法的换基顺序不一样，普通单纯形

28、法是先确定进基变量后确定出基变量，对偶单纯形法是先确定出基变量后确定进基变量；,（4）对偶单纯形法在确定出基变量时，若不遵循 规则，任选一个小于零的bi对应的基变量出基，不影响计算结果，只是迭代次数可能不一样,应当注意：,2.7 灵敏度分析,系数 br、cj 变化，最优解的最优性、可行性是否变化？,系数在什么范围内变化，最优解或最优性不变？,如何求新的最优解？,例2.2,1.求解此线性规划的解2.当C2=2时，新的线性规划问题的解3.当C2=5时，新的线性规划问题的解4.当 b1=9时，新的线性规划问题的解5.当 b1=12时，新的线性规划问题的解,灵敏度分(Sensitivity Analy

29、isi),就是分析研究LP 模型参数 aij,br,cj 的取值变化对最优解和最优基的影响。它在应用线性规划解决实际问题的过程中是非常有用的。,实际LP问题的最优解，是在模型参数区某一组定值的基础上获得的，而这些定值往往是一些预测和估计的数字，因此或者有一定的误差，或者可能变动。如市场条件出现了变动，cj 的值就会发生变化；aij是随着工艺技术条件的改变而改变的，而 br 值则是根据资源投入后能产出多大经济效果来决定的一种决策选择。,因此就会产生以下问题：当这些参数中的一个或几个发生了变化时，问题的最优解会有什么变化，或者这些参数在一个多大的范围内变化时，问题的最优解不变。这就是我们学习灵敏度

30、分析所要研究解决的问题。当然通过上面的学习我们知道：当线性规划问题中的一个或者几个参数变化时，可以用单纯形法从头计算，看最优解有无变化，但是这样做既麻烦又没有必要。,因为我们知道单纯形法的迭代运算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，因此有可能把个别参数的变化直接在计算得到最优解的单纯形表上面反映出来，这样就不需要从头计算了，而直接对计算得到的最优解的单纯形表进行审查，看一些数字变化后，是否满足最优解的条件，如果不满足的话，再从这个表开始进行迭代计算，求出最优解。,Chapter 2 灵敏度分析,灵敏度分析的步骤可以归纳如下：1)将参数的改变计算反

31、映到最终单纯形表上来;具体的计算方法是，按照相关公式计算出由参数的变化而引起的最终单纯形表上有关数字的变化；2)检查原问题是否仍为可行解;3)检查对偶问题是否仍为可行解;4)我们可以按照书中表中罗列的几种情况得出结论和决定继续计算的步骤,Chapter 2 灵敏度分析,2.7.1 资源数量br发生变化的分析资源数量变化是指系数br发生了变化，br变化为 br=br+br，并假设规划问题的其它系数都没有发生变化。根据讨论，最优解的基变量 xB=B-1b.这样使得最终表中原问题的解相应的变化为XB=B-1（b+b）其中，b=（0，,br,0,0）T,1、资源系数br的灵敏度变化分析,根据讨论，只要

32、保持 B-1(b+b)0，最终表中检验数不变，则最优基不变，但最优解的值变化，XB=B-1(b+b)为新的最优解；否则，需要利用对偶单纯形法继续计算。,为了使最优基 B 不变，求 br 的变化范围。,B-1的第r列,这个时候在最终表里面求得的 b 列的所有元素 i=1,2,，m。由此可得 由此可得，最优基不变（检验数不变）的条件是,例题:,问题：某公司在计划期内要安排生产I、II两种产品，已知生产单位产品所需的设备台时及A B两种原材料的消耗如表所示，该工厂每生产一件产品I可获利2元，每生产一件产品II可获利3元，问应该如何安排计划使该工厂获利最多？,Chapter 2 灵敏度分析,Chapt

33、er 2 灵敏度分析,最终单纯形表为:若该厂又从别处抽出 4 台时用于生产 I、II，求这时该厂生产产品 I,II 的最优方案。,这里 各列分别对应 b1、b2、b3 的单一变化下面给出最优基不变时，b1 的变化范围,B=（x1 x5 x2),可得b1-2/0.5=-4,b1-4/-2=2由公式知b1变化范围-4,2,显然 b1变化范围4,10因此，当 b1=4 时，最优基发生变化，需要用对偶单纯形法继续求解,解：先计算B-1b,将这个结果放到最终表中得,表中b列中有负数，故可用对偶单纯形法求最优解。最优解见下表,即该厂最优生产方案应改为生产产品 I为 4 件，生产产品 II 为 3 件，获利

34、17元。从最优表中看出 x3=2,即设备有2小时未被利用。,2.7.2 价值系数 cj 的变化分析当目标系数 cj 变化时，可能引起检验数的变化，从而影响最优性条件是否满足。为了方便起见，分别就对应的是非基变量与基变量两中情况来讨论最优解不变的条件。,（1）当 cj 是非基底变量 xj 的系数，检验数为,或,当 cj 变化 cj 后，检验数要小于或等于零，即,只要 j 0,即 cj-j，则最优解不变；否则，将最优单纯形表中的检验数 j 用 j 取代，继续单纯形法的表格计算。,Chapter 2 灵敏度分析,例题:Max z=-2x1-3x2-4x3 S.t.-x1-2x2-x3+x4=-3-2

35、x1+x2-3x3+x5=-4 x1,x2,x3,x4,x5 0,Chapter 2 灵敏度分析,最优单纯形表:,从表中可得到c3 9/5 时，原最优解不变。同理，c4 8/5，c5 1/5时，原最优解不变。,Chapter 2 灵敏度分析,若 cs 是基变量的系数：因csCB,所以每个检验数j 中含有c s,当 cs 变化为 c scs 后,j 同时变化，那么 j=cj-ci aij(c scs)asj=j-cs asj,is那么对所有非基变量，只要对所有非基变量 j 0，即 j cs asj，则最优解 不变；否则，将最优单纯形表中的检验数 j 用 j取代，继续单纯形法的表格计算。,最优解不

36、变：cs的变化范围,j 0，即 j cs asj，j 为非基变量下标，则最优解不变；否则，将最优单纯形表中的检验数 j 用 j取代，继续单纯形法的表格计算。,Max z=2x1+3x2+0 x3+0 x4+0 x5 s.t.x1+2x2+x3=8 4x1+x4=16 4x2+x5=12 x1,x2,x3,x4,x5 0,下表为最优单纯形表,考虑基变量系数 c2 发生变化,例题:仍以第一章例1的最终表为例。设基变量x2的系数 c2变化 c2，在原最优解不变的条件下，确定 c2 的变化范围。,Chapter 2 灵敏度分析,从表中可得到-3c21时，原最优解不变。即 x2 的价值系数 c2 可在0

37、,4之间变化，不影响原最优解。,总 结,1、掌握写出线性规划对偶问题的方法，注意原问题与其对偶问题的对应关系(以对称形式为参照)2、掌握对偶问题的基本理论和性质(尤其是互补松弛性质的应用)3、理解影子价格的定义(对偶规划的最优解)和意义4、理解并掌握对偶单纯形方法的思想和步骤（对初始基本解的要求（对偶可行）,5、掌握线性规划灵敏度分析(1)资源数量 bi 发生变化的分析 最优基不变：bi 的变化范围(2)目标函数中价值系数 cj 发生变化的分析 最优解不变：cj 的变化范围(注意基变量和非基变量价值系数的不同),作业：2.1（1），（2）（3）2.22.32.6（1）2.92.10,精品课件！,精品课件！,Shanghai University of Engineering Science,Thank You!,