线性规划灵敏度分析.pptVIP

同时成立一般而言，我们把某一可行点（如X*和Y*）处的严格不等式约束（包括对变量的非负约束）称为松约束，而把严格等式约束称为紧约束。所以有如下推论：设一对对偶问题都有可行解，若原问题的某一约束是某个最优解的松约束，则它的对偶约束一定是其对偶问题最优解的紧约束。Chapter2灵敏度分析如果线性规划的原问题存在可行解，则其对偶问题也一定存在可行解如果线性规划的对偶问题无可行解，则原问题也一定无可行解。在互为对偶的一对原问题和对偶问题中，不管原问题是求极大或者极小，原问题可行解的目标函数值都一定不超过其对偶问题可行解的目标函数值。例题判断下例说法是否正确，为社么？Chapter2灵敏度分析解：A不对。因为原问题为无界解时（它当然有可行解），其对偶问题无可行解。B此句为A的逆否命题，所以也不对。C不对。因为哪个问题是原问题，哪个问题是对偶问题是相对而言的。Chapter2灵敏度分析Chapter2灵敏度分析例题:已知原问题的最优解为X*=（），Z=12试求对偶问题的最优解。01解:02将X*=（0.0.4）代入原问题中，有下式：Chapter2灵敏度分析所以，根据互补松弛条件，必有y*1=y*2=0，代入对偶问题（3）式，y3=3。因此，对偶问题的最优解为1Y*=（0.0.3），W=12。2Chapter2灵敏度分析Chapter2灵敏度分析影子价格是对现有资源实现最大效益时的一种估价01企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。02影子价格的经济含义Chapter2灵敏度分析影子价格表明资源增加对总效益产生的影响。根据推论“设x0和y0分别为原规划（P）和对偶规划（D）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系01因此，可以将z*看作是bi,i=1,2，…,m的函数，对bi求偏导数可得到02这说明，如果右端常数增加一个单位，则目标函数值的增量将是03Chapter2灵敏度分析Chapter2灵敏度分析影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。Chapter2灵敏度分析Chapter2灵敏度分析对偶单纯形法对偶单纯形法的基本思想对偶单纯形法的基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。对偶单纯形法在什么情况下使用：应用前提：有一个基，其对应的基满足:单纯形表的检验数行全部非正（对偶可行）；变量取值可有负数（非可行解）。注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。Chapter2灵敏度分析Chapter2灵敏度分析Chapter2灵敏度分析例题:用对偶单纯形法求解Chapter2灵敏度分析解:将上述模型转化为Chapter2灵敏度分析cj-9-12-15000cBxBbx1x2x3x4x5x60x4-10-2-2-11000x5-12-2-3-10100x6-14-1-1-5001(-9/-1.-12/-1.-15/-5)-Z′0-9-12-15000Chapter2灵敏度分析cj-9-12-15000cBxBbx1x2x3x4x5x60x4-36/5-9/5-9/5010-1/50x5-46/5-9/5-14/5001-1/5-15x314/51/5