运筹学对偶规划与灵敏度分析

1、1第第3 3章章线性规划问题的线性规划问题的对偶与灵敏度分析对偶与灵敏度分析2本章内容重点本章内容重点 线性规划的对偶问题的概线性规划的对偶问题的概念、理论及经济意义念、理论及经济意义 线性规划的对偶单纯形法线性规划的对偶单纯形法 线性规划的灵敏度分析线性规划的灵敏度分析33.1.1 对偶问题的提出：对偶问题的提出： 若第二章例若第二章例2.1问题的设备都用于问题的设备都用于外协加工，工厂收取加工费。试问：外协加工，工厂收取加工费。试问：设备设备 A、B、C 每工时各如何收费每工时各如何收费才最有竞争力？才最有竞争力？ 设设 y1 ，y2 ，y3 分别为每工时设备分别为每工时设备 A、B、C

2、的收取费用。的收取费用。3.1 3.1 线性规划对偶问题线性规划对偶问题3.1 线性规划对偶问题线性规划对偶问题例例2.1:某工厂拥有某工厂拥有A、B、C三种类型的设备，三种类型的设备，生产甲、乙两种产品。每件产品在生产中生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润/（元/件/p>

3、025005Max z = 1500 x1 + 2500 x2 原问题原问题s.t. 3x1 + 2x2 65 2x1 + x2 40 3x2 75 x1 , x2 0Min f = 65y1+ 40y2 + 75y3 对偶问题对偶问题s.t. 3y1+2y2 1500 （不少于甲产品的利润）（不少于甲产品的利润） 2y1+y2+3y3 2500（不少于乙产品的利润）（不少于乙产品的利润） y1, y2 , y3 063.1.2 对偶规划的形式对偶规划的形式 有有对称形式对称形式和和非对称形式非对称形式。 对称形式对称形式的对偶规划之间具有下面的的对偶规划之间具有下面的对应关系：对应关系： (

4、1) 若一个模型为目标求若一个模型为目标求“极大极大”，约，约束为束为“小于等于小于等于”的不等式，则它的的不等式，则它的对偶模型为目标求对偶模型为目标求“极小极小”，约束是，约束是“大于等于大于等于”的不等式。即的不等式。即 “max，” 和和 “min，” 相对应。相对应。7(2) 从约束系数矩阵看：一个模型中从约束系数矩阵看：一个模型中为为，则另一个模型中为，则另一个模型中为AT。一个。一个模型是模型是m个约束，个约束，n个变量，则它的个变量，则它的对偶模型为对偶模型为n个约束，个约束，m个变量。个变量。(3) 从数据从数据b、C的位置看：在两个规的位置看：在两个规划模型中，划模型中，b

5、和和C的位置对换。的位置对换。(4) 两个规划模型中的变量皆非负。两个规划模型中的变量皆非负。8 对称形式：对称形式： 互为对偶互为对偶 (LP) Max z = cT x (DP) Min f = bT y s.t. Ax b s.t. AT y c x 0 y 0 “Max - ” “Min- ”9 非对称形式非对称形式的对偶规划的对偶规划: :对非对称形式，对非对称形式，可以按照下面的对应关系直接给出其对偶规划可以按照下面的对应关系直接给出其对偶规划(1) 将模型统一为将模型统一为“max，”或或“min，” 的形式，对于其中的等式约束按的形式，对于其中的等式约束按下面下面(2)、(3)

6、中的方法处理；中的方法处理；(2) 若原规划的某个约束条件为等式约若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；那个变量取值没有非负限制；(3) 若原规划的某个变量的值没有非负若原规划的某个变量的值没有非负限制，则在对偶问题中与此变量对应限制，则在对偶问题中与此变量对应的那个约束为等式。的那个约束为等式。10 下面对关系下面对关系(2)作一说明。对于关系作一说明。对于关系(3)可以给出类似的解释：可以给出类似的解释： 设原规划中第一个约束为等式：设原规划中第一个约束为等式： a11x1 + + a1nxn = b1 那么

7、，它与下面两个不等式等价那么，它与下面两个不等式等价1111111111.bxaxabxaxannnn 11 mjxbxaxabxaxabxaxaxcxcZjmnmnmnnnnnn,2, 1,0max11111111111111原规划模型可以写成原规划模型可以写成12 这里，把这里，把y1看作是看作是 y1 =y1 - y1，于是于是y1没有非负限制。没有非负限制。 没有非负限制没有非负限制121111112211211211111111221111, 0, , minyyyyycyayayacyayayacyayayaybybybybfmnmmnnnmmmmmm转化为对称形式，直接写出对偶规

