20.第1章线性规划及单纯形法(1.11)8P1+02P2+..+omPm=0（1.11）式乘上一个不为零的数μ得：(1.12)uo,P+ud2P2++oPm=0(1.10)+(1.12)得:(z/+uo,)P+(r2+μo2)P2++(rm+uom)Pm=b(1.10) -(1.12)得:(xl =μo,)Pi + (r2 -μo2)P2 + +(rm-μom)Pm = bX1)=[(1+uo1),(2+μo2),,(m+μom),0,",0]Ax(2)= [(x1-μo1), (x2-μo2), ,(m-μom), 0, , 0]又u可以这样来选取，使得对所有i=1，…，m有x, ±μo,≥0x(1)+x(2)，即×不是可行域的顶点。由此X(1)EC,X(2)EC,又X=22（2）X不是可行域的顶点一X不是基可行解，不失一般性，设X=（1，2，，，0，，0）不是可行域的顶点，因而可以找到可行域内另外两个不同点Y和Z，有X=aY+（1"α）Z(0<α<1)，或可写为：(0<a<l,j=l,, n)a,=ay+(l-a),因α>0，1-a>0，故当,=0时，必有=,=0P, = 2P, = b因有E2p, = 2P,= b(1.13)故有-2p,r,pe, = b(1.14)=-1a(y, ~ z,)P, = 0式（1.13）－式（1.14)得因（y，-z）不全为零，故Pi，，P，线性相关，即X不是基可行解定理3若线性规划问题有最优解，一定存在一个基可行解是最优解【证】设x(0）=（,,…，）是线性规划的一个最优解，z=Cx(0）=c°是目标函数的最大值.若x(0)不是基可行解，由定理2知x(0）不是项点，Cc一定能在可行域内找到通过×(0）的直线上的另外两个点（x(0）+μ）≥0和（x(0）-u8）≥0.将这两个点代人目标函数有C(x+uo) =Cx+CuoC(xo-μo) =cxo-Cus因Cx(0）为目标函数的最大值，故有
3单纯形法原理21Cx(0)≥CX(0) + CuCx(0)≥CX(0)-Cug由此Cμo=0，即有C（X(0)+μo）=Cx(0）C（x0)-）如果（x(0）+u6）或（x(0）一us）仍不是基可行解，按上面的方法继续做下去，最后一定可以找到一个基可行解，其目标函数值等于Cx(0），间题得证.3一3确定初始基可行解因线性规划问题如果存在最优解，一定可以在基可行解中找到：因此单纯形法的基本思路是：先找到一个初始基可行解，如果不是最优解，设法转换到另一个基可行解，并使目标函数值不断增大，一直到找到最优解为止，当线性规划的约束条件全部为“”时，可按下述方法比较方便地寻找出初始基可行解。设给定线性规划问题max2ay,≤b,(i = 1,",m)S.1(Gj = 1,",n)=0在第i个约束条件上加上松弛变量s（i=1，，m），化为标准形式7Pt+ogmaxzys1↓ =1(i= l,,m)s.t.Zut,+ra=b,1(j=l,, n)a≥0其约束方程组的系数矩阵为：010[a11a12ain01.0a21a22u2n::：::001Lam1amnam2，Psm），只要以这个单位由于这个系数矩阵中含一个单位矩阵（Pl，矩阵作为基，就可以立即解出基变量值。=b，（i=1，…，m），因为有b0（对i=1，"，m），由此x=（0，，0，b1，，bm）T就是一个基可行解，当线性规划中约束条件为“”或“”时，化为标准形式后，一般约束条件的系数矩阵中不包含有单位矩阵，这时为能方便地找出一个初始的基可行
·22第1章乡线性规划及单纯形法解，可添加人工变量来人为地构造一个单位矩阵作为基，称做人工基：这种方法将在本章第五节中讨论从初始基可行解转换为另一基可行解3-4设初始基可行解为x(0)=（r，，，)T，其中非零坐标有m个不失一般性，假定前㎡个坐标为非零，即(n-m)个X(0)= (ri, -2, , am, 0, ., 0)TZpr! =b因x(0)EC,故有(1.15)写出方程组（1.15）的系数矩阵的增广矩阵，上面讲到包括用构造人工基的方法，总可以使基矩阵是单位矩阵形式，因此有增广矩阵P1 P2Pm +1..P,Pm...P.b.00[1b1a1.mt1al,ain"?010-62a2,m+1a21a2n:.*:::..+P001rammα.因P1，，P是一个基，其他向量P,可用这个基的线性组合来表示，有5P,a.Pm或(1.16)P.aP=0将（1.16）式乘上一个正的数8>0得：B(P, - Zap.)= 0(1.17)（1.15）+（1.17）式并经过整理后有Z(r! - la,)P: + OP, = b(1.18)由(1.18)式找到满足约束方程组么P,,=b 的另个点x(1),有X(1)- (ra,,.., Bam,0, , 8,, 0)其中6是x(1)的第j个坐标的值，要使X(1)是一个基可行解，因6>0故应对所有i=1，，m存在r! -Ba,≥0(1.19)且这m个不等式中至少有一个等号成立.因为当a≤0时，（1.19）式显然成
23-$4单纯形法的计算步骤立，故可令xi(1.20)a=min?0auatlau(i=l)-0!-Ba.由式（1.20）得≥0(i)这样X(1)中的正的分量最多有m个，容易证明m个向量Pi，，Pl-1,PI+1，，Pm，P，线性无关，故只需按式（1.20）来确定8的值，XU)就是一个新的基可行解3一 5 最优性检验和解的判别将基可行解X<0）和X1)分别代入目标函数得Zer!2(0)=E2(1) e,(r! - Ba,) + 0c,1-11:c+(c. -Sca,) = (2(0) + 8(c(1.21)cay.=-12ca)>0,就有1>(0）（1.21)式中因9>0为给定，所以只要有（c，一1=1c.a,)通常简写为(c,～z,）或,，它是对线性规划问题的解进行最优性=检验的标志（1）当所有的,≤0时，表明现有顶点（基可行解）的目标函数值比起相邻各顶点（基可行解）的目标函数值都大，现有顶点对应的基可行解即为最优解，(2)当所有的,≤0，又对某个非基变量,有c,一2,=0，且按公式（1.20）可以找到>0，这表明可以找到另一顶点（基可行解）目标函数值也达到最大，由于该两点连线上的点也属可行域内的点，且目标函数值相等，即该线性规划问题有无穷多最优解、(3）如果存在某个,>0，又P，向量的所有分量a，≤0，由公式（1.19）对任意8>0，恒有（°-6a）≥0.因A取值可无限增大，由（1.21）式目标函数值也可无限增大，这时线性规划问题存在无界解，对线性规划无可行解的判别将在后面第五节中讲述84单纯形法的计算步骤根据上节讲述的原理，单纯形法的计算步骤可以归结如下：
·24,第1章线性规划及单纯形法第一步：求出线性规划的初始基可行解，列出初始单纯形表对非标准形式的线性规划问题首先要化戏标准形式，由于我们总可以设法使约束方程的系数矩阵中包含一个单位矩阵，不妨设这个单位矩阵是（Pt"，P），以此作为基即可求得问题的一个初始基木可行解X一（6l，，bm，0, , 0).要检验这个初始基可行解是否最优，需要将其目标函数值与可行域中相邻顶点的目标函数值比较为了计算上的方便和规格化，对单纯形法计算设计了一种专门表格，称为单纯形表（见表一2），迭代计算中每找出个新的基本可行解时，就要重新画一张单纯形表，含初始基可行解的单纯形表称初始单纯形表，含最优解的单纯形表称最终单纯形表在单纯形表的第2～3列列出某个基可行解中的基变量及它们的取值，接下来列出问题中的所有变量：在基变量下面各列数字分别是对应的基向量数字。表1一2中变Z1，，7m下面各列组成的单位矩阵就是初始基可行解对应的基，表1-2Ca,c1ConS,Ca基2,Xnbam21.bi01...alnalC111b200a2n42,C2-12:：:::..:01ammsbmCm1Sca00c, - z,-每个非基变量工，下面的数字，是该变最在约束方程的系数向量P，表达为基向量线性组合时的系数：因为有[a1,P,=:Lam又表1-2中基向量P，，Pm都是单位向量，故有(1.22)P,=a1,P+a2,P2+..+amPm由此初始单纯形表中，下面这一列数字恰好就是P，中各元素的值，表1-2最上端的一行数是各变量的目标函数中的系数值，最左端一列数是与各基变量对应的目标函数中的系数值Cz·