第四章 对偶理论及灵敏度分析

1、机械设计制造机械设计制造2010级级2022-3-111机械设计制造机械设计制造2010级级2022-3-1124对偶理论与灵敏度分析对偶理论与灵敏度分析4-1 线性规划对偶问题4-2 对偶单纯形法4-3 影子价格4-4 灵敏度分析Operations Research2022-3-11本科适用本科适用34-1线性规划对偶问题线性规划对偶问题 在例在例2.7中：某工厂生产中：某工厂生产I、II两种型号的计算机，为了生产两种型号的计算机，为了生产一台一台I型和型和 II型计算机，所需要原料分别为型计算机，所需要原料分别为2和和3个单位，需要个单位，需要的工时分别为的工时分别为4和和2个单位。在计

2、划期内可以使用的原料为个单位。在计划期内可以使用的原料为100个单位，工时为个单位，工时为120个单位。已知生产每一台个单位。已知生产每一台I 、II型计型计算机可获利分别为算机可获利分别为6和和4个单位，试确定获利最大的生产方案。个单位，试确定获利最大的生产方案。 I 型计算机型计算机 II型计算机型计算机原料2 23 3100100工时4 42 2120120利润（每台）6 64 4 Operations Research2022-3-11本科适用本科适用4设 y1 ，y2 分别为每单位原料与每工时收取费用。4-14-1线性规划对偶问题线性规划对偶问题1.对偶问题： 若该工厂的原料和工时都

3、用于对外出租，工厂收取租赁费。试问：每单位原料与每工时各如何收费才最有竞争力？Operations Research2022-3-11本科适用本科适用54-1线性规划对偶问题线性规划对偶问题原问题原问题对偶问题对偶问题（不少于型的利润）（不少于型的利润）0,423642. .120100inf21212121yyyyyytsyyM0,120241003246max21212121xxxxxxxxzOperations Research2022-3-11本科适用本科适用64-1线性规划对偶问题线性规划对偶问题 2、对偶定义 对称形式： 互为对偶0. .XbAXt sXCMaxz(LP)TTTYC

4、YAtsYbM0. .inf“Min- ”“Max - ”(DP)Operations Research2022-3-11本科适用本科适用7 一对对称形式的对偶规划之间具有下面的对应关系。v（1）原问题的目标是对CX求极大，而对偶问题的目标是对Yb求极小；v （2）原问题的价值系数成为对偶问题的资源系数，原问题的资源系数b成为对偶问题的价值系数； 4-1线性规划对偶问题线性规划对偶问题Operations Research2022-3-11本科适用本科适用84-1线性规划对偶问题线性规划对偶问题v（3）对偶问题与原问题相比较，约束条件的 方向改变了；v （4）原问题的系数矩阵的转置恰为对偶问题

5、的系数矩阵，即原问题的每一列系数对应对偶问题的每一行系数；v （5）原问题的约束行数等于对偶问题的变量数，即列数，而原问题的变量数等于对偶问题的约束行数。Operations Research2022-3-11本科适用本科适用94-1线性规划对偶问题线性规划对偶问题v3、 对偶理论v性质性质1：（对称性）：（对称性）对偶问题（D）的对偶是原问题（L）。v性质性质2：原问题第i个约束为等式，则其对偶问题中的第i个对偶变量为自由变量；v反之，若原问题的第j个变量是自由变量，则其对偶问题的第j个约束为等式。v*根据对偶的定义及前述的两个性质，可以求出任何形式的线性规划的对偶规划。* Operatio

6、ns Research2022-3-11本科适用本科适用104-1线性规划对偶问题线性规划对偶问题v线性规划原问题与其对偶问题不仅具有形式上的对称性，而且它们的解之间也具有紧密的联系。0,34313242min2131321321321xxxxxxxxxxxxxz0,34313242min2131321321321xxxxxxxxxxxxxz变形 0,41323234max2132121321321yyyyyyyyyyyyyz互为互为对偶对偶Operations Research2022-3-11本科适用本科适用114-1线性规划对偶问题线性规划对偶问题v性质性质3：（弱对偶性）：（弱对偶性）