8、划转化为对称形式，直接写出对偶规划13例例 写出下面线性规划的对偶规划模型写出下面线性规划的对偶规划模型 没没有有非非负负限限制制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ14解解 先将约束条件变形为先将约束条件变形为“”形式形式 没没有有非非负负限限制制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx15根据非对称形式的对应关系，直接写根据非对称形式的对应关系，直接写出对偶规划出对偶规划 0,725472123122510306025min543215

9、4213213132154321yyyyyyyyyyyyyyyyyyyyyyf没有非负限制没有非负限制16定理定理3-1 (弱对偶定理）弱对偶定理） 若若X和和Y分别为原规划（分别为原规划（P）和对偶规划（和对偶规划（D）的可行解，那）的可行解，那么么cTx bTy。推论推论1 设设X0和和Y0分别为原规划分别为原规划（P）和对偶规划（）和对偶规划（D）的可行解，）的可行解，当当CTX0=bTY0时，时，X0、Y0分别是分别是两个问题的最优解。两个问题的最优解。3.1.3 3.1.3 线性规划对偶问题线性规划对偶问题17推论推论2 若规划（若规划（P）有可行解，则（）有可行解，则（P）有最优解

10、的充分必要条件是规划（有最优解的充分必要条件是规划（D）有可行解。有可行解。推论推论3 若规划（若规划（D）有可行解，则（）有可行解，则（D）有最优解的充分必要条件是规划（有最优解的充分必要条件是规划（P）有可行解。有可行解。定理定理 3.2 若原规划（若原规划（P）有最优解，则）有最优解，则对偶规划（对偶规划（D）也有最优解，反之亦）也有最优解，反之亦然。并且两者的然。并且两者的目标函数值相等目标函数值相等若（若（P）、）、(D)都有可行解都有可行解 二者二者都有最优解。都有最优解。（P）(D)其中之一有最优解其中之一有最优解 另另一个也有最优解。一个也有最优解。一个有可行解，一个无可行解一

11、个有可行解，一个无可行解 二者都无最优解。二者都无最优解。19例例 求解下面线性规划问题，并根求解下面线性规划问题，并根据最优单纯形表中的检验数，给据最优单纯形表中的检验数，给出其对偶问题的最优解。出其对偶问题的最优解。 0,1003310022734max321321321321xxxxxxxxxxxxz20解得最优单纯形表解得最优单纯形表 最优解为最优解为(0, 25, 25)T，最优值为，最优值为250。表中松弛变量的检验数分别为表中松弛变量的检验数分别为-0.5，-2，可以验证可以验证(0.5, 2)T为对偶规划的最优解。为对偶规划的最优解。 x1x2x3x4x5-0.75100.75

12、-0.51.2501-0.250.5-2.500-0.5-2cBxB3x2257x325-z-2504370021 可以用下面方法验证的对偶最优性。可以用下面方法验证的对偶最优性。原规划的对偶规划为原规划的对偶规划为 0,7323243.100100min2121212121yyyyyyyytsyyf(1/2,2)T为对偶可行解，并且目标值为为对偶可行解，并且目标值为f =250由定理由定理3.1的推论的推论1可以判断可以判断(1/2,2)T为对偶问为对偶问题的最优解。题的最优解。22 从本例的结论可以看到，对从本例的结论可以看到，对偶规划的最优解可以在原规划的偶规划的最优解可以在原规划的最优

13、解的检验数中得到，最优解的检验数中得到，原规划原规划最优解的检验数最优解的检验数 的后的后m个分量个分量（松弛变量对应的检验数）的负（松弛变量对应的检验数）的负值，为对偶规划的最优解值，为对偶规划的最优解。对偶规划的最优解又称对偶规划的最优解又称231 1影子价格的概念影子价格的概念考虑互为对偶的线性规划考虑互为对偶的线性规划(P)(P)，(D)(D)设设y*=（y1*,，ym*)T为对偶规划为对偶规划(D)(D)的最优解，的最优解，则则yi* *称为规划称为规划(P)(P)第第i个个约束对应的影子价格约束对应的影子价格( (shadow Price) )。3.1.4 影子价格影子价格24影子

