1-2線性規(guī)劃問題幾何意義與解的性質(zhì)定理-zff課件

二、

線性規(guī)劃的幾何意義

1二、線性規(guī)劃的幾何意義

12.1基本概念①凸集：設(shè)K是n維歐式空間的一個(gè)點(diǎn)集,若任意兩點(diǎn)X(1)∈K,X(2)∈K的連線上一切點(diǎn)

a

X

(1)+(1-a)

X(2)∈K(0<a<1),則稱K為凸集.22.1基本概念2③頂點(diǎn)：設(shè)K是凸集,X

∈K。若X不能用不同的兩點(diǎn)x(1)∈K,x(2)∈K的線性組合表示，即X≠ax(1)+(1-a)x(2)(0<a<1),則稱X為K的一個(gè)頂點(diǎn)(極/角點(diǎn)).②凸組合：設(shè)

X(1),X(2),…,X(k)

是n維歐式空間的k個(gè)點(diǎn),若存在k個(gè)數(shù)u1,u2,…,uk

滿足0≤ui≤1,,則稱X=u1X(1)+u2X(2)+…+uk

X(k)

為X(1),X(2),…,X(k)的凸組合。332.

四個(gè)重要定理定理1

線性規(guī)劃問題的可行解集(可行域)是凸集。

證明思路：根據(jù)凸集定義，采用直接法證明。具體步驟：①從D中任取兩個(gè)不同的點(diǎn)X(1)和X(2)，二者應(yīng)滿足可行解定義中的等式條件；②設(shè)X是點(diǎn)X(1)和X(2)連線上的任意一點(diǎn)，有X=αX(1)+(1-α)X(2)，證明X∈D。

42.四個(gè)重要定理定理1線性規(guī)劃問題的可行解集(可行域)證明：①X(1)和X(2)滿足可行解定義中的等式條件，則有；②設(shè)X是點(diǎn)X(1)和X(2)連線上的任意一點(diǎn)，有X=αX(1)+(1-α)X(2)，那么有5證明：566引理1

若X是LP問題的可行解，則X是基本可行解的充分必要條件是X的正分量所對應(yīng)的系數(shù)列向量線性獨(dú)立.證明思路：X為LP的基本可行解<=>X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān).[證]必要性→對于有著秩為m的m×n階系數(shù)矩陣的LP問題，由基本可行解定義可知，其基本可行解X的非零分量數(shù)目k<=m，且全部為正。當(dāng)k=m，這m個(gè)正分量所對應(yīng)的系數(shù)列向量線性無關(guān)，并恰好構(gòu)成一個(gè)基；當(dāng)k<m，這k個(gè)正分量所對應(yīng)的系數(shù)列向量線性無關(guān)，且有其他（m-k）個(gè)0分量所對應(yīng)的系數(shù)列向量和這k個(gè)列向量構(gòu)成一個(gè)基。

7引理1若X是LP問題的可行解，則X是基本可行解的充分必要充分性←對于有著秩為m的m×n階系數(shù)矩陣的LP問題，X為其可行解，則X中所有元素大于等于0。設(shè)其中的正分量數(shù)目為k，且其對應(yīng)的系數(shù)列向量P1,P2,

…Pk線性獨(dú)立，則必有k<=m（否則系數(shù)矩陣的秩必然要求大于m）。當(dāng)k=m，這k個(gè)列向量恰好構(gòu)成一個(gè)基，從而可行解X為其相應(yīng)的基解，則X是一個(gè)基可行解。當(dāng)k<m，除了P1,P2,…Pk線性獨(dú)立外，必然可以在其他n-k個(gè)列向量中找出m-k個(gè)列向量，與P1,P2,…Pk構(gòu)成最大的線性獨(dú)立向量組（否則系數(shù)矩陣的秩必然要求小于m），其對應(yīng)的解為X，所有X是一個(gè)基可行解。8充分性←對于有著秩為m的m×n階系數(shù)矩陣的LP問題定理2（線性規(guī)劃幾何理論基本定理）

X是LP問題的可行解（可行域中的一點(diǎn)），如果它是基可行解，則它必然對應(yīng)于可行域D的頂點(diǎn)。證明思路：X為LP的基本可行解<=>

