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

管 理 运 筹 学第六章 单纯形法的灵敏度分析与对偶 1 单纯形表的灵敏度分析 2 线性规划的对偶问题 3 对偶规划的基本性质 4 对偶单纯形法1管 理 运 筹 学1 单纯形表的灵敏度分析一、目标函数中变量 Ck系数灵敏度分析1.在最终的单纯形表里， X k是非基变量 由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与 Ck没有任何关系，所以当 Ck变成 Ck+ Ck时，在最终单纯形表中其系数的增广矩阵不变，又因为 Xk是非基变量，所以基变量的目标函数的系数不变，即 CB不变，可知 Zk也不变，只是 Ck变成了 Ck+ Ck。 这时 K= Ck-Zk就变成了 Ck+ Ck- Zk= K+ Ck。 要使原来的最优解仍为最优解，只要 K+ Ck 0即可，也就是 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 2管 理 运 筹 学1 单纯形表的灵敏度分析根据上式可知检验数 J (J=1,2,M) 变成了 J,有 J=CJ-ZJ= J+ CK aKj 。 要使最优解不变，只要当 J K时， J 0，就可求出的取值范围，也就是使得第 K个约束条件的对偶价格不变的bk的变化范围。，11管 理 运 筹 学1 单纯形表的灵敏度分析下面我们仍以第二章例 1在最终单纯形表上对 bj 进行灵敏度分析。最终单纯形表如下所示： 迭代次数 基 变 量 CB X1 X2 S1 S2 S3 b50 100 0 0 02 X1 50 1 0 1 0 -1 50S2 0 0 0 -2 1 1 50X2 100 0 1 0 0 1 250ZJ 50 100 50 0 50 27500CJ -ZJ 0 0 -50 0 -5012管 理 运 筹 学1 单纯形表的灵敏度分析我们对 b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在 250与 325之间变化，则设备台时数的对偶价格不变，都为每台设备台时 50元。13管 理 运 筹 学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在初始表上的系数列的 问题 ，14管 理 运 筹 学1 单纯形表的灵敏度分析接上页迭代次数 基 变 量 CB X1 X2 S1 S2 S3 X3 b50 100 0 0 0 150X1 50 1 0 1 0 -1 0.5 50S2 0 0 0 -2 1 1 -2 50X2 100 0 1 0 0 1 1.5 250ZJ 50 100 50 0 50 175 27500CJ -ZJ 0 0 -50 0 -50 -2515管 理 运 筹 学1 单纯形表的灵敏度分析例 假设上例题中产品 的工 艺结 构有了改 进 ， 这时 生 产 1件 产 品需要使用 1.5台 设备 ，消耗原料 A为 2千克，原料 B为 1千克，每件 产 品的利 润为 160元， 问该 厂的生 产计 划是否要修改 。解：首先求出 X3在最 终 表上的系数列迭代次数基 变 量 CB X1 X2 S1 S2 S3 X3 b50 100 0 0 0 1502 X1 50 1 0 1 0 -1 0.5 50 50/0.5S2 0 0 0 -2 1 1 0 50X2 100 0 1 0 0 1 1 250 250/1ZJ 50 100 50 0 50 125 27500CJ -ZJ 0 0 -50 0 -50 3516管 理 运 筹 学1 单纯形表的灵敏度分析接下来又可以有新的迭 代 S3进基，迭代次数基 变 量 CB X1 X2 S1 S2 S3 X3 b50 100 0 0 0 1503X3 160 2 0 2 0 -2 1 100 -S2 0 0 0 -2 1 1 0 50 50/1X2 100 -20 1 -2 0 3 0 150 250/3ZJ 120 100 120 0 -20 160 31000CJ -ZJ -70 0 -120 0 20 017管 理 运 筹 学1 单纯形表的灵敏度分析接上页可知此规模的最优解 X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此时，最大目标函数为 32000元。也就是说，该厂的新的生产计划为不生产 、产 品，生 产 产 品 200件 , 可 获 得最大利 润 32000元。迭代次数基 变 量 CB X1 X2 S1 S2 S3 X3 b50 100 0 0 0 1504 X3 160 2 0 2 0 -2 1 200 -S3 0 0 0 -2 1 1 0 50 50/1X2 100 -2 1 4 -3 0 0 0 250/3ZJ 120 100 80 20 0 160 32000CJ -ZJ -70 0 -80 -20 0 018管 理 运 筹 学1 单纯形表的灵敏度分析2.在初始表上的变量 XK的系数 PK改变为 PK，经过迭代后，在最终 表上 XK是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表而是直接计算。19管 理 运 筹 学1 单纯形表的灵敏度分析四、增加一个约束条件的灵敏度分析在原线性规划中增加一个约束条件时 ,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。下面仍以第三章例 1为例来加以说明。例：假如该工厂除了在设备台时，原材料 A、 B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为 5000度，而生产一个 产品需要用电 10度，而生产一个 产品需要用电 30度。试分析此时该厂获得最大利润的生产计划？20管 理 运 筹 学1 单纯形表的灵敏度分析解：先将原问题的最优解 =50， =250代入用电量的约束条件得： 10 50+30 250=500+75005000,所以原题的最优解不是本题的最优解。在用电量的约束条件中加入松驰变量 S4后得：把这个约束条件加入到原最终单纯形表上，其中 S4为基变量，得表如下：迭代次数基 变 量 b 比 值50 100 0 0 0 050 1 0 1 0 -1 0 500 0 0 -2 1 1 0 50100 0 1 0 0 1 0 2500 10 30 0 0 0 1 500050 100 50 0 50 0 275000 0 -50 0 -50 021管 理 运 筹 学1 单纯形表的灵敏度分析在上表中的 X1， X2不是单位向量，故进行行的线性变换，得迭代次数基 变 量 CB x1 x2 s1 s2 s3 s4 b 比值50 100 0 0 0 0x1 50 1 0 1 0 -1 0 50s2 0 0 0 -2 1 1 0 50x2 100 0 1 0 0 1 0 250s4 0 0 0 -10 0 -20 1 -3000zj 50 100 50 0 50 0 275000 0 -50 0 -50 0把上表中的 S4行的约束可以写为：上式两边乘以（ -1），再加上人工变量 a1得：用上式替换上表中的 S4行，得下表：22管 理 运 筹 学1 单纯形表的灵敏度分析迭代次数基 变量x1 x2 s1 s2 s3 s4 a1 b 比 值50 100 0 0 0 0 -Mx1 50 1 0 1 0 -1 0 0 50s2 0 0 0 -2 1 (1) 0 0 50x2 100 0 1 0 0 1 0 0 250s4 -M 0 0 -10 0 -20 1 1 3000zj 50 100 50-10M 0 50-20M 0 -M0 0 10M-50 0 20M-50 0 0 x1 50 1 0 -1 1 0 0 0 100 s3 0 0 0 -2 1 1 0 0 50 x2 100 0 1 2 -1 0 0 0 200 s4 -M 0 0 50 -20 0 -1 1 2000 zj 50 100 150-50M 20M-50 0 M -M 0 50M-150 50-20M 0 -M 0 x1 50 1 0 0 3/5 0 -1/50 1/50 140 s3 0 0 0 0 1/5 1 -2/50 2/50 130 x2 100 0 1 0 -1/5 0 2/50 -2/50 120 s4 0 0 0 1 -2/5 0 -1/50 1/50 40 zj 50 100 0 10 0 3 -3 0 0 -10 0 -3 -M+3 23管 理 运 筹 学1 单纯形表的灵敏度分析由上表可知，最优解为：即该工厂在添加了用电限量以后的最优生产计划为 产品生产 140件， 产品生产 120件。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管 理 运 筹 学迭代变 量基 变 量 b-300 -400 -250 0 0 -M1-M 1 0 -1 0 1 50 50/2-250 1 1 1