对运筹学课程中百分之一百法则的进一步思考

陈士成，何丽红，李桥兴，罗云中

（兰州大学 管理学院，甘肃 兰州 730000）

对运筹学课程中百分之一百法则的进一步思考

陈士成，何丽红，李桥兴，罗云中

（兰州大学 管理学院，甘肃 兰州 730000）

目前，运筹学课程的线性规划灵敏度分析的表述中，都只给出了判断条件不超过100%时，决策方案中的关键决策量不会改变，而超过100%时就不能确定关键决策量是否会发生改变，只能重新求解。在教学过程中，师生都认为这种表述不尽完整，若能对判断值超过100%时也能更明晰的表述，可更进一步提高决策方法的可操作性。为此，我们总结了一部分判断条件超过了100%，但决策方案中的关键决策量仍然不会改变。补充了原百分一百法则的表述。

运筹学课程；线性规划；百分之一百法则

一、问题的提出

运筹学课程的线性规划灵敏度分析中，有两个百分之一百法则：对多个价值系数同时变化判断最优解是否变化的百分之一百法则；以及对多个常数项同时变化判断对偶价格是否变化的百分之一百法则。这两个判断法则的具体表述为[1，2]：

定理1.1如果多个价值系数（cj）同时变动，计算出每一个系数变动量占该系数允许变动量（允许增加量或允许增加量）的百分比，然后将各个系数的变动百分比相加，所得的和不超过100%，则最优解不会改变；如果超过100%，则不能确定原最优解（xj）是否改变，只能通过重新进行规划求解来判断。

定理1.2如果多个常数项（bi）同时变动，计算出每一个常数项变动量占该常数项允许变动量（允许增加量或允许增加量）的百分比，如果所有常数项的变动百分比之和不超过100%，则对偶然价格（di）不会改变（仍然有效）；如果所有变动百分比之和超过了100%，那就无法确定原对偶价格是否效，只能通过重新进行规划求解来判断。

在上述定理所给出的判断准则中，只给出了判断值不超100%的充分条件，而当百分比之和超过100%时，就无法确定最优解或对偶价格是否会发生变化，只能重新求解才能得知具体值。而在笔者多年的教学过程中，对线性规划应用做了多方面研究[3，4]，同时我们发现在线性规划模型求解的灵敏度分析讨论中，确实存在百分比之和超过100%但可以确定原最优解或原对偶价格不变的条件。由此，本文给出如下结论。

二、百分之一百法则的补充

定理2若多个价值系数（cj）按当前值同比例增减，不论百分比之和是否超过100%，则最优解（xj）一定不变。

证明：假设一般线性规划模型如下所示：

假设cj同比例增加（或减少）p%，则目标函数可以改写为：max（min） z’=（1±p%）（clxl+c2x2+…+cnxn），因为p%为正数，为不改变目标函数值的正负数属性，暂设减少的比例p%＜1。这时max（min） z’必然与max（min） z同解，所以，最优解不变。

定理3若多个常数项（bi）按当前值同比例增减，不论百分比之和是否超过100%，则对偶价格（di）一定不变。

证明：在由线性规划数学模型的约束条件构成的可行域中，若各约束条件的常数项同比例增减，可使可行域的每个边界同比例扩张或收缩，无论改变量有多大，都始终使可行域发生相似形的变化，因此只改变形状，不会改变可行域的结构。根据对偶价格变化的判定条件（可行域的结构改变导致对偶价格改变，可行域形状变化不会影响对偶价格）[2]。所以原对偶价格不会发生改变。

三、实例验证

假设某厂利用2种原料A、B生产甲、乙、丙3种产品，生产单位产品所需原料数（公斤）、单位利润（元/单位）及有关数据如下表：

该决策问题的线性规划数学模型：

运用作者开发设计的运筹学求解软件[2]，得到该模型的决策结果如图1所示：

（1）假设，价值系数同比例增加50%，即三个产品的单位利润都增加50%，则应该怎么决策？

（2）假设，两种原材料同比例增加10%，各对偶价格将会怎么变化？

图1 原模型的求解结果

对问题1，价值系数的实际增加量Δcl=250、Δc2=230、Δc3=180，而允许的增量分别为638-500=138、720-460=260和613.333-360=253.333。按百分一百法则，其判定值为：

远大于100%。而用计算机求解的结果如图2：

图2 增加价值系数后的求解结果

最优解并没发生变化。

对于问题2，常数项的实际增加量Δbl=55、Δb2=36，而允许的增量分别为1440-550=890和366.6667-360=6.6667：此时百分一百法则的判定值为：

远大于100%。而用计算机求解验证对偶价格并没发生变化。如图3：

图3 常数项变化后的求解结果

四、本问题研究的用途

对上述的实例分析，若其它企业愿意分别以45元/公斤的价格出售原料A和原料B，该厂应不应该购进而扩大生产？

对于该问题，原材料B对应约束条件的对偶价格76远大于市场购进价格，而原材料A对应约束打伤的对偶价格26远小于市场购进价格，所以应该大量购进原材料B以扩大生产获取较高的利润，但原材料B对应约束对偶价格不变总量上限为366.667公斤，从总体比例上看，只购进6.667公斤（占当前值的1.85%）扩大生产并没有实际意义。因此必须考虑在保持对偶价格不变的前提下找到大量购进原材料以扩大生产，用于对资源利用效果做出盈亏核算的客观条件。这就可以用到定理3的判断准则：

如仍按两种原材料当前值同时增加10%的比例购进，既然对偶价格不会发生变化，我们就可以直接用原对偶价格来进行原材料利用效果的盈亏核算。即核算原材料的价值与价格贡献的差值（目标函数的净增加值）：

目标函数的净增加值大于0，说明可以按这个比例购进原材料而扩大生产。这里就用到了约束条件各常数项的增加的值导致百分之一百法则判定值大于100%，但对偶价格仍然不变的判定结果。这样就可用原对偶价格进行核算，完全可以避免由于常数项的变化而重新建模，重新求解的过程。这也是对线性规划灵敏度分析用途的一种拓展。

五、结论

运筹学课程中，虽然线性规划中百分之一百法则强调的是关键决策量变化的充分条件而非必要条件，但能对法则中明确部分必要条件也能为决策应用带来很大的方便。本文针对在运筹学教学过程和线性规划运用实践中总结了某类参数同比例增减变化时，虽然判断条件值已大于100%，但相应的决策量并不会发生变化的规律性特征，是对百分之一百法则中关键决策时变化必要条件的研究尝试。并且在教学和运用实践中可能还会有其它的条件有待于继续研究。

[1]叶向.实用运筹学[M].北京：中国人民大学出版社，2007.

[2]陈士成.实用管理运筹学——基于Excel[M].北京：清华大学出版社，2011.

[3]何丽红，陈士成.管理运筹学课程的教学改革与实践[J].教育教学论坛，2011，（12）上旬刊：21-23.

[4]陈士成，何丽红，何丽红.大学《运筹学》课程分层教学目标研究[J].教育教学论坛，2013，（9）：70-71.

G642.4

A

1674-9324（2014）30-0203-03

兰州大学教学研究项目（201203）资助，兰州大学管理学院管理教育研究专项资金资助（13SMJXYJ001）。

陈士成（1957—），男，河南省镇平县人，经济学硕士，副教授，研究方向：企业管理与系统分析。