14、价格的经济含义影子价格的经济含义(1) 影子价格是对现有资源实现最大效影子价格是对现有资源实现最大效益时的一种估价益时的一种估价 企业可以根据现有资源的影子价格，企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于设备设备用于外加工或出租，若租费高于设备的影子价格，可考虑出租设备，否则不宜的影子价格，可考虑出租设备，否则不宜出租。第二，是否将投资用于购买设备，出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买子价格，可

15、考虑买进该设备，否则不宜买进进。253.1.4 3.1.4 影子价格影子价格 (2) 影子价格表明资源增加对总效益产影子价格表明资源增加对总效益产生的影响。生的影响。 根据推论，在最优解的根据推论，在最优解的情况下，有情况下，有 因此，可以将因此，可以将z* *看作是看作是bi的函数，的函数，对对bi求偏导数可得到求偏导数可得到 这说明，如果右端常数增加一个这说明，如果右端常数增加一个单位，则目标函数值的增量将是单位，则目标函数值的增量将是y* *. .*22*11*mmybybybfz miybzii, 2 , 1,* 26 影子价格反映了不同的局部影子价格反映了不同的局部或个体的增量可以获

16、得不同的整或个体的增量可以获得不同的整体经济效益。如果为了扩大生产体经济效益。如果为了扩大生产能力，能力，考虑增加设备，就应该从考虑增加设备，就应该从影子价格高的设备入手。影子价格高的设备入手。这样可这样可以用较少的局部努力，获得较大以用较少的局部努力，获得较大的整体效益。的整体效益。 需要指出，影子价格不是固定不变需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，时，有可能使影子价格发生变化。另外，影子价格的经济含义是指资源在一定范影子价格的经济含义是指资源在一定范围内增加时的情况围内增加时的情况，当某种资源

17、的增加，当某种资源的增加超过了这个超过了这个“一定的范围一定的范围”时，总利润时，总利润的增加量则不是按照影子价格给出的数的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在灵敏度值线性地增加。这个问题还将在灵敏度分析一节中讨论。分析一节中讨论。283.2 对偶单纯形法对偶单纯形法3.2.1 3.2.1 对偶单纯形法的基本思想对偶单纯形法的基本思想 从原规划的一个从原规划的一个对偶可行基本对偶可行基本解解（检验数非正）出发，然后检验（检验数非正）出发，然后检验原规划的原规划的基本解基本解是否可行，即是否是否可行，即是否非负。如果有小于零的分量，则进非负。如果有小于零的分量，则进行迭代

18、，求另一个行迭代，求另一个基本解基本解（保持检（保持检验数非正）。验数非正）。偶单纯形法的适用范围偶单纯形法的适用范围 对偶单纯形法适合于解如下形式的线对偶单纯形法适合于解如下形式的线性规划问题：性规划问题：njxmibxacxcfjnjijijnjjjj, 2 , 1, 0, 2 , 10min11301. 建立初始对偶单纯形表建立初始对偶单纯形表, 对应一个基本解对应一个基本解,所有检验数均非正所有检验数均非正, 转转2；2. 若若 b0, 则得到最优解则得到最优解, 停止停止;否则否则, 若有若有bk0, 则选则选k行的基变量为出基变量行的基变量为出基变量, 转转33. 若所有若所有ak

19、j0( j = 1,2,n )，则原问题无可，则原问题无可行解行解, 停止停止; 否则否则, 若有若有akj0, 则选则选 =min j / akjakj0= r/akr那么那么, xr为进基变量为进基变量,转转4；4. 以以akr为转轴元为转轴元, 作矩阵行变换使其变为作矩阵行变换使其变为1, 该列其他元变为该列其他元变为0, 转转2。3.2.2 对偶单纯形法主要步骤：对偶单纯形法主要步骤：31例例 求解线性规划问题：求解线性规划问题： Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4 x1 , x2 , x3 0解：解

20、： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1- 2x2-x3+x4 = -3 -2x1+x2-3x3 +x5= -4 x1,x2,x3,x4,x5 0表格对偶单纯形法表格对偶单纯形法最优解为最优解为: x = ( 2.2, 0.4, 0, 0, 0 )T , z = -5.6最优值最优值 f = 5.6无可行解情况无可行解情况 线性规划问题可能出现不存在可线性规划问题可能出现不存在可行解的情况，这时，在对偶单纯形表行解的情况，这时，在对偶单纯形表中显示矛盾方程。中显示矛盾方程。例例 Max z = x1 3x2 2x3 s.t. x1 + 2x2 + 3x3 + x

