第6章单纯形法的灵敏度分析与课件.ppt

《第6章单纯形法的灵敏度分析与课件.ppt》由会员分享，可在线阅读，更多相关《第6章单纯形法的灵敏度分析与课件.ppt（62页珍藏版）》请在三一办公上搜索。

1、1,上节回顾,4.退化问题（求出基变量过程中存在两个以上的最小比值，这样在下一次迭代就有一个或多个基变量等于零，造成的后果是：最优值在经过了一次或几次迭代而没有改善，降低了单纯型算法的效率）5.针对退化问题，讲解了一个迭代循环的例子，引出了勃兰特法则：按照决策变量、松弛变量、人工变量顺序排序。不管是检验数相等，还是比值相等，都选下标最小的为入基变量或出基变量。时间问题，习题没有做。,2,第六章 单纯形法的灵敏度分析与对偶问题,1单纯形表的灵敏度分析2线性规划的对偶问题3对偶规划的基本性质4对偶单纯形法,3,单纯形表,4,1单纯形表的灵敏度分析,一、目标函数中变量系数Ck灵敏度分析（在什么范围内

2、变化，最优解不变，与第二章，第三章联系起来）在线性规划的求解过程中，目标函数系数的变动将会影响检验数的取值，但是，当目标函数的系数的变动不破坏最优判别准则时，原最优解不变，否则，原最优解将发生变化，要设法求出新的最优解。下面我们具体的分析 1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系，所以当Ck变成Ck+Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变成了Ck+Ck。这时 K=Ck-Zk就变成了Ck+Ck-Zk=K+Ck。要使原来的最

3、优解仍为最优解，只要 K+Ck0即可，也就是Ck的增量 Ck-K。,5,2.在最终的单纯形表中，X k是基变量 当Ck变成Ck+Ck时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数CB变了，则ZJ(J=1,2,.,N)一般也变了，不妨设CB=(CB1,CB2。,Ck,，CBm),当CB变成=(CB1,CB2。,Ck+Ck,CBm),则：ZJ=(CB1,CB2。,Ck,，CBm)(a1j,a2j,aKj,amj)ZJ=(CB1,CB2。,Ck+Ck,，CBm)(a1j,a2j,aKj,amj)=ZJ+Ck aKj,6,1单纯形表的灵敏度分析,根据上式可知 检验数 J(J=1,

4、2,.,M)变成了 J,只要当J K时，有 J=CJ-ZJ=J-CK aKj。要使最优解不变，J=0,7,1单纯形表的灵敏度分析,例：目标函数：Max z=50X1+100X2 约束条件：X1+X2300 2X1+X2400 X2250 X1，X20最优单纯形表如下,8,1单纯形表的灵敏度分析,对非基变量目标函数系数：C3 我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。这里3=-50，所以当c3的增量c3-（-50），最优解不变。对基变量目标函数系数：c1 再对基变量x1的目标函数的系数c1进行灵敏度分析。在a11,a12,a13,a14,a15中，除了知道a11和 a13大于0，a

5、15小于0，可知，有 同样有。这样可以知道当-50c150时，也就是x1的目标函数c1在0c1100时最优解不变。,9,1单纯形表的灵敏度分析,从30，得到-c10,即c10，并且从50，得到c1100。那么如果c1取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。,另外一种求最优解不变的C1变化范围方法在最终的单纯形表中，用C1代替原来的C1=50,计算得表,10,常数项灵敏度分析之前的一点补充知识：,11,补充知识,12,补充知识,13,补充知识,14,补充知识,15,补充知识,16,1单纯形表的灵敏度分析,二、约束方程中常数项的灵敏度分析（使对偶价格不变的b的

6、变化范围）回想一下：第2章例一各个约束的对偶价格：从上表我们可以发现各个松弛变量的Zj值，正好等于相应变量的对偶价格。,17,1单纯形表的灵敏度分析,单纯形表中的Zj跟对偶价格的关系：对于含有小于等于号的约束条件，添加松弛变量转化为标准型。这时这个约束条件的对偶价格就和松弛变量的Zj有关。对偶价格应取松弛变量的Zj的值。对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时 这个约束条件的对偶价格就和这个剩余变量的 有关了。这时约束条件的对偶价格应取 值的相反数-。对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方 程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变

