線性規(guī)劃問題幾何意義與解的性質(zhì)定理-z.pptVIP

1,二、 線性規(guī)劃的幾何意義,2,2.1基本概念 凸集：設K是n維歐式空間的一個點集, 若任意 兩點 X(1)K, X(2)K 的連線上一切點 a X (1) +(1-a) X(2)K (0a1), 則稱K為凸集.,3,頂點：設K是凸集, X K。 若X不能用不同的兩點x(1)K, x(2)K 的線性組合表示，即 Xa x(1) +(1-a) x(2) (0a1), 則稱X為K的一個頂點(極 / 角點).,凸組合：設 X(1), X(2), , X(k) 是n維歐式空間的 k個點, 若存在k個數(shù)u1,u2, ,uk 滿足0ui1, , 則稱 X= u1X(1)+u2X(2)+ uk X(k) 為 X(1), X(2), , X(k) 的凸組合。,4,2. 四個重要定理,定理1 線性規(guī)劃問題的可行解集(可行域) 是凸集。,證明思路：根據(jù)凸集定義，采用直接法證明。 具體步驟：從D中任取兩個不同的點X(1)和 X(2)，二者應滿足可行解定義中的等式條件； 設X是點X(1)和X(2) 連線上的任意一點，有X=X(1)+(1-)X(2)，證明XD。,5,證明： X(1)和X(2)滿足可行解定義中的等式條件，則有； 設X是點X(1)和X(2) 連線上的任意一點，有X=X(1)+(1-)X(2)，那么有,6,7,引理1 若X是LP問題的可行解，則X是基本可行解的充分必要條件是X的正分量所對應的系數(shù)列向量線性獨立.,證明思路：X為LP的基本可行解X的正分 量所對應的系數(shù)列向量線性無關. 證 必要性對于有著秩為m的mn階系數(shù)矩陣的LP問題，由基本可行解定義可知，其基本可行解X的非零分量數(shù)目k=m，且全部為正。當k=m，這m個正分量所對應的系數(shù)列向量線性無關，并恰好構(gòu)成一個基；當km，這k個正分量所對應的系數(shù)列向量線性無關，且有其他（m-k）個0分量所對應的系數(shù)列向量和這k個列向量構(gòu)成一個基。,8,充分性對于有著秩為m的mn階系數(shù)矩陣的LP問題，X為其可行解，則X中所有元素大于等于0。設其中的正分量數(shù)目為k，且其對應的系數(shù)列向量P1, P2, Pk線性獨立，則必有k =m（否則系數(shù)矩陣的秩必然要求大于m）。 當k=m，這k個列向量恰好構(gòu)成一個基，從而可行解X為其相應的基解，則X是一個基可行解。 當km，除了P1, P2, Pk線性獨立外，必然可以在其他n-k個列向量中找出m-k個列向量，與P1, P2, Pk構(gòu)成最大的線性獨立向量組（否則系數(shù)矩陣的秩必然要求小于m ），其對應的解為X，所有X是一個基可行解。,9,定理2 （線性規(guī)劃幾何理論基本定理） X是LP問題的可行解（可行域中的一點），如果它是基可行解，則它必然對應于可行域D的頂點。 證明思路： X為LP的基本可行解 X是D的一個頂點 可以利用引理1（X為LP的基本可行解X的正分量所對應的系數(shù)列向量線性無關）進行證明。,10,證明思路：,X不是基可行解X不是D的頂點,11,必要性,X不是基可行解X不是D的頂點,證明： （1）X是可行解，則其所有元素大于等于0。假定其前m個分量為正，則有式（1）成立。 （1）,（2）此外，由引理1可知，如果X不是基可行解，則其正分量所對應的系數(shù)列向量P1, P2, Pm線性相關，即存在一組不全為0的數(shù)ai(i=1,2,m)使得式（2）成立 （2）,12,必要性,X不是基可行解X不是D的頂點,（3）用一個u0的數(shù)乘以式（2），然后與式（1）相加減，得,現(xiàn)取,則X(1),X(2)是該LP問題的可行解（對應可行域上的兩點）,13,必要性,X不是基可行解X不是D的頂點,（4）由X, X(1), X(2)的分量表達可知，,即X是X(1)和X(2)連線的中點，一定不是D的頂點。,必要性證畢,14,充分性,X不是D的頂點 X不是基可行解,證明： （1）X在可行域中，但不是頂點，則在可行域D中可找到不同的兩點使X=aX(1)+(1-a)X(2) (0a1) 成立,（2）假定X是基可行解(反證思路) ，對應基向量組P1, P2, Pm線性獨立。當jm時，有,15,充分性,X不是D的頂點 X不是基可行解,（3）因為X(1)和X(2)是可行解，又有下兩式成立,將兩式相減，可得 成立,因為X(1)和X(2)是兩個不同可行解，上式中系數(shù)不全為0，所以向量組P1, P2, Pm線性相關，否定（2）的假設，即X不應該是基可行解。,充分性證畢,16,引理2 若K是有界凸集，則此凸集上的任何一點X可表示為K的頂點的凸組合。 證明思路： 根據(jù)凸組合的定義證明。,17,定理3 若可行域有界，則線性規(guī)劃問題的目標函數(shù)一定可以在可行域的頂點上達到最優(yōu)值。 證明思路： 1)首先, 可行域有界就能夠找到最優(yōu)解; 2)如果在非頂點X處取得最優(yōu)值，則存在頂點X(m)也取得相同的最優(yōu)值。,18,證明：,設X(1) , X(2) , X(k)是可行域D的頂點。若X(0)是可行域中的一點，但不是頂點，而LP的目標函數(shù)在X(0)處達到最優(yōu)值Z*=CX(0)。 首先，X(0)是可行域中的一點，則可用D的頂點表示,因此有,那么，在所以頂點中必然可以找到一個X(m)，使CX(m)是所有CX(i)中最大者。從而有下式成立,19,即,根據(jù)假設LP的目標函數(shù)在X(0)處達到最優(yōu)值Z*=CX(0)，只能有CX(0)=CX(m)Z*。 即目標函數(shù)在頂點X(m)處也達到最大。,20,上述定理的一些有意義的啟示：,LP的可行域一定是凸集，但是凸集不一定成為LP的可行域，而非凸集一定不會是LP的可行域。 （為什么？能舉例說明嗎？） 線性規(guī)劃的基本可行解和可行域的頂點是一一對應的（