21、4 = -10 2x1 + x2 + 5x3 + x5 = 20 3x1 + 2x2 - x3 + x6 = -12 x1 , x2 , x3 , x4 , x5 , x6 0对偶单纯形表对偶单纯形表表中第表中第1行反映了一个矛盾约束：行反映了一个矛盾约束： x1 + 2x2 + 3x3 + x4 = -10 即，若所有即，若所有akj0( j = 1,n )，则原问，则原问题无可行解题无可行解,停止停止;是是是是是是是是否否否否否否否否所有所有所有所有得到得到最优解最优解计算计算计算计算典式对应原规划的典式对应原规划的基本解是可行的基本解是可行的典式对应原规划的基典式对应原规划的基本解的检验

22、数本解的检验数所有所有所有所有计算计算计算计算以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代以为中心元素进行迭代停停没没有有最最优优解解没没有有最最优优解解单纯形法单纯形法对偶单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min比较比较0 csMin j/asj asj0 br Min-bi/air air050上例最优单纯形表如下上例最优单纯形表如下 例例51 0 1/4 0 0 1/4 0 这里这里 B B-1 -1 = -2 1/2 1 = -2 1/2 1 1/2 -1/8 0 1

23、/2 -1/8 0 各列分别对应各列分别对应 b1、b2、b3 的单一变化的单一变化因此，设因此，设 b1 增加增加 4，则，则 x1 , x5 , x2分别变为：分别变为：4+04=4, 4+(-2)4=-40, 2+ 1/21/2 4=4用对偶单纯形法进一步求解，可得：用对偶单纯形法进一步求解，可得：52于是，于是，x* = ( 4, 3, 2, 0, 0 )T f* = 1753 讨论保持最优基不变的前提下，讨论保持最优基不变的前提下， b2的允许变化范围的允许变化范围 4 + b2 0.25 0 b2 -16 4 + b2 0.5 0 b2 -8 2 + b2 (- 0.125) 0

24、b2 16于是于是 -8 b2 16例题：例题：某厂生产甲、乙、丙三种产品，分别经过某厂生产甲、乙、丙三种产品，分别经过、三种设备加工。已知生产单位产品所需的、三种设备加工。已知生产单位产品所需的设备台时数、设备的现有加工能力及每件产品的利设备台时数、设备的现有加工能力及每件产品的利润见下页表，求：润见下页表，求：(1) (1) 产品丙利润增加到多大时才值得安排生产？如产品丙利润增加到多大时才值得安排生产？如产品丙每件的利润增加到产品丙每件的利润增加到50/6 50/6 ，求最优生产计划，求最优生产计划。(2) (2) 产品甲的利润在多大范围内变化时，原最优计产品甲的利润在多大范围内变化时，原

25、最优计划保持不变？划保持不变？(3) (3) 设备设备A A的能力如为的能力如为100+10100+10 ，确定保持原最优，确定保持原最优基不变的基不变的 的变化范围。的变化范围。(4) (4) 如有一种新产品丁，加工一件需设备如有一种新产品丁，加工一件需设备A A、B B、C C的台时各为的台时各为1 1、4 4、3 3小时，预期每件的利润为小时，预期每件的利润为8 8元，元，是否值得安排生产？是否值得安排生产？(5) (5) 如合同规定该厂至少生产如合同规定该厂至少生产1010件产品丙，试确定件产品丙，试确定最优计划的变化。最优计划的变化。 甲甲乙乙丙丙设备能力（设备能力（台时）台时）10

26、100100600600300300单位产品利单位产品利润（元）润（元）10最优单纯形表最优单纯形表1064000cBxBx1x2x3x4x5x66x2200/3015/65/3-1/6010 x1100/3101/6-2/31/600 x6100004-01-zj-2200/300-8/3 -10/3 -2/30参考解答参考解答(1) 3 = -8/3 +c30, 故故c38/3，即当产品丙即当产品丙的利润大于的利润大于20/3（48/3）时，值得安排生产；）时，值得安排生产； 如产品丙每件的利润增加到如产品丙每件的利润增加到50/650/6，则，则最优生产计划最优生产计划 x* = 175

