第二讲对偶理论与灵敏度分析精选PPT.ppt

《第二讲对偶理论与灵敏度分析精选PPT.ppt》由会员分享，可在线阅读，更多相关《第二讲对偶理论与灵敏度分析精选PPT.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二讲对偶理论与灵敏度分析第1页，本讲稿共66页【例1】某企业用四种资源生产三种产品，工艺系数、资源限量及价值系数如下表：建立总收益最大的数学模型。产品资源ABC资源限量986500547450832300764550单件产品利润1008070线性规划的对偶模型DualmodelofLP线性规划的对偶模型第2页，本讲稿共66页【解】设【解】设x1，x2，x3分别为产品分别为产品A，B，C的产量，则线性的产量，则线性规划数学模型为：规划数学模型为：现现在在从从另另一一个个角角度度来来考考虑虑企企业业的的决决策策问问题题。假假如如企企业业不不考考虑虑自自己生产产品，而己生产产品，而将现有的资源标价

2、出售将现有的资源标价出售，问题：决策者应怎样给定资源一个合理的价格？问题：决策者应怎样给定资源一个合理的价格？线性规划的对偶模型DualmodelofLP第3页，本讲稿共66页设y1，y2，y3及y4分别表示四种资源的单位增值价格(售价成本增值)，总增值最低可用min w=500y1+450y2+300y3+550y4表表示示。企企业业生生产产一一件件产产品品A用用了了四四种种资资源源的的数数量量分分别别是是9，5，8和和7个个单单位位，利利润润是是100,企企业业出出售售这这些些数数量量的的资资源源所所得得的利润不能少于的利润不能少于100，即，即同理，对产品同理，对产品B 和和C 有有线性

3、规划的对偶模型DualmodelofLP第4页，本讲稿共66页称称上上述述线线性性规规划划模模型型是是前前面面生生产产计计划划模模型型的的对对偶偶线线性性规规划划模模型型,这这一一问问题题称称为为对对偶偶问问题题。生生产产计计划划的的线线性性规规划划问问题题称称为为原原始始线线性性规划问题或规划问题或原问题原问题。价价格格不不可可能能小小于于零零，即即有有yi0(i=1,4),从从而而企企业业的的资资源源价价格模型为格模型为线性规划的对偶模型DualmodelofLP第5页，本讲稿共66页注：注：以上两问题是同一组数据以上两问题是同一组数据参数，只是位置有所不同，所参数，只是位置有所不同，所描

4、述的问题实际上是从两个不描述的问题实际上是从两个不同的角度去描述。原始线性规同的角度去描述。原始线性规划问题考虑的是充分利用现有划问题考虑的是充分利用现有资源，以产品数量和单位产品资源，以产品数量和单位产品的利润来决定企业的总利润，的利润来决定企业的总利润，没有考虑资源的价格，实际上没有考虑资源的价格，实际上在构成产品的利润中，不同的在构成产品的利润中，不同的资源对利润的贡献也不同，它资源对利润的贡献也不同，它是企业生产过程中一种隐含的是企业生产过程中一种隐含的潜在价值，经济学中称为潜在价值，经济学中称为影子价影子价格格。线性规划的对偶模型DualmodelofLP第6页，本讲稿共66页第7页

