发布时间 : 星期四 文章优化设计-2更新完毕开始阅读7f7ffcdcdd88d0d233d46ad8
?a110??x1??b1???? ???a??211??x5??b2?选a11为消元主元，结果为
b1????10??x1??a11? ?01??x???b1???5??b2?a21??a11???从而得
x1?b1,a11x5?b2?a21b1 (3.4) a11用x1替换x5的约束方程为
?1a11??x4??b1??0a??x???b? (3.5)
21??1???2?选a21为消元主元，结果为
b2??b?a?10??x4??111a21?? (3.6) ?01??x???b2????1????a21??从而得
x4?b1?a11b2,a21x1?b2 (3.7) a21观察式（3.4）和式（3.7），注意到当
?b??5x1?min?i??min??1?ai1?3?b23??3 (3.8) ??1?a211时，可得到基本可行解，否则x1的取值不能使所有基本变量的取值成为基本可行解，如式3.4。出基变量与式3.8有着必然联系。式3.8中最小比值对应的右端项元素或系数行下标对应的基本变量就是出基变量，且比值分母系数下标就是进基变量对应的主消元素。验证式3.3可知，变量x5为被替换出的变量，与计算机结果一致。由此可见，目标函数与约束条件配合，约束方程求解完成后，将基本变量结果代入目标函数中，通过比较非基本变量系数大小决定进基变量（此时认为非基本变量取值不为0）。对求最大值问题，系数较大的非基本变量为进基变量；对求最小值问题，系数较小的非基本变量为进基变量。确定了进基变量后，则计算右端项与进基变量在约束方程中列系数向量对应元素的比值，比值小者的行下标对应的基本变量为出基变量。
将式3.1中的约束矩阵A按列表示： A=[ p1 p2 … pn]
pi (i=1,2, …,n)是m×1的向量，pi的分量是各约束方程中与设计变量xi对应的系数。设矩阵A的秩为m将设计变量x分解为基本变量和非基本变量，即x=[ xE xN ]T，相应地，系数矩
阵A也分解为两部分，一部分为基矩阵，用E表示；另一部分为非基矩阵，用N表示。于是A=[ E N ]，E=[ p1 p2 … pm]，N=[ pm+1 pm+2 … pn]。式3.1中的约束条件重新表示为
?E即
?x?N??E??b （3.9） ?xN?ExE?NxN?b
上式两端左乘E-1并移项，得
xE?E?1b?E?1NxN （3.10）
xN的分量为自由变量，它们取不同的值，就会得到方程组的不同解。特别地，如果令xN=0，则得到
?xE??E?1b?x?????? （3.11）
?xN??0?称解x为方程组Ax=b的一个基本解。如果E-1b≥0，则称
?xE??E?1b?x??????
x?N??0?为满足约束条件的基本可行解（非负的基本解）。 2 基本可行解的转换
基本可行解的转换就是得到某组基本可行解后，如何进一步改进获得更好的解，最终达到最优基本可行解。从上节的分析可知，获得改进的解是在满足约束条件的前提下使目标函数值增加（对于最大值问题）或使目标函数值减少（对于最小值问题）的解。设已经获得一组基本可行解：
x(0)?E?1b????
0??其对应的目标函数值记为f0。设x???xE??是另一组基本可行解，将其代入目标函数中，得 x?N?Tf?cTx?cE?xE?cTN???xN?TT?1?1TT?1TT?1 ?cExE?cTNxN?cE(Eb?ENxN)?cNxN?cEEb?(cN?cEEN)xN （3.12）
???f0?j?m?1?(cnj?cEpj)xj?f0?TE?1j?m?1?(cnj?zj)xj如果每次将一个非基本变量转换为基本变量，并假定目标函数的最大值，那么由式3.12可知，选择求和项中系数cj?zj>0最大者对应的非基本变量进入基本变量，当该变量取正值时，可使目标函数增加最多。如果所有非基本变量的系数cj?zj不再有正值，则说明非基
本变量的进基运算不会再使目标函数值增加，此时就终止计算，输出最优结果。非基本变量转换为基本变量后，则要将上一轮迭代中的一个基本变量转换为非基本变量，判断出基本变量表的条件由约束方程的消元计算格式给出。
设xk为进基变量，不失一般性，认为xk替换xr，在约束方程中相应地用pk代替pr，
?kpk??a1?k?ank??T,pr??a1?ra2?r?anr??,新的基矩阵为E（1）a2。为表示清楚，
T(k)pk将标记为pr(k)，其元素相应地表示为pr表示为
?k?a1?(k)?ka2(k)??ank(k)T?。因此基矩阵E
（1）
E(1)?p1?p2?pr(k)?pm??r(k)?10?a1??(rk)?01?a2???????(k)????arr??????(k)??00?amr?1?x?E?E(1)b (3.13)
?0???0??? ??0?????1??变量xk由0变为正值后，新方程组的解为
其中，基矩阵E（1）的逆矩阵为
??r(k)a1?10??a?(k)rr??(rk)?01??a2??(k)arr?????1E(1)???????1??(k)arr??????(k)?00??amr??(k)arr???0???0????? (3.14) ?0??????1???初始基矩阵为单位矩阵，在基矩阵中用pk将标记为pr，就是将pk放在第r列的位置上。对
于式3.14所示矩阵，其逆矩阵只有第r列的元素发生变化，对角线上的元素为相应元素的倒数，该列上其他元素等于原来的元素取反再除以对角线上的元素。式3.13的解为
xr(k)?br?（3.15） ?(k)arrx(k)i?(k)br?air?(k)xr(k),i?1,2,?,m,i?r（3.16） ?bi??(k)?bi??air?arr由于设计变量非负，并假设设计变量在约束方程中的系数和右端项元素均大于0，因此xr(k)
≥0自然满足；而式3.16中的变量非负意味着
?(k)br?airbi??(k)?0
?arr即
bi?br???0（3.17） (k)(k)??airarr当
??xk??bi??br?(k)??min,a?0?(k)ir?（3.18） (k)??arr?air?时，则能保证用xk替换xr，使所有基本变量非负。在线性规划中，通常称
?j?cj?zj（3.19）
j为判别数或检验数。对极小化问题，进基变量xk的下标与?k?ck?zk?min(cj?zj)项的
下标k对应，非基本变量xk的引入使目标函数f?f0?j?m?1??njxj增加最多（最大值问题），
或减少最多（最小值问题）。出基变量xEr的下标与???b??br???0?项的下标?min?i,aik“r”
??arka?ik?对应。式3.18和式3.19是单纯形法求解线性规划问题的重要判别式和检验规则。
3 单纯形法的计算步骤
例3.2 用单纯形法求下述问题的最优解：
minz??6x1?3x2?2x3s.t.2x1?x2?x3?6x1?x3?2x1,x2,x3?0解：
首先引入松弛变量x4，x5，把数学模型化为标准形式：
minz??6x1?3x2?2x3?0x4?0x5s.t.2x1?x2?x3?x4?0x5?6x1?0x2?x3?0x4?x5?2x1,x2,x3,x4,x5?0引入松弛变量后，变量总数n=5，约束方程数m=2（不含变量大于等于0的约束），因此有n-m=3个非基本变量，并令其为0进行求解。一个简单的做法就是选松弛变量x4，x5为基本变量，因此其系数列向量为单位基向量E??p4和非基本变量表示，得 x4=6-2 x1- x2- x3
?10?p5????。将基本向量用在端列向量
01??