27、/6, 275/6, 25。(2) - 4 c1 5，即，即产品甲的利润产品甲的利润 6 c1 1 5时，原最优计划保持不变。时，原最优计划保持不变。(3) 当当 - 4 5，保持原最优基不变。保持原最优基不变。(4) 新产品丁值得安排生产。新产品丁值得安排生产。(5) 如合同规定该厂至少生产如合同规定该厂至少生产1010件产品丙，则件产品丙，则最优计划为最优计划为 x* = 95/3, 175/3, 10 。 59增加变量增加变量 xn+1, 相应有相应有pn+1, cn+1 。 可计算出可计算出 B-1pn+1, n+1=cn+1-cri ari n+1 填入最优单纯形表：填入最优单纯形表

28、： 若若 n+1 0 则则 最优解不变；最优解不变； 否则，进一步用单纯形法求解。否则，进一步用单纯形法求解。3.3.4 增加新变量分析增加新变量分析60例例 对前例，增加对前例，增加x6 , p6=( 2, 6, 3 )T, c6=5用单纯形法进一步求解，可得：用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5666616pcc,pBpTB 61 首先，应把最优解代入新的约束首先，应把最优解代入新的约束 若满足，则最优解不变，停止；若满足，则最优解不变，停止； 否则，引入一个新的非负变量（否则，引入一个新的非负变量（原约原约束若是束若是小于等于形式

29、可引入非负松弛变量，否则引小于等于形式可引入非负松弛变量，否则引入非负人工变量入非负人工变量），填入最优单纯形表作），填入最优单纯形表作为新的一行，并通过矩阵行变换把为新的一行，并通过矩阵行变换把对应对应基中的列向量变为单位向量基中的列向量变为单位向量。 进一步用对偶单纯形法求解。进一步用对偶单纯形法求解。3.3.5 增加一个约束条件增加一个约束条件62例例 上例增加上例增加 3x1+ 2x2 15，原最优解不，原最优解不满足这个约束。于是满足这个约束。于是 对表中新的一行利用矩阵初等行变对表中新的一行利用矩阵初等行变换进行处理，可得新的对偶单纯形表：换进行处理，可得新的对偶单纯形表：63经对

