第二章对偶理论及灵敏度分析.pptVIP

根据求bi的偏导数得：这说明，原问题某一约束条件的右边常数bi增加一个单位时，则由此引起最优目标函数值的增加量，就等于与该约束相对应的对偶变量的最优值。这样一来，在有限资源条件下使收益最大化这一类问题中，就可以把对偶变量的最优值，看成是相应资源每一单位对于目标函数的贡献，即这些资源被充分利用时所能带来的收益。从而，yi*的值就相当于对单位i种资源在实现最大利润时的一种价格估计。这种估计是针对具体企业，具体产品而存在的一种特殊价格，称之为影子价格，它与市场价格不同。若仅从经济上考虑，当某种资源的市场价格低于影子价格时，企业就可以考虑买进这种资源；当市场价格高于影子价格时，企业则可以出售这种资源。随着资源的买进卖出，它的影子价格也将随之变化，直到影子价格与市场价格保持同等水平时，才处于平衡状态。第29页，共68页，星期日，2025年，2月5日影子价格是一种边际价格（图示）Q1Q3Q2Q4Ox1x25x2＝156x1＋2x2＝24x1＋x2＝5z＝2z＝8.5(3.5，1.5)(25)第30页，共68页，星期日，2025年，2月5日影子价格的应用（1）用影子价格判别资源的供求关系如果线性规划的原问题在得到最优解时，某个约束条件为严格的不等式，即最优解中该约束的松弛变量的值大于零，即表明该种资源有剩余，供大于求。增加这种资源时，目标函数值不会有任何改善。如果线性规划的原问题在得到最优解时，某个约束条件为严格的等式，即最优解中该约束的松弛变量的值等于零，即表明该资源恰恰用完。这种资源增加一个单位，目标函数值就改进一个影子价格。由此可见，影子价格大于零，说明资源紧缺；影子价格等于零，说明资源有剩余。影子价格愈大，说明该资源愈紧缺，该种资源每增加一个单位所相应增加的目标函数值愈大。第31页，共68页，星期日，2025年，2月5日如果xn+i=0,必有yi＞0，资源紧缺；

如果xn+i＞0,必有yi＝0，资源剩余。松弛变量xs对偶变量yi资源限量bi第32页，共68页，星期日，2025年，2月5日（2）应用影子价格来合理分配资源算出各种资源的影子价格后，可参考影子价格高低顺序合理分配资源，高者优先投资。同时，也可以参考资源的影子价格，合理地确定各种资源的价格。第33页，共68页，星期日，2025年，2月5日§2-4对偶单纯形法引言前面介绍的单纯形法，是从一个基本可行解开始进行迭代运算，在迭代过程中，始终保持解的可行性，当所有检验数都非正时，就得到了原问题的最优解。根据对偶定理，原问题单纯形表中的检验数实际上是对偶问题的一组解，但不一定可行，检验数逐渐变为非正的过程，可以理解为对偶问题解的不可行性逐渐消失的过程，当对偶问题的解变为可行解时，原问题就得到了最优解。因此，我们可以选择在对偶问题的解之间进行迭代运算，在迭代过程中，始终保持最优判别条件得到满足，当求出对偶问题的可行解时，也就得到了原问题的最优解。返回本章目录第34页，共68页，星期日，2025年，2月5日例4用对偶单纯形法求解线性规划问题：将约束条件两边同时乘以“-1”得：标准形式得到初始基为：基变量为y4,y5，非基变量为y1,y2,y3。令所有的非基变量等于0，得到该问题的一个解为：Y=(0,0,0,-2,-1)T这个解不可行，称为正则解。对偶单纯形法就是从一个正则解开始迭代的。第35页，共68页，星期日，2025年，2月5日表2-8cj→-15-24-500CB基by1y2y3y4y50y4-20-6-1100y5-1-5-2-101cj－zj-15-24-500确定换出变量y4为换出变量2.确定换入变量y2为换入变量。3.迭代运算，得新单纯形表。-24y21/3011/6-1/600y5-1/3-50-2/3-1/31cj－zj-150-1-40-24y21/4-5/410-1/41/4-5y31/215/2011/2-3/2cj－zj-15/200-7/2-3/2∵sj≤0，最优解Y=(0,1/4,1/2,0,0)TMinw=15y1+24y2+5y3=17/2第36页，共68页，星期日，2025年，2月5日§2-5灵敏度分析对一线性规划问题来说，一旦其约束条件系数矩阵A、约束条件右侧常数向量b和价值系数向量C给定之后，这个线性规划问题就确定了。反之，给定一个线性规划