1、3.線性規劃的基本定理 1標準形式及圖解法 1.1標準形式11 min s.t. , i=1,2,.m x0, j=1,2,.n (3.1)njjjnijjijjc xa xb稱如下形式的線性規劃為標準形式矩陣表示3.線性規劃的基本性質 min s.t. , i=1,2,.m x0, (3.2)cxaxb其中a是mn矩陣，c是n維行向量， b是m維列向量。評注：為計算需要，一般假設b0.否則，可在方程兩端乘以(-1)即可化為非負。3.線性規劃的基本性質1122nn1111221nn12112222nn2m11m22mnnm min c xc x.c x s.t. a xa x.a xb a x

2、a x.a xb . axax.axb j x0, j1,2,.n任意非標準形式均可劃為標準形式，如引入松弛變量xn+1， xn+2 , xn+m.則有3.線性規劃的基本性質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若某變量xj無非負限制，則引入xj = xj - xj ， xj , xj 0若有上下界限制，比如xj lj, 令xj = xj - lj, , 有 xj 03.線性規劃的基本性質 1.2.

3、 圖解法 當自變量個數少于3時，我們可以用較簡便的方法求解。3.線性規劃的基本性質min 3x +2.5y s.t. 2x + 4y 40 3x + 2y 50 x, y 0.例如，考慮食譜問題3.線性規劃的基本性質30104020501020304050yx03x +2.5y2x+4y 403x+2y 50(15, 2.5)可行區域的極點：可行區域的極點：(0, 25)(15, 2.5) 最優解最優解(20, 0) 2 基本性質 2.1 線性規劃的可行域3.線性規劃的基本性質定理定理 3.1 線性規劃的可行域是凸集線性規劃的可行域是凸集. 2.2 最優極點觀察上例，最優解在極點(15,2.5

4、)達到，我們現在來證明這一事實:線性規劃若存在最優解線性規劃若存在最優解,則最優解一定可在某極點上達到則最優解一定可在某極點上達到.考察線性規劃的標準形式(3. 2)3.線性規劃的基本性質(1)(2)( )(1)(2)( ),.,.,ktxxxddd設可行域的極點為極方向為。根據表示定理，任意可行點x可表示為 (3.3) 1 0, 1,2,., 0, 1,2,., .iiiiixxdikit kt(i)(i)i=1i=1ki=1把x的表達式代入(3. 2),得等價的線性規劃:3.線性規劃的基本性質min()() (3.4) 1 0, 1,2,., 0, 1,2,., .iiiiicxcdiki

5、t kt(i)(i)i=1i=1ki=1于是,問題簡化成3.線性規劃的基本性質jj1,j,cd0,cd() (j)(j)若有某 使得則有 從而問題的目標函數值可以無限小()。此時我們稱該問題是無界的或不存在有限最優解。j2,0,0j12,t5jcd( j )若對任意的 有則為極小化目標函數，必有 ， ，. . . ,. ( 3. )在(3.6)中令3.線性規劃的基本性質 min() (3.6) 1 0, 1,2,.,iiicxik k( i )i =1ki =1p(i)1 i kcxmin cx (3.7) ( )顯然,當pj1,0, jp (3.8) 時目標函數取極小值.3.線性規劃的基本性

6、質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)的最優解,此時2,若若(3. 2)存在有限最優解存在有限最優解,則目標數的最優值則目標數的最優值可在某極點達到可在某極點達到.3.線性規劃的基本性質定理定理3.2 設線性規劃設線性規劃(3.2)(3.2)的可行域非空的可行域非空, ,則則1,(3. 2)1,(3. 2)存在最優解的充要條件是所有存在最優解的充要條件是所有(j)cd非負非負,其中其中 是可行域的極方向是可行域的極方向d(j) 3最

7、優基本可行解3.線性規劃的基本性質前面討論知道們最優解可在極點達到，而極點是一幾何概念，下面從代數的角度來考慮。 min cx s.t. axb, i=1,2,.m x0, (3.2)不失一般性,設rank(a)=m,a=b,n,b是m階可逆的.bnxxx設 bnxbxn的分量與 中列對應;的分量與 中列對應3.線性規劃的基本性質于是,ax=b可寫為bnbnx(b,n)bx bxnxb (3.9)即-1-1bnxb bb nx于是特別的令nx =0,則-1bnxb bx (3.10)x0稱為方程組ax=b的一個基本解基本解.3.線性規劃的基本性質定義定義3.1-1bnxb bxx0b稱為基矩陣