7、量的 值。,18,最终单纯形表对于不同约束类型的对偶价格的取值。常数项的灵敏度分析-使对偶价格不变的bj灵敏度分析-知道对偶价格Zj等于Cb*Pj的转置。我们知道单纯型法是增广矩阵的行的初等变换，bj的变化并不影响系数矩阵的变化。所以Pj是不变的。所以要使对偶价格不变，只要使Cb不变就可以，就是最终单纯形表中的最优基不变，即最终单纯型表中的基变量还是基变量，怎么保证基变量还是基变量？（即最优基不变，所得到的基本解是可行解，也就是基变量的值仍然大于等于零）所以原问题转化为：使最优解的所有基变量不变，且所得的最优解仍然是可行的Bj的变化范围。,1单纯形表的灵敏度分析,19,1单纯形表的灵敏度分析,

8、当bj中的第k项bK 变成 时，也就是原来的初始单纯形表中的b向量变成了b向量,20,1单纯形表的灵敏度分析,这样在最终单纯形表中基变量XB的解就变成了 如要使XB成为可行解，只要使上述等式的右边0，就可求出 的取值范围，也就是使得第K个约束条件的对偶价格不变的bk的变化范围。，,21,1单纯形表的灵敏度分析,（k的取值固定的值，i的取值是1到m）下面我们仍以第二章例1在最终单纯形表上对b1进行灵敏度分析。最终单纯形表如下所示：,22,1单纯形表的灵敏度分析,我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,实际意义可以描述为：设备台时数在250与325之间变化，则设备台时数的

9、对偶价格不变，都为每台设备台时50元。,23,1单纯形表的灵敏度分析,三、约束方程系数矩阵A灵敏度分析（约束条件改变，对最优解的影响，比如有新产品要生产、生产工艺改进等）下面分两种情况讨论 1.在最终单纯形表上Xk是非基变量：在初始单纯形表上的变量Xk的系数列Pk改变为Pk经过迭代后，在最终单纯形表上Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变换，Pk变成Pk仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以及 k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj,而Zk就变成CBB-1Pk，新的检验数 k=Ck-CBB-1Pk。若 k0，则原最优解仍然为最优解。若

10、k 0，则继续进行迭代以求出最优。例 以第二章例1为基础，设该厂除了生产，种产品外，现在试制成一个新产品，已知生产产品,每件需要设备2台时，并消耗A原料0.5公斤。B原料1.5公斤，获利150元，问该厂应该生产该产品多少？解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量X3在初始表上的系数列的问题，,24,1单纯形表的灵敏度分析,25,1单纯形表的灵敏度分析,例 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要使用1.5台设备，消耗原料A为2千克，原料B为1千克，每件产品的利润为160元，问该厂的生产计划是否要修改。解：首先求出X3在最终表上的系数列,26,1单纯形表的灵敏

11、度分析,接下来又可以有新的迭代S3进基，,27,1单纯形表的灵敏度分析,接上页 可知此规划的最优解X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、产品，生产产品200件,可获得最大利润32000元。,28,1单纯形表的灵敏度分析,2.最终表上XK是基变量：在初始表上的变量XK的系数PK改变为PK，经过迭代后，在最终表上XK是基变量，（比如X1，X2，制作产品1，产品2的工艺有改善，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂）一般不去修改最终单纯形表，而是重新用单纯形法计算。,29,1单

12、纯形表的灵敏度分析,四、增加一个约束条件的灵敏度分析（增加一个约束条件对最优解的影响）在原线性规划中增加一个约束条件时,（1）先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，停止计算。（2）否则将新增的约束添入原最终单纯形表上，进一步求解。下面仍以第三章例1为例来加以说明。例：假如该工厂除了在设备台时，原材料A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个产品需要用电10度，而生产一个产品需要用电30度。试分析此时该厂获得最大利润的生产计划？,30,1单纯形表的灵敏度分析,解：先将原问题的最优解,=5

