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

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

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

3、標(biāo)函數(shù)無(wú)有限極值)圖解法得出線性規(guī)劃問(wèn)題解的幾種情況 問(wèn)題 : 圍成無(wú)界區(qū)域就不能有唯一解嗎?解的幾種情況約束條件圖形特點(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)值缺少一必要條件的方程列向量列向量 x=(x1，x2，xn）T為n維列向量。xRn線性相關(guān)線性相關(guān) 一組向量v1,vn,如果有一組不全為零的系數(shù) 1, ,n,使得: 1 v1+nvn=0 則稱v1,vn 是線性相關(guān)的.線性無(wú)關(guān)線性無(wú)關(guān) 一組向量v1,vn,如果對(duì)于任

4、何數(shù)1,n, 若要滿足: 1 v1+nvn=0 ,則必有系數(shù) 1=n=0,(全為零)則稱v1,vn線性無(wú)關(guān). 矩陣矩陣A A的秩的秩 設(shè)A為一個(gè)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是有界凸集,則任何 一點(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í),有 xj =xj(1)=xj(2)=0,由于x(1),x

5、(2)是可行域的兩點(diǎn).應(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ī)劃問(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*=maxz),則X(0)可以用頂點(diǎn)表示為 X(0)=iX(i) i0,i=1記X(1),X(2), ,X(k)中使max CX(i)的頂點(diǎn)為X(m)。于是， 由假設(shè)CX(0)為最優(yōu)解，所以CX(0)=CX(m)，即最優(yōu)解可在頂點(diǎn)X(m)達(dá)到。kikimmiiiCXXCXCCX11)()()()0(注：1 有時(shí)目標(biāo)函數(shù)可能在多個(gè)