最优化单纯形法例题讲解

例1用单纯形法解下列问题:minx1-Ix2+x3sJ.x1+x2-2x3+x4=10,2工1一工2+4工3<8,-x1+2X2-4x3<4,X7-0,7=1,—,4-解：将原问题化成标准形:max-xx+2x2-x3sJ.xi+苏-2x3+x4=10,2xx-X2+4X3+X5=8,-X1+IX2-4x3+x6=4,X/-0,/=l,...,6.Xl与添加的松弛变量有，益在约束方程组中其系数列正好构成一个3阶单位阵，它们可以作为初始基变量，初始基可行解为¥二（0,0,0,10,8,4）T列出初始单纯形表，见表1。分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。〃=min（一，）=2=一1o2因此确定2为主元素（表1中以防括号口括起），意味着将以非基变量与去置换基变量与，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将4的系数列（1,'、，2）t变换成益的系数列（O,O,l）t,变换之后重新计算检验数。变换结果见表2。检验数6=3>0,当前基可行解仍然不是最优解。继续“换基”，确定2为主元素，即以非基变量与置换基变量与。变换结果见表，此时，3个非基变量的检验数都小于O・e=-9/4,os=-3/2,气=-7/4,表明已求得最优解：M=(0,12,5,8,0,0)，去除添加的松弛变量，原问题的最优解为：X'=(0,12,5,8)T,最小值为J9例2用大M法求解下列问题：minxi+x2-3x3sJ.xi-2x2+x3<工Z2xi+x2&4巧A3,K-2七=1,xy>0寸=l,・..,3.解引进松弛变量X4、、剩余变量XS和人工变量*6、X7,解下列问题：minxi+x2-3x3+oa4+0x5+M(x6+X7)sJ.x1-2x2：x3+x4=112xi+x2-4x3-X5+x6=3玉-2X3+x7=1Xj叽j=l,2,...『用单纯形法计算如下：表1CLII-3OOMMCR基bXl*3Xi必XiOX411-21OO0MX632I-4O-110MX71⑴O-20OOiCpZj4M1・3MI-M3+6MOMOO由于0,说明表中基可行解不是最优解，所以确定为为换入非基变量：以为的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。gz=3mln(一，一，一)=1=-

因此确定I为主元素（表1中以防括号口括起），意味着将以非基变量与去置换基变量不，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将占的系数列（1,2,I）T变换成七的系数列（0,0,1A，变换之后重新计算检验数。变换结果见表2。由于0,说明表中当前基可行解仍不是最优解，所以确定力为换入非基变量：以赴的系数列的正分量对应去除常数列，最小比值所在行对应的基变量作为换出的基变量。因此确定1为主元素，意味着将以非基变量M去置换基变量与，采取的做法是对约束方程组的系数增广矩阵实施初等行变换，将Q的系数列（・2,1,O）T变换成X的系数列©I,°）L变换之后重新计克检验数。变换结果见表3。由于只有6<0,表中当前基可行解仍不是最优解，所以确定必为换入非基变量：乂由于X3的系数列的正分量只有3,所以确定3为主元素，意味着将以非基变量后去置换基变量Xi，对约束方程组的系数增广矩阵实施初等行变换，将力的系数列（3,0,・2）T变换成七的系数列（l,0,0）T,变换之后重新计算检验数。变换结果见表4。得原问题的最优解：再=9,《二1，必=4,最小目标函数值为・2。

