管理运筹学讲义第3章对偶规划.ppt

《管理运筹学讲义第3章对偶规划.ppt》由会员分享，可在线阅读，更多相关《管理运筹学讲义第3章对偶规划.ppt（37页珍藏版）》请在三一办公上搜索。

1、管理运筹学-管理科学方法,中山大学南方学院工商管理系,演讲：王甜源,2,第3 章 对偶规划,Sub title,学习要点,理解线性规划问题的对偶问题 构建线性规划问题的对偶模型 正确理解对偶规划的基本性质 掌握影子价值的涵义及其应用 资源总存量和分配量增减决策,3,设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表：,产品数据表,问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？,一、对偶问题的提出,第一节 对偶规划的数学模型,4,解：设甲、乙型产品各生产x1及x2件，则数学模型为

2、：,反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？,第一节 对偶规划的数学模型,5,在市场竞争的时代，厂长的最佳决策显然应符合两条：（1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。（2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。,设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：,第一节 对偶规划的数学模型,6,把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。,原问题与对偶

3、问题对比表,第一节 对偶规划的数学模型,7,2.原问题与对偶问题的对应关系,原问题（对偶问题）,对偶问题（原问题）,第一节 对偶规划的数学模型,8,生产计划问题,例.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。,第一节 对偶规划的数学模型,一、对偶问题的提出,9,第一节 线性规划的一般模型,(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受设备能力制约，能力需求不能突

4、破有效供给量。设备A的约束条件表达为 2 x1 16同理，设备B的加工能力约束条件表达为 2x2 10设备C的装配能力也有限，其约束条件为 3x1+4x2 32(3)目标函数：目标是企业利润最大化 max Z=3x1+5x2(4)非负约束：甲乙产品的产量为非负 x1 0，x2 0,综上的LP模型：,10,第一节 对偶规划的数学模型,若该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题：合理安排生产能取得多大利润?为保持利润水平不降低，资源转

5、让的最低价格是多少？问题 的最优解：x1=4，x2=5，Z*=37。,一、对偶问题的提出,11,第一节 对偶规划的数学模型,一、对偶问题的提出,出让定价,假设出让A、B、C设备所得利润分别为y1、y2、y3原本用于生产甲产品的设备台时，如若出让，不应低于自行生产带来的利润，否则宁愿自己生产。于是有 2y1+0y2+3y3 3同理，对乙产品而言，则有 0y1+2y2+4y3 5设备台时出让的价格（希望出让的价格最少值以获得市场优势）min 16y1+10y2+32y3显然还有 y1，y2，y30,12,第一节 对偶规划的数学模型,一、对偶问题的提出,例1的对偶问题的数学模型,对偶问题的最优解：y

6、1=0，y2=1/2，y3=1，W*=37两个问题的目标函数值相等并非偶然前者称为线性规划原问题，则后者为对偶问题，反之亦然。对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。,13,（1）对称形式,特点：目标函数求极大值时，所有约束条件为号，变量非负;目标函数求极小值时，所有约束条件为号，变量非负.,已知P，写出D,第一节 对偶规划的数学模型,14,例2.1 写出线性规划问题的对偶问题,解：首先将原问题变形为对称形式,第一节 对偶规划的数学模型,15,第一节 对偶规划的数学模型,16,(2)非对称型对偶问题,若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。

7、,第一节 对偶规划的数学模型,17,第一节 对偶规划的数学模型,18,课堂练习：写出下列线性规划问题的对偶问题.,解：原问题的对偶问题为,第一节 对偶规划的数学模型,19,第一节 对偶规划的数学模型,二、对偶规划的性质,例2.3 分别求解下列2个互为对偶关系的线性规划问题,分别用单纯形法求解上述2个规划问题，得到最终单纯形表如下表：,20,第一节 对偶规划的数学模型,二、对偶规划的性质,原问题最优表,对偶问题最优表,21,第一节 对偶规划的数学模型,二、对偶规划的性质,原问题与其对偶问题的变量与解的对应关系：在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。

8、,22,第一节 对偶规划的数学模型,二、对偶规划的性质,性质1 对称性定理：对偶问题的对偶是原问题,23,第一节 对偶规划的数学模型,二、对偶规划的性质,性质2 最优性定理：如果 是原问题的可行解，是其对偶问题的可行解，并且:,则 是原问题的最优解，是其对偶问题的最优解。,性质3 对偶性定理：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。,24,第一节 对偶规划的数学模型,二、对偶规划的性质,性质4 互补松弛性：设X*和Y*分别是P问题 和 D问

9、题 的可行解，则它们分别是最优解的充要条件是：,其中：Xs、Ys为松弛变量,25,第一节 对偶规划的数学模型,二、对偶规划的性质,性质4的应用：该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y求X或已知X求Y,互补松弛条件,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系：若Y0，则Xs必为0；若X0，则Ys必为0利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。,26,第一节 对偶规划的数学模型,例2.4 已知线性规划,的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。,解：写出原问题的对偶问题，即,标准化,27,第一节

10、对偶规划的数学模型,设对偶问题最优解为Y(y1，y2),由互补松弛性定理可知，X和 Y满足：,即：,因为X10，X20，所以对偶问题的第一、二个约束的松弛变量等于零，即y30，y40，带入方程中：,解此线性方程组得y1=1,y2=1,从而对偶问题的最优解为：Y=(1,1)，最优值w=26。,28,第一节 对偶规划的数学模型,课堂练习：已知线性规划,的对偶问题的最优解为Y=(0,-2)，求原问题的最优解。,解:对偶问题是,标准化,29,第一节 对偶规划的数学模型,设对偶问题最优解为X(x1，x2，x3)T,由互补松弛性定理可知，X和 Y满足：,将Y带入由方程可知，y3y50，y41。,y2=-2

11、0 x50又y4=10 x20,将x2，x5分别带入原问题约束方程中，得：,解方程组得：x1=-5,x3=-1,所以原问题的最优解为,X=(-5,0,-1)，最优值z=-12,30,第一节 对偶规划的数学模型,二、对偶规划的性质,原问题与对偶问题解的对应关系小结,31,第二节 对偶规划的经济解释,一、影子价值的内涵,yi是资源bi每增加一个单位对目标函数Z的贡献；对偶变量 yi在经济上表示原问题第i种资源的边际价值。对偶变量的值 yi*表示第i种资源的边际价值，称为影子价值。若原问题价值系数Cj表示单位产值，则yi 称为影子价格。若原问题价值系数Cj表示单位利润，则yi 称为影子利润。影子价格

12、=资源成本+影子利润,32,第二节 对偶规划的经济解释,一、影子价值的内涵,影子价格不是资源的实际价格，反映了资源配置结构，其它数据固定，某资源增加一单位导致目标函数的增量。对资源i总存量的评估：购进 or 出让对资源i当前分配量的评估：增加 or 减少第一，影子利润说明增加哪种资源对经济效益最有利第二，影子价格告知以怎样的代价去取得紧缺资源第三，影子价格是机会成本，提示资源出租/转让的基价第四，利用影子价格分析新品的资源效果：定价决策第五，利用影子价格分析现有产品价格变动的资源紧性第六，可以帮助分析工艺改变后对资源节约的收益第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺,33,第二节 对偶

13、规划的经济解释,一、影子价值的内涵,此理论应用PPT 第8页的例子根据原问题最优解（X2，X1）=（5，4）可求出对偶问题最优解（Y1，Y2，Y3）=（0，0.5，1），Y1=0设备A的工时增加不影响利润增加非瓶颈资源Y2=0.5设备B的工时增加1小时可带来0.5的利润增加瓶颈资源Y3=1设备C的工时增加1小时可带来1的利润增加瓶颈资源X3=8是代表A设备剩余的工时,34,第二节 对偶规划的经济解释,一、影子价值的内涵,一般情况，市场价格小于影子价格，则说明自己生产比卖出去更能获利；市场价格大于影子价格，则说明与其自己生产不如卖给别人更赚钱。若本例中三个设备A，B，C工时成本分别为20，15，

14、10，则影子价格为20+0，15+0.5，10+1，即20，15.5，11。如果三种设备工时市场价格为21，15，12，则A设备工时可出让，B设备工时购进，C设备工时虽然是瓶颈资源，但是因为市场价格大于影子价格而暂时不能购买。,35,第三节 资源定价的决策方案,例：某厂生产甲、乙两种产品，生产单位产品的资源消耗如下表所示。问如何安排甲、乙两产品的产量，使每周的利润为最大。如果企业可以不生产，那资源出让如何定价,36,第三节 资源定价的决策方案,一、最优生产决策,决策变量：要确定甲、乙两种产品的产量，我们设每周生产的甲产品的产量x1，每周生产的乙产品的产量 x2。由上表计算单位甲产品的成本为383元，单位乙产品的成本为340元，则它们的盈利能力分别为7和12。生产计划的线性规划模型：,37,第三节 资源定价的决策方案,二、资源获利决策,如果决策者考虑自己不生产甲乙两种产品，而把原拟用于生产这两种产品的原材料、设备工时、电量资源全部出售给外单位，或者做代加工，则应如何确定这三种资源的价格。,设原材料的单位出让获利为y1，设备工时的单位出让获利为y3，电量的单位出让获利为y2。出让决策的线性规划模型：,