7、设X、Y分别是原问题（L）和对偶问题（D）的任一可行解，则： YbCX 00YCYAXbAX且YbAX两端同乘以XCYA两端同乘以CXYAXYbYAX,YbCX性质性质4：（无界性）若原问题：（无界性）若原问题(对偶问题对偶问题)为为无界解，则其对偶问题（原问题）无可行解。无界解，则其对偶问题（原问题）无可行解。（这个性质可由弱对偶性证得，此处略。）（这个性质可由弱对偶性证得，此处略。）则则v证明：由已知证明：由已知在在在在得到：得到：Operations Research2022-3-11本科适用本科适用124-1线性规划对偶问题线性规划对偶问题v性质性质5：设 是原问题的可行解， 是对偶问

8、题的可行解，且 ，则 、 是各自问题的最优解。v证明：设X是原问题的任一可行解，则有 v 是原问题的最优解。v同理 ，v性质性质6：若原问题有最优解，那么其对偶问题也有最优解，且它们的最优值相等 v XXYYbYCXXCYbCXYbXCYbYX可见是对偶问题的最优解。所以Operations Research2022-3-11本科适用本科适用134-1线性规划对偶问题线性规划对偶问题v性质性质7：在对称形式对偶问题的线性规划中，对偶问题最优解的单纯形表上，出现在目标v函数检验数行的后面的m个元素（不包括常数项），它们的相反数构成原问题的最优解。 Operations Research2022-

9、3-11本科适用本科适用144-1线性规划对偶问题线性规划对偶问题 例3.1 写出下面线性规划的对偶规划模型解 先将约束条件变形为“”形式没有非负限制4321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxxZOperations Research2022-3-11本科适用本科适用154-1线性规划对偶问题线性规划对偶问题没有非负限制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx 再根据非对称形式的对应关系，直接写出对偶规划Operations Research20

10、22-3-11本科适用本科适用164-1线性规划对偶问题线性规划对偶问题0,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyyyyyyyyyf没有非负限制Operations Research2022-3-11本科适用本科适用174-2 对偶单纯形法对偶单纯形法v从前面讨论中，可以看到在原问题取得最优解时，也得到对偶问题的最优解。v即：如果原问题最优基为B，取 v则所有v 1BCYB0jjjYPccYAYCXbCBYb1也就是则是对偶可行解又因为所以也是最优解。Operations Research2022-3-11本科适

11、用本科适用184-2 对偶单纯形法对偶单纯形法v 在单纯形算法中，是从一个原问题的基可行解转到另一个基可行解，一直迭代到 是对偶可行解为止。 1 CBYOperations Research2022-3-11本科适用本科适用194-2 对偶单纯形法对偶单纯形法v 对偶单纯形法则是从原问题的一个对偶可行解（满足所有的 ）v出发，以基变量值是否全部非负为检验数，连续迭代到原问题的可行解为止。01jjjPCBcOperations Research2022-3-11本科适用本科适用204-2 对偶单纯形法对偶单纯形法v 两种算法最终的结果是一样的，区别是对偶单纯形法的初始解不一定要满足原问题的可行性

