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

1、第三節(jié) 單純形法原理,一、線性規(guī)劃規(guī)劃問題的解的概念 （一）線性規(guī)劃問題標(biāo)準(zhǔn)型,（1）可行解：滿足上述約束條件(1.7),(1.8)的解X=(x1,xn)T，稱為線性規(guī)劃問題的可行解。全部可行解的集合稱為可行域。 （2）最優(yōu)解：使目標(biāo)函數(shù)(1.6)達(dá)到最大值的可行解稱為最優(yōu)解。 （3）基：設(shè)A為約束方程組(1.7)的mn階系數(shù)矩陣，（設(shè)nm），其秩為m，B是矩陣A中的一個mm階的滿秩子矩陣，稱B是線性規(guī)劃問題的一個基。不失一般性，設(shè),B中的每一個列向量Pj(j=1,m)稱為基向量，與基向理Pj對應(yīng)的變量xj稱為基變量。線性規(guī)劃中除基變量以外的變量稱為非基變量。,（4）基解：在約束方程組(1.7

2、)中，令所有非基變量為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ù)不超過Cnm個。 （5）基可行解：滿足變量非負(fù)約束條件(1.8)的基解稱為基可行解。 （6）可行基：對應(yīng)基可行解的基稱為可行基。,可行解,基解,基可行解,（二）可行解、基解與基可行解的關(guān)系,線性規(guī)劃的基矩陣、基變量、非基變量,（三）線性規(guī)劃的基本概念的直觀描述,（四）求出下列線性規(guī)劃問題的所

3、有基解、基可行解,該線性規(guī)劃問題的標(biāo)準(zhǔn)型為：,基變量x1、x2、x3，非基變量x4、x5、x6,基解為（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基可行解，表示可行域的一個極點。 目標(biāo)函數(shù)值為：z=20,基變量x1、x2、x4，非基變量x3、x5、x6,基解為 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基可行解，表示可行域的一個極點。 目標(biāo)函數(shù)值為：z=18,基變量x1、x2、x5，非基變量x3、x4、x6,基解為（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基解，但不是可行解，不是一個極點。,基變

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

5、2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基解但不是可行解。,例：設(shè)有一標(biāo)準(zhǔn)的線性規(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 (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的

6、凸組合。 以上定義有明顯的幾何意義，它表示凸集C中的任意兩個不相同的點連線上的點（包括這兩個端點），都位于凸集C之中。,2 頂點 凸集C中滿足下述條件的點X稱為頂點：如果C中不存在任何兩個不同的點X1，X2，使X成為這兩個點連線上的一個點?；蛘哌@樣敘述：對任何X1C，X2C ，不存在X= X1+(1- )X2C （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代約束條件有：,X1，

7、X2連線上任意一點可以表示為：,將（1.9）代入（1.10）得：,即：,引理 線性規(guī)劃問題的可行解X=（x1,x2,xn)為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量線性獨立的。 證：（1）必要性（結(jié)論條件） 由基可行解的定義顯然成立。 （2）充分性。 （條件結(jié)論）若向量P1,P2,Pk線性獨立，則必有km. 當(dāng)k=m時，它們恰好構(gòu)成一個基，從而X=(x1,x2,xm,0,0,.,0)為相應(yīng)的基可行解。 當(dāng)K0,故當(dāng)xj=0時,必有yj=zj=0 因有,故有,式(1.14)-式(1.15)得,因(yj-zj)不全為零,故p1,pr線性相關(guān),即X不是基可行解,定理3 若線性規(guī)劃問題有最優(yōu)解

8、，一定存在一個基可行解是最優(yōu)解。 證 設(shè)X(0)=(x10,x20,xn0)是線性規(guī)劃的一個最優(yōu)解,是目標(biāo)函數(shù)的最大值.若X(0)不是基可行解,由定理2知X(0)不是頂點,一定能在可行域內(nèi)找到通過X(0)的直線上的另外兩個頂點(X(0)+)0和(X(0) -)0.將這兩個點代入目標(biāo)函數(shù)有,因CX(0)為目標(biāo)函數(shù)的最大值,故有,由此C=0,即有X(x(0)+)=CX(0)=X(X(0)-)。如果 (x(0)+)或(x(0)-)仍不是基可行解,按上面的方法繼續(xù)做下去,最后一定可以找到一個基可行解,其目標(biāo)函數(shù)值等于CX(0),問題得證。,四、單純形法迭代原理,1 確定初始基可行解,在約束條件(1.1

9、6)式的變量的系數(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)有,寫出式(1.19)系數(shù)的增廣矩陣,因P1,Pm一個基，其他向量Pj可用這個基的線性組合來表示，有,將(1.20)式乘上一個正的數(shù)0得,（1.19)式+(1.21)式并經(jīng)過整理后有,要使X(1)是一個基可行解，因規(guī)定0，故應(yīng)對所有i=1,m，存在,令這

10、m個不等式至少有一個等號成立。因為aij0時，(1.23)式顯然成立，故可令,故X(1)是一個可行解。 又因與變量x11,x1l,x1l-1, x1l+1,xm,xj對應(yīng)的向量，經(jīng)重新排列后加上b列有如下形式的增廣矩陣。,因alj0，故由上述矩陣元素組成的行列式不為零，P1,P2,Pl-1,Pj,Pl+1,Pm是一個基。在上述增廣矩陣中進(jìn)行行的初等變換，將第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)相鄰的基可行解，且由基向量組成的矩陣仍為單位矩