《第6章单纯形法的灵敏度分析与对偶》由会员分享，可在线阅读，更多相关《第6章单纯形法的灵敏度分析与对偶（67页珍藏版）》请在金锄头文库上搜索。
1、1,第六章 单纯形法的灵敏度分析与对偶,1单纯形表的灵敏度分析2线性规划的对偶问题3对偶规划的基本性质4对偶单纯形法,2,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即可，也就
2、是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,3,1单纯形表的灵敏度分析,根据上式可知 检验数
3、 J (J=1,2,.,M)变成了 J,有 J=CJ-ZJ= J- CK aKj 。要使最优解不变，只要当J K时， J 0，就可求出 的取值范围，也就是使得第K个约束条件的对偶价格不变的bk的变化范围。 ，,16,1单纯形表的灵敏度分析,下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。最终单纯形表如下所示：,17,1单纯形表的灵敏度分析,我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1, 实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备台时50元。,18,1单纯形表的灵敏度分析,1
4、9,1单纯形表的灵敏度分析,【解】由表29知，最优基B、B1及分别为,对于b1：比值的分母取B1的第一列，这里只有11=1，而21=31=0，则,b1无上界，即b15，因而b1在35,+) 内变化时对偶价格不变。,20,1单纯形表的灵敏度分析,对于b2：比值的分母取B1的第二列，120，220，则,即b2在15，25上变化时最优基不变,21,1单纯形表的灵敏度分析,对于b3：比值的分母取B1的第三列，有,故有15b35，b3在0，20上变化时最优基不变。,22,1单纯形表的灵敏度分析,三、约束方程系数矩阵A灵敏度分析下面分两种情况讨论 1.在初始单纯形表上的变量Xk的系数列Pk改变为Pk经过迭
5、代后，在最终单纯形表上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元，问该厂应该生产该产品多少？解：这是一个增加新变量的问题。我们可以把它认为是一个改变
6、变量X3在初始表上的系数列的问题，,23,1单纯形表的灵敏度分析,接上页,24,1单纯形表的灵敏度分析,例 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要使用1.5台设备 ，消耗原料A为2千克，原料B为1千克，每件产品的利润为160元，问该厂的生产计划是否要修改。 解：首先求出X3在最终表上的系数列,25,1单纯形表的灵敏度分析,接下来又可以有新的迭代S3进基，,26,1单纯形表的灵敏度分析,接上页 可知此规模的最优解X1=0, X2=0, S1=0, S2=0, S3=50, X3=200,此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、产品，生产产品200
7、件, 可获得最大利润32000元。,27,1单纯形表的灵敏度分析,2.在初始表上的变量XK的系数PK改变为PK，经过迭代后，在最终表上XK是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表而是直接计算。,28,1单纯形表的灵敏度分析,四、增加一个约束条件的灵敏度分析,在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。 下面仍以第三章例1为例来加以说明。 例：假如该工厂除了在设备台时，原材料A、B上对该厂的生产有限制外，还有
8、电力供应上的限制。最高供应电量为5000度，而生产一个产品需要用电10度，而生产一个产品需要用电30度。试分析此时该厂获得最大利润的生产计划？,29,1单纯形表的灵敏度分析,解：先将原问题的最优解,=50，,=250代入用电量的约束条件,得：1050+30250=500+75005000,所以原题的最优解不是本题的最优解。在用电量的约束条件中加入松驰变量S4后得：,把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：,30,1单纯形表的灵敏度分析,在上表中的X1，X2不是单位向量，故进行行的线性变换，得,把上表中的S4行的约束可以写为：,上式两边乘以（-1），再加上人工变量a1得：,用上式替换上表中的S4行，得下表：,31,1单纯形表的灵敏度分析,32,1单纯形表的灵敏度分析,由上表可知，最优解为：,即该工厂在添加了用电限量以后的最优生产计划为产品生产140件，产品生产120件。,33,1单纯形表的灵敏度分析,【例】考虑下列线性规划,求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。,（1）改变右端常数为:,综合分析,34,1单纯形表的灵敏度分析,（2）改变目标函数x3的系数为c3=1;,