13、0，,=250代入用电量的约束条件,得：1050+30250=500+75005000,所以原题的最优解不是本题的最优解。在用电量的约束条件中加入松驰变量S4后得：,把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：,31,1单纯形表的灵敏度分析,在上表中的X1，X2不是单位向量，故进行行的线性变换，得,把上表中的S4行的约束可以写为：,上式两边乘以（-1），再加上人工变量a1得：,用上式替换上表中的S4行，得下表：,32,1单纯形表的灵敏度分析,33,1单纯形表的灵敏度分析,由上表可知，最优解为：,即该工厂在添加了用电限量以后的最优生产计划为产品生产140件，产品生产120件

14、。,34,上节回顾,单纯形法的灵敏度分析1.目标函数系数Cj的灵敏度2.常数项bj的灵敏度分析3.系数矩阵A的灵敏度分析 在初始表上的变量XK的系数PK改变为PK，经过迭代后，在最终表上XK是基变量，（比如X1，X2，制作产品1，产品2的工艺有改善，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂）一般不去修改最终单纯形表，而是重新用单纯形法计算。4.增加一个约束条件的灵敏度分析（1）先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，停止计算。（2）否则将新增的约束添入原最终单纯形表上，进一步求解。,35,对偶单纯形法：对偶单纯

15、形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于0的情况下，通过迭代使得所有的约束都大于等于0，最后求得最优解。优点：简化计算是对偶单纯形法的优点 例子：缺点：但是它在使用上有很大的局限，这主要是 大多数线性规划问题很难找到初始解使得其所有检验数都小于0。适用目标函数的特点：A.max f=-M1*X1-M2*X2.的形式 B.用在灵敏度分析中（增加约束条件的）。,上节回顾,36,1.对偶问题的定义2.原问题与对偶问题的关系3.如何根据原问题的结果去找对偶问题的答案4.如何将原问题转化成对偶问题5.对偶规划的基本性质,2 线性规划的对偶问题,37,任何一个求极

16、大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题。例题1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示 该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？解：设 为产品 的计划产量，为产品的计划产量，则有目标函数：Max z=50X1+100 x2约束条件：，,2 线性规划的对偶问题,38,现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那

17、么该厂的厂长应该如何来确定合理的租金呢？设 分别为设备A、B、C的每台时的租金。租金定价的原则是：出租者：生产一个单位的 产品需消耗1个单位的设备A、2个单位的设备B、0个单位的设备C，获利50个单位；那么，将这些资源（设备台时）全部转让时所获得的利润 应不少于50个单位，否则就不出租还是用于生产 产品以获利50元；同样把生产一个单位 产品所需各设备的台时的总租金也不应当低于原利润100元，即，否则这些设备台时就不出租，还是用于生产 产品以获利100元。,2 线性规划的对偶问题,39,对于租用者，他要求在满足上述要求的前提下，也就是在出租者愿意出租的前提下尽量要求全部设备台时的总租金越低越好，

18、即min，这样我们得到了该问题的数学模型：目标函数：约束条件：这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题，而另外一个叫对偶问题。,40,如果我们把求目标函数最大值的线性规划问题看成原问题，则求目标函数最小值的线性规划问题看成对偶问题。下面来研究这两个问题在数学模型上的关系。1 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。2 原问题的目标函数中的变量系数为对偶问题中的

19、约束条件的右边常数项，并且原问题的目标函数中的第i个变量的系数就等于对偶问题中的第i个约束条件的右边常数项。3 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。并且原问题的第i个约束条件的右边常数项就等于零对偶问题的目标函数中的第i个变量的系数。,2 线性规划的对偶问题,41,4 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。设 A=则,42,如果我们用矩阵形式来表示，则有原问题：其中A是 矩阵m*n，该问题有m个约束条件n个变量，x=,b=,c=对偶问题：其中 是A的转置，是b的转置,是c的转置,y=现在我们用单纯形法求对偶问题的解。,2 线性规划的对偶问题,43,加

20、上剩余变量 和人工变量，把此问题化成标准型如下：把上述数据填入单纯形表计算。,2 线性规划的对偶问题,44,2 线性规划的对偶问题,45,由上表，最优解：=50，-f 的最大值为-27500，即目标函数f的最大值为f=27500元。从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目 标函数的最小值。通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格。对于两个有对偶关系的线性规划的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而求得其

