运筹学第七周灵敏度分析运输问题ppt课件.pptx

《运筹学第七周灵敏度分析运输问题ppt课件.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章对偶理论与灵敏度分析1本章内容对偶理论是线性规划最重要的基础理论之一是进行经济分析的重要工具2一般形式单纯形法计算的矩阵描述设线性规划问题:目标函数约束条件AX≤b;非负条件X≥0线性规划问题的约束条件加入松弛变量以后，得到标准型：maxz=CX+0XsAX+IXs=b;X，Xs≥0maxz=CX3矩阵A可以分块记为A=[B，N]相应地，向量X和C可以记为XB=B-1b—B-1NXN—B-1Xs对于一个确定的基B，目标函数z可以写成目标函数z用非基变量表出的形式4CBCN00XBXNXSb0XS

2、BNIb检验数CBCN00XBXNXSbCBXBIB－1NB－1B－1b检验数0CN－CBB－1N－CBB－1－CBB－1b初始单纯形表迭代n步之后的单纯形表5影子价格总结：3.影子价格是在系统达到最优时对系统资源的一种最优估价，并假设第i种资源增加一个单位时最优基没改变。4.影子价格可以告诉管理人员，增加哪一种资源对增加经济效益有利，帮助企业调节生产规模；5.影子价格可以告诉管理人员，花多大的代价来增加资源才是合算的；6.影子价格可以帮助管理人员进行生产要素对产出贡献的分解；7.影子价格可以告诉管理

3、人员如何考虑新产品的价格。1.影子价格的大小客观地反映了资源在系统内的稀缺程度。2.影子价格的取值与系统的状态有关，系统中任一状态的改变都会引起影子价格的变化。6对偶单纯形法是应用对偶原理求解原始线性规划的一种方法——在原始问题的单纯形表格上进行对偶处理。注意：不是解对偶问题的单纯形法！什么是对偶单纯形法？71.使用条件：①检验数全部≤0；②右端向量列至少一个元素<0；2.实施对偶单纯形法的基本原则：在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个右端负分量作为换出变量去替换某个

4、非基变量（作为换入变量），使原始问题的非可行解向可行解靠近。对偶单纯形法的实施83.计算步骤：①建立初始单纯形表，计算检验数行。右端向量列≥0——已得最优解；右端向量至少一个元素<0,转下步;右端向量列≥0——原始单纯形法；至少一个元素<0,另外处理；检验数全部≤0（非基变量检验数<0）至少一个检验数>09基变换：先确定换出变量——右端向量列中的负元素（一般选最小的负元素）对应的基变量出基；相应的行为主元行。10然后确定换入变量——原则是：在保持对偶可行的前提下，减少原始问题的不可行性。如果（最小比

5、值原则），则选为换入变量，相应的列为主元列，主元行和主元列交叉处的元素为主元素。11按主元素进行换基变换（初等行变换），将主元素变成1，主元列变成单位向量，得到新的单纯形表。最优解判别法则：右端向量满足非负约束12第五节灵敏度分析13以前讨论线性规划问题时，假定αij，bi,cj都是常数，但实际上这些系数往往是估计值或预测值。如市场条件一变，cj值就会变化；αij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。14灵敏度分析：指对系统或事物因周围条件变化显示出来的敏感

6、程度的分析。线性规划模型的灵敏性分析：研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程，称为线性规划的灵敏度分析。一、灵敏度分析的含义和内容15目标函数的价值系数变化约束方程右端向量变化约束方程组系数阵变化决策变量或约束条件变化2.线性规划灵敏度分析的内容maxz=CXAX=bX≥01.最优解保持不变，即基变量和它们的取值没有变化2.基变量保持不变，但它们的值改变了3.基解完全变了对解的影响主要有:可行性B－1b≥0最优性CN－CBB－1N≥016LP灵敏度分析最终回答：计算量少

7、，充分利用到原最优的单纯形表结果1.这些系数在什么范围内变化时，原先求出的线性规划问题的最优解或最优基不变。2.如果系数的变化超出了上述范围，如何用最简便的方法求出新的最优解。17三、灵敏度分析的步骤将参数的改变通过计算反映到最终单纯形表上2.检查原问题和对偶问题是否还是可行解3.按照下表所列情况分别进行讨论原问题对偶问题结论或继续计算方法可行解可行解问题的最优解保持不变可行解非可行解用单纯形法继续求解非可行解可行解对对偶单纯形法求解非可行解非可行解引用人工变量，构造基，重新计算181.价值系数cj的

8、变化分析四、灵敏度分析的具体内容XBXNXSbCBXBIB－1NB－1B－1b检验数0CN－CBB－1N－CBB－1－CBB－1bCBCN00XBXNXSb0XSBNIb检验数CBCN00初始单纯形表最优单纯形表19当cj变化时，如能保持，则当前解仍为最优解，否则可用单纯形法继续迭代求出新的最优解。将cj看作待定参数，令解这n-m个不等式，可算出保持最优解不变时cj的变化范围。（1）当cj是非基变量的价值系数——它的变化只影响一个检验数。（2）当cj是基