纯形法的灵敏度分析与对偶.ppt

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