运筹学0903对偶规划.ppt

《运筹学0903对偶规划.ppt》由会员分享，可在线阅读，更多相关《运筹学0903对偶规划.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、管理运筹学管理运筹学-管理科学方法管理科学方法中国人民大学出版社OM:SM2第第3 章章 对偶规划对偶规划Sub titleSub title学习要点 理解线性规划问题的对偶问题理解线性规划问题的对偶问题 构建线性规划问题的对偶模型构建线性规划问题的对偶模型 正确理解对偶规划的基本性质正确理解对偶规划的基本性质 掌握影子价值的涵义及其应用掌握影子价值的涵义及其应用 资源总存量和分配量增减决策资源总存量和分配量增减决策OM:SM3第一节第一节 对偶规划的数学模型对偶规划的数学模型一、对偶问题的提出一、对偶问题的提出若若例例1 1中中该该厂厂的的产产品品平平销销，现现有有另另一一企企业业想想租租赁

2、赁其其设设备备。厂厂方方为为了了在在谈谈判判时时心心中中有有数数，需需掌掌握握设设备备台台时时费费用用的的最最低低价价码码，以以便衡量对方出价，对出租与否做出抉择。便衡量对方出价，对出租与否做出抉择。在在这这个个问问题题上上厂厂长长面面临临着着两两种种选选择择：自自行行生生产产或或出出租租设设备备。首首先要弄清两个问题：先要弄清两个问题：合理安排生产能取得多大利润合理安排生产能取得多大利润?为保持利润水平不降低，资源转让的最低价格是多少？为保持利润水平不降低，资源转让的最低价格是多少？问题问题 的最优解：的最优解：x1=4，x2=5，Z*=37。OM:SM4第一节第一节 对偶规划的数学模型对偶

3、规划的数学模型一、对偶问题的提出一、对偶问题的提出出让定价出让定价假设出让假设出让A、B、C设备所得利润分别为设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有自行生产带来的利润，否则宁愿自己生产。于是有 2y1+0y2+3y3 3同理，对乙产品而言，则有同理，对乙产品而言，则有 0y1+2y2+4y3 5设备台时出让的收益（希望出让的收益最少值）设备台时出让的收益（希望出让的收益最少值）min 16y1+10y2+32y3显然还有显然还有 y1，y2，y30OM:SM5

4、第一节第一节 对偶规划的数学模型对偶规划的数学模型一、对偶问题的提出一、对偶问题的提出例例1 1的对偶问题的数学模型的对偶问题的数学模型对偶问题的最优解：对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=37两个问题的目标函数值相等并非偶然两个问题的目标函数值相等并非偶然前者称为线性规划原问题，则后者为对偶问题，反之亦然。前者称为线性规划原问题，则后者为对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基变对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。量的检验数的负值。min =16y1+10y2+32y3 2y1+0y2+3y3 3 0y

5、1+2y2+4y3 5 y1，y2，y30 S.t.maxZ=3x1+5 x2 2x1 16 2x2 10 3x1+4 x2 32 x1,x2 0S.t.OM:SM6OM:SM7OM:SM8OM:SM9例：写出线性规划问题的对偶规划例：写出线性规划问题的对偶规划OM:SM10第一节第一节 对偶规划的数学模型对偶规划的数学模型二、对偶规划的性质二、对偶规划的性质1 1、对称性定理、对称性定理 对偶问题的对偶问题是原问题。对偶问题的对偶问题是原问题。根据对偶规划，很容易写出对偶问题的对偶问题模型。根据对偶规划，很容易写出对偶问题的对偶问题模型。2 2、最优性定理最优性定理 设设 ，分别为原问题和对

6、偶问题的可行解，且分别为原问题和对偶问题的可行解，且 则则 ，分别为各自的最优解。分别为各自的最优解。3.3.对偶性定理对偶性定理 若原问题有最优解，那么对偶问题也有最优解，而且若原问题有最优解，那么对偶问题也有最优解，而且 两者的目标函数值相等两者的目标函数值相等。4.4.互补松弛性互补松弛性 最优解的充分必要条件是最优解的充分必要条件是 ，OM:SM11OM:SM12OM:SM13OM:SM14OM:SM15OM:SM16OM:SM17OM:SM18OM:SM19OM:SM20OM:SM21第二节第二节 对偶规划的经济解释对偶规划的经济解释一、影子价值的内涵一、影子价值的内涵左边是资源左边

