最優(yōu)化方法課件_圖解法和LP基本定理

1、線線 性性 規(guī)規(guī) 劃劃Linear Programming邵紅梅邵紅梅考慮如下約束數(shù)學(xué)規(guī)劃模型考慮如下約束數(shù)學(xué)規(guī)劃模型 maxmin. .( )0,1,2,( )0,1,2,nijf xf xxRs t h xilgxjm或其中其中: : 都是都是線性函數(shù)線性函數(shù). .( ), ( ),( )ijf x h x g x11max (min)( ). .( ,) ,1,2,njjjnijjijf xc xs ta xbiml 即即: :3. LPLP基本定理基本定理4. 單純形法單純形法 1. 圖解法圖解法5. 大大M法法第二章第二章 線性規(guī)劃（線性規(guī)劃（LP）6. LPLP對偶理論（對偶單純形

2、法）對偶理論（對偶單純形法）2.LP2.LP標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形3 37. 靈敏度分析及應(yīng)用靈敏度分析及應(yīng)用確定可行域：確定可行域： 畫約束直線，確定滿足約束條件的半平畫約束直線，確定滿足約束條件的半平面，所有半平面的交集，即為線性規(guī)劃的面，所有半平面的交集，即為線性規(guī)劃的可行域?？尚杏颉４_定目標(biāo)函數(shù)的等值線及優(yōu)化方向確定目標(biāo)函數(shù)的等值線及優(yōu)化方向： 畫一條目標(biāo)函數(shù)等值線，并確定目標(biāo)函數(shù)畫一條目標(biāo)函數(shù)等值線，并確定目標(biāo)函數(shù)優(yōu)化的方向。優(yōu)化的方向。平行移動(dòng)目標(biāo)函數(shù)等值線，通過觀察得平行移動(dòng)目標(biāo)函數(shù)等值線，通過觀察得到線性規(guī)劃的最優(yōu)解。到線性規(guī)劃的最優(yōu)解。圖解圖解法的法的步驟步驟4 4 第一節(jié)第一節(jié) 圖解

3、法圖解法例例1. 用圖解法求解線性規(guī)劃問題用圖解法求解線性規(guī)劃問題二、例題解析二、例題解析5 5121212min23412. .220,1,2jzxxxxs txxxj x1x2o-3X1 -4X2 =-12() Lo： 0 = 2X1 + X2 D此點(diǎn)是唯一最優(yōu)解，此點(diǎn)是唯一最優(yōu)解，且最優(yōu)目標(biāo)函數(shù)值且最優(yōu)目標(biāo)函數(shù)值 min Z=-7可行域可行域6 61222( )xx 163,55解：解：121212min23412. .220,1,2jzxxxxs txxxj 例例2. 1212121212max35.71.910.21.93.8. .1.93.81.93.8zxxxxxxs txxxx

4、 x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）30.6 = 3X1+5.7X2 藍(lán)色線段上的所有點(diǎn)都是最藍(lán)色線段上的所有點(diǎn)都是最優(yōu)解。這優(yōu)解。這種情形為有無窮多最種情形為有無窮多最優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值優(yōu)解，但是最優(yōu)目標(biāo)函數(shù)值max Z=30.6是相同的是相同的。可行域可行域8 8例例2. 1212121212max35.71.910.21.93.8. .1.93.81.93.8zxxxxxxs txxx

5、x x1x2O10203040102030405050可行域是空集可行域是空集無無可行解可行解(即無最優(yōu)解即無最優(yōu)解)121212122401.530. .500,0 xxxxs txxxx max Z=3x1+4x29 9例例3. 2X1 + X2 = 40()X1 +1.5 X2 = 30()X1 + X2 = 50()線性規(guī)劃的圖解法啟示：線性規(guī)劃的圖解法啟示：線性規(guī)劃問題的解有多種情形；線性規(guī)劃問題的解有多種情形；若線性規(guī)劃的可行域非空，則一定是凸若線性規(guī)劃的可行域非空，則一定是凸集（區(qū)域內(nèi)任意兩點(diǎn)連線都在其中）；集（區(qū)域內(nèi)任意兩點(diǎn)連線都在其中）；線性規(guī)劃問題若有最優(yōu)解線性規(guī)劃問題若有

6、最優(yōu)解, ,則最優(yōu)解在可則最優(yōu)解在可行域的某頂點(diǎn)上達(dá)到行域的某頂點(diǎn)上達(dá)到. .優(yōu)缺點(diǎn)優(yōu)缺點(diǎn)簡單、直觀、便于初學(xué)者理解和記憶；簡單、直觀、便于初學(xué)者理解和記憶；僅適用于低維情況，通常適用于含兩個(gè)僅適用于低維情況，通常適用于含兩個(gè)或三個(gè)變量的情況。或三個(gè)變量的情況。1111對于高維情況對于高維情況, 怎么求解呢怎么求解呢? - 單純形法單純形法 第二節(jié)第二節(jié) 線性規(guī)劃的標(biāo)準(zhǔn)形線性規(guī)劃的標(biāo)準(zhǔn)形1212線性規(guī)劃的形式線性規(guī)劃的形式是多種多樣的是多種多樣的: 目標(biāo)函數(shù)求極大目標(biāo)函數(shù)求極大( (極小極小);); 約束可能有等式約束約束可能有等式約束, 也可能有不等式約束也可能有不等式約束; 決策變量有的受

