1.272線性規(guī)劃問題的幾何意義ppt課件

1、凸集凸集凸組合凸組合頂點頂點v實心圓，實心球體，實心立方體等都是凸集，圓環(huán)不實心圓，實心球體，實心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖有空洞。圖1-71-7中的中的(a)(b)(a)(b)是凸集，是凸集，(c)(c)不是凸集。不是凸集。v圖圖1-21-2中的陰影部分中的陰影部分v 是凸集。是凸集。 k1ii1 定理定理1 : 1 : 若線性規(guī)劃問題存在可行域，若線性規(guī)劃問題存在可行域， 則其可行域則其可行域 是凸集是凸集 n1jjjjn, 2 , 1j, 0 x,bxP n1jjjj0 x,bxPXD T

2、2n22212T1n12111x,x,xXx,x,xX 是是D D內(nèi)任意兩點；內(nèi)任意兩點；X(1) X(2)X(1) X(2)v則有則有v令令X=(x1X=(x1，x2x2，xn)Txn)T為為x(1) , x(2)x(1) , x(2)連線上的任連線上的任意一點，即意一點，即v X=X(1) +(1-)X(2) (01)X=X(1) +(1-)X(2) (01)vX X的每一個分量是的每一個分量是v將它代入約束條件，將它代入約束條件， n1j2j2jjn1j1j1jjn,2, 1j,0 x,bxPn,2, 1j,0 x,bxP 2j1jjx)1(xx 2j1jjx)1(xx bbbbxPxP

3、xPx1xPxPn1jn1j2jj2jjn1j1jjn1jn1j2j1jjjj n1jjjj0 x,bxPXD m1jjjbxP現(xiàn)在分兩步來討論，分別用反證法?，F(xiàn)在分兩步來討論，分別用反證法。（1-81-8）v根據(jù)引理根據(jù)引理1 1，若，若X X不是基可行解，則其正分量所對不是基可行解，則其正分量所對應(yīng)的系數(shù)列向量應(yīng)的系數(shù)列向量P1P1，P2P2，PmPm線性相關(guān)，線性相關(guān)，v即存在一組不全為零的數(shù)即存在一組不全為零的數(shù)i,i=1,2,mi,i=1,2,m使得使得v1P1+2P2+mPm=0 (1-9)1P1+2P2+mPm=0 (1-9)v用一個用一個0 0的數(shù)乘的數(shù)乘(1-9)(1-9)式

4、再分別與式再分別與(1-8)(1-8)式相加式相加和相減，和相減，這樣得到這樣得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm(x1+1)P1+(x2+2)P2+(xm+m)Pm=b=b xii0，i=1,2,m即X(1)，X(2)是可行解。這證明了X 不是可行域 D 的頂點。 現(xiàn)取現(xiàn)取X(1)=X(1)=(x1-1),(x2-2),(xm-m),0,(x1-1),(x2-2),(xm-m),0,，0 0X(2)=X(2)=(x1+1),(x2+2),(xm+m),0,(x1

5、+1),(x2+2),(xm+m),0,，0 0由由X(1),X(2)X(1),X(2)可以得到可以得到X=X=（1/21/2X(1) +X(1) +（1/21/2X(2)X(2)，即即X X是是X(1)X(1)，X (2)X (2)連線的中點連線的中點因為因為X X不是可行域不是可行域 D D 的頂點，故在可行域的頂點，故在可行域D D中可找到不同中可找到不同的 兩 點的 兩 點 X ( 1 ) = ( x 1 ( 1 ) , x 2 ( 1 ) , , x n ( 1 ) ) T X ( 1 ) = ( x 1 ( 1 ) , x 2 ( 1 ) , , x n ( 1 ) ) T X(2

6、)=(x1(2),x2(2),xn(2)TX(2)=(x1(2),x2(2),xn(2)T使使 X=X(1)+(1-) X(2) X=X(1)+(1-) X(2) ， 0 01 1設(shè)設(shè)X X是基可行解，對應(yīng)向量組是基可行解，對應(yīng)向量組P1PmP1Pm線性獨立。線性獨立。當(dāng)當(dāng)j jmm時，有時，有xj=xj(1)=xj(2)=0 xj=xj(1)=xj(2)=0，由于，由于X(1)X(1)，X(2)X(2)是可行是可行域的兩點。應(yīng)滿足域的兩點。應(yīng)滿足 m1jm1j2jj1jjbxPbxP與與將這兩式相減，即得將這兩式相減，即得 m1j2j1jj0 xxPv因因X(1)X(2)X(1)X(2)，所

7、以上式系數(shù)不全為零，故向量組，所以上式系數(shù)不全為零，故向量組P1,P2,P1,P2,，PmPm線性相關(guān)，與假設(shè)矛盾。即線性相關(guān)，與假設(shè)矛盾。即X X不是基可行解。不是基可行解。v本引理證明從略，用以下例子說明這引理。本引理證明從略，用以下例子說明這引理。v例例5 5： 設(shè)設(shè)X X是三角形中任意一點，是三角形中任意一點，X(1),X(2)X(1),X(2)和和X(3)X(3)是三角形的三個頂點，試用三個頂點是三角形的三個頂點，試用三個頂點的坐標(biāo)表示的坐標(biāo)表示X(X(見圖見圖1-8) 1-8) vX=X(1)+(1-)X(3) 0X=X(1)+(1-)X(3) 01 1v又因又因X X是是XX與與

8、X(2)X(2)連線上的一個點，故連線上的一個點，故vX=X+(1-)X(2) 0X=X+(1-)X(2) 01 1v將將XX的表達式代入上式得到的表達式代入上式得到vX=X=X(1)+(1-)X(3)X(1)+(1-)X(3)+(1-)X(2)+(1-)X(2)v=X(1)+(1-)X(3)+(1-)X(2)=X(1)+(1-)X(3)+(1-)X(2)v這就得到這就得到 X=1X(1)+2X(2)+3X(3)X=1X(1)+2X(2)+3X(3)vii=1,0ii=1,0ii1 1 k1ik1iiiii0CXXCCX k1ik1iiiiii01,0,xX（1- 101- 10）在所有的頂點

9、中必然能找到某一個頂點在所有的頂點中必然能找到某一個頂點X(m)X(m)，使，使CX(m)CX(m)是是所有所有CX(i)CX(i)中最大者。并且將中最大者。并且將X(m)X(m)替代替代(1-10)(1-10)式中的所有式中的所有X(i)X(i)，這就得到這就得到 mk1imik1iiiCXCXCX 由于：由于：v由此得到由此得到 CX(0)CX(m)CX(0)CX(m)v根據(jù)假設(shè)根據(jù)假設(shè)CX(0)CX(0)是最大值，所以是最大值，所以v只能有只能有 CX(0)=CX(m)CX(0)=CX(m)v即目標(biāo)函數(shù)在頂點即目標(biāo)函數(shù)在頂點X(m)X(m)處也達到最大值。處也達到最大值。)k()2()1

10、(X,X,X k1ik1iiiii1,0,XX于是于是 k1iiik1iiiXCXCXC k,2,1i,mXCi 設(shè)：設(shè)：，mmXCk1ii 可行域為非封閉的無界區(qū)域可行域為非封閉的無界區(qū)域zx1x2 唯一最優(yōu)解唯一最優(yōu)解x1x2 z 無窮多個最優(yōu)解無窮多個最優(yōu)解x1x2Z 無界解無界解線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無界域，它們有有限個頂點，線性規(guī)也可能為無界域，它們有有限個頂點，線性規(guī)劃問題的每個基可行解對應(yīng)可行域的一個頂點；劃問題的每個基可行解對應(yīng)可行域的一個頂點；若線性規(guī)劃問題有最優(yōu)解，必在某頂點上得到。若線性規(guī)劃問題有最優(yōu)解，必在某頂點上得到。雖然頂點數(shù)目是有限的雖然頂點數(shù)目是有限的( (它不大于個它不大于個) )，若采用，若采用“枚舉法枚舉法找