运筹学第二章线性规划

第二章线性规划教学目的和要求：目的：使学生具备线性规划的基本知识以及应用线性规划的基本能力。要求：理解线性规划概念，标准型，解的概念，基本定理；掌握单纯形法，人工变量法，了解图解法。重点：线性规划标准型，解的概念，单纯形法，人工变量法。难点：线性规划基本定理，单纯形法。教学方法：讲授法，习题法。学时分配：12学时作业安排：见教材P*解：设产品A、解：设产品A、B、C产量分别为X,X,X件,Z表示利润，要求总利润最大，即求Z=4.5X+5X+7X32另外对甲、乙、丙、丁设备需满足2X1+2X2+4X3^8002，3满足线性规划是运筹学的一个重要分支。1939年苏联科学家康托罗维奇提出了生产组织和计划中的线性规划模型。1947年美国学者丹捷格(GeorgeB.Dantzig)提出了求解一般线性规划问题的方法。此后，线性规划理论日趋成熟，应用也日益广泛和深入。第一节线性规划问题一、问题的提出在企业的生产经营活动中经常会面临这样两类问题：一是如何合理地利用有限的人力、物力、财力等资源，取得最佳的经济效果；二是在取得一定的经济效果的前提下，如何合理安排使用人力、物力、财力等资源，使花费的成本最低。例1.生产计划问题某工厂利用甲、乙、丙、丁四种设备生产A、B、C三种产品，具体数据如下表所示。A、B、C单位产品的利润分别是4.5、5、7(百元)。问如何安排生产计划，才能使所获总利润最大？产品设备、\^ABC设备可供工时(h)甲224800乙123650丙423850丁242700单位利润4.557销地产地B1B2♦♦♦Bn产量A1C11C12♦♦♦C1na1A2C21C22♦♦♦C2na2♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦♦AmCm1Cm2♦♦♦Cmnam销量b1b2♦♦♦bnmn£a.=£bi=11i=1j解：设Xjj（i=1,2,...,m;j=1,2,...,n）表示由土到B.的物资运输量，则总运费为mn，另外，对Z=££C..X..i=1jmn，另外，对Z=££C..X..i=1j=1ijijA应有n，i=1,2,...,m对B，应有

