84单纯形法的计算步骤25对，只要将它下面这-列数字与C中同行的数字分别相乘，再用它上端的c，值减去上述乘积之和有(1.23)C, - (cal, + c2a2, +... + cman,) = c,ca.（1.23）就是上一节中讲到的对应变量,的检验数o,．对j=1，…，n，将分别求得的检验数记入表的最下面一行，第二步：进行最优性检验，如果表中所有检验数,≤0，则表中的基可行解就是问题的最优解，计算到此结束，否则转下一步，第三步：从一个基可行解转换到另一个目标函数值更大的基可行解，列出新的单纯形表（1）确定换入基的变量，只要有检验数，>0，对应的变量，就可作为换入基的变量，当有一个以上检验数大于零时，一般从中找出最大一个6x =max to,lo, >01其对应的变量工作为换人基的变量（简称换入变量）（2）确定换出基的变量，根据上一节中确定9的规则，对P列由公式（1.20）计算得到_bib.g=mina>0au确定3，是换出基的变量（简称换出变量）.元素a决定了从一个基本可行解到另一个可行解的转移去向，取名主元素、（3）用换入变量替换基变量中的换出变量，得到一个新的基（P，，，P,-1，P，Pi+1，，Pm）.对应这个基可以找出个新的基本可行解，并相应地可以画出一个新的单纯形表（表1一3），表1-3Cn+...Cic,c1CraraCg基b3,"{!..Xm+++e11..:al,ainb1001-a1k/au.J1t1++：:::::：+ain01/uikai,1br/an0xc*.1三目:::::".0ann6nany0amk/a1ImCm0(cm一z,）002,)"...(.(c,....2/)c, ~3
.26第1章线性规划及单纯形法在这个新的表中的基仍应是单位矩阵，即P应变换成单位向量：为此对表1-2进行下列运算，并将运算结果填入表1-3相应的格中，（a）将主元素所在1行数字除以主元素α，即有(1.24)bi-b,/akai,=ay/au(b）为使P列变换成单位向量，将表1-2中的第1行数字乘上（-t,/α）加到表1一2的第i行数字上，记人表1-3的相应行．即有br.aa(itl)b; = b,akar.au(il)(1.25)ay=a,au（c）表1-3中各检验数的计算：由式（1.23）知：S1c,ark(C-2）=CICaka1=1=1+1Ck1l(c-z)I(1.26)c,akaik在快an1aicau+ckcaiC.a1++1a1= (c, - 2,) -i(c α)a.C1aih=I(1.27)由式（1.27）看出，检验数的计算同样因α变基变量后，其检验数（c一）应为零，故将表1-2中第1行数字乘上（-（c一z）/au）加到该表的检验数上，得表1-3中各变量的检验数第四步：重复第二、三步一直到计算终止，[例 5] 用单纯形法求解线性规划问题max =2r1+3x2s.t.[2xi+2x2≤12164315元215111,2≥0[解]首先在各约束条件上添加松弛变量，将上述问题化为标准形式max2=2x1+3x2+0x3+0r4+0xs
64单纯形法的=12s.t. [2.r1+222+23421=16+34512+xs=15x,≥0(j=1,,5)本例中P3，P4，P,组成一个基，令非基变量，=22=0，即得到一个基可行解为X=（0，0，12，16，15），并据此列出初始单纯形表，见表1-4表1-420300c,→基Csb1ts23Z420001221(1)130(2)0164001x40001015[5](3)as02300(4)C-2,因2>01，故表中有大于零的检验数，故表中的基可行解不是最优解。确定α2为换人基的变量．为确定换出基的变量，将6列数字除以t2列同行数字得71215)=15 =3g=minS2因此rs为换出基的变量，5为主元素，将其加上“［］”号标记。将换人变量无，替换基变量中的工，画出新的单纯形表（见表1-5），表中数字的计算参见式（1.24），（1.25）和（1.26).表1-523000c,基bCe.1233x4ts6[2]0100-2/5(1)t3000(2)01641a401001/5(3)*33x2000(4)23/5c, - 2,为清楚说明计算过程，表1一4中各行分别标以（1）、（2）、（3）、（4），表1-5巾相应行标以（1）、（2）、（3）、（4）首先将主元素行除以主元素，故有（3）=（3）/5，即（3）行数字由
第 1 章 28.线性规划及单纯形法表1－4中第（3）行数字除以主元素5得来，2(3)(1)"= (1)5即表1-5中第（1）行数字为表1-4中第（3）行数字乘（-2/5）加到表1一4的第（1）行得来0+(2)"=(2)(3)类似地有53(3)(4)=(4)5故确定工，为换入基的变量，又因表1-5中仍存在大于零的检验数01，16166=3g=min242故2为主元素，元3为换出基的变量，用，替换3，得到新的单纯形表，见表1-6.表1-600023c,→r4rsCs基b3:1323(1)*0101/2- 1/52311(2)"0-24/5040r401/5(3)0103332(4)"000-1/5-1c,-,表1-6中各行数字的计算过程为(1)=(1)/24(1)(2)"=(2)=20(3)"= (3)+(1)22(1)(4)"=(4)--2表1-6中所有检验数,≤0，表明已找到问题最优解r=3，r2=3，x3=0，α4-4，3s=0，代人目标函数得z*=15单纯形法计算中可能出现以下两种情况：（1）出现两个以上maxl，原则上可任取一个对应的，为换人基的变量：（2）相持．即计算6值出现两个以上相同的最小值
35单纯形法的进一步讨论29当任选其中一个基变量作为换出变量时，则下面表中其他基变量的值将等于0，这种现象称为退化：含一个或多个基变量为零的基可行解称为退化的基可行解：当发生退化现象时，从理论上讲，有可能出现计算过程的循环，有些书中还专门编造了计算过程出现循环的例子，并提出何防止循环的措施，有兴趣的读者可参阅S.1.Gass著LinearProgramming（fifthed.），183～193页幸而对实际问题的线性规划模型，计算中末曾出现过循环现象因此出现退化时，实际上可以随意决定哪一个变量作为换出变量，不必考虑理论上有可能出现循环的后果，5单纯形法的进一步讨论5一1人工变量法前面讨论了线性规划问题的约束条件若为：Bar,≤b (i=m.m)A化成标准形式时在每个不等式左端添加一个松弛变量，由此在约束方程的系数矩阵中包含一个单位矩阵，选这个单位矩阵作为初始基，使得求初始基可行解和建立初始单纯形表都十分方便：当线性规划的约束条件都是等式，而系数矩阵中又不包含有单位矩阵时，往往采用添加人工变量的方法来人为构造一个单位基矩阵，当约束条件是“≥”的情况下，可以先在不等式左端减去一个大于等于零的剩余变量（也可称为松驰变量）化为等式，然后再添加一个人工变量.用单纯形法求解线性规划问题【例6]】(1.28a)max z=-31+x3s.t.+2+<4(1.28b)2 +x2-α3≥1(1.28c)F(1.28d)32+x3=9(1.28e)1，2，30【解】将此问题化成标准形式，在约束条件（1.28b）中添加松弛变量、（1.28c）中添加剩余变量后得maxz=-3ri+a3+0x4+0rs