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

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

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

3、：為了證明滿足線性規(guī)劃問題的約束條件njjjjnjxbxP1, 2 , 1, 0,的所有點(可行解)組成的集合是凸集，只要證明D中任意兩點連線上的點必然在D內即可。設是D內的任意兩點；X(1)X(2)。TnTnxxxXxxxX222212112111,則有 njjjjnjjjjnjxbxPnjxbxP122111, 2 , 1, 0, 2 , 1, 0, 令 X=(x1，x2，xn)T為 x(1),x(2)連線上的任意一點，即 X=X(1)+(1-)X(2) (01) X 的每一個分量是 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的正分量所對應的系數(shù)列向量是線性獨立的。 證證: : (1) 必要性由基可行解的定義可知。 (2) 充分性若向量P1，P2，Pk線性獨立， 則必有 km；當 k=m 時，它們恰構成一個基，從而 X=(x1,x2,xk,00)為相應的基可行解。當 km 時， 則一定可以從其余的列向量中取出 m-k 個與 P1，P2，Pk 構成最大的線性獨立向量組，其對應的解恰為 X，

5、 所以根據(jù)定義它是基可行解。 定理定理2 2 線性規(guī)劃問題的基可行解X對應于可行 D的頂點。證：證：不失一般性，假設基可行解X的前m個分量為正。故mjjjbxP1現(xiàn)在分兩步來討論，分別用反證法。（1-8）(1) 若X不是基可行解，則它一定不是可行域D的頂點 根據(jù)引理1，若X不是基可行解，則其正分量所對應的系數(shù)列向量P1，P2，Pm線性相關，即存在一組不全為零的數(shù)i,i=1,2,m使得 1P1+2P2+mPm=0 (1-9) 用一個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)連線的中點另一方面，當充分小時，可保證 xii0，i=1,2,m 即X(1)，X(2)是可行解。 這證明了X 不是可行域 D 的頂點。 (2) 若X不是可行域D的頂點，則它一定不是基可行解因為X不是可行域 D 的頂點，故在可行域D中可找到不同的兩點 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 設X是基可行解，對應向量組P1Pm線性獨立。當jm時，有xj=xj(1)=xj(2)=0，由于X(1)，X(2)是可行域的兩點。應滿足 mjmjjjjjbxPbxP1121與 mjjjjxxP1210將這兩式相減，即得 因X(1)X(2)，所以上式系數(shù)不全為零，故向量組P1,P2,，Pm線性相關，與假設矛盾。即X不是基可行解。引理2 若K是有界凸集，則任何一點XK可表示為K的頂點的凸組合。 本引理證明從略，用以下例子說明這引理。 例5 設X是三角形中任意一點，X(1),X(2)和X(3)是三角形的三個頂點，試用三個頂點的坐標表示X(見圖1-8) 解 任選一頂點X(2

8、)，做一條連線XX(2)；并延長交于X(1)、X(3)連接線上一點X。因X是X(1)、X(3)連線上一點，故可用X(1)、X(3)線性組合表示為 X=X(1)+(1-)X(3) 01 又因X是X與X(2)連線上的一個點，故 X=X+(1-)X(2) 01 將X的表達式代入上式得到 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ī)劃問題的目標函數(shù)一定可以在其可行域的頂點上達到最優(yōu)。證證 設X(1),X(2)，X(k)

9、是可行域的頂點，若X(0)不是頂點，且目標函數(shù)在X(0)處達到最優(yōu)z*=CX(0)(標準型是z=max z)。因X(0)不是頂點，所以它可以用D的頂點線性表示為 kikiiiiiixX1101, 0,定理3的證明：證：證： 設X(1),X(2)，X(k)是可行域的頂點，若X(0)不是頂點，且目標函數(shù)在X(0)處達到最優(yōu)z*=CX(0)(標準型是z=max z)。 代入目標函數(shù)得 kikiiiiiCXXCCX110在所有的頂點中必然能找到某一個頂點X(m)，使CX(m)是所有CX(i)中最大者。并且將X(m)代替(1-10)式中的所有X(i)，這就得到（1- 10） mkimikiiiCXCXC

10、X11 由此得到 X(0)CX(m) 根據(jù)假設CX(0)是最大值，所以只能有 CX(0)=CX(m) 即目標函數(shù)在頂點X(m)處也達到最大值。 有時目標函數(shù)可能在多個頂點處達到最大;這時在這些頂點的凸組合上也達到最大值。稱這種線性規(guī)劃問題有無限多個最優(yōu)解。假設是目標函數(shù)達到最大值的頂點，若是這些頂點的凸組合，即 1X， 2X， kX kikiiiiiXX111, 0,于是 kiiikiiiXCXCXC11 kimXCi, 2 , 1,設：于是：mmXCkii1另外，若可行域為無界，則可能無最優(yōu)解，也可能有最優(yōu)解，若有也必定在某頂點上得到。根據(jù)以上討論，可以得到以下結論：線性規(guī)劃問題的所有可行解構成的集合是凸集，也可能為無界域，它們有有限個頂點