i£xij=aij同时，运输量应非负，故X可，以上问题数学模型为：极小化(i=1,2,...,m;j=1,2,...,n)满足mnz=££C..X..满足i=1j=1ijijn，i=1,2,...,m£x..=a.j=1ijim,j=1,2,...,n£x..=b.i=1ijj七Xij可（i=1,2,...,m;j=1,2,...,n）例3.配料问题要配制一种面包，每只面包要求含甲、乙、丙3种营养成分至少各为20、24、30单位。现有4种原料可供选用，下表给出了每10g原料所含各种营养成分的单位数。试确定每种原料各取多少，才能使面包的配制成本最低？原料营养种ABCD甲121/21/4乙3121/2丙3124价格（分/10g）10153025解：先假设配制一只面包，数量多只需扩大相应倍数即可。由观察可知，原料上还是价格上都优于C，故C不选用，设A、B、D各取X,^,^个10g。则可得数学模型如下：极小化Z=10X+15X+25X满足12rx+2Xrx+2X+(1/4)X沱203X1+X2+(1/2)X4沱243X1+X2+4X4沱30匚X,,X,,X卷以上几个问题各有不同，但其数学模型有共同之处：它们都是要求一组变量（称为决策变量）X,X，…，X，这组变量全部或者其中一部分具有非负要求，且满足一系列线性等式或不等式n12,i=1,2,n...,m,使一个用线性式表示的目标（称为目标函£aijXj=（-，-）%数)Z=C1X1+C2X2+・・・+CnXn达到极值，这类问题称为线性规划。一般而言，线性规划数学模型为：极大化(极小化)Z=CX+CX+・・・+CX…一般而言，线性规划数学模型为：极大化(极小化)Z=CX+CX+・・・+CX…n,i=1,2,2...,m..^(②1a.x.(,)b.j1ijJ1X>0全部或部分j,j=1,2,…,n・••…①式为目标函数，②为约束条件，③为非负要求；式①②全为线性式，否则称为非线性规划。满足②③的一组变量X1，X2,…，X」称为线性规划的可行解，由所有可行解组成的集合称为可行解集合或可行域，若X=(X1，X：…，X)丁使目标函数达到极值的可行解，称为最优解。为了表述方便及深入研究线性规划，线性规划底型可表三为矩阵和向量形式：极大化(极小化)Z=CX,满足AX=(wW)b,X>0;满足PX+PX+・・・+PXCn)，X=(X1•••a1n・a2n或极大化(极小化)Z=CX其中C=(C1，C2，a11a21A=a12a22=(Pi，22nnX2,…，Xn)TP2,…，Pn)M习b,b=(b,b,X#•••,DT，P=(a,a,・・・a)Tj=1,2,…，nmj1j2jmj第二节线性规划的图解法线性规划的图解法是一种解析几何方法，它简单直观，有助于理解其基本概念和求解一般原理。例4.求解线性规划极大化Z=600X1+700X2满足］X1+2X2M60X1+X2M2043X1+X2<300X2<60'X1，X2>0解：(1在平面上建立直角坐标系O-X1X2,X1为横轴，X2为纵轴。(2戕出可行域，由解析几何知识可知，X1+2X2M60代表直线X1+2X2=160左下半平面，X1+X2^20代表直线X1+X2=120左下半平面,3X1+X2<300代表直线3X1+X2=300左下半平面，X2三60代表直线X2=60下半平面，X1>0,X2>0表示第一象限，以上区域的公共部分D即为可行域。(3)在可行域中找最优解，将Z视为参数，则Z=600X1+700X2可表示为以Z为参数的一族平行线，X2=(-600/700)X+(Z/700)其中同一条直线上任何一点都具有相同的Z值，故称之为等值线。当Z值由小变大时，等值线沿其法线方向垂直方向)向右上方移动，当移动到过X*点时，Z值最大，因为若Z值再增大，则等值线与可行域无交点，不满足约束条件。初始等值线可选择一个适宜的Z值，与可行域相交即可，比如Z=42000,故本例最优解为X*=(80,40t,最优值为Z*=76000例5:用图解法求解下列线性规划例5:用图解法求解下列线性规划(1极大化Z=2X/A满足［X1-X2>1J-X+孜<0〔X…（2）极小化Z=2X1+2X2满足X-X沱1<-X+12X司,x1,X2^0解：这两个问题约束条件相同，其可行域如图2-3所示，是个无界集，从图2-3中可看出无论Z多大，Z=2%+2X2总与D相交，故Z可无限增大，则（1）无最优解但有可行解，当Z减少时目标函数等值线过X*例6：求解线性规划极大化Z=X+X2满足]X+X11«x+x2wx1，X2g解:如图2-4所示，可行域为空集故不存在可行解也无最优解。例7：在例4中将目标函数改为极大化Z=600X1+600X2其它不变，则极大化Z=600X1+600X2与X]+X2=120平衡,Z由0变大时，等值线最后将与可行域D的边X*X（3）（X1+X2=120所形成的边）重合,故线段X*X⑶上的每一点都是最优解，（图2-5）综上可知，两个变量的线性规划有以下特点：1）可行域可能是空集，也可能是有界凸多边形，或无界凸区域；2）当D非空时，D至少有一个极点（顶点）；3）当D非空有界时，线性规划一定有最优解，且最优解必在D的一个极点上得到；4）当线性规划的最优解不唯一时，那么必有无穷多个最优解；5）如果D无界，则线性规划可能无最优解（例5（1））也可能有最优解（例5（2））.以上结论对于nW也成立，下节将论证。第三节线性规划的标准型和解线性规划的图解法虽直观简便，但对于n^2时就无能为力。下面介绍一种代数方法一单纯形法，为了以后便于讨论，先研究一下线性规划数学模型的标准型和解的基本性质。对于一个具体的线性规划应先化为标准型再用单纯形法求解。一、线性规划的标准型规定线性规划的标准型为：

极大化Z=CX+CX+...+CX(2-10)1122nn满足(aX+aX+...+aX=b1111221nn1aX+aX+.+aX=b2112222nn2aX+aX+.+aX=b(2-11)m11m22mnnm〔X可j=1,2,...,n(2-12)矩阵形式:MaxZ=CX,满足AX=b,X^0.向量形式:MinZ=CX，满足P1X1+P2X2+.+PnXn=b,X可二、化标准型若目标函数为“MinZ=CX”，因为MinZ=-Max(-Z),令z'=-Z=(-C)X，则目标函数变为Maxz'=(-C)X,Z'值的相反数就是所求目标函数值。若有b<0(1目盆)则将此约束条件两边同乘(-1),便得(-b)>0。若第ki个约束条件为aX+aX+...+aX斗则在左端加入一个非负松驰变量X,k11k22knnkn+k使之成为aX+aX+...+aX+X=bk11k22knnn+kk若第s个约束条件为aX+aX+...+aX斗则在左端减去一个非负剩余变量X,s11s22snnsn+s使之成为aX+aX+...+aX-X=bs11s22snnn+ss若决策变量X司，则用X'=-X代入目标函数和约束条件中，则X'^0,jjjj若决策变量X无非负要求，则令x=x'-x〃,x',x"Z0ssssss代入线性规划模型中，则变量都有了非负要求。例8.将线性规划化为标准型MinZ=5X-2X+3X-6X(X+2X+3x+4女M18412342X+X+X+2X沱103X1-X-32X+X=-6X],1X；X4%,4X3无非负要求.解:1)令Z'=-Z=-5X1+2X2-3X3+6X4使目标函数成为MaxZ=-5X1+2X2-3X3+6X4第一个约束条件左端加入松驰变量X5；3)第二个约束条件左端减去剩余变量X64)第三个约束条件两边同乘(-1)；4)第三个约束条件两边同乘(-1)；5)令x=x:—x:":,x；Z033333则线性规划的标准型为：MaxZ'=-5X1+2X2-3X3'+3X3''+6X4+0X5+0X6{Xi+2X2+3X3‘-3X3''+4X4+X52X1+X2+X3'-X3''+2X4-3X1+X2+2X3'-2X3''-X4X1，X2,X3',X3'',X4,X5,三、线性规划解的基本概念=18-X6=10=6X6可,111211121maa......a21222maa......am1m2mB=(P1，P2,……Pm)=线性规划标准型即式(2-10)---(2-12)形式，且m<n,R(A)=m.基本解求解线性规划，实质上是求解具有特殊要求(变量非负及目标函数值达到极大)的线性方程组，因为m<n,R(A)=m.故约束方程组有无穷多解。设B是A中一个非奇异的m阶子阵(即|B怙0)则称B是线性规划的一个基。不妨设B是由A的前m个向量组成，即P1,P2,Pm线性无关，称Pj(j=1,2,m)为基向量，与基向量Pj相应的变量Xj称为基变量，其它的向量和变量称为非基向量和非基变量。将约束方程组表示为ai1X1+ai2X2+.+a2mXm=bi-aim+1Xm+1-.-ainXn,i=1,2,...m.

