§3 图解法的灵敏度分析
线性规划的标准化
? 一般形式
目标函数： Max （Min） z = c1 x1 + c2 x2 + … + cn xn
约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn ≤ （ =, ≥ ）b1 a21 x1 + a22 x2 + … + a2n xn ≤ （ =, ≥ ）b2 …… ……
am1 x1 + am2 x2 + … + amn xn ≤ （ =, ≥ ）bm x1 ，x2 ，… ，xn ≥ 0 ? 标准形式
目标函数： Max z = c1 x1 + c2 x2 + … + cn xn
约束条件： s.t. a11 x1 + a12 x2 + … + a1n xn = b1 a21 x1 + a 22 x 2 + … + a……
2n xn …… = b 2 am1 x1 + am2 x2 + … + amn xn = bm x1 ，x2 ，… ，xn ≥ 0，bi ≥0
可以看出，线性规划的标准形式有如下四个特点：
– 目标最大化； – 约束为等式； – 决策变量均非负； – 右端项非负。
对于各种非标准形式的线性规划问题，我们总可
以通过以下变换，将其转化为标准形式: 1.极小化目标函数的问题： 设目标函数为
Min f = c1x1 + c2x2 + … + cnxn (可以)令 z ＝ -f ，
则该极小化问题与下面的极大化问题有相同的最优解， 即 Max z = - c1x1 - c2x2 - … - cnxn
但必须注意，尽管以上两个问题的最优解相同，但它们 最优解的目标函数值却相差一个符号，即 Min f ＝ - Max z 2、约束条件不是等式的问题： 设约束条件为
ai1 x1+ai2 x2+ … +ain xn ≤ bi 可以引进一个新的变量s ，使它等于约束右边与左边之差 s=bi–(ai1 x1 + ai2 x2 + … + ain xn ) 显然，s 也具有非负约束，即s≥0，
11
这时新的约束条件成为
ai1 x1+ai2 x2+ … +ain xn+s = bi 当约束条件为
ai1 x1+ai2 x2+ … +ain xn ≥ bi 时， 类似地令
s=(ai1 x1+ai2 x2+ … +ain xn)- bi
显然，s 也具有非负约束，即s≥0，这时新的约束条件成为 ai1 x1+ai2 x2+ … +ain xn-s = bi 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为―松弛变量‖；当不等式为“大于等于”时称为―剩余变量‖。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量。
例：将以下线性规划问题转化为标准形式 Min f = 2 x1 -3x2 + 4 x3 s.t. 3 x1 + 4x2 - 5 x3 ≤6
2 x1 + x3 ≥8 x1 + x2 + x3 = -9 x1 , x2 , x3 ≥ 0
解：首先,将目标函数转换成极大化： 令 z= -f = -2x1+3x2-4x3
其次考虑约束，有2个不等式约束，引进松弛变量 x4，x5 ≥0。
第三个约束条件的右端值为负，在等式两边同时乘-1。
通过以上变换，可以得到以下标准形式的线性规划问题： Max z = - 2x1 + 3 x2 - 4x3 s.t. 3x1+4x2-5x3 +x4 = 6 2x1 +x3 -x5= 8 -x1 -x2 -x3 = 9 x1 ,x2 ,x3 ,x4 ,x5 ≥ 0 *** 变量无符号限制的问题***：
在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没 有非负约束时，可以令 xj = xj’- xj” 其中
xj’≥0，xj”≥0
即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。
12
§3 图解法的灵敏度分析
灵敏度分析：建立数学模型和求得最优解后，研究线性规划的一个或多个参数（系数）
ci , aij , bj 变化时，对最优解产生的影响。 3.1 目标函数中的系数 ci 的灵敏度分析
考虑例1的情况， ci 的变化只影响目标函数等值线的斜率，目标函数 z = 50 x1 + 100 x2
原 在 z = x2 (x2 = z 斜率为0 ) 到 z = x1 + x2 (x2 = -x1 + z 斜率为 -1 )之间时，
最优解 x1 = 50，x2 = 100 仍是最优解。 ? 一般情况：
z = c1 x1 + c2 x2 写成斜截式 x2 = - (c1 / c2 ) x1 + z / c2 目标函数等值线的斜率为 - (c1 / c2 ) ，
当 -1 ? - (c1 / c2 ) ? 0 （*） 时，原最优解仍是最优解。 ? 假设产品Ⅱ的利润100元不变，即 c2 = 100，代到式（*）并整理得 0 ? c1 ? 100
? 假设产品Ⅰ的利润 50 元不变，即 c1 = 50 ，代到式（*）并整理得 50 ? c2 ? + ? ? 假若产品Ⅰ、Ⅱ的利润均改变，则可直接用式（*）来判断。 ? 假设产品Ⅰ、Ⅱ的利润分别为60元、55元，则
- 2 ? - (60 / 55) ? - 1 那么，最优解为 z = x1 + x2 和 z = 2 x1 + x2 的交点 x1 = 100，x2 = 200 。
3.2 约束条件中右边系数 bj 的灵敏度分析
当约束条件中右边系数 bj 变化时，线性规划的可行域发生 变化，可能引起最优解的变化。 考虑例1的情况：
假设设备台时增加10个台时，即 b1变化为310，这时可行
域扩大，最优解为 x2 = 250 和 x1 + x2 = 310 的交点 x1 = 60，x2 = 250 。 变化后的总利润 - 变化前的总利润 = 增加的利润
(50×60+ 100×250) - (50 × 50+100 × 250) = 500 ，500 / 10 = 50 元
说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。
假设原料 A 增加10 千克时，即 b2变化为410，这时可行域扩大，但最优解仍为 x2
= 250 和 x1 + x2 = 300 的交点 x1 = 50，x2 = 250 。此变化对总利润无影响，该约束条件的对偶价格为 0 。 解释：原最优解没有把原料 A 用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。
在一定范围内，当约束条件右边常数增加1个单位时
（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）； （2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）； （3）若约束条件的对偶价格等于0，则最优目标函数值不变。
13
第三章 线性规划问题的计算机求解
§1 “管理运筹学”软件的操作方法 §2 “管理运筹学”软件的输出信息分析
随书软件为―管理运筹学‖2.0版（Window版），是1.0版（DOS版）的升级版。它包括：线性规划、运输问题、整数规划（0-1整数规划、纯整数规划和混合整数规划）、目标规划、对策论、最短路径、最小生成树、最大流量、最小费用最大流、关键路径、存储论、排队论、决策分析、预测问题和层次分析法，共15个子模块。
§1 “管理运筹学”软件的操作方法
1.软件使用演示：（演示例1）
第一步：点击“开始”->“程序”-> “管理运筹学 2.0”，弹出主窗口。
例1.目标函数：
Max z = 50 x1 + 100 x2 约束条件： s.t.
x1 + x2 ≤ 300 (A) 2 x1 + x2 ≤ 400 (B) x2 ≤ 250 (C) x1 ≥ 0 (D) x2 ≥ 0 (E)
第二步：选择所需子模块，点击主窗口中的相应按钮。本题中选用“线性规划”方 法。点击按钮弹出如下界面：
14
第三步：点击“新建”按钮，输入数据。本题中共有2个变量，4个约束条件，目标函 数取MAX。点击“确定”后，在表中输入Cj,bi和aij等值，并确定变量的正负约束。 输入数值后的界面如下。
第四步：点击“解决”按钮，得出计算结果。本题的运行结果界面如下。
15