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

管理运筹学1第六章单纯形法的灵敏度分析与对偶管理运筹学2§1单纯形表的灵敏度分析§2线性规划的对偶问题§3对偶规划的基本性质§4对偶单纯形法管理运筹学3第一节单纯形表的灵敏度分析管理运筹学4kkcckckc一、目标函数中变量Ck系数灵敏度分析1.在最终的单纯形表里，Xk是非基变量由于约束方程系数增广矩阵在迭代中只是其本身的行的初等变换与没有任何关系，所以当变成时，在最终单纯形表中其系数的增广矩阵不变，又因为Xk是非基变量，所以基变量的目标函数的系数不变，即CB不变，可知Zk也不变，管理运筹学5只是变成了这时就变成了要使原来的最优解仍为最优解，只要即可，也就是的增量即可.kkckkkcz.kkcckc.kkkkkcczcVV0kkcVkc管理运筹学62.在最终的单纯形表中，是基变量当变成时，最终单纯形表中约束方程的增广矩阵不变，但是基变量的目标函数的系数变了，则一般也变了，不妨设当变成则：kkcckckx(1,2,)jzjnLBc12(,,,,),BBBkBmcccccLLBc12(,,,,),BBBkkBmccccccLVL管理运筹学71212112(,,,,)(,,,,)(,,,,)TjBBkBmjjkjmjjkjjBBkkBmmjzccccaaaaaazccccca变＋成了管理运筹学811221122BjBjkkkjBmmjBjBjkkjBmmjkkjjkkjcacaccacacacacacacazca＝＋＋（＋）＋＝＋＋＋＋＝＋管理运筹学9根据上式可知检验数变成了且有：(1,2,)jjm,j()()jjjjjkkjjjkkjjkkjczczcaczcaca管理运筹学10要使最优解不变，只要0jkkjkkjjcaca当时，0kja,0;jjkkjkjcaa当时，0kja,0;jjkkjkjcaa0,jjk时，：即管理运筹学11010.jkkkkkkkkkkkkkjkcczcczcaxa当＝时，变＝，而而是基量所以，管理运筹学12kkjkjkkkjjkjkkjjjkjkkjkjkja'0a'CΔCa'0a'ΔCa'maxa'0ΔCMina'0a'a'kC说变对，满，满，变围为:也就是，要使得最优解不，于除了以外的所有大于的的增量足所有小于的足所以可知的化范管理运筹学13例：121212212max50100.300400250,0zxxstxxxxxxx最优单纯形表如下管理运筹学14迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-50管理运筹学15我们先对非基变量S1的目标函数的系数C3进行灵敏度分析。这里σ3=-50，所以当c3的增量Δc3≤50时，最优解不变。再对基变量x1的目标函数的系数c1进行灵敏度分析。在a11’,a12’,a13’,a14’,a15’中，除了知道a11’和a13’大于0，a15’小于0，可知有:3135050,1a管理运筹学16这样可以知道当-50≤Δc1≤50时，也就是x1的目标函数c1’在0≤c1’≤100时最优解不变。我们也可以在最终的单纯形表中，对它进行灵敏度分析，在最终的单纯形表中，用C’1代替原来的C1=50,计算得下表：'11'51115max0max5050'min0min50.''jjjjjjaaaaa，同理有：管理运筹学17迭代次数基变量CBX1X2S1S2S3bC’11000002X1C’11010-150S2000-21150X210001001250ZJC’1100C’10-C’1+100CJ-ZJ00-C’10C’1-100管理运筹学18从σ3≤0，得到-c1’≤0,即c1’≥0，并且从σ5≤0，得到c1’≤100。那么如果c1’取值超出这个范围，必然存在一个检验数大于0，我们可以通过迭代来得到新的最优解。管理运筹学19二、资源指标项的灵敏度分析资源指标项的灵敏度分析是指：约束方程中常数项在什么范围内变化时，其对偶价格不变。因此我们首先应从单纯形表格中找到有关对偶价格的信息。管理运筹学20所谓对偶价格是指：约束条件的常数项增加一个单位而使得目标函数值得到改进的数量。因此可知约束条件的对偶价格与松弛变量（或剩余变量，或人工变量）的值有关系，下面仍以上面的题为例在单纯形表中找到约束方程的对偶价格。此题的求解结果与最终单纯形表如下：jz管理运筹学21迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-50管理运筹学22管理运筹学23从上表我们可以发现各个松弛变量的值，正好等于相应约束方程的对偶价格。jz管理运筹学24如在最优解中S2=50是基变量，即原料A有50千克没用完，再增加A原料是不会增加利润的，故A的对偶价格为0。一、在最终的单纯形表上当松弛变量为基变量时，都有其对偶价格为零。管理运筹学25我们知道对于任何的松弛变量它在目标函数中的系数而在最终的单纯形表上若松弛变量为基变量时，都有其检验数那么为松弛变量的也为零，因为这正确反映了对任何为基变量的松弛变量所对应的约束条件的对偶价格为零。0,j0,jc0,jjjzcjz管理运筹学26二、对于为非基变量的松弛变量而言，其值也正确反映了对应的约束条件的对偶价格。因为对于所有的松弛变量都有所以在对非基变量的目标函数的灵敏度分析时，我们知道当时最优解不变。也就是说，当时，非基变量仍为非基变量，仍然为零。0,jc,jjjjzcjjcjjc管理运筹学27这时与其对应的约束条件譬如说设备台时数全部用完了，只有当即时，对应为非基变量的松弛变量要变成入基变量了。对于设备台时数约束来说，当其松弛变量的价格指标从0变到50时，也就是只要当前余下一台时数设备从不能获利变成获利50元时，jjcz,jjc管理运筹学28譬如有人愿意出50元买一个设备时，我们就不必为生产Ι、П产品而使用完所有的设备台时了，这说明了设备台时数的对偶价格就是Z3=50元。同理可以知道原料B的对偶价格为50。管理运筹学29而对于含有大于等于号的约束条件，添加剩余变量化为标准型。这时这个约束条件的对偶价格就和这个剩余变量的有关了。这将使得最优目标值特别“恶化”而不是改进，故这时约束条件的对偶价格应取值的相反数jz.jzjz管理运筹学30对于含有等于号的约束条件，其约束条件的对偶价格就和该约束方程的人工变量有关了。其约束条件的对偶价格就等于此约束方程的人工变量的值。下表给出了一个由最终单纯形表对于不同约束类型的对偶价格的取值。jz管理运筹学31约束条件对偶价格的取值≤等于这个约束条件对应的松弛变量的值。≥等于这个约束条件对应的剩余变量的值的相反数，即=等于这个约束条件对应的人工变量的值。jzjzjz.jz管理运筹学32其次，我们已知单纯形法的实质是:令),(NBA，x=(Bx,Nx)。bAx分块bNxBxNB左乘1BbBNxBxNB11即NBNxBbBx11Nx=001bBx管理运筹学33即单纯形表的迭代实质是在表上进行行初等变换，由线性代数知:11(,)(,)(,)(,)BIIBBIIB，－－因此也有：因此，在初始单纯形表里的系数矩阵中的单位矩阵正好变成了如上例的最终单纯形表如下：1.B管理运筹学34迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-50管理运筹学35由上表可知：1101211001B同时还可以知道：1.bbBb迭代管理运筹学36下面我们研究当右端项发生变化时，在什么范围内其对偶价格不变由于的变化并不影响系数矩阵的迭代，故其最终单纯形表中的系数矩阵没有变化。要使对偶价格不变，只要原来最终单纯形表中的所有值都不变化。jbjbjz管理运筹学37而这样当基变量的系数不变，即基不变时，原线性规划问题的对偶价格就不变。而要使所有基变量不变，只要使当变化时，原来的基不变得到的基本可行解仍然是可行解，也就是所求的基变量的值一定要大于0。jb,jTjBzcp管理运筹学38由此可见，所谓使其对偶价格不变的的变化范围，也就是使其最优解的所有基变量不变，且所得的最优解仍然是可行的的变化范围。jbjb管理运筹学39例：在第二章例1为中分析，若：（1）、在什么范围内变化时，其对应的设备的对偶价格不变。（2）、当时，求出新的最优解。解：其最终单纯形表如下：1b1350b管理运筹学40迭代次数基变量CBX1X2S1S2S3b501000002X1501010-150S2000-21150X210001001250ZJ501005005027500CJ-ZJ00-500-50管理运筹学411101211001B（1）、由表可以知道：11101211400001250BbxBb管理运筹学42111111250265025025026500250325.250BbxBbbbbb由管理运筹学43实际意义可以描述为：当设备台时数的对偶价格不变，都为每设备台时数在250与325之间变化，则设备台时数的对偶价格不变，都为每台设备台时50元。管理运筹学44（2）、当时有：1350b110135021140000125010050250bBb满资标负不足源指非要求。管理运筹学45迭代次数基变量CBX1X2S1S2S3b501000002X1501010-1100S2000-211-50X210001001250ZJ501005005027500CJ-ZJ00-500-50管理运筹学46所有检验数都小于或等于零，但是资源指标有取负值的，需要重新迭代找到新的最优解，我们随后将借助于对偶单纯形法来求解。管理运筹学47三、技术指标的灵敏度分析：下面分两种情况讨论1、在初始单纯形表上的变量的系数列改变为经过迭代后，在最终单纯形表上是非基变量。kxkpkpkx管理运筹学48由于单纯形表的迭代是约束方程的增广矩阵的行变换，变成仅仅影响最终单纯形表上第列数据，包括的系数列、以及这时最终单纯形表上的的系数列就变成了而就变成新的检验数kxkpkpkkxkz,k1,kBp1,BkCBp1.kkBkcCBpkz管理运筹学49若则原最优解仍然为最优解。若则继续进行迭代以求出最优。10,kkBkcCBp10,kkBkcCBp管理运筹学50例1：以第二章例1为基础，设该厂除了生产Ι，Ⅱ种产品外，现在试制成一个新产品Ⅲ，已知生产产品Ⅲ,每件需要设备2台时，并消耗A原料0.5公斤。B原料1.5公斤，获利150元，问该厂应该生产该产品多少？管理运筹学51解：这是一个增加新变量的问题。我们可以把它认为是一个改变变量在初始表上的系数列的问题，从变成