第6章++单纯形法的灵敏度分析与对偶课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,管 理 运 筹 学,1,第六章 单纯形法的灵敏度分析与对偶,1,单纯形表的灵敏度分析,2,线性规划的对偶问题,3,对偶规划的基本性质,4,对偶单纯形法,2,1,单纯形表的灵敏度分析,一、目标函数中变量,C,k,系数灵敏度分析,1.,在最终的单纯形表里，,X,k,是非基变量,由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与,C,k,没有任何关系，,所以当,C,k,变成,C,k,+ C,k,时，在最终单纯形表中其系数的增广矩阵不变，又因为,X,k,是非,基变量，所以基变量的目标函数的系数不变，即,C,B,不变，可知,Z,k,也不变，只是,C,k,变,成了,C,k,+ C,k,。这时,K,= C,k,-Z,k,就变成了,C,k,+ C,k,- Z,k,=,K,+ C,k,。要使原来的最优解,仍为最优解，只要,K,+ C,k,0,即可，也就是,C,k,的增量,C,k,-,K,。,2.,在最终的单纯形表中，,X,k,是基变量,当,C,k,变成,C,k,+ C,k,时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目,标函数的系数,C,B,变了，则,Z,J,(J=1,2,.,N),一般也变了，不妨设,C,B,=(C,B1,C,B2,。,C,k,，,C,Bm,),当,C,B,变成,=(C,B1,C,B2,。,C,k,+ C,k,C,Bm,),则：,Z,J,=(C,B1,C,B2,。,C,k,，,C,Bm,)(,a,1j,a,2j,a,Kj,a,mj,),Z,J,=(C,B1,C,B2,。,C,k,+ C,k,，,C,Bm,)(,a,1j,a,2j,a,Kj,a,mj,) = Z,J,+,C,k,a,Kj,3,1,单纯形表的灵敏度分析,根据上式可知,检验数,J,(J=1,2,.,M),变成了,J,有,J,=C,J,-Z,J,=,J,+ C,K,a,Kj,。要使最优解不变，只要当,J K,时，,J,0,，就可求出,的取值范围，也就是使得第,K,个约束条件的对偶价格不变的,b,k,的变化范围。,，,12,1,单纯形表的灵敏度分析,下面我们仍以第二章例,1,在最终单纯形表上对,b,j,进行灵敏度分析。,最终单纯形表如下所示：,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,b,50 100 0 0 0,2,X,1,50,1 0 1 0 -1,50,S,2,0,0 0 -2 1 1,50,X,2,100,0 1 0 0 1,250,Z,J,50 100 50 0 50,27500,C,J,-Z,J,0 0 -50 0 -50,13,1,单纯形表的灵敏度分析,我们对,b,1,进行灵敏度分析，因为在第一个约束方程中含有松弛变量,S,1,实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台,时数在,250,与,325,之间变化，则设备台时数的对偶价格不变，都为每台设备,台时,50,元。,14,1,单纯形表的灵敏度分析,三、约束方程系数矩阵,A,灵敏度分析,下面分两种情况讨论,1.,在初始单纯形表上的变量,X,k,的系数列,P,k,改变为,P,k,经过迭代后，在最终单纯形表,上,X,k,是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换，,P,k,变成,P,k,仅仅影响最终单纯形表上第,k,列数据，包括,X,k,的系数列、,Z,k,以及,k,，这时最终单纯形表上的,X,k,的系数列就变成了,B,-1,P,j,而,Z,k,就变成,C,B,B,-1,P,k,，新的检验数,k,=C,k,-C,B,B,-1,P,k,。若,k,0,，则原最优解仍然为最优解。若,k,0,，则继续进行迭代以求出最优。,例,以第二章例,1,为基础，设该厂除了生产,，,种产品外，现在试制成一个新产品,，已知生产,产品,每件需要设备,2,台时，并消耗,A,原料,0.5,公斤。,B,原料,1.5,公斤，获利,150,元，问该厂应该生产该产品多少？,解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量,X,3,在初始表上的系数列的问题，,15,1,单纯形表的灵敏度分析,接上页,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,X,3,b,50 100 0 0 0 150,X,1,50,1 0 1 0 -1 0.5,50,S,2,0,0 0 -2 1 1 -2,50,X,2,100,0 1 0 0 1 1.5,250,Z,J,50 100 50 0 50 175,27500,C,J,-Z,J,0 0 -50 0 -50 -25,16,1,单纯形表的灵敏度分析,例 假设上例题中产品,的工艺结构有了改进，这时生产,1件,产品需要使用,1.5,台设备 ，消耗原料,A,为,2,千克，原料,B,为,1,千克，每件,产品的利润为,160,元，问该厂的生产计划是否要修改,。,解：首先求出,X,3,在最终表上的系数列,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,X,3,b,50 100 0 0 0 150,2,X,1,50,1 0 1 0 -1 0.5,50,50/0.5,S,2,0,0 0 -2 1 1 0,50,X,2,100,0 1 0 0 1 1,250,250/1,Z,J,50 100 50 0 50 125,27500,C,J,-Z,J,0 0 -50 0 -50 35,17,1,单纯形表的灵敏度分析,接下来又可以有新的迭,代,S,3,进基，,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,X,3,b,50 100 0 0 0 150,3,X,3,160,2 0 2 0 -2 1,100,-,S,2,0,0 0 -2 1 1 0,50,50/1,X,2,100,-20 1 -2 0 3 0,150,250/3,Z,J,120 100 120 0 -20 160,31000,C,J,-Z,J,-70 0 -120 0 20 0,18,1,单纯形表的灵敏度分析,接上页,可知此规模的最优解,X,1,=0, X,2,=0, S,1,=0, S,2,=0, S,3,=50, X,3,=200,此时，最大目标函数为,32000,元。也就是说，该厂的新的生产计划为不生产,、,产品，生产,产品,200,件,可获得最大利润,32000,元。,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,X,3,b,50 100 0 0 0 150,4,X,3,160,2 0 2 0 -2 1,200,-,S,3,0,0 0 -2 1 1 0,50,50/1,X,2,100,-2 1 4 -3 0 0,0,250/3,Z,J,120 100 80 20 0 160,32000,C,J,-Z,J,-70 0 -80 -20 0 0,19,1,单纯形表的灵敏度分析,2.,在初始表上的变量,X,K,的系数,P,K,改变为,P,K,，经,过迭代后，在最终,表上,X,K,是基变量，在这种情况下,原最优解的可行性和最优解都可能被破坏，问题十分,复杂，一般不去修改原表而是直接计算。,20,1,单纯形表的灵敏度分析,四、增加一个约束条件的灵敏度分析,在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。,下面仍以第三章例,1,为例来加以说明。,例：假如该工厂除了在设备台时，原材料,A,、,B,上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为,5000,度，而生产一个,产品需要用电,10,度，而生产一个,产品需要用电,30,度。试分析此时该厂获得最大利润的生产计划？,21,1,单纯形表的灵敏度分析,解：先将原问题的最优解,=50,，,=250,代入用电量的约束条件,得：,1050+30,250=500+75005000,所以原题的最优解不是本题的最优解。,在用电量的约束条件中加入松驰变量,S,4,后得：,把这个约束条件加入到原最终单纯形表上，其中,S,4,为基变量，得表如下：,迭代次数,基变量,b,比值,50,100,0,0,0,0,50,1,0,1,0,-1,0,50,0,0,0,-2,1,1,0,50,100,0,1,0,0,1,0,250,0,10,30,0,0,0,1,5000,50,100,50,0,50,0,27500,0,0,-50,0,-50,0,22,1,单纯形表的灵敏度分析,在上表中的,X,1,，,X,2,不是单位向量，故进行行的线性变换，得,迭代,次数,基变量,C,B,x,1,x,2,s,1,s,2,s,3,s,4,b,比值,50,100,0,0,0,0,x,1,50,1,0,1,0,-1,0,50,s,2,0,0,0,-2,1,1,0,50,x,2,100,0,1,0,0,1,0,250,s,4,0,0,0,-10,0,-20,1,-3000,z,j,50,100,50,0,50,0,27500,0,0,-50,0,-50,0,把上表中的,S,4,行的约束可以写为：,上式两边乘以（,-1,），再加上人工变量,a,1,得：,用上式替换上表中的,S,4,行，得下表：,23,1,单纯形表的灵敏度分析,迭代次数,基变量,x,1,x,2,s,1,s,2,s,3,s,4,a,1,b,比值,50,100,0,0,0,0,-M,x,1,50,1,0,1,0,-1,0,0,50,s,2,0,0,0,-2,1,(1),0,0,50,x,2,100,0,1,0,0,1,0,0,250,s,4,-M,0,0,-10,0,-20,1,1,3000,z,j,50,100,50-10M,0,50-20M,0,-M,0,0,10M-50,0,20M-50,0,0,x,1,50,1,0,-1,1,0,0,0,100,s,3,0,0,0,-2,1,1,0,0,50,x,2,100,0,1,2,-1,0,0,0,200,s,4,-M,0,0,50,-20,0,-1,1,2000,z,j,50,100,150-50M,20M-50,0,M,-M,0,50M-150,50-20M,0,-M,0,x,1,50,1,0,0,3/5,0,-1/50,1/50,140,s,3,0,0,0,0,1/5,1,-2/50,2/50,130,x,2,100,0,1,0,-1/5,0,2/50,-2/50,120,s,4,0,0,0,1,-2/5,0,-1/50,1/50,40,z,j,50,100,0,10,0,3,-3,0,0,-10,0,-3,-M+3,24,1,单纯形表的灵敏度分析,由上表可知，最优解为：,即该工厂在添加了用电限量以后的最优生产计划为,产品生产,140,件，,产品生产,120,件。,25,每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。,例题,1,某工厂在计划期内安排,、,两种产品，生产单位产品所需设备,A,、,B,、,C,台时如表所示,该工厂每生产一单位产品 可获利,50,元，每生产一单位产品,可获利,100,元，问工厂应分别生产多少 产品和,产品，才能使工厂获利最多？,解：设 为产品 的计划产量， 为产品,的计划产量，则有,目标函数：,Max,z,=50 +100,约束条件：,，,2,线性规划的对偶问题,26,现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备,A,、,B,、,C,，那么该厂的厂长应该如何来确定合理的租金呢？,设 分别为设备,A,、,B,、,C,的每台时的租金。为了叙述方便，这里把租金定义为扣除成本后的利润。作为出租者来说，把生产单位 产品所需各设备的台时各总租金不应低于原利润,50,元，即 ，否则就不出租还是用于生产 产品以获利,50,元；同样把,生产一单位 产品所需各设备的台时的总租金也不应当低于原利润,100,元， 即,，否则这些设备台时就不出租，还是用于生产 产品以获利,100,元。但对于租用者来说，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，即,min,，这样我们得到了该问题的数学模型：,目标函数：,约束条件：,这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做,原问题,，而另外一个叫,对偶问题,。,2,线性规划的对偶问题,27,如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。,1,求目标函数最大值的线性规划问题中有,n,个变量,m,个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有,m,个变量,n,个约束条件，其约束条件都为大于等于不等式。,2,原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第,i,个变量的系数就等于对偶问题中的第,i,个约束条件的右边常数项。,3,原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第,i,个约束条件的右边常数项就等于零对偶问题的目标函数中的第,i,个变量的系数。,4,对偶问题的约束条件的系数矩阵,A,是原问题约束矩阵的转置。,设,A=,则,2,线性规划的对偶问题,28,如果我们用矩阵形式来表示，则有原问题：,其中,A,是 矩阵,m*n,，该问题有,m,个约束条件,n,个变量，,x= ,b= ,c=,对偶问题：,其中 是,A,的转置， 是,b,的转置,是,c,的转置, y=,现在我们用单纯形法求对偶问题的解。,2,线性规划的对偶问题,29,加上剩余变量 和人工变量 ，把此问题化成标准型如下：,把上述数据填入单纯形表计算。,2,线性规划的对偶问题,30,迭代变量,基变量,b,-300,-400,-250,0,0,-M,1,-M,1,0,-1,0,1,50,50/2,-250,1,1,1,0,-1,0,100,100/1,-M-250,-2M-250,-250,M,250,-M,-50M-25000,M-250,2M-150,0,-M,-250,0,2,-400,1/2,1,0,-1/2,0,1/2,25,-250,1/2,0,1,1/2,-1,-1/2,75,-325,-400,-250,75,250,-75,-28750,25,0,0,-75,-250,-M+75,3,-300,1,2,0,-1,0,1,50,-250,0,-1,1,1,-1,-1,50,-300,-350,-250,50,250,-50,-27500,0,-50,0,-50,-250,-M+50,2,线性规划的对偶问题,31,由上表，最优解：,=50,，,-f,的最大值为,-27500,，即目标函数,f,的最大值为,f=27500,元。,从上面可知租金：,A,设备为,50,元，,B,设备为,0,元，,C,设备为,50,元。这样把工,厂的所有设备出租可共得租金,27500,元。对出租者来说这租金是出租者愿意出,租设备的最小费用，因为这是目 标函数的最小值。,通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种,设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划,的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而,求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最,优值，因为这两个最优值相等。,2,线性规划的对偶问题,32,下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。,S.T.,2,线性规划的对偶问题,33,这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（,-1,），使不等号方向改变即可，得,这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有,显然，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的,两边都乘以（,-1,），得,2,线性规划的对偶问题,34,通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：,s.t.,2,线性规划的对偶问题,35,这个求最大值的线性规划问题的约束条件都取小于等于号，我们马,上可以写出其对偶问题：,s.t,.,2,线性规划的对偶问题,36,这里 和 一样都是不同的决策变量，为了表示这两个,决策变量都来源于原问题的第三个约束条件，记为 。,因为在该对偶问题中 和 的系数只相差一个符号，我们可以把,上面的对偶问题化为：,s.t.,2,线性规划的对偶问题,37,进一步，我们可以令 ，这时当 时， ，当,时， 。这也就是说，尽管 但 的取值可以为正，可以为,0,，,可以为负，即 没有非负限制。,这样我们把原规划的对偶问题化为,s.t.,没有限制。,对照原线性规划问题，我们可以知道：,当原线性规划问题的第,i,个约束条件取等号时，则其对偶问题的,i,个决策变量没有非,负限制。,如果当原线性规划问题中的第,i,个决策变量 没有非负限制时，我们也可以用,进行替换，这里 ， ，用类似的方法知道其对偶问题中第,i,个,约束条件取等号。,2,线性规划的对偶问题,38,另外，用大于等于,0,的两个决策变量之差来代替无非负限制的决策变,量也是求解含有无非负限制的决策变量的线性规划问题的一种方法。,原线性规划问题为：,s.t.,无非负限制。,2,线性规划的对偶问题,39,3,对偶规划的基本性质,对偶规划的基本性质,1,对称性,。即对偶问题的对偶是原问题。,2,弱对偶性,。即对于原问题（,）和对偶问题（,）的可行解 都有,C b,T,。,由弱对偶性，可得出以下推论：,（,1,）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。,（,2,）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。,（,3,）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,40,3,对偶规划的基本性质,3,最优性,。如果 是原问题,(),的可行解， 是对偶问题,(),的可行解，并且,C = b,T,，,则 和 分别为原问题,(),和对偶问题,(),的最优解。,4,强对偶性,。即若原问题,(),及其对偶问题,(),都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。,5,互补松弛性,。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即,若,y,i,*0,则有,若 ，则有,y,i,*=0,41,4,对偶单纯形法,对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原,有问题的所有检验数都小于,0,的情况下，通过迭代使得所有的约束都大于等于,0,，,最后求得最优解。,简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是,大多数线性规划问题很难找到初始解使得其所有检验数都小于,0,。但是在灵敏度,分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。 上节分析中已知当,250,b,1,325,时第一个约束条件的对偶价格不变，现在,b,1,=300,变成,b,1,=350,，请问这时第一个约束方程的对偶价格应为多少呢？,解：求出在第二次迭代表上的常数列,42,4,对偶单纯形法,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,b,50 100 0 0 0,2,X,1,50,1 0 1 0 -1,100,S,2,0,0 0 -2 1 1,-50,X,2,100,0 1 0 0 1,250,Z,J,50 100 0 50 50,C,J,-Z,J,0 0 -50 0 -50,1.,确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量,43,4,对偶单纯形法,4.,检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复,1-4,步。,迭代次数,基变量,C,B,X,1,X,2,S,1,S,2,S,3,b,50 100 0 0 0,2,X,1,50,1 0 1 1/2 -1/2,75,S,2,0,0 0 -2 -1/2 -1/2,25,X,2,100,0 1 0 0 1,250,Z,J,50 100 0 25 75,28750,C,J,-Z,J,0 0 0 -25 -75,