第5讲 对偶问题与敏感分析.ppt

对偶问题引例 生产计划问题：某厂计划安排生产A，B两种产品，已知生产单位产品的利润与所需的劳动力，设备台时及原材料的消耗如图所示。问应该如何安排生产获利最大？ 原问题的LP模型 生产计划问题： 对偶问题的提出 资源定价问题：假设该工厂决定不生产产品A和B，而将其所有资源（劳动力、设备、原材料）出租或外售，那么每种资源应该如何定价？ 构造如下的数学模型：设y1,y2,y3分别表示出租单位劳动力，单位设备台时的租金和单位原材料的附加收入（附加收入额=出售价格-成本）， 明显地，出租和出让资源所得到的收入应该不低于用这些资源进行生产所得到的利润。 具体地说。若用9单位劳动力，4单位设备台时和3单位原材料可以生产1单位产品A而获利70元，那么就应有： 9 y1 + 4 y2 + 3 y3 ≥70 资源最优定价模型 同理，若用4单位劳动力，5单位设备台时和10单位原材料可以生产1单位产品B而获利120元，那么就应有： 4 y1 + 5 y2 + 10 y3 ≥120 将所有资源都出租和出让的总收入为ω= 360 y1 + 200 y2 + 300y3 ，在保证出租总收入不会比自己生产获利少的前提下，为了使工厂的竞争能力达到最大，应该极小化总收入ω，为此需要求解以下线性规划问题： min ω= 360 y1 + 200 y2 + 300 y3 S.t. 9 y1 + 4 y2 + 3 y3 ≥70 4 y1 + 5 y2 + 10 y3 ≥120 y1 ≥0 , y2 ≥0, y3 ≥0 原问题与对偶问题 为了提高工厂的经济效益，从两个不同角度出发而形成了一对线性规划问题，我们把资源定价问题称为是生产计划问题的对偶问题，二者模型比较如下： 对偶问题的基本性质 关于对偶问题 1. 对偶问题的一般形式； 2.对偶关系对应表； 3.由原问题(Primal)得出对偶问题(Dual)例。 对偶问题的基本性质 1. 对称性 ：原问题与对偶问题互为对偶问题。 2. 弱对偶性：求max问题的一切可行解的目标函数值 不超过求min问题一切可行解的目标函数值。 原问题与对偶问题 3. 无界性： 若其中一个问题无界，则另一个问题无 可行解。 4. 对偶定理：若其中一个问题有最优解，则另一个问题也有最优解，并且二者的目标函数最优值相等。 对偶最优解的经济解释 影子价格：在其他条件不变的情况下，第i种资源的限额bi增加一个单位所引起的目标函数最优值的改进量称为该资源的影子价格。 影子价格（shadow price）不是资源的市场价格而是一种边际价格，是根据资源在生产中的贡献而作的估价，也是一种动态价格。 对偶最优解的意义就在于它是各资源的影子价格。 关于影子价格 影子价格的大小反映了资源的稀缺程度，在最优利用条件下面，如果某资源有剩余，尽管它有实实在在的市场价格，但是它的影子价格却必定为零。如果某资源是稀缺资源，它的影子价格必定大于零。（为什么？） 当约束条件右端是可用资源的数量时，影子价格可以表示增加1单位资源企业所能够额外付出的最大资金。 影子价格的作用 影子价格是当系统达到最优状态时对资源价值的一种估价，并非资源的市场价格。它可提供以下信息： （1）增加何种资源对提高经济效益最有利？ （2）增加资源的代价多大才合算？ （3）新产品如何定价？ （4）产品价格变动时资源稀缺程度的变化。 （5）工艺改变后对资源节约的效益。 灵敏度分析 线性规划的灵敏度分析又称为敏感性分析，是从动态角度来讨论线性规划问题，即考虑模型中各系数aij, bi, cj等变化时对于最优解的影响。 灵敏度分析主要有以下两个方面的问题： （1）当这些参数中的一个或几个发生变化时，最优解会有什么变化？ （2）要使最优解不发生变化，这些系数的变化范围如何？ 百分之百法则 百分之百法则：定义“可行增加”是指系数的最大增量不超过最优范围的上限， “可行减少”是指系数的最大减少量不超过最优范围的下限。 对于所有变化的目标函数系数，如果没有超过可行增加和可行减少的范围，则最优解不变。 对于所有变化的约束条件右端的值，如果没有超过可行增加和可行减少的范围，则对偶价格不变。 求解和分析的例（数据） 例：生产数据如下： 某工厂有9台磨床和6台钻床，采用研磨和钻孔两种加工工艺生产5种产品P1，P2，P3，P4，P5，