管理运筹学6单纯形法的灵敏度分析与对偶1

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