管理运筹学讲义：04

管理运筹学

2008年9月10日

SHUFE

如何用4条直线分隔10个点

2

元培学院

SHUFE

火灾

美国电影院曾经发生过一次可怕的火灾，在这次 火灾中共有四百多人丧生。后来，警察经过严 密调查，发现事实上所有人都能逃出大楼，但 他们都没有逃出去。你知道是为什么吗？

3

元培学院

SHUFE

第一节 线性规划的计算机求解

例1

5

元培学院

SHUFE

**********************最优解如下*************************目标函数最优值为 : 27500 变量 最优解 相差值 x1 50 0 x2 250 0 约束 松弛/剩余变量 对偶价格 1 0 50 2 0 50 3 50 0 目标函数系数范围 : 变量 下限 当前值 上限 x1 0 50 100 x2 50 100 无上限 常数项数范围 : 约束 下限 当前值 上限 1 250 300 325 2 200 250 300 3 350 400 无上限6

元培学院

SHUFE

第二节 软件的输出信息分析当单个系数变化时进行的灵敏度分析：

相差值相差值提供的数据表示相应的决策变量的目标系数需 要改进的数量，使得该决策变量有可能取正数值。所 以当决策变量为正数时，对应的相差值为0。

对偶价格 上限和下限

7

元培学院

SHUFE

软件的输出信息分析

例

8

元培学院

SHUFE

软件的输出信息分析

问题：当两个或多个系数同时变化时，怎么来进行 灵敏度分析呢？ 例1:假设每件产品I和产品II的利润分别由50元和100 元分别变为75元和80元，此时最优解是否改变呢？ 例2:假设约束条件中的常数项分别由300,400,250 变为315,390,240,此时，对偶价格是否改变？ 回答：使用百分之百法则元培学院

9

SHUFE

软件的输出信息分析

分类：价值系数的百分之百法则 约束条件中常数项的百分之百法则 价值系数的百分之百法则：对所有变化的价值系数， 当其所有允许增加百分比和允许减少百分比之和不 超过百分之百时，最优解不变。 约束条件中常数项的百分之百法则：对所有变化的 约束条件中的常数项，当其所有允许增加百分比和 允许减少百分比之和不超过百分之百时，其对偶价 格不变。10

元培学院

SHUFE

软件的输出信息分析

允许增加量：上限范围内的最大增加量 =上限-现在值 允许减少量：下限范围内的最大减少量 =现在值-下限 允许增加百分比=增加量/允许增加量 允许减少百分比=减少量/允许减少量

11

元培学院

SHUFE

软件的输出信息分析

使用百分之百法则注意点： 当允许增加量(减少量)为无穷大时，则对应的百 分比=0; 百分之百法则是判断最优解或对偶价格是否发生变 化的充分条件，但不是必要条件； 百分之百法则不能应用于价值系数和

约束条件中常 数项同时变化的情况，此时应重新求解。

12

元培学院

SHUFE

**********************最优解如下*************************目标函数最优值为 : 27500 变量 最优解 相差值 x1 50 0 x2 250 0 约束 松弛/剩余变量 对偶价格 1 0 50 2 0 50 3 50 0 目标函数系数范围 : 变量 下限 当前值 上限 x1 0 50 100 x2 50 100 无上限 常数项数范围 : 约束 下限 当前值 上限 1 250 300 325 2 200 250 300 3 350 400 无上限13

元培学院

SHUFE

软件的输出信息分析

例： 某公司由于生产需要，共需要A,B两种原料 至少350t(可替代),原料A至少购进125t。加 工A需要2小时/t,加工B需要1小时/t,公司共 有600加工时数。原料A价格2万/t,原料B价格 3万/t。问在满足资源约束的前提下，如何购 买A,B两种原料，使得购进成本最低？解：设x1为购进原料A的数量， x2为购进原料B的数量14

元培学院

SHUFE

软件的输出信息分析

x1+x2 ≥350

x1≥ 125 约束条件2x1+x2≤600

x1≥0 , x2≥0目标函数

min Z=2x1+3x215

元培学院

SHUFE

软件的输出信息分析

16

元培学院

SHUFE

软件的输出信息分析

17

元培学院