运筹学对偶规划.pptx

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

1、1第一节第一节 对偶规划的数学模型对偶规划的数学模型一、对偶问题的提出一、对偶问题的提出若例1中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：合理安排生产能取得多大利润?为保持利润水平不降低，资源转让的最低价格是多少？问题 的最优解：x1=4，x2=5，Z*=37。第1页/共56页2第一节第一节 对偶规划的数学模型对偶规划的数学模型一、对偶问题的提出一、对偶问题的提出出让定价假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于

2、生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有 2y1+0y2+3y3 3同理，对乙产品而言，则有 0y1+2y2+4y3 5设备台时出让的收益（希望出让的收益最少值）min 16y1+10y2+32y3显然还有 y1，y2，y30第2页/共56页3第一节第一节 对偶规划的数学模型对偶规划的数学模型一、对偶问题的提出一、对偶问题的提出例1的对偶问题的数学模型对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=37两个问题的目标函数值相等并非偶然前者称为线性规划原问题，则后者为对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量

3、的检验数的负值。min=16y1+10y2+32y3 2y1+0y2+3y3 3 0y1+2y2+4y3 5 y1，y2，y30 S.t.maxZ=3x1+5 x2 2x1 16 2x2 10 3x1+4 x2 32 x1,x2 0S.t.第3页/共56页4第4页/共56页5第5页/共56页6第6页/共56页7例：写出线性规划问题的对偶规划第7页/共56页8第一节第一节 对偶规划的数学模型对偶规划的数学模型二、对偶规划的性质二、对偶规划的性质1、对称性定理 对偶问题的对偶问题是原问题。根据对偶规划，很容易写出对偶问题的对偶问题模型。2、最优性定理 设 ，分别为原问题和对偶问题的可行解，且 则

4、，分别为各自的最优解。3.对偶性定理 若原问题有最优解，那么对偶问题也有最优解，而且 两者的目标函数值相等。4.互补松弛性 最优解的充分必要条件是 ，第8页/共56页9第9页/共56页10第10页/共56页11第11页/共56页12第12页/共56页13第13页/共56页14第14页/共56页15第15页/共56页16第16页/共56页17第17页/共56页18第18页/共56页19第二节第二节 对偶规划的经济解释对偶规划的经济解释一、影子价值的内涵一、影子价值的内涵左边是资源bi每增加一个单位对目标函数Z的贡献；对偶变量 yi在经济上表示原问题第i种资源的边际价值边际价值。对偶变量的值 yi

5、*表示第i种资源的边际价值，称为影子价值影子价值。若原问题价值系数Cj表示单位产值，则yi 称为影子价格影子价格。若原问题价值系数Cj表示单位利润，则yi 称为影子利润影子利润。第19页/共56页20第20页/共56页21第21页/共56页22第22页/共56页23生产计划问题生产计划问题例例2 2.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。产品产品设备设备工时消耗工时消耗甲甲 乙乙工时成本工时

6、成本元元/h生产能力生产能力hABC 2 0 0 2 3 4201510161032第23页/共56页24第24页/共56页25对对偶偶问问题题第25页/共56页26原问题是以利润为目标，对偶变量 yi则定义为资源bi每增加一个单位对利润的贡献程度，称为资源的 影子利润利润；Y1=0,Y1=0,说明设备说明设备A A的工时增加并不影响利润的工时增加并不影响利润 Y2=0.5Y2=0.5说明设备说明设备 B B的工时每增加的工时每增加1 1小时，则使利润增加小时，则使利润增加0.50.5元。元。最最优优解解哪些是非瓶颈资源和瓶颈资源？哪些是非瓶颈资源和瓶颈资源？第26页/共56页27影子价格影子