7、是资源bi每增加一个单位对目标函数每增加一个单位对目标函数Z的贡献；的贡献；对偶变量对偶变量 yi在经济上表示原问题第在经济上表示原问题第i种资源的种资源的边际价值边际价值边际价值边际价值。对偶变量的值对偶变量的值 yi*表示第表示第i种资源的边际价值，称为种资源的边际价值，称为影子价值影子价值影子价值影子价值。若原问题价值系数若原问题价值系数Cj表示单位产值，则表示单位产值，则yi 称为称为影子价格影子价格影子价格影子价格。若原问题价值系数若原问题价值系数Cj表示单位利润，则表示单位利润，则yi 称为称为影子利润影子利润影子利润影子利润。OM:SM22OM:SM23OM:SM24OM:SM2

8、5生产计划问题生产计划问题例例例例2 2 2 2.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备设备A A、B B加工，最后都需在设备加工，最后都需在设备C C上装配。经测算得到相关数据如表上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。所示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为据市场分析，单位甲乙产品的销售价格分别为7373和和7575元，试确定元，试确定获利最大的产品生产计划。获利最大的产品生产计划。产品产品设备设备工时消耗工时消耗甲甲 乙乙工时成本工时成本

9、元元/h生产能力生产能力hABC 2 0 0 2 3 4201510161032OM:SM26OM:SM27对对偶偶问问题题OM:SM28原原问问题题是是以以利利润润为为目目标标，对对偶偶变变量量 yi则则定定义义为为资资源源bi每每增增加加一一个单位对利润的贡献程度，称为资源的个单位对利润的贡献程度，称为资源的 影子影子利润利润利润利润；Y1=0,Y1=0,说明设备说明设备说明设备说明设备A A的工时增加并不影响利润的工时增加并不影响利润的工时增加并不影响利润的工时增加并不影响利润 Y2=0.5Y2=0.5说明设备说明设备说明设备说明设备 B B的工时每增加的工时每增加的工时每增加的工时每增

10、加1 1小时，则使利润增加小时，则使利润增加小时，则使利润增加小时，则使利润增加0.50.5元。元。元。元。最最优优解解哪些是非瓶颈资源和瓶颈资源？哪些是非瓶颈资源和瓶颈资源？OM:SM29影子价格影子价格影子价格影子价格=资源成本资源成本资源成本资源成本+影子利润影子利润影子利润影子利润影影影影子子子子价价价价格格格格并并并并不不不不是是是是资资资资源源源源的的的的实实实实际际际际价价价价格格格格，而而而而是是是是企企企企业业业业内内内内部部部部资资资资源源源源的的的的配配配配比比比比价价价价格格格格，是是是是由由由由企企企企业业业业内内内内部部部部资资资资源源源源的的的的配配配配置置置置状

11、状状状况况况况决决决决定定定定的，并不是由市场来决定的的，并不是由市场来决定的的，并不是由市场来决定的的，并不是由市场来决定的影子价格的应用影子价格的应用影子价格的应用影子价格的应用1.1.影子价格与市场价格对比：影子价格与市场价格对比：影子价格与市场价格对比：影子价格与市场价格对比：成本：成本：成本：成本：A A：2020元元元元/小时小时小时小时 B B：15 C15 C：1010市场：市场：市场：市场：A:21;B:15;C:12A:21;B:15;C:12OM:SM30影子价格的应用影子价格的应用影子价格的应用影子价格的应用2.2.增加哪一种资源对增加经济效益有利增加哪一种资源对增加经

12、济效益有利增加哪一种资源对增加经济效益有利增加哪一种资源对增加经济效益有利3.3.告诉经营者一怎样的代价去取得稀缺资源告诉经营者一怎样的代价去取得稀缺资源告诉经营者一怎样的代价去取得稀缺资源告诉经营者一怎样的代价去取得稀缺资源4.4.是是是是一一一一种种种种机机机机会会会会成成成成本本本本，提提提提示示示示企企企企业业业业设设设设备备备备出出出出租租租租或或或或原原原原材材材材料料料料的的的的转让的基价转让的基价转让的基价转让的基价5.5.知道新产品的定价与投产决策知道新产品的定价与投产决策知道新产品的定价与投产决策知道新产品的定价与投产决策6.6.分析工艺改变后对资源节约的收益分析工艺改变后

13、对资源节约的收益分析工艺改变后对资源节约的收益分析工艺改变后对资源节约的收益7.7.分析现有产品价格变动时对资源紧缺的影响分析现有产品价格变动时对资源紧缺的影响分析现有产品价格变动时对资源紧缺的影响分析现有产品价格变动时对资源紧缺的影响OM:SM31最最优优解解OM:SM32 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 2x1 +x3 =16 2x2 +x4 =10 3x1+4 x2 +x5=32 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8OM:SM33

