《运筹学0903对偶规划.ppt》由会员分享，可在线阅读，更多相关《运筹学0903对偶规划.ppt（57页珍藏版）》请在三一办公上搜索。
1、管理运筹学-管理科学方法,中国人民大学出版社,2,第3 章 对偶规划,Sub title,学习要点,理解线性规划问题的对偶问题 构建线性规划问题的对偶模型 正确理解对偶规划的基本性质 掌握影子价值的涵义及其应用 资源总存量和分配量增减决策,3,第一节 对偶规划的数学模型,一、对偶问题的提出,若例1中该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：合理安排生产能取得多大利润?为保持利润水平不降低，资源转让的最低价格是多少？问题 的最优解：
2、x1=4，x2=5，Z*=37。,4,第一节 对偶规划的数学模型,一、对偶问题的提出,出让定价,假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有 2y1+0y2+3y3 3同理，对乙产品而言，则有 0y1+2y2+4y3 5设备台时出让的收益（希望出让的收益最少值）min 16y1+10y2+32y3显然还有 y1，y2，y30,5,第一节 对偶规划的数学模型,一、对偶问题的提出,例1的对偶问题的数学模型,对偶问题的最优解：y1=0，y2=1/2，y3=1，W*=37两个问题的目标函数值相等并非偶然
3、前者称为线性规划原问题，则后者为对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。,6,7,8,9,例：写出线性规划问题的对偶规划,10,第一节 对偶规划的数学模型,二、对偶规划的性质,1、对称性定理 对偶问题的对偶问题是原问题。根据对偶规划，很容易写出对偶问题的对偶问题模型。2、最优性定理 设，分别为原问题和对偶问题的可行解，且 则，分别为各自的最优解。3.对偶性定理 若原问题有最优解，那么对偶问题也有最优解，而且 两者的目标函数值相等。4.互补松弛性 最优解的充分必要条件是，,11,12,13,14,15,16,17,18,19,20,21,第二节
4、 对偶规划的经济解释,一、影子价值的内涵,左边是资源bi每增加一个单位对目标函数Z的贡献；对偶变量 yi在经济上表示原问题第i种资源的边际价值。对偶变量的值 yi*表示第i种资源的边际价值，称为影子价值。若原问题价值系数Cj表示单位产值，则yi 称为影子价格。若原问题价值系数Cj表示单位利润，则yi 称为影子利润。,22,23,24,25,生产计划问题,例2.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产
5、计划。,26,27,对偶问题,28,原问题是以利润为目标，对偶变量 yi则定义为资源bi每增加一个单位对利润的贡献程度，称为资源的 影子利润；Y1=0,说明设备A的工时增加并不影响利润Y2=0.5说明设备 B的工时每增加1小时，则使利润增加0.5元。,最优解,哪些是非瓶颈资源和瓶颈资源？,29,影子价格=资源成本+影子利润,影子价格并不是资源的实际价格，而是企业内部资源的配比价格，是由企业内部资源的配置状况决定的，并不是由市场来决定的,影子价格的应用,1.影子价格与市场价格对比：成本：A：20元/小时 B：15 C：10市场：A:21;B:15;C:12,30,影子价格的应用,2.增加哪一种资
6、源对增加经济效益有利,3.告诉经营者一怎样的代价去取得稀缺资源,4.是一种机会成本，提示企业设备出租或原材料的转让的基价,5.知道新产品的定价与投产决策,6.分析工艺改变后对资源节约的收益,7.分析现有产品价格变动时对资源紧缺的影响,31,最优解,32,maxZ=3x1+5 x2+0 x3+0 x4+0 x5=0 2x1+x3=16 2x2+x4=10 3x1+4 x2+x5=32,33,最优解:X*=(4,5,8,0,0)T，Z*=37,34,35,36,37,38,39,40,41,42,43,二、右端常量的变动分析,参数bi的变化范围 第r个约束的右端项为br，增量br，其它数据不变。新
7、的基解为,只要XB0，则可保持最优基不变。,44,二、约束方程中常数项的灵敏度分析 从上表我们可以发现各个松弛变量的值，正好等于相应变量的对偶价格。在最优解中S2=50是基变量，即为，原料A有50千克没用完，再增加A原料是不会增加利润的，A的对偶价格为0。对于任何为基变量的松弛变量所对应的约束条件的对偶价格为0。,45,46,47,48,49,第二节 对偶规划的经济解释,一、影子价值的内涵,影子价格不是资源的实际价格，反映了资源配置结构，其它数据固定，某资源增加一单位导致目标函数的增量。对资源i总存量的评估：购进 or 出让对资源i当前分配量的评估：增加 or 减少第一，影子利润说明增加哪种资
8、源对经济效益最有利第二，影子价格告知以怎样的代价去取得紧缺资源第三，影子价格是机会成本，提示资源出租/转让的基价第四，利用影子价格分析新品的资源效果：定价决策第五，利用影子价格分析现有产品价格变动的资源紧性第六，可以帮助分析工艺改变后对资源节约的收益第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺,50,51,52,53,54,55,第三节 资源定价的决策方案,例：某厂生产甲、乙两种产品，生产单位产品的资源消耗如下表所示。问如何安排甲、乙两产品的产量，使每周的利润为最大。如果企业可以不生产，那资源出让如何定价,56,第三节 资源定价的决策方案,一、最优生产决策,决策变量：要确定甲、乙两种产品的产量，我们设每周生产的甲产品的产量x1，每周生产的乙产品的产量 x2。由上表计算单位甲产品的成本为383元，单位乙产品的成本为340元，则它们的盈利能力分别为7和12。生产计划的线性规划模型：,57,第三节 资源定价的决策方案,二、资源获利决策,如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产这两种产品的原材料、设备工时、电量资源全部出售给外单位，或者做代加工，则应如何确定这三种资源的价格。,设原材料的单位出让获利为y1，设备工时的单位出让获利为y3，电量的单位出让获利为y2。出让决策的线性规划模型：,