例3用两阶段法求解卜列问题:max2x1-x^si.x2+x2>2,X1-X1IX[K3,x1,x2>0.解将原问题化成标准形为：min-2X[+x2si.xi+x2-x3=2xi-X2-XA=1xi+x5=3xi，x2--sx5>0第一阶段用单纯形法求解第一阶段的线性规划问题:minbx&+x7sJ.X]+X2-X3+,r6=2士一工2一工4+x7=1il=3X”.>0G…，J:Io求解过程见若表1CLOOOOOI1Cb基hxMXl必打M1X62\1-1OO1O1I[i]-1O-1OO10x531OOO1OOC产i3-2O11OOO1X61O[2]-11OI-I0X/11-IO-1OOIO必2OIO11O-1IO-21-1OI20必1Z2O1-1/21/2O1/2-1/2OX3/2IO1/2-IZ2O1/21/2O必3/2OO1/21/21-1/2-1/2OOOOOO2I

因此，第一阶段求得最优解为(X22,9匕内尸=(5,5,O,O,式，基变量为朴M和左，不包含人工变量。第二阶段以第一阶段的最终单纯形表为基础，除去人工变量工6、M及其系数列，恢复目标价值向量为C=(2,・l,0,0,0)t,重新计算检验数，维续迭代，见表2。表2-2IOOOCB基bxlMX4I1/20I-1/2[10O-2必3/21O-1/2-1/2O0XS3/2OO1/21/21C产)-5/2OO-1/2-3/2O0X4IO2-11O-2XJ21I-1O0O1O-1⑴01-403-2OOOx420IO1I-231O0OIO1O-110CT4O10O2因此，求得原问题的最优解为(玉，七，玉，大4，/),二(3,0,1,2,0)7，最大目标函数值为6&例4用K-r条件求下列问题min/(x1,x2)=(xi-1)2+(x2-2)2sJ.x1+x2-2<0-x1<0-x2<0-x1+x2-1=0解该问题的LagJ"gc函数是L(Ar,2,x>)=(玉-I)?+(x2-2)e-xi(-xi-.v2+2)->irvi->i3x2+x?—1)由于f人=2(乂]-1)+%—蛔一//言二2(三言二2(三*■2)+4-4+〃故该问遨的KT条件是2(X：-I)-A-A-"=02(x2-2)+4-A3-//=O“Ff+2)=0&XI=OAX2=B4,4,4NO作为K-r点，除满足上述条件，自然还应满足可行性条件xi+x2-2-0,-x1+x2-1=0X【-0,x2-0为使求解易于进行，从互补松紧条件入手讨论：Ie设X]WQ,x2尹0r4=0由互补松紧条件知4=4=。，由KT条件知2(x,-1)-x/=0,2(X2-2)+//=0再由可行性条件+工-1=0得到*=LW=2,〃=0,但是显然不满足可行性X1+W-2-0,故此解舍弃。2。设4尹o由互补松紧条件知再+i-2=0•再加上可行性条件-占+工-1=0知再=；/2=|，从而由互补松紧条件知4=4=0,将已知值代入易得4=1，M=0,易知这时K-T条件和可行性条件满足，因而X・=g,I)7'为K-T点。易见/区，电)和一％(芭,工2)=芯+工2-2为凸函数，A(xpx2)=-xt+x2-1是线性函数，所以由定理3.6知X"=(；§)'为全局最优解。(力〃彳三)二Ba正定)例5用0.618法求解问题tTnn/(x)=x3-2x+l的近似最优解，已知f(x)的单峰区间为[0,3],要求最后区间精度£=0.5。解a=0,b=3,X1=a-0382(6-a)=1.146,/】=/(x1)=0.2131:x2=a^0.618(Z>-a)=1.1854,f2=/(x2)=3.6648:因为力〈力，所以向左搜索，贝Ua=0,6=X2=1854,X2=Xl=LI46,4=力=0.2131：x1=a+0382(6-a)=0.708,f}=/(x1)=-0.0611：因为f\<h，所以向左搜索，则a=0,b=x2=Ll46,X2=Xl=0.7086,/2=f\=-0.06I工:$=a+0.382(6一a)=0.438-f=/(x1)=0.208：因为f\>顷所以向右搜索，则a=0.438,b=*2=1.146,x1=x2=0-7086，力沁f2=-0.06”：x2=a+O.618(b-a)=0.876rf2=f(x?)=0.0798:因为/L〉。人所以向右搜索，贝。a=0.708,h^x2=1.146»X1=X2=0,876,/=/蛔=-0.0798:x=以+0.618(A-a)=0.9787,f。=，(X。)=一0.0199:因为|“〃卜0.438<0.5=£，所以算法停止，得到•a+A0.708+1.146X0.927o22例6用FR共短梯度法求解问题min/(X)=X；+2夫，要求选取初始点X。=用g。用g。=10V/(X)=八<20r0/5-10a._小+必)=(-2。，J1O,do=_g0=「20(5-10a)2-2(5—20a)2,20,于是/二工。+劭念二da(40y贝I]g工=W(P)=令W/(x°+ado)=1800a-500=0,贝劭二一罕广二弓M=今旦，Ao=

20,于是/二工。+劭念二da(40y贝I]g工=W(P)=乙】/、4oozl20、250,]20a、2令•JA•f(xI+8/工)=0,KiJoI=-1.于是x?=xI+勺由二(：):则g2=Y/(x2)=0.IIg2II=6<A*故一二”二(；)为所求。例7用外罚函数法求解：min^(r)=(ri-1)1+xjSJX)-工NO解P(x,Z\/)=(xi-1)2+x；+M[min(0,x2-1)1z“、[Cri-02+xtW-INomiDP(X,A^)=<.)(Xj-1)2+工工+;V/(x2-i),x2-1<0

于是dp于是dpXC==2(x-l)cx.cP2x2,x2>\5x2112x2+2M(x2TXx2<12==O2==Odxidx2最优值内(M)=IP(KM)==C),尸(=C),尸(x,")T/(x・)=l…，、\)、当“一+8时，x^M)-、,x2(M)4,X(M)—X例8用内罚函数法求解:min—(xi+1)3+x2sJ.XI-I>Ox2>O解定义障碍函数第r*)=蛔(xi一。3-x2+/-寸-、+-l)，12X|-1X2用解析法求minP(x/Q,令竺出生2=L