14、162010050101/2012300-21x3x2x5050300-5/205-4Cj比比值值CBXBb检验数检验数 jx1x2x3x4x535000检验数检验数 j80014/3-2/350101/204100-2/31/3x3x2x1053000-1/2-1最优解最优解:X*=(4,5,8,0,0)T，Z*=37OM:SM34OM:SM35OM:SM36OM:SM37OM:SM38OM:SM39OM:SM40OM:SM41OM:SM42OM:SM43二、右端常量的变动分析二、右端常量的变动分析 参数参数bi的变化范围的变化范围 第r个约束的右端项为br，增量br，其它数据不变。新的基解

15、为只要XB0，则可保持最优基不变。OM:SM44二、约束方程中常数项的灵敏度分析二、约束方程中常数项的灵敏度分析 从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中优解中S2=50是基变量，即为，原料是基变量，即为，原料A有有50千克没用完，再增加千克没用完，再增加A原料是不会增原料是不会增加利润的，加利润的，A的对偶价格为的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为对偶价格为0。迭代次数基变量CBX1 X2 S1 S2 S3b50

16、 100 0 0 02X1501 0 1 0 -150 S200 0 -2 1 150 X21000 1 0 0 1250 ZJ50 100 50 0 5027500CJ-ZJ0 0 -50 0 -50OM:SM45OM:SM46OM:SM47OM:SM48OM:SM49第二节第二节 对偶规划的经济解释对偶规划的经济解释一、影子价值的内涵一、影子价值的内涵影子价格不是资源的实际价格，反映了资源配置结构，影子价格不是资源的实际价格，反映了资源配置结构，其它数据固定，某资源增加一单位导致目标函数的增量。其它数据固定，某资源增加一单位导致目标函数的增量。对资源对资源i总存量的评估：总存量的评估：购进

17、购进购进购进 or 出让出让出让出让对资源对资源i当前分配量的评估：当前分配量的评估：增加增加增加增加 or 减少减少减少减少第一，影子利润说明增加哪种资源对经济效益最有利第一，影子利润说明增加哪种资源对经济效益最有利第二，影子价格告知以怎样的代价去取得紧缺资源第二，影子价格告知以怎样的代价去取得紧缺资源第三，影子价格是机会成本，提示资源出租第三，影子价格是机会成本，提示资源出租/转让的基价转让的基价第四，利用影子价格分析新品的资源效果：定价决策第四，利用影子价格分析新品的资源效果：定价决策第五，利用影子价格分析现有产品价格变动的资源紧性第五，利用影子价格分析现有产品价格变动的资源紧性第六，可

18、以帮助分析工艺改变后对资源节约的收益第六，可以帮助分析工艺改变后对资源节约的收益第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺OM:SM50OM:SM51OM:SM52OM:SM53OM:SM54OM:SM55第三节第三节 资源定价的决策方案资源定价的决策方案例：例：某厂生产甲、乙两种产品，生产单位产品的资源消耗如某厂生产甲、乙两种产品，生产单位产品的资源消耗如下表所示。下表所示。问如何安排甲、乙两产品的产量，使每周的利润为最大。如问如何安排甲、乙两产品的产量，使每周的利润为最大。如果企业可以不生产，那资源出让如何定价果企业可以不生产，那资源出

19、让如何定价甲乙资源成本资源拥有量原材料 (kg)设备 (工时)电力 (度)943451020501360200300销售价格（元）390352OM:SM56第三节第三节 资源定价的决策方案资源定价的决策方案一、最优生产决策一、最优生产决策决策变量决策变量：要确定甲、乙两种产品的产量，我们设每周生产要确定甲、乙两种产品的产量，我们设每周生产的甲产品的产量的甲产品的产量x1，每周生产的乙产品的产量，每周生产的乙产品的产量 x2。由上表计算单位甲产品的成本为由上表计算单位甲产品的成本为383元，单位乙产品的成本元，单位乙产品的成本为为340元，则它们的盈利能力分别为元，则它们的盈利能力分别为7和和1

20、2。生产计划的线性规划模型：生产计划的线性规划模型：OM:SM57第三节第三节 资源定价的决策方案资源定价的决策方案二、资源获利决策二、资源获利决策如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产这两种产品的原材料、设备工时、电量资源全部出售给外单位，这两种产品的原材料、设备工时、电量资源全部出售给外单位，或者做代加工，则应如何确定这三种资源的价格。或者做代加工，则应如何确定这三种资源的价格。设原材料的单位出让获利为设原材料的单位出让获利为y1，设备工时的单位出让获利为，设备工时的单位出让获利为y3，电量的单位出让获利为，电量的单位出让获利为y2。出让决策的线性规划模型：出让决策的线性规划模型：