运筹学课件2012 第06章 单纯形法的灵敏度分析与对偶.ppt

《运筹学课件2012 第06章 单纯形法的灵敏度分析与对偶.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章单纯形法的灵敏度分析与对偶§1单纯形表的灵敏度分析§2线性规划的对偶问题§3对偶规划的基本性质§4对偶单纯形法1§1单纯形表的灵敏度分析2§1单纯形表的灵敏度分析一、目标函数中变量Ck系数灵敏度分析3§1单纯形表的灵敏度分析4§1单纯形表的灵敏度分析5§1单纯形表的灵敏度分析例：目标函数：Maxz=50X1+100X2约束条件：X1+X2≤3002X1+X2≤400X2≤250X1，X2≥0最优单纯形表如下迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2

2、000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-506§1单纯形表的灵敏度分析7§1单纯形表的灵敏度分析8§1单纯形表的灵敏度分析迭代次数基变量CBX1X2S1S2S3bC’11000002X1C’11010-150S2000-21150X210001001250ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-1009§1单纯形表的灵敏度分析二、约束方程中常数项的灵敏度分析我们在第三章对线性规划问题的计算机求解中，也曾经

3、对约束方程右边常数bj进行了灵敏度分析，根据计算机输出的表格，可知道，约束方程右边常数在什么范围内变化时，其对偶价格不变，那么在用单纯形表对bj进行灵敏度分析时，首先应从单纯形表中找到有关对偶价格的信息。在第三章里我们给了对偶价格这样的定义：在约束条件右边量增加一个单位而使最优目标值得到改进的数量。根据这个定义，我们可以发现约束条件的对偶价格与松弛变量(或剩余变量或人工变量)的Zj有关。下面我们仍以第二章例1为例在其最终单纯形表上找出其约束条件的对偶价格。10此题的最终单纯形表如下，这是一个求目标

4、函数最大值的问题。从上表可以发现设备台时数的约束方程中的松弛变量S1的zj值50正好等于计算机解中设备台数的对偶价格，原料A约束方程中的松弛变量S2的Zj值0正好等于计算机解中的原料A的对偶价格。同样原料B的约束方程中的松弛变量S3的Zj值50正好等于计算机解中的原料B的对偶价格。松弛变量的Zj值是否等于对应的约束条件的对偶价格呢?回答是肯定的。迭代次数基变量CBx1x2s1s2s3b501000002x1S2x25001001010-100-211010015050250zjσj=cj-zj50

5、1005005000-500-502750011首先知道在最优解中S2=50是基变量，也就是说，原料A有50千克没用完，再增加原料A是不会带来任何利润的，故原料A的对偶价格为零。在最终单纯形表上当松弛变量为基变量时，都有其检验数σj为零，又知道对任何的松弛变量，它在目标函数中的系数Cj都为零，那么为基变量的松弛变量的Zj也必然为零，因为Zj=Cj-σj=0-0=0，这正确地反映了对于任何为基变量的松弛变量所对应的约束条件的对偶价格为零。下面我们来看一看对于非基变量的松弛变量的Zj值是否也正确地给出

6、了与其对应的约束条件的对偶价格?§1单纯形表的灵敏度分析12因为对所有松弛变量都有Cj=0所以Zj=Cj-σj=-σj，在对非基变量的目标函数的灵敏度分析中，知道当ΔCj≤-σj时最优解不变。也就是说当ΔCj≤-σj时，非基变量仍然为非基变量，仍然为零。这时与其对应的约束条件譬如说设备台时数全部使用完了。只有当ΔCj≥-σj，也就是△Cj≥Zj时，对应为非基变量的松弛变量要变成入基变量了。对于设备台时数来说，当其松弛变量在目标函数中系数从零变到Z3=50时，也就是说只有当余下一个台时数的设备不能获

7、利变成能获利50元时，譬如说别人愿意出价50元买一个设备时，就不必为生产Ⅰ、Ⅱ产品而使用完所有的设备台时了，这正说明了设备台数的对偶价格就是Z3=50元。同样我们也可以知道原料B的对偶价格为Z5=50元。§1单纯形表的灵敏度分析13对于含有大于等于号的约束条件，为了化成标准型就添上了剩余变量。这时这个约束条件的对偶价格就和这个剩余变量的Zj有关了。只不过当约束条件右边的常量增加一个单位时，约束条件更严格了。这将给满足约束条件带来些困难。就使最优目标函数值特别“恶化”而不是改进，故这时，约束条件的对

8、偶价格应取Zj值的相反数-Zj。对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的Zj值。下面我们给出一个由最终单纯形表对于不同约束类型的对偶价格的取值表：约束类型对偶价格的取值≤等于这个约束条件对应的松弛变量的Zj值≥等于与这个约束条件对应的剩余变量的Zj值的相反数-Zj=等于与这个约束条件对应的人工变量的Zj值§1单纯形表的灵敏度分析14从对偶价格的定义，可以知道当对偶价格为正时，它将改进目标函数值。对