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

第二讲对偶理论与灵敏度分析本讲稿第一页，共六十六页【例【例1】某企业用四种资源生产三种产品，工艺系数、某企业用四种资源生产三种产品，工艺系数、资源资源限量及价值系数如下表：限量及价值系数如下表：建立总收益最大的数学模型。建立总收益最大的数学模型。产品资源ABC资源限量986500547450832300764550单件产品利润1008070线性规划的对偶模型线性规划的对偶模型DualmodelofLP线性规划的对偶模型线性规划的对偶模型本讲稿第二页，共六十六页【解】设【解】设x1，x2，x3分别为产品分别为产品A，B，C的产量，则线性的产量，则线性规划数学模型为：规划数学模型为：现现在在从从另另一一个个角角度度来来考考虑虑企企业业的的决决策策问问题题。假假如如企企业业不不考考虑自己生产产品，而虑自己生产产品，而将现有的资源标价出售将现有的资源标价出售，问题：决策者应怎样给定资源一个合理的价格？问题：决策者应怎样给定资源一个合理的价格？线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第三页，共六十六页设设y1，y2，y3及及y4分别表示四种资源的单位增值价格分别表示四种资源的单位增值价格(售价成本增值售价成本增值)，总增值最低可用，总增值最低可用min w=500y1+450y2+300y3+550y4表表示示。企企业业生生产产一一件件产产品品A用用了了四四种种资资源源的的数数量量分分别别是是9，5，8和和7个个单单位位，利利润润是是100,企企业业出出售售这这些些数数量量的的资资源源所所得得的的利润不能少于利润不能少于100，即，即同理，对产品同理，对产品B 和和C 有有线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第四页，共六十六页称称上上述述线线性性规规划划模模型型是是前前面面生生产产计计划划模模型型的的对对偶偶线线性性规规划划模模型型,这这一一问问题题称称为为对对偶偶问问题题。生生产产计计划划的的线线性性规规划划问问题题称称为为原原始始线线性规划问题或性规划问题或原问题原问题。价价格格不不可可能能小小于于零零，即即有有yi0(i=1,4),从从而而企企业业的的资资源源价价格格模型为模型为线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第五页，共六十六页注：注：以上两问题是同一组数以上两问题是同一组数据参数，只是位置有所不同，据参数，只是位置有所不同，所描述的问题实际上是从两所描述的问题实际上是从两个不同的角度去描述。原始个不同的角度去描述。原始线性规划问题考虑的是充分线性规划问题考虑的是充分利用现有资源，以产品数量利用现有资源，以产品数量和单位产品的利润来决定企和单位产品的利润来决定企业的总利润，没有考虑资源业的总利润，没有考虑资源的价格，实际上在构成产品的价格，实际上在构成产品的利润中，不同的资源对利的利润中，不同的资源对利润的贡献也不同，它是企业润的贡献也不同，它是企业生产过程中一种隐含的潜在生产过程中一种隐含的潜在价值，经济学中称为价值，经济学中称为影子价影子价格格。线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第六页，共六十六页本讲稿第七页，共六十六页线性规划问题线性规划问题(2.2)就是原线性规划问题就是原线性规划问题(2.1)的对偶线性规划问题，的对偶线性规划问题，反之，反之，(2.2)的对偶问题就是的对偶问题就是(2.1)原问题与对偶问题有如下原问题与对偶问题有如下关系关系(假设原问题假设原问题(2.1)：(1)原问题的约束个数原问题的约束个数(不含非负约束不含非负约束)等于对偶变量的个数等于对偶变量的个数(2)原问题的目标函数系数对应于对偶问题的右端项原问题的目标函数系数对应于对偶问题的右端项(3)原问题的右端项对应于对偶问题的目标函数系数原问题的右端项对应于对偶问题的目标函数系数(4)原问题的约束矩阵转置就是对偶问题系数矩阵原问题的约束矩阵转置就是对偶问题系数矩阵(5)原问题求最大，对偶问题是求最小原问题求最大，对偶问题是求最小(6)原问题不等式约束符号为原问题不等式约束符号为“”,对偶问题不等式约束符号为对偶问题不等式约束符号为“”线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第八页，共六十六页【例【例2】写出该线性规划的对偶问题】写出该线性规划的对偶问题【解】【解】线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第九页，共六十六页线性规划问题的线性规划问题的规范形式规范形式(或叫或叫对称形式对称形式)：定义：定义：目标函数求目标函数求极大值极大值时，所有约束条件时，所有约束条件为为号号，变量非负变量非负；目标函数求目标函数求极小值极小值时，所有约束条件时，所有约束条件为为号，变量非负号，变量非负。注：注：(1)(1)线性规划规范形式与标准型是两种不同形式，但可线性规划规范形式与标准型是两种不同形式，但可以相互转换。以相互转换。(2)规范形式的线性规划问题的对偶仍然是规范形式规范形式的线性规划问题的对偶仍然是规范形式线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第十页，共六十六页对于一般的线性规划问题：对于一般的线性规划问题：其中其中为为矩阵，矩阵，为为维列向量，维列向量，为为维向量，维向量，为为维列向量维列向量(i=1,2,3;j=1,2)且且令令，此问题可化为此问题可化为线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第十一页，共六十六页用用分别表示以上四组约束的对偶问题，则分别表示以上四组约束的对偶问题，则原问题的对偶问题是原问题的对偶问题是本讲稿第十二页，共六十六页令令，整理得对偶问题为整理得对偶问题为将原问题与对偶问题的对将原问题与对偶问题的对应关系列于表应关系列于表2。本讲稿第十三页，共六十六页原问题(或对偶问题)对偶问题(或原问题)目标函数max目标函数系数(资源限量)约束条件系数矩阵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本讲稿第十四页，共六十六页【例【例3】写出下列线性规划的对偶问题】写出下列线性规划的对偶问题【解】【解】=y10，y20，y3无约束线性规划的对偶模型线性规划的对偶模型DualmodelofLP本讲稿第十五页，共六十六页对偶问题是对偶问题是(记为记为DP)：这里这里A是是mn矩阵矩阵,X是是n1列向量列向量,Y是是1m行向量。行向量。【性质性质1】对称性对称性:对偶问题的对偶是原问题。对偶问题的对偶是原问题。设原问题是设原问题是(记为记为LP)：对偶性偶性质Dualproperty对偶性质对偶性质【性质性质2】弱对偶性弱对偶性:设设X*、Y*分别为分别为LP(max)与与DP(min)的可行解，则的可行解，则 本讲稿第十六页，共六十六页对偶性偶性质Dualproperty由这个性质可得到下面几个由这个性质可得到下面几个结论结论：(1)(LP)的任一可行解的目标值是的任一可行解的目标值是(DP)的最优值下的最优值下(2)界；界；(DP)的任一可行解的目标是的任一可行解的目标是(LP)的最优值的上界；的最优值的上界；(2)在在互互为为对对偶偶的的两两个个问问题题中中，若若一一个个问问题题可可行行且且具具有有无无界解，则另一个问题无可行解；界解，则另一个问题无可行解；(3)若原问题可行且另一个问题不可行，则原问题具若原问题可行且另一个问题不可行，则原问题具有无界解。有无界解。注注意意:上上述述结结论论(2)及及(3)的的条条件件不不能能少少。一一个个问问题题无无可可行行解解时时，另另一一个个问问题题可可能能有有可可行行解解(此此时时具具有有无无界界解解)也也可可能能无可行解。无可行解。本讲稿第十七页，共六十六页例如：例如：无可行解，而对偶问题无可行解，而对偶问题有可行解，由结论有可行解，由结论(3)知必有无界解。知必有无界解。对偶性偶性质Dualproperty本讲稿第十八页，共六十六页【性性质质3】最最优优准准则则定定理理:设设X*与与Y*分分别别是是(LP)与与(DP)的的可可行解，则行解，则X*、Y*是是(LP)与与(DP)的最优解当且仅当的最优解当且仅当C X*=Y*b.对偶性偶性质Dualproperty【性性质质4】对对偶偶性性：若若互互为为对对偶偶的的两两个个问问题题其其中中一一个个有有最最优解，则另一个也有最优解，且最优值相同。优解，则另一个也有最优解，且最优值相同。另另一一结结论论：若若(LP)与与(DP)都都有有可可行行解解，则则两两者者都都有有最最优优解解，若若一个问题无最优解，则另一问题也无最优解。一个问题无最优解，则另一问题也无最优解。【性性质质5】互互补补松松弛弛定定理理:设设X*、Y*分分别别为为(LP)与与(DP)的的可可行行解解，XS和和YS分分别别是是它它们们的的松松弛弛变变量量的的可可行行解解，则则X*和和Y*是最优解当且仅当是最优解当且仅当YSX*=0和和Y*XS=0本讲稿第十九页，共六十六页性性质质5告告诉诉我我们们已已知知一一个个问问题题的的最最优优解解时时求求另另一一个个问问题题的的最最优解的方法，即已知优解的方法，即已知Y*求求X*或已知或已知X*求求Y*。Y*XS=0和和YS X*=0两式称为两式称为互补松弛条件互补松弛条件。将互补松弛条件写成下式。将互补松弛条件写成下式由由于于变变量量都都非非负负，要要使使求求和和式式等等于于零零，则则必必定定每每一一分分量量为为零零，因而有下列关系：因而有下列关系：对偶性偶性质Dualproperty本讲稿第二十页，共六十六页(1)当当yi*0时，时，,反之当反之当,时时yi*=0；利利用用上上述述关关系系，建建立立对对偶偶问问题题(或或原原问问题题)的的约约束束线线性性方方程程组，方程组的解即为最优解。组，方程组的解即为最优解。【例【例4】已知线性规划已知线性规划的最优解是的最优解是,求对偶问题的最优解。求对偶问题的最优解。对偶性偶性质Dualproperty本讲稿第二十一页，共六十六页【解】对偶问题是【解】对偶问题是因因为为x10，x20，所所以以对对偶偶问问题题的的第第一一、二二个个约约束束的的松松弛变量等于零，即弛变量等于零，即解解此此线线性性方方程程组组得得y1=1,y2=1,从从而而对对偶偶问问题题的的最最优优解解为为Y=(1，1)，最优值，最优值w=26。对偶性偶性质Dualproperty本讲稿第二十二页，共六十六页【例【例5】已知线性规划已知线性规划的对偶问题的最优解为的对偶问题的最优解为Y=(0，2)，求原问题的最优解。，求原问题的最优解。【解】对偶问题是【解】对偶问题是对偶性偶性质Dualproperty本讲稿第二十三页，共六十六页解方程组得：解方程组得：x1=5,x3=1,所以原问题的最优解为所以原问题的最优解为X=(5，0，1)T，最优值，最优值Z=12。因为因为y20，所以原问题第二个松弛变量，所以原问题第二个松弛变量=0，由，由y1=0、y2=2知，松弛变量知，松弛变量故故x2=0，则原问题的约束条件为线性方程组：则原问题的约束条件为线性方程组：对偶性偶性质Dualproperty本讲稿第二十四页，共六十六页【例【例6】证明该线性规划无最优解：证明该线性规划无最优解：【证】容易看出【证】容易看出X=(4，0，0)是一可行解。对偶问题是一可行解。对偶问题将三个约束的两端分别相加得将三个约束的两端分别相加得,而第二个约束有而第二个约束有y21,矛盾，故对偶问题无可行解，因而原问题具有矛盾，故对偶问题无可行解，因而原问题具有无界解，即无最优解。无界解，即无最优解。对偶性偶性质Dualproperty本讲稿第二十五页，共六十六页【性性质质6】LP(max)的的检检验验数数的的相相反反数数对对应应于于DP(min)的的一一组组基基本本解解，其其中中第第j个个决决策策变变量量xj的的检检验验数数的的相相反反数数对对应应于于(DP)中中第第j个个松松弛弛变变量量的的解解，第第i个个松松弛弛变变量量的的检检验验数数的的相相反反数数对对应应于于第第i个个对对偶偶变变量量yi的的解解。反反之之，(DP)的的检检验验数数(注注意意：不不乘乘负负号号)对对应于应于(LP)的一组基本解。的一组基本解。对偶性偶性质Dualproperty注：注：应用性质应用性质6 6 的前提是线性规划为规范形式，而性质的前提是线性规划为规范形式，而性质1-1-5 5则对所有形式线性规划有效。则对所有形式线性规划有效。本讲稿第二十六页，共六十六页根据对偶性质；可将原问题与对偶问题解的对应关系列表根据对偶性质；可将原问题与对偶问题解的对应关系列表如下：如下：一个问题max另一个问题min有最优解有最优解性质4无无最优解无最优解性质4最优无界解(有可行解)无可行解性质2解无可行解无界解(有可行解)应用已知最优解通过解方程求最优解性质5已知检验数检验数乘以1求得基本解性质6对偶性偶性质Dualproperty本讲稿第二十七页，共六十六页影子价格影子价格因为原问题和对偶问题的最优值相等，将线性规划的目因为原问题和对偶问题的最优值相等，将线性规划的目标函数表达成资源的函数，故有标函数表达成资源的函数，故有即即yi是第是第i 种资源的变化率，说明当其它资源供应量种资源的变化率，说明当其它资源供应量bk(ki)不变时，不变时，bi增加一个单位时目标值增加一个单位时目标值Z 增加增加yi个单位个单位对偶性偶性质Dualproperty本讲稿第二十八页，共六十六页正确理解影子价格，利用影子价格作下列经济活动分析正确理解影子价格，利用影子价格作下列经济活动分析:(1)调节生产规模例如，目标函数调节生产规模例如，目标函数Z表示利润表示利润(或产值或产值)(2)当第当第i 种资源的影子价格大于零种资源的影子价格大于零(或高于市场价格或高于市场价格)时，时，表表(3)示有利可图，企业应购进该资源扩大生产规模，当影子示有利可图，企业应购进该资源扩大生产规模，当影子价格等于零价格等于零(或低于市场价格或低于市场价格)，企业不能增加收益，这，企业不能增加收益，这(1)时应将资源卖掉或出让，缩小生产规模。时应将资源卖掉或出让，缩小生产规模。(2)生产要素对产出贡献的分解通过影子价格分析每生产要素对产出贡献的分解通过影子价格分析每(3)种资源获得多少产出例如，企业获得种资源获得多少产出例如，企业获得100万元的利润，万元的利润，(4)生产过程中产品的直接消耗的资源有材料生产过程中产品的直接消耗的资源有材料A、材料、材料B、设备和工时，这些资源各产生多少利润，由影子价格可设备和工时，这些资源各产生多少利润，由影子价格可以大致估计出来。以大致估计出来。对偶性偶性质Dualproperty本讲稿第二十九页，共六十六页(3)由性质由性质2.5知，第知，第i个松弛变量大于零时第个松弛变量大于零时第i个对偶变个对偶变(4)量等于零，并不能说明该资源在生产过程中没有作出量等于零，并不能说明该资源在生产过程中没有作出(5)贡献，只能理解为第贡献，只能理解为第i种资源有剩余时再增加该资源量种资源有剩余时再增加该资源量(6)不能给企业带来利润或产值的增加不能给企业带来利润或产值的增加(4)影子价格是企业生产过程中资源的一种隐含的潜在价影子价格是企业生产过程中资源的一种隐含的潜在价(5)值，表明单位资源的贡献，与市场价格是不同的两个概值，表明单位资源的贡献，与市场价格是不同的两个概(6)念同一种资源在不同的企业、生产不同的产品或在不念同一种资源在不同的企业、生产不同的产品或在不(7)同时期影子价格都不一样同时期影子价格都不一样例如，某种钢板市场价格是例如，某种钢板市场价格是(8)每吨每吨8000元，一个企业用来生产汽车，另一个企业用来元，一个企业用来生产汽车，另一个企业用来(9)生产空调外壳，每吨钢板的产值是不一样的生产空调外壳，每吨钢板的产值是不一样的对偶性偶性质Dualproperty本讲稿第三十页，共六十六页(5)影子价格是一个变量由影子价格是一个变量由的含义知影子的含义知影子(6)价格是价格是一种边际产出，与一种边际产出，与bi的基数有关，在最优基的基数有关，在最优基B(7)不变的条件下不变的条件下yi不变，当某种资源增加或减少后，不变，当某种资源增加或减少后，最最(8)优基优基B可能发生了变化，这时可能发生了变化，这时yi的值也随之发生变化的值也随之发生变化对偶性偶性质Dualproperty本讲稿第三十一页，共六十六页对偶单纯形法对偶单纯形法对于任何一个可行基对于任何一个可行基B,为原问题的为原问题的一个基可行解，单纯形法是从一个基可行解到另一个相一个基可行解，单纯形法是从一个基可行解到另一个相邻的基可行解，直到基邻的基可行解，直到基B满足满足 为止。为止。对偶偶单纯形法形法DualSimplexMethod单纯形法首先化问题为标准型：单纯形法首先化问题为标准型：本讲稿第三十二页，共六十六页对偶偶单纯形法形法DualSimplexMethod原始单纯形法的思想原始单纯形法的思想：从满足可行性条件的一个基可行解从满足可行性条件的一个基可行解(即基即基B满足满足)出发，经过换基运算迭代到另一个基可行解，出发，经过换基运算迭代到另一个基可行解，直到找到满足最优性条件直到找到满足最优性条件()的基可行解，的基可行解，这就是原问题的最优解。这就是原问题的最优解。CBB1bC-CBB1AB-1 1bB-1A XBbX对于任意基对于任意基B ,对应的单纯形表为对应的单纯形表为本讲稿第三十三页，共六十六页若上表为最优单纯形表，则下列两个式子同时成立：若上表为最优单纯形表，则下列两个式子同时成立：对偶偶单纯形法形法DualSimplexMethod问题：可否从满足条件问题：可否从满足条件(2)的基出发去找原问题的最优解？的基出发去找原问题的最优解？对偶单纯形法思想对偶单纯形法思想：从满足条件从满足条件(2)的基的基(一般称为一般称为正则基正则基)B出发，经过出发，经过换基运算到另一个正则基，即一直保证条件换基运算到另一个正则基，即一直保证条件(2)成立，直成立，直到找到一个满足条件到找到一个满足条件(1)的正则基。的正则基。CBB1bC-CBB1AB-1 1bB-1A XBX本讲稿第三十四页，共六十六页对偶单纯形法的计算步骤对偶单纯形法的计算步骤：(1)将将线线性性规规划划的的约约束束化化为为等等式式，找找出出一一个个正正则则基基，即即全全部部检检验验数数j0（max）或或j0（min）,求求出出其其对对应应的的基基本本解解，当当基基本本解解可可行行时时，则则达达到到最最优优解解；若若基基本本解解不不可可行行，即即有有某某个个基基变变量量的的解解bi0，则进行换基计算；则进行换基计算；(2)换基计算换基计算(i)先确定先确定出基变量出基变量:l 行对应的变量出基；行对应的变量出基；(ii)再选再选进基变量进基变量:求最小比值求最小比值(3)求求新新的的基基本本解解，用用初初等等变变换换将将主主元元素素alk化化为为l,k列列其其它它元元素素化化为为零零，得得到新的基本解，转到第到新的基本解，转到第(1)步重复运算。步重复运算。对偶偶单纯形法形法DualSimplexMethod本讲稿第三十五页，共六十六页【例【例7】用对偶单纯形法求解】用对偶单纯形法求解【解】先将约束不等式化为等式，再两边同乘以【解】先将约束不等式化为等式，再两边同乘以(1)，得到，得到x4、x5为基变量，用对偶单纯形法，迭代过程如表为基变量，用对偶单纯形法，迭代过程如表2-7所示。所示。对偶偶单纯形法形法DualSimplexMethod本讲稿第三十六页，共六十六页XBx1x2x3x4x5b表(1)x4x5-1-1-11-14100153j41300表表2-7对偶偶单纯形法形法DualSimplexMethod最优解：最优解：X(4，1，0)T；Z=17表(2)x2x51-21013-110158j30210表(3)x2x101105/2-3/2-1/2-1/21/21/214j0013/25/23/2本讲稿第三十七页，共六十六页线线性性规规划划的的灵灵敏敏度度分分析析也也称称为为敏敏感感性性分分析析，它它是是研研究究和和分分析析数数据据(cj，bi，aij)的的波波动动对对最最优优解解的的影影响响程程度度，主主要要研研究究下面两个方面：下面两个方面：(1)当当模模型型中中这这些些数数据据有有一一个个或或几几个个发发生生变变化化时时，最最优优解解有有什什么么变变化化，或或这这些些数数据据在在什什么么范范围围内内变变化化时时，原原最最优优解解或最优基不变；或最优基不变；(2)若若最最优优解解或或最最优优基基发发生生变变化化后后，如如何何求求出出新新的的最最优基或最优解。优基或最优解。灵敏度分析灵敏度分析灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第三十八页，共六十六页设线性规划设线性规划其中其中Amn，线性规划有最优解，设基，线性规划有最优解，设基B为最优基，则有为最优基，则有灵敏度分析灵敏度分析SensitivityAnalysis求解思路：求解思路：将变化后的数据代入上述公式，看看可行性将变化后的数据代入上述公式，看看可行性条件与最优性条件是否依然成立：若成立，则还是最优条件与最优性条件是否依然成立：若成立，则还是最优解；若不成立，则利用单纯形法或对偶单纯形法可求出解；若不成立，则利用单纯形法或对偶单纯形法可求出变化后的最优解。变化后的最优解。本讲稿第三十九页，共六十六页价值系数价值系数cj 的变化分析的变化分析为使最优解不变，求为使最优解不变，求cj 的变化范围的变化范围灵敏度分析灵敏度分析SensitivityAnalysis由最优性条件可知，当目标函数系数由最优性条件可知，当目标函数系数发生变化时，发生变化时，有可能引起检验数有可能引起检验数的变化，从而影响最优性条件的变化，从而影响最优性条件是否满足？是否满足？要使最优解不变，即当要使最优解不变，即当cj 变化为变化为后，检验数仍然是小于等于零，即后，检验数仍然是小于等于零，即这时分这时分cj是非基变量和基变量的系数两种情况讨论。是非基变量和基变量的系数两种情况讨论。本讲稿第四十页，共六十六页(1)cj 是非基变量是非基变量xj 的系数的系数即即cj的的增增量量不不超超过过cj的的检检验验数数的的相相反反数数时时，最最优优解解不变，否则最优解就要改变。不变，否则最优解就要改变。所以所以(2)ci是基变量是基变量xi的系数的系数 因因ciCB，故每个检验数，故每个检验数j 中含有中含有 ,当当c i变化为变化为c ici后后j 同时变化，这时同时变化，这时灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十一页，共六十六页令令要使得所有要使得所有，则有，则有灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十二页，共六十六页要使得所有要使得所有，则有，则有只要求出上限只要求出上限2及下限及下限1就可以求出就可以求出ci的变化区间的变化区间灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十三页，共六十六页资源限量资源限量bi 变化分析变化分析为了使最优基为了使最优基B不变，求不变，求bi的变化范围。的变化范围。设设br的增量为的增量为br ,b 的增量为的增量为原原性性规规划划的的最最优优解解为为X，基基变变量量为为XB=B1b，要要使使最最优优基基B不不变变，即要求即要求而而灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十四页，共六十六页因为因为灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十五页，共六十六页所以所以令令灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十六页，共六十六页因而要使得所有因而要使得所有必须满足必须满足这这个个公公式式与与求求的的上上、下下限限的的公公式式类类似似，比比值值的的分分子子都都小小于于等等于于零零，分分母母是是B1中中第第r列列的的元元素素，大大于于等等于于比比值值小小于于零零的的最大值，小于等于比值大于零的最小值。当某个最大值，小于等于比值大于零的最小值。当某个时，时，可能无上界或无下界。可能无上界或无下界。灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十七页，共六十六页约束系数的灵敏度分析约束系数的灵敏度分析1 1、非基变量非基变量 的系数列向量的系数列向量 发生变化发生变化则改变后只影响则改变后只影响 的检验数，而对其他的检验数没有影响的检验数，而对其他的检验数没有影响由于由于 是对偶可行解，要使最优基是对偶可行解，要使最优基B B不变，则必须有不变，则必须有灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十八页，共六十六页当当中只有第中只有第i 个分量发生变化个分量发生变化灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第四十九页，共六十六页2 2、基变量基变量 的系数列向量的系数列向量 发生变化发生变化当最优基当最优基B的列向量的列向量发生变化时，发生变化时，也发生变化，从单也发生变化，从单纯形表可知，几乎所有位置都受到影响，故很难给出变化范纯形表可知，几乎所有位置都受到影响，故很难给出变化范围的一般公式，在实际问题中往往重新计算。围的一般公式，在实际问题中往往重新计算。3 3、增加新的决策变量增加新的决策变量假假设设增增加加一一个个新新变变量量 ，其其对对应应的的目目标标函函数数系系数数为为 ，在在约约束束函函数数中中对对应应的的列列向向量量 ，在在最最优优单单纯纯形表中增加一列形表中增加一列 相应的检验数为相应的检验数为 若若 ，则原问题最优解不变，则原问题最优解不变 若若 ，则以，则以 为新的进基变量，可用单纯形法继续迭代。为新的进基变量，可用单纯形法继续迭代。灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第五十页，共六十六页4 4、增加新的约束条件增加新的约束条件(i)若在原问题中增加一个新的不等式约束条件若在原问题中增加一个新的不等式约束条件先将原问题的最优解代入新的约束条件中，若满足，则原最优解先将原问题的最优解代入新的约束条件中，若满足，则原最优解是新问题的最优解，否则需将新约束加入原问题，具体做法：是新问题的最优解，否则需将新约束加入原问题，具体做法：(1)引入松弛变量引入松弛变量，新约束成为，新约束成为(2)在单纯形表中增加一行一列，并以在单纯形表中增加一行一列，并以为基变量，为基变量，下面的下面的系数为系数为，注意，注意在单纯形表中的列向量在单纯形表中的列向量是单位向量，而原来的是单位向量，而原来的m个基变量对应的列向量可能不是单位向个基变量对应的列向量可能不是单位向量，故应先做初等变换，然后继续迭代求解。量，故应先做初等变换，然后继续迭代求解。灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第五十一页，共六十六页(ii)若在原问题中增加一个新的等式约束条件若在原问题中增加一个新的等式约束条件先将原问题的最优解代入新的约束条件中，若满足，则原先将原问题的最优解代入新的约束条件中，若满足，则原最优解不变，否则在新约束引入人工变量，再用大最优解不变，否则在新约束引入人工变量，再用大M法求法求解新问题。解新问题。灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第五十二页，共六十六页注：注：由以上讨论可知，当某些参数变化时，并不一定要用单纯形由以上讨论可知，当某些参数变化时，并不一定要用单纯形法重新计算，而可从原最优单纯形表出发，做适当修改，再根据法重新计算，而可从原最优单纯形表出发，做适当修改，再根据具体情况求得新最优解，其步骤如下：具体情况求得新最优解，其步骤如下：(1)修改原最优单纯形表，以反映参数的变化。修改原最优单纯形表，以反映参数的变化。(2)检验以上修改是否使最优解发生变化，即以下式子是否成立：检验以上修改是否使最优解发生变化，即以下式子是否成立：(3)若满足可行性而不满足最优性，则用单纯形法求解；若满足可行性而不满足最优性，则用单纯形法求解；若满足最优性而不满足可行性，则用对偶单纯形法求解。若满足最优性而不满足可行性，则用对偶单纯形法求解。(4)若可行性与最优性都不满足，则引入人工变量后重新求解；若可行性与最优性都不满足，则引入人工变量后重新求解；若最优性与可行性都满足，则最优基不变。若最优性与可行性都满足，则最优基不变。灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第五十三页，共六十六页【例【例8】考虑下列线性规划】考虑下列线性规划求求出出最最优优解解后后，分分别别对对下下列列各各种种变变化化进进行行灵灵敏敏度度分分析析，求出变化后的最优解。求出变化后的最优解。综合应用综合应用灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第五十四页，共六十六页(2)改变目标函数改变目标函数x3的系数为的系数为c3=1;(3)改变改变x2的系数为的系数为(4)改变约束改变约束(1)为为(5)增加新约束增加新约束(1)改变右端常数为改变右端常数为:本讲稿第五十五页，共六十六页【解】加入松弛变量【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优表如，用单纯形法计算，最优表如210所示。所示。表表210Cj2-14000bCBXBx1x2x3x4x5x64x305/711/73/7022x112/701/74/7010 x60200111j031/702/720/70最优解最优解X=(1，0，2，0，0，1)T，最优值，最优值Z=10灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第五十六页，共六十六页最优基矩阵及其逆最优基矩阵及其逆(1)基变量的解为基变量的解为基基本本解解不不可可行行，将将求求得得的的XB代代替替表表210中中的的常常数数项项，用用对对偶偶单单纯纯形形法求解，其结果见表法求解，其结果见表211所示。所示。灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第五十七页，共六十六页表表211Cj214000bCBXBx1x2x3x4x5x64x305/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本讲稿第五十八页，共六十六页最优解最优解(2)由表由表210容易得到基变量容易得到基变量x3的系数的系数c3的增量变化范围是的增量变化范围是而而c3=1不不在在允允许许的的变变化化范范围围之之外外，故故表表210的的解解不不是是最最优优解解。非非基变量的检验数基变量的检验数x4进基，用单纯形法计算，得到表进基，用单纯形法计算，得到表212灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第五十九页，共六十六页表表212XBx1x2x3x4x5x6bx305/711/73/702x112/701/74/701x60200111j016/701/711/70 x405713014x11110103x60200111j031020最优解为最优解为X=(3，0，0，14，0，1)T，最优值，最优值Z=6。灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第六十页，共六十六页(3)这时目标函数的系数和约束条件的系数都变化了，同样求出这时目标函数的系数和约束条件的系数都变化了，同样求出2判别最优解是否改变。判别最优解是否改变。x2进基，计算结果如表进基，计算结果如表213所示所示灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第六十一页，共六十六页表表213Cj234000bCBXBx1x2x3x4x5x64x30011/73/7022x11101/74/7010 x60300111j0502/720/704x30011/73/7022x11001/75/211/34/33x201001/31/31/3j0002/725/215/3最优解最优解灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第六十二页，共六十六页(4)第第一一个个约约束束变变为为实实际际上上是是改改变变了了a12及及b1，这时要求，这时要求2及及XB，判断解的情况，判断解的情况,因为因为可行，所以最优解为可行，所以最优解为灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第六十三页，共六十六页。应当注意，当应当注意，当且且时用单纯形法继续迭代，当时用单纯形法继续迭代，当且且不可行时用对偶单纯形法继续迭代，当不可行时用对偶单纯形法继续迭代，当且且不可行时，需加入人工变量另找可行基不可行时，需加入人工变量另找可行基.(5)引入松弛变量引入松弛变量x7得得 x1、x3是基变量，利用表是基变量，利用表27消去消去x1、x3，得，得x7为为新新的的基基变变量量，基基本本解解X=(1，0，2，0，0，1，2)T 不不可可行行，将将上上式加入表式加入表210中用对偶单纯形法迭代得到表中用对偶单纯形法迭代得到表2-14。灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第六十四页，共六十六页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本讲稿第六十五页，共六十六页表表2-15参数或条件变化最优表可能发生变化可行与最优方 法基变量系数ci所有非基变量的检验数可行若非最优，用普通单纯形法非基变量系数cj只有xj的检验数变化可行若非最优，用普通单纯形法biXB对偶问题可行若不可行，用对偶单纯形法基变量系数aij基、基变量、检验数等视检验数和基本解来确定非基变量系数aij非基变量系数及xj的检验可行若非最优，用普通单纯形法综合变化，参数、增减变量与约束等用1.5介绍的5个计算公式判断变化情况若原问题与对偶问题都不可行，用人工变量法灵敏度分析灵敏度分析SensitivityAnalysis本讲稿第六十六页，共六十六页