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

1、线性规划的对偶问题,例1：某公司利用现有三条生产线生产两种 产品，有关数据 如下表：,设 产量 产量,问如何安排生产，使获利最多？,一、对偶问题的提出,例2.1* 有一个中间商接到一批加工定单，需用到该公司的三条生产线,有意租用该公司的三条生产线全部可用时间，问中间商应如何出价，才能使公司觉得有利可图肯把设备出租，又使自己付出的租金最少？,中 间 商,付出的代价最小,出让代价应不低于 用同等数量的资源 自己生产的利润。,对方能接受,公 司,公司能接受的条件： 中间商的意愿：,出让代价应不低于 用同等数量的资源 自己生产的利润。,设：生产线一 Y1百元时,生产线二 y2百元 时,生产线三y3百元

2、时,对 偶 问 题,原 问 题,中 间 商,公 司,一对对偶问题,设原线性规划问题为：,则称下面的线性规划问题：,为其对偶规划，,二、原问题与对偶问题的对应关系,1：定义,表中间的数(aij)的每一行与xj对应地乘起来相加后不大于这一行右边的数bi，就是原问题的一个约束条件。最后一行cj 与xj 对应地乘起来相加就是原问题的目标函数。类似地，把(aij)的每一列与yi 对应地乘起来相加后不小于cj 就是对偶问题的一个约束条件。最后一列与yj 对应地乘起来相加就是目标函数。,所求对偶问题为：,化为定义中的形式,对偶规划问题（D）为,对偶规划问题（D）为,对偶规划问题（D）为：,对偶规划问题（D）

3、为：,原问题（P）,对偶问题（D）,变量约束：,方程约束：,变量,方程,变量无限制,方程=,变量,方程,方程约束：,变量约束：,方程=,变量无限制,方程,变量,方程,变量,重要结论,、若原问题存在最优解，则其对偶问题一定存在最优解，且有相同的最优值,1、对偶问题的对偶就是原问题。 （即互为对偶规划）,练习：,（P）与(D)的关系对应表：,目标函数max,目标函数min,目标函数系数,约束方程常数列,约束方程常数列,目标函数系数,变量个数n,约束方程个数n,约束方程个数m,变量个数m,约束方程,变量0,0,=,无符号约束,变量0,约束方程,0,无符号约束,=,系数矩阵A,对偶解的经济意义 -影子

4、价格,资源的合理利用问题：,资源,单位 消费,产品,资源 限制,单位 利润,还有现金，问应该投资何种资源？,决策依据：,比较第i种资源增加一个单位，其余资源不增加时利润的增加值是否为正。,决策依据： 在取得最优方案的前提下,比较第i种资源增加一个单位，其余资源不增加时利润的增加值,设 是最优解，Z*是最优值,设其最优解,最优值为*,则Z*,此时原问题变为,最优值为* 此时目标函数的增量是 *-*,此时由于该对偶问题可行域没发生变化，目标函数中第i个系数改变很小，所以可以假设其最优解没有变化，则还是最优解，设 此时最优值为*,则 Z* *,此时对偶问题变为,Z*,第i种资源增加一个单位，其余资源

5、不增加时利润的增加值正好是原问题的对偶问题最优解的第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万元,例:某公司利用现有三条生产线生产两种 产品，有关数据如下表：,问如何安排生产，使获利最多？,数学模型一：设甲产

6、量 x1 乙产量x2 则生产一个单位甲产品获利润711313（百元） 则生产一个单位乙产品获利润921215（百元）,最优解 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、影子价格在经济管理中的应用,影子价格越大的资源，表明：,这种资源对目标增益的影响越大,这种资源对该企业 越稀缺、贵重,