【上财系列】运筹学课件第二章对偶理论与灵敏度分析.ppt

第二章 对偶理论与灵敏度分析,对偶问题的提出 原问题与对偶问题的关系 对偶问题的基本性质 对偶问题的经济解释-影子价格 对偶单纯形法 灵敏度分析 参数线性规划,2.1 对偶问题的提出 一、对偶线性规划问题,某工厂计划安排生产、两种产品，已知每种单位产品的利润、生产单位产品所需的设备台时及a、b两种原材料的消耗、现有原材料和设备台时的定额如下表所示：,【例1】,原问题的策略: 问应如何安排生产才能使工厂获利最大？,现在的策略: 假设不生产、产品 ,而是计划将现有资源出租或出售,从而获得利润,这时需要考虑如何定价才合理?,设x1、x2分别表示计划生产产品、的单位数量，由题意原问题的模型为：,工厂获得最大利润,符合资源限制,原问题的模型,改变策略后，需要考虑如何给资源定价的问题！,设y1、y2 、y3分别表示出租单位设备台时的租金和出售单位原材料a、b的利润.,y1+4y22，,2y1+4y33,则：,工厂出租设备、原材料的租金要大于生产的利润才合算。,工厂把所有设备台时和资源都出租和出让，其收入为：,要寻找使租用者支付的租金最少的策略。即求 min g,新问题的模型,工厂改变策略以后的数学模型为：,工厂获得相应利润,用户所付租金最少,联系在于，它们都是关于工厂生产经营的模型,并且使用相同的数据； 区别在于,它们所反映的实质内容是完全不同的：前者是站在工厂经营者的立场上追求工厂的销售收入最大，而后者则是站在谈判对手的立场上寻求应付工厂租金最少的策略。,原模型和对偶模型的联系与区别,由以上不难得到，所谓对偶规划，就是与线性规划原问题相对应并使用同一组数据按照特定方法形成的另一种反映不同性质问题的线性规划模型。,原问题与对偶问题之间存在着严格的对应关系。如原问题如求目标函数最大化，对偶问题即求目标函数最小化；原问题目标函数的系数变成为对偶问题的右边项，而原问题的约束的右边项则变成为对偶问题目标函数的系数；对偶问题的系数矩阵是原问题系数矩阵的转置。,原问题的一般模型可定义为：,二、对偶规划的一般数学模型对偶规划一,相应的对偶问题的一般模型可定义为：,上述的原问题p和对偶问题 d还可以用矩阵形式写为：,其中,上述的对偶模型满足下列两个条件：（1）所有的变量都是非负的；（2）约束条件都是同向不等式，称为对称型对偶模型。而在当原问题转化为标准型以后所建立的对偶模型则是非对称型的，这时该如何写出其相应的对偶模型？,矩阵形式,2. 2 原问题与对偶问题的对应关系,当我们讨论对偶问题时必定是指一对问题，因为没有原问题也就不可能有对偶问题。原问题和对偶问题总是相依存在的。同时，原问题和对偶问题之间也并没有严格的界线，它们互为对偶，谁都可以是原问题，谁也都可以是对偶问题。,(1) 一个问题中的约束条件个数等于另一个问题的变量数。 (2) 一个问题的目标函数中的系数是另外一个问题中约束不等式的右端项。 (3) 约束条件在一个问题是“”，在另一个问题是“”。 (4) 目标在一个问题是求极小，在另一个问题是求极大。,对偶线性规划与原问题的比较:,下表给出了原问题模型和对偶模型的对应关系，可以看作是一个线性规划原问题转化为对偶问题的一般规律。,线性规划问题对偶关系表（原问题(maxz),注意掌握记忆规律）,原问题 对偶问题 目标函数max 目标函数min,原问题(maxz)与对偶之关系：,原问题(maxz)口诀: 约束决定变量是反号,原问题(maxz)口诀: 变量决定约束是同号,线性规划问题对偶关系表（原问题(min s)注意掌握记忆规律）,原问题 对偶问题 目标函数min 目标函数max,原问题(mins) 与对偶之关系：,原问题(mins)口诀: 约束决定变量是同号,原问题(mins)口诀: 变量决定约束是反号,解：,依线性规划问题的对偶关系，有：,（还可依对偶问题写出原问题）,例1,写出下列问题的对偶问题：,变量决定约束是同号,约束决定变量是反号,min w=15y1+24y2+5y3,6y2+y3 2 5y1 +2y2 +y3 1 y1 , y2 , y3 0,s.t.,解：,依线性规划问题的对偶关系，有：,s.t.,，,（还可依对偶问题写出原问题）,例2,写出下列问题的对偶问题：,s.t.,1,3,2,1,+,-4,x,x,2x,x1,x2,x3 0,变量决定约束是反号,约束决定变量是同号,，,练习：试求下列线性规划问题的对偶问题,答案：,s.t.,，,练习：试求下列线性规划问题的对偶问题,maxz=5y1+4y2+6y3 y1+2y2 2 y1 +2y2 +y3 3 -3y1 +y3 -5 y1 -y2 +y31 y1 0, y2 , y3 0,答案：,定理1 （对称性定理）,2.3 对偶问题的基本性质,定理2 （弱对偶定理）,即对偶问题的对偶是原问题。,设x和y分别是原问题和对偶问题的可行解，则必有cxyb,定理3 （无界性）,若原问题(对偶问题)为无界解，则其对偶问题(原问题)为无可行解。,若原问题有可行解对偶问题无可行解，则原问题一定无界；反之，如对偶问题有可行解原问题无可行解，则对偶问题一定无界。,定理4 （可行解是最优解的性质）,定理5 （强对偶定理）,设x*是原问题的可行解，y*是对偶问题的可行解，当cx*=y*b时， x*与y*是最优解 。,若原问题有最优解，那么对偶问题也有最优解，且目标函数值相等。,综合上述结论得原问题与对偶问题的解的关系,原问题与对偶问题解的对应关系,定理6（互补松弛定理）,若x,y分别是原问题和对偶问题的可行解，那么yxs=0和ysx=0，当且仅当x,y为最优解。即： 在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。,原始问题和对偶问题最优解之间的互补松弛关系,maxz=cx s.t. axxs=b x, xs0,min w=yb s.t. ya-ys=c y, ys0,max z=cx s.t. axb x 0,min w=b s.t. ac 0,互补松弛关系,maxz=cx s.t. ax+xs=b x, xs 0,minw=yb s.t. ya-ys=c y, ys 0,ysx=0 yxs=0,n,m,=,a,xs,i,b,m,x,原始问题和对偶问题变量、松弛变量的维数,y1 yi ym ym+1 ym+j yn+m,x1 xj xn xn+1 xn+i xn+m,对偶问题的变量 对偶问题的松弛变量,原始问题的变量 原始问题的松弛变量,xjym+j=0 yixn+i=0 (i=1,2,m; j=1,2,n) 在一对变量中，其中一个大于0，另一个一定等于0,讨论:,互补松弛定理也称松紧定理，它描述了线性规划达到最优时，原问题（或对偶问题）的变量取值和对偶问题（或原问题）约束松紧之间的对应关系。我们知道，在一对互为对偶线性规划问题中，原问题的变量和对偶问题的约束一一对应，原问题的约束和对偶问题的变量一一对应。当线性规划问题达到最优时，我们不仅同时得到了原问题和对偶问题的最优解，而且也还得到了变量和约束之间的一种对应关系。互补松弛定理即揭示了这一点。,1.如果原问题的某一约束为紧约束（严格等式:松弛变量为零），该约束对应的对偶变量应大于或等于零；,2.如果原问题的某一约束为松约束（严格不等式:松弛变量大于零），则对应的对偶变量必为零；,3.如果原问题的某一变量大于零，该变量对应的对偶约束必为紧约束(严格等式)；,4.如果原问题的某一变量等于零，该变量对应的对偶约束可能是紧约束(严格等式)，也可能是松约束(严格不等式)。,线性规划达到最优时的关系,定理7 单纯形求解中原问题与对偶问题的最优解的关系,设原问题是 maxz=cx;axxs=b;x, xs0 它的对偶问题是 min w=yb; ya-ys=c; y, ys0 用单纯形法求解线性规划时，迭代的每一步在得到原问题一个基本可行解的同时，其检验数行的（zj-cj）值是其对偶问题的一个基本解yi ；在单纯形表中，原问题的松驰变量对应对偶问题的变量，对偶问题的剩余变量对应原问题的变量； 即：原问题单纯形表的检验数行对应其对偶问题的一个基本解。特别地，原问题加入松弛变量检验数的相反数对应于对偶问题的基本解。 这些互相对应的变量如果在一个问题的解中是基变量，则在另一问题的解中是非基变量；将这两个解代入各自的目标函数中有 z=w。,min w = 2y1 +y2 s.t. y1 2y2 1 y1 + y2 1 y1 y2 0 y1,y2 0,应用上述性质求解线性规划问题,试用对偶理论证明上述规划问题为无界解。,由第一约束条件可知对偶问题无可行解，则原问题的解无界或无可行解， 由于原问题存在可行解，所以解无界。,解 该问题存在可行解，如x=(0，0，0)；,其对偶问题为：,22,1/5 3,17/55,7/5 2,3=3,解 写出对偶问题为： max z = 4y1 + 3y2 s.t. y1 + 2y2 2 y1 y2 3 2y1 +3y2 5 y1 + y2 2 3y1 +y2 3 y1,y2 0,又例,已知对偶问题的最优解为 y1 = 4/5, y2 = 3/5, 试应用对偶理论解原问题。,x2 = 0,x3 = 0,x4 = 0,等号,将y1、y2的值代入，得知、为严格不等式，于是由互补松弛定理知，必有x2 = x3 = x4 = 0；又因y1,y2 0，故原问题的两个约束必为紧约束，于是有：,x*=(1,0,0,0,1) minz=5,解之，有：x1 = x5 = 1。,max.z=2x1+4x2+x3+x4 s.t. x1+3x2 +x48 2x1+x2 6 x2 + x3 +x46 x1 + x2 +x3 9 xj0（j=1,2,3,4）,附 练习答案：y1=4/5, y2=3/5, y3=1, y4=0,已知原问题的最优解为:x*=(2,2,4,0)t，试根据互补松弛定理解出其对偶问题的最优解。,线性规划问题的对偶问题为： min.z=8y1+6y2+6y3+9y4 s.t. y1+2y2 +y4 2 3y1+y2 + y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）,练习：已知线性规划问题为：,为严格不等式，由互补松弛定知，必有y4 = 0；,max.z=2x1+4x2+x3+x4 s.t. x1+3x2 +x48 2x1+x2 6 x2 + x3 +x46 x1 + x2 +x3 9 xj0（j=1,2,3,4）, 8=8, 6=6, 6=6, 89,解之，有： y1=4/5, y2=3/5, y3=1，y4 = 0,答案：因为原问题的最优解为:x*=(2,2,4,0)t ：,又因x1, x2 , x30，故对偶问题的前三个约束必为紧约束,线性规划问题的对偶问题为： min.z=8y1+6y2+6y3+9y4 s.t. y1+2y2 +y4 2 3y1+y2 + y3 +y4 4 y3 +y4 1 y1 +y3 1 yj0（j=1,2,3,4）,等号,2.4 对偶问题的经济解释影子价格,影子价格的定义： 上式中对偶变量yi的意义代表对一个单位第i种资源的估价。这种估价不是资源的市场价格，而是根据资源在生产中做出的贡献而作的估价，称为影子价格。 影子价格的意义： （1）资源的市场价格是已知数，相对比较稳定，而它的影子价格则有赖于资源的利用情况，是未知数。由于企业生产任务、产品结构等情况发生变化，资源的影子价格也随之改变。 （2）影子价格是一种边际价格。由于 。这说明yi的值相当于在给定的条件下，bi每增加一个单位时目标函数z的增量。 影子价格越大，说明这种资源越是相对紧缺 影子价格越小，说明这种资源相对不紧缺 -,（3）资源的影子价格实际上又是一种机会成本。当某种资源的市场价格低于影子价格时，企业应买进资源用于扩大再生产；当某种资源的市场价格高于企业影子价格时，则企业的决策者应把已有资源卖掉。 （4）互补松弛关系的经济解释,在利润最大化的生产计划中 （1）影子价格大于0的资源没有剩余 （2）有剩余的资源边际利润等于0,现应用单纯形方法同时求解两问题,原问题是：,maxz=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,原问题的标准型是：,maxz=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi 0,maxz=2x1 +x2+0x3+0x4 +0x5 5x2 +x3 =15 6x1 + 2x2 +x4 = 24 x1 + x2 +x5 = 5 xi 0,最终单纯形表,原问题最优解:x*=(7/2,3/2,15/2,0,0)t，z*=17/2,原问题变量,原问题松驰变量,对偶问题剩余变量 y4、y5,对偶问题变量 y1、y2 、y3,对偶问题最优解:y*=(0,1/4,1/2,0,0)t，s*=17/2,其检验数行的yi和（zj-cj）值是其对偶问题的一个基本解,2.5 对偶单纯形法,一、 用对偶单纯形方法解线性规划 对偶单纯形法是使用对偶原理求解原问题解的一种方法，而不是求解对偶问题解的单纯形方法。与对偶单纯形方法相对应，已有的单纯形方法称原始单纯形法。,两种方法的主要区别在于：,而对偶单纯形方法在整个迭代过程中，则是始终保持对偶问题的可行性即 亦即, ，也就是全部检验数0，最后达到全部右边项由有负分量逐步变为全部右边项0,即满足原问题的可行性时为止。,所以,对偶单纯形法实质就是在保证对偶问题可行的条件下向原问题可行的方向迭代。,原始单纯形方法在整个迭代过程中，始终是保持原问题的可行性，即或，最后达到检验数 即 即maxz取得最优值时为止, 而 也就是 ，,对偶单纯形法的解题步骤：,（1）写出与已有的初始基b对应的初始单纯形表。根据模型的标准型，若右边项的数字都为非负，且检验数都为非正，则已得到最优解，计算结束；否则，若右边项中至少有一个负分量，且检验数也仍然非正，则进行如下计算。,（2）确定换出变量。若有： 则以对应的变量 xr为换出变量。,（3）确定换入变量。在单纯形表中观察xr所在行的各系数arj，若所有的arj0，则无可行解，停止计算；否则若存在：,， 则以xk为换入变量。,（4） 以ark为主元按原始单纯形法进行迭代，得到新的单纯形表。,现应用对偶单纯形方法解下述线性规划问题,原问题是：,原问题的标准型是：,maxw= -15y1-24y2-5y3 +0y4 +0y5 6y2+y3 - y4 = 2 5y1 +2y2 +y3 - y5 =1 y1 , y2 , y3 , y4 , y5 0,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5 0,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5 0,最优解:y*=(0,1/4,1/2,0,0)t，w*=-17/2,minz=17/2,应用对偶单纯形方法之矩阵法,maxw= -15y1-24y2-5y3 +0y4 +0y5 -6y2 - y3 + y4 = - 2 -5y1 -2y2 -y3 + y5 = - 1 y1 , y2 , y3 , y4 , y5 0,最优解:y*=(0,1/4,1/2,0,0)t， w*=-17/2 minz=17/2,现应用对偶单纯形方法解下述线性规划问题,原问题是：,原问题的标准型是：,maxz= -2x1-3x2-4x3 +0x4 +0x5 x1+ 2x2+x3 - x4 = 3 2x1 - x2 +3x3 - x5 =4 x1 , x2 , x3 , x4 , x5 0,maxw= -2x1-3x2-4x3 +0x4 +0x5 -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,最优解:x*=(11/5,2/5,0,0,0)tmaxw=-28/5,maxw= -2x1-3x2-4x3 +0x4 +0x5 -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,从而z*=28/5,应用对偶单纯形方法之矩阵法,最优解:y*=(11/5,2/5,0,0,0)t，maxw =-28/5,maxw= -2x1-3x2-4x3 +0x4 +0x5 -x1 -2x2 - x3 +x4 = - 3 -2x1 + x2 -3x3 + x5 = - 4 x1 , x2 , x3 , x4 , x5 0,minz* = 28/5,对偶单纯形法的优点及局限：,优点： （1）初始解可以不是可行解，当检验数都非正时，即可以进行基的变换，这时不需要引进人工变量 ，因此就简化了计算。 （2）对于变量个数多于约束方程个数的线性规划问题，采用对偶单纯形法计算量较少。因此对于变量较少、约束较多的线性规划问题, 可以先将它转化成对偶问题，然后用对偶单纯形方法求解。 （3）在灵敏度分析中，有时需要使用对偶单纯形法，这样可以简化计算。 局限： 在求解线性规划时很少单独使用。,灵敏度分析，是指对系统或事物因周围条件变化所表现出的敏感性程度的分析。,在前面讲的线性规划问题中，通常都是假定问题中的aij， bi， cj系数是已知的常数,但实际上这些参数都是一些估计或预测的数字。在现实中，如果市场条件变化， cj值就会发生变化；如果工艺技术条件改变，则aij就会变化；如果资源的可用量发生变化，则bi也会发生变化。因此就必然会提出这样的问题，即当这些参数中的一个或几个发生变化时，问题的最优解会有什么变化，或者说，当这些参数在一个多大的范围内变化时,问题的最优解才会保持不变。这就是灵敏度分析所要研究解决的问题。,2.6 灵敏度分析,当然，如果线性规划问题中的一个或几个参数变化时，完全可以用单纯形法从头计算，看最优解有无变化，但这样做既麻烦又没有必要。因为由单纯形的迭代过程我们知道，线性规划的求解是从一组基向最变换为另一组基向量，其中每步迭代得到的数字只随着基向量的不同选择而有所改变，因此完全有可能把个别参数的变化直接在获得最优解的最终单纯形表上反映出来。这样就不需要从头计算，而只需对获得最优解的单纯形表进行审查，看一些数字变化后是否仍满足最优解的条件,如果不满足的话,再从这个表开始进行迭代计算，求得最优解即可。这也就是灵敏度分析。在这里，仅介绍价值向量和资源约束的灵敏度分析。,灵敏度分析的步骤如下：,1.将参数的改变计算反映到最终单纯形表上来,b*=b-1 b,具体计算方法是，按下列公式计算出由参数aij、bi、 cj的变化而引起的最终单纯形表上有关数字的变化：,pi*=b-1 pi,(cj-zi)*= (cj-zi) -aijyi*,2.检验原问题是否仍为可行解；,3.检验对偶问题是否仍为可行解；,4.按下表所列情况得出结论和决定继续计算的步骤。,判定表,一、分析cj变化的影响,目标函数中的系数cj的变化仅仅影响到检验数(cj-zi)的变化。所以将cj 的变化直接反映到最终单纯形表中，只可能出现表中的前两种情况。,【例】已知线性规划问题：,maxz=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,用单纯形法求得最终单纯形表如下,最终单纯形表,试确定： (a)当目标函数变为max z=5x1 +1.5x2时，最优解会出现什么变化；,(b) 目标函数变为max z=(2+l) x1+x2时， l在什么范围变化，最优解不变；,maxz=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,maxz=5x1 +1.5 x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,【解】,(a)将目标函数系数的变化直接反映到最终单纯形表中,变量x5的检验数为正，继续迭代；,maxz=5x1 +1.5 x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,继续迭代得下表,即得新解x1=4， x2=0 此时maxz=20,【解】,(b)将目标函数系数的变化直接反映到最终单纯形表中,为使表中解为最优，应有,-1/4-1/4l0， -1/2+1/2l0,即得 -1 l1,二、分析bi变化的影响,bi的变化在实际问题中表明可用资源的数量发生变化，其变化反映到最终单纯形表上只引起基变量列数字变化。因此灵敏度分析的步骤为：,1.由b*=b-1b算出b*，将其加到基变量列的数字上；,2.由于其对偶问题仍为可行解，故只需检查原问题是否仍为可行解，再按相应步骤进行。,注:此公式是单纯形法求解的推导结果!,【例】上例中,最终单纯形表,(a)若第2个约束条件右端项增大到32，分析最优解变化；,(b)若第2个约束条件变为 6x1+2x224+l，分析l在什么范围内变化，表中基为最优基；,maxz=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,maxz=2x1 + x2 5x2 15 6x1 + 2x2 32 x1 + x2 5 x1 , x2 0,【解】 (a)第2个约束条件右端项增大到32,因,因表中原问题为非可行解，故用对偶单纯形法继续计算,将其加到最终单纯形表的基变量b这一数列上得下表,35/2 11/2 -1/2 -21/2,继续迭代得下表,即得新的最优解x1=5， x2=0， z*=10,【解】 (b)若第2个约束条件变为 6x1+2x224+l,因,将其加到最终单纯形表的基变量b这一数列上得下表,15/2+5l/4 7/2+l/4 3/2-l/4 -17/2-l/4,【解】,表中基为最优基的条件为：,15/2+5/4l0 l-6,即得 -6 l6,7/2+1/4l0 l-14,3/2-1/4l0 l6,三、增加一个变量的分析,增加一个变量在实际问题中反映为增加一种新的产品。分析步骤是：,1.计算sj=cj-zi= cj -aijyi*,其中yi*是对偶问题的解,2.计算pi=b-1pi,3.若sj0，只需将pi和sj 的值直接反映到最终单纯形表中，原最优解不变；若sj0，则按单纯形法继续迭代计算。,注:此公式是单纯形法求解的推导结果!,其中cj 是新变量目标函数系数, aij是新变量约束函数系数yi*是对偶问题的解,【例】上例中,最终单纯形表,若增加一个变量x6，有c6=3, p6=(3,4,2)t，试分析最优解的变化。,maxz=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,maxz=2x1 + x2 +3 x6 5x2 +3x6 15 6x1 + 2x2 +4x6 24 x1 + x2 +2x6 5 x1 , x2 , x6 0,【解】,将其反映到最终单纯形表中得下表,因s6=10 ,故用单纯形法继续计算,继续迭代得下表,由此得新的解为,x1=7/2， x2=0， x6=3/4，max z*=27/2+33/4=37/4,四、分析aij变化的影响,假如xj在最终表中为基变量，则aij的变化将使最终表中的b-1变化，因此有可能出现原问题与对偶问题均为非可行解的情况。,【例】上例中， c2=3，x2的系数向量变为p2=(8，4，1)t，试分析最优解的变化。,【解】同上例,maxz=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,maxz=2x1 +3x2 8x2 15 6x1 + 4x2 24 x1 + x2 5 x1 , x2 0,因s 2 =3/20 ,故用单纯形法将x2替换出基变量中的x2， x2不再保留。,先将其作为一个新的变量x2，故用单纯形法将x2替换出基变量中的x2，并在下一个表中不再保留x2,继续迭代得下表,因原问题与其对偶问题均为非可行解，通过引入人工变量将原问题转化为可行解，再用单纯形法继续计算。将第一行x3+4x4 -24x5=-9 化为标准型-x3-4x4 +24x5=9,再加上人工变量 -x3 -4x4 +24x5 +x6 =9,因s5 0 ,故用单纯形法迭代计算,x34x4 +24x5 +x6 =9,继续迭代得下表,新的最优解为x1=11/4， x2=15/8，z*=211/4+315/8=89/8,五、增加一个约束条件的分析,增加一个约束条件，在实际问题中相当于增添一道工序。分析的方法是先将原来的问题的最优解变量取值代入这个新增的约束条件中，如满足，说明新增约束未起到限制作用，原最优解不变。否则，将新增约束直接反映到最终表中，再进行分析。,【例】上例中， 新增添一个约束条件 3x1+2x2 12，试分析最优解的变化。,【解】先将原问题最优解x1 =7/2, x2 =3/2代入新约束条件，因有,故将约束条件写成3x1+2x2 +x6 = 12，并取x6为基变量，直接反映到最终表中,37/2+23/2=27/212,maxz=2x1 + x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 3x1 +2x2 12 x1 , x2 0,得下表,x1与x2的向量不是单位向量，要继续变换,得下表,用对偶单纯形法迭代继续变换,得下表,新的最优解为x1=4， x2=0，z*=24 = 8,2.7 参数线性规划,参数aij、bi、 cj在什么范围内变化时最优解不变是实际问题中常常要研究的问题，当这些参数超出这个范围时，最优解会发生怎样的变化，即为参数线性规划要研究的问题。,【例】线性规划问题,maxz(l)=2x1 +x2 5x2 15 6x1 + 2x2 24 x1 + x2 5+l x1 , x2 0,第三个约束右端不断增大，分析最优解会发生怎样的变化？,此时l 0,参数线性规划求解步骤,1.令l=0求解得最终单纯形表,2.将参数的变化反映到最终单纯形表中；因,反映到最终单纯形表中,3.让 l逐步增大，观察原问题与对偶问题解的变化，看哪一个首先出现非可行解。,本例中0 l1方案已为最优,此时x1= 7/2-(1/2) l,x2= 3/2 +(3/2) l,z*= 17/2+(1/2) l,当 l1时，用对偶单纯形法迭代,当 l继续增大，原问题与对偶问题都保持可行解，故计算至此结束。,当 l1时，用对偶单纯形法迭代计算得,结论： l1,x1= 7/2-(1/2) l,x2= 3/2 +(3/2)l, maxz= 17/2+(1/2) l l1,x1= 3, x2= 3, maxz= 9,【图示】目标函数z(l)与l的变化关系图,9,l1, z= 17/2+(1/2) l,l1, z= 9,注：问题中多个参数变化时，应使目标函数z(l)是l的线性函数。,【例】求解下述参数线性规划问题,maxz=（2+l)x1 +(1+2l)x2 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0,【解】按参数线性规划求解问题的第一、二步，令l=0求得最优解，并将cj的变化值反映到最终单纯形表中。,反映到最终单纯形表中,当 - 1/5l1时，表中解为最优解。此时,当l1 ，变量x4的检验数为正值，用单纯形法继续迭代得,z*=7/2(2+l)+3/2 (1+2l)= 17/