第6--单纯形法的灵敏度分析与对偶.pptx

管管 理理 运运 筹筹 学学1单纯形法的矩阵描述 max Z=CX max Z=CBXB+CNXNs.t.AX=b s.t.BXB+NXN=b X0 XB,XN 0 则则XB=B-1(b-NXN)=B-1b-B-1NXN代入代入Z=CBXB+CNXN =CB(B-1b-B-1NXN)+CNXN =CBB-1b+(CN-CBB-1N)XN令令XN=0，则，则 XB=B-1b Z=CBB-1b若若B-1b 0，则，则 X=(B-1b,0)是一个基本可行解。是一个基本可行解。管管 理理 运运 筹筹 学学2单纯形法的矩阵描述EXEX：已知线形规划问题：已知线形规划问题：Max Z=5x1+2x2+3x3 s.t.x1+5x2+2x3 b1 x1-5x2-6x3 b2 x1,x2,x3 0 对于给定的非负常数对于给定的非负常数b1，b2，其最优单纯形表如下，其最优单纯形表如下，请完成该表，并求出请完成该表，并求出b1，b2。cjbxB cB x1 x2 x3 x4 x5 x1 x5 1 -13010zjcj-zj 管管 理理 运运 筹筹 学学311单纯形表的灵敏度分析单纯形表的灵敏度分析一、目标函数中变量一、目标函数中变量C Ck k系数灵敏度分析系数灵敏度分析1.在最终的单纯形表里，在最终的单纯形表里，X k是非基变量是非基变量 Ck Ck+Ck，CB不变，Zk也不变，这时 K=Ck+Ck-Zk=K+Ck。要使原来的最优解仍为最优解，只要 K+Ck0即可，也就是Ck的增量 Ck-K2.在最终的单纯形表中，在最终的单纯形表中，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 管管 理理 运运 筹筹 学学411单纯形表的灵敏度分析单纯形表的灵敏度分析根据上式可知 检验数 j(j=1,2,.,m)变成了 j,有 j=Cj-Zj=j -CK aKj。要使最优解不变，只要当j k时，j 0，就可求出 的取值范围，也就是使得第K个约束条件的对偶价格不变的bk的变化范围。，管管 理理 运运 筹筹 学学1311单纯形表的灵敏度分析单纯形表的灵敏度分析下面我们仍以第二章例1在最终单纯形表上对bj 进行灵敏度分析。最终单纯形表如下所示：迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 0 -150 S200 0 -2 1 150 X21000 1 0 0 1250 ZJ50 100 50 0 5027500CJ-ZJ0 0 -50 0 -50管管 理理 运运 筹筹 学学1411单纯形表的灵敏度分析单纯形表的灵敏度分析 我们对b1进行灵敏度分析，因为在第一个约束方程中含有松弛变量S1,实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备台时50元。管管 理理 运运 筹筹 学学1511单纯形表的灵敏度分析单纯形表的灵敏度分析三、约束方程系数矩阵三、约束方程系数矩阵A A灵敏度分析灵敏度分析 1.在初始单纯形表上的变量在初始单纯形表上的变量Xk的系数列的系数列Pk改变为改变为Pk，经过迭代后，在最终单经过迭代后，在最终单纯形表上纯形表上Xk是非基变量。是非基变量。最终单纯形表上的Xk的系数列就变成了B-1Pj,而Zk就变成CBB-1Pk，新的检验数 k=Ck-CBB-1Pk。若 k0，则原最优解仍然为最优解。若 k 0，则继续进行迭代以求出最优。例例 以第二章例以第二章例1 1为基础，设该厂除了生产为基础，设该厂除了生产，种产品外，现在试种产品外，现在试制成一个新产品制成一个新产品，已知生产，已知生产产品产品,每件需要设备每件需要设备2 2台时，并消耗台时，并消耗A A原料原料0.50.5公斤。公斤。B B原料原料1.51.5公斤，获利公斤，获利150150元，问该厂应该生产该产元，问该厂应该生产该产品多少？品多少？管管 理理 运运 筹筹 学学1611单纯形表的灵敏度分析单纯形表的灵敏度分析迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 150X1501 0 1 0 -1 0.550 S200 0 -2 1 1 -250 X21000 1 0 0 1 1.5250 ZJ50 100 50 0 50 17527500CJ-ZJ0 0 -50 0 -50 -25管管 理理 运运 筹筹 学学1711单纯形表的灵敏度分析单纯形表的灵敏度分析例 假设上例题中产品的工艺结构有了改进，这时生产1件产品需要使用1.5台设备，消耗原料A为2千克，原料B为1千克，每件产品的利润为160元，问该厂的生产计划是否要修改。解：首先求出X3在最终表上的系数列 迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1502X1501 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 12527500CJ-ZJ0 0 -50 0 -50 35管管 理理 运运 筹筹 学学1811单纯形表的灵敏度分析单纯形表的灵敏度分析接下来又可以有新的迭代S3进基，迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1503X31602 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 16031000CJ-ZJ-70 0 -120 0 20 0管管 理理 运运 筹筹 学学1911单纯形表的灵敏度分析单纯形表的灵敏度分析接上页 可知此规模的最优解X1=0,X2=0,S1=0,S2=0,S3=50,X3=200,此时，最大目标函数为32000元。也就是说，该厂的新的生产计划为不生产、产品，生产产品200件,可获得最大利润32000元。迭代次数基变量CBX1 X2 S1 S2 S3 X3 b50 100 0 0 0 1504X31602 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 16032000CJ-ZJ-70 0 -80 -20 0 0管管 理理 运运 筹筹 学学2011单纯形表的灵敏度分析单纯形表的灵敏度分析 2.在初始表上的变量在初始表上的变量XK的系数的系数PK改变为改变为PK，经，经过迭代后，在最终表上过迭代后，在最终表上XK是基变量，在这种情况下是基变量，在这种情况下原最优解的可行性和最优解都可能被破坏，问题十原最优解的可行性和最优解都可能被破坏，问题十分复杂，一般不去修改原表而是直接计算。分复杂，一般不去修改原表而是直接计算。管管 理理 运运 筹筹 学学2111单纯形表的灵敏度分析单纯形表的灵敏度分析四、增加一个约束条件的灵敏度分析四、增加一个约束条件的灵敏度分析*在原线性规划中增加一个约束条件时在原线性规划中增加一个约束条件时,先将原问先将原问题的最优解的变量值代入新增的约束条件，如满足题的最优解的变量值代入新增的约束条件，如满足则说明新增的条件没有起到限制作用，故原最优解则说明新增的条件没有起到限制作用，故原最优解不变，否则将新增的约束添入原最终单纯形表上进不变，否则将新增的约束添入原最终单纯形表上进一步求解。一步求解。下面仍以第三章例1为例来加以说明。例：假如该工厂除了在设备台时，原材料A、B上对该厂的生产有限制外，还有电力供应上的限制。最高供应电量为5000度，而生产一个产品需要用电10度，而生产一个产品需要用电30度。试分析此时该厂获得最大利润的生产计划？管管 理理 运运 筹筹 学学2211单纯形表的灵敏度分析单纯形表的灵敏度分析 解：先将原问题的最优解=50=50，=250代入用电量的约束条件得：1050+30250=500+75005000,所以原题的最优解不是本题的最优解。在用电量的约束条件中加入松驰变量S4后得：把这个约束条件加入到原最终单纯形表上，其中S4为基变量，得表如下：迭代迭代次数次数基变量基变量b b比比值值50501001000 00 00 00 050501 10 01 10 0-1-10 050500 00 00 0-2-21 11 10 050501001000 01 10 00 01 10 02502500 0101030300 00 00 01 150005000505010010050500 050500 027500275000 00 0-50-500 0-50-500 0管管 理理 运运 筹筹 学学2311单纯形表的灵敏度分析单纯形表的灵敏度分析 在上表中的X1，X2不是单位向量，故进行初等行变换，得迭代迭代次数次数基变量基变量C CB Bx x1 1x x2 2s s1 1s s2 2s s3 3s s4 4b b比值比值50501001000 00 00 00 0 x x1 150501 10 01 10 0-1-10 05050s s2 20 00 00 0-2-21 11 10 05050 x x2 21001000 01 10 00 01 10 0250250s s4 40 00 00 0-10-100 0-20-201 1-3000-3000z zj j505010010050500 050500 027500275000 00 0-50-500 0-50-500 0把上表中的S4行的约束可以写为：上式两边乘以（-1），再加上人工变量a1得：用上式替换上表中的S4行，得下表：管管 理理 运运 筹筹 学学24迭代迭代次数次数基变基变量量x x1 1x x2 2s s1 1s s2 2s s3 3s s4 4a a1 1b b比值比值50501001000 00 00 00 0-M-Mx x1 150501 10 01 10 0-1-10 00 05050s s2 20 00 00 0-2-21 1(1)(1)0 00 050505050 x x2 21001000 01 10 00 01 10 00 0250250250250a a1 1-M-M0 00 010100 02020-1-11 130003000150150z zj j505010010050-10M50-10M0 050-20M50-20MM M-M-M27500-3000M27500-3000M0 00 010M-5010M-500 020M-5020M-50-M-M0 0 x x1 150501 10 0-1-11 10 00 00 0100100s s3 30 00 00 0-2-21 11 10 00 05050 x x2 21001000 01 12 2-1-10 00 00 0200200100100a a1 1-M-M0 00 0(50)(50)-20-200 0-1-11 1200020004040z zj j5050100100150-50M150-50M20M-5020M-500 0M M-M-M25000-2000M25000-2000M0 00 050M-15050M-15050-20M50-20M0 0-M-M0 0 x x1 150501 10 00 03/53/50 0-1/50-1/501/501/50140140s s3 30 00 00 00 01/51/51 1-2/50-2/502/502/50130130 x x2 21001000 01 10 0-1/5-1/50 02/502/50-2/50-2/50120120s s1 10 00 00 01 1-2/5-2/50 0-1/50-1/501/501/504040z zj j50501001000 010100 03 3-3-319000190000 00 00 0-10-100 0-3-3-M+3-M+3管管 理理 运运 筹筹 学学2511单纯形表的灵敏度分析单纯形表的灵敏度分析 由上表可知，最优解为：即该工厂在添加了用电限量以后的最优生产计划为产品生产140件，产品生产120件。管管 理理 运运 筹筹 学学26课堂练习课堂练习已知某线形规划问题的最终单纯形表如下所示：已知某线形规划问题的最终单纯形表如下所示：其中：其中：x4，x5是对应于初始单位矩阵的松弛变量。是对应于初始单位矩阵的松弛变量。1）利用最终单纯形表求）利用最终单纯形表求 c1，c2，c3，c4，c5。2）分别对）分别对c2和和b2作灵敏度分析。作灵敏度分析。3）若增加一新变量）若增加一新变量x6，目标函数系数，目标函数系数c6为为4，在初始单纯形，在初始单纯形表中对应的系数列为（表中对应的系数列为（3，5）T，那么最优解是否改变？，那么最优解是否改变？XB CBc1 c2 c3 c4 c5x1 x2 x3 x4 x5bx1 c1x2 c2 1 0 -1 3 -1 0 1 2 -1 112cj-zj 0 0 -3 -3 -1Z=8管管 理理 运运 筹筹 学学27例题例题1 1 某工厂在计划期内安排、两种产品，生产单位产品所需设备A、B、C台时如表所示 该工厂每生产一单位产品可获利50元，每生产一单位产品可获利100元，问工厂应分别生产多少产品和产品，才能使工厂获利最多？解：设x1为产品的计划产量，x2为产品的计划产量，则有目标函数：Max z z=50 x1+100 x2约束条件：x1+x2300 2x1+x2 400 x2 250 x1,x202 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学28 现在我们从另一个角度来考虑这个问题。假如有另外一个工厂要求租用该厂的设备A、B、C，那么该厂的厂长应该如何来确定合理的租金呢？目标函数：约束条件：这样从两个不同的角度来考虑同一个工厂的最大利润（最小租金）的问题，所建立起来的两个线性模型就是一对对偶问题，其中一个叫做原问题原问题，而另外一个叫对偶问题对偶问题。2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学29如果我们用矩阵形式来表示，则有原问题：其中A是 矩阵m*n，该问题有m个约束条件n个变量，x=,b=,c=对偶问题：其中 是A的转置，是b的转置,是c的转置,y=现在我们用单纯形法求对偶问题的解。2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学30 加上剩余变量 和人工变量 ，把此问题化成标准型如下：把上述数据填入单纯形表计算。2 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-25000M-2502M-1500-M-25002-4001/210-1/201/225-2501/2011/2-1-1/275-325-400-25075250-75-287502500-75-250-M+753-300120-10150-2500-111-1-150-300-350-25050250-50-275000-500-50-250-M+502 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学32 由上表，最优解：y1 =50，y2=0，y3=50，s1=0，s2=0，a1=0，-f 的最大值为-27500，即目标函数f的最大值为f=27500元。从上面可知租金：A设备为50元，B设备为0元，C设备为50元。这样把工厂的所有设备出租可共得租金27500元。对出租者来说这租金是出租者愿意出租设备的最小费用，因为这是目 标函数的最小值。通过比较，我们发现：对偶问题的最优解即最佳租金恰好对偶问题的最优解即最佳租金恰好等于原问题各种设备的对偶价格等于原问题各种设备的对偶价格。2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学33 下面来阐述如何写出一个线性规划问题的对偶问题。为了便于阐述，我们不妨以下面的线性规划为例，写出它的对偶问题。S.T.2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学34 通过上面的一些变换，我们得到了一个和原线性规划等价的线性规划问题：s.t.2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学35 这个求最大值的线性规划问题的约束条件都取小于等于号，我们马上可以写出其对偶问题：s.t.2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学36 这里 和 一样都是不同的决策变量，为了表示这两个决策变量都来源于原问题的第三个约束条件，记为 。因为在该对偶问题中 和 的系数只相差一个符号，我们可以把上面的对偶问题化为：s.t.2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学37 进一步，我们可以令 ，没有非负限制。这样我们把原规划的对偶问题化为 s.t.结论：结论：当原线性规划问题的第当原线性规划问题的第i个约束条件取等号时，则其对偶问题的个约束条件取等号时，则其对偶问题的 i个决策变量没有非负限制。个决策变量没有非负限制。反之，如果当原线性规划问题中的第 i个决策变量 没有非负限制时，我们也可以用 进行替换，这里 ，用类似的方法知道其对偶问题中第 i个约束条件取等号。2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学38 原线性规划问题为：s.t.2 2 线性规划的对偶问题线性规划的对偶问题管管 理理 运运 筹筹 学学39先将第个约束条件两边乘以（）得然后按照上述规则，可得其对偶问题为：管管 理理 运运 筹筹 学学40 线性规划原问题与其对偶问题的相互关系对照表线性规划原问题与其对偶问题的相互关系对照表2 2 线性规划的对偶问题线性规划的对偶问题原问题（）原问题（）对偶问题（）对偶问题（）Max fMin f目标函数系数Cj约束条件右端系数bi约束条件右端系数Cj目标函数系数bi变量个数n约束条件数m约束条件数n变量个数m变量变量无正负限制约束约束约束约束约束约束变量变量无正负限制管管 理理 运运 筹筹 学学41课堂练习：试写出下列线形规划问题的对偶问题。课堂练习：试写出下列线形规划问题的对偶问题。管管 理理 运运 筹筹 学学4233对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质对偶规划的基本性质1对称性对称性。即对偶问题的对偶是原问题。2弱对偶性弱对偶性。即对于原问题（）和对偶问题（）的可行解 都有C bT 。由弱对偶性，可得出以下推论：（1）原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是其原问题目标函数值的上界。（2）如原问题有可行解且目标函数值无界（或具有无界解），则其对偶问题无可行解；反之对偶问题有可行解且目标函数值无界，则其原问题无可行解（注意：本点性质的逆不成立，当对偶问题无可行解时，其原问题或具有无界解或无可行解，反之亦然）。（3）若原问题有可行解而其对偶问题无可行解，则原问题目标函数值无界；反之对偶问题有可行解而其原问题无可行解，则对偶问题的目标函数值无界。管管 理理 运运 筹筹 学学4333对偶规划的基本性质对偶规划的基本性质3最优性最优性。如果 是原问题()的可行解，是对偶问题()的可行解，并且 C =bT ，则 和 分别为原问题()和对偶问题()的最优解。4强对偶性强对偶性。即若原问题()及其对偶问题()都有可行解，则两者都有最优解；且它们的最优解的目标函数都相等。5互补松弛性互补松弛性。在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束条件取严格等式；反之，如果约束条件取严格不等式，则其对应的对偶变量一定为零也即 若yi*0,则有 若 ，则有yi*=0管管 理理 运运 筹筹 学学44对偶问题的经济意义对偶问题的经济意义影子价格影子价格定义定义：在一对对偶问题中，若P的某个约束条件的右端常数bi增加一个单位时，所引起的目标函数最优值Z*的改变量yi*称为第i个约束条件的影子价格。影子价格的特点：影子价格的特点：1）影子价格是对系统资源的一种最优估价，只有系统达到最优状态时才可能赋予该资源这种价值。2）对偶解影子价格的大小客观地反映了资源在系统内的紧缺程度。影子价格越高，资源在系统中越稀缺。管管 理理 运运 筹筹 学学45对偶问题的经济意义对偶问题的经济意义影子价格影子价格 例：某企业生产A、B两种产品。A产品需消耗2单位原料和1小时人工；B产品需消耗3单位原料和2小时人工。A、B售价分别为23元、40元。该企业每天可用原料及人工为25单位和15小时。每单位原料采购成本5元，每小时人工工资10元，问如何安排生产销售利润最大。模型模型1 模型模型2管管 理理 运运 筹筹 学学46对偶问题的经济意义对偶问题的经济意义影子价格影子价格 例：某企业生产A、B两种产品。A产品需消耗2单位原料和1小时人工；B产品需消耗3单位原料和2小时人工。A、B售价分别为23元、40元。该企业每天可用原料及人工为25单位和15小时。每单位原料采购成本5元，每小时人工工资10元，问如何安排生产销售利润最大。模型模型1 模型模型2管管 理理 运运 筹筹 学学47影子价格在经济管理中的应用影子价格在经济管理中的应用1）影子价格可以告诉企业管理者，增加哪一种资源对增加经济效益最有利。5050，0 0，50502）影子价格可以告诉企业管理者，花多大代价来增加资源才是合算的。如增加如增加1 1台时设备的代价大于台时设备的代价大于5050元就不合算元就不合算3）影子价格可以告诉企业管理者，应如何考虑新产品的价格。如企业要生产一种新产品，该产品耗用资源的数量分别为如企业要生产一种新产品，该产品耗用资源的数量分别为（2 2，1 1，2 2），则新产品定价一定要大于），则新产品定价一定要大于 （5050，0 0，5050）（2 2，1 1，2 2）T T=200=200 才能增加公司收益，否则不合算。才能增加公司收益，否则不合算。管管 理理 运运 筹筹 学学48对偶问题的经济意义对偶问题的经济意义影子价格影子价格4）影子价格可以帮助分析工艺改进后对资源节约的收益。如工艺改进后原料如工艺改进后原料B B能节约能节约10%10%，则带来的经济收益将是，则带来的经济收益将是 50*400*10%=200050*400*10%=20005）利用影子价格，可以分析现有产品价格变动对资源紧缺情况的影响。如当产品利润由（如当产品利润由（5050，100100）变为（）变为（4040，120120），则从最终），则从最终单纯形表可出重新计算对偶解得：单纯形表可出重新计算对偶解得：管管 理理 运运 筹筹 学学4944对偶单纯形法对偶单纯形法 对偶单纯形法也是解决线性规划问题的一种方法。对偶单对偶单纯形法也是解决线性规划问题的一种方法。对偶单纯形法是在保持原有问题的所有检验数都小于纯形法是在保持原有问题的所有检验数都小于0的情况下，的情况下，通过迭代使得所有的约束都大于等于通过迭代使得所有的约束都大于等于0，最后求得最优解。，最后求得最优解。上节分析中已知当250b1325时第一个约束条件的对偶价格不变，现在b1=300变成b1=350，请问这时第一个约束方程的对偶价格应为多少呢？解：求出在第二次迭代表上的常数列 管管 理理 运运 筹筹 学学5044对偶单纯形法对偶单纯形法迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 1 0 -1100 S200 0 -2 1 1-50 X21000 1 0 0 1250 ZJ50 100 0 50 50CJ-ZJ0 0 -50 0 -501.确定出基变量，在常数列中找一最小的负常量，把这个常量所在行作为出基变量管管 理理 运运 筹筹 学学5144对偶单纯形法对偶单纯形法 4.检查常数列值，若已经都非负结束迭代，即为最优，如果还有负数重复1-4步。迭代次数基变量CBX1 X2 S1 S2 S3b50 100 0 0 02X1501 0 0 1/2 -1/275 S100 0 1 -1/2 -1/225 X21000 1 0 0 1250 ZJ50 100 0 25 7528750CJ-ZJ0 0 0 -25 -75