12、，而只要求所有检验数都非正即可，v 在保证所得解始终是对偶可行解的前提下，连续迭代到原问题的基可行解，从而取得问题的最优解。 Operations Research2022-3-11本科适用本科适用214-2 对偶单纯形法对偶单纯形法v对偶单纯形法计算步骤如下：v步骤步骤1： 确定原问题（L）的初始基B，使所有 ，即 是基可行解，建立初始单纯形表。v步骤步骤2： 检查基变量所取的值，若 ，v则已经得到最优解，停止计算。否则，计算v ，确定 为旋出变量。0j1CBY01bBXBLiibBbBbB)(0)( |min111）（LBxOperations Research2022-3-11本科适用本

13、科适用224-2 对偶单纯形法对偶单纯形法v步骤步骤3： 若所有 ，则原问题无可行解，计算停。否则计算 确定为 xk 旋入变量。v步骤步骤4： 以 alk 为主元作（L,K）旋转变换，转步骤2。v可以证明按照上述方法进行迭代，所得解始终是对偶可行解。0ljalkkljljjaaa0|minOperations Research2022-3-11本科适用本科适用234-2 对偶单纯形法对偶单纯形法v例：例：用对偶单纯形法求解下面的问题：0,34222421216812min43214213214321xxxxxxxxxxxxxxz解：解：令zz则问题可以标准化为：Operations Resea

14、rch2022-3-11本科适用本科适用244-2 对偶单纯形法对偶单纯形法v取初始基0,34222421216812max654321642153214321xxxxxxxxxxxxxxxxxxz100165PP0,3265jxxx其余12,16, 8,1243211BCYB是对偶可行解，建立单纯形表（见表是对偶可行解，建立单纯形表（见表4-1） 则则是非基可行解，但是非基可行解，但Operations Research2022-3-11本科适用本科适用254-2 对偶单纯形法对偶单纯形法CCBXBB-1b x1 x2 x3 x4 x5 x600X5X6-2-30-12-23/4001216

15、8121040220104120012168124/10102/12/101041245xx3001626Operations Research2022-3-11本科适用本科适用264-2 对偶单纯形法对偶单纯形法CCBXBB-1b x1 x2 x3 x4 x5 x6-8-12X2X42-1/4-8-12X2X111/20012168124/ 12/ 11202/ 10104123208022/1124011344102368600Operations Research2022-3-11本科适用本科适用274-2 对偶单纯形法对偶单纯形法v一般情况下，如果问题能够用对偶单纯形法，计算量会少于单

16、纯形法。v 但是，并不是任何问题都能用对偶单纯形法计算的。当线性规划问题具备下面条件时，可以用偶单纯形法求解：v 问题标准化后，价值系数全非正； 所有约束条件全是不等式。v一般，当问题中的变量多于约束条件时，用对偶单纯形法计算可以减少计算工作量。Operations Research2022-3-11本科适用本科适用284-2 对偶单纯形法对偶单纯形法v证明：证明：首先看到问题存v在可行解，如（0 0 0）v上述问题的对偶问题： v由第一约束条件可知对v偶问题无可行解，因而v无最优解。由此，原问v题也无最优解。 0,122max32132132121xxxxxxxxxxxz0,01122min

17、2121212121yyyyyyyyyyw例：已知线性规划问题：例：已知线性规划问题：试用对偶理论证明该试用对偶理论证明该线性规划问题无最优解线性规划问题无最优解。Operations Research2022-3-11本科适用本科适用29 对偶单纯形法的适用范围对偶单纯形法的适用范围 对偶单纯形法适合于解如下形式对偶单纯形法适合于解如下形式的线性规划问题的线性规划问题njxmibxacxcfjnjijijnjjjj,2, 1,0,2, 10min114-24-2对偶单纯形法对偶单纯形法Operations Research2022-3-11本科适用本科适用30 在引入松弛变量化为标准型之后，

18、约束等式两侧同乘-1，能够立即得到检验数全部非正的原规划基本解，可以直接建立初始对偶单纯形表进行求解，非常方便。 对于有些线性规划模型，如果在开始求解时不能很快使所有检验数非正，最好还是采用单纯形法求解。因为，这样可以免去为使检验数全部非正而作的许多工作。 从这个意义上看，可以说，对偶单纯形法是单纯形法的一个补充。除此之外，在对线性规划进行灵敏度分析中有时也要用到对偶单纯形方法，可以简化计算。4-24-2对偶单纯形法对偶单纯形法Operations Research2022-3-11本科适用本科适用31单纯形表的理解（例题）单纯形表的理解（例题）上表中6个常数 a1 , a2 , a3 , b

19、 , 1 , 2 取值在什么范围可使1、现可行解最优，且唯一？何时不唯一？2、现基本解不可行；3、问题无可行解；4、无有限最优解；5、现基本解可行，由 x1 取代 x6 目标函数可改善。 CiCBXBbx1x2x3x4x5x6 x3b4a110a20 x42-1-501-10 x63a3-300-411200-30Operations Research2022-3-11本科适用本科适用32单纯形法和对偶单纯形法步骤是是是是是是是是否否否否否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代以为中心

20、元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0minOperations Research2022-3-11本科适用本科适用334-3影子价格影子价格*22*11*mmybybybfZmiybZii,2,1,*, yx*bycx*iy*iy分别为（LP）和（DP）的最优解 那么有：那么有：根据根据可知可知表示表示 bi 变化变化1个单位对目标个单位对目标 f 产生的影响产生的影响 为为 bi 的影子价格的影子价格称称Operations Resear

21、ch2022-3-11本科适用本科适用344-3影子价格影子价格 影子价格影子价格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。1*BCyB注意：注意：若若 B 是最优基，则是最优基，则为影子价格向量为影子价格向量Operations Research2022-3-11本科适用本科适用354-3影子价格影子价格v 另单纯形中，设B是最优基， v是最优解；则最优值 v 取 v则Y是对偶最优解。bBXB10NxbBCzB1mByyyBCY211Operations Research2022-3-11本科适用本科适用364-3影子价格影子价格v下面我们进一步讨论一下 v的经济含义。

22、v设 v有单位增量，即：v其它各参数不变。若最优基不变，则 ), 2 , 1(miYi),2,1(mibi1ibiiBbYzbbBCzz)0, 0 , 0(1iiYbYzOperations Research2022-3-11本科适用本科适用374-3影子价格影子价格v综上，所以 表示在原问题已取得最优解的情况下，第i种资源改变一个单位时，总收益的变化值。v 也可以说 是对第i种资源的一种价格估计。这种价格估计并不是第i种资源的实际成本或价值，而是由该企业在制产品的收益来估计所用资源的单位价值称为影子价格。 iYiYOperations Research2022-3-11本科适用本科适用384

23、-3影子价格影子价格v 由于影子价格是指资源增加时对最优收由于影子价格是指资源增加时对最优收益的贡献，所以也称它为资源的机会成本或益的贡献，所以也称它为资源的机会成本或边际产出，它表示资源在最优产品组合时，边际产出，它表示资源在最优产品组合时，具有的具有的“潜在价值潜在价值”或或“贡献贡献”。v 资源的影子价格是与具体的企业及产品资源的影子价格是与具体的企业及产品有关的，同一种资源，在不同企业或生产不有关的，同一种资源，在不同企业或生产不同产品时，对应的影子价格并不相同。同产品时，对应的影子价格并不相同。Operations Research2022-3-11本科适用本科适用394-3影子价格

24、影子价格v 影子价格是经济学中的重要概念，将一影子价格是经济学中的重要概念，将一个企业拥有的资源的影子价格与市场价格比个企业拥有的资源的影子价格与市场价格比较，可以决定是购入或出让该种资源。较，可以决定是购入或出让该种资源。v在考虑一个地区或国家某种资源的进出口决策中，在考虑一个地区或国家某种资源的进出口决策中，资源的影子价格是影响决策的一个重要的因素。资源的影子价格是影响决策的一个重要的因素。 当某种资源的市场价格低于影子价格时，企业应该当某种资源的市场价格低于影子价格时，企业应该购入该资源用于扩大生产购入该资源用于扩大生产；否则，应将已有资源卖掉。否则，应将已有资源卖掉。Operation

25、s Research2022-3-11本科适用本科适用40BCBXbB14321xxxx12xxjC 6 4 0 0备注 4 620208/34/1014/12/1104/52/100上表为例上表为例2.7的最优单纯形表，在单纯形法计算表中，的最优单纯形表，在单纯形法计算表中，可以算得问题的各种资源的影子价格可以算得问题的各种资源的影子价格。其中松弛变量其中松弛变量43xx 、的检验数分别为：的检验数分别为：2/101Y4/500244YYP4-3影子价格影子价格3YP0 31B33PBCCOperations Research2022-3-11本科适用本科适用41BCBXbB14321xxx

26、x43xx12xxjC 6 4 0 0备注 0 0100120 100/2120/4K=1L=2 6 4 0 0. . 4 62020j4/52/1002/1013Y4/5024Y01103/81/4-1/4-1/224321001Operations Research2022-3-11本科适用本科适用42 影子价格的经济含义 影子价格是对现有资源实现最大效益时的一种估价。 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。 第二，是否将投资用于购买设备，以扩大生产能力，若市价低于设备的影子价格

27、，可考虑买进该设备，否则不宜买进。4-3影子价格影子价格Operations Research2022-3-11本科适用本科适用43 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。4-3影子价格影子价格Operations Research2022-3-11本科适用本科适用44 需要指出，影子价格不是固定不变的，当需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化时，有可能使约束条件、产品利润等发生变化时，有可能使影子价格发生变化。影子价格发生变化。4

28、-3影子价格影子价格 另外，影子价格的经济含义另一方面，是指另外，影子价格的经济含义另一方面，是指资源在一定范围内增加时的情况，当某种资源的资源在一定范围内增加时的情况，当某种资源的增加超过了这个增加超过了这个“一定的范围一定的范围”时，总利润的增时，总利润的增加量则不是按照影子价格给出的数值线性地增加。加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。这个问题还将在灵敏度分析一节中讨论。Operations Research2022-3-11本科适用本科适用45 在线性规划问题中，目标函数、约束在线性规划问题中，目标函数、约束条件的系数以及资源的限制量等都当作确

29、条件的系数以及资源的限制量等都当作确定的常数，并在这些系数值的基础上求得定的常数，并在这些系数值的基础上求得最优解。最优解。 但是，实际上这些系数或资源限制量并非但是，实际上这些系数或资源限制量并非是一成不变的，它们往往是一些估计和预是一成不变的，它们往往是一些估计和预测的数字。测的数字。4-44-4灵敏度分析灵敏度分析Operations Research2022-3-11本科适用本科适用46 市场经济条件下，价值系数随着市场的变化而变化市场经济条件下，价值系数随着市场的变化而变化 约束系数随工艺的变化或消耗定额的变化而变化，约束系数随工艺的变化或消耗定额的变化而变化， 计划期的资源限制量也

30、是经常变化的。计划期的资源限制量也是经常变化的。 当这些系数发生变化时，最优解会受到什么样当这些系数发生变化时，最优解会受到什么样的影响呢？最优解对哪些参数的变动最敏感？的影响呢？最优解对哪些参数的变动最敏感？ 搞清这些问题会使我们在处理实际问题时，具搞清这些问题会使我们在处理实际问题时，具有更大的主动性和可靠性。有更大的主动性和可靠性。 4-44-4灵敏度分析灵敏度分析Operations Research2022-3-11本科适用本科适用474-44-4灵敏度分析灵敏度分析v 确定线性规划模型的某些系数或限制参确定线性规划模型的某些系数或限制参数的变动对最优解的影响分析被称作数的变动对最优

31、解的影响分析被称作-灵敏灵敏度分析度分析。v Operations Research2022-3-11本科适用本科适用484-44-4灵敏度分析灵敏度分析v灵敏度分析主要解决两个问题：灵敏度分析主要解决两个问题：v （1）这些系数在什么范围内变化时，）这些系数在什么范围内变化时，v原求出的线性规划的最优解或最优基不变，原求出的线性规划的最优解或最优基不变，v即最优解相对参数变化的稳定性。即最优解相对参数变化的稳定性。v （2）如果系数的变化引起了最优解变化，）如果系数的变化引起了最优解变化，v如何用最简洁的方法求出新的最优解。如何用最简洁的方法求出新的最优解。Operations Resear

32、ch2022-3-11本科适用本科适用49c ci , b bj发生变化 本段重点 增加一约束或变量及A中元素发生变化通过例题学会处理 对于表格单纯形法，通过计算得到最优单纯形表。 应能够找到最优基 B B 的逆矩阵 B B-1 ， B B-1b b 以及 B B-1N N，检验数 j 等。4-4灵敏度分析灵敏度分析Operations Research2022-3-11本科适用本科适用504-44-4灵敏度分析灵敏度分析v1、目标函数中价值系数、目标函数中价值系数C的灵敏度分析的灵敏度分析v分非基变量和基变量的价值系数两种情况讨分非基变量和基变量的价值系数两种情况讨论。论。v1）设非基变量）

33、设非基变量 X j 的价值系数的价值系数C j 有增有增 量量 v其它参数不变，求其它参数不变，求jcjc的范围使原最优解不变的范围使原最优解不变Operations Research2022-3-11本科适用本科适用514-44-4灵敏度分析灵敏度分析v由于由于 C j 是非基变量的价值系数，因此它的是非基变量的价值系数，因此它的改变仅仅影响检验数改变仅仅影响检验数 的变化，而对其它的变化，而对其它检验数没有影响。设检验数没有影响。设v v v所以当所以当 j01jjjBjjjcPBCccjjc原最优解不变原最优解不变。Operations Research2022-3-11本科适用本科适用

34、52v即非基变量的价值系数 C Cj j 变化，只当 最优解不变；否则，将最优单纯形表中的检验数 4-44-4灵敏度分析灵敏度分析jjc取代用jj继续单纯形法的计算继续单纯形法的计算。 Operations Research2022-3-11本科适用本科适用53例3.3: Max z = -2x1 - 3x2 - 4x3 S.t. -x1-2x2-x3+x4 = - 3 -2x1+x2-3x3+x5 = - 4 x1 ,x2 ,x3 ,x4 ,x5 04-44-4灵敏度分析灵敏度分析Operations Research2022-3-11本科适用本科适用54 例例3.3：最优单纯形表：最优单纯

35、形表 4-44-4灵敏度分析灵敏度分析 假设假设 C C3 3的值有增量的值有增量 cc3 3 分析分析 c3 使最优解不变的范围使最优解不变的范围+c+c3 3+c+c3 3表中表中3 3= c= c3 3+c+c3 3-(c-(c2 2a a1313+c+c1 1a a23 23 ) ) = = -9/5+-9/5+c3 只要只要-9/5+-9/5+c3 0 ，即，即c3 9/5 9/5 则原最优解不变则原最优解不变Operations Research2022-3-11本科适用本科适用554-44-4灵敏度分析灵敏度分析v (2)设基变量 XB 的价值系数 CB 有增量 ，其它参数不变，

36、求使最优解不变。v 由于 CB是基变量的价值系数，因此它的变化将影响所有的非基变量的检验数的变化。v令 则 BrC00BrBBCCC100BCCBrBjjjPYcjBrjPBC1001BCYB100BCYBrjBrjPBCYc0010BrrjjCaOperations Research2022-3-11本科适用本科适用56下标为下标为r r的基变量价值系数有增量，的基变量价值系数有增量，只要使所有非基变量 则最优解不变 4-44-4灵敏度分析灵敏度分析rjBrjjaC即,00|min0|maxrjrjjBrrjrjjaaCaav是单纯形表中下标为是单纯形表中下标为 r的基变的基变量所在行的系数

37、。量所在行的系数。rja即使即使Operations Research2022-3-11本科适用本科适用57 若下标为若下标为 r r的基变量价值系数有增量，的基变量价值系数有增量，只要使所有非基变量 的检验数满足 原最优解不变；否则将最优单纯形表中的检验 继续单纯形法的表格计算。 4-44-4灵敏度分析灵敏度分析取代用jj0|min0|maxrjrjjBrrjrjjaaCaaOperations Research2022-3-11本科适用本科适用58例3.4: MaxMax z z = 2 = 2x x1 1 + 3 + 3x x2 2 + 0+ 0 x x3 3 + 0 + 0 x x4

38、4+ 0+ 0 x x5 5 s.t.s.t. x x1 1 + 2 + 2x x2 2 + + x x3 3 = 8= 8 4 4x x1 1 + + x x4 4 = 16 = 16 4 4x x2 2 + + x x5 5 = = 1212 x x1 1 , , x x2 2 , , x x3 3 , , x x4 4 , , x x5 5 0 04-44-4灵敏度分析灵敏度分析Operations Research2022-3-11本科适用本科适用594-44-4灵敏度分析灵敏度分析 例例: : 下表为最优单纯形表下表为最优单纯形表, ,考虑考虑c c2 2变化变化可得到 -3c21时

39、，原最优解不变+c+c2 2+c+c2 2-c-c2 2/ /2 2+c+c2 2/ /8 80|min0|maxrjrjjBrrjrjjaaCaa可直接用公式Operations Research2022-3-11本科适用本科适用604-44-4灵敏度分析灵敏度分析v 以上就两种情况讨论了 在什么范围内变动时，原最优解不变，如果 不在上述（下式给出）范围内变动，则一定会出现正的检验数，原最优解不再是最优解，以该解为初始解，用单纯形法继续迭代可以尽快地求出新的最优解 0|min0|maxrjrjjBrrjrjjaaCaajCjCjjc再举2-2例如下：Operations Research20

40、22-3-11本科适用本科适用61BCBXbB14321xxxx43xx12xxjC 6 4 0 0备注 0 0100120 2 3 1 0 4 2 0 1100/2120/4K=1L=2 6 4 0 0. . 4 62020j8/34/1014/12/110（1） 即即 是基变量的价值系数是基变量的价值系数4/52/100（1）求 的范围使原最优解不变2C（2）如 变为12，求新的最优解。 1C 用非基变量的检验数与单纯形表中基变量用非基变量的检验数与单纯形表中基变量X2所在行所在行相应的元素作比值得：相应的元素作比值得：51, 54/14/52/12/1122CC即（2）将）将 C1=12

41、 代入原最优表，重新求检验数，代入原最优表，重新求检验数，原最优解不再是最优解，用单纯形法继续迭代运算原最优解不再是最优解，用单纯形法继续迭代运算Operations Research2022-3-11本科适用本科适用62BCBXbB14321xxxx13xx12xxjC 12 4 0 0备注 4 122020 0 1 1/2 -1/4 1 0 -1/4 3/8 K=1L=20 0 1 -7/2 012j新的最优解为： 4/102/112/11203020，即为所求。最优值其余360, 0,304013zxxxj4030Operations Research2022-3-11本科适用本科适用6

42、34-44-4灵敏度分析灵敏度分析v2、资源系数、资源系数b的分析的分析 v设 有增量 ，其它参数不变，则v的变化将影响基变量所取的值，但是对于检验数没有影响。记：ibibibTibbb00 bBXB1iTmiiiBbBBBX11211001TibbBOperations Research2022-3-11本科适用本科适用644-44-4灵敏度分析灵敏度分析v2、资源系数、资源系数b的分析的分析 v如果变化后的基变量所取的数值仍大于或等如果变化后的基变量所取的数值仍大于或等于零，则原最优基不变，新的最优解就是：于零，则原最优基不变，新的最优解就是： iTmiiiBBbBBBXX11211iTm

43、iiiBTiBbBBBXbbBbBX112111100Operations Research2022-3-11本科适用本科适用654-44-4灵敏度分析灵敏度分析v那么 ，取何值能够保证 呢？v令v v时，原问题的最优基不变。v 是原最优逆阵的第i列。v结果说明 的变化是由基变量的相反值与 v 的第 i 列相应的元素比值所确定的。ib0BX011211iTmiiiBBbBBBXX0|)(min0|)(max111111kikikikikikBBbBbBBbBTmiiiBBB112111Bib当当Operations Research2022-3-11本科适用本科适用664-44-4灵敏度分析灵

44、敏度分析v 如果 不在上述范围内变动，则变化后的基变量 所取的值肯定会出现负分量，但由于 不影响检验数的变化，因此可以用 取 v代原有的 ，以该解为初始解，用对偶单纯形法继续求解。v例：例：已知线性规划问题的初始解及最优解上例v求：（1） 的范围使原最优基不变；v （2）若 变为200，求新的最优解。ibBXibBXBX1b1b幻灯片 58Operations Research2022-3-11本科适用本科适用674-44-4灵敏度分析灵敏度分析解：解：（1）由单纯形表可知用基变量的值与 第一列相应元素去比得： 原最优基不变。 20208/ 34/ 14/ 12/ 11BXB，1B80401b

45、（2）由于5701202008/ 34/ 14/ 12/ 11bBXB是非基可行解，用 替换原最优表中基变量的值，采用对偶单纯形法继续求解570BXOperations Research2022-3-11本科适用本科适用68BCBXbB14321xxxx32xx12xxjC 6 4 0 0备注 4 670-5 0 1 1/2 -1/4 1 0 -1/4 3/8 K=1L=20 0 -1 /2 -5/4 4 0j新的最优解为： 2/31042/10122002，即为所求。最优值其余240, 0,206032zxxxj6020Operations Research2022-3-11本科适用本科适用

46、69v3、系数矩阵、系数矩阵A的分析的分析v以下分4种情况讨论系数矩阵的变化： （1 1） 增加一个变量增加一个变量 增加变量 xn+1 则有相应的pn+1 ,cn+1 。 那么那么 计算出计算出B B-1-1p pn n+1 +1 , , n n+1+1= =c cn n+1+1-c cri ri a ariri n n+1+1 填入最优单纯形表。 若若 n+1 0 则则 最优解不变； 否则，否则，进一步用单纯形法求解。4-44-4灵敏度分析灵敏度分析Operations Research2022-3-11本科适用本科适用70例例3.6:3.6:例3.4增加x6 , p6=( 2, 6, 3

47、 )T, c6=5 计算得到Ci230005CBXBbX1X2X3X4X5X62 X141001/401.50 X5400-21/2123 X22011/2-1/800.25j00-1.5-1/801.25用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.54-44-4灵敏度分析灵敏度分析Operations Research2022-3-11本科适用本科适用71 （2 2）增加一个约束）增加一个约束 增加一个约束之后，应把最优解带入新的约束，若满足则最优解不变。 否则，将增加的约束填入最优单纯形表，否则，将增加的约束填入最优单纯形表，作为新的一行并引

48、入新的松弛变量或人工作为新的一行并引入新的松弛变量或人工变量构造单位阵；变量构造单位阵； 再通过矩阵行变换把该行对应其他基变量再通过矩阵行变换把该行对应其他基变量所在所在“列列”的元素变为的元素变为0 0； 进一步用单纯形法或对偶单纯形法求解。进一步用单纯形法或对偶单纯形法求解。4-44-4灵敏度分析灵敏度分析Operations Research2022-3-11本科适用本科适用72例例3.7:3.7:例3.4增加3x1+ 2x215，原最优解不满足这个约束。于是Ci 2 3 0 0 0 0 CB XB b X1 X2 X3 X4 X5 X6 2 X1 4 1 0 0 1/4 0 0 0 X5 4 0 0 -2 1/2