第三章--线性规划问题的计算机求解.ppt

第三章 线性规划问题的计算机求解
§1　“管理运筹学”软件的操作方法
§2　“管理运筹学”软件的输出信息分析
1
第三章 线性规划问题的计算机求解
随书软件为“管理运筹学”（Window版），（DOS对应的资源每增加一个单位，将增加多少个单位的最优值。
目标函数系数范围表示最优解不变的状况下，目标函数的决策变量系数的变更范围。当前值是指当前的最优解中的系数取值。
常数项范围是指约束条件的右端常量。上限值和下限值是指当约束条件的右端常量在此范围内变更时，与其对应的约束条件的对偶价格不变。当前值是指现在的取值。
以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变更的基础上得出的！
7
§　“管理运筹学”软件的输出信息分析
一、软件输出结果分析


1）给出最优解信息
2）相差值供应的决策信息
相差值的含义：指相应的决策变量的目标函数须要改进的数量，使得该决策变量有可能取正数值，当决策变量已取正数值时则相差值即为零。

1）松弛/剩余变量信息
2）对偶价格信息

给出了使最优解保持不变的决策变量系数ci的变更范围。

给出了使约束条件的对偶价格保持不变的相应的bi的变更范围。
8
§　“管理运筹学”软件的输出信息分析
留意：
以上计算机输出的目标函数系数和约束条件右边值的灵敏度分析都是在其他系数值不变，只有一个系数变更的基础上得出的！
假如两个或两个系数同时发生变更，如何推断最优解或者对偶价格是否发生变更呢。下面我们介绍两个或更多系数发生变更的灵敏度分析——百分之一百法则。
9
§　“管理运筹学”软件的输出信息分析
二、多个系数变更时的灵敏度分析
百分之一百法则：对于全部变更的目标函数决策系数（约束条
件右边常数值），当其全部允许增加的百分比与允许削减的百分比
之和不超过100%时，最优解不变（对偶价格不变，最优解仍是原
来几个线性方程的解）。
* 允许增加量 = 上限 - 现在值
c1 的允许增加量为 100 - 50 = 50
b1 的允许增加量为 325 - 300 = 25
* 允许削减量 = 现在值 - 下限
c2 的允许削减量为 100 - 50 = 50
b3 的允许削减量为 250 - 200 = 50
* 允许增加的百分比 = 增加量 / 允许增加量
* 允许削减的百分比 = 削减量 / 允许削减量
10
§　“管理运筹学”软件的输出信息分析
： c1 变为 74 , c2 变为 78, 则 (74 - 50) / 50 + (100 - 78 ) / 50 = 92%，故最优解不
变。
b1 变为 315 , b3 变为 240, 则 (315 - 50) / 25 + (250 - 240 ) / 50 = 80%，故对偶价
格不变（最优解仍是原来几个线性方程的解）。
在运用百分之一百法则进行灵敏度分析时，要留意：
1）当允许增加量（允许削减量）为无穷大时，则对随意增加量（削减量），其允许增加（削减）百分比均看作0；
2）百分之一百法则是充分条件，但非必要条件；也就是说超过100%并不确定变更；
3）百分之一百法则不能用于目标函数决策变量系数和约束条件右边常数值同时变更的状况。这种状况下，只有重新求解。
11

目标函数：
Min f = 2x1 + 3 x2
. x1 + x2 ≥ 350
x1 ≥ 125
2 x1 + x2 ≤ 600
x1 , x2 ≥ 0
从上图可知，当购进原材料A 250t，原料B 100t时，购进成本最低，为800万元。
§　“管理运筹学”软件的输出信息分析
12
在松弛/剩余变量栏中，约束条件2的值为125，它表示对原料A的最低需求，即对A的剩余变量值为125；同理可知约束条件1的剩余变量值为0；约束条件3的松弛变量值为0。
在