《第6章单纯形法的灵敏度分析与对偶61074》由会员分享，可在线阅读，更多相关《第6章单纯形法的灵敏度分析与对偶61074（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。要使原来的最优解 仍为最优解，只
2、要 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,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
4、 单纯形表的灵敏度分析,19,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.在初始单纯形表上的变
5、量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元，问该厂应该生产该产品多少？ 解：这是一个增加新变
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元。也就是说，该厂的新
7、的生产计划为不生产、产品，生产产品200件, 可获得最大利润32000元。,27,1 单纯形表的灵敏度分析,2.在初始表上的变量XK的系数PK改变为PK，经 过迭代后，在最终表上XK是基变量，在这种情况下 原最优解的可行性和最优解都可能被破坏，问题十分 复杂，一般不去修改原表而是直接计算。,28,1 单纯形表的灵敏度分析,四、增加一个约束条件的灵敏度分析,在原线性规划中增加一个约束条件时,先将原问题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进一步求解。下面仍以第三章例1为例来加以说明。例：假如该工厂除了在设备
8、台时，原材料A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个产品需要用电10度，而生产一个产品需要用电30度。试分析此时该厂获得最大利润的生产计划？,29,1 单纯形表的灵敏度分析,解：先将原问题的最优解,=50，,=250代入用电量的约束条件,得：1050+30250=500+75005000,所以原题的最优解不是本题的最优解。 在用电量的约束条件中加入松驰变量S4后得：,把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：,30,1 单纯形表的灵敏度分析,在上表中的X1，X2不是单位向量，故进行行的线性变换，得,把上表中的S4行的约束可
9、以写为：,上式两边乘以（-1），再加上人工变量a1得：,用上式替换上表中的S4行，得下表：,31,1 单纯形表的灵敏度分析,32,1 单纯形表的灵敏度分析,由上表可知，最优解为：,即该工厂在添加了用电限量以后的最优生产计划为产品生产140件，产品生产120件。,33,1 单纯形表的灵敏度分析,【例】考虑下列线性规划,求出最优解后，分别对下列各种变化进行灵敏度分析，求出变化后的最优解。,（1）改变右端常数为:,综合分析,34,1 单纯形表的灵敏度分析,（2）改变目标函数x3的系数为c3=1;,（3）改变目标函数中x2的系数为c2=2；,（4）改变x2的系数为,（5）改变约束（1）为,（6）增加新
10、约束,（7）增加新约束,35,1 单纯形表的灵敏度分析,【解】加入松弛变量x4、x5、x6，用单纯形法计算，最优下表所示。,最优解X=（1，0，2，0，0，1）T ，最优值Z=10,36,1 单纯形表的灵敏度分析,上述cj及bi的最大允许变化范围是假定其它参数不变的前提下，单个参数的变化范围，当几个参数同时在各自范围内变化时，最优解或最优基有可能改变。,37,每一个线性规划问题，都存在每一个与它密切相关的线性规划的问题，我们称其为原问题，另一个为对偶问题。 例题1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示该工厂每生产一单位产品 可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少 产品和产品，才能使工厂获利最多？ 解：设 为产品 的计划产量， 为产品的计划产量，则有 目标函数： Max z=50 +100 约束条件： ，,
