1、線性規劃的基本線性規劃的基本(jbn)定理定理第一頁，共32頁。 min s.t. , i=1,2,.m x0, (3.2)cxAxb其中A是mn矩陣(j zhn)，c是n維行向量， b是m維列向量。評注：為計算需要，一般假設b0.否則，可在方程兩端乘以(-1)即可化為非負。第1頁/共32頁第二頁，共32頁。1122nn1111221nn12112222nn2m11m22mnnm min c xc x.c x s.t. a xa x.a xb a xa x.a xb . axax.axb j x0, j1,2,.n任意非標準形式(xngsh)均可劃為標準形式(xngsh)，如引入松弛(sn c

2、h)變量xn+1， xn+2 , xn+m.第2頁/共32頁第三頁，共32頁。1122nn1111221nnn 112112222nnn 22m11m22mnnn mm min c xc x.c x s.t. a xa x.a xxb a xa x.a xxb . axax.axxb j x0, j1,2,.nm第3頁/共32頁第四頁，共32頁。第4頁/共32頁第五頁，共32頁。Min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.例如(lr)，考慮食譜問題第5頁/共32頁第六頁，共32頁。30104020501020304050yx03x +2.5y2

3、x+4y 403x+2y 50(15, 2.5)可行區域可行區域(qy)的極點：的極點：(0, 25)(15, 2.5) 最優解最優解(20, 0)第6頁/共32頁第七頁，共32頁。定理定理 3.1 3.1 線性規劃線性規劃(xin xn(xin xn u hu)u hu)的可行域是凸集的可行域是凸集. . 2.2 最優極點觀察上例，最優解在極點(15,2.5)達到，我們現在來證明這一事實:線性規劃若存在最優解線性規劃若存在最優解,則最優解一定可在某極點上達到則最優解一定可在某極點上達到.第7頁/共32頁第八頁，共32頁。(1)(2)( )(1)(2)( ),.,.,ktxxxddd設可行域的

4、極點為極方向為。根據表示定理(dngl)，任意可行點x可表示為 (3.3) 1 0, 1,2,., 0, 1,2,., .iiiiixxdikit kt(i)(i)i=1i=1ki=1第8頁/共32頁第九頁，共32頁。min()() (3.4) 1 0, 1,2,., 0, 1,2,., .iiiiicxcdikit kt(i)(i)i=1i=1ki=1第9頁/共32頁第十頁，共32頁。jj1,j,cd0,cd() (j)(j)若有某 使得則有 從而問題的目標函數值可以無限小()。此時我們稱該問題是無界的或不存在有限最優解。j2,0,0j12,t5jcd( j )若對任意的 有則為極小化目標函

5、數，必有 ， ，. . . ,. ( 3. )第10頁/共32頁第十一頁，共32頁。 min() (3.6) 1 0, 1,2,.,iiicxik k( i )i =1ki =1p(i)1 i kcxmin cx (3.7) ( )顯然(xinrn),當pj1,0, jp (3.8) 時目標(mbio)函數取極小值.第11頁/共32頁第十二頁，共32頁。iipiipcx(cx)(cd) (cx)(cx) =cx kt(i)(i)i=1i=1kk(i)( )i=1i=1( )(p)x因此極點是問題(3.2)的最優解.即(3.5)和(3.8)是(3.4)的最優解,此時(c sh)第12頁/共32頁

6、第十三頁，共32頁。定理定理(dngl)3.2 設線性規劃設線性規劃(3.2)的可行域非空的可行域非空,則則1,(3. 2)1,(3. 2)存在最優解的充要條件是所有存在最優解的充要條件是所有(j)cd非負非負,其中其中 是可行域的極方向是可行域的極方向d(j)第13頁/共32頁第十四頁，共32頁。前面(qin mian)討論知道們最優解可在極點達到，而極點是一幾何概念，下面從代數的角度來考慮。 min cx s.t. Axb, i=1,2,.m x0, (3.2)不失一般性,設rank(A)=m,A=B,N,B是m階可逆的.BNxxx設 BNxBxN的分量與 中列對應;的分量與 中列對應第1

7、4頁/共32頁第十五頁，共32頁。BNBNx(B,N)bx BxNxb (3.9)即-1-1BNxB bB Nx于是(ysh)特別的令Nx =0,則-1BNxB bx (3.10)x0第15頁/共32頁第十六頁，共32頁。定義定義(dngy)3.1(dngy)3.1-1BNxB bxx0B稱為基矩陣基矩陣, 的各分量稱為基變量基變量. xB基變量的全體12mBBBx ,x,.,x稱為一組基一組基.的各分量稱為基變量基變量. xN-1BNxB bxx01B b0,又若則稱為約束條件Ax=b,x0的一個基本可行解基本可行解. B稱為可行基矩陣可行基矩陣第16頁/共32頁第十七頁，共32頁。12mB

