管理运筹：第6章单纯形法的灵敏度分析与对偶.ppt

管 理 运 筹 学 管理运筹学 教学课件 06 工商管理学院 李时椿 1 管 理 运 筹 学 第六章 单纯形法的灵敏度分析与对偶 单纯形表的灵敏度分析 线性规划的对偶问题 对偶单纯形法 本章重点 2 管 理 运 筹 学 第六章 单纯形法的灵敏度分析与对偶 1 单纯形表的灵敏度分析 2 线性规划的对偶问题 3 对偶规划的基本性质 4 对偶单纯形法 3 管 理 运 筹 学 1 单纯形表的灵敏度分析 一、目标函数中变量Ck系数灵敏度分析 1.在最终的单纯形表里，X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与Ck没有任何关系， 所以当Ck变成Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非 基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，只是Ck变 成了Ck+ Ck。这时 K= Ck-Zk就变成了Ck+ Ck- Zk= K+ Ck。要使原来的最优解 仍为最优解，只要 K+ Ck0即可，也就是Ck的增量 Ck- K。 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 4 管 理 运 筹 学 1 单纯形表的灵敏度分析 根据上式可知 检验数 J (J=1,2,M)变成了 J,有 J=CJ-ZJ= J+ CK aKj 。要使最优解不变，只要当J K时， J 0，就可求出 的取值范围，也就是使得第K个约束条件的对偶价格不变的 bk的变化范围。 ， 13 管 理 运 筹 学 1 单纯形表的灵敏度分析 下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。 最终单纯形表如下所示：迭代次数基变量CBX1 X2 S1 S2 S3b 50 100 0 0 0 2 X1501 0 1 0 -150 S200 0 -2 1 150 X21000 1 0 0 1250 ZJ 50 100 50 0 5027500 CJ -ZJ0 0 -50 0 -50 14 管 理 运 筹 学 1 单纯形表的灵敏度分析 我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量 S1, 实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台 时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备 台时50元。 15 管 理 运 筹 学 1 单纯形表的灵敏度分析 三、约束方程系数矩阵A灵敏度分析 下面分两种情况讨论 1.在初始单纯形表上的变量Xk的系数列Pk改变为Pk经过迭代后，在最终单 纯形表上Xk是非基变量。由于单纯形表的迭代是约束方程的增广矩阵的行变 换，Pk变成Pk仅仅影响最终单纯形表上第k列数据，包括Xk的系数列、Zk以 及 k，这时最终单纯形表上的Xk的系数列就变成了B-1Pj,而Zk就变成CBB-1Pk ，新的检验数 k=Ck-CBB-1Pk。若 k0，则原最优解仍然为最优解。若 k 0 ，则继续进行迭代以求出最优。 例 以第二章例1为基础，设该厂除了生产，种产品外，现在试制成一个新产 品，已知生产产品,每件需要设备 2台时，并消耗A原料0.5公斤。B原料 1.5公斤，获利150元，问该 厂应该 生产该产 品多少？ 解：这是一个增加新变量的问题 。我们可以把它认为 是一个改变变 量X3在初 始表上的系数列的问题 ， 16 管 理 运 筹 学 1 单纯形表的灵敏度分析 接上页 迭代次数基变量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 X1501 0 1 0 -1 0.550 S200 0 -2 1 1 -250 X21000 1 0 0 1 1.5250 ZJ50 100 50 0 50 17527500 CJ -ZJ0 0 -50 0 -50 -25 17 管 理 运 筹 学 1 单纯形表的灵敏度分析 例 假设上例题中产品的工艺结 构有了改进，这时 生产1件产品需要 使用1.5台设备 ，消耗原料A为2千克，原料B为1千克，每件产品的 利润为 160元，问该 厂的生产计 划是否要修改。 解：首先求出X3在最终表上的系数列 迭代 次数 基变量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 2 X1501 0 1 0 -1 0.55050/0.5 S200 0 -2 1 1 050 X21000 1 0 0 1 1250250/1 ZJ50 100 50 0 50 12527500 CJ -ZJ0 0 -50 0 -50 35 18 管 理 运 筹 学 1 单纯形表的灵敏度分析 接下来又可以有新的迭代S3进基， 迭代 次数 基变量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 3 X31602 0 2 0 -2 1100- S200 0 -2 1 1 05050/1 X2100-20 1 -2 0 3 0150250/3 ZJ120 100 120 0 -20 16031000 CJ -ZJ-70 0 -120 0 20 0 19 管 理 运 筹 学 1 单纯形表的灵敏度分析 接上页 可知此规模的最优解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此时， 最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、 产品，生产产品200件, 可获得最大利润32000元。 迭代 次数 基变量CBX1 X2 S1 S2 S3 X3 b 50 100 0 0 0 150 4 X31602 0 2 0 -2 1200- S300 0 -2 1 1 05050/1 X2100-2 1 4 -3 0 00250/3 ZJ120 100 80 20 0 16032000 CJ -ZJ-70 0 -80 -20 0 0 20 管 理 运 筹 学 1 单纯形表的灵敏度分析 2.在初始表上的变量XK的系数PK改变为PK，经 过迭代后，在最终表上XK是基变量，在这种情况下 原最优解的可行性和最优解都可能被破坏，问题十分 复杂，一般不去修改原表而是直接计算。 21 管 理 运 筹 学 1 单纯形表的灵敏度分析 四、增加一个约束条件的灵敏度分析 在原线性规划中增加一个约束条件时,先将原问 题的最优解的变量值代入新增的约束条件，如满足 则说明新增的条件没有起到限制作用，故原最优解 不变，否则将新增的约束添入原最终单纯形表上进 一步求解。 下面仍以第三章例1为例来加以说明。 例：假如该工厂除了在设备台时，原材料A、B 上对该厂的生产有限制外，还有电力供应上的限制 。最高供应电量为5000度，而生产一个产品需要 用电10度，而生产一个产品需要用电30度。试分 析此时该厂获得最大利润的生产计划？ 22 管 理 运 筹 学 1 单纯形表的灵敏度分析 解：先将原问题的最优解=50，=250代入用电量的约束条件 得：1050+30250=500+75005000,所以原题的最优解不是本题的最优解。 在用电量的约束条件中加入松驰变量S4后得： 把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下： 迭代 次数 基变变量b比值值 501000000 501010-1050 000-211050 100010010250 0103000015000 501005005002750 0 00-500-500 23 管 理 运 筹 学 1 单纯形表的灵敏度分析 在上表中的X1，X2不是单位向量，故进行行的线性变换，得 迭代 次数 基变变量CBx1x2s1s2s3s4b比 值值 501000000 x1501010-1050 s2000-211050 x2100010010250 s4000-100-201-3000 zj5010050050027500 00-500-500 把上表中的S4行的约束可以写为： 上式两边乘以（-1），再加上人工变量a1得： 用上式替换上表中的S4行，得下表： 24 管 理 运 筹 学 1 单纯形表的灵敏度分析 迭代 次数 基变变 量 x1x2s1s2s3s4a1b比值值 501000000-M x1501010-10050 s2000-21(1)0050 x21000100100250 s4-M00-100-20113000 zj5010050-10M050-20M0-M 0010M-50020M-5000 x15010-11000100 s3000-2110050 x2100012-1000200 s4-M0050-200-112000 zj50100150-50M20M-500M-M 050M-15050-20M0-M0 x1501003/50-1/501/50140 s300001/51-2/502/50130 x2100010-1/502/50-2/50120 s40001-2/50-1/501/5040 zj5010001003-3 00-100-3-M+3 25 管 理 运 筹 学 1 单纯形表的灵敏度分析 由上表可知，最优解为： 即该工厂在添加了用电限量以后的最优生产计划为 产品生产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是 矩阵m*n，该问题有m个约束条件n个变量，x= ,b= , c= 对偶问题： 其中 是A的转置， 是b的转置, 是c的转置, y= 现在我们用单纯形法求对偶问题的解。 2 线性规划的对偶问题 30 管 理 运 筹 学 加上剩余变量 和人工变量 ，把此问题化成标准型如下： 把上述数据填入单纯形表计算。 2 线性规划的对偶问题 31 管 理 运 筹 学 迭代 变量 基变量 b -300-400-25000-M 1 -M1 0 -1 0 15050/2 -250 1 1 1 0 -1 0 100100/1 -M-250-2M- 250 -250M250-M-50M-25000 M-250 2M- 150 0-M-2500 2 -4001/210-1/201/225 -2501/2011/2-1-1/275 -325-400-25075250-75-28750 2500-75-250-M+75 3 -300120-10150 -2500-111-1-150 -300-350-25050250-50-27500 0-500-50-250-M+50 2 线性规划的对偶问题 32 管 理 运 筹 学 由上表，最优解： =50， -f 的最大值为-27500，即目标函数f的最大值为f=27500元。 从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工 厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出 租设备的最小费用，因为这是目 标函数的最小值。 通过比较，我们发现：对偶问题的最优解即最佳租金恰好等于原问题各种 设备的对偶价格，这在道理上也能讲得通。 对于两个有对偶关系的线性规划 的问题，我们只要求得了其中一个最优解，就可以从这个问题的对偶价格而 求得其对偶问题的最优解，知道其中一个最优值也就找到了其对偶问题的最 优值，因为这两个最优值相等。 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 管 理 运 筹 学 3 对偶规划的基本性质 对偶规划的基本性质 1对称性。即对偶问题的对偶是原问题。 2弱对偶性。即对于原问题（）和对偶问题（）的可 行解 都有C bT 。 由弱对偶性，可得出以下推论： （1）原问题任一可行解的目标函数值是其对偶问题目标函数值的 下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数 值的上界。 （2）如原问题有可行解且目标函数值无界（或具有无界解），则 其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界， 则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无 可行解时，其原问题或具有无界解或无可行解，反之亦然）。 （3）若原问题有可行解而其对偶问题无可行解，则原问题目标函 数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问 题的目标函数值无界。 41 管 理 运 筹 学 3 对偶规划的基本性质 3最优性。如果 是原问题()的可行解， 是对偶问 题()的可行解，并且 C = bT ，则 和 分别为 原问题()和对偶问题()的最优解。 4强对偶性。即若原问题()及其对偶问题()都有 可行解，则两者都有最优解；且它