X是D的一個(gè)頂點(diǎn)可以利用引理1（X為LP的基本可行解<=>X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)）進(jìn)行證明。9定理2（線性規(guī)劃幾何理論基本定理）9證明思路：

X是基可行解X是D的一個(gè)頂點(diǎn)X不是基可行解X不是D的頂點(diǎn)10證明思路：X是基可行解X是D的一個(gè)頂點(diǎn)X不是基可行解必要性→X不是基可行解X不是D的頂點(diǎn)證明：（1）X是可行解，則其所有元素大于等于0。假定其前m個(gè)分量為正，則有式（1）成立。（1）（2）此外，由引理1可知，如果X不是基可行解，則其正分量所對應(yīng)的系數(shù)列向量P1,P2,…Pm線性相關(guān)，即存在一組不全為0的數(shù)ai(i=1,2,…m)使得式（2）成立（2）11必要性→X不是基可行解X不是D的頂點(diǎn)證明：（2）此外，由引必要性→X不是基可行解X不是D的頂點(diǎn)（3）用一個(gè)u>0的數(shù)乘以式（2），然后與式（1）相加減，得現(xiàn)取則X(1),X(2)是該LP問題的可行解（對應(yīng)可行域上的兩點(diǎn)）12必要性→X不是基可行解X不是D的頂點(diǎn)（3）用一個(gè)u>0的數(shù)必要性→X不是基可行解X不是D的頂點(diǎn)（4）由X,X(1),X(2)的分量表達(dá)可知，即X是X(1)和X(2)連線的中點(diǎn)，一定不是D的頂點(diǎn)。必要性證畢13必要性→X不是基可行解X不是D的頂點(diǎn)（4）由X,X(1)充分性→X不是D的頂點(diǎn)X不是基可行解證明：（1）X在可行域中，但不是頂點(diǎn)，則在可行域D中可找到不同的兩點(diǎn)使X=aX(1)+(1-a)X(2)(0<a<1)成立（2）假定X是基可行解(反證思路)

，對應(yīng)基向量組P1,P2,…Pm線性獨(dú)立。當(dāng)j>m時(shí)，有14充分性→X不是D的頂點(diǎn)X不是基可行解證明：（2）假定X是充分性→X不是D的頂點(diǎn)X不是基可行解（3）因?yàn)閄(1)和X(2)是可行解，又有下兩式成立將兩式相減，可得成立因?yàn)閄(1)和X(2)是兩個(gè)不同可行解，上式中系數(shù)不全為0，所以向量組P1,P2,…Pm線性相關(guān)，否定（2）的假設(shè)，即X不應(yīng)該是基可行解。充分性證畢15充分性→X不是D的頂點(diǎn)X不是基可行解（3）因?yàn)閄(1)和引理2若K是有界凸集，則此凸集上的任何一點(diǎn)X可表示為K的頂點(diǎn)的凸組合。證明思路：

根據(jù)凸組合的定義證明。16引理2若K是有界凸集，則此凸集上的任何一點(diǎn)X可表示為K的定理3

若可行域有界，則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)值。證明思路：1)首先,可行域有界就能夠找到最優(yōu)解;2)如果在非頂點(diǎn)X處取得最優(yōu)值，則存在頂點(diǎn)X(m)也取得相同的最優(yōu)值。17定理3若可行域有界，則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行證明：設(shè)X(1),X(2),…,X(k)是可行域D的頂點(diǎn)。若X(0)是可行域中的一點(diǎn)，但不是頂點(diǎn)，而LP的目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu)值Z*=CX(0)。首先，X(0)是可行域中的一點(diǎn)，則可用D的頂點(diǎn)表示因此有那么，在所以頂點(diǎn)中必然可以找到一個(gè)X(m)，使CX(m)是所有CX(i)中最大者。從而有下式成立18證明：設(shè)X(1),X(2),…,X(k)是即根據(jù)假設(shè)LP的目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu)值Z*=CX(0)，只能有CX(0)=CX(m)＝Z*。即目標(biāo)函數(shù)在頂點(diǎn)X(m)處也達(dá)到最大。19即根據(jù)假設(shè)LP的目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu)上述定理的一些有意義的啟示：

