我的運(yùn)籌課件or

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

2、無有限最優(yōu)解(無界解)有無窮多解兩個頂點處達(dá)到最優(yōu)解0,12416482.42max21212121xxxxxxtsxxz例2：x2x1x1+2x2=84x2=124x1=16約束條件圍不成區(qū)域(又稱矛盾方程)無可行解0,124322.23max21212121xxxxxxt sxxz例3：x1x2Max z=4x1+3x2 -3x1+2x2 6 s.t -x1+3x2 18 x1, x2 0無有限最優(yōu)解(無界解)x1 x2例4：-3x1+2x2=6 線性規(guī)劃問題若有最優(yōu)解,一定在其可行域的頂點達(dá)到 (唯一最優(yōu)解必在一個頂點達(dá)到 或無窮多最優(yōu)解至少在兩個頂點達(dá)到) ;無最優(yōu)解(可行域為空集或目

3、標(biāo)函數(shù)無有限極值)圖解法得出線性規(guī)劃問題解的幾種情況 問題 : 圍成無界區(qū)域就不能有唯一解嗎?解的幾種情況約束條件圖形特點方程特點唯一解一般圍成有限區(qū)域,最優(yōu)值只在一個頂點達(dá)到無窮多解在圍成的區(qū)域邊界上,至少有兩個頂點處達(dá)到最優(yōu)值目標(biāo)和某一約束方程成比例無可行解(無解)圍不成區(qū)域有矛盾方程無界解(無解) 圍成無界區(qū)域, 且無有限最優(yōu)值缺少一必要條件的方程列向量列向量 x=(x1，x2，xn）T為n維列向量。xRn線性相關(guān)線性相關(guān) 一組向量v1,vn,如果有一組不全為零的系數(shù) 1, ,n,使得: 1 v1+nvn=0 則稱v1,vn 是線性相關(guān)的.線性無關(guān)線性無關(guān) 一組向量v1,vn,如果對于任

4、何數(shù)1,n, 若要滿足: 1 v1+nvn=0 ,則必有系數(shù) 1=n=0,(全為零)則稱v1,vn線性無關(guān). 矩陣矩陣A A的秩的秩 設(shè)A為一個mn階矩陣(m0的數(shù)乘（2）式在分別與（1）相加和相減，這樣得到(x1-1)P1+(x2-2)P2+(xk-k)Pk=b(x1+1)P1+(x2+2)P2+(xk+k)Pk=b引理2 若K是有界凸集,則任何 一點XK可表示為K的頂點的凸組合.證明略。必要性（基可行解頂點，逆否命題）：X不是可行域的頂點,故可在可行域內(nèi)找到兩個不同的點x(1),x(2)，使得x=x(1)+(1-)x(2), 0m時,有 xj =xj(1)=xj(2)=0,由于x(1),x

5、(2)是可行域的兩點.應(yīng)滿足 Pjxj(1)=b與Pjxj(2)=b將這兩式相減,即得 Pj(xj(1)-xj(2)=0因X(1)x(2),所以上式系數(shù)(xj(1)-xj(2)不全為零,故向量P1,P2,Pm組線性相關(guān)與假設(shè)矛盾.即X不是基可行解. 若可行域有界,線性規(guī)劃問題的目標(biāo)函數(shù)一定可以在其可行域的頂點上達(dá)到最優(yōu). 證：證：設(shè)X(1),X(2), ,X(k)是可行域的頂點,若X(0)不是頂點且目標(biāo)函數(shù)在X(0)處達(dá)到最優(yōu) z*=CX(0)(不妨設(shè)標(biāo)準(zhǔn)型是z*=maxz),則X(0)可以用頂點表示為 X(0)=iX(i) i0,i=1記X(1),X(2), ,X(k)中使max CX(i)的頂點為X(m)。于是， 由假設(shè)CX(0)為最優(yōu)解，所以CX(0)=CX(m)，即最優(yōu)解可在頂點X(m)達(dá)到。kikimmiiiCXXCXCCX11)()()()0(注：1 有時目標(biāo)函數(shù)可能在多個