1、線性規(guī)劃線性規(guī)劃(xin xn u hu)算法算法第一頁，共26頁。 代數(shù)式maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm xj 0 j=1,2,n第1頁/共26頁第二頁，共26頁。線性規(guī)劃線性規(guī)劃(xin xn u hu)標(biāo)準(zhǔn)標(biāo)準(zhǔn)型型 和式：maxZ=cjxj aijxj=bi i=1,2,m xj 0 j=1,2,n 向量(xingling)式：maxZ=CTX pjxj=bi i=1,2,m xj 0 j=1,2,n矩陣式： maxZ=CTX AX=b X 0 第2頁/共

2、26頁第三頁，共26頁。線性規(guī)劃線性規(guī)劃(xin xn u hu)解的解的概念概念12( ,)( ,P )BB NBP P分解m若A =， 其中，可逆，稱 為基矩陣1B2BNNnxxxX,xxxx基相應(yīng)地 為，為變量非基變量B-11BNBNNx,xxxBxxbBB代入約束：(B,N)即+N=b,b-N-1B-1NBNxB bxxBx0令=0,b，稱x=為基本解-1BNxB bBx0基本可行解若x=0稱為， 為可行基第3頁/共26頁第四頁，共26頁。線性規(guī)劃線性規(guī)劃(xin xn u hu)解的解的性質(zhì)性質(zhì)可行域凸集（凸多面體）可行域非空至多有有限個(gè)頂點(diǎn)最優(yōu)解若存在(cnzi)，必可在頂點(diǎn)達(dá)到線

3、性規(guī)劃的基本定理：線性規(guī)劃的基本可行解就是可行域的極點(diǎn)。 這一定理的重要性在于把可行域的極點(diǎn)這一幾何概念與基本可行解這一代數(shù)概念聯(lián)系起來，因而可以通過求基本可行解的線性代數(shù)的方法來得到可行域的一切極點(diǎn)，從而有可能進(jìn)一步獲得最優(yōu)極點(diǎn)。 第4頁/共26頁第五頁，共26頁。 計(jì)算計(jì)算(j sun)流程流程線性規(guī)劃線性規(guī)劃(xin xn u hu)的單的單純形算法純形算法初始基本可行解初始基本可行解是否最優(yōu)解或是否最優(yōu)解或無限最優(yōu)解無限最優(yōu)解? ?結(jié)束結(jié)束沿邊界找新沿邊界找新的基本可行解的基本可行解N NY Y第5頁/共26頁第六頁，共26頁。1. 初始基本可行初始基本可行(kxng)解的確定解的確定

4、從系數(shù)從系數(shù)(xsh)矩陣中找到一個(gè)可行基矩陣中找到一個(gè)可行基B，不妨設(shè)，不妨設(shè)B由由A的前的前m列組成，即列組成，即B=(P1,P2,Pm)。進(jìn)行等價(jià)變換約束。進(jìn)行等價(jià)變換約束方程兩端分別左乘方程兩端分別左乘B1 -11BNBNxxxBxBB即+N=b,b-N-1NB bx0(0)令=0,得初始基本可行解x-1-10B b(,)B b0NTTTBBcccT (0)對應(yīng)的目標(biāo)函數(shù)值z =c x第6頁/共26頁第七頁，共26頁。-11BNAXxBxB由=b,b-N，其目標(biāo)函數(shù)值：BBNNx(,)x +xxNTTTTBBNccccTz=c x-1-1NN(B b-B Nx )+xTTBNcc-1-

5、1NB b(B N)xTTTBBNccc-10N+(B N)xTTNBzcc-10jjj R+(B P )x ,TjBzccR非基變量下標(biāo)集-1NB NTTNBcc記-1jBTjBjccPjR即，(NN0)0,x，判別準(zhǔn)則：當(dāng)則得到最優(yōu)解否則繼續(xù)尋找改進(jìn)的基為檢驗(yàn)數(shù)本可行解-1BBB B0TTBcc注第7頁/共26頁第八頁，共26頁。3. 基變換基變換(binhun)轉(zhuǎn)軸變換轉(zhuǎn)軸變換(binhun)取某一非基變量(binling)xk換入基（即讓xk0，其余非基變量(binling)仍為0）同時(shí)(tngsh)，再從基變量中換出一個(gè)變量xBr作為非基變量。如何求換入變量如何求換入變量xk和換出變

