第2章 对偶理论和灵敏度分析-第2节-清华大学运筹学第三版课件

运筹学（第三版）《运筹学》教材编写组编清华大学出版社第2章对偶理论和灵敏度分析第2节改进单纯形法钱颂迪制作第2章对偶理论和灵敏度分析第2节改进单纯形法求解线性规划问题的关键是计算•以下介绍一种比较简便的计算方法1B设m•m系数矩阵A，求其逆矩阵mmmmmmaaaaaaaaaA212222111211可以先从第1列开始121111maaaP)(a/aa/aa/aaaPmm111111121111112111主元素以为主元素,进行变换11a然后构造含有（1）列，而其他列都是单位列的矩阵110011111121111a/aa/aa/Em可得到：)(mm)(m)(m)()(m)(aaaaaaAE;PE11212122111121110010011121122211211121aaaaaaaa而后以第2列的为主元素，进行变换)(a/aa/a/aP)()(m)()()()(2112212122122112212)(a122然后构造含有（2）列，而其他列都是单位列的矩阵1001001122121221221122)()(m)()()(a/aa/a/aE可得到)(mm)(m)(m)(m)()(aaaaaaAEE222212322321312001001重复以上的步骤，直到获得112111AAEEEm•求单纯形表的基矩阵的逆矩阵也可以用这方法以例1为例进行计算1241648200032524132154321xxxxxxxxxxxxzmax第1步：确定初始基，初始基变量;确定换入，换出变量。（1）确定初始基和初始基变量：54354300111xxxX;P,P,PBB（2）计算非基变量的检验数，确定换入变量。换入变量对应注意：212100103240204110001000100032000x,x,),,(,)P,PN(NBCCBNN(3)确定换出变量计算：表示选择0的元素5341201628021021010x,,minPBPBbBminii对应（4）基变换计算将新的基单位矩阵。计算：243P,P,P410121141021402112//E//P；构造主元素4101211111410121110111////BEB（5）计算非基变量的系数矩阵410214114141012111411111////NBN（6）计算RHS316212168410121111//bB第1步计算结束后的结果),(),,,(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB023001111512432431价值系数非基变量基变量基第2步重复第1步的计算步骤从新的基，基变量开始。计算非基变量的检验数，确定换入变量。换入变量对应注意：515111114321000414100010210130002111x,x/,//),,(,)P,PN(NBCCBNN(3)确定换出变量计算：表示选择0的元素120341612011111111x,,minPBPBbBminii对应410021421014100010210110001400110001400104104111212212412////BEBEPP,P,PB2主元素计算RHS382121684100214210112//bB第2步计算结束后的结果),(),,,(C,CC;x,xX;x,x,xX;P,P,PBNBTNTB003022222532412412价值系数非基变量基变量基第3步从新的基，基变量开始,重复第1步的计算步骤.计算非基变量检验数，检查检验数，确定换入变量换入变量正检验数对应注意：535322124121000014100314210130200222x,x/,//),,(,)P,PN(NBCCBNN(3)确定换出变量计算：表示选择0的进行计算4441328212051251212x/,,/minPBPBbBminii对应新的基主元素的系数向量是换入变量412211004100214210151252513////PBx;P,P,PB计算B逆矩阵18100210041181214133///E///构造08121121204104100214210118100210041112313/////////BEB计算非基变量的检验数已无正检验数注意：8123010001081211212041030200433313333/,/////),,(,P,PNNBCCBNN最优解24412812116212841013251////bBxxxX*目标函数的值1424430213,,bBCzB*