第2章 对偶理论和灵敏度分析-第7,8节

《第2章 对偶理论和灵敏度分析-第7,8节》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、（第三版）《运筹学》教材编写组编清华大学出版社运筹学第2章对偶理论和灵敏度分析第7节灵敏度分析第8节参数线性规划第7节灵敏度分析以前讨论线性规划问题时，假定αij，bi，cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。因此提出这样两个问题：(1)当这些系数有一个或几个发生变化时，已求得的线性规划问题的最优解会有什么变化；(2)或者这些系数在什么范围内变化时，线性规划问题的最优解或最优基不变。后一个问题将在第8节参数线性规划中讨论。线性规

2、划问题中某一个或几个系数发生变化显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。当然可以用单纯形法从头计算，以便得到新的最优解。这样做很麻烦，而且也没有必要。因在单纯形法迭代时，每次运算都和基变量的系数矩阵B有关，因此可以把发生变化的个别系数，经过一定计算后直接填入最终计算表中，并进行检查和分析，可按表2-9中的几种情况进行处理。表2-9下面就各种情况分别按节进行讨论。7.1资源数量变化的分析资源数量变化是指资源中某系数br发生变化，即br′=br+Δbr。并假设规划问题的其他系数都不变。这样使最终表中原问题的解相应地变化为X

3、B′=B-1(b+Δb)这里Δb=(0,…，Δbr,0,…，0)T。只要XB′≥0，因最终表中检验数不变，故最优基不变，但最优解的值发生了变化，所以XB′为新的最优解。新的最优解的值可允许变化范围用以下方法确定。B-1是最终计算表中的最优基的逆b列的元素变化例如求第1章例1中第二个约束条件b2的变化范围。解：可以利用第1章例1的最终计算表中的数据：可计算Δb2：由上式，可得Δb2≥-4/0.25=-16，Δb2≥-4/0.5=-8，b2≤2/0.125=16。所以Δb2的变化范围是［-8，16］；显然原b2=16，加它的变化范围后，b2的变化范围是［8，3

4、2］。例7从表1-5得知第1章例1中，每设备台时的影子价格为1.5元，若该厂又从其他处抽调4台时用于生产产品Ⅰ，Ⅱ。求这时该厂生产产品Ⅰ，Ⅱ的最优方案。解先计算B-1Δb,将结果反映到最终表1-5中，得表2-10。由于表2-10中b列有负数，故用对偶单纯形法求新的最优解。计算结果见表2-11。表2-11即该厂最优生产方案应改为生产4件产品Ⅰ，生产3件产品Ⅱ，获利z*=4×2+3×3=17(元)从表2.11看出x3=2，即设备还有2小时未被利用7.2目标函数中价值系数cj的变化分析可以分别就cj是对应的非基变量和基变量两种情况来讨论。(1)若cj是非基变量x

5、j的系数，这时它在计算表中所对应的检验数是σj=cj-CBB-1Pj或当cj变化Δcj后，要保证最终表中这个检验数仍小于或等于零，即σj’=cj+Δcj-CBB-1Pj≤0那么cj+Δcj≤YPj，即Δcj的值必须小于或等于YPj-cj，才可以满足原最优解条件。这就可以确定Δcj的范围了。(2)若cr是基变量xr的系数当cr变化Δcr时，引起CB的变化Δcr可变化的范围:例8试以第1章例1的最终表表1-5为例。设基变量x2的系数c2变化Δc2，在原最优解不变条件下，确定Δc2的变化范围。解这时表1-5最终计算表便成为表2-12所示。若保持原最优解，从表2

6、-12的检验数行可见应有由此可得Δc2≥-3和Δc2≤1。Δc2的变化范围为-3≤Δc2≤1即x2的价值系数c2可以在［0，4］之间变化，而不影响原最优解。7.3技术系数αij的变化分两种情况来讨论技术系数αij的变化，下面以具体例子来说明。例9分析在原计划中是否应该安排一种新产品。以第1章例1为例。设该厂除了生产产品Ⅰ，Ⅱ外，现有一种新产品III。已知生产产品III，每件需消耗原材料A，B各为6kg，3kg，使用设备2台时；每件可获利5元。问该厂是否应生产该产品和生产多少?解分析该问题的步骤是：(1)设生产产品III为x3′台，其技术系数向量P3′=(2

7、,6,3)T，然后计算最终表中对应x3′的检验数σ3′=c3′-CBＢ-1Ｐ3′=5-(1.5,0.125,0)(2,6,3)T=1.25＞0说明安排生产产品III是有利的。分析该问题的步骤(2)是：表2-13(a)由于b列的数字没有变化，原问题的解是可行解。但检验数行中还有正检验数，说明目标函数值还可以改善。分析该问题的步骤(3)是：(3)将x3′作为换入变量，x5作为换出变量，进行迭代，求出最优解。计算结果见表2-13(b)，这时得最优解：x1=1,x2=1.5，x3′=2。总的利润为16.5元。比原计划增加了2.5元。表2-13(b)例10分析原计划

8、生产产品的工艺结构发生变化。仍以第1章例1为例，若原计划生产产品Ⅰ