1、12.1单纯形法的矩阵表示现在介绍用矩阵来描述单纯形法的整个计算过程它将有助于加深对单纯形法的理解、研究改进单纯形法、对偶理论等设线性规划问题maxZ=CX0XbAX给这个规划问题的约束条件中加入松驰变量X5=（xn+1,xn+2,xn+m）T以后得到标准型2maxZ=CX+0X0,0SSXXbIXAX这里I是mm阶单位矩阵设B是一个可行基，也称为基矩阵于是可将系数矩阵A分为两块A=（B，N）这里N是非基向量构成的矩阵对应于B的变量xB1,xB2,xBm是基变量用向量XB=（xB1,xB2,xBm）T表示其它的为非基变量。则NBXXx3这时C也分为两块（CB，CN）其中CB是目标函数中基变量向
2、量XB的系数行向量；CN是目标函数中非基变量向量XN的系数行向量。SNNBBSNBNBsSNBSNBsXXCXCXXXCCXXCIXNXBXXXXINBXXIA0) 0 ,() 0 ,(),(),(4maxZ=CBXB+CNXN+0XS0,) 5 . 4 (SNBSNBXXXbIXNXBX将式（4.5）移项后得到BXB=bNXNIXS上式左乘B-1后，得到XB的表达式XB=B-1bB-1NXNB-1XS上式代入目标函数，得到Z=CBB1b+(CNCBB-1N)XNCBB-1XS5令非基变量XN=0，XS=0，得到一个基可行解001) 1 (bBXXXXSNB目标函数取值Z=CBB-1b61、非
3、基变量的系数CNCBB-1N与CBB-1就是第一章中用符号CjZj(j=1,2,n)表示的检验数。因为xB的系数是0，实质上是CBCBB-1B=0Xs的系数实质上是0CBB-1I因此所有的检验数可用CCBB-1A与CBB-1表示72、用矩阵描述时，规则的表达式是ljlijijiPBbBPBPBbB)()(0)()(min11111这里（B-1b)i是向量（B-1b）中第i个元素。（B-1Pj)i是向量（B-1Pj）中第i个元素。83、单纯形表初始单纯形表初始非基变量初始基变量X=（XB，XN）TXS（B，N）Ib(cB，cN)00分块的系数矩阵可用表格形式表示为基变量XB非基变量XNXSIB-
4、1NB-1b0CNCBB-1NCBB-1CBB-1b上述表格即为迭代后的计算表92.改进单纯形法v前面我们已经熟悉了单纯形法的表格计算方法，这是求解线性规划问题的一般的通用方法。但用这种方法求解具体问题时，发现在每次迭代过程中不必要的计算了很多无用的数字，影响了计算效率。从计算机计算的角度来徇，单纯形法也不是一个很经济的算法，需要计算的数字多，并且要占有大量的计算机存储容量。这样就导致了改进单纯形法的出现。改进单纯形法是但泽在1953年研究出来的，其基本步骤与单纯形法大致相同，最主的区别在于每次迭代中不再以矩阵的行初等变换为基础，而是每次都从原始数据求得迭代的结果。这样就减少了每次迭代中积累起
5、来的误差，既提高了计算的精度，又减少了计算机的存储容量。v我们知道，单纯形法的迭代过程实质上是从一组基到另一组基的变换，变换一组基，得到一个新的表。根据矩阵理论，每当基变量确定后，要想得到新的表，可以有两种方法，一是矩阵的初等行变换；二是由原始数据直接得到即把这个基变量在初始单纯形表中相应列的系数矩阵的逆矩阵求出来，则新表中的列都可由这个逆矩阵左乘原来的列得到。而为了确定一组新的基，关键是要找出换入变量和换出变量，找换入变量是通过求所有非基变量列的检验数，从中找出最大的正检验数来确定。在找出换入变量后，根据规则确定换出变量。而每次迭代中真正有用的数字是b列数字，基的逆矩阵，非基变量的检验数以及
6、最大正检验数对应的非基变量的系数列向量。10例1：试用改进单纯形法求解下述问题vminZ=3x1+x2+x30,1232411232131321321xxxxxxxxxxx11解：步解：步1 化标准形式，求初始解化标准形式，求初始解vmaxZ=3x1x2x3Mx6Mx70,12324112721731653214321xxxxxxxxxxxxxxx12v初始基变量(x4,x6,x7)T，CB0=(0,M,M)v初始基矩阵v计算B0-1=B0=Iv得初始解v计算单纯形乘子IPPPB100010001),(76400,131113110100NBxIbBx), 0 (), 0 (1000MMIMM
7、BCYB13步2：计算非基变量的检验数MMMPYCMMMPYCMMMPYCMMMPYC 010),0(031121),0(11012),0(163241),0(3505530332012101114步3：vmax(20,30)=3，k=3对应x3为换入变量v计算x3的系数列向量a3va3有大于零的分量，故该题有解。121213103IIPBa15步4：计算1)1/1 ,2/3,1/11min(L=3，可知x7为换出变量。a33=1为主元素。新的基变量为（x4,x6,x3）TCB1=(0,-M,-1)B1=(P4,P6,P3)16步5：写出E33矩阵lka写出Elk矩阵的方法（1）E的单位列向量
8、不变；（2）第k列元素中，主元素lka变为lka/1其它元素除以负的主元素-Elk（l，k表示主元素的位置）10121010133E17步6：计算新基的逆100210101100210101103311IBEB计算新基可行解111013111002101011111bBbxB计算单纯形乘子) 12 , 0 (), 0 (111111MMBMMBCYB18v转步2：计算非基变量检验数MMMPYCMMMPYCMMPYC010)12,0(01112)12,0(11241)12,0(3515521221111因人工变量旋出后，一般不会再旋入，故不用计算7。因j中有大于零的分量，xB1不是最优解。19转
9、步3：max(10，20)=2，k=2，故x2为换入变量，计算x2的系数列向量01201211211BPB20步4：计算=min-1/1,=1，可知L=2，对应x6为换出变量，主元素a22=1新的基变量为（x4,x2,x3）T，CB2=(0,-1,-1)B2=(P4,P2,P3)步5：写出E22矩阵步6：计算12B100210521112212BEB10001002122E21计算新的基可行解11121311121222BbBbxB计算单纯形乘子及检验数1010) 1 , 1, 0(01241) 1 , 1, 0(3) 1 , 1, 0() 1, 1, 0(52551211122222PYCP
10、YCBBCYB6，7不用计算j中仍有不大于0的分量，故xB2不是最优解22步3：max(10)=1，k=1，故x1为换入变量。计算x1的系数列向量 20324112112BPB步4：计算=min12/3,，=4，L=1，则x4为换出变量。a11=3为主元素。新的基变量为（x1,x2,x3）CB3=(3,-1,-1)B3=(P1,P2,P3)23步5：写出E11矩阵步6：计算13B3 / 73 / 43 / 22103 / 53 / 23 / 1121113BEB计算新的基可行解) 3/ 2, 3/ 1, 3/ 1 () 1, 1, 3 (914131113133313133BBCYBbBxBB
11、103/2010003/111E24转步2：计算非基变量检验数3/13/153554344PYCPYC6，7不用计算所有j0，说明目标函数已达极大，停止计算最优解x=(4,1,9,0,0,0,0)TmaxZ=-2则minZ=2253. 3. 对偶问题的提出对偶问题的提出 对偶原理 对偶问题定义 线性规划问题写出其对偶问题，要掌握在对称形式和非对称情况下由原问题写出对偶问题的方法。 对偶定理 理解原问题与对偶问题解的关系。26 1.对偶问题： 若第一章例1.1问题的设备都用于外协加工，工厂收取加工费。试问：设备 A、B、C 每工时各如何收费才最有竞争力？ 设 y1 ，y2 ，y3 分别为每工时设
12、备 A、B、C 的收取费用。27线性规划原问题线性规划原问题 例1.1:某工厂拥有A、B、C三种类型的设备，生产甲、乙两种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示。求获最大利润的方案。产品甲产品乙设备能力（h）设备A3 32 26565设备B2 21 14040设备C0 03 37575利润/（元/件）150015002500250028 Max z = 1500 x1 + 2500 x2 s.t. 3x1 + 2x2 65 2x1 + x2 40 原问题原问题 3x2 75 x1 ,x2 0 Min f = 65y1+ 40y2 +
13、 75y3 s.t. 3y1+2y2 1500 （不少于甲产品的利润） 2y1+y2+3y3 2500 对偶问题对偶问题 （不少于乙产品的利润） y1, y2 , y3 029 第4节、线性规划的对偶理论 1、对称形式： 互为对偶(LP)Maxz = cx(DP)Minf= bTys.t. Ax bs.t.ATycx0y0“Max”“Min”30 ), 1(0max:221122222121112121112211njxbxaxaxabxaxaxabxaxaxaxcxcxczLPjmnmnmmnnnnnn ), 1(0min:221122222112112211112211miycyayaya
14、cyayayacyayayaybybybwDPinmmnnnmmmmmm对称形式下对偶问题的一般形式31 一对对称形式的对偶规划之间具有下面的对应关系。 (1)若一个模型为目标求“极大”，约束为“小于等于”的不等式，则它的对偶模型为目标求“极小”，约束是“大于等于”的不等式。即“max，”和“min，”相对应。32 (2)从约束系数矩阵看：一个模型中为，则另一个模型中为AT。一个模型是m个约束，n个变量，则它的对偶模型为n个约束，m个变量。 (3)从数据b、C的位置看：在两个规划模型中，b和C的位置对换。 (4)两个规划模型中的变量皆非负。33LP和和DP的联系与区别的联系与区别(1)一个极大
15、化，一个极小化一个极大化，一个极小化(2)LP的价值系数行向量的价值系数行向量(DP右端项右端项)(3)LP的系数矩阵的系数矩阵(DP系数矩阵系数矩阵)(4)LP的右端项的右端项(DP的价值系数的价值系数)(5)LP的约束个数的约束个数DP的变量个数的变量个数(6)LP的变量个数的变量个数DP的约束个数的约束个数LP：原线性规划：原线性规划DP：对偶规划：对偶规划34例：写出例：写出LP的对偶问题的对偶问题02,1121214222max:21212121xxxxxxxxxxzLP0,224222min:321321321321yyyyyyyyyyyywDP35 2、非对称形式的对偶规划 一般
16、称不具有对称形式的一对线性规划为非对称形式的对偶规划。 对于非对称形式的规划，可以按照下面 的对应关系直接给出其对偶规划。 （1）将模型统一为“max，”或“min，” 的形式，对于其中的等式约束按下面（2）、（3）中的方法处理； （2）若原规划的某个约束条件为等式约束，则在对偶规划中与此约束对应的那个变量取值没有非负限制；2b2b36 （3）若原规划的某个变量的值没有非负限 制，则在对偶问题中与此变量对应的那个 约束为等式。 下面对关系（2）作一说明。对于关系（3） 可以给出类似的解释。 设原规划中第一个约束为等式： a11x1 + + a1nxn = b1 那么，这个等式与下面两个不等式等
17、价11111bxaxann11111bxaxann371111111111.bxaxabxaxannnnmjxbxaxabxaxabxaxaxcxcZjmnmnmnnnnnn,2,1,0max11111111111111原规划成为38此时已转化为对称形式，直接写出对偶规划这里，把 y1 看作是 y1 = y1 - y1，于是 y1 没有非负限制，关系（2）的说明完毕。没有非负限制121111112211211211111111221111, 0, , minyyyyycyayayacyayayacyayayaybybybybfmnmmnnnmmmmmm39对偶关系相互对照表原问题(LP)对偶问
18、题(DP)目标函数形式max目标函数形式min变量N个变量变量0变量0无正负限制约束n个约束约束约束约束约束M个约束约束约束约束变量m个变量变量0变量0无正负限制约束方程右端项目标函数价值系数目标函数价值系数约束方程右端项40无约束32132132132132100121213225minxxxxxxxxxxxxxxxz例例 写出下列线性规划的对偶问题写出下列线性规划的对偶问题结果无约束32132132132132100322252maxyyyyyyyyyyyyyyyw41练习写出下列线性规划的对偶问题无约束321313213213210034313242maxxxxxxxxxxxxxxxz练
19、习结果无约束321321213213210041323234minyyyyyyyyyyyyyyw42 例 写出下面线性规划的对偶规划模型解 先将约束条件变形为“”形式没有非负限制321432143143214321, 0,1053042260272252375maxxxxxxxxxxxxxxxxxxxZ43再根据非对称形式的对应关系，直接写出对偶规划没有非负限制4321443214314321,0,051030422602722523xxxxxxxxxxxxxxxx440,725472123122510306025min5432154213213132154321yyyyyyyyyyyyyyy
20、yyyyyyyf没有非负限制45 3.对偶问题的基本性质(对偶定理）考虑（LP）和（DP） 推论 若（LP）可行，那么（LP）无有限最优解的充分必要条件是（DP）无可行解。（1）对称性定理：对偶问题的对偶是原问题。）对称性定理：对偶问题的对偶是原问题。（2）(弱对偶定理弱对偶定理)：如果：如果X(0)是原问题的可行解，是原问题的可行解，Y(0)是对偶问题的可行解，则恒有是对偶问题的可行解，则恒有 C X(0) Y(0) b46b,如原问题有可行解且目标函数值无界，如原问题有可行解且目标函数值无界，则其对偶问题无可行解；则其对偶问题无可行解； 反之反之,对偶问题有可行解且目标函数值无界对偶问题有
21、可行解且目标函数值无界则其原问题无可行解。则其原问题无可行解。a,原问题任一可行解的目标函数值是原问题任一可行解的目标函数值是 其对偶问题目标函数值的下界；其对偶问题目标函数值的下界； 反之反之,对偶问题任一可行解的目标函数值对偶问题任一可行解的目标函数值 是其原问题目标函数值的上界。是其原问题目标函数值的上界。c,如原问题有可行解而其对偶问题无可行解，如原问题有可行解而其对偶问题无可行解， 则原问题目标函数值无界；则原问题目标函数值无界； 反之反之,对偶问题有可行解而其原问题无可行解，对偶问题有可行解而其原问题无可行解， 则对偶问题的目标函数值无界。则对偶问题的目标函数值无界。47(3)(最
22、优准则定理最优准则定理)：如果：如果X(0)是原问题的可行解，是原问题的可行解，Y(0)是对偶问题的可行解，是对偶问题的可行解，则当则当C X(0) Y(0) b时，时， X(0) ， Y(0)分别为各自问题的最优解。分别为各自问题的最优解。(4)(强对偶性定理强对偶性定理)：如果原问题和对偶问题中有一个有最优解，如果原问题和对偶问题中有一个有最优解，则另一个问题也必存在最优解，则另一个问题也必存在最优解，且两个问题的目标函数值相等。且两个问题的目标函数值相等。 原问题与对偶问题的解之间只有以下3种可能的关系a,两个问题都有可行解，从而都有最优解b,一个为无界，另一个必无可行解c,两个都无可行
23、解48(6)(互补松弛性)为最优解。当且仅当和则：题的可行解，分别为原问题和对偶问若Y,X0XY0XYY,XSS注：以上定理、推论对任意形式的相应线性规划的对偶均有效在线性规划问题的最优解中，在线性规划问题的最优解中，如果对应某一约束条件的对偶变量值为非零，则该约束取严格等式；如果对应某一约束条件的对偶变量值为非零，则该约束取严格等式；反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。反之如果约束条件取严格不等式，则其对应的对偶变量一定为零。49对偶性质应用对偶性质应用例例 不计算，判断下列线性规划解的特征：不计算，判断下列线性规划解的特征： 012232132132121x,x,xx
24、xxxxx. t . sxxzMax50显然，x=(0,0,0)T是原规划的可行解；对偶规划为：显然，第一约束与非负约束矛盾，对偶规划无解。故原规划无有限最优解。0,0112.s.t2Max2121212121yyyyyyyyyyf5102, 11332232max:21212121xxxxxxxxxxzLP例例 已知下列问题的最优解为已知下列问题的最优解为X*=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。用互补松弛定理求其对偶问题的最优解。52解：第一步，写出对偶问题0002321332min:321321321321yyyyyyyyyyyywDP第二步，将LP，DP都化为标准
25、型0,02, 11332232max:32132122112121SSSSSSxxxxxxxxxxxxxxzLP0,0002321332min:2132123211321321SSSSyyyyyyyyyyyyyyywDP53第三步：将最优解代入标准型中，确定松弛变量取值73900171137137112712711713321321SSSSSSxxxxxx第四步：利用互补松弛定理0*)*,*,(*332211321321SSSSSSSXYXYXYXXXYYYXYY3*=0540*),(*22112121XYXYXXYYXYSSSSSY1S=0Y2S=0第五步：将Y3*=0Y1S=0Y2S=0代
26、入约束条件75742213212121yyyyyy 对偶问题的最优解为对偶问题的最优解为Y*=(4/7,5/7,0)55例例 利用对偶理论求解下列线性规划问题：利用对偶理论求解下列线性规划问题：0 x,x,3xx3243xx2. .3x2x5x32win54321543215432154321xxxxxxxxxtsxxM已知其对偶问题的解为已知其对偶问题的解为5zmax,53y,54y*2*1560y,y) 5 (3y3y) 4(2yy) 3 (53y2y) 2(3yy) 1 (22yy. t . s3y4ymaxz:21212121212121对偶问题为解由互补松弛性得）为严格不等式，带入约
27、束条件中，得将4)(3)(2(y,y*2*10 xxx*4*3*23x4,2x3xx, 0y,y*5*1*5*121所以：应取等式原问题的两个约束条件因1x, 1x*5*1解得：5w10001X*T*；），（原问题的最优解为：57练习练习 若对偶问题的最优解为若对偶问题的最优解为Y*=(4.1)，试用互补松弛定理求原问题的最优解。试用互补松弛定理求原问题的最优解。答案：答案：X*=(0,0,4,4)01222282652max4143214314321xxxxxxxxxxxxz58 第第5 5节节. .影子价格影子价格 是一个向量，它的分量表示最优目标值随相应资源数量变化的变化率。 若x*,y
28、* 分别为（LP）和（DP）的最优解， 那么， c x* = bT y* 。 根据 f = bTy*=b1y1*+b2y2*+bmym* 可知 f / bi = yi* yi* 表示 bi 变化1个单位对目标 f 产生的影响，称 yi* 为 bi的影子价格。 注意：注意：若 B 是最优基， y* = (BT)-1 cB 为影子价格向量。59 影子价格的经济含义 (1)影子价格是对现有资源实现最大效益时的一种估价 企业可以根据现有资源的影子价格，对资源的使用有两种考虑：第一，是否将设备用于外加工或出租，若租费高于某设备的影子价格，可考虑出租该设备，否则不宜出租。第二，是否将投资用于购买设备，以扩
29、大生产能力，若市价低于某设备的影子价格，可考虑买进该设备，否则不宜买进。60 因此，可以将因此，可以将z z* *看作是看作是b bi i, ,i i=1,2=1,2， , ,m m的函数，的函数， 对对b bi i求偏导数可得到求偏导数可得到*22*11*mmybybybfZ2）影子价格表明资源增加对总效益产生的影响。影子价格表明资源增加对总效益产生的影响。根据推论推论“设x0和y0分别为原规划（LP）和对偶规划（DP）的可行解，当cx0=bTy0时，x0、y0分别是两个问题的最优解”可知，在最优解的情况下，有关系miybZii,2, 1,*这说明，如果右端常数增加一个单位，这说明，如果右端
30、常数增加一个单位，则目标函数值的增量将是则目标函数值的增量将是miyi,2,1,*61 影子价格反映了不同的局部或个体的增量可以获得不同的整体经济效益。如果为了扩大生产能力，考虑增加设备，就应该从影子价格高的设备入手。这样可以用较少的局部努力，获得较大的整体效益。 需要指出，影子价格不是固定不变需要指出，影子价格不是固定不变的，当约束条件、产品利润等发生变化的，当约束条件、产品利润等发生变化时，有可能使影子价格发生变化。另外，时，有可能使影子价格发生变化。另外，影子价格的经济含义是指资源在一影子价格的经济含义是指资源在一定范围内增加时的情况定范围内增加时的情况，当某种资源，当某种资源的增加超过
31、了这个的增加超过了这个“一定的范围一定的范围”时，时，总利润的增加量则不是按照影子价格给总利润的增加量则不是按照影子价格给出的数值线性地增加。这个问题还将在出的数值线性地增加。这个问题还将在灵敏度分析一节中讨论。灵敏度分析一节中讨论。63 5.由最优单纯形表求对偶问题最优解 标准形式： Max z = 50 x1 + 100 x2 s.t. x1 + x2 + x3 = 300 2x1 + x2 + x4 = 400 x2 + x5 = 250 x1 ,x2 ,x3 ,x4 ,x5 06450100000CBXBx1x2x3x4x5i0 x3300111003000 x440021010400
32、0 x52500(1)001250-z050100*0000 x350(1)010-1500 x41502001-175100 x225001001-z-2500050*000-10050 x1501010-10 x45000-211100 x225001001-z-2750000-500-50-c-cB BT TB B-1-1I IB B=(p p1 1, p, p4 4,p,p2 2 )oTB B-1-1最优解 x1 = 50 x2 = 250 x4 = 50影子价格影子价格 y y1 1 = 50 = 50 y y2 2 = 0 = 0 y y3 3 = 50 , = 50 , B B-
33、1-1对应的检验数对应的检验数 T T = = c cB BT TB B-1-165 对偶单纯形法的基本思想 从原规划的一个基本解基本解出发，此基本解不一定可行，但它对应着一个对偶对偶可行解可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。第第6 6节节. .对偶单纯形法对偶单纯形法66 如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行
34、，当同时得到对偶规划与原 规划的可行解时，便 得到原规划的最优解。. .对偶单纯形法对偶单纯形法67 对偶单纯形法在什么情况下使用 ： 应用前提：有一个基，其对应的基满足: 单纯形表的检验数行全部非正（对偶可行）； 变量取值可有负数（非可行解）。 注：通过矩阵行变换运算，使所有相应变量取值均为非负数即得到最优单纯形表。. .对偶单纯形法对偶单纯形法68v 1.建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 2.若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 3.若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则
35、选 =minj / akjakj0=r/akr那么 xr为进基变量,转4； 4.以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。 对偶单纯形法求解线性规划问题对偶单纯形法求解线性规划问题过程：过程：. .对偶单纯形法对偶单纯形法69例：求解线性规划问题：求解线性规划问题： 标准化：标准化： Max z = - 2x1 - 3x2 - 4x3 s.t. -x1-2x2-x3+x4= -3 -2x1+x2-3x3+x5= -4 x1,x2,x3,x4,x5 0Min f = 2x1 + 3x2 + 4x3 S.t. x1 + 2x2 + x3 3 2x1 - x2 + x3 4
36、x1 , x2 , x3 0 2.2.对偶单纯形法对偶单纯形法最优解为最优解为: x = ( 2.2, 0.4, 0, 0, 0 )T , z = -5.6最优值最优值 f = 5.6无可行解情况无可行解情况 线性规划问题可能出现不存在可线性规划问题可能出现不存在可行解的情况，这时，在对偶单纯形表行解的情况，这时，在对偶单纯形表中显示矛盾方程。中显示矛盾方程。例例 MaxMax z = x1 3x2 2x3 s.t.s.t. x1 + 2x2 + 3x3 + x4 = -10 2x1 + x2 + 5x3 + x5 = 20 3x1 + 2x2 - x3 + x6 = -12 x1 , x2
37、, x3 , x4 , x5 , x6 0对偶单纯形表对偶单纯形表表中第表中第1行反映了一个矛盾约束：行反映了一个矛盾约束： x1 + 2x2 + 3x3 + x4 = -10 即过程的第即过程的第3 3步：步：3.3.若所有若所有akj0( ( j = 1,2,n ) )，则原问题无可行解，则原问题无可行解, ,停止停止; ;-1-3-2000 xB x1 x2 x3 x4 x5 x6 x4 -10123100 x5 20215010 x6 -1232-1001 0-1-3-2000比较比较是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数
38、所有所有计算计算以为中心元素进行迭代以为中心元素进行迭代停没有最优解没有最优解单纯形法单纯形法对偶单纯形法对偶单纯形法0j0ib0maxjjk0miniiebbb0ika0ljaekeikikiabaab0minekkejejiaaa0min0csMinj/asjasj0brMin-bi/airair0. .灵敏度分析灵敏度分析89例:上例最优单纯形表如下C i23000CBX BBX 1X 2X 3X 4X 52X 141001/400X 5400-21/213X 22011/2-1/80j00-1.5-1/80. .灵敏度分析灵敏度分析90 0 0.25 0 这里 B B-1 = -2 0
39、.5 1 0.5 -0.125 0 各列分别对应 b1、b2、b3 的单一变化因此，设 b1 增加 4，则 x1 ,x5 ,x2分别变为：4+04=4, 4+(-2)4=-40, 2+0.54=4用对偶单纯形法进一步求解，可得：x* = ( 4, 3, 2, 0, 0 )T f* = 17. .灵敏度分析灵敏度分析91 增加一个变量 增加变量 xn+1 则有相应的pn+1 ,cn+1 。 那么 计算出B B-1pn+1 , n+1=cn+1-cri ari n+1 填入最优单纯形表, 若 n+1 0 则 最优解不变； 否则，进一步用单纯形法求解。. .灵敏度分析灵敏度分析92例:例 增加x6
40、, p6=( 2, 6, 3 )T, c6=5 计算得到Ci230005CBXBbX1X2X3X4X5X62X141001/401.50X5400-21/2123X22011/2-1/800.25j00-1.5-1/801.25用单纯形法进一步求解，可得：x* = ( 1,1.5,0,0,0,2 )T f* = 16.5灵敏度分析灵敏度分析93 增加一个约束 增加约束一个之后，应把最优解带入新的约束，若满足则最优解不变，否则填入最优单纯形表作为新的一行，引入一个新的非负变量（原约束若是小于等于形式可引入非负松弛变量，否则引入非负人工变量），并通过矩阵行变换把对应基变量的元素变为0，进一步用单纯
41、形法或对偶单纯形法求解。. .灵敏度分析灵敏度分析94例:增加3x1+ 2x215，原最优解不满足这个约束。于是Ci230000CBXBbX1X2X3X4X5X62X141001/4000X5400-21/2103X22011/2-1/8000X6-100-1-1/201j00-1.5-1/800. .灵敏度分析灵敏度分析经对偶单纯形法一步，可得最优解为（3.5,2.25,0,0,3,2)T，最优值为13.7595精品课件精品课件！96精品课件精品课件！97 A A中元素发生变化(只讨论 N 中某一列变化情况） 与增加变量 xn+1 的情况类似，假设 pj 变化 。那么，重新计算出 B B-1pj j = cj - cri ari j 填入最优单纯形表，若 j 0 则最 优解不变；否则，进一步用单纯形法求解。（例子从略）. .灵敏度分析灵敏度分析
