厦门大学运筹学2宣讲培训.ppt

第二章 对偶理论与灵敏度分析 在这一章中，我们将通过举例来说明线性规划对偶问 题的提出并说明它的经济意义；由此来阐述它们两者之间 的关系。进一步来探讨如何求一个线性规划问题的对偶问 题、以及线性规划与它的对偶问题之间的关系、对偶单纯 形算法以及对线性规划问题解的变化的进一步讨论（即灵 敏度分析和参数规划等等）。 第一节 对偶问题的提出 在第一章第一节的例1中，我们讨论了工厂生产计划模 型及其解法，现从另一个角度来讨论这个问题。假设该工;厂的决策者决定不生产产品I、II，而将其所有资源出租或 出售。这时，工厂的决策者就要考虑给每种资源进行定价 的问题。设用 y1、 y2、 y3 分别表示出租单位设备台时的 租金和出让单位原材料 A、B 的附加费。作决策时，需要 如下的比较：若一个单位设备台时和四个单位原材料 A可 以生产一件产品I，可获利2元，那么生产每件产品I的设备 台时和原材料出租和出让的所有收入应不低于生产一件产 品I的利润。这就有： y1 + 4y2 ? 2 ；对于产品II同理有： 2 y2 + 4y3 ? 3； 把工厂所有设备台时和资源都出租和出让 ，其收入应为：w = 8y1 + 16y2 + 12y3 。; 从工厂的决策者来看，当然希望 w 的值越大越好；但 从接受者的角度来看，他支付的越少越好。所以工厂决策 者只能在满足 ? 所有产品的单位利润条件下，使其总收入 尽可能地小，才能实现工厂决策者的意愿。为此需要解如 下的线性规划问题：; 根据上述例题可见，对于形如如下形式的线性规划问 题： ;二、对偶问题的经济解释——影子价格 设 B 是线性规划问题{Max Z = CTX | AX ? b ，X ? 0 } 的最优基，则该线性规划问题的最优解为 ( B-1b，0)T，其 对应的目标函数最优值则为：Z* = CTB-1b = (Y *)b ，其中 ： Y * = CTB-1 ( 我们称为单纯形乘子) 由此可得：;这说明，在其它条件不变的情况下，机器台时增加一台时 ，该厂按最优计划安排生产可多获利1.5元，原材料 A 每 增加一公斤，可多获利0.125元，原材料 B 每增加一公斤 ，对获利没有影响。;从上图我们可以看到：设备每增加一台时，代表约束 条件的直线就由 ? 移至 ? ? ，相应地最优解由点 A =(4，2) 移到点 B = (4，2.5)，目标函数值 Z = 2?4 + 3?2.5 = 15.5， 即比原来的增大1.5。又若原材料 A 增加一公斤，代表约 束条件的直线就由? 移至? ，相应地最优解由点 A =(4，2) 移到点B = (4.25，1.875)，目标函数值 Z = 2?4.25 +3?1.875 = 14.125，即比原来的增大0.125。原材料 B 增加一公斤时 ，该约束条件的直线由? 移至? ‘ ，这时的最优解不变。 yi 的值代表对第 i 种资源的估价。这种估价是针对具 体产品而存在的一种特殊价格，我们称它为“影子价格”。;在该厂现有资源和现有生产方案的条件下，设备的每小时 出租费为1.5元，一公斤原材料 A 的出让费为除成本外再 附加0.125元，一公斤原材料 B 可按原成本出让，这时该 厂的收入与自己组织生产时获利相等。影子价格随具体情 况而异。在完全市场经济的条件下，当某种资源的市场价 格低于影子价格时，企业应买进该资源用于扩大再生产； 而当某种资源的市场价格高于影子价格时，则企业的决策 者应把已有的资源卖出，这时企业的获利比由自己生产的 还高。可见，影子价格对市场有调节作用。 下面再从另一个角度来讨论该问题：;由于 -Y T = - CBTB-1 ，将此式两边同时右乘于b 得到： -Y Tb= -CBTB-1b 即： Y Tb= CBTB-1b = Z 综合1、2、3的讨论，我们可以得到另一个线性规划问 题： (2.2); 第二节 线性规划问题的对偶理论 以上讨论可以直观地了解到原线性规划问题与对偶问 题之间的关系，这一节将从理论上进一步讨论线性规划问 题的对偶问题。 2.1 原问题与对偶问题的关系 由第一节的讨论，如下形式的线性规划问题的