6、量和換出變量xBr？K=?，r=?kmax|0,0,0jjj Rk選令x其余非基變量-11BNAXxBxB由=b,b-N-11-11kkK0BxBP x0BB BKx b- （,P , ）b-kxkb-Y第8頁/共26頁第九頁，共26頁。3. 基變換基變換(binhun)轉(zhuǎn)軸變換轉(zhuǎn)軸變換(binhun)kbyxbyB111kBBmmmkx更詳細(xì)地x =x-10jj0jj R+(B P )x+TjBkzzcczx從目標(biāo)函數(shù)看從目標(biāo)函數(shù)看xk越大越好，但從可行性看越大越好，但從可行性看xk又不能任意大。又不能任意大。若若yik0,i=1,，m,xk可任意取值，此時(shí)問題可任意取值，此時(shí)問題(wnt)

7、是無界的；是無界的；若若yik0,為保證可行性，即為保證可行性，即xBi=bi-yikxk0，應(yīng)取，應(yīng)取ikikbxymin|0ikikikbxyy令 rrkby注意注意(zh y)：xBr=0第9頁/共26頁第十頁，共26頁。3. 基變換基變換(binhun)轉(zhuǎn)軸變換轉(zhuǎn)軸變換(binhun)新可行解：新可行解：x=(xB1,xBr-1,0,xBr+1,xBm,0,，0,xk,0,，0)可以證明此解為新的基本可行解。這是因?yàn)樵瓉砜梢宰C明此解為新的基本可行解。這是因?yàn)樵瓉?yunli)的基的基PB1,PBm線性無關(guān)，而線性無關(guān)，而yk=B-1Pk,故故Pk=Byk=yikPBi，而，而PBr的系

8、數(shù)的系數(shù)yrk0，所以，用所以，用Pk代替代替Pr后的向量組后的向量組PB1,Pk,PBm線性線性無關(guān)，所以無關(guān)，所以x為基本可行解為基本可行解在新的基本可行解中，目標(biāo)函數(shù)比原來增加了在新的基本可行解中，目標(biāo)函數(shù)比原來增加了kxk。重復(fù)上述過程，直至所有的重復(fù)上述過程，直至所有的j均均0，得到最優(yōu)解。因?yàn)椋玫阶顑?yōu)解。因?yàn)?yn wi)基本可行解的個(gè)數(shù)是有限的，因此在非退化基本可行解的個(gè)數(shù)是有限的，因此在非退化(r(A)=m)情情況下，經(jīng)有限次迭代必能達(dá)到最優(yōu)解。況下，經(jīng)有限次迭代必能達(dá)到最優(yōu)解。第10頁/共26頁第十一頁，共26頁。總結(jié)計(jì)算步驟：給定總結(jié)計(jì)算步驟：給定(i dn)初始基初始基

9、B步步1.令令xN=0,，xB=B-1b=b，z0=cBTxB ；步步2.檢驗(yàn)數(shù)檢驗(yàn)數(shù)j=cj-cBTB-1 Pj，j0，停止，得最優(yōu)解，否則取，停止，得最優(yōu)解，否則取kmaxj，轉(zhuǎn)步，轉(zhuǎn)步3；步步3. 解解yk=B-1Pk，若，若yk0，停止，停止,不存在不存在(cnzi)有限最優(yōu)解有限最優(yōu)解. 否則轉(zhuǎn)步否則轉(zhuǎn)步4；步步4.計(jì)算計(jì)算 xk進(jìn)基，進(jìn)基，xBr離基，用離基，用Pk替代替代PBr得新的可行基得新的可行基B， 轉(zhuǎn)步轉(zhuǎn)步1。min|0irikikbyyrrkby第11頁/共26頁第十二頁，共26頁。 例：用單純形法的基本思路求解(qi ji)下面的線性規(guī)劃問題： Max z = 150

10、0 x1 + 2500 x2 s.t. 3 x1 + 2 x2 + x3 = 65 2 x1 + x2 + x4 = 40 3 x2 + x5 = 75 x1 , x2 , x3 , x4 , x5 0321002101003001AC=(1500, 2500, 0, 0, 0)Tb=(65, 40, 75)T第12頁/共26頁第十三頁，共26頁。第一次迭代：第一次迭代：（1）取初始可行基）取初始可行基B0= (p3 , p4 , p5)，那么那么x3 ，x4 ，x5為基變量，為基變量，x1 ，x2為為非基變量。將基變量和目標(biāo)非基變量。將基變量和目標(biāo)(mbio)函函數(shù)用非基變量表示：數(shù)用非基變