7、非負(fù)約束決策變量有的受非負(fù)約束,有的是無限制有的是無限制. 為了方便研究為了方便研究, 考慮將各種形式的考慮將各種形式的LPLP化為一種統(tǒng)一化為一種統(tǒng)一的形式的形式, 這種形式即被稱為這種形式即被稱為LPLP的標(biāo)準(zhǔn)形式的標(biāo)準(zhǔn)形式. .11min. .,1,2,0,1,2,njjjnijjijjzc xs ta xbimxjn 1313一、一、LP標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形三大特點(diǎn)三大特點(diǎn)目標(biāo)函數(shù)：目標(biāo)函數(shù)：min約束條件：約束條件：=變量符號：變量符號：0二、化二、化LPLP為標(biāo)準(zhǔn)型的方法為標(biāo)準(zhǔn)型的方法1414min fz 15)nijjija xb 0.ix 其其中中稱稱為為弛弛變變量量松松16)nijj

8、ija xb 0.ix 其其稱稱為為剩剩余余中中變變量量2)(0)jjjxh h4)jx 的的符符號號無無限限制制0,0,jjjjjjyyxyyx 引引入入令令代代入入模模型型消消去去,0;jjjjyxhy引引入入則則10,nijjijiixxa xb 10,inijjiija xbxx 1) max z3)0jx ,0;jjjyxy 令令則則1515例例1121212121max23674. .230zxxxxxxs txxx 2. 舉例舉例分析分析: :共有共有4 4處不符合處不符合標(biāo)準(zhǔn)形的要求標(biāo)準(zhǔn)形的要求. .1)fz 令令12min fxx 23434),0,0 xxxxx2 2 令令

9、2,x并并將將上上式式代代入入原原模模型型 消消去去),3 3 對對于于不不等等式式約約束束條條件件 分分別別引引入入松松弛弛變變量量和和剩剩余余變變量量將將它它們們化化為為等等式式約約束束. .解解: :161613413413413546min2336774. .230,1,3,4,5,6jxfxxxxxxxxxxs txxxxj 則相應(yīng)的標(biāo)準(zhǔn)形為則相應(yīng)的標(biāo)準(zhǔn)形為56, x, x.其其中中為為松松弛弛變變量量為為剩剩余余變變量量1717例例21212121212max54351525. .22110,0zxxxxxxs txxxx 分析分析: :共有共有5 5處不符合處不符合標(biāo)準(zhǔn)形的要求標(biāo)

10、準(zhǔn)形的要求. .1)fz 令令1254min fxx 323),0 xxx 2 2 令令則則2,x并并將將上上式式代代入入原原模模型型 消消去去),3 3 對對于于不不等等式式約約束束條條件件 分分別別引引入入松松弛弛變變量量和和剩剩余余變變量量將將它它們們化化為為等等式式約約束束. .解解: :181851313134136min54351525. .22110,1,3,4,5,6jxxxfxxxxxxs txxxj 則相應(yīng)的標(biāo)準(zhǔn)形為則相應(yīng)的標(biāo)準(zhǔn)形為465,.xxx其其中中和和 為為松松弛弛變變量量為為剩剩余余變變量量第三節(jié) LP基本定理 將將LPLP化為標(biāo)準(zhǔn)形后化為標(biāo)準(zhǔn)形后,如何求最優(yōu)解呢

11、如何求最優(yōu)解呢? 有一個(gè)定理給出了這個(gè)問題的答案有一個(gè)定理給出了這個(gè)問題的答案, 這就是這就是LPLP基本定理基本定理.2020 LP標(biāo)準(zhǔn)形的矩陣形式標(biāo)準(zhǔn)形的矩陣形式min. .0TzC Xs tAXbX 其中其中 121212,(),TTnnTijm nmCcccXxxxAabb bb 11min. .,1,2,0,1,2,njjjnijjijjzc xs ta xbimxjn 2121 考慮具有標(biāo)準(zhǔn)形的考慮具有標(biāo)準(zhǔn)形的LP:LP:一、線性規(guī)劃的基本概念一、線性規(guī)劃的基本概念min.0TfC XAXbs tX 約束系數(shù)矩陣約束系數(shù)矩陣A是是mn 矩陣矩陣, mn，并且，并且 r (A)m.

12、當(dāng)當(dāng) mn 時(shí)，基矩陣唯一時(shí)，基矩陣唯一; 當(dāng)當(dāng) m n 時(shí)，基矩陣就可時(shí)，基矩陣就可能有多個(gè)，但數(shù)目不超過能有多個(gè)，但數(shù)目不超過 個(gè)。個(gè)。mnC1. 基矩陣基矩陣: 若若A中的中的mm子矩陣子矩陣B滿足滿足 r (B)m, 即即則稱則稱B是是LPLP問題的一個(gè)基矩陣（簡稱為問題的一個(gè)基矩陣（簡稱為基基）。）。 0,B 于是于是A中至少有一個(gè)中至少有一個(gè)mm子矩陣子矩陣B，使得：使得：r (B)m。約束方程的系數(shù)矩陣為約束方程的系數(shù)矩陣為：511 1010620 1A 91001B710,21B811,20B610,61B151,10 6B251,10 0B350,10 1B41162B51