8、BBx ,x,.,x稱為一組可行基一組可行基.B b0,稱基本可行解是非退化非退化的,若-1 若B b0,-1 且至少(zhsho)有一個分量為0,稱基本可行解是退化的.1212例1, 求出約束為x +x =1 的所有基本可行解x ,x0:A(1,1),AAx, x,. 解注意到 任意一基矩陣是 的可逆子矩陣.于是,容易知道, 僅有兩個一元矩陣(1)從而得所有10的基本解為 =它們都是基本可行解01第17頁/共32頁第十八頁，共32頁。31/2.,x1231212例2, 求出約束為x +x +x =1 x -x的所有基本可行解x ,x01231111:A,b1101/2111111B,B,B.

9、111010解均可逆第18頁/共32頁第十九頁，共32頁。111111/21/2B1/21/21/21/213/4xBb01/21/21/21/41221101B110111/2xBb0111/21/2第19頁/共32頁第二十頁，共32頁。1331101B110111/2xBb111/23/212,x ,x3可見是非退化的基本可行解,而x 不是非負的,從而不是基本可行解.第20頁/共32頁第二十一頁，共32頁。nn!mm!(nm)!(1,0)(0,1)123x +x +x =1基本可行解極點第21頁/共32頁第二十二頁，共32頁。證明證明: (提綱提綱)1)設設x是是K的極點的極點,則則x是是

10、Ax=b,x0的基本的基本(jbn)可行解可行解.2)設設x是是Ax=b,x0的基本的基本(jbn)可行解可行解,則則x是是K的極點的極點.第22頁/共32頁第二十三頁，共32頁。1),先證極點先證極點x的正分量的正分量(fn ling)所對應的所對應的A的列線性無關的列線性無關.T12sj12ss 1s 2nx(x ,x ,.,x ,0,0,.,0) ,x0, j1,2,.s,A(p ,p ,.,p ,p,p,.,p )設其中記 12s12s12sjsjjj 1x ,x ,.,xp ,p ,.,p .p ,p ,.,p, j1,2,.,sp0設所對應的列為假設線性相關 則存在一組不全為零的數

11、使得 jjjj(1)(2)jjx, j1,2,.,sx, j1,2,.,sx, x 0, js1,2,.,n0, js1,2,.,n 記第23頁/共32頁第二十四頁，共32頁。j(1)(2)jjx0, j1,2,.,s0,x0,x0, j1,2,.,s由于故可取充分小的使得(1)nn(1)jjjjjj 1j 1ssjjjjj 1j 1 Axx p(x)p x ppb則(2)Axb同理 (1)(2)(1)(2)0,xx(xx).x.從而當充分小 有是可行點,1但我們又有x=此與 為極點相矛盾2第24頁/共32頁第二十五頁，共32頁。12s12ss 1m,p ,p ,.,p,smr(A),A,B(

12、p ,p ,.,p ,p,.,p ).B于是線性無關從而可將其擴充為 的一組基 記做我們得到可逆陣T12s1122sss 1m1BBBBNx(x ,x ,.,x ,0,0,.,0)K,Axb,x0,x px p.x p0p.0pb Bxb,xB b0 xxxx0又是 的極點 所以滿足于是 即且 從而是基本可行解第25頁/共32頁第二十六頁，共32頁。2)設設x是是Ax=b,x0的基本的基本(jbn)可行解可行解,記記(1)(2)(1)(2)x,x(0,1), xx+(1)x 假設存在兩點及某使得BBNxxx0 x0(1)(2)(1)(2)BB(1)(2)NNxx x,x.xx記(1)(2)(1

13、)(2)-1BBNNxxB b(1).0 xx 則 第26頁/共32頁第二十七頁，共32頁。(1)(2)(1)(2)-1BBNNB bx(1)x,0 x(1)x. (1)(2)NN(1)(2)NN0,(1)0,x0,x0.x0,x0. 又 則由上兩式知(1)(2)(1)(2)(1)11(1)1BN(2)11(2)1BN(1)(2)x,x Axb,AxbxB bB NxB b xB bB NxB bx xx又由于都是可行點,所以于是可得于是 =第27頁/共32頁第二十八頁，共32頁。第28頁/共32頁第二十九頁，共32頁。定理定理3. 4 若若Ax=b,x0有可行解有可行解,則一定存在則一定存在(cnzi)基本可基本可行解行解,其中其中A是秩為是秩為m的的mn矩陣矩陣.12nT12sjA(p ,p ,.,p ) x(x ,x ,.,x ,0,0,.,0), x0, j1,2,.s.證明:記 設 是一可行解其中12sxsp ,p ,.,p,x若 的 個正分量對應的列線性無關 則可以將其擴充為一組基 從而得 即一基本可行解.第29頁/共32頁第三十頁，共32頁。12ssjjjj 1p ,p ,.,p, j1,2,.,s p0假設線性相關 則存在一組不全為零的數(且至少有一個為正)使得 jjj x: