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

管理运筹学-管理科学方法,中山大学南方学院工商管理系,演讲：王甜源,2,第3 章 对偶规划,Sub title,学习要点,理解线性规划问题的对偶问题 构建线性规划问题的对偶模型 正确理解对偶规划的基本性质 掌握影子价值的涵义及其应用 资源总存量和分配量增减决策,3,设某工厂生产两种产品甲和乙，生产中需4种设备按A，B，C，D顺序加工，每件产品加工所需的机时数、每件产品的利润值及每种设备的可利用机时数列于下表 ：,产品数据表,问：充分利用设备机时，工厂应生产甲和乙型产品各多少件才能获得最大利润？,一、对偶问题的提出,第一节 对偶规划的数学模型,4,解：设甲、乙型产品各生产x1及x2件，则数学模型为：,反过来问：若厂长决定不生产甲和乙型产品，决定出租机器用于接受外加工，只收加工费，那么种机器的机时如何定价才是最佳决策？,第一节 对偶规划的数学模型,5,在市场竞争的时代，厂长的最佳决策显然应符合两条： （1）不吃亏原则。即机时定价所赚利润不能低于加工甲、乙型产品所获利润。由此原则，便构成了新规划的不等式约束条件。 （2）竞争性原则。即在上述不吃亏原则下，尽量降低机时总收费，以便争取更多用户。,设A、B、C、D设备的机时价分别为y1、y2、y3、y4，则新的线性规划数学模型为：,第一节 对偶规划的数学模型,6,把同种问题的两种提法所获得的数学模型用表2表示，将会发现一个有趣的现象。,原问题与对偶问题对比表,第一节 对偶规划的数学模型,7,2. 原问题与对偶问题的对应关系,原问题 （对偶问题）,对偶问题 （原问题）,第一节 对偶规划的数学模型,8,生产计划问题,例. 某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。 据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。,第一节 对偶规划的数学模型,一、对偶问题的提出,9,第一节 线性规划的一般模型,(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。 (2)约束条件：生产受设备能力制约，能力需求不能突破有效供给量。 设备A的约束条件表达为 2 x1 16 同理，设备B的加工能力约束条件表达为 2x2 10 设备C的装配能力也有限，其约束条件为 3x1+ 4x2 32 (3)目标函数：目标是企业利润最大化 max Z= 3x1 +5x2 (4)非负约束：甲乙产品的产量为非负 x1 0， x2 0,综上的LP模型：,10,第一节 对偶规划的数学模型,若该厂的产品平销，现有另一企业想租赁其设备。厂方为了在谈判时心中有数，需掌握设备台时费用的最低价码，以便衡量对方出价，对出租与否做出抉择。 在这个问题上厂长面临着两种选择：自行生产或出租设备。首先要弄清两个问题： 合理安排生产能取得多大利润? 为保持利润水平不降低，资源转让的最低价格是多少？ 问题 的最优解：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的对偶问题的数学模型,对偶问题的最优解： y1=0，y2=1/2，y3=1，W* =37 两个问题的目标函数值相等并非偶然 前者称为线性规划原问题，则后者为对偶问题，反之亦然。 对偶问题的最优解对应于原问题最优单纯型法表中，初始基变量的检验数的负值。,13,（1）对称形式,特点：目标函数求极大值时，所有约束条件为号，变量非负;目标函数求极小值时，所有约束条件为号，变量非负.,已知P，写出D,第一节 对偶规划的数学模型,14,例2.1 写出线性规划问题的对偶问题,解：首先将原问题变形为对称形式,第一节 对偶规划的数学模型,15,第一节 对偶规划的数学模型,16,(2) 非对称型对偶问题,若给出的线性规划不是对称形式，可以先化成对称形式再写对偶问题。,第一节 对偶规划的数学模型,17,第一节 对偶规划的数学模型,18,课堂练习：写出下列线性规划问题的对偶问题.,解：原问题的对偶问题为,第一节 对偶规划的数学模型,19,第一节 对偶规划的数学模型,二、对偶规划的性质,例2.3 分别求解下列2个互为对偶关系的线性规划问题,分别用单纯形法求解上述2个规划问题，得到最终单纯形表如下表：,20,第一节 对偶规划的数学模型,二、对偶规划的性质,原问题最优表,对偶问题最优表,21,第一节 对偶规划的数学模型,二、对偶规划的性质,原问题与其对偶问题的变量与解的对应关系： 在单纯形表中，原问题的松弛变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量。,22,第一节 对偶规划的数学模型,二、对偶规划的性质,性质1 对称性定理：对偶问题的对偶是原问题,23,第一节 对偶规划的数学模型,二、对偶规划的性质,性质2 最优性定理：如果 是原问题的可行解， 是其对偶问题的可行解，并且:,则 是原问题的最优解， 是其对偶问题的最优解。,性质3 对偶性定理：若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。,还可推出另一结论：若（LP）与（DP）都有可行解，则两者都有最优解，若一个问题无最优解，则另一问题也无最优解。,24,第一节 对偶规划的数学模型,二、对偶规划的性质,性质4 互补松弛性：设X*和Y*分别是P问题 和 D问题 的可行解，则它们分别是最优解的充要条件是：,其中：Xs、Ys为松弛变量,25,第一节 对偶规划的数学模型,二、对偶规划的性质,性质4的应用： 该性质给出了已知一个问题最优解求另一个问题最优解的方法，即已知Y求X或已知X求Y,互补松弛条件,由于变量都非负，要使求和式等于零，则必定每一分量为零，因而有下列关系： 若Y0，则Xs必为0；若X0，则Ys必为0 利用上述关系，建立对偶问题（或原问题）的约束线性方程组，方程组的解即为最优解。,26,第一节 对偶规划的数学模型,例2.4 已知线性规划,的最优解是X=(6,2,0)T,求其对偶问题的最优解Y。,解：写出原问题的对偶问题，即,标准化,27,第一节 对偶规划的数学模型,设对偶问题最优解为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=-20 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 称为影子利润。 影子价格=资源成本+影子利润,32,第二节 对偶规划的经济解释,一、影子价值的内涵,影子价格不是资源的实际价格，反映了资源配置结构， 其它数据固定，某资源增加一单位导致目标函数的增量。 对资源i总存量的评估：购进 or 出让 对资源i当前分配量的评估：增加 or 减少 第一，影子利润说明增加哪种资源对经济效益最有利 第二，影子价格告知以怎样的代价去取得紧缺资源 第三，影子价格是机会成本，提示资源出租/转让的基价 第四，利用影子价格分析新品的资源效果：定价决策 第五，利用影子价格分析现有产品价格变动的资源紧性 第六，可以帮助分析工艺改变后对资源节约的收益 第七，可以预知哪些资源是稀缺资源而哪些资源不稀缺,33,第二节 对偶规划的经济解释,一、影子价值的内涵,此理论应用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，10，则影子价格为20+0，15+0.5，10+1，即20，15.5，11。 如果三种设备工时市场价格为21，15，12，则A设备工时可出让，B设备工时购进，C设备工时虽然是瓶颈资源，但是因为市场价格大于影子价格而暂时不能购买。,35,第三节 资源定价的决策方案,例：某厂生产甲、乙两种产品，生产单位产品的资源消耗如下表所示。 问如何安排甲、乙两产品的产量，使每周的利润为最大。如果企业可以不生产，那资源出让如何定价,36,第三节 资源定价的决策方案,一、最优生产决策,决策变量：要确定甲、乙两种产品的产量，我们设每周生产的甲产品的产量x1，每周生产的乙产品的产量 x2。 由上