13、1,6 0B1234123553.106220 ,1,5jxxxxs txxxxxj 例例1 1 設(shè)設(shè)123min42fxxx 易看出易看出 r（A）=2，2 階子矩陣有階子矩陣有 = 10個(gè)，而基矩陣只有個(gè)，而基矩陣只有9個(gè)，個(gè)，25C222210101051,0 ,102BBB不不是是基基。但但對對于于：由由于于故故2. 基向量基向量: 基矩陣對應(yīng)的列向量稱為基向量基矩陣對應(yīng)的列向量稱為基向量，其余列向量稱其余列向量稱為非基向量為非基向量. 3. 基變量基變量: 基向量對應(yīng)的變量稱為基變量，非基向量對應(yīng)的變基向量對應(yīng)的變量稱為基變量，非基向量對應(yīng)的變量稱為量稱為非基變量非基變量(自由變量自

14、由變量)。例如例如：對于基：對于基B2而言，而言，x1 , x4是基變量，是基變量，x2 , x3 , x5是非基變量。是非基變量。251,10 0B511 1010620 1Ax1 x4思考思考：基變量的選取唯一嗎？取法有多少種？：基變量的選取唯一嗎？取法有多少種？【注注】基變量、非基變量是針對某一確定基而言的，不同的基基變量、非基變量是針對某一確定基而言的，不同的基對應(yīng)的基變量和非基變量也不同。對應(yīng)的基變量和非基變量也不同。 4. 基本解基本解: 對于某一確定的基對于某一確定的基B，令，令所有的自由變量等于零所有的自由變量等于零, 求出求出 Ax=b的解，稱這組解為的解，稱這組解為LP問題

15、的關(guān)于基問題的關(guān)于基 的基本解。的基本解。 5. 基可行解基可行解: 非負(fù)的基本解稱為基可行解（基本可行解）非負(fù)的基本解稱為基可行解（基本可行解）.【注注】基可行解基可行解也被定義為也被定義為“可行的基本解可行的基本解”。 2424注注: 基變量的選取方式基變量的選取方式 有限有限, 所以基本解的個(gè)數(shù)也為所以基本解的個(gè)數(shù)也為有限個(gè)有限個(gè).mnC 可見：可見：求基可行解要先求基本解求基可行解要先求基本解, 然后看是否非負(fù)即可。然后看是否非負(fù)即可。 另外，基本可行解也一定為有限個(gè)。另外，基本可行解也一定為有限個(gè)。 二、基本解的求法二、基本解的求法例例1 1 求求134123246.350 ,1,4

16、jxxxs txxxxj 1234min324zxxxx的一個(gè)基本解和一個(gè)基本可行解的一個(gè)基本解和一個(gè)基本可行解. .解解: : 約束方程的增廣矩陣約束方程的增廣矩陣20416( , )11305A b x2 x4 注意到注意到A是是24矩陣矩陣, ,r(Ar(A) )2.2.由于第由于第2 2列和第列和第4 4列線性無關(guān)列線性無關(guān), ,構(gòu)成一個(gè)構(gòu)成一個(gè)2 2階單位子塊階單位子塊，因此可構(gòu)成一個(gè)基矩陣因此可構(gòu)成一個(gè)基矩陣. .24,xx取取為基變量為基變量, ,13,xx為自由變量為自由變量, ,表示基變量得如下同解方程組表示基變量得如下同解方程組: :21353xxx 4136 24xxx

17、用自由變量用自由變量213413536 24xxxxxx 130:xx令令得得 0, 5, 0, 6Tx 又因該解非負(fù)，所以又是一個(gè)基本可行解。又因該解非負(fù)，所以又是一個(gè)基本可行解。思考思考: 若基變量選為其他變量時(shí)若基變量選為其他變量時(shí),如何求基本解呢如何求基本解呢?啟發(fā)啟發(fā): 若系數(shù)矩陣中含有若系數(shù)矩陣中含有m階單位子塊很容易求基本解階單位子塊很容易求基本解.于是，得一個(gè)基本解：于是，得一個(gè)基本解：245,6xx三、線性規(guī)劃的基本定理三、線性規(guī)劃的基本定理考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題考慮標(biāo)準(zhǔn)形式的線性規(guī)劃問題min. .0TzCXs tAXbX ( )r Amn 12,TnnXx xxR 12,Tnnbb bbR 2828定理定理3.1（2）線性規(guī)劃問題若有最優(yōu)解，那么一定）線性規(guī)劃問題若有最優(yōu)解，那么一定有最優(yōu)的基本可行解。有最優(yōu)的基本可行解。（1）線性規(guī)劃問題若有可行解，那么一定）線性規(guī)劃問題若有可行解，那么一定 有基本可行解。有基本可行解。定理定理3.2 線性規(guī)劃問題的