8、基矩陣, 的各分量稱為基變量基變量. xb基變量的全體12mbbbx ,x,.,x稱為一組基一組基.的各分量稱為基變量基變量. xn-1bnxb bxx01b b0,又若則稱為約束條件ax=b,x0的一個基本可行解基本可行解. b稱為可行基矩陣可行基矩陣3.線性規劃的基本性質12mbbbx ,x,.,x稱為一組可行基一組可行基.b b0,稱基本可行解是非退化非退化的,若-1 若b b0,-1 且至少有一個分量為0,稱基本可行解是退化退化的.1212例1, 求出約束為x +x =1 的所有基本可行解x ,x0:a(1,1),aax, x,. 解注意到 任意一基矩陣是 的可逆子矩陣.于是,容易知道

9、, 僅有兩個一元矩陣(1)從而得所有10的基本解為 =它們都是基本可行解013.線性規劃的基本性質31/2.,x1231212例2, 求出約束為x +x +x =1 x -x的所有基本可行解x ,x01231111:a,b1101/2111111b,b,b.111010解均可逆3.線性規劃的基本性質111111/21/2b1/21/21/21/213/4xbb01/21/21/21/41221101b110111/2xbb0111/21/23.線性規劃的基本性質1331101b110111/2xbb111/23/212,x ,x3可見是非退化的基本可行解,而x 不是非負的,從而不是基本可行解.

10、 容易知道,基矩陣的個數是有限的,因此基本解從而基本可行解的個數也是有限的, 不超過3.線性規劃的基本性質nn!mm!(nm)!(1,0)(0,1)123x +x +x =1基本可行解極點定理定理3. 3 令k=x| ax=b,x0,a是mn矩陣,r(a)=m則k的極點集與ax=b,x0的基本可行解集合等價.3.線性規劃的基本性質證明證明: (提綱)1)設x是k的極點,則x是ax=b,x0的基本可行解.2)設x是ax=b,x0的基本可行解,則x是k的極點.3.線性規劃的基本性質1),先證極點x的正分量所對應的a的列線性無關.t12sj12ss 1s 2nx(x ,x ,.,x ,0,0,.,0

11、) ,x0,j1,2,.s,a(p ,p ,.,p ,p,p,.,p )設其中記 12s12s12sjsjjj 1x ,x ,.,xp ,p ,.,p .p ,p ,.,p, j1,2,.,sp0設所對應的列為假設線性相關 則存在一組不全為零的數使得 jjjj(1)(2)jjx,j1,2,.,sx,j1,2,.,sx, x 0, js1,2,.,n0, js1,2,.,n 記3.線性規劃的基本性質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)ax

12、b同理 (1)(2)(1)(2)0,xx(xx).x.從而當充分小 有是可行點,1但我們又有x=此與 為極點相矛盾23.線性規劃的基本性質12s12ss 1m,p ,p ,.,p,smr(a),a,b(p ,p ,.,p ,p,.,p ).b于是線性無關從而可將其擴充為 的一組基 記做我們得到可逆陣t12s1 122sss 1m1bbbbnx(x ,x ,.,x ,0,0,.,0)k,axb,x0,x px p.x p0p.0pb bxb,xb b0 xxxx0又是 的極點 所以滿足于是 即且 從而是基本可行解3.線性規劃的基本性質2)設x是ax=b,x0的基本可行解,記(1)(2)(1)(2

13、)x,x(0,1), xx+(1)x 假設存在兩點及某使得bbnxxx0 x0(1)(2)(1)(2)bb(1)(2)nnxx x,x.xx記(1)(2)(1)(2)-1bbnnxxb b(1).0 xx 則 即3.線性規劃的基本性質(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又由于都是可行點,所以于是可得于是 = 總結,線性

14、規劃存在最優解,目標函數的最優值 一定能在某極點上達到.可行域k=x| ax=b,x0的極點就是其基本可行解. 從而,求線性規劃的最優解,只需要求出最優基本可行解即可.3.線性規劃的基本性質 3. 4 基本可行解的存在問題3.線性規劃的基本性質定理定理3. 4 若ax=b,x0有可行解,則一定存在基本可行解,其中a是秩為m的mn矩陣.12nt12sja(p ,p ,.,p ) x(x ,x ,.,x ,0,0,.,0), x0, j1,2,.s.證明:記 設 是一可行解其中12sxsp ,p ,.,p,x若 的 個正分量對應的列線性無關 則可以將其擴充為一組基 從而得 即一基本可行解.否則,我們通過如下步驟構造出一基本可行解3.線性規劃的基本性質12ssjjjj 1p ,p ,.,p,j1,2,.,s p0假設