2对偶理论与灵敏度分析.ppt

1、回顾线性规划和单纯形法，线性规划问题的建模，图解法，最佳解必须在顶点，模型标准形式，单纯形法的基本可行解，单纯形表，第2章对偶理论和灵敏度分析，运筹学，2.1线性规划的对偶理论，2.2灵敏度分析，2.1线性规划的对偶理论，1。对偶问题的提出和模型，1 .提出对偶问题的例子1第一章的例子1。这时，另一家工厂提出购买甲、乙、丙三种资源。在原工厂可以接受的条件下，这个单价能让另一家工厂支付最低的多少？例1称为例2的原问题，用(p)表示，例2称为例1的对偶问题，用(D)，2表示，对偶模型的一般形式。以例2为例，原来的问题是：(p):Y(y1，y2，y3)，那么对偶问题是：(d):这是对偶模型最常见的形

2、式，它们之间有非常对称的对应关系。对偶模型的特点是：(1)P是最大型，d是最小型；(2)P的变量数；(3)P的约束数；(4)资源约束向量；(5)资源约束向量；(6)普氏技术系数矩阵；D的技术系数矩阵转置如果P的一个变量是自由的，D的相应约束是“=”。让y3- y4，那么有：3。如何编写线性规划模型的对偶模型，(1)如果线性规划是最大类型，尽可能将其转化为(P)形式。(方程和自由变量不需要转换)，(P)，(D)，(2)如果LP是min型，则应尽可能转换成(D)型。(方程和自由变量不需要转换)。例3写了以下线性规划的对偶规划模型。解决方法：如果对偶变量是y1，y2，y3和Y3，对偶目标是W，那么它

3、的对偶规划模型是：练习写下面的LP的对偶模型。双重模式是：2 .对偶性质和定理；1.对称性：(p)和(d)是相互对偶的。2.弱二元性。假设x和y是(p)和(d)的任何可行解，那么我们可以推导出：3。无界如果(p)是无界解，(d)没有可行解；如果(d)是无界解，(p)没有可行解。4。解的最优性。对偶定理。如果(p)有一个最优解，(d)也有一个最优解，并且它们的最优值相等。然后，让可行解分别为(p)和(d)，问题是：(1)根据性质5，对偶问题的最优解的表达式是Y*=？y *=CB B- 1；其中b是原问题的最优基础。(2)有必要为Y*重新求解(d)吗？Y*是(p)最终表格中XS支票号码的负值；如果

4、没有XS，则Y*=CB* (B*)-1用于计算。示例4已知用于求解以下线性规划模型的单纯形最终表如下，并且获得其对偶模型的最优解。X*=(2，0，9，0)T；z*=5 Y*=(0，0.5)；W*=5，6，弹性定理(互补松弛)，它表明在线性规划问题的最优解中，如果约束条件对应的对偶变量值为非零，那么约束条件取一个严格的方程；另一方面，如果约束条件是一个严格的不等式，其对应的变量必须为零。如果可行解分别为(p)和(d)，则有：原问题的变量x，其中一个大于0，另一个必须等于0。松弛变量Xs，松弛变量Ys，对偶问题的变量y，例5:线性规划问题已知，对偶问题的最优解已知为y1*=4/5，y2*=3/5，

5、z*=5。试着用对偶理论找到原问题的最优解。线性规划问题是已知的，原问题的最优解已知为x1*=2，x2*=2，x3*=4，x4*=0。3。对偶问题的经济学解释，1。双重最优解的经济学解释资源的影子价格y *=(y1 *，y2 *，ym*)是动态规划的最优解，那么yi*代表线性规划中某一资源的bi单位变化对目标的影响，称为bi的影子价格。CB-1双重问题的最优解，买方的最低出价，原问题的影子价格，1个单位资源的增加所引起的总收入的增加，以及卖方的内部控制价格。实例6和实例1的最终单形表如下：请指出资源A、B和C的影子价格，并解释其经济意义。影子价格在管理决策中的作用：(1)影子价格市场价格，如果

6、，影子价格市场价格，应该，影子价格市场价格应该，买卖这种资源；(2)影子价格反映了资源的稀缺性，影子价格越高，越稀缺。例如，如果资源c的影子价格是0，这意味着有盈余。2、双重约束经济学解释产品的机会成本，机会成本：指为了得到某物而放弃某物的最大价值。小机会成本具有比较优势，即在将某一资源投入某一用途后，在其他用途中可以获得的最大利益。例如，如果某块土地选择饲养某种家禽，它就不能选择饲养其他家禽。假设养猪可以得到9万元，养鸡可以得到7万元，养鸭可以得到8万元，那么养猪的机会成本是8万元；养鸡的机会成本为9万元；养鸭的机会成本也是9万元。机会成本表示通过减少产品节省的资源可以增加的利润。双松弛变量

7、的经济解释差异成本、机会成本、利润、机会成本、差异成本、利润、4。利润最大化生产计划中互补松弛关系的经济学解释：(1)影子(2)剩余资源的影子价格等于0；(3)安排生产的产品的机会成本等于利润；(4)机会成本大于利润的产品不安排生产。2.2灵敏度分析，任务：讨论模型系数或变量的微小变化对解的影响(例如，当它们变化时，原始最优解或最优基在什么范围内可以保持不变？)主要讨论a、b、c和可变结构变化对解的影响。1.资源数量B变化时的分析(仅影响解决方案的可行性)。问：在什么范围内B发生变化，它不影响最佳基础？方法：(1)b资源的影子价格是多少？(2)使最佳基础仍然适用的最佳资源的变化范围是什么？(在

8、不影响最佳基础的情况下，b2在多大范围内变化？)(3)如果有人愿意以每公斤0.1元的价格向工厂提供25公斤的资源，值得接受吗？2.分析价格系数C的变化，当价格从cj变化到cj时，它只影响最优性，这在两种情况下讨论：(1) cj是非基本变量xj的价格系数；(2) cj是基本变量xj的价格系数；当乙产品的价格c2发生变化时，最优解在什么范围内保持不变？3.技术系数A变化时的分析。方法：(1)增加一个新变量xn 1经济意义：n 1新产品是否应该投入生产；数学意义：xn 1是否应该进入基数。经济意义：市场价格，影子价格，如果现在考虑一个新产品C，它的资源消耗是2，6，3，价格是5。问问这个产品是否能投入生产。(2)共同执行活动中技术系数的变化限制了系数矩阵A的变化，Pj Pj分为两种情况：Pj