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

線性規(guī)劃問題的幾何意義第一頁(yè)，共三十六頁(yè)，2022年，8月28日

第1章線性規(guī)劃與單純形法

第2節(jié)線性規(guī)劃問題的幾何意義

2.1基本概念2.2幾個(gè)定理第二頁(yè)，共三十六頁(yè)，2022年，8月28日2.1基本概念凸集凸組合頂點(diǎn)第三頁(yè)，共三十六頁(yè)，2022年，8月28日

1.凸集

設(shè)K是n維歐氏空間的一點(diǎn)集，若任意兩點(diǎn)X(1)∈K，X(2)∈K的連線上的所有點(diǎn)αX(1)+(1-α)X(2)∈K，(0≤α≤1)；則稱K為凸集。圖1-7第四頁(yè)，共三十六頁(yè)，2022年，8月28日實(shí)心圓，實(shí)心球體，實(shí)心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖1-7中的(a)(b)是凸集，(c)不是凸集。圖1-2中的陰影部分是凸集。任何兩個(gè)凸集的交集是凸集，見圖1-7(d)第五頁(yè)，共三十六頁(yè)，2022年，8月28日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)則稱X為X(1)，X(2)，…，X(k)的凸組合。（當(dāng)0＜μi＜1時(shí)，稱為嚴(yán)格凸組合）.第六頁(yè)，共三十六頁(yè)，2022年，8月28日

3.頂點(diǎn)

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

圖中0，Q1,2,3,4都是頂點(diǎn)。第七頁(yè)，共三十六頁(yè)，2022年，8月28日2.2幾個(gè)定理定理1若線性規(guī)劃問題存在可行域，則其可行域是凸集

第八頁(yè)，共三十六頁(yè)，2022年，8月28日證：為了證明滿足線性規(guī)劃問題的約束條件

的所有點(diǎn)(可行解)組成的集合是凸集，只要證明D中任意兩點(diǎn)連線上的點(diǎn)必然在D內(nèi)即可。設(shè)是D內(nèi)的任意兩點(diǎn)；X(1)≠X(2)。第九頁(yè)，共三十六頁(yè)，2022年，8月28日第十頁(yè)，共三十六頁(yè)，2022年，8月28日第十一頁(yè)，共三十六頁(yè)，2022年，8月28日

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

第十二頁(yè)，共三十六頁(yè)，2022年，8月28日

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

D的頂點(diǎn)。

證：不失一般性，假設(shè)基可行解X的前m個(gè)分量為正。故現(xiàn)在分兩步來討論，分別用反證法。（1-8）第十三頁(yè)，共三十六頁(yè)，2022年，8月28日若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)式相加和相減，。第十四頁(yè)，共三十六頁(yè)，2022年，8月28日這樣得到

(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)第十五頁(yè)，共三十六頁(yè)，2022年，8月28日另一方面，當(dāng)μ充分小時(shí)，可保證

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

第十六頁(yè)，共三十六頁(yè)，2022年，8月28日(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)滿足第十七頁(yè)，共三十六頁(yè)，2022年，8月28日將這兩式相減，即得第十八頁(yè)，共三十六頁(yè)，2022年，8月28日因X(1)≠X(2)，所以上式系數(shù)不全為零，故向量組P1,P2,…，Pm線性相關(guān)，與假設(shè)矛盾。即X不是基可行解。第十九頁(yè)，共三十六頁(yè)，2022年，8月28日引理2若K是有界凸集，則任何一點(diǎn)X∈K可表示為K的頂點(diǎn)的凸組合。

本引理證明從略，用以下例子說明這引理。例5設(shè)X是三角形中任意一點(diǎn)，X(1),X(2)和X(3)是三角形的三個(gè)頂點(diǎn)，試用三個(gè)頂點(diǎn)的坐標(biāo)表示X(見圖1-8)第二十頁(yè)，共三十六頁(yè)，2022年，8月28日解任選一頂點(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)第二十一頁(yè)，共三十六頁(yè)，2022年，8月28日

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

這就得到X=μ1X(1)+μ2X(2)+μ3X(3)∑iμi=1,0＜μi＜1第二十二頁(yè)，共三十六頁(yè)，2022年，8月28日定理3若可行域有界，線性規(guī)劃問題的目標(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)線性表示為第二十三頁(yè)，共三十六頁(yè)，2022年，8月28日定理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)。第二十四頁(yè)，共三十六頁(yè)，2022年，8月28日代入目標(biāo)函數(shù)得在所有的頂點(diǎn)中必然能找到某一個(gè)頂點(diǎn)X(m)，使CX(m)是所有CX(i)中最大者。并且將X(m)代替(1-10)式中的所有X(i)，這就得到（1-10）第二十五頁(yè)，共三十六頁(yè)，2022年，8月28日由此得到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á)到最大值。稱這種線性規(guī)劃問題有無(wú)限多個(gè)最優(yōu)解。第二十六頁(yè)，共三十六頁(yè)，2022年，8月28日假設(shè)

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

于是設(shè)：第二十七頁(yè)，共三十六頁(yè)，2022年，8月28日于是：第二十八頁(yè)，共三十六頁(yè)，2022年，8月28日另外，若可行域?yàn)闊o(wú)界，則可能無(wú)最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點(diǎn)上得到。根據(jù)以上討論，可以得到以下結(jié)論：線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無(wú)界域，它們有有限個(gè)頂點(diǎn)，線性規(guī)劃問題的每個(gè)基可行解對(duì)應(yīng)可行域的一個(gè)頂點(diǎn)；若線性規(guī)劃問題有最優(yōu)解，必在某頂點(diǎn)上得到。雖然頂點(diǎn)數(shù)目是有限的(它不大于個(gè))，若采用“枚舉法”找所有基可行解，然后一一比較，最終可能找到最優(yōu)解。但當(dāng)n,m的數(shù)較大時(shí)，這種辦法是行不通的，所以要繼續(xù)討論，如何有效地找到最優(yōu)解，有多種方法，這里僅