線性規(guī)劃問(wèn)題的幾何意義演示文稿

線性規(guī)劃問(wèn)題的幾何意義演示文稿當(dāng)前1頁(yè)，總共34頁(yè)。（優(yōu)選）線性規(guī)劃問(wèn)題的幾何意義當(dāng)前2頁(yè)，總共34頁(yè)。2.1基本概念凸集凸組合頂點(diǎn)當(dāng)前3頁(yè)，總共34頁(yè)。

1.凸集

設(shè)K是n維歐氏空間的一點(diǎn)集，若任意兩點(diǎn)X(1)∈K，X(2)∈K的連線上的所有點(diǎn)αX(1)+(1-α)X(2)∈K，(0≤α≤1)；則稱(chēng)K為凸集。圖1-7當(dāng)前4頁(yè)，總共34頁(yè)。實(shí)心圓，實(shí)心球體，實(shí)心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒(méi)有凹入部分，其內(nèi)部沒(méi)有空洞。圖1-7中的(a)(b)是凸集，(c)不是凸集。圖1-2中的陰影部分是凸集。任何兩個(gè)凸集的交集是凸集，見(jiàn)圖1-7(d)當(dāng)前5頁(yè)，總共34頁(yè)。2.凸組合設(shè)X(1)，X(2)，…，X(k)是n維歐氏空間E中的k個(gè)點(diǎn)。若存在μ1，μ2，…，μk，且0≤μi≤1,i=1,2,…，k;使X=μ1X(1)+μ2X(2)+…+μkX(k)則稱(chēng)X為X(1)，X(2)，…，X(k)的凸組合。（當(dāng)0＜μi＜1時(shí)，稱(chēng)為嚴(yán)格凸組合）.當(dāng)前6頁(yè)，總共34頁(yè)。

3.頂點(diǎn)

設(shè)K是凸集，X∈K；若X不能用不同的兩點(diǎn)X(1)∈K和X(2)∈K的線性組合表示為X=αX(1)+(1-α)X(2)，(0＜α＜1)則稱(chēng)X為K的一個(gè)頂點(diǎn)(或極點(diǎn))。

圖中0，Q1,2,3,4都是頂點(diǎn)。當(dāng)前7頁(yè)，總共34頁(yè)。2.2幾個(gè)定理定理1若線性規(guī)劃問(wèn)題存在可行域，則其可行域是凸集

當(dāng)前8頁(yè)，總共34頁(yè)。證：為了證明滿足線性規(guī)劃問(wèn)題的約束條件

的所有點(diǎn)(可行解)組成的集合是凸集，只要證明D中任意兩點(diǎn)連線上的點(diǎn)必然在D內(nèi)即可。設(shè)是D內(nèi)的任意兩點(diǎn)；X(1)≠X(2)。當(dāng)前9頁(yè)，總共34頁(yè)。當(dāng)前10頁(yè)，總共34頁(yè)。當(dāng)前11頁(yè)，總共34頁(yè)。

引理1線性規(guī)劃問(wèn)題的可行解X=(x1,x2,…，xn)T為基可行解的充要條件是X的正分量所對(duì)應(yīng)的系數(shù)列向量是線性獨(dú)立的。

當(dāng)前12頁(yè)，總共34頁(yè)。

定理2線性規(guī)劃問(wèn)題的基可行解X對(duì)應(yīng)于可行

D的頂點(diǎn)。

證：不失一般性，假設(shè)基可行解X的前m個(gè)分量為正。故現(xiàn)在分兩步來(lái)討論，分別用反證法。（1-8）當(dāng)前13頁(yè)，總共34頁(yè)。若X不是基可行解，

則它一定不是可行域D的頂點(diǎn)

根據(jù)引理1，若X不是基可行解，則其正分量所對(duì)應(yīng)的系數(shù)列向量P1，P2，…，Pm線性相關(guān)，即存在一組不全為零的數(shù)αi,i=1,2,…,m使得α1P1+α2P2+…+αmPm=0(1-9)用一個(gè)μ＞0的數(shù)乘(1-9)式再分別與(1-8)式相加和相減，。當(dāng)前14頁(yè)，總共34頁(yè)。這樣得到

(x1-μα1)P1+(x2-μα2)P2+…+(xm-μαm)Pm=b

(x1+μα1)P1+(x2+μα2)P2+…+(xm+μαm)Pm=b

現(xiàn)取

X(1)=［(x1-μα1),(x2-μα2),…,(xm-μαm),0,…，0］

X(2)=［(x1+μα1),(x2+μα2),…,(xm+μαm),0,…，0］

由X(1),X(2)可以得到X=（1/2）X(1)+（1/2）X(2)，即X是X(1)，X(2)連線的中點(diǎn)當(dāng)前15頁(yè)，總共34頁(yè)。另一方面，當(dāng)μ充分小時(shí)，可保證

xi±μαi≥0，i=1,2,…,m即X(1)，X(2)是可行解。這證明了X不是可行域D的頂點(diǎn)。