21、对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值，因为这两个最优值相等。,2 线性规划的对偶问题,46,下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。S.T.,2 线性规划的对偶问题,47,这是一个求最大值的线性规划问题，为了写出它的对偶问题，我们不妨把它的约束条件都变换成取小于号的不等式。显然第一个约束条件已符合要求，不要做任何变动，而第二个约束条件，我们只要两边都乘以（-1），使不等号方向改变即可，得 这样第二个约束条件也就符合要求。对于第三个约束条件，我们可以用小于等于和大于等于两个约束条件来替代它。即有 显然

22、，这两个约束条件与原来第三个约束条件是等价的，我们再把其中的两边都乘以（-1），得,2 线性规划的对偶问题,48,通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：s.t.,2 线性规划的对偶问题,49,这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题：s.t.,2 线性规划的对偶问题,50,这里 和 一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为。因为在该对偶问题中 和 的系数只相差一个符号，我们可以把上面的对偶问题化为：s.t.,2 线性规划的对偶问题,51,进一步，我们可以令，这时当 时，当 时，。这也就是

23、说，尽管 但 的取值可以为正，可以为0，可以为负，即 没有非负限制。这样我们把原规划的对偶问题化为 s.t.没有限制。对照原线性规划问题，我们可以知道：当原线性规划问题的第i个约束条件取等号时，则其对偶问题的 i个决策变量没有非负限制。如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用 进行替换，这里，用类似的方法知道其对偶问题中第 i个约束条件取等号。,2 线性规划的对偶问题,52,原线性规划问题为：s.t.无非负限制。,2 线性规划的对偶问题,53,上节回顾,1.对偶问题的定义 任何一个求极大化的线性规划问题都有一个求极小化的线性规划问题与之对应，反之亦然，如果我们把其

24、中一个叫原问题，则另一个就叫做它的对偶问题，并称这一对互相联系的两个问题为一对对偶问题。2.原问题与对偶问题的关系a 求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。b 原问题的目标函数中的变量系数为对偶问题中的约束条件的右边常数项。c 原问题的约束条件的右边常数项为对偶问题的目标函数中的变量的系数。d 对偶问题的约束条件的系数矩阵A是原问题约束矩阵的转置。,54,3.如何根据原问题的结果去找对偶问题的答案 对于两个有对偶关系的线性规划的问题，我们只要

25、求得了其中一个最优解，就可以从这个问题的对偶价格而求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最优值4.如何将原问题转化成对偶问题 当原线性规划问题的第i个约束条件取等号时，则其对偶问题的 i个决策变量没有非负限制。如果当原线性规划问题中的第 i个决策变量没有非负限制时，其对偶问题中第 i个约束条件取等号。5.对偶规划的基本性质,55,3对偶规划的基本性质,对偶规划的基本性质1对称性。即对偶问题的对偶是原问题。2弱对偶性。即对于原问题（）和对偶问题（）的可行解 都有C bT。由弱对偶性，可得出以下推论：（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶

26、问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。,56,3对偶规划的基本性质,3最优性。如果 是原问题()的可行解，是对偶问题()的可行解，并且 C=bT，则 和 分别为原问题()和对偶问题()的最优解。4强对偶性。即若原问题()

27、及其对偶问题()都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。5互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即 若yi*0,则有 若，则有yi*=0,57,例子,已知LP问题 max z=x1+2x2+3x3+4x4 S.t.x1+2x2+2x3+3x4=0其对偶问题的最优解为：y1=1.2 y2=0.2 最优值为28.试用互补松弛性定理确定LP问题的最优解。,58,4对偶单纯形法,对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检

28、验数都小于0的情况下，通过迭代使得所有的约束都大于等于0，最后求得最优解。简化计算是对偶单纯形法的优点，但是它在使用上有很大的局限，这主要是大多数线性规划问题很难找到初始解使得其所有检验数都小于0。但是在灵敏度分析中，有时需要对偶单纯形法，这样可以简化处理。下面以第二节例一为例。上节分析中已知当250b1325时第一个约束条件的对偶价格不变，现在b1=300变成b1=350，请问这时第一个约束方程的对偶价格应为多少呢？解：求出在第二次迭代表上的常数列,59,4对偶单纯形法,1.确定出基变量，在常数列中找一个最小的负常量，把这个常量所在行作为出基变量,60,精品课件！,61,精品课件！,62,4对偶单纯形法,4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复1-4步。,