第1章 線性規(guī)劃與單純形法-第2節(jié)

1、運(yùn)籌學(xué)運(yùn)籌學(xué)（第三版）運(yùn)籌學(xué)教材編寫組 編清華大學(xué)出版社 第1章 線性規(guī)劃與單純形法 第2節(jié) 線性規(guī)劃問題的幾何意義錢頌迪 制作第1章 線性規(guī)劃與單純形法 第2節(jié)線性規(guī)劃問題的幾何意義 2.1 基本概念 2.2 幾個(gè)定理2.1 基本概念1. 凸集2. 凸組合3. 頂點(diǎn)1.凸集 設(shè)K是n維歐氏空間的一點(diǎn)集，若任意兩點(diǎn)X(1)K，X(2)K的連線上的所有點(diǎn)X(1)+(1-)X(2)K，(01)；則稱K為凸集。 圖1-7 實(shí)心圓，實(shí)心球體，實(shí)心立方體等都是凸集，圓環(huán)不是凸集。從直觀上講，凸集沒有凹入部分，其內(nèi)部沒有空洞。圖1-7中的(a)(b)是凸集，(c)不是凸集。 圖1-2中的陰影部分 是凸集。

2、 任何兩個(gè)凸集的交集是凸集，見圖1-7(d) 2. 凸組合 設(shè)X(1)，X(2)，X(k)是n維歐氏空間E中的k個(gè)點(diǎn)。若存在1，2，k，且0i1, i=1,2,，k; 使X=1X(1)+2X(2)+kX(k) 則稱X為X(1)，X(2)，X(k)的凸組合。（當(dāng)0i1時(shí)，稱為嚴(yán)格凸組合）.kii113. 頂點(diǎn) 設(shè)K是凸集，XK；若X不能用不同的兩點(diǎn)X(1)K和X(2)K的線性組合表示為 X=X(1)+(1-)X(2)，(01) 則稱X為K的一個(gè)頂點(diǎn)(或極點(diǎn))。 圖中0，Q1,2,3,4都是頂點(diǎn)。2.2 幾個(gè)定理 定理1 若線性規(guī)劃問題存在可行域，則其可行域 是凸集 njjjjxbxPXD10,證

3、：為了證明滿足線性規(guī)劃問題的約束條件njjjjnjxbxP1, 2 , 1, 0,的所有點(diǎn)(可行解)組成的集合是凸集，只要證明D中任意兩點(diǎn)連線上的點(diǎn)必然在D內(nèi)即可。設(shè)是D內(nèi)的任意兩點(diǎn)；X(1)X(2)。TnTnxxxXxxxX222212112111,則有 njjjjnjjjjnjxbxPnjxbxP122111, 2 , 1, 0, 2 , 1, 0, 令 X=(x1，x2，xn)T為 x(1),x(2)連線上的任意一點(diǎn)，即 X=X(1)+(1-)X(2) (01) X 的每一個(gè)分量是 21)1 (jjjxxx，將它代入約束條件， 得到 bbbbxPxPxPxxPxPnjnjjjjjnjjj

4、njnjjjjjj11221111211又因 01 , 0, 0,21jjxx，所以 xj0，j=1,2,n。 由此可見 XD，D 是凸集。 證畢。 引理 1 線性規(guī)劃問題的可行解X=(x1,x2,，xn)T為基可行解的充要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨(dú)立的。 證證: : (1) 必要性由基可行解的定義可知。 (2) 充分性若向量P1，P2，Pk線性獨(dú)立， 則必有 km；當(dāng) k=m 時(shí)，它們恰構(gòu)成一個(gè)基，從而 X=(x1,x2,xk,00)為相應(yīng)的基可行解。當(dāng) km 時(shí)， 則一定可以從其余的列向量中取出 m-k 個(gè)與 P1，P2，Pk 構(gòu)成最大的線性獨(dú)立向量組，其對應(yīng)的解恰為 X，

5、 所以根據(jù)定義它是基可行解。 定理定理2 2 線性規(guī)劃問題的基可行解X對應(yīng)于可行 D的頂點(diǎn)。證：證：不失一般性，假設(shè)基可行解X的前m個(gè)分量為正。故mjjjbxP1現(xiàn)在分兩步來討論，分別用反證法。（1-8）(1) 若X不是基可行解，則它一定不是可行域D的頂點(diǎn) 根據(jù)引理1，若X不是基可行解，則其正分量所對應(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)式相加和相減，。這樣得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)