LP的可行域一定是凸集，但是凸集不一定成為LP的可行域，而非凸集一定不會(huì)是LP的可行域。（為什么？能舉例說明嗎？）線性規(guī)劃的基本可行解和可行域的頂點(diǎn)是一一對應(yīng)的（類似于坐標(biāo)與點(diǎn)的對應(yīng)關(guān)系?。?0上述定理的一些有意義的啟示：LP的可行域一定是凸集，但是

在可行域中尋找LP的最優(yōu)解可以轉(zhuǎn)化為只在可行域的頂點(diǎn)中找，從而把一個(gè)無限的問題轉(zhuǎn)化為一個(gè)有限的問題.頂點(diǎn)個(gè)數(shù)＝基本可行解個(gè)數(shù)≤基的個(gè)數(shù)≤

若已知一個(gè)LP有兩個(gè)或兩個(gè)以上最優(yōu)解，那么就一定有無窮多個(gè)最優(yōu)解。21在可行域中尋找LP的最優(yōu)解可以轉(zhuǎn)化21二、

線性規(guī)劃的幾何意義

22二、線性規(guī)劃的幾何意義

12.1基本概念①凸集：設(shè)K是n維歐式空間的一個(gè)點(diǎn)集,若任意兩點(diǎn)X(1)∈K,X(2)∈K的連線上一切點(diǎn)

a

X

(1)+(1-a)

X(2)∈K(0<a<1),則稱K為凸集.232.1基本概念2③頂點(diǎn)：設(shè)K是凸集,X

∈K。若X不能用不同的兩點(diǎn)x(1)∈K,x(2)∈K的線性組合表示，即X≠ax(1)+(1-a)x(2)(0<a<1),則稱X為K的一個(gè)頂點(diǎn)(極/角點(diǎn)).②凸組合：設(shè)

X(1),X(2),…,X(k)

是n維歐式空間的k個(gè)點(diǎn),若存在k個(gè)數(shù)u1,u2,…,uk

滿足0≤ui≤1,,則稱X=u1X(1)+u2X(2)+…+uk

X(k)

為X(1),X(2),…,X(k)的凸組合。2432.

四個(gè)重要定理定理1

線性規(guī)劃問題的可行解集(可行域)是凸集。

證明思路：根據(jù)凸集定義，采用直接法證明。具體步驟：①從D中任取兩個(gè)不同的點(diǎn)X(1)和X(2)，二者應(yīng)滿足可行解定義中的等式條件；②設(shè)X是點(diǎn)X(1)和X(2)連線上的任意一點(diǎn)，有X=αX(1)+(1-α)X(2)，證明X∈D。

252.四個(gè)重要定理定理1線性規(guī)劃問題的可行解集(可行域)證明：①X(1)和X(2)滿足可行解定義中的等式條件，則有；②設(shè)X是點(diǎn)X(1)和X(2)連線上的任意一點(diǎn)，有X=αX(1)+(1-α)X(2)，那么有26證明：5276引理1

若X是LP問題的可行解，則X是基本可行解的充分必要條件是X的正分量所對應(yīng)的系數(shù)列向量線性獨(dú)立.證明思路：X為LP的基本可行解<=>X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān).[證]必要性→對于有著秩為m的m×n階系數(shù)矩陣的LP問題，由基本可行解定義可知，其基本可行解X的非零分量數(shù)目k<=m，且全部為正。當(dāng)k=m，這m個(gè)正分量所對應(yīng)的系數(shù)列向量線性無關(guān)，并恰好構(gòu)成一個(gè)基；當(dāng)k<m，這k個(gè)正分量所對應(yīng)的系數(shù)列向量線性無關(guān)，且有其他（m-k）個(gè)0分量所對應(yīng)的系數(shù)列向量和這k個(gè)列向量構(gòu)成一個(gè)基。

28引理1若X是LP問題的可行解，則X是基本可行解的充分必要充分性←對于有著秩為m的m×n階系數(shù)矩陣的LP問題，X為其可行解，則X中所有元素大于等于0。設(shè)其中的正分量數(shù)目為k，且其對應(yīng)的系數(shù)列向量P1,P2,