令非基变量Xm+1=•••=Xn=0.则由P]Xi+P2X2+...+PmXm=b得唯一一组解X.=b.,i=1,2,…，mii因此X=(b,b，…,b,0,0,...,0)T为约束方程组的一个解,X称为对应基B的基本解。在基本解X中,非零分量最多为m个，线性规划的每个基都对应一个基本解,A的非奇异的令非基变量Xm+1=•••=Xn=0.则由P]Xi+P2X2+...+PmXm=b得唯一一组解n!Cm=个nm!(n-m)!基可彳丁解满足非负要求的基本解，即属于可行域中的基本解，称为线性规划的基可行解，基本可行解最多有Cm个。n设B=(Pi,P2,Pm)是一个基，A=(BN),X=(XbXn)T,N=(Pm+1,Pm+2，.Pm),Xn=(Xm+1,Xm+2,-Xm)T,Xb=(X],X2,.Xm)T，则(2-11)式可化为AX=(BN)(XbXn)T=BXB+NXN=b，XB=B-1b-B-1NXN，令XN=0,贝0XB=B-1b，若XB^0，则X=(Xb，0)T=(B-1b，0)T是线性规划(相应于基B)的基可行解，B称为可行基。最优解:使目标函数值Z达到极值的可行解称为最优解。四、线性规划的基本定理它是从理论上深入论证解的基本性质基本概念凸集：设S是n维欧氏空间En中的一个集合(即SuEn)若对VX⑴,X(2)孑及V实数入(0£三1),都有入X(1)+(1-入)X(2)£S,则S称为凸集。凸组合：设X⑴，X⑵，...X(K)是En的K个点，实数入*,...入满足入目,i=1,2,...,k.A1,则称TOC\o"1-5"\h\z12kii(1)(2)(K)(1)(2)(K)(1)(2)(K)(1)(2)(K)人X十人X+..•十人X为X,X,...X的凸组合，若X=人X十人X+..•十人X则称、X是X,X,...X的凸组合。2k12k⑶极点：对于凸集S,X£S，若不存在这样的两个点X⑴,X(2)£S,(X⑴以⑵,X(1)^X,X(2)^X)使X可以表示成X⑴和X(2)的凸组合，即X=X⑴+(1顷)X(2),0<X<1，则X是S的一个极点。基本定理定理1.线性规划可行域D是凸集.推论.线性规划最优解集合是凸集.定理2.X是线性规划的可行解，它是基可行解。X的非0分量对应的系数列向量线性无关.定理3.线性规划的基可行解对应可行域D的极点，即可行解X是基可行解。X是可行域D的极点.定理4.若线性规划有可行解，则一定有基可行解(即若线性规划可行域非空，则D一定有极点).定理5.若线性规划有最优解，则一定有最优基可行解.定理6.若线性规划可行域D有界，则最优解一定可以在D的极点上得到.推论：若线性规划的最优解可在D的两个极点上得到，则线性规划必有无穷多个最优解.第四节单纯形法一、概述单纯形法是求解线性规划的基本方法(代数方法),根据线性规划的基本定理可知，若线性规划有最优解，一定可在基可行解中得到，单纯形法的基本思想就是从一个基本可行解开始，通过更换基变量，转换到另一个基可行解，同时使目标函数的值逐步增大，当目标函数达到最大值时，问题就得到了最优解。例10.求解线性规划MaxZ=10X1+15X2+X3+3X4+2X5(2-20)满足r-X1+2X2+X3=181X1+X2+X4=2...(2-21)X1+X5=15〔Xj可,j=1,2,3,4,5...(2-22)解：问题已是标准型[-1210018'1.确定初始基可行解(Ab)=[1101024]〔1000115JR(A)=3,m=3,n=5,B0=(P3，P4，P5)是A的一个基，相应的基变量为X3，X4，X5，非基变量为X]，X2基向量为P3,P4,P5，非基向量为P1，P2.用非基变量表示基变量，约束条件(2-21)可变为：X3=18-(-X1)-2X2X4=24-Xi-X2(2-23)X5=15-Xi将(2-23)代入(2-20)得Z=120-(-6)X1-(-10)X2...(2-24)令X1=X2=0，则X(0)=(0,0,18,24,15)t为初始基可行解，对应的目标函数值为Z(0)=120.检验由(2-24)Z=120-(-6)X1-(-10)X2可看出，若让X］或X2变为基变量，即取值由0变为正数，则Z将增大，故X(0)不是最优解，Z(0)不是最优值。基可行解转换确定进基变量：通过比较X1，X2的系数可知选X2为进基变量，Z增加更快，称其为进基变量；确定出基变量：因为基变量只能有m=3个，故须将原来的基变量换出一个为非基变量，称其为出基变量，X1仍为非基变量，令X1=0，则(2-23)变为：|X3=18-2X2X4=24-X2(2-25)LX5=15为了使所有变量保持非负，则18-2X2^0,24-X2^0故可得X?M9，取X2=9使Z尽可能增大，此时X3=0即X3为出基变量，因此新基B1=(P2,P4,P5)，相应的基变量为X2，X4,X5.基可行解转换计算(迭代)由(2-23)得『X2=9-(-1/2)X1-(1/2)X3'X4=15-(3/2)X1+(1/2)X3......(2-26)'X5=15-X1以(2-26)代入(2-24)得Z=210-(-11)X1-5X3...(2-27)令X1=X3=0,则X(1)=(0,9,0,15,15)T,Z(1)=210.重复2-3步骤直至最优解从(2-27)可看出将X1为进基变量,Z将增大，令X3=0,则(2-26)变为］X2=9-(-1/2)X1X4=15-(3/2)X1X5=15-X1且9-(-1/2)X1^0,15-(3/2)X1^0,15-X1当)故可得X1三10,取X］=10，则X4=0,X4为出基变量，因此新基为B2=(P2,P1,P5),相应的基变量为X2,X1,X5.由(2-26)得］X2=14-(1/3)X3-(1/3)X4，X1=10-(-1/3)X3-(2/3)X4...(2-28)LX5=5-(1/3)X3-(-2/3)X4将(2-28)代入(2-27)得Z=320-(4/3)X3-(22/3)X4...(2-29)令X3=X4=0,则X(2)=(10,14,0,0,5)T,Z⑵=320.从(2-29)可看出，此时X(2)为最优解，即X*=X(2)，最优值为Z*=Z⑵单纯形法的主要步骤：找一个初始基可行解(要求标准型A中有R(A)=m阶单位子阵)。检验基可行解是否最优(看Z能否增大)。若不是最优解，进行基可行解的更换，进基变量应使Z增加最快，出基变量选择原则是保持所有变量要非负，进行基可行解的转换计算，这种计算称为迭代。重复2)-3)直至最优解。二、单纯形法(针对一般线性规划标准型)的求解步骤：初始基可行解的确定.为了确定初始基可行解，要先找出初始可行基，方法如下：(1)若从标准型中，可直接从A中找到m个线性无关的单位列向量，即m阶单位矩阵，不妨设为B0=(P1,P2,Pm)，N0=(Pm+1，Pm+2,Pn)即得一可行基B0，即线性规划标准型为：MaxZ=寸CX(2-30)jj'j=1X1+a1m+1m+amm+1Xm+1+・••m+amm+1Xm+1+・••+amnXn=bmX2+a2m+1Xm+1+・•・+a2nXn=b2•••(2-31)

Xj寻j=1,2,.,n(2-32)bi可，(i=1,2,...,m)则初始基可行解为X(0)=(b1，b2,...bm，O...O)T,对应的目标函数值为Z0=CBXB+CNXN=CBb.(2)若从A中找不到m个线性无关的单位列向量，则采用人工变量法(见第五节).最优性检验得到初始基可行解后，要检验一下是否是最优解：如果是，则停止迭代(基变量的转换计算)；若不是，则继续迭代，…但每次迭代后都要检验一下是否是最优解。因此需要建立一个检验准则。假设一般情况下,经过迭代后(基B0变换到UB1)约束条件(2-31)变为(把基变量仍然排在前m项)：X.=bi-/ai.X.,i=1,2,...,m...(2-33)(用非基变量表示基变量)将(2-33)代入(2-30)得j=m+1mnm_Z=XC.b:-£(XC.a:.-C,)X.•••(2-34),令z=£Cb',◎=£Ca'一C,i=111.=m+1i=11ijjj1iij.ijji=1i=1则Z=Z-£!oX.……(2-35)在(2-33)中令非基变量等于0,得基本可行解义1)，j=m+1(2-35)可以看出当所有的Qj^0(j=m+1,...m),从z=z.-£!ox°j=m+1X(1)为最优解，Z1为最优值，Qj为解的检验数。用矩阵和向量的形式表达检验数：XB=B-1b-B-1NXn,Z=CX=CBXB+CNXN=CBB-1b—(CbB-1N-Cn)Xn,QN=CbB-1N-Cn,QN=(CbB-1Pm+1-Cm+1，…CBB-1Pn-Cn)=(Qm+1(2-35)可以看出当所有的Qj^0(j=m+1,...m),迭代(基可行解的转换计算)若存在某些检验数Qj<0，则X(1)不是最优解，要进行基可行解(可行基)的转换。⑴进基变量确定:从(2-35)可看出，当某些Qj<0，则应选Qj<0中绝对值最大者，即Qs=—MaxD|Qj||Qj<0｝对应的Xs为进基变量(最大换入原则).出基变量确定(最小换出原则)(A'b')=fX].Xr.XmXm+1.a1m+1-S….a1s.Xna1n..0...00.1.0'arm+1ars.a(A'b')=fX].Xr.XmXm+1.a1m+1-S….a1s.Xna1n..0...00.1.0'arm+1ars.arnb'r、0...0...1行初等变换得'amm+1'...ams-••amnbm「广X]...Xr••-XmXm+1---XS.Xn1...-a1s/ars…0a1m+1••-0—a1nb'、b''1(A''b'')=0...1/ars0arm+1…1…arnb''r(1)主兀彳丁除以ars即ajj=arj/arsQ—12.・.n)br=br/ars(2)其匕彳丁兀素为a切=ajj-(arj/ars)ais,i女(j=1,2,...n),a”is=0,i女，b''i=b'i-(b'r/a'rs)a"i女，其中a”ij,b''i是迭代后的元素。由线性代数知识可得a''=(B)-1a',b''=(B)-1b',令非基变量等于0,则X(2)=(b"...b",0,b",0...0,b",0...0)T,Z=Cb''=(B)-1b'221r-1r+1r2B22若检检验数=^Ca〃+Ca〃一C，均>0,j=r,m+1,...,s_1,s+1,...n(。j=CbP''j-Cj=CB2(B2)-1P'j-Cj)J1ijsrjj2i=1i,r则X(2)为最优解,Z为最优值,否则重复前面步骤继续迭代，直到求出最优解或证明无最优解为止.4.单纯形表2为了方便地应用单纯形法求解线性规划，设计一种表格，在表格上运用单纯形法运算，这种表称为单纯形表，单纯形表里面的数字随着基可行解的变换而变换，每一个基可行解对应着一段单纯形表，如表2-4所示：单纯形表CjC1C2...CmCm+1Cm+2...Cnbb/aisCbXbX1X2...XmXm+1Xm+2…XnCC12X乂21001...0...0‘1m+1'1m+2•••&1n2m+1，2m+22nbb12CmXm00...1'mm+1'mm+2''''mnbmbj00...0bb...bm+1m+2nZ=tiC.b.T例11.运用单纯形表求解例9.解：标准型为：MaxZ=3X]+4X2+0X3+0X4+0X5TOC\o"1-5"\h\z满足「-2X1+2X2+X3=2X1+X2+X4=5*X1+X5=4、Xj^0,J=1,2,3,4,5求解如表2-5所示：可得线性规划的最优解和最优值分别为：X*=(23002)T,Z*=18.Cj34000bbi/aisCbXbX]X2X3X4X5000XX34X5-2[2]10011010100012541/5/bj-3-4000Z=0400X2X4X£-111/200[2]0-1/21010001144/2/4b.-702004430jX2X1X.011/41/2010-1/41/20001/4-1/213225b.j001/47/2018第五节人工变量法和几种特殊情况、人工变量法前面已提到，若从线性规划标准型A中找不到线性无关的单位列向量，则采用人工变量法确定初始基本可行解，即在约束方程左端添加非负的人工变量，使A中出现m阶单位子阵。在最优解中人工变量必须为0,否则将违背原等式约束，因此经过基的变换，必须把人工变量变为非基变量，若最优解中人工变量为基变量且不为0,则原线性规划无可行解。为了保证人工变量在最优解中为0,所用的方法常见的有两种：大M法和两阶段法。1.大M法：线性规划约束条件中加进人工变量后，假定人工变量在目标函数中的系数为(-M)(M为任意大的正数)，这样目标函数要实现最大化，必需把人工变量从基变量中换出，否则目标函数不可能实现最大化。例13.求解线性规划.MaxZ=3Xi-X2-X3满足[X1-2X2+X3MII<-4X1+X2+2X3沱32X-X3=-1IXj^0,j=1,2,3解：标准化并加入人工变量X6,X7MaxZ=3X1-X2-X3+0X4+0X5-MX6-MX7TOC\o"1-5"\h\z满足]X1-2X2+X3+X4=11J-4X1+X2+2X3-X5+X6=3]-2X1+X3+X7=1〔Xj^0,j=1,2,3,4,5,6,7用单纯形表求解如表2-7所示：得线性规划的最优解和最优值分别为：X*=(419)T,Z*=2.C;3-1-100-M-MbCX.X,X2X。XX,X,X70X41-211500011-MX6-4120-1103-MX7-20[11000116M-3-M+1-3M+10M00-4M0X43-20100-110-MX60[1100-11-21-1X-20100011-1-M+100M03M-1-M-10XF31001-22-512-1X2^0100-11-21-1X-20100011bj-10001M-1M+1-23X1—1001/3-2/32/3-5/34-1X20100-11-21-1X。0012/3-4/34/3-7/39bj0001/31/3M-1/3M-2/322.两阶段法用电子计算机求解含人工变量的线性规划时，只能用很大的确定的数代替M，这可能造成计算上的错误，故采用两阶段法。第一阶段：把原线性规划标准化并加入人工变量，构造一个辅助线性规划如下：Minw=Xn+1+…+Xn+m(人工变量之和)fa11X1+-+a1nXn+Xn+1=b1a21X1+...+a2nXn+Xn+2=b2am1X1+・..+amnXn+Xn+m=bmlXj沱0j=1,2,...,n,...,n+m

对辅助线性规划进行标准化，并用单纯形法求解，有两种结果：一是目标函数最小值为0,这说明原线性规划存在一个可行解域，并且已得到了一个初始基可行解，可转入第二阶段计算；二是目标函数最小值大于0,原问题没有可行解，停止计算。注意：求目标函数极小化，也可以不通过转化为求极大化，由目标函数表达式Z=mC.b!-¥(ZC.a，-C.)X.(2-34)可看出，若一个基可行解的检验数全部非正，i=111j=m+1i=1iijjjm即=£C.a'-C.<0,则目标函数达到了最小值，得到了最优解。否则，选取对应。s=Max｛巧|巧>0｝的i=1非基变量Xs为进基变量,再运用最小比值原则寻求出基变量，确定主元，进行迭代。第二阶段：将第一阶段最优表格中目标函数系数换成原目标函数系数，划去人工变量所在列，即得原线性规划初始单纯形表，然后继续求解。仍以例13为例。第一阶段：求辅助线性规划MinW=X6+X7满足［X1-2X2+X3+X4=11J-4X1+X2+2X3-X5+X6=3-2X1+X3+X7=1〔Xj^0,j=1,2,3,4,5,6,7列单纯形表求解如下：C0000011bCXXX2^XXX5XX70X1-211000111X6-4120-11031X-20m000116-6130100W=40X43-20100-1101X0m00-11-210X.-2010001160100-10-310jX3001-22-5120X20100-11-210X~2-20100011600000-1-10j由上表可得辅助线性规划的最优解和最优值分别为：X=(01112000)T,W*=0.由第一阶段的最优表得到了原线性规划的一个初始基可行解：X=(011120)T,以及相应的约束方程组表示形式(与原约束方程组形式等价)。第二阶段：求原线性规划最优解MaxZ=3X1-X2-X3+0X4+0X