当前位置:文档之家› (第三版)《运筹学》教材编写组编清华大学出版社

(第三版)《运筹学》教材编写组编清华大学出版社


解 先计算B-1Δb,将结果反映到最终表1-5中, 得 表2-10。
0.25 0 4 0 0 1 B b 2 0 .5 1 0 8 0.5 0.125 0 0 2
cj → CB 2 0 3 XB x1 x5 x2 cj- zj b 4+0 4-8 2+2 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 0 x4
线性规划问题中某一个或几个系数发生变化 • 显然,当线性规划问题中某一个或几个系数发 生变化后,原来已得结果一般会发生变化。当 然可以用单纯形法从头计算,以便得到新的最 优解。这样做很麻烦,而且也没有必要。因在 单纯形法迭代时,每次运算都和基变量的系数 矩阵B有关,因此可以把发生变化的个别系数, 经过一定计算后直接填入最终计算表中,并进 行检查和分析,可按表2-9中的几种情况 进行 处理。
0 x5 0 1 0 0
0 0.25 [-2] 0.5 0.5 –0.125 -1.5 -0.125
由于表2-10中b列有负数,故用对偶单纯形法求新 的最优解。计算结果见表2-11。
表2-11
cj → CB 2 0 3 XB x1 x3 x2 cj- zj b 4 2 3 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 0 1 0 0 0 x4 0.25 -0.25 0 -0.5 0 x5 0 -0.5 0.25 -0.75
b列的元素变化
在最终表中求得的经过变化后的 b 列的所有元素, 要求b i +a ir Δ br ≥0,i=1,2,…,m。由此可得 a ir Δ br ≥b i ,i=1,2,…,m 当 a ir >0 时,Δ br ≥b - ia / ir; 当 a ir <0 时,Δ br ≤b - ia / ir;于是得到
• 资源数量变化是指资源中某系数br 发生变化, 即 br′=br+Δ br 。并假设规划问题的其他系数 都不变。这样使最终表中原问题的解相应地变 化为 XB′=B-1(b+Δ b) • 这里 Δ b=(0,… , Δ br,0,… , 0)T 。只要 XB′≥0 , 因最终表中检验数不变,故最优基不变,但最 优解的值发生了变化,所以XB′为新的最优解。 新的最优解的值可允许变化范围用以下方法确 定。
B-1 是最终计算表中的最优基的逆
0 B 1 (b b) B 1b B 1b B 1b B 1 br 0 a1r 0 a1r br B 1 br air br br air 0 a mr br a mr
1 / 4 0 0 0 4 0 可计算Δ b2: 1 1 B b B b2 4 2 1 / 2 1 b2 0 2 1 / 2 1 / 8 0 0 4 1/ 4 0 4 1 / 2 b2 0 2 1/ 8 0 由上式,可得 Δ b2≥-4/0.25=-16 , Δ b2≥-4/0.5=-8 , b2≤2/0.125=16 。 所以 Δ b2 的变化范围是[ -8 , 16 ];显然原 b2 =16 ,加它 的变化范围后, b2的变化范围是[8,32]。
运筹学(第三ຫໍສະໝຸດ )《运筹学》教材编写组 编
第2章 对偶理论和 灵敏度分析 第7节 灵敏度分析
第8节
参数线性规 划
钱颂迪 制作
清华大学出版社
第7节
灵敏度分析
• 以前讨论线性规划问题时,假定 αij , bi,cj 都是常数。 但实际上这些系数往往是估计值和预测值。 • 如市场条件一变, cj 值就会变化; αij 往往是因工艺条 件的改变而改变; bi是根据资源投入后的经济效果决 定的一种决策选择。 • 因此提出这样两个问题: (1)当这些系数有一个或几个发生变化时,已求得的线性 规划问题的最优解会有什么变化; (2)或者这些系数在什么范围内变化时,线性规划问题的 最优解或最优基不变。后一个问题将在第 8 节参数线 性规划中讨论。
bi bi max air 0 br min air 0 i i air air
例如求第1章例1中第二个约束条件b2的变化范围。 • 解:可以利用第1章例1的最终计算表中的数据:
cj→
CB 2 0 3 -z XB x1 x5 x2 b 4 4 2 -14 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 1 -2 1/2 -3/2 0 x4 1/4 1/2 -1/8 -1/8 0 x5 0 1 0 0 θ
例7 从表1-5得知第1章例1中,每设备台时的影子价 格为1.5元,若该厂又从其他处抽调4台时用于生产产 品Ⅰ,Ⅱ。求这时该厂生产产品Ⅰ,Ⅱ的最优方案。
cj→
CB 2 0 3 -z XB x1 x5 x2 b 4 4 2 -14 2 x1 1 0 0 0 3 x2 0 0 1 0 0 x3 1 -2 1/2 -3/2 0 X4 1/4 1/2 -1/8 -1/8 0 x5 0 1 0 0 θ
表 2-9
原问题 可行解 可行解 非可行解 非可行解 对偶问题 可行解 非可行解 可行解用 非可行解 结论或继续计算的步骤 表中的解仍为最优解 用单纯形法继续迭代求最优解 对偶单纯形法继续迭代求最优解 引进人工变量,编制新的单纯形表,求最优解
下面就各种情况分别按节进行讨论。
7.1 资源数量变化的分析
相关主题