11、量表示： z =1500 x1+2500 x2 x3 = 65 - 3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2當(dāng)非基變量當(dāng)非基變量x1，x2=0時(shí)，相應(yīng)的基變量時(shí)，相應(yīng)的基變量和目標(biāo)和目標(biāo)(mbio)函數(shù)值為函數(shù)值為x3=65，x4=40，x5= 75，z = 0，得到當(dāng)前的基本可行解：，得到當(dāng)前的基本可行解：x(0) =(0,0,65,40,75)T，z = 0 。-11BNxBxBb-N-10BbTBcT(0)z =c x第13頁/共26頁第十四頁，共26頁。（2 2）最優(yōu)性檢驗(yàn)：）最優(yōu)性檢驗(yàn)： 在目標(biāo)函數(shù)在目標(biāo)函數(shù)z = 1500 x1

12、+ 2500 x2z = 1500 x1 + 2500 x2中，非基中，非基變量變量x1x1，x2x2的系數(shù)都是正數(shù)的系數(shù)都是正數(shù)(zhngsh)(zhngsh)，此解，此解非最優(yōu)。取非最優(yōu)。取kkmax1500, 2500max1500, 2500，（3 3）轉(zhuǎn)軸變換：選擇）轉(zhuǎn)軸變換：選擇x2x2為進(jìn)基變量，另一個(gè)為進(jìn)基變量，另一個(gè)非基變量非基變量x1x1保持零值不變。保持零值不變。-10jj0jj R+(B P )x+TjBkzzcczx第14頁/共26頁第十五頁，共26頁。 確定出基變量。在約束條件確定出基變量。在約束條件 x3 = 65 - 3 x1 - 2 x2 x3 = 65 -

13、3 x1 - 2 x2 x4 = 40 - 2 x1 - x2 x4 = 40 - 2 x1 - x2 x5 = 75 - 3 x2 x5 = 75 - 3 x2中，當(dāng)中，當(dāng)x2x2的值從的值從0 0開始增加開始增加(zngji)(zngji)時(shí)，基變量時(shí)，基變量x3 x3 、x4 x4 、x5x5的值分別從當(dāng)前的值的值分別從當(dāng)前的值6565、4040和和7575開開始減少，當(dāng)始減少，當(dāng)x2x2增加增加(zngji)(zngji)到到2525時(shí)，時(shí)，x5x5首先下首先下降為降為0 0成為非基變量。這時(shí)，新的基變量為成為非基變量。這時(shí)，新的基變量為x3 x3 、x4 x4 、x2 x2 ，新的非

14、基變量為，新的非基變量為x1 x1 、x5 x5 ，當(dāng)前的基，當(dāng)前的基本可行解和目標(biāo)函數(shù)值為：本可行解和目標(biāo)函數(shù)值為：X(1) = (0X(1) = (0，2525，1515，1515，0)T0)T，z = 62500z = 62500。 22213ByP 65/2min 40/174/3第15頁/共26頁第十六頁，共26頁。第二次迭代：第二次迭代： （1）當(dāng)前）當(dāng)前(dngqin)的可行基為的可行基為B1 = (p2 , p3 , p4)，那么，那么x2 ，x3 ，x4為基變量，為基變量，x1 ，x5為非基為非基變量。將基變量和目標(biāo)函數(shù)用非基變量表示：變量。將基變量和目標(biāo)函數(shù)用非基變量表示：

15、 z = 62500 + 1500 x1 (2500/3) x5 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 第16頁/共26頁第十七頁，共26頁。 （2 2）選擇進(jìn)基變量。在目標(biāo)函數(shù)）選擇進(jìn)基變量。在目標(biāo)函數(shù)z = 62500 + 1500 x1 (2500/3) x5 z = 62500 + 1500 x1 (2500/3) x5 中，中，非基變量非基變量x1x1的系數(shù)是正數(shù)，因此的系數(shù)是正數(shù)，因此 x1 x1進(jìn)基可以進(jìn)基可以使目標(biāo)函數(shù)使目標(biāo)函數(shù)z z增大，于是增大，于是(ysh)(ysh)選擇選

