数据模型决策线性规划

线性规划的对偶问题例1：某公司利用现有三条生产线生产两种产品，有关数据如下表：设

Ⅰ产量–––––Ⅱ产量–––––问如何安排生产，使获利最多？产品甲产品乙每周可用量生产线一104小时生产线二0212小时生产线三3218小时产品利润3百元5百元一、对偶问题的提出例2.1*有一个中间商接到一批加工定单，需用到该公司的三条生产线,有意租用该公司的三条生产线全部可用时间，问中间商应如何出价，才能使公司觉得有利可图肯把设备出租，又使自己付出的租金最少？中间商

付出的代价最小出让代价应不低于用同等数量的资源自己生产的利润。对方能接受公司生产线一生产线二生产线三利润（百元）１０３３０２２５４时12时18时ⅠⅡD公司能接受的条件：中间商的意愿：出让代价应不低于用同等数量的资源自己生产的利润。设：生产线一—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软件求求解原原问题时时，程程序的的输出出结果果会给给出所所有的的对偶偶价格格资源单位消费产品甲乙资源限制钢材52170煤炭23100设备台时15150单位利润（万元）1018最优解解X*=(50/7，200/7)最优值值Z*=4100/7Y*=(0，32/7,6/7)对偶价价格对偶价价格（（影子子价格格）Y*=(0，32/7,6/7)钢材煤炭设备台时即再增增加1吨钢材材，利利润不不会增增加即再增增加1吨煤炭炭，利利润增增加3/7万元即再增增加1个台时时，利利润增增加6/7万元例:某公司司利用用现有有三条条生产产线生生产两两种产产品品，有有关数数据如如下表表：问如何何安排排生产产，使使获利利最多多？产品甲产品乙每周可用量资源单位成本生产线一104小时1百元/小时生产线二0212小时1百元/小时生产线三3218小时1百元/小时产品售价7百元9百元数学模模型一一：设甲产产量–––––––x1乙产量量–––––––––x2则生生产产一一个个单单位位甲甲产产品品获获利利润润7－1××1－3××1＝3（百百元元））则生生产产一一个个单单位位乙乙产产品品获获利利润润9－2××1－2××1＝5（百百元元））最优优解解X*=(2，6)最优优值值Z*=36Y*=(0,1.5,1)对偶偶价价格格最优优解解X*=(2,6,2,12,18)最优优值值Z*=36Y*=(1,2.5,2,0,1.5,1)对偶偶价价格格数学学模模型型二二：：设甲甲产产量量–––––––––x1乙产产量量–––––––––x2三条条生生产产线线实实际际利利用用时时间间分分别别为为x3,x4,x5小时时注意意：：从刚刚才才的的两两个个模模型型可可以以看看到到：：模型型一一中中的的对对偶偶价价格格（（影影子子价价格格））是是指指当当资资源源增增加加一一个个单单位位时时，，总总利利润润的的增增加加量量，，因因此此此此时时的的对对偶偶价价格格准准确确来来讲讲应应该该称称为为影子子利利润润。模型型二二中中的的前前三三个个对对偶偶价价格格，，是是指指当当资源源无无成成本本的的增增加加一一个个单单位位时时总总利利润润的的增增加加量量，它它们们反反映映了了资资源源在在系系统统内内的的真真正正价价值值，，因因此此他他们们才才是是真真正正意意义义上上的的影子子价价格格。例例如如第第二二个个对对偶偶价价格格2.5反映映了了第第二二种种资资源源在在系系统统内内的的真真正正价价值值是是250元，，比比其其成成本本100元要要大大150元，，因因此此增增加加一一个个单单位位的的第第二二种种资资源源，，利利润润增增加加150元。。影子子价价格格是是一一种种资资源源的的虚虚拟拟价价格格≠资源源的的市市场场价价格格,是根根据据资资源源在在生生产产中中作作出出的的贡贡献献而而作作出出的的估估价价，，它它实实际际上上是是一一种种机会会成成本本。为什什么么叫叫影影子子价价格格？？机会会成成本本是指指从从事事某某一一种种业业务务而而损损失失别别的的业业务务的的代代价价2、影影子子价价格格在在经经济济管管理理中中的的应应用用影子子价价格格越越大大的的资资源源，，表表明明：：这种种资资源源对对目目标标增增益益的的影影响响越越大大这种种资资源源对对该该企企业业越越稀稀缺缺、、贵贵重重影子子价价格格(影子子利利润润)为零零的的资资源源，，表表明明：：这种种资资源源对对该该企企业业来来说说相相对对富富裕