30、偶单纯形法一步，可得最优解为经对偶单纯形法一步，可得最优解为（3.5, 2.25, 0, 0, 3, 2 )T，最优值为最优值为 13. 75 64(只讨论只讨论 N 中某一列变化情况）中某一列变化情况） 与增加变量与增加变量 xn+1 的情况类似，的情况类似，假设假设 pj 变化变化 。那么，重新计算出。那么，重新计算出 pj=B-1pj j = cj - cri ari j 填入最优单纯形表，若填入最优单纯形表，若 j 0 则最则最 优解不变；否则，进一步用单纯形优解不变；否则，进一步用单纯形法求解。（例子从略）法求解。（例子从略）3.3.6 A中元素发生变化中元素发生变化 作业作业P80

31、-3.1(3); P81-3.7(1);P82- 3.10线性规划应用与线性规划应用与计算机解题计算机解题6667线性规划的计算机求解线性规划的计算机求解介绍小型的运筹学教学软件：介绍小型的运筹学教学软件： MS60用用ExcelExcel求解线性规划求解线性规划68线性规划问题的计算机求解线性规划问题的计算机求解(Excel)决策变量决策变量 x1 x2 1 1目标函数目标函数 c1 c2 f 50 100 150约束矩阵约束矩阵 Aij sum b 1 1 2 300 2 1 3 400 0 1 1 25069线性规划问题的计算机求解线性规划问题的计算机求解(Excel)(Excel)运算

32、结果报告运算结果报告目标单元格目标单元格 ( (最大值最大值) ) 单元格单元格 名字名字 初值初值 终值终值 $E$5 f 150 27500可变单元格可变单元格 单元格单元格 名字名字 初值初值 终值终值 $B$2 x1 1 50 $C$2 x2 1 250约束约束 单元格单元格 名字名字 单元格值单元格值 公式公式 状态状态 型数值型数值 $D$8 sum 300 $D$8=$E$8 $D$8 sum 300 $D$8=$E$8 到达限制值到达限制值 0 0 $D$9 sum 350 $D$9=$E$9 $D$9 sum 350 $D$9=$E$9 未到限制值未到限制值 5050 $D$

33、10 sum 250 $D$10=$E$10 $D$10 sum 250 $D$10=0 $B$2 x1 50 $B$2=0 未到限制值未到限制值 5050 $C$2 x2 250 $C$2=0 $C$2 x2 250 $C$2=0 未到限制值未到限制值 25025070线性规划问题的计算机求解线性规划问题的计算机求解(Excel)敏感性报告敏感性报告可变单元格可变单元格单元格单元格 名字名字 终值终值 递减成本递减成本 目标式系数目标式系数 允许的增量允许的增量 允许的减量允许的减量$B$2 x1 50 0 50 50 50$B$2 x1 50 0 50 50 50$C$2 x2 250 0

34、 100 1E+30 50$C$2 x2 250 0 100 1E+30 50约束约束单元格单元格 名字名字 终值终值 阴影约束阴影约束 约束限制值约束限制值 允许的增量允许的增量 允许的减量允许的减量$D$8 sum 300 50 300 25 50$D$8 sum 300 50 300 25 50$D$9 sum 350 0 400 1E+30 50$D$9 sum 350 0 400 1E+30 50$D$10 sum 250 50 250 50 50$D$10 sum 250 50 250 50 5071结果考察：结果考察：1、当目标函数的系数、当目标函数的系数 ci 单一变化时，单一

35、变化时，只要不超过其上、下限，基不变，即只要不超过其上、下限，基不变，即最优解不变；最优解不变；2、当约束条件中右边系数、当约束条件中右边系数 bj 变化时，变化时，当其不超过上、下限，基不变，即对当其不超过上、下限，基不变，即对偶价格不变解；偶价格不变解； 3、当有多个系数变化时，需要进一步、当有多个系数变化时，需要进一步讨论。讨论。72百分之一百法则百分之一百法则 对于所有变化的目标函数决策对于所有变化的目标函数决策系数（约束条件右边常数值），当系数（约束条件右边常数值），当其所有允许增加的百分比与允许减其所有允许增加的百分比与允许减少的百分比之和不超过少的百分比之和不超过100%100%

36、时，最时，最优解不变（对偶价格不变），即最优解不变（对偶价格不变），即最优基不变。优基不变。73 允许增加量允许增加量 = 上限上限 - 现在值现在值 例例 c1 的允许增加量为的允许增加量为 100 - 50 = 50 b1 的允许增加量为的允许增加量为 325 - 300 = 25 允许减少量允许减少量 = 现在值现在值 - 下限下限 例例 c2 的允许减少量为的允许减少量为 100 - 50 = 50 b3 的允许减少量为的允许减少量为 250 - 200 = 50 允许增加的百分比允许增加的百分比 = 增加量增加量 / 允许增加量允许增加量 允许减少的百分比允许减少的百分比 = 减少量

37、减少量 / 允许减少量允许减少量 示例说明示例说明74示例说明示例说明-续续 c1 变为变为 74 , c2 变为变为 78, 则则 (74 - 50)/50 + (100 - 78 )/50 = 92%，故最优解不变。故最优解不变。 b1 变为变为 315 , b3 变为变为 240, 则则 (315-300)/25+(250-240)/50 = 80%，故对偶价格不变故对偶价格不变（最优基不变）（最优基不变）。751）当允许增加量（允许减少量）为无穷）当允许增加量（允许减少量）为无穷大时，则对任意增加量（减少量），其允大时，则对任意增加量（减少量），其允许增加（减少）百分比均看作许增加（减

38、少）百分比均看作0；2）百分之一百法则是充分条件，但非必）百分之一百法则是充分条件，但非必要条件；要条件；3）百分之一百法则不能用于目标函数决）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变策变量系数和约束条件右边常数值同时变化的情况。这种情况下，只有重新求解。化的情况。这种情况下，只有重新求解。百分之一百法则的要点：百分之一百法则的要点：762.2 线性规划应用线性规划应用 线性规划应用很广，有线性规划应用很广，有一些典型的问题可归类为线一些典型的问题可归类为线性规划性规划问题：问题： 某企业生产某企业生产 3种产品甲、乙、丙，种产品甲、乙、丙，生产受到的约束为原料生产受到的约束为原料A、B、C、D的的限制，分别为限制，分别为 630 吨、吨、600 吨、吨、728 吨、吨、270 吨。生产每吨产品对各原料吨。生产每吨产品对各原料 A、B、C、D的消耗吨数为：的