…Pk線性獨(dú)立，則必有k<=m（否則系數(shù)矩陣的秩必然要求大于m）。當(dāng)k=m，這k個(gè)列向量恰好構(gòu)成一個(gè)基，從而可行解X為其相應(yīng)的基解，則X是一個(gè)基可行解。當(dāng)k<m，除了P1,P2,…Pk線性獨(dú)立外，必然可以在其他n-k個(gè)列向量中找出m-k個(gè)列向量，與P1,P2,…Pk構(gòu)成最大的線性獨(dú)立向量組（否則系數(shù)矩陣的秩必然要求小于m），其對應(yīng)的解為X，所有X是一個(gè)基可行解。29充分性←對于有著秩為m的m×n階系數(shù)矩陣的LP問題定理2（線性規(guī)劃幾何理論基本定理）

X是LP問題的可行解（可行域中的一點(diǎn)），如果它是基可行解，則它必然對應(yīng)于可行域D的頂點(diǎn)。證明思路：X為LP的基本可行解<=>

X是D的一個(gè)頂點(diǎn)可以利用引理1（X為LP的基本可行解<=>X的正分量所對應(yīng)的系數(shù)列向量線性無關(guān)）進(jìn)行證明。30定理2（線性規(guī)劃幾何理論基本定理）9證明思路：

X是基可行解X是D的一個(gè)頂點(diǎn)X不是基可行解X不是D的頂點(diǎn)31證明思路：X是基可行解X是D的一個(gè)頂點(diǎn)X不是基可行解必要性→X不是基可行解X不是D的頂點(diǎn)證明：（1）X是可行解，則其所有元素大于等于0。假定其前m個(gè)分量為正，則有式（1）成立。（1）（2）此外，由引理1可知，如果X不是基可行解，則其正分量所對應(yīng)的系數(shù)列向量P1,P2,…Pm線性相關(guān)，即存在一組不全為0的數(shù)ai(i=1,2,…m)使得式（2）成立（2）32必要性→X不是基可行解X不是D的頂點(diǎn)證明：（2）此外，由引必要性→X不是基可行解X不是D的頂點(diǎn)（3）用一個(gè)u>0的數(shù)乘以式（2），然后與式（1）相加減，得現(xiàn)取則X(1),X(2)是該LP問題的可行解（對應(yīng)可行域上的兩點(diǎn)）33必要性→X不是基可行解X不是D的頂點(diǎn)（3）用一個(gè)u>0的數(shù)必要性→X不是基可行解X不是D的頂點(diǎn)（4）由X,X(1),X(2)的分量表達(dá)可知，即X是X(1)和X(2)連線的中點(diǎn)，一定不是D的頂點(diǎn)。必要性證畢34必要性→X不是基可行解X不是D的頂點(diǎn)（4）由X,X(1)充分性→X不是D的頂點(diǎn)X不是基可行解證明：（1）X在可行域中，但不是頂點(diǎn)，則在可行域D中可找到不同的兩點(diǎn)使X=aX(1)+(1-a)X(2)(0<a<1)成立（2）假定X是基可行解(反證思路)

，對應(yīng)基向量組P1,P2,…Pm線性獨(dú)立。當(dāng)j>m時(shí)，有35充分性→X不是D的頂點(diǎn)X不是基可行解證明：（2）假定X是充分性→X不是D的頂點(diǎn)X不是基可行解（3）因?yàn)閄(1)和X(2)是可行解，又有下兩式成立將兩式相減，可得成立因?yàn)閄(1)和X(2)是兩個(gè)不同可行解，上式中系數(shù)不全為0，所以向量組P1,P2,…Pm線性相關(guān)，否定（2）的假設(shè)，即X不應(yīng)該是基可行解。充分性證畢36充分性→X不是D的頂點(diǎn)X不是基可行解（3）因?yàn)閄(1)和引理2若K是有界凸集，則此凸集上的任何一點(diǎn)X可表示為K的頂點(diǎn)的凸組合。證明思路：

根據(jù)凸組合的定義證明。37引理2若K是有界凸集，則此凸集上的任何一點(diǎn)X可表示為K的定理3

若可行域有界，則線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在可行域的頂點(diǎn)上達(dá)到最優(yōu)值。證明思路：