5、，本讲稿共66页线性规划问题线性规划问题(2.2)就是原线性规划问题就是原线性规划问题(2.1)的对偶线性规划问的对偶线性规划问题，反之，题，反之，(2.2)的对偶问题就是的对偶问题就是(2.1)原问题与对偶问题有如下原问题与对偶问题有如下关系关系(假设原问题假设原问题(2.1)：(1)原问题的约束个数(不含非负约束)等于对偶变量的个数(2)原问题的目标函数系数对应于对偶问题的右端项(3)原问题的右端项对应于对偶问题的目标函数系数(4)原问题的约束矩阵转置就是对偶问题系数矩阵(5)原问题求最大，对偶问题是求最小(6)原问题不等式约束符号为原问题不等式约束符号为“”,对偶问题不等式约束符号为对偶

6、问题不等式约束符号为“”线性规划的对偶模型DualmodelofLP第8页，本讲稿共66页【例2】写出该线性规划的对偶问题【解】【解】线性规划的对偶模型DualmodelofLP第9页，本讲稿共66页线性规划问题的规范形式(或叫对称形式)：定义：定义：目标函数求目标函数求极大值极大值时，所有约束条件时，所有约束条件为为号号，变量非负变量非负；目标函数求目标函数求极小值极小值时，所有约束条件时，所有约束条件为为号，变量非负号，变量非负。注：注：(1)(1)线性规划规范形式与标准型是两种不同形式，但线性规划规范形式与标准型是两种不同形式，但可以相互转换。可以相互转换。(2)规范形式的线性规划问题的

7、对偶仍然是规范形式规范形式的线性规划问题的对偶仍然是规范形式线性规划的对偶模型DualmodelofLP第10页，本讲稿共66页对于一般的线性规划问题：其中为矩阵，为维列向量，为维向量，为维列向量(i=1,2,3;j=1,2)且令，此问题可化为线性规划的对偶模型DualmodelofLP第11页，本讲稿共66页用分别表示以上四组约束的对偶问题，则原问题的对偶问题是第12页，本讲稿共66页令，整理得对偶问题为将原问题与对偶问题的对将原问题与对偶问题的对应关系列于表应关系列于表2。第13页，本讲稿共66页原问题(或对偶问题)对偶问题(或原问题)目标函数max目标函数系数(资源限量)约束条件系数矩阵

8、A(AT)目标函数min资源限量(目标函数系数)约束条件系数矩阵AT(A)变量n个变量第j个变量0第j个变量0第j个变量无约束约束n个约束第j个约束为第j个约束为第j个约束为=约束m个约束第i个约束第i个约束第i个约束为=变量m个变量第i个变量0第i个变量0第i个变量无约束表2线性规划的对偶模型DualmodelofLP第14页，本讲稿共66页【例3】写出下列线性规划的对偶问题【解】【解】=y10，y20，y3无约束线性规划的对偶模型DualmodelofLP第15页，本讲稿共66页对偶问题是(记为DP)：这里这里A是是mn矩阵矩阵,X是是n1列向量列向量,Y是是1m行向量。行向量。【性质性质

9、1】对称性对称性:对偶问题的对偶是原问题。对偶问题的对偶是原问题。设原问题是(记为LP)：对偶性质Dualproperty对偶性质【性质性质2】弱对偶性弱对偶性:设设X*、Y*分别为分别为LP(max)与与DP(min)的可行解，则的可行解，则 第16页，本讲稿共66页对偶性质Dualproperty由这个性质可得到下面几个由这个性质可得到下面几个结论结论：(1)(LP)的任一可行解的目标值是的任一可行解的目标值是(DP)的最优值下的最优值下(2)界；界；(DP)的任一可行解的目标是的任一可行解的目标是(LP)的最优值的上界；的最优值的上界；(2)在在互互为为对对偶偶的的两两个个问问题题中中，

10、若若一一个个问问题题可可行行且且具具有无界解，则另一个问题无可行解；有无界解，则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具若原问题可行且另一个问题不可行，则原问题具有无界解。有无界解。注注意意:上上述述结结论论(2)及及(3)的的条条件件不不能能少少。一一个个问问题题无无可可行行解解时时，另另一一个个问问题题可可能能有有可可行行解解(此此时时具具有有无无界界解解)也也可可能能无可行解。无可行解。第17页，本讲稿共66页例如：无可行解，而对偶问题有可行解，由结论有可行解，由结论(3)知必有无界解。知必有无界解。对偶性质Dualproperty第18页，本讲稿共66页【性

11、质3】最优准则定理:设X*与Y*分别是(LP)与(DP)的可行解，则X*、Y*是(LP)与(DP)的最优解当且仅当C X*=Y*b.对偶性质Dualproperty【性性质质4】对对偶偶性性：若若互互为为对对偶偶的的两两个个问问题题其其中中一一个个有有最最优优解，则另一个也有最优解，且最优值相同。解，则另一个也有最优解，且最优值相同。另另一一结结论论：若若(LP)与与(DP)都都有有可可行行解解，则则两两者者都都有有最最优优解解，若一个问题无最优解，则另一问题也无最优解。若一个问题无最优解，则另一问题也无最优解。【性质5】互补松弛定理:设X*、Y*分别为(LP)与(DP)的可行解，XS和YS分

12、别是它们的松弛变量的可行解，则X*和Y*是最优解当且仅当YSX*=0和Y*XS=0第19页，本讲稿共66页性质5告诉我们已知一个问题的最优解时求另一个问题的最优解的方法，即已知Y*求X*或已知X*求Y*。Y*XS=0和YS X*=0两式称为两式称为互补松弛条件互补松弛条件。将互补松弛条件写成下式。将互补松弛条件写成下式由由于于变变量量都都非非负负，要要使使求求和和式式等等于于零零，则则必必定定每每一一分分量量为为零零，因而有下列关系：因而有下列关系：对偶性质Dualproperty第20页，本讲稿共66页(1)当yi*0时，,反之当,时yi*=0；利利用用上上述述关关系系，建建立立对对偶偶问问

13、题题(或或原原问问题题)的的约约束束线线性性方方程程组组，方程组的解即为最优解。方程组的解即为最优解。【例4】已知线性规划的最优解是,求对偶问题的最优解。对偶性质Dualproperty第21页，本讲稿共66页【解】对偶问题是因因为为x10，x20，所所以以对对偶偶问问题题的的第第一一、二二个个约约束束的的松松弛变量等于零，即弛变量等于零，即解解此此线线性性方方程程组组得得y1=1,y2=1,从从而而对对偶偶问问题题的的最最优优解解为为Y=(1，1)，最优值，最优值w=26。对偶性质Dualproperty第22页，本讲稿共66页【例5】已知线性规划的对偶问题的最优解为Y=(0，2)，求原问题

14、的最优解。【解】对偶问题是【解】对偶问题是对偶性质Dualproperty第23页，本讲稿共66页解方程组得：解方程组得：x1=5,x3=1,所以原问题的最优解为所以原问题的最优解为X=(5，0，1)T，最优值，最优值Z=12。因为因为y20，所以原问题第二个松弛变量，所以原问题第二个松弛变量=0，由，由y1=0、y2=2知，松弛变量知，松弛变量故故x2=0，则原问题的约束条件为线性方程组：则原问题的约束条件为线性方程组：对偶性质Dualproperty第24页，本讲稿共66页【例6】证明该线性规划无最优解：【证】容易看出【证】容易看出X=(4，0，0)是一可行解。对偶问题是一可行解。对偶问题

15、将三个约束的两端分别相加得将三个约束的两端分别相加得,而第二个约束有而第二个约束有y21,矛盾，故对偶问题无可行解，因而原问题具有矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。无界解，即无最优解。对偶性质Dualproperty第25页，本讲稿共66页【性质6】LP(max)的检验数的相反数对应于DP(min)的一组基本解，其中第j个决策变量xj的检验数的相反数对应于(DP)中第j个松弛变量的解，第i个松弛变量的检验数的相反数对应于第i个对偶变量yi的解。反之，(DP)的检验数(注意：不乘负号)对应于(LP)的一组基本解。对偶性质Dualproperty注：注：应用性质应用性质6

16、 6 的前提是线性规划为规范形式，而性质的前提是线性规划为规范形式，而性质1-51-5则对所有形式线性规划有效。则对所有形式线性规划有效。第26页，本讲稿共66页根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：一个问题max另一个问题min有最优解有最优解性质4无无最优解无最优解性质4最优无界解(有可行解)无可行解性质2解无可行解无界解(有可行解)应用已知最优解通过解方程求最优解性质5已知检验数检验数乘以1求得基本解性质6对偶性质Dualproperty第27页，本讲稿共66页影子价格影子价格因为原问题和对偶问题的最优值相等，将线性规划的目标因为原问题和对偶问题的最优值相等，将线性规划

17、的目标函数表达成资源的函数，故有函数表达成资源的函数，故有即即yi是第是第i 种资源的变化率，说明当其它资源供应量种资源的变化率，说明当其它资源供应量bk(ki)不变时，不变时，bi增加一个单位时目标值增加一个单位时目标值Z 增加增加yi个单位个单位对偶性质Dualproperty第28页，本讲稿共66页正确理解影子价格，利用影子价格作下列经济活动分析正确理解影子价格，利用影子价格作下列经济活动分析:(1)调节生产规模例如，目标函数调节生产规模例如，目标函数Z表示利润表示利润(或产值或产值)(2)当第当第i 种资源的影子价格大于零种资源的影子价格大于零(或高于市场价格或高于市场价格)时，表时，

18、表(3)示有利可图，企业应购进该资源扩大生产规模，当影子示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零价格等于零(或低于市场价格或低于市场价格)，企业不能增加收益，这，企业不能增加收益，这(1)时应将资源卖掉或出让，缩小生产规模。时应将资源卖掉或出让，缩小生产规模。(2)生产要素对产出贡献的分解通过影子价格分析每生产要素对产出贡献的分解通过影子价格分析每(3)种资源获得多少产出例如，企业获得种资源获得多少产出例如，企业获得100万元的利润，万元的利润，(4)生产过程中产品的直接消耗的资源有材料生产过程中产品的直接消耗的资源有材料A、材料、材料B、设备和工时，这些资源各产生多少利润，

19、由影子价格可设备和工时，这些资源各产生多少利润，由影子价格可以大致估计出来。以大致估计出来。对偶性质Dualproperty第29页，本讲稿共66页(3)由性质2.5知，第i个松弛变量大于零时第i个对偶变(4)量等于零，并不能说明该资源在生产过程中没有作出(5)贡献，只能理解为第i种资源有剩余时再增加该资源量(6)不能给企业带来利润或产值的增加(4)影子价格是企业生产过程中资源的一种隐含的潜在价影子价格是企业生产过程中资源的一种隐含的潜在价(5)值，表明单位资源的贡献，与市场价格是不同的两个概值，表明单位资源的贡献，与市场价格是不同的两个概(6)念同一种资源在不同的企业、生产不同的产品或在不念

20、同一种资源在不同的企业、生产不同的产品或在不(7)同时期影子价格都不一样同时期影子价格都不一样例如，某种钢板市场价格是例如，某种钢板市场价格是(8)每吨每吨8000元，一个企业用来生产汽车，另一个企业用来元，一个企业用来生产汽车，另一个企业用来(9)生产空调外壳，每吨钢板的产值是不一样的生产空调外壳，每吨钢板的产值是不一样的对偶性质Dualproperty第30页，本讲稿共66页(5)影子价格是一个变量由的含义知影子(6)价格是一种边际产出，与bi的基数有关，在最优基B(7)不变的条件下yi不变，当某种资源增加或减少后，最(8)优基B可能发生了变化，这时yi的值也随之发生变化对偶性质Dualp

21、roperty第31页，本讲稿共66页对偶单纯形法对于任何一个可行基B,为原问题的一个基可行解，单纯形法是从一个基可行解到另一个相邻的基可行解，直到基B满足 为止。对偶单纯形法DualSimplexMethod单纯形法首先化问题为标准型：第32页，本讲稿共66页对偶单纯形法DualSimplexMethod原始单纯形法的思想：从满足可行性条件的一个基可行解(即基B满足)出发，经过换基运算迭代到另一个基可行解，直到找到满足最优性条件()的基可行解，这就是原问题的最优解。CBB1bC-CBB1AB-1bB-1A XBbX对于任意基B ,对应的单纯形表为第33页，本讲稿共66页若上表为最优单纯形表，

22、则下列两个式子同时成立：对偶单纯形法DualSimplexMethod问题：可否从满足条件问题：可否从满足条件(2)的基出发去找原问题的最优解？的基出发去找原问题的最优解？对偶单纯形法思想对偶单纯形法思想：从满足条件从满足条件(2)的基的基(一般称为一般称为正则基正则基)B出发，经过换出发，经过换基运算到另一个正则基，即一直保证条件基运算到另一个正则基，即一直保证条件(2)成立，直成立，直到找到一个满足条件到找到一个满足条件(1)的正则基。的正则基。CBB1bC-CBB1AB-1bB-1A XBX第34页，本讲稿共66页对偶单纯形法的计算步骤：(1)将将线线性性规规划划的的约约束束化化为为等等

23、式式，找找出出一一个个正正则则基基，即即全全部部检检验验数数j0（max）或或j0（min）,求求出出其其对对应应的的基基本本解解，当当基基本本解解可可行行时时，则则达达到到最最优优解解；若若基基本本解解不不可可行行，即即有有某某个个基基变变量量的解的解bi0，则进行换基计算；则进行换基计算；(2)换基计算换基计算(i)先确定出基变量:l 行对应的变量出基；(ii)再选再选进基变量进基变量:求最小比值求最小比值(3)求求新新的的基基本本解解，用用初初等等变变换换将将主主元元素素alk化化为为l,k列列其其它它元元素素化化为零，得到新的基本解，转到第为零，得到新的基本解，转到第(1)步重复运算。

24、步重复运算。对偶单纯形法DualSimplexMethod第35页，本讲稿共66页【例7】用对偶单纯形法求解【解】先将约束不等式化为等式，再两边同乘以【解】先将约束不等式化为等式，再两边同乘以(1)，得到，得到x4、x5为基变量，用对偶单纯形法，迭代过程如表为基变量，用对偶单纯形法，迭代过程如表2-7所示。所示。对偶单纯形法DualSimplexMethod第36页，本讲稿共66页XBx1x2x3x4x5b表(1)x4x5-1-1-11-14100153j41300表2-7对偶单纯形法DualSimplexMethod最优解：最优解：X(4，1，0)T；Z=17表(2)x2x51-21013-

25、110158j30210表(3)x2x101105/2-3/2-1/2-1/21/21/214j0013/25/23/2第37页，本讲稿共66页线性规划的灵敏度分析也称为敏感性分析，它是研究和分析数据(cj，bi，aij)的波动对最优解的影响程度，主要研究下面两个方面：(1)当当模模型型中中这这些些数数据据有有一一个个或或几几个个发发生生变变化化时时，最最优优解解有有什什么么变变化化，或或这这些些数数据据在在什什么么范范围围内内变变化化时时，原原最最优优解或最优基不变；解或最优基不变；(2)若若最最优优解解或或最最优优基基发发生生变变化化后后，如如何何求求出出新新的的最最优优基基或最优解。或最

26、优解。灵敏度分析灵敏度分析SensitivityAnalysis第38页，本讲稿共66页设线性规划其中其中Amn，线性规划有最优解，设基，线性规划有最优解，设基B为最优基，则有为最优基，则有灵敏度分析SensitivityAnalysis求解思路：求解思路：将变化后的数据代入上述公式，看看可行性条件将变化后的数据代入上述公式，看看可行性条件与最优性条件是否依然成立：若成立，则还是最优解；若不与最优性条件是否依然成立：若成立，则还是最优解；若不成立，则利用单纯形法或对偶单纯形法可求出变化后的最优成立，则利用单纯形法或对偶单纯形法可求出变化后的最优解。解。第39页，本讲稿共66页价值系数cj 的变

27、化分析为使最优解不变，求为使最优解不变，求cj 的变化范围的变化范围灵敏度分析SensitivityAnalysis由最优性条件可知，当目标函数系数发生变化时，有可能引起检验数的变化，从而影响最优性条件是否满足？要使最优解不变，即当cj 变化为后，检验数仍然是小于等于零，即这时分这时分cj是非基变量和基变量的系数两种情况讨论。是非基变量和基变量的系数两种情况讨论。第40页，本讲稿共66页(1)cj 是非基变量xj 的系数即cj的增量不超过cj的检验数的相反数时，最优解不变，否则最优解就要改变。所以(2)ci是基变量是基变量xi的系数的系数 因因ciCB，故每个检验数，故每个检验数j 中含有中含

28、有 ,当当c i变化为变化为c ici后后j 同时变化，这时同时变化，这时灵敏度分析SensitivityAnalysis第41页，本讲稿共66页令要使得所有，则有灵敏度分析SensitivityAnalysis第42页，本讲稿共66页要使得所有，则有只要求出上限只要求出上限2及下限及下限1就可以求出就可以求出ci的变化区间的变化区间灵敏度分析SensitivityAnalysis第43页，本讲稿共66页资源限量bi 变化分析为了使最优基B不变，求bi的变化范围。设设br的增量为的增量为br ,b 的增量为的增量为原原性性规规划划的的最最优优解解为为X，基基变变量量为为XB=B1b，要要使使最

29、最优优基基B不不变变，即要求即要求而灵敏度分析SensitivityAnalysis第44页，本讲稿共66页因为灵敏度分析SensitivityAnalysis第45页，本讲稿共66页所以令灵敏度分析SensitivityAnalysis第46页，本讲稿共66页因而要使得所有必须满足这个公式与求的上、下限的公式类似，比值的分子都小于等于零，分母是B1中第r列的元素，大于等于比值小于零的最大值，小于等于比值大于零的最小值。当某个时，可能无上界或无下界。灵敏度分析SensitivityAnalysis第47页，本讲稿共66页约束系数的灵敏度分析1、非基变量 的系数列向量 发生变化则改变后只影响 的

30、检验数，而对其他的检验数没有影响由于 是对偶可行解，要使最优基B不变，则必须有灵敏度分析SensitivityAnalysis第48页，本讲稿共66页当中只有第i 个分量发生变化灵敏度分析SensitivityAnalysis第49页，本讲稿共66页2、基变量 的系数列向量 发生变化当最优基B的列向量发生变化时，也发生变化，从单纯形表可知，几乎所有位置都受到影响，故很难给出变化范围的一般公式，在实际问题中往往重新计算。3 3、增加新的决策变量增加新的决策变量假设增加一个新变量 ，其对应的目标函数系数为 ，在约束函数中对应的列向量 ，在最优单纯形表中增加一列 相应的检验数为 若 ，则原问题最优解

31、不变 若 ，则以 为新的进基变量，可用单纯形法继续迭代。灵敏度分析SensitivityAnalysis第50页，本讲稿共66页4 4、增加新的约束条件增加新的约束条件(i)若在原问题中增加一个新的不等式约束条件若在原问题中增加一个新的不等式约束条件先将原问题的最优解代入新的约束条件中，若满足，则原最优解先将原问题的最优解代入新的约束条件中，若满足，则原最优解是新问题的最优解，否则需将新约束加入原问题，具体做法：是新问题的最优解，否则需将新约束加入原问题，具体做法：(1)引入松弛变量，新约束成为(2)在单纯形表中增加一行一列，并以为基变量，下面的系数为，注意在单纯形表中的列向量是单位向量，而原

32、来的m个基变量对应的列向量可能不是单位向量，故应先做初等变换，然后继续迭代求解。灵敏度分析SensitivityAnalysis第51页，本讲稿共66页(ii)若在原问题中增加一个新的等式约束条件先将原问题的最优解代入新的约束条件中，若满足，则原最先将原问题的最优解代入新的约束条件中，若满足，则原最优解不变，否则在新约束引入人工变量，再用大优解不变，否则在新约束引入人工变量，再用大M法求解新法求解新问题。问题。灵敏度分析SensitivityAnalysis第52页，本讲稿共66页注：由以上讨论可知，当某些参数变化时，并不一定要用单纯形法重新计算，而可从原最优单纯形表出发，做适当修改，再根据具

33、体情况求得新最优解，其步骤如下：(1)修改原最优单纯形表，以反映参数的变化。修改原最优单纯形表，以反映参数的变化。(2)检验以上修改是否使最优解发生变化，即以下式子是否成立：检验以上修改是否使最优解发生变化，即以下式子是否成立：(3)若满足可行性而不满足最优性，则用单纯形法求解；若满足可行性而不满足最优性，则用单纯形法求解；若满足最优性而不满足可行性，则用对偶单纯形法求解。若满足最优性而不满足可行性，则用对偶单纯形法求解。(4)若可行性与最优性都不满足，则引入人工变量后重新求解；若可行性与最优性都不满足，则引入人工变量后重新求解；若最优性与可行性都满足，则最优基不变。若最优性与可行性都满足，则

34、最优基不变。灵敏度分析SensitivityAnalysis第53页，本讲稿共66页【例8】考虑下列线性规划求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。综合应用灵敏度分析SensitivityAnalysis第54页，本讲稿共66页(2)改变目标函数x3的系数为c3=1;(3)改变x2的系数为(4)改变约束(1)为(5)增加新约束(1)改变右端常数为:第55页，本讲稿共66页【解】加入松弛变量【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如，用单纯形法计算，最优表如210所示。所示。表表210Cj2-14000bCBXBx1x2x3x4x5x64x305/7

35、11/73/7022x112/701/74/7010 x60200111j031/702/720/70最优解最优解X=(1，0，2，0，0，1)T，最优值，最优值Z=10灵敏度分析SensitivityAnalysis第56页，本讲稿共66页最优基矩阵及其逆最优基矩阵及其逆(1)基变量的解为基变量的解为基基本本解解不不可可行行，将将求求得得的的XB代代替替表表210中中的的常常数数项项，用用对对偶偶单纯形法求解，其结果见表单纯形法求解，其结果见表211所示。所示。灵敏度分析SensitivityAnalysis第57页，本讲稿共66页表表211Cj214000bCBXBx1x2x3x4x5x6

36、4x305/711/73/7022/72x112/701/74/706/70 x60200112j031/702/720/704x30011/71/145/1417/72x11001/73/71/74/71x201001/21/21j0002/79/1431/14灵敏度分析SensitivityAnalysis第58页，本讲稿共66页最优解(2)由表由表210容易得到基变量容易得到基变量x3的系数的系数c3的增量变化范围是的增量变化范围是而而c3=1不不在在允允许许的的变变化化范范围围之之外外，故故表表210的的解解不不是是最最优优解解。非基变量的检验数非基变量的检验数x4进基，用单纯形法计算

37、，得到表进基，用单纯形法计算，得到表212灵敏度分析SensitivityAnalysis第59页，本讲稿共66页表212XBx1x2x3x4x5x6bx305/711/73/702x112/701/74/701x60200111j016/701/711/70 x405713014x11110103x60200111j031020最优解为X=(3，0，0，14，0，1)T，最优值Z=6。灵敏度分析SensitivityAnalysis第60页，本讲稿共66页(3)这时目标函数的系数和约束条件的系数都变化了，同样求出这时目标函数的系数和约束条件的系数都变化了，同样求出2判别最优解是否改变。判别最

38、优解是否改变。x2进基，计算结果如表进基，计算结果如表213所示所示灵敏度分析SensitivityAnalysis第61页，本讲稿共66页表213Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11101/74/7010 x60300111j0502/720/704x30011/73/7022x11001/75/211/34/33x201001/31/31/3j0002/725/215/3最优解灵敏度分析SensitivityAnalysis第62页，本讲稿共66页(4)第第一一个个约约束束变变为为实实际际上上是是改改变变了了a12及及b1，这时要求，这时要

39、求2及及XB，判断解的情况，判断解的情况,因为可行，所以最优解为灵敏度分析SensitivityAnalysis第63页，本讲稿共66页。应当注意，当且时用单纯形法继续迭代，当且不可行时用对偶单纯形法继续迭代，当且不可行时，需加入人工变量另找可行基.(5)引入松弛变量引入松弛变量x7得得 x1、x3是基变量，利用表是基变量，利用表27消去消去x1、x3，得，得x7为为新新的的基基变变量量，基基本本解解X=(1，0，2，0，0，1，2)T 不不可可行行，将上式加入表将上式加入表210中用对偶单纯形法迭代得到表中用对偶单纯形法迭代得到表2-14。灵敏度分析SensitivityAnalysis第6

40、4页，本讲稿共66页XBx1x2x3x4x5x6x7bx305/711/73/7002x112/701/74/7001x602001101x7013/7011/72/7012j031/702/720/700 x306/11105/1101/1120/11x115/11006/1101/1113/11x602001101x4013/11012/1107/1114/11j045/110032/1102/11表214最优解灵敏度分析SensitivityAnalysis第65页，本讲稿共66页表2-15参数或条件变化最优表可能发生变化可行与最优方 法基变量系数ci所有非基变量的检验数可行若非最优，用普通单纯形法非基变量系数cj只有xj的检验数变化可行若非最优，用普通单纯形法biXB对偶问题可行若不可行，用对偶单纯形法基变量系数aij基、基变量、检验数等视检验数和基本解来确定非基变量系数aij非基变量系数及xj的检验可行若非最优，用普通单纯形法综合变化，参数、增减变量与约束等用1.5介绍的5个计算公式判断变化情况若原问题与对偶问题都不可行，用人工变量法灵敏度分析SensitivityAnalysis第66页，本讲稿共66页