7、价格=资源成本资源成本+影子利润影子利润影影子子价价格格并并不不是是资资源源的的实实际际价价格格，而而是是企企业业内内部部资资源源的的配配比比价价格格，是是由由企企业业内内部部资资源源的的配配置置状状况况决决定定的，并不是由市场来决定的的，并不是由市场来决定的影子价格的应用影子价格的应用1.1.影子价格与市场价格对比：影子价格与市场价格对比：成本：成本：A A：2020元元/小时小时 B B：15 C15 C：1010市场：市场：A:21;B:15;C:12A:21;B:15;C:12第27页/共56页28影子价格的应用影子价格的应用2.2.增加哪一种资源对增加经济效益有利增加哪一种资源对增加

8、经济效益有利3.3.告诉经营者一怎样的代价去取得稀缺资源告诉经营者一怎样的代价去取得稀缺资源4.4.是是一一种种机机会会成成本本，提提示示企企业业设设备备出出租租或或原原材材料料的的转让的基价转让的基价5.5.知道新产品的定价与投产决策知道新产品的定价与投产决策6.6.分析工艺改变后对资源节约的收益分析工艺改变后对资源节约的收益7.7.分析现有产品价格变动时对资源紧缺的影响分析现有产品价格变动时对资源紧缺的影响第28页/共56页29最最优优解解第29页/共56页30 maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 2x1 +x3 =16 2x2 +x4 =10 3x1+4 x2

9、+x5=32 Cj比比值值CBXBb检验数检验数 jx1x2x3x4x535000162010010020103234001x3x4x5000035000-10/2=532/4=8第30页/共56页31162010050101/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*=37第31页/共56页32第32页/共56页33第33页/共56页34第34页/

10、共56页35第35页/共56页36第36页/共56页37第37页/共56页38第38页/共56页39第39页/共56页40第40页/共56页41二、右端常量的变动分析二、右端常量的变动分析 参数bi的变化范围 第r个约束的右端项为br，增量br，其它数据不变。新的基解为只要XB0，则可保持最优基不变。第41页/共56页42二、约束方程中常数项的灵敏度分析 从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中S2=50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增加利润的，A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为0。迭代次数基变

11、量CBX1 X2 S1 S2 S3b50 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 -50第42页/共56页43第43页/共56页44第44页/共56页45第45页/共56页46第46页/共56页47第二节第二节 对偶规划的经济解释对偶规划的经济解释一、影子价值的内涵一、影子价值的内涵影子价格不是资源的实际价格，反映了资源配置结构，其它数据固定，某资源增加一单位导致目标函数的增量。对资源i总存量的评估：购进购进 or 出让出让对资源i当前分配量

12、的评估：增加增加 or 减少减少第一，影子利润说明增加哪种资源对经济效益最有利第二，影子价格告知以怎样的代价去取得紧缺资源第三，影子价格是机会成本，提示资源出租/转让的基价第四，利用影子价格分析新品的资源效果：定价决策第五，利用影子价格分析现有产品价格变动的资源紧性第六，可以帮助分析工艺改变后对资源节约的收益第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺第47页/共56页48第48页/共56页49第49页/共56页50第50页/共56页51第51页/共56页52第52页/共56页53第三节第三节 资源定价的决策方案资源定价的决策方案例：某厂生产甲、乙两种产品，生产单位产品的资源消耗如下表所示

13、。问如何安排甲、乙两产品的产量，使每周的利润为最大。如果企业可以不生产，那资源出让如何定价甲乙资源成本资源拥有量原材料 (kg)设备 (工时)电力 (度)943451020501360200300销售价格（元）390352第53页/共56页54第三节第三节 资源定价的决策方案资源定价的决策方案一、最优生产决策一、最优生产决策决策变量：要确定甲、乙两种产品的产量，我们设每周生产的甲产品的产量x1，每周生产的乙产品的产量 x2。由上表计算单位甲产品的成本为383元，单位乙产品的成本为340元，则它们的盈利能力分别为7和12。生产计划的线性规划模型：第54页/共56页55第三节第三节 资源定价的决策

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