第1章 線性規(guī)劃及單純形法(2)

1、第三節(jié) 單純形法原理 一、線性規(guī)劃規(guī)劃問題的解的概念 （一）線性規(guī)劃問題標準型 )8 . 1 (),.,1(0 )7 . 1 (),.,1( . . )6 . 1 (max 1 1 njx mibxa ts xcz j i n j jij n j jj （1）可行解：滿足上述約束條件(1.7),(1.8) 的解X=(x1,xn)T，稱為線性規(guī)劃問題的可行 解。全部可行解的集合稱為可行域。 （2）最優(yōu)解：使目標函數(shù)(1.6)達到最大值 的可行解稱為最優(yōu)解。 （3）基：設(shè)A為約束方程組(1.7)的mn階 系數(shù)矩陣，（設(shè)nm），其秩為m，B是矩陣A 中的一個mm階的滿秩子矩陣，稱B是線性 規(guī)劃問題的

2、一個基。不失一般性，設(shè) B中的每一個列向量Pj(j=1,m)稱為基向量， 與基向理Pj對應(yīng)的變量xj稱為基變量。線性規(guī) 劃中除基變量以外的變量稱為非基變量。 ),.,( . . . 1 1 111 m mmm m PP aa aa B （4）基解：在約束方程組(1.7)中，令所有 非基變量為xm+1=xm+2=xn=0零，以因為有 |B|0，根據(jù)克萊姆法則，由m個約束方程可解 出m個基變量的唯一解XB=(x1,xm)T。將這個 解加上非基解中變量取0的值有X= （x1,x2,xm,0,0,0）T，稱X為線性規(guī)劃問 題的基解。顯然在基解中變量取非零值的個數(shù) 不大于方程數(shù)m，故基解的總數(shù)不超過Cn

3、m個。 （5）基可行解：滿足變量非負約束條件(1.8) 的基解稱為基可行解。 （6）可行基：對應(yīng)基可行解的基稱為可行基。 可行解 基解 基可行解 （二）可行解、基解與基可行解的關(guān)系 線性規(guī)劃的基矩陣、基變量、非基變量 = = 目標函數(shù) 約束條件 行列式0 基矩陣 右邊常數(shù) （三）線性規(guī)劃的基本概念的直觀描述 （四）求出下列線性規(guī)劃問題的所有基解、基可行解 該線性規(guī)劃問題的標準型為： x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 基變量x1、x2、x3，非基變量x4、x5、x6 基解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，

4、0） 是基可行解，表示可行域的一個極點。 目標函數(shù)值為：z=20 x1+3x2+x3=15 2x1+3x2-x3=18 x1-x2+x3=3 x1+3x2+x4=15 2x1+3x2=18 x1-x2=3 基變量x1、x2、x4，非基變量x3、x5、x6 基解為 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基可行解，表示可行域的一個極點。 目標函數(shù)值為：z=18 x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 x1+3x2=15 2x1+3x2+x5=18 x1-x2=3 x1+3x2+x3+x4=15 2

5、x1+3x2-x3+x5=18 x1-x2+x3+x6=3 基變量x1、x2、x5，非基變量x3、x4、x6 基解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基解，但不是可行解，不是一個極點。 x1+3x2=15 2x1+3x2=18 x1-x2+x6=3 基變量x1、x2、x6，非基變量x3、x4、x5 基解為（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基可行解，表示可行域的一個極點。 目標函數(shù)值為：z=18 x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 3x2+x3+x4=15 3x2-

6、x3=18 -x2+x3=3 基變量x2、x3、x4，非基變量x1、x5、x6 基解為 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0， 0） 是基解，但不是可行解。 x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 3x2+x3=15 3x2-x3+x5=18 -x2+x3=3 基變量x1、x2、x3，非基變量x4、x5、x6 基解為（x1，x2，x3，x4，x5，x6）=（0，3，6，0， 15，0） 是基可行解，表示可行域的一個極點。 目標函數(shù)值為：z=15 x1+3x2+x3+x4=15 2x1+3x2-x3+x

7、5=18 x1-x2+x3+x6=3 3x2+x3=15 3x2-x3=18 -x2+x3+x6=3 基變量x1、x2、x3，非基變量x4、x5、x6 基解為 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0， 0，10） 是基解但不是可行解。 x1+3x2+x3+x4=15 2x1+3x2-x3+x5=18 x1-x2+x3+x6=3 例：設(shè)有一標準的線性規(guī)劃問題的約束條件 如下： 2x1+x2+ x4=7 x2+x3 =3 x1,x2,x3,x40 已知下列各點均滿足以上的兩個方程： (1)(0,7,-4,0)T,(2)(2,3,0,0)T,(3)(1,0,3,5)T

8、(4)(2.5,2,1,0)T,(5)(0,3,0,4)T 二、凸集及其頂點 1凸集 設(shè)C是n維空間中的一個點集。若對任 意n維向量X1C，X2C，且X1X2，以及 任意實數(shù)（0 1），有 X= X1+(1- )X2C 則稱C為n維空間中的一個凸集。點X稱 為點X1和X2的凸組合。 以上定義有明顯的幾何意義，它表示凸 集C中的任意兩個不相同的點連線上的點 （包括這兩個端點），都位于凸集C之中。 2 頂點 凸集C中滿足下述條件的點X稱為頂點： 如果C中不存在任何兩個不同的點X1，X2，使 X成為這兩個點連線上的一個點。或者這樣敘 述：對任何X1C，X2C ，不存在X= X1+(1- )X2C （

9、0 1）， 則稱X是凸集 C的頂點。 三、幾個定理的證明 定理定理1 若線性規(guī)劃問題存在可行解，則問題的 可行域是凸集。 證：設(shè)C為滿足約束條件的集合， X1=（x11,x12,x1n)T,X2=(x21,x22,x2n)T為C內(nèi)任意兩 點，即X1C，x2C，將X1，X2代約束條件有： )9.1(; 1 2 1 1 bxPbxP n j jj n j jj X1，X2連線上任意一點可以表示為： )10.1()10()1( 21 XXX 將（1.9）代入（1.10）得： )1( 2 1 1 1 j n j jj n j jj xxPxP bbbb xPxPxP n j jj n j jj n j

10、 jj 1 2 1 2 1 1 即：CXXX 21 )1( 0)1( 21 XXX又 引理引理 線性規(guī)劃問題的可行解X=（x1,x2,xn) 為基可行解的充要條件是X的正分量所對應(yīng) 的系數(shù)列向量線性獨立的。 證：（1）必要性（結(jié)論條件） 由基可行解的定義顯然成立。 （2）充分性。 （條件結(jié)論）若向量 P1,P2,Pk線性獨立，則必有km. 當k=m時，它們恰好構(gòu)成一個基，從而 X=(x1,x2,xm,0,0,.,0)為相應(yīng)的基可行解。 當Km時，則一定可以從其余列向量中找 出(m-k)個與P1,P2,Pk構(gòu)成一個基，其對 應(yīng)的解恰為X，所以根據(jù)定義它是基可行解。 定理定理2 線性規(guī)劃問題的基可