6、Pm=b 現(xiàn)取X(1)=(x1-1),(x2-2),(xm-m),0,，0X(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)充分小時(shí)，可保證 xii0，i=1,2,m 即X(1)，X(2)是可行解。 這證明了X 不是可行域 D 的頂點(diǎn)。 (2) 若X不是可行域D的頂點(diǎn)，則它一定不是基可行解因?yàn)閄不是可行域 D 的頂點(diǎn)，故在可行域D中可找到不同的兩點(diǎn) X(1)=(x1(1),x2(1),xn(1)T X(2)=(x1(2),x2(2),xn(2)T 使 X=X(1)+(

7、1-) X(2) ， 01 設(shè)X是基可行解，對應(yīng)向量組P1Pm線性獨(dú)立。當(dāng)jm時(shí)，有xj=xj(1)=xj(2)=0，由于X(1)，X(2)是可行域的兩點(diǎn)。應(yīng)滿足 mjmjjjjjbxPbxP1121與 mjjjjxxP1210將這兩式相減，即得 因X(1)X(2)，所以上式系數(shù)不全為零，故向量組P1,P2,，Pm線性相關(guān)，與假設(shè)矛盾。即X不是基可行解。引理2 若K是有界凸集，則任何一點(diǎn)XK可表示為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) 解 任選一頂點(diǎn)X(2

8、)，做一條連線XX(2)；并延長交于X(1)、X(3)連接線上一點(diǎn)X。因X是X(1)、X(3)連線上一點(diǎn)，故可用X(1)、X(3)線性組合表示為 X=X(1)+(1-)X(3) 01 又因X是X與X(2)連線上的一個(gè)點(diǎn)，故 X=X+(1-)X(2) 01 將X的表達(dá)式代入上式得到 X=X(1)+(1-)X(3)+(1-)X(2) =X(1)+(1-)X(3)+(1-)X(2)令 1=,2=(1-),3=(1-) 這就得到 X=1X(1)+2X(2)+3X(3) ii=1,0i1定理 3 若可行域有界，線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點(diǎn)上達(dá)到最優(yōu)。證證 設(shè)X(1),X(2)，X(k)

9、是可行域的頂點(diǎn)，若X(0)不是頂點(diǎn)，且目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu)z*=CX(0)(標(biāo)準(zhǔn)型是z=max z)。因X(0)不是頂點(diǎn)，所以它可以用D的頂點(diǎn)線性表示為 kikiiiiiixX1101, 0,定理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=max z)。 代入目標(biāo)函數(shù)得 kikiiiiiCXXCCX110在所有的頂點(diǎn)中必然能找到某一個(gè)頂點(diǎn)X(m)，使CX(m)是所有CX(i)中最大者。并且將X(m)代替(1-10)式中的所有X(i)，這就得到（1- 10） mkimikiiiCXCXC

10、X11 由此得到 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ī)劃問題有無限多個(gè)最優(yōu)解。假設(shè)是目標(biāo)函數(shù)達(dá)到最大值的頂點(diǎn)，若是這些頂點(diǎn)的凸組合，即 1X， 2X， kX kikiiiiiXX111, 0,于是 kiiikiiiXCXCXC11 kimXCi, 2 , 1,設(shè)：于是：mmXCkii1另外，若可行域?yàn)闊o界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點(diǎn)上得到。根據(jù)以上討論，可以得到以下結(jié)論：線性規(guī)劃問題的所有可行解構(gòu)成的集合是凸集，也可能為無界域，它們有有限個(gè)頂點(diǎn)