16、擇x1x1進(jìn)基，進(jìn)基，使使x1x1的值從的值從0 0開始增加開始增加, , 另一個(gè)非基變量另一個(gè)非基變量x5x5保保持零值不變。持零值不變。 (3) (3)確定出基變量。在約束條件確定出基變量。在約束條件 x2 = 25 (1/3) x5 x2 = 25 (1/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x3 = 15 - 3 x1 + (2/3) x5 x4 = 15 - 2 x1 + (1/3) x5 x4 = 15 - 2 x1 + (1/3) x5 第17頁/共26頁第十八頁，共26頁。中，由于進(jìn)基變量中，由于進(jìn)基變量x1在兩個(gè)約束條件中的在兩個(gè)約束條件中的系數(shù)都是

17、負(fù)數(shù)，當(dāng)系數(shù)都是負(fù)數(shù)，當(dāng)x1的值從的值從0開始增加時(shí)，開始增加時(shí)，基變量基變量x3 、x4的值分別從當(dāng)前的值的值分別從當(dāng)前的值15、15開始減少，當(dāng)開始減少，當(dāng)x1增加到增加到5時(shí)，時(shí)，x3首先下首先下降為降為0成為非基變量。這時(shí)，新的基變量成為非基變量。這時(shí)，新的基變量為為x1 、x2 、x4 ，新的非基變量為，新的非基變量為x3 、x5 ，當(dāng)前的基本可行，當(dāng)前的基本可行(kxng)解和目標(biāo)函解和目標(biāo)函數(shù)值為：數(shù)值為：X(2) = (5，25，0，5，0)T，z = 70000。 第18頁/共26頁第十九頁，共26頁。第三次迭代：第三次迭代： （1）當(dāng)前的可行基為）當(dāng)前的可行基為B2 = (

18、p1 , p2 , p4 )，那么那么x1 ，x2 ，x4為基變量，為基變量，x3 ，x5為非基為非基變量。將基變量和目標(biāo)函數(shù)變量。將基變量和目標(biāo)函數(shù)(hnsh)用非基用非基變量表示：變量表示： z = 70000 500 x3 500 x5 x1 = 5 (1/3) x3 + (2/9) x5 x2 = 25 (1/3) x5 x4 = 5 + (2/3) x3 (1/9) x5 第19頁/共26頁第二十頁，共26頁。 （2）選擇）選擇(xunz)進(jìn)基變量。在目標(biāo)函數(shù)進(jìn)基變量。在目標(biāo)函數(shù) z = 70000 500 x3 500 x5 中，非基變量中，非基變量x3 、x5的系數(shù)均不是正數(shù)，因

19、此的系數(shù)均不是正數(shù)，因此進(jìn)基都不可能使目標(biāo)函數(shù)進(jìn)基都不可能使目標(biāo)函數(shù)z增大，于是得到最優(yōu)增大，于是得到最優(yōu)解，解， x* = (5，25，0，5，0)T，最優(yōu)目標(biāo)值為最優(yōu)目標(biāo)值為 z* = 70000。我們也稱相應(yīng)的基我們也稱相應(yīng)的基 B2 = (p1 , p2 , p4)為最優(yōu)基。計(jì)算結(jié)束。為最優(yōu)基。計(jì)算結(jié)束。 第20頁/共26頁第二十一頁，共26頁。1X(0) =(0,0,65,40,75)T，z = 0 。對應(yīng)。對應(yīng)(duyng)于圖于圖中的中的D、E交點(diǎn)交點(diǎn)X(1) = (0，25，15，15，0)T，z = 62500。對應(yīng)。對應(yīng)(duyng)于圖中的于圖中的C、D交點(diǎn)。交點(diǎn)。x* = (5，25，0，5，0)T， z* = 70000。對應(yīng)。對應(yīng)(duyng)于圖的于圖的A、C交點(diǎn)。交點(diǎn)。第21頁/共26頁第二十二頁，共26頁。單純形表單純形表 maxZ=CTX s.t.AX=b X 0 BNxxxBNcCcA=(B,N)NBNx. .xxTstBTBBNmaxzc x +c+N=b x0BNN. .xxxTstBTBBNmaxz+N=bzc x +c x0zxBxN右端項(xiàng)0BNb1cBcN0第22頁/共26頁第二十三頁，共26頁。1BN-1-1N. .xxB b(B N)xTTTBBNstBbccc-1maxz+N=Bz x0zxBxN右端