数据模型决策01线性规划2（PPT30页).ppt

线性规划的对偶问题 例1 某公司利用现有三条生产线生产两种产品 有关数据如下表 设 产量 产量 问如何安排生产 使获利最多 一 对偶问题的提出 例2 1 有一个中间商接到一批加工定单 需用到该公司的三条生产线 有意租用该公司的三条生产线全部可用时间 问中间商应如何出价 才能使公司觉得有利可图肯把设备出租 又使自己付出的租金最少 中间商 付出的代价最小 出让代价应不低于用同等数量的资源自己生产的利润 对方能接受 公司 公司能接受的条件 中间商的意愿 出让代价应不低于用同等数量的资源自己生产的利润 设 生产线一 Y1百元 时 生产线二 y2百元 时 生产线三 y3百元 时 对偶问题 原问题 中间商 公司 一对对偶问题 设原线性规划问题为 则称下面的线性规划问题 为其对偶规划 二 原问题与对偶问题的对应关系 1 定义 表中间的数 aij 的每一行与xj对应地乘起来相加后不大于这一行右边的数bi 就是原问题的一个约束条件 最后一行cj与xj对应地乘起来相加就是原问题的目标函数 类似地 把 aij 的每一列与yi对应地乘起来相加后不小于cj就是对偶问题的一个约束条件 最后一列与yj对应地乘起来相加就是目标函数 所求对偶问题为 化为定义中的形式 对偶规划问题 D 为 对偶规划问题 D 为 对偶规划问题 D 为 对偶规划问题 D 为 原问题 P 对偶问题 D 变量约束 方程约束 变量 方程 变量无限制 方程 变量 方程 方程约束 变量约束 方程 变量无限制 方程 变量 方程 变量 重要结论 若原问题存在最优解 则其对偶问题一定存在最优解 且有相同的最优值 1 对偶问题的对偶就是原问题 即互为对偶规划 练习 P 与 D 的关系对应表 目标函数max 目标函数min 目标函数系数 约束方程常数列 约束方程常数列 目标函数系数 变量个数n 约束方程个数n 约束方程个数m 变量个数m 约束方程 变量 0 0 无符号约束 变量 0 约束方程 0 无符号约束 系数矩阵A 对偶解的经济意义 影子价格 资源的合理利用问题 资源 单位消费 产品 资源限制 单位利润 还有现金 问应该投资何种资源 决策依据 比较第i种资源增加一个单位 其余资源不增加时利润的增加值是否为正 决策依据 在取得最优方案的前提下 比较第i种资源增加一个单位 其余资源不增加时利润的增加值 设是最优解 Z 是最优值 设其最优解 最优值为 则Z 此时原问题变为 最优值为 此时目标函数的增量是 此时由于该对偶问题可行域没发生变化 目标函数中第i个系数改变很小 所以可以假设其最优解没有变化 则还是最优解 设此时最优值为 则Z 此时对偶问题变为 Z 第i种资源增加一个单位 其余资源不增加时利润的增加值正好是原问题的对偶问题最优解的第i个分量对偶价格 边际价格 1 对偶价格的定义 对偶价格也称为影子价格 在用lingo软件求解原问题时 程序的输出结果会给出所有的对偶价格 资源 单位消费 产品 最优解X 50 7 200 7 最优值Z 4100 7 Y 0 32 7 6 7 对偶价格 对偶价格 影子价格 Y 0 32 7 6 7 即再增加1吨钢材 利润不会增加 即再增加1吨煤炭 利润增加3 7万元 即再增加1个台时 利润增加6 7万元 例 某公司利用现有三条生产线生产两种产品 有关数据如下表 问如何安排生产 使获利最多 数学模型一 设甲产量 x1乙产量 x2则生产一个单位甲产品获利润7 1 1 3 1 3 百元 则生产一个单位乙产品获利润9 2 1 2 1 5 百元 最优解X 2 6 最优值Z 36 Y 0 1 5 1 对偶价格 最优解X 2 6 2 12 18 最优值Z 36 Y 1 2 5 2 0 1 5 1 对偶价格 数学模型二 设甲产量 x1乙产量 x2三条生产线实际利用时间分别为x3 x4 x5小时 注意 从刚才的两个模型可以看到 模型一中的对偶价格 影子价格 是指当资源增加一个单位时 总利润的增加量 因此此时的对偶价格准确来讲应该称为影子利润 模型二中的前三个对偶价格 是指当资源无成本的增加一个单位时总利润的增加量 它们反映了资源在系统内的真正价值 因此他们才是真正意义上的影子价格 例如第二个对偶价格2 5反映了第二种资源在系统内的真正价值是250元 比其成本100元要大150元 因此增加一个单位的第二种资源 利润增加150元 影子价格是一种资源的虚拟价格 资源的市场价格 是根据资源在生产中作出的贡献而作出的估价 它实际上是一种机会成本 为什么叫影子价格 机会成本是指从事某一种业务而损失别的业务的代价 2 影子价格在经济管理中的应用 影子价格越大的资源 表明 这种资源对目标增益的影响越大 这种资源对该企业越稀缺 贵重 影子