第二章对偶理论与灵敏度分析.ppt

第二章 对偶理论与灵敏度分析,1线性规划的对偶问题 2对偶问题的基本性质 3影子价格 4对偶单纯形法 5灵敏度分析,1线性规划的对偶问题,1.1 对偶问题的提出 1.2 对称形式下对偶问题的一般形式 1.3 非对称形式的原对偶问题关系 1.4 对偶问题的定义 1.5 对偶关系对应表,例1：美佳公司利用该公司资源生产两种家电产品。,1.1 对偶问题的提出,1线性规划的对偶问题,现从另一角度提出问题。假定有另一公司想把美佳公司的资源收买过来，它至少应付出多大代价，才能使美佳公司愿意放弃生产活动，出让自己的资源？ 显然美佳公司愿出让自己资源的条件是，出让代价应不低于用同等数量资源由自己组织生产活动时获取的盈利。 设分别用yl，y2和y3代表单位时间（h）设备A、设备B和调试工序的出让代价。因美佳公司用6小时设备A和l小时调试可生产一件家电I，盈利2元；用5小时设备A，2小时设备B及1小时调试可生产一件家电II，盈利1元。,1线性规划的对偶问题,由此y1，y2，y3的取值应满足:,该公司希望用最小代价把美佳公司的全部资源收买过来。,因此，线性规划模型为：,1线性规划的对偶问题,1线性规划的对偶问题,原问题：设x1 ， x2 为产品1，2的产量,maxZ= 2X1 +3x2,1线性规划的对偶问题,对偶问题：设 y1 , y2 , y3 , y4分别为A, B, C, D设备的单价,1线性规划的对偶问题,对称的含义：满足下列条件的线性规划问题称为具有对称形式：其变量均具有非负约束，其约束条件当目标函数求极大时均取“”号，当目标函数求极小时均取“”号。 对称形式下线性规划原问题的一般形式为：,max Z=c1x1+ c2x2+cnxn,1.2 对称形式下对偶问题的一般形式,1线性规划的对偶问题,用yi(i1，m)代表第i种资源的估价，则其对偶问题的一般形式为：,min w=b1y1+ b2y2+bmym,1线性规划的对偶问题,用矩阵形式表示，原问题为:,其对偶问题为：,1线性规划的对偶问题,原问题与对偶问题的对应关系,1线性规划的对偶问题,1.3 非对称形式的原对偶问题关系,1线性规划的对偶问题,例2 写出下述线性规划问题的对偶问题,无约束,1.3 非对称形式的原对偶问题关系,1线性规划的对偶问题,写出其对偶问题为：,可变换成具有如下对称形式的线性规划问题,1.3 非对称形式的原对偶问题关系,1线性规划的对偶问题,进行整理为：,无约束,例3 写出下述线性规划问题的对偶问题,1.3 非对称形式的原对偶问题关系,1线性规划的对偶问题,解：原问题可化为,则对偶问题：,1线性规划的对偶问题,令 y1 = y1' -y1 “,1线性规划的对偶问题,1.4 对偶的关系,原始问题 max z=CTX s.t. AX b X 0,对偶问题 min y=bTW s.t. ATW C W 0,1线性规划的对偶问题,1.5 对偶关系对应表,1线性规划的对偶问题,2对偶问题的基本性质,单纯形法计算的矩阵描述 一、对称性 二、弱对偶性 三、无界性 四、可行解是最优解的性质 五、对偶定理 六、松紧定理,用矩阵形式表示，原问题为:,其对偶问题为：,min y=bY s.t. AY C Y 0,max z=CX s.t. AX b X 0,2对偶问题的基本性质,单纯形法计算的矩阵描述,对称形式线性规划问题的矩阵表达式加上松弛变量后为：,上式中XS为松弛变量,I 为m×m单位矩阵,通过迭代后: X=XB + XN,相应地: C=CB + CN,系数矩阵 : A= B + N,2对偶问题的基本性质,参1-105,迭代后新的单纯形表为：,初始单纯形表：,2对偶问题的基本性质,迭代后新的单纯形表为：,初始单纯形表：,C- CBB-1A,2对偶问题的基本性质,可以看出：,(1)对应初始单纯形表中的单位矩阵I，迭代后的单纯形表中为B-1 ； (2)初始单纯形表中基变量Xsb，迭代后的表中 XB=B1b ； (3)初始单纯形表中约束系数矩阵为A，I B，N，I ，迭代后的表中约束系数矩阵为B-1A，B-1IB-1B，B-1N，B-1I I，B-1N，B-1 ； (4)若初始矩阵中变量Xi的系数向量为Pj，迭代后为Pj，则有Pj=B-1Pj 。,2对偶问题的基本性质,当B为最优基时,因xB的检验数可写为 CB- CBI=0,CBB-1称为单纯形乘子，若令Y= CBB-1 ，则,所以,CN- CBB-1N 0 -CBB-1 0,C- CBB-1A 0 -CBB-1 0,2对偶问题的基本性质,看出这时检验数行，若取其相反数恰好是其对偶问题的一个可行解。 将这个解代入对偶问题的目标函数值，有：,当原问题为最优解时，这时对偶问题为可行解，且两者具有相同的目标函数值，对偶问题的解也为最优解。,w=Yb= CBB-1b=z,2对偶问题的基本性质,例4,maxZ=2x1+ x2+0·x3 +0·x4+0·x5,min w=15y1+ 24y2+ 5y3 +0·y4+0·y5,2对偶问题的基本性质,最终单纯形表：,2对偶问题的基本性质,一 . 对称性 ： 对偶问题的对偶是原问题,2对偶问题的基本性质,对 偶,2对偶问题的基本性质,若x是原问题的可行解，y是对偶问题的可行解。则有 cxyb,二. 弱对偶性,2对偶问题的基本性质,推论(2)： 若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。,推论(1)： 原问题任一可行解的目标函数值是其对偶问题目标函数值的下界，反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,注 ： 其逆不成立。,推论(3)若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界，反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,2对偶问题的基本性质,设x是原问题的可行解，y是对偶问题的可行解. 当 cx= yb 时 x, y 是最优解。,三 . 最优性,2对偶问题的基本性质,四 . 强对偶性（对偶定理）,若原问题及其对偶问题均具有可行解，则两者均具有最优解且它们最优解的目标函数值相等。,证明： 由弱对偶定理推论1，可知两者都有最优解。 由前面公式可知，当原问题有最优解时，对偶问题有可行解，且目标函数值相等。 由最优性知，两者均为最优解。,2对偶问题的基本性质,五. 互补松弛性（松紧定理）,在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,y1 y2 y3,2对偶问题的基本性质,即：,2对偶问题的基本性质,证明：,几个练习,2对偶问题的基本性质,2对偶问题的基本性质,1 ）说明原问题和对偶问题都有最优解. 2 ）求原问题和对偶问题的最优目标函数值的一个上界和下界.,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,2对偶问题的基本性质,3影子价格,式中bi是线性规划原问题约束条件的右端项，它代表第i种资源的拥有量；对偶变量yi*的意义代表在资源最优利用条件下对单位第i仲资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中作出的贡献而作的估价，为区别起见，称为影子价格(shadow price)。,关于影子价格的几点说明,1影子价格是未知数,有赖于资源的利用情况。,2影子价格是一种边际价格。,这说明影子价格的值相当于在资源得到最优利用的生产条件下，b每增加一个单位时目标函数Z的增量。,3影子价格,例1,A B C,15/2 0 0,资源,剩余,0 1/4 1/2,影子价格,3影子价格,所以第2种资源的影子价格为0.25，第3种资源的影子价格为0.5。,3影子价格,3资源的影子价格实际上又是一种机会成本。 在纯市场经济条件下，可以根据影子价格与市场价格的关系确定资源的买进或卖出。,4生产过程中如果某种资源末得到充分利用时，该种资源的影子价格为零；又当资源的影子价格不为零时，表明该种资源在生产中已耗费完毕。,3影子价格,5单纯形表中各个检验数的经济意义,6对线性规划问题的求解是确定资源的最优分配方案，而对于对偶问题的求解则是确定对资源的恰当估价。,当产品产值大于隐含成本时，表明生产该项产品有利，可在计划中安排，否则这些资源来生产别的产品更为有利，就不在计划中安排。这就是单纯形表中各个检验数的经济意义。,3影子价格,4对偶单纯形法,单纯形法的思路：找一个基可行解，在保持解可行的前提下，让检验数全为非正。,对偶单纯形法的基本思路：先找出一个对偶问题的可行基，并保持对偶问题为可行解条件下，如不存在XB o，通过变换到一个相邻的目标函数值较小的基本解(因对偶问题是求目标函数极小化)，并循环进行，一直到原问题也为可行解(即XB o)，这时对偶问题与原问题均为可行解。 在迭代过程中保持原问题的检验数为非正，逐步替换负基变量，从而得到最优解。,4对偶单纯形法,对偶单纯形法的计算步骤：,1. 列出初始单纯形表，且检验数非正。,4对偶单纯形法,4.以ars为主元素，进行迭代变换。 可以证明，按照上述方法进行迭代变换以后，检验数仍保持为非正，即对偶问题仍可行。,5 . 返 2，直到B 0为止。,原始单纯形法 按列选主元 对偶单纯形法 按行选主元,对于对偶问题有可行解，而原问题无可行解的判断。 判断准则是：对 ，而对所有j=1,n，有 。,4对偶单纯形法,例5：用对偶单纯形法求解下列问题,4对偶单纯形法,4对偶单纯形法,4对偶单纯形法,4对偶单纯形法,已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=35 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-1, 5, 7, 0, 0, 0） max y=35,4对偶单纯形法,从以上计算可以看出，用对偶单纯形法求解线性规划问题时，当约束条件为“”时，不必引进人工变量，使计算简化。但在初始单纯形表中其对偶问题应是基可行解这点，对多数线性规划问题很难实现。因此对偶单纯形法一般不单独使用，而主要应用于灵敏度分析及整数规划等有关章节中。,4对偶单纯形法,例:(初始解原始、对偶都不可行的问题),解法1：先解决原始可行性,在得到原始可行解时同时得到对偶可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,解法2：先解决对偶可行性,已得到对偶可行解，再用对偶单纯形法求解,得到原始可行解，已获得最优解： （x1, x2, x3, x4, x5, x6）=（5, 7, 6, 0, 0, 0） min z=17 对偶问题的最优解为： （w1, w2, w3, w4, w5, w6）=（-7, 5, 10, 0, 0, 0） max y=17,对偶单纯形法的优点： 1 简化计算 2 减少计算量 3 灵敏度分析 缺点： 第一个正则解很难找到,4对偶单纯形法,5灵敏度分析,灵敏度分析是指对系统或事物因周围条件变化显示出来的敏感程度的分析。A，b，C 当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者这些参数在一个多大范围内变化时，问题的最优解不变。这就是灵敏度分析所要研究解决的问题。 单纯形法的迭代计算是从一组基向量变换为另一组基向量，表中每步迭代得到的数字只随基向量的不同选择而改变，因此有可能把个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来。,灵敏度分析的步骤 1将参数的改变计算反映到最终单纯形表上来：,5灵敏度分析,2检查原问题是否仍为可行解； 3检查对偶问题是否仍为可行解； 4按下表所列情况得以结论和决定继续计算的步骤。,5灵敏度分析,灵敏度分析解决的主要问题： (1)、参数A，b，C在什么范围内变动，对当前方案无影响？ (2)、参数A，b，C中的一个(几个)变动，对当前方案影响？ (3)、如果最优方案改变，如何用简便方法求新方案？,5灵敏度分析,一、分析Cj的变化 线性规划目标函数中变量系数Cj的变化仅仅影响到检验数(Cj-Zj)约变化。所以将Cj的变化直接反映到最终单纯形表中，只可能出现前两种情况。,5灵敏度分析,5灵敏度分析,例5 在第一章例1的美佳公司例子中: (1)若家电I的利润降至1. 5元件，而家电的利润增至2元件时，美佳公司最优生产计划有何变化?,5灵敏度分析,解 (1)将家电I，II的利润变化直接反映到最终单纯形表中。,以x4为换入变量,x3为换出变量，列新单纯形表。,所有检验数为非正，问题得到最优解：X（2，3，0，6，0）,5灵敏度分析,(2)若家电I的利润不变，则家电II的利润在什么范围内变化时，则该公司的最优生产计划将不发生变化？ 设家电II的利润为(1十)元，反映到最终单纯形表中为：,为使表中的解仍为最优解，应有,即家电II的利润C2的变化范围应满足：,例6,问：如何安排产品产量，可获最大利润？,5灵敏度分析,最优单纯形表为：,问: 价值系数变化时对最优解的影响？,5灵敏度分析,(1)、非基变量系数Cj, Cj 改变，仍有j0 时对最优方案无影响。,即C3 8,例中C3在什么范围内变化时，对最优方案无影响？, 3 = C3 -CBB-1 P3,5灵敏度分析, C3改为10， 最优方案如何变化？, 3 =20,5灵敏度分析,(2)、基变量系数Cj, Cj 改变？ 全部 j0，最优方案不变,例中C1改变 A = C -CBB-1 A,=(0,0,-2,-2C1+8, C1 -8) 0,4 C1 8,5灵敏度分析, C1改变 C1=10？, 5 =20 ,换基,5灵敏度分析,二、分析bi的变化,右端项bj的变化在实际问题中反映为可用资源数量的变化。,5灵敏度分析,例7：在美佳公司的例子中：(1)若设备A和调试工序的每天能力不变，而设备B每天的能力增加到32小时，分析公司最优计划的变化?,解：因为：,5灵敏度分析,以X2为换出变量，X4为换入变量，列新单纯形表得：,问题的最优解：X（5，0，15，2，0）,5灵敏度分析,单纯形表中 b列数字为：,(2)若设备A和B每天可用能力不变，则调试工序能力在什么范围内变化时，问题的最优基不变?,设调试工序每天可用能力为（5+）小时，因有,当b 0时问题的最优基不变，解得：-1 1 因此调试工序的能力应在4小时-6小时之间。,5灵敏度分析,(1)、bj 改变？ B-1 b仍0时，最优方案不变。,例中b1改变,前面例子：,三、增加一个变量xj的分析,增加一个变量在实际问题中反映为增加一种新的产品。 其分析步骤为：,3.若 ，原最优解不变，只需将计算得到的 和 直接写入最终单纯 形表中；若 ，则按单纯形法继续迭代计算找出最优。,5灵敏度分析,例8 在美佳公司例子中，设该公司又计划推出新型号的家电III，生产一件所需设备A、B及调试工序的时间分别为3小时、4小时、2小时，该产品的预期盈利为3元件。试分析该种产品是否值得投产，如投产，对该公司的最优生产汁划有何变化。,解：设该公司生产家电III 件，有,5灵敏度分析,以x2 为换出变量， x6 为换入变量，列新单纯形表得：,5灵敏度分析,问题的最优解：X（7/2，0，51/4，0，0，3/4）T。 所以，该公司新的生产计划应为每天生产家电I 7/2件，生产家电III 3/4件。,5灵敏度分析,现有新产品D，已知生产1个单位D要消耗： 甲：3 乙：2 ，可以得利润10。 问：投产产品D是否有利？,前面例子：,结论：无利,（1）利润为多少时，投产产品D有利？, 6 = C6 - CBB-1 P6 = C6 - 12 0 得 C6 12,（2） C6 =15 时 ，原问题的最优解为多少？ 6 =3,四、分析参数aij的变化,aij的变化使线性规划的约束系数矩阵A发生变化。 若变量xj在最终单纯形表中为非基变量，其约束条件中系数aij的变化分析步骤可参照本节之三； 若变量xi在最终单纯形表中为基变量，则aij的变化将使相应的B和B-1 发生变化因此有可能出现原问题和对偶问题均为非可行解的情况。 出现这种情况时，需引进入工变量将原问题的解转化为可行解，再用单纯形法求解。,5灵敏度分析,例9 在美佳公司的例子中，若家电II每件需设备A，B和调试工时变为8小时、4小时、1小时，该产品的利润变为3元/件，试重新确定该公司最优生产计划。,解：将生产工时变化后的新家电II看作是一种新产品，生产量为x2'。,5灵敏度分析,因x2已变换为x2' ，故用单纯形算法将x2'替换出基变量中的x2 ，并在单纯形表中不再保留x2。,5灵敏度分析,增加人工变量。,X3+ 4X4 - 24X5= -9,5灵敏度分析,美佳公司的最优生产计划为每天生产家电I 11/4件，新家电II 15/8件。,5灵敏度分析,前面例子：产品A工艺改变，对甲、乙需求变为2，2。 利润为7，问最优方案如何？,换入？ 换出？,五、增加一个约束条件的分析,增加一个约束条件在实际问题中相当增添一道工序。从图形（二维）上分析相当于增加了一条直线。分析的方法是先将原问题最优解的变量值代入新增的约束条件。如满足，说明新增的约束未起到限制作用，原最优解不变。否则，将新增的约束直接反映到最终单纯形表中再进步分析。,5灵敏度分析,例10 仍以美佳公司为例，设家电I，II经调试后，还需经过道环境试验工序。家电I每件须环境试验3小时，家电II每件2小时，又环境试验工序每天生产能力为12小时试分析增加该工序后的美佳公司最优生产计划。 解：先将原问题的最优解x1 =7/2, x2 =3/2代入环境试验工序的约束条件： 3x1 +2 x2 12。因为3×7/2 + 2×3/2 12，故原问题最优解不是本例的最优解。,5灵敏度分析,在试验工序中加入松驰变量得：3X1+ 2X2 +X6= 12,5灵敏度分析,5灵敏度分析,在前面的例子中， 新增加电力约束：13 A、B、C每单位需电 2、1、3,问：原方案是否改变？,新增加的约束条件为：2X1 +X2 +3X3 13,原方案 A：4 B：8 C：0 16 13 原方案要改变,加入松驰变量：2X1 +X2 +3X3 +X6 = 13,练 习 题,一、判断下列说法是否正确？ (1)任何线性规划问题存在并具有唯一的对偶问题； (2)对偶问题的对偶问题一定是原问题； (3)根据对偶问题的性质，当原问题为无界解时，其对偶问题无可行解，反之，当对偶问题无可行解时，其原问题具有无界解； (4)设x,y 分别为标准形式的原问题与对偶问题的可行解，x*，y*分别为其最优解，则恒有 cx cx*= cy* cy （5)若线性规划的原问题有无穷多最优解，则其对偶问题也一定具有无穷多最优解；,(6)已知yi*为线性规划的对偶问题的最优解，若yi*0，说明在最优生产计划中第i种资源已完全耗尽； (7)已知yi*为线性规划的对偶问题的最优解，若yi=0，说明在最优生产计划中第i种资源一定有剩余； (8)若某种资源的影子价格等于k，在其它条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k； (9)应用对偶单纯形法计算时，若单纯形表中某一基变量xi0，又xi所在行的元素全部大于或等于零，则可以判断其对偶问题具有无界解；,练 习 题,Abdefik对 cghj错 12456911 37810,(10)若线性规划问题中的b,c值同时发生变化，反映到最终单纯形表中，不会出现原问题与对偶问题均为非可行解的情况； (11)在线性规划问题的最优解中，如某一变量xj为非基变量，则在原来问题中，无论改变它在目标函数中的系数cj，或在各约束中的相应系数aij,反映到最终单纯形表中，除该列数字有变化外，将不会引起其它列数字的变化。,练 习 题,二、已知线性规划问题,用单纯形法求解得最终单纯形表如表,求a11 , a12 , a13 , a21 , a22 , a23 , b1 , b2 , c1 , c2 , c3,练 习 题,三、已知下表是求其极大化线性规划问题的初始单纯形表和迭代计算中某一步的表。试求表中未知数a-l的值。,练 习 题,四、已知线性规划问题,其对偶问题最优解为yl1.2，y20.2，试根据对偶理论求出原问题的最优解,练 习 题,五、己知线性规划问题,1)写出其对偶问题； (2)已知原问题最优解为X*(1，1，2，0)，试根据对偶理论，直接求出对偶问题的最优解。,练 习 题,作 业,P77 2.1(1)(2) P79 2.9(2) P80 2.12,