运筹学第三章对偶问题与灵敏度分析.ppt

对偶理论与灵敏度分析,线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析,3.1 线性规划的对偶问题,一、问题的提出,回顾例题1,例1 某工厂在计划期内要安排生产A、B两种产品（假定产 品畅销）。已知生产单位产品的利润与所需的劳动力、设备 台时及原材料的消耗，如表1.1所示 问该厂应如何安排生产使获利最大？,表1-1,其对应的数学模型为：,现从另一个角度提出问题。假定有某个公司想把该工厂的 资源收买过来，它至少应付出多大代价，才能使这个工厂 放弃生产活动，出让自己的资源。,显然该工厂愿出让自己资源的条件是，出让价格应不低于 用同等数量资源由自己组织生产活动时获取的盈利。,价格底线,表1-1,设单位劳动力出让价格y1元，单位设备台时出让价格y2 元，单位原材料出让价格y3元。,出让收入应不低于自己生产收入：,该公司希望用最小代价把这个工厂的全部资源收买过来：,综上所述，我们得到如下数学模型：,原问题,对偶问题,二、对称形式下对偶问题的一般形式,定义： 满足下列条件的线性规划问题称为具有对称形式：其变 量均具有非负约束，其约束条件当目标函数求极大时取 “”号，当目标函数求极小时均取“”号。,下面是对称形式下线性规划原问题的一般形式：,用yi(i=1,m)代表第i种资源的估价，则其对偶问题的一般形式为：,若用矩阵表示：,对称形式下的原问题,对称形式下的对偶问题,将上述对称形式下线性规划的原问题与对偶问题进行比较， 可列出下表所示的对应关系,原问题有m个约束条件，对偶问题有m个变量,原问题有n个变量，对偶问题有n个约束条件,原问题的价值系数对应对偶问题的右端项,原问题的右端项对应对偶问题的价值系数,原问题的系数矩阵转置后为对偶问题系数矩阵,原问题的约束条件与对偶问题方向相反,原问题与对偶问题优化方向相反,小结,写出下面线性规划的对偶规划模型,课堂练习,解：按照对称形式的对偶关系，其对偶模型为,相关证明： 对偶问题的对偶即原问题,令 = ,对偶问题,对偶问题,令Z = Z ,三、非对称形式下原对偶问题关系,原问题和对偶问题有很多内在联系，它们之间存在着严格的对应关系：,目标函数类型之间的对应关系,目标函数系数与右边项的对应关系,约束系数矩阵之间的对应关系,约束类型与变量类型之间的对应关系,并非所有线性规划问题具有对称形式，故下面讨论一般情 况下线性规划问题如何写出其对偶问题：,由于前面三个对应关系与标准形式下的对应关系一致，故我们只需讨论约束类型与变量类型之间的对应关系:,综上所述，其变换形式归纳如下：,例 写出下列线性规划问题的对偶问题,解：,S,S,S,S,S,S,O,O,B,B,S,S,O,O,B,B,例 写出下列线性规划问题的对偶问题,课堂练习,答案：,课堂练习,对偶理论与灵敏度分析,线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析,3.2 对偶问题的基本性质,一、单纯形法计算的矩阵描述,对称形式线性规划问题的矩阵表达式加上松驰变量X后为：,单纯形法计算时，总选取为初始基，对应基变量Xs,举例：,设迭代若干步后，基变量为XB, XB在初始 单纯形表中的系 数矩阵为B。,将B在初始单纯形表中单独列出，而A中去掉B的若干列后剩下的列组成N。,于是其初始单纯形表可表示成如下形式(P53),表2.4,当迭代若干步后，基变量为XB时，该步的单纯形表中由 XB系数组成的矩阵为 (单位矩阵)。 又因单纯形法的迭代是对增广矩阵进行的初等变换，对 应Xs的系数矩阵在新表中应为B-1; 对应XN的系数矩阵在 新表中应为B-1N 于是迭代后的单纯形表可表示成如下形式(P53)：,表2.5,初始单纯形表:,B-1,表2.5,CB,课堂练习,2 -1 1 0 0 0,由,可知：,检验数的求解：,当B为最优基时，其所有检验数应小于零（j 0 ) 于是对应于表2.5有：,而对于XB的检验数可写为：,由此，（1）（2）（3）式可重新表示为：,若令Y= CB B-1 ,则上式可表达为：,这时可以看出检验数行,若取其相反数恰好是其对偶问题 的可行解。,为什么？ 由于对偶问题的限制条件是的形式，则标准形式是在 左边减去一个剩余变量的基础上得到的，这个剩余变量 为,可以看出，当原问题为最优解时，其对偶问题为可行解， 且两者具有相同的目标函数值。后面我们将看到，这时对偶问题的解也为最优解,将这个解代入对偶问题的目标函数，有:,由上面的推导知，我们可以从线性规划问题的最终单纯中直接读出其对偶问题的最优解。,注：Cj Zj为检验数，需对其取反,z1-c1 z2-c2 zn-cn,ym+1 ym+2 yn,松弛变量Xs,更一般的结论： 用单纯形法求解线性规划问题时，迭代的每一步在得到原问题一个基可行解的同时，其检验行（行0）中的 yi和zjcj值是其对偶问题的一个基解,举例：,下面是两个互为对偶的线性规划问题：,原问题,对偶问题,将上面两个线性规划问题加入松弛和剩余变量后，得到如下形式：,y1 y2 y3,对偶变量,对偶变量,x1 x2,用单纯形法和大M法求得两个问题的最终单纯形表如下：,原问题变量,原问题松弛变量,对偶问题的剩余变量,对偶问题变量,原问题最终单纯形表,对偶问题最终单纯形表,对偶问题变量,对偶问题剩余变量,原问题松弛变量,原问题变量,从上面两个表可以清楚的看出两个问题变量之间的对应关系。同时看出只需求解其中一个问题，从最优的单纯形表中同时得到另一个问题的最优解,二、对偶问题的基本性质,【定义2.1】（弱对偶性） 如果xj (j=1,.n)是原问题的可行解，yi (i=1,m)是其对偶问题的可行解，则恒有,证明：,由弱对偶性，可得出以下结论：,1、原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界,2、如原问题有可行解且目标函数值无界（具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解。,注意：本点性质的逆不成立，即当对偶问题无可行解时，其原问题或具有无界解或无可行解；反之亦然,3、若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,【定理2.2】（最优性） 如果xj (j=1,n) 是原问题的可行解，yi (i= 1,m)是其对偶问题的可行解，且有,则xj (j=1,n)是原问题的最优解，yi (i=1,m)是其对偶问题的最优解,证明：设xj*(j=1,n)是原问题的最优解，yi*(i=1,m)是 对偶问题的最优解。由弱对偶性质有：,又知：,【定理2.3】（强对偶性） 若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等,证明： 由于两者均有可行解，根据弱对偶性，对原问题的目标 函数具有上界，对偶问题的目标函数具有下界，因此两者具有最优解。,由矩阵描述一节可知，当原问题为最优解时，其对偶问 题的解为可行解，且有Z=,由定理2.2可知，这时两者均为最优解,【定理2.4】（互补松弛性） 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零，也即：,以前面例子说明互补松弛定理：,y1 y2 y3,对偶变量,y1 y2 y3,互补松弛定理（说明续）：,原问题变量,原问题松弛变量,对偶问题的剩余变量,对偶问题变量,原问题最终单纯形表,已知线性规划问题 min = 2x1 + 3x2 + 5x3 + 2x4 + 3x5 x1 + x2 + 2x3 + x4 + 3x5 4 2x1 x2 + 3x3 + x4 + x5 3 xj 0 (j = 1, 2, , 5) 对偶问题的最优解为y1* = 4/5, y2* = 3/5, Z=5, 试找出原问题的最优解。,课堂举例,st.,分析： 先写出其对偶问题 max Z = 4y1 + 3y2 y1 + 2 y2 2 y1 - y2 3 2y1 + 3y2 5 y1 + y2 2 3y1 + y2 3,x1 x2 x3 x4 x5,将y1*、y2* 的值带入约束条件， 得到24个约束条件为严格不等 式；由互补松弛性得x2* =x3* =x4*=0. 因y1*、y2*0;原问题的两个约束 条件应取等式： x1* + 3x5* = 4 2x1* + x5* = 3 求解后得到x1*= 1, x5*=1,故原问题 最优解x*=(1,0,0,0,0,1)T; *=5,课堂练习,已知原问题,的最优解为X*=(0,0,4)T,最优值为Z*=12.试用对偶理论求对偶问题的最优解,将X*=(0, 0, 4)T ,代入原问题的三个约束条件可知：,由松弛互补定理可知，必有y1*=y2*=0，代入对偶问题得y3*=3,解：原问题的对偶问题为：,Y*=(0,0,3), 最优值为W*=12,对偶理论与灵敏度分析,线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析,当线性规划原问题求得最优解xj*(j=1,2n)时，其对偶 问题也得到最优解yi*(i=1,m),代入各自的目标函数后有：,3.3.1,其中，bi代表第i种资源的拥有量，对偶变量yi*的意义代 表在资源最优利用条件下对单位资源i的估价。,这种估计不是资源的市场价格，而是根据在生产中做出 的贡献而作的估价，为区别一般意义的价格，我们将其 （yi*）称为影子价格（shadow price）,3.3 影子价格（对偶最优解的经济解释）,影子价格的几点说明,1 资源的市场价格是已知数，相对比较稳定，而它的影子 价格则有赖于资源的利用情况，是未知数。因企业生产任 务、产品结构等情况发生变化，资源的影子价格也随之改 变。,2 影子价格是一种边际价格，在3.31式中对Z求bi的偏导数 得,这说明yi*的值相当于在资源得到最优利用的生产条件 下，bi每增加一个单位时目标函数Z的增量,关于第2点的说明,最终单纯形表,y1 y2 y3,对偶变量,y1 y2 y3,关于第2点的说明,(2,6),(5/3,13/2),Z1=3(2)+5(6)=36,2x2=12,2x2=13,Z2=3(5/3)+5(13/2)=37.5,Z=Z2 Z1= 3/2 = y*2,3 资源的影子价格实际上又是一种机会成本。在纯市场经济 条件下，当某一资源的市场价格低于该影子价格时，可以买 进这种资源；相反，当市场价格高于影子价格时，就会卖出 这种资源。随着资源的买进卖出，它的影子价格也将随之发 生变化，一直到影子价格与市场价格保持同等水平时，才处 于平衡状态。 4、在上一节对偶问题的互补松弛性质中有,这表明生产过程中如果某资源bi未得到充分利用，则该种 资源的影子价格为零；又当某资源的影子价格不为零时， 表明该种资源已消耗完毕。 (互补松弛定理的经济解释),5 对单纯形表的检验数,Cj代表第j种产品的单位产值， aijyi是生产单位该种产品所消耗各项资源的影子价格的总和。当产品单位产值大于隐含成本时，表明生产该项产品有利，可在计划中安排生产，否则用这些资源赖生产别的产品更为有利，就不安排生产。（检验数的经济解释）,6 一般说来，对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价，这种估计直接涉及资源的最有效利用。 例如，在一个大公司内部，可借助资源的影子价格确定一些内部结算价格，以便控制有限资源的使用和考核下属企业经营的好坏。 又如，在社会上可对一些最紧缺的资源，借助影子价格规定使用这种单位资源时必须上交的利润额，以控制一些经济效益低的企业自觉地节约使用紧缺资源，使有限资源发挥更大的经济效益。,对偶理论与灵敏度分析,线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析,3.4 对偶单纯形法,一、对偶单纯形法的基本思路,对原问题的一个基可行解，判别是否所有检验数 ，若是，又基变量中无非零人工变量，即找到了问题的最优解；若为否，再找出相邻的目标函数值更大的基可行解，并继续判别，只要最优解存在，就一直循环进行到找出最优解为止。,求解线性规划的单纯形法的思路是：,对偶单纯形法的基本思路是：,从原问题的一个基本解出发，此基本解不一定可行（即b中有负数），但它对应着一个对偶可行解（检验数非正），所以此时也可以说是从一个对偶可行解出发；然后检验原问题的基本解是否可行，即b是否有非负的分量,若否，则进行迭代，求解另一个基本解，此基本解对应着另一个对偶可行解（保持检验数非正）。如果得到的基本解的分量皆非负，则该基本解为最优解。,也就是说，对偶单纯形法在迭代过程中始终保持对偶解的 可行性（即检验数非正），使原问题的基本解由不可行逐 步变为可行。当同时得到对偶问题与原问题的可行解时， 便得到了原问题的最优解。,二、对偶单纯形法的计算步骤,1 根据线性规划问题，列出初始单纯形表，检查b列的数字，若都为非负，检验数都为非正，则已得到最优解，停止计算。若检查b列的数字时，至少有一个负分量，所有检验数保持非正，那么进行以下计算,2 确定换出基的变量 按 对应的基变量xr为换出基的变量,确定换入变量 在单纯形表中检查xr所在行的各系数arj(j=1,2,n) 若所有arj 0，则原问题无可行解,xr + ar,m+1xm+1 + arn xn = br 因为arj 0 (j=m+1,n), 又br0, 故不可能存在 xj 0 (j=1,2n)，故原问题无可行解。,若存在arj 0(j =1,2n), 则按最小比值原则计算,称ars为主元素（枢轴元素），xs为换入基的变量,4 以ars为主元素，进行高斯消元，得到新的计算表 重复14的步骤,单纯形法与对偶单纯形法之间的比较,三、对偶单纯形法举例,例 用对偶单纯法求解下述线性规划问题：,分析：先将问题改写为最大化形式，然后在约束条件两端乘“1”后，加入相应的松弛变量得：,列出单纯形表，并用上述对偶单纯形法求解步骤进行计算,-24/-6 -5/-1 (最小比值原则),枢轴元素,因为所有bi 0 且所有j 保持非正，故该问题得到最优解，停止计算,四、对偶单纯形法的应用时机,1 对偶单纯形法的优点是，初始解可以是非可行解，不需要加入人工变量,2 对一个线性规划问题，即可以用单纯形法求解，也可以用对偶单纯形法求解。 具体采用那种方法，由当前情况（计算表）决定。使用那种方法比较方便，就使用那种方法,3 求目标函数最大化时，在单纯形表中： 如果检验数均非正，而b列中有负值，这时使用对偶单 纯形法； 如果所有bi 0, 检验数有正值，使用单纯形法 如果b列中有负值，且检验数中有正值，这时必须引入 人工变量，建立新的单纯形表，重新计算,课堂练习,用对偶单纯形法求解,解：将模型转化为,(-9/-1, -12/-1, -15/-5),(-30/-9,-45/-14,-15/-1),(-3/-9, -45/-9, -33/-1),对偶理论与灵敏度分析,线性规划的对偶问题 对偶问题的基本性质 影子价格 对偶单纯形法 灵敏度分析,3.5 灵敏度分析,为什么进行灵敏度分析？,在前面讨论线性规划时，假定aij、bi、cj都是常数（回忆前面线性规划问题的四个假设确定性）。但实际上这些系数往往是估计值和预测值。 如市场条件一变，cj值就会发生变化；aij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。,因此提出这样的两个问题：,当这些系数一个或几个发生变化时，已求得的线性规划 问题的最优解是否会发生变化（确定敏感参数） 对于非敏感参数在什么范围内变化，线性规划问题的最 优解不变,灵敏度分析采用的方法：,对于上述两个问题，如果将问题从头计算求解，当然是一种方法，但是这样不仅麻烦、没有必要，而且也得不到更多有用的信息。,灵敏度分析采用的方法是从已得到的最优解出发，通过对变化数据进行一些简单的计算，便可迅速得到所需要的结果以及变化后的最优解。因此，灵敏度分析也称优化后分析。,灵敏度分析的步骤：,将参数的改变通过计算反映到最终单纯形表上来： （难点、关键）,初始单纯形表：,迭代若干步后的单纯形表：（最终单纯形表）,初始单纯形表： 系数列向量： Pj （j= 1,2n） 右端项： b 价值系数: Cj （j= 1,2n）,B-1,最终单纯形表： 系数列向量： B-1Pj 右端项：B-1b 检验数： j =Cj-CBB-1pj,1 将参数的改变通过计算反映到最终单纯形表上来：,2 检查原问题是否仍为可行解,3 检查对偶问题是否仍为可行解,灵敏度分析的三把尺子,4 按下表所列的情况得出结论或者决定继续计算的步骤,灵敏度分析背景例子,美佳公司计划制造I、II两种家电产品。已知各制造一件时分别占用A、B的台时、调试时间及每天可用于这两种家电的能力、各售出一件时的获利情况，如下表所示。 问 该公司每天应制造两种家电各多少件，使获利最大,其数学模型为：,初始单纯形表,最终单纯形表：,一、分析Cj的变化,线性规划目标函数中变量系数Cj的变化仅仅影响到 检验数（Cj - Zj）的变化。Cj的变化不会影响到解 的可行性，我们只需要判断解的最优性（对偶问 题的可行性）即可。,若该解最优，则最优解不变 若该解不是最优，则使用单纯形法迭代直 到得到最优解,下面举例说明：,（1）若家电I的利润 2 1.5，而家电II的利润12，美佳公司最优生产计划有何变化,(2) 若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划不发生变化,分析：(1),最终单纯形表,j = Cj - CBB-1pj ,其中B-1pj可从最终单纯形表读得,0 0 0 1/8 -9/4,因变量x4的检验数大于零，故需继续用单纯形法迭代,6 14 ,即美佳公司随家电利润的变化应调整为生产I 2件，生产II 3 件,分析：(2) 设家电II的利润为(1+)元，反映到最终单纯形表中，得下表：,0 0 0 -1/4+1/4 -1/2-3/2,为使上表的解仍为最优解，应有： -1/4 + 1/4 0 ; -1/2 2/3 0 解得： -1/3 1 即家电II的利润c2的变化范围应满足 ： 2/3 c2 2,二、分析bi的变化,右端项bi的变化在实际问题中反映为可用资源数量的变化。由于bi变化反映到最终单纯形表上仅引起b列数字的变化，故解的最优性不受影响（对偶问题可行），我们只需要判断解的可行性即可。,若该解可行，则最优基不变 若该解不可行，则使用对偶单纯形法迭代直到找到最优解,在上述美佳公司的例子中：,（1）若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32h，分析公司最优计划的变化,（2）若设备A和设备B每天可用能力不变，则调试工序能力在什么范围变化时，问题的最优基不变,分析： (1)因为 ，于是有：,将计算结果反映到最终单纯形表中去,有：,原最终单纯形表,由于原问题为非可行解，故用对偶单纯形法继续计算得下表,由此，美佳公司的最优计划改变为只生产家电 5件,分析： （2）设调试工序每天可用能力为（ 5 + ）h,因此有：,当b 0时问题的最优基不变，解得 -1 1 由此，此调试工序的能力应在46h之间,三、增加一个变量xj的变化,增加一个变量在实际问题中放映为增加一种新的产品，其 分析步骤为：,1、计算,2、计算,3、若,，则原最优解不变，只需将计算得到的,直接写入最终单纯形表中即可；若存在, 则按单纯形法继续迭代计算找出最优解。,美佳公司又计划推出新型号的家电III，生产一件所需设 备A、B及调试工序的时间分别为3h, 4h, 2h，该产品的预 期盈利为3元/件， 试分析该种产品是否值得投产；如投 产，对该公司的最优生产计划有何变化。,分析： 设该公司生产家电III x6件，有C6=3, P6=(3,4,2)T,将其反映到最终单纯形表中得下表：,由此，美佳公司最优生产