《数据模型决策01线性规划2PPT30页》由会员分享，可在线阅读，更多相关《数据模型决策01线性规划2PPT30页（29页珍藏版）》请在金锄头文库上搜索。
1、线性规划的对偶问题1例例1：某公司利用现有三条生产线生产两种：某公司利用现有三条生产线生产两种 产品，有关数据产品，有关数据 如下表：如下表：设设 产量产量 产量产量问如何安排生产，使获利最多？问如何安排生产，使获利最多？产品甲产品甲产品乙产品乙每周可用量每周可用量生产线一104小时生产线二0212小时生产线三3218小时产品利润3百元5百元一、对偶问题的提出一、对偶问题的提出2例2.1* 有一个中间商接到一批加工定单，需用到该公司的三条生产线,有意租用该公司的三条生产线全部可用时间，问中间商应如何出价，才能使公司觉得有利可图肯把设备出租，又使自己付出的租金最少？ 中中间间商商 付出的代价最小
2、付出的代价最小出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。对方能接受对方能接受公公司司3生产线一生产线一生产线二生产线二生产线三生产线三利润（百元）利润（百元）时时12时时 18时时D公司能接受的条件：公司能接受的条件：中间商的意愿：中间商的意愿：出让代价应不低于出让代价应不低于用同等数量的资源用同等数量的资源自己生产的利润。自己生产的利润。设：生产线一设：生产线一 Y1Y1百元时百元时, ,生产线二生产线二 y2百元百元时时, ,生产线三生产线三y y3 3百元百元时时4对对偶偶问问题题原原问问题题中中间间商商公公司司一对对偶问题一对对偶问
3、题5设原线性规划问题为：则称下面的线性规划问题：为其对偶规划，二、原问题与对偶问题的对应关系二、原问题与对偶问题的对应关系1：定义6表中间的数(aij)的每一行与xj对应地乘起来相加后不大于这一行右边的数bi，就是原问题的一个约束条件。最后一行cj 与xj 对应地乘起来相加就是原问题的目标函数。类似地，把(aij)的每一列与yi 对应地乘起来相加后不小于cj 就是对偶问题的一个约束条件。最后一列与yj 对应地乘起来相加就是目标函数。7所求对偶问题为：8化为定义中的形式910对偶规划问题（D）为11对偶规划问题（D）为对偶规划问题（D）为：12对偶规划问题（D）为：原问题（P）对偶问题（D）变量
4、约束：方程约束：变量方程变量无限制方程=变量方程方程约束：变量约束：方程=变量无限制方程变量方程变量13重要结论、若原问题存在最优解，则其对偶问题一定存若原问题存在最优解，则其对偶问题一定存在最优解，且有相同的最优值在最优解，且有相同的最优值1、对偶问题的对偶就是原问题对偶问题的对偶就是原问题。 （即互为对偶规划）14练习：（P）与(D)的关系对应表： 原问题 对偶问题目标函数max目标函数min目标函数系数约束方程常数列约束方程常数列 目标函数系数变量个数n约束方程个数n约束方程个数m变量个数m约束方程变量00=无符号约束变量0约束方程0无符号约束=系数矩阵A15对偶解的经济意义 -影子价格
5、16资源的合理利用问题：资源单位消费产品资源限制单位利润还有现金，问应该投资何种资源？决策依据： 比较第i种资源增加一个单位，其余资源不增加时利润的增加值是否为正。17决策依据：在取得最优方案的前提下比较第i种资源增加一个单位，其余资源不增加时利润的增加值设 是最优解，Z*是最优值设其最优解最优值为*则Z*18此时原问题变为最优值为*此时目标函数的增量是*-*19此时由于该对偶问题可行域没发生变化，目标函数中第i个系数改变很小，所以可以假设其最优解没有变化，则还是最优解，设此时最优值为*则 Z* *此时对偶问题变为Z*第i种资源增加一个单位，其余资源不增加时利润的增加值正好是原问题的对偶问题最
6、优解的第i个分量对偶价格对偶价格20边际价格1、对偶价格的定义对偶价格也称为影子价格影子价格，在用lingo软件求解原问题时，程序的输出结果会给出所有的对偶价格21资源单位消费产品甲乙资源限制钢材52170煤炭23100设备台时15150单位利润（万元）1018最优解X*=(50/7，200/7)最优值Z*=4100/7Y*=(0，32/7,6/7)对偶价格22对偶价格（影子价格）Y*=(0，32/7,6/7)钢材煤炭设备台时即再增加1吨钢材，利润不会增加即再增加1吨煤炭，利润增加3/7万元即再增加1个台时，利润增加6/7万元23例例:某公司利用现有三条生产线生产两种某公司利用现有三条生产线生
7、产两种 产品，有产品，有关数据如下表：关数据如下表：问如何安排生产，使获利最多？问如何安排生产，使获利最多？产品甲产品甲产品乙产品乙每周可用量每周可用量资源单位成本资源单位成本生产线一104小时1百元/小时生产线二0212小时1百元/小时生产线三3218小时1百元/小时产品售价7百元9百元24数学模型一：设甲产量 x1 乙产量x2则生产一个单位甲产品获利润711313（百元）则生产一个单位乙产品获利润921215（百元）最优解X*=(2，6)最优值Z*=36Y*=(0,1.5,1)对偶价格25最优解X*=(2,6,2,12,18)最优值Z*=36Y*=(1,2.5,2,0,1.5,1)对偶价格
8、数学模型二：设甲产量 x1 乙产量x2三条生产线实际利用时间分别为 x3,x4,x5小时26注意：从刚才的两个模型可以看到：n模型一中的对偶价格（影子价格）是指当资源增加一个单位时，总利润的增加量，因此此时的对偶价格准确来讲应该称为影子利润影子利润。n模型二中的前三个对偶价格，是指当资源无成本资源无成本的增加一个单位时总利润的增加量的增加一个单位时总利润的增加量，它们反映了资源在系统内的真正价值，因此他们才是真正意义上的影子价格影子价格。例如第二个对偶价格 2.5 反映了第二种资源在系统内的真正价值是250元，比其成本100元要大 150 元，因此增加一个单位的第二种资源，利润增加150元。27影子价格是一种资源的虚拟价格资源的市场价格,是根据资源在生产中作出的贡献而作出的估价，它实际上是一种机会成本机会成本。机会成本机会成本是指从事某一种业务而损失别的业务的代价 282、影子价格在经济管理中的应用影子价格越大的资源，表明：这种资源对目标增益的影响越大这种资源对该企业 越稀缺、贵重影子价格(影子利润)为零的资源，表明：这种资源对该企业来说相对富裕决策者：将本企业资源的影子价格与当时的市场价格进行比较采用的决策：若某种资源的影子价格市场价格-卖出若某种资源的影子价格市场价格-买进29