11、行解X對應(yīng)線性規(guī) 劃問題可行域（凸集）的頂點。 證：即要證明X是可行域頂點X是基可行解 反證法，即X不是可行域頂點X不是基可行解 （1）X不是基可行解 X不是可行域頂點 不失一般性，設(shè)X的前m個分量為正，即： )11.1( 1 bxP m j jj 由引理知P1,P2,Pm線性相關(guān)，即存在一組不全為 零的數(shù)i(i=1,m)使得有： 1P1+ 2P2+ mPm=0 (1.12) (1.12)式乘上一個不為零的數(shù)得： 1P1+2P2+mPm=0 (1.13) 式(1.11)+(1.13)得： (x1+1)P1+(x2+2)P2+(xm+m)Pm=b 式(1.11)-(1.13)得： (x1-1)P

12、1+(x2-2)P2+(xm-m)Pm=b 令：X(1)=(x1+1),(x2+2),(xm+m),0,0 X(2)=(x1-1),(x2-2),(xm-m),0,0 又可以這樣來選取，使得對所有i=1,2,m有 x11 0 由引X(1)C,X(2) C,又X=X(1)/2+X(2)/2 即X不是可行域的頂點。 （2）X不是可行域頂點 X不是基可行解 不失一般性，設(shè)X=(x1,x2,xr,0,0)不是可 行域的頂點，因而可以找到可行域內(nèi)另外兩 個不同點Y和Z， 有 X=Y+(1-)Z (01)，或可寫成 xj= yj+(1- )zj (0 0,1- 0,故當xj=0時,必有yj=zj=0 因有

13、 bxPxP r j jj n j jj 11 故有 )15.1 ( )14.1 ( 11 11 bzPzP byPyP r j jj n j jj r j jj n j jj 式(1.14)-式(1.15)得0)( 1 j r j jj Pzy 因(yj-zj)不全為零,故p1,pr線性相關(guān),即X不是基可行解 定理定理3 若線性規(guī)劃問題有最優(yōu)解，一定存在 一個基可行解是最優(yōu)解。 證 設(shè)X(0)=(x10,x20,xn0)是線性規(guī)劃的一個 最優(yōu)解, n j jj xcCXZ 1 0)0( 是目標函數(shù)的最大值.若X(0)不是基可行解,由定理2 知X(0)不是頂點,一定能在可行域內(nèi)找到通過X(0)

14、的直 線上的另外兩個頂點(X(0)+)0和(X(0) -)0.將 這兩個點代入目標函數(shù)有 CCXXC CCXXC )0()0( )0()0( )( )( 因CX(0)為目標函數(shù)的最大值,故有 CCXCX CCXCX )0()0( )0()0( 由此C=0,即有C(x(0)+)=CX(0)=C(X(0)- )。如果 (x(0)+)或(x(0)-)仍不是基可行 解,按上面的方法繼續(xù)做下去,最后一定可以 找到一個基可行解,其目標函數(shù)值等于CX(0), 問題得證。 四、單純形法迭代原理 1 確定初始基可行解 )17.1(),.,1(0 )16.1( . max 1 1 njx bxP ts xcz j

15、 n j jj n j jj )18.1( 100 010 001 ),( 21 m PPP 在約束條件(1.16)式的變量的系數(shù)矩陣中總會 存在一個單位矩陣 基可行解：X=(x1,xm,xm+1,xn)T=(b1,bm,0,.,0)T 2 從一個基可行解轉(zhuǎn)換為相鄰的基可行解。 定義：兩個基可行解稱為相鄰的，如果它們 之間變換且僅變換一個基變量。 設(shè)初始基可行解中的前m個為基變量，即 X(0)=(x10,x20,xm0,0,0)T 代入約束條件(1.16)有 )19.1( 1 0 bxP m i ii 寫出式(1.19)系數(shù)的增廣矩陣 因P1,Pm一個基，其他向量Pj可用這個基的 線性組合來表

16、示，有 mmnmjmm njm njm njmm baaa baaa baaa bPPPPPP 1, 2221,2 1111,1 121 100 010 001 )20.1(0 1 1 m i iijj m i iijj PaP PaP 或 將(1.20)式乘上一個正的數(shù)0得 （1.19)式+(1.21)式并經(jīng)過整理后有 )21.1(0)( 1 m i iijj PaP T mjmj n j jj j m i iij o i axaxX XbxP bPPax )0,0,( )22.1( )22.1()( 0 1 0 1 )1( )1( 1 1 的另一個點 式找到滿足約束方程組由 要使X(1)是

17、一個基可行解，因規(guī)定0，故應(yīng)對所有 i=1,m，存在 令這m個不等式至少有一個等號成立。因為 aij0時，(1.23)式顯然成立，故可令 )23.1(0 0 iji ax )(0 )(0 )24.1( )24.1(0|min 0 00 li li ax a x a a x iji lj l ij ij i i 由式 故X(1)是一個可行解。 又因與變量x11,x1l-1,x1l, x1l+1,xm,xj對應(yīng)的向量， 經(jīng)重新排列后加上b列有如下形式的增廣矩陣。 bPPPPPP mljl 1121 mmj ljl llj ljl j j ba ba ba ba ba ba 10000 01000 00000 00100 00010 00001 11 11 22 11 因alj0，故由上述矩陣元素組成的行列式不為零， P1,P2,Pl-1,Pj,Pl+1,Pm是一個基。在上述增廣矩陣 中進行行的初等變換，將第l行乘上(1/alj)，再分別乘以 (-aij)(i=1,k,l-1,l+1,m)加到各行上去，則增廣矩陣 左半部變成為單位矩陣，又因bl/alj=，故 X(1)=(b1-a1j,bl-1- al-1,j,bl+1- al+1,j,bm- amj)T 由此X(1)是同X(0)相鄰的基可行解，且由基向量組成的矩