運(yùn)籌學(xué)線(xiàn)性規(guī)劃圖解法

1、2.1 圖解法 圖解法不是解線(xiàn)性規(guī)劃的主要方法,只是用于說(shuō)明線(xiàn)性規(guī)劃解的性質(zhì)和特點(diǎn)。只能解兩個(gè)變量問(wèn)題。 （用圖解法求解,線(xiàn)性規(guī)劃不需要化成標(biāo)準(zhǔn)型）圖解法的步驟： 1、約束區(qū)域的確定 2、目標(biāo)函數(shù)等值線(xiàn) 3、平移目標(biāo)函數(shù)等值線(xiàn)求最優(yōu)值2 線(xiàn)性規(guī)劃圖解法線(xiàn)性規(guī)劃解的幾種可能情況 1、唯一最優(yōu)解 2、無(wú)窮多最優(yōu)解 3、無(wú)可行解 4、無(wú)有限最優(yōu)解(無(wú)界解)1例1： max z=2x1+ 3x2 s.t. x1+2x28 4x116 x1,x20有唯一解x1x2可行域(4,2) z=14目標(biāo)函數(shù)等值線(xiàn)畫(huà)圖步驟：1、約束區(qū)域的確定 2、目標(biāo)函數(shù)等值線(xiàn)3、平移目標(biāo)函數(shù)等值線(xiàn)求最優(yōu)值2有無(wú)窮多解線(xiàn)段Q1Q2

2、上的任意點(diǎn)都是最優(yōu)解x2x1x1+2x2=84x2=123x1=12例2 max z =2x1+4x2 s.t. x1+2x28 4x2 12 3x1 12 x1, x2 0Q1Q23約束條件圍不成區(qū)域(又稱(chēng)矛盾方程)無(wú)可行解例3：x1x24max z=4x1+3x2 -3x1+2x26 s.t. -x1+3x218 x1, x2 0無(wú)有限最優(yōu)解(無(wú)界解)x1 x2例4：-3x1+2x2=65線(xiàn)性規(guī)劃的幾何特性： 線(xiàn)性規(guī)劃問(wèn)題若有最優(yōu)解,一定在其可行域的頂點(diǎn)達(dá)到； 唯一最優(yōu)解必在一個(gè)頂點(diǎn)達(dá)到 或無(wú)窮多最優(yōu)解至少在兩個(gè)頂點(diǎn)達(dá)到； 無(wú)解(可行域?yàn)榭占蚰繕?biāo)函數(shù)無(wú)有限極值)。6圖解法得出線(xiàn)性規(guī)劃問(wèn)題

3、解的幾種情況解的幾種情況約束條件圖形特點(diǎn)方程特點(diǎn)唯一解一般圍成有限區(qū)域,最優(yōu)值只在一個(gè)頂點(diǎn)達(dá)到無(wú)窮多解在圍成的區(qū)域邊界上,至少有兩個(gè)頂點(diǎn)處達(dá)到最優(yōu)值目標(biāo)和某一約束方程成比例無(wú)可行解(無(wú)解)圍不成區(qū)域有矛盾方程無(wú)界解(無(wú)解)圍成無(wú)界區(qū)域,且無(wú)有限最優(yōu)值缺少一必要條件的方程7列向量 x=(x1，x2，xm）T為m維列向量。xRm線(xiàn)性相關(guān) 一組向量v1,vn,如果有一組不全為零的系數(shù) 1, ,n,使得: 1 v1+nvn=0 則稱(chēng)v1,vn 是線(xiàn)性相關(guān)的.線(xiàn)性無(wú)關(guān) 一組向量v1,vn,如果對(duì)于任何數(shù)1,n, 若要滿(mǎn)足: 1 v1+nvn=0 ,則必有系數(shù) 1=n=0,(全為零)則稱(chēng)v1,vn線(xiàn)性無(wú)關(guān)

4、(線(xiàn) 性獨(dú)立). 矩陣A的秩 設(shè)A為一個(gè)mn階矩陣(m0的數(shù)乘（2）式在分別與（1）相加和相減，這樣得到(x1-1)P1+(x2-2)P2+(xm-m)Pm=b(x1+1)P1+(x2+2)P2+(xm+m)Pm=b17引理2 若K是有界凸集,則任何一點(diǎn)XK可表示為K的頂點(diǎn)的凸組合.證明略。必要性（基可行解頂點(diǎn)，用反證法）：X不是可行域的頂點(diǎn),故可在可行域內(nèi)找到兩個(gè)不同的點(diǎn)x(1),x(2)，使得X =x(1)+(1-)x(2), 0m時(shí),有X j =xj(1)=xj(2)=0,由于x(1),x(2)是可行域的兩點(diǎn).應(yīng)滿(mǎn)足Pjxj(1)=b 與 Pjxj(2)=b將這兩式相減,即得 Pj(xj

5、(1)-xj(2)=0因x(1)x(2),所以上式系數(shù)(xj(1)-xj(2)不全為零,故向量P1,P2,Pm組線(xiàn)性相關(guān)與假設(shè)矛盾.即X不是基可行解.18 定理3 若可行域有界,線(xiàn)性規(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)(設(shè)標(biāo)準(zhǔn)型是z*=max z),則X(0)可以用頂點(diǎn)表示為 X(0)=iX(i) i0,i=1記X(1),X(2), ,X(k)中滿(mǎn)足max CX(i)的頂點(diǎn)為X(m)。于是， 由假設(shè)CX(0)為最優(yōu)解，所以CX(0)=CX(m)，即最優(yōu)解可在頂點(diǎn)X(m)達(dá)到。19注： 1、有時(shí)目標(biāo)函數(shù)可能在多個(gè)頂點(diǎn)處達(dá)到最