當(dāng)前16頁(yè)，總共34頁(yè)。(2)若X不是可行域D的頂點(diǎn)，則它一定不是基可行解因?yàn)閄不是可行域D的頂點(diǎn)，故在可行域D中可找到不同的兩點(diǎn)X(1)=(x1(1),x2(1),…,xn(1))TX(2)=(x1(2),x2(2),…,xn(2))T使X=αX(1)+(1-α)X(2)，

0＜α＜1設(shè)X是基可行解，對(duì)應(yīng)向量組P1…Pm線性獨(dú)立。當(dāng)j＞m時(shí)，有xj=xj(1)=xj(2)=0，由于X(1)，X(2)是可行域的兩點(diǎn)。應(yīng)滿足當(dāng)前17頁(yè)，總共34頁(yè)。將這兩式相減，即得當(dāng)前18頁(yè)，總共34頁(yè)。因X(1)≠X(2)，所以上式系數(shù)不全為零，故向量組P1,P2,…，Pm線性相關(guān)，與假設(shè)矛盾。即X不是基可行解。當(dāng)前19頁(yè)，總共34頁(yè)。引理2若K是有界凸集，則任何一點(diǎn)X∈K可表示為K的頂點(diǎn)的凸組合。

本引理證明從略，用以下例子說(shuō)明這引理。例5設(shè)X是三角形中任意一點(diǎn)，X(1),X(2)和X(3)是三角形的三個(gè)頂點(diǎn)，試用三個(gè)頂點(diǎn)的坐標(biāo)表示X(見(jiàn)圖1-8)當(dāng)前20頁(yè)，總共34頁(yè)。解任選一頂點(diǎn)X(2)，做一條連線XX(2)；并延長(zhǎng)交于X(1)、X(3)連接線上一點(diǎn)X′。因X′是X(1)、X(3)連線上一點(diǎn)，故可用X(1)、X(3)線性組合表示為

X′=αX(1)+(1-α)X(3)0＜α＜1又因X是X′與X(2)連線上的一個(gè)點(diǎn)，故X=λX′+(1-λ)X(2)0＜λ＜1將X′的表達(dá)式代入上式得到X=λ［αX(1)+(1-α)X(3)］+(1-λ)X(2)=λαX(1)+λ(1-α)X(3)+(1-λ)X(2)當(dāng)前21頁(yè)，總共34頁(yè)。

令μ1=αλ,μ2=(1-λ),μ3=λ(1-α)

這就得到X=μ1X(1)+μ2X(2)+μ3X(3)∑iμi=1,0＜μi＜1當(dāng)前22頁(yè)，總共34頁(yè)。定理3若可行域有界，線性規(guī)劃問(wèn)題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。

證設(shè)X(1),X(2)，…，X(k)是可行域的頂點(diǎn)，若X(0)不是頂點(diǎn)，且目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu)z*=CX(0)(標(biāo)準(zhǔn)型是z=maxz)。因X(0)不是頂點(diǎn)，所以它可以用D的頂點(diǎn)線性表示為當(dāng)前23頁(yè)，總共34頁(yè)。定理3的證明：證：設(shè)X(1),X(2)，…，X(k)是可行域的頂點(diǎn)，若X(0)不是頂點(diǎn)，且目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu)z*=CX(0)(標(biāo)準(zhǔn)型是z=maxz)。當(dāng)前24頁(yè)，總共34頁(yè)。代入目標(biāo)函數(shù)得在所有的頂點(diǎn)中必然能找到某一個(gè)頂點(diǎn)X(m)，使CX(m)是所有CX(i)中最大者。并且將X(m)代替(1-10)式中的所有X(i)，這就得到（1-10）當(dāng)前25頁(yè)，總共34頁(yè)。由此得到X(0)≤CX(m)根據(jù)假設(shè)CX(0)是最大值，所以只能有CX(0)=CX(m)即目標(biāo)函數(shù)在頂點(diǎn)X(m)處也達(dá)到最大值。有時(shí)目標(biāo)函數(shù)可能在多個(gè)頂點(diǎn)處達(dá)到最大;這時(shí)在這些頂點(diǎn)的凸組合上也達(dá)到最大值。稱(chēng)這種線性規(guī)劃問(wèn)題有無(wú)限多個(gè)最優(yōu)解。當(dāng)前26頁(yè)，總共34頁(yè)。假設(shè)

是目標(biāo)函數(shù)達(dá)到最大值的頂點(diǎn)，若是這些頂點(diǎn)的凸組合，即

于是設(shè)：當(dāng)前27頁(yè)，總共34頁(yè)。于是：當(dāng)前28頁(yè)，總共34頁(yè)。另外，若可行域?yàn)闊o(wú)界，則可能無(wú)最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點(diǎn)上得到。根據(jù)以上討論，可以得到以下結(jié)論：線性規(guī)劃問(wèn)題的所有可行解構(gòu)成的集合是凸集，也可能為無(wú)界域，它們有有限個(gè)頂點(diǎn)，線性規(guī)劃問(wèn)題的每個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)；若線性規(guī)劃問(wèn)題有最優(yōu)解，必在某頂點(diǎn)上得到。雖然頂點(diǎn)數(shù)目是有限的(它不大于個(gè))，若采用“枚