線性規(guī)劃_運籌學

1、 交通運輸與物流工程專業(yè) 運 籌 學 教 程 同濟大學 交通運輸工程學院 2006 運籌學定義；運籌學定義； 運籌學主要分支；運籌學主要分支； 運籌學研究步驟；運籌學研究步驟； 緒 論 教學要求教學要求 運籌學發(fā)展簡介；運籌學發(fā)展簡介； 關(guān)鍵詞： 系統(tǒng)（研究對象）； 決策優(yōu)化（研究任務(wù)）； 定量分析技術(shù)（研究方法）； 1 1、運籌學定義、運籌學定義 系統(tǒng)優(yōu)化技術(shù)系統(tǒng)優(yōu)化技術(shù); 系統(tǒng)決策優(yōu)化的定量分析技術(shù)系統(tǒng)決策優(yōu)化的定量分析技術(shù)。 系 統(tǒng) 指由相互關(guān)聯(lián)、相互制約、相互作 用的要素按照一定的結(jié)構(gòu)組成的具有特定功 能和性能特征的有機整體。 決策優(yōu)化 決策概念（方案選擇）； 決策民主化和科學化 （智

2、囊與領(lǐng)導、定性與定量）； 決策優(yōu)化（絕對與相對）； 定量化分析技術(shù) 數(shù)學建模技術(shù)； （運籌學方法精髓） 模型優(yōu)化算法； （模型運算及分析） 計算機數(shù)據(jù)庫技術(shù)等； （大規(guī)模問題的計算機求解） 運籌學運籌學/ Operations Research，英文英文原意是原意是作作 戰(zhàn)研究、運用研究戰(zhàn)研究、運用研究。 起源于二次大戰(zhàn)的起源于二次大戰(zhàn)的軍事軍事領(lǐng)域領(lǐng)域， 發(fā)揚于戰(zhàn)后的發(fā)揚于戰(zhàn)后的社會社會、經(jīng)濟、工程與管理經(jīng)濟、工程與管理 領(lǐng)域領(lǐng)域。 2 2、運籌學發(fā)展簡介、運籌學發(fā)展簡介 （英）希（英）希 爾：高射炮系統(tǒng)利用研究爾：高射炮系統(tǒng)利用研究 ； （英）莫爾斯：美海軍大西洋護航方案研究；（英）莫爾斯

3、：美海軍大西洋護航方案研究； （英）空軍（英）空軍OR小組：雷達警報和控制系統(tǒng)研究；小組：雷達警報和控制系統(tǒng)研究； 1948年，美國年，美國MIT率先開設(shè)了運籌學課程；率先開設(shè)了運籌學課程； 1950年，美國出版了第一份運籌學雜志；年，美國出版了第一份運籌學雜志； 1951年，美國年，美國 P.M.Morse與G.E.Kimball出版出版 了運籌學方法專著，全面總結(jié)了二次大戰(zhàn)中了運籌學方法專著，全面總結(jié)了二次大戰(zhàn)中 運籌學的軍事應(yīng)用。運籌學的軍事應(yīng)用。 目前，運籌學已廣泛應(yīng)用到現(xiàn)代社會、經(jīng)濟、目前，運籌學已廣泛應(yīng)用到現(xiàn)代社會、經(jīng)濟、 工程和管理等各個領(lǐng)域。工程和管理等各個領(lǐng)域。 人口、庫存、

4、廠址定位、資源分配、能人口、庫存、廠址定位、資源分配、能 源建設(shè)源建設(shè)；設(shè)計、生產(chǎn)、可靠性、服務(wù)設(shè)計、生產(chǎn)、可靠性、服務(wù)；搜索、控搜索、控 制、比賽對抗和軍事對抗等；制、比賽對抗和軍事對抗等； 在交通領(lǐng)域已廣泛應(yīng)用于交通規(guī)劃、工在交通領(lǐng)域已廣泛應(yīng)用于交通規(guī)劃、工 程建設(shè)、運營管理、物流配送等各個階段；程建設(shè)、運營管理、物流配送等各個階段； 。數(shù)學規(guī)劃。數(shù)學規(guī)劃 線性規(guī)劃；非線性規(guī)劃；線性規(guī)劃；非線性規(guī)劃； 整數(shù)規(guī)劃；目標規(guī)劃；整數(shù)規(guī)劃；目標規(guī)劃； 動態(tài)規(guī)劃；組合規(guī)劃；動態(tài)規(guī)劃；組合規(guī)劃； 。網(wǎng)絡(luò)優(yōu)化技術(shù)；。網(wǎng)絡(luò)優(yōu)化技術(shù)； 。排隊論與庫存論；。排隊論與庫存論； 。對策論與決策論；。對策論與決策論

5、； 。搜索論與可靠性理論；。搜索論與可靠性理論； 。系統(tǒng)模擬等；。系統(tǒng)模擬等； 3 3、運籌學主要分支、運籌學主要分支 （1）系統(tǒng)調(diào)查與分析，建立系統(tǒng)框架；）系統(tǒng)調(diào)查與分析，建立系統(tǒng)框架； （2）構(gòu)建數(shù)學模型，描述決策問題；）構(gòu)建數(shù)學模型，描述決策問題； （3）探索模型求解的結(jié)構(gòu)并導出系統(tǒng)）探索模型求解的結(jié)構(gòu)并導出系統(tǒng) 的求解過程；的求解過程； （4）尋求系統(tǒng)最優(yōu)解及信息，供決策參考。）尋求系統(tǒng)最優(yōu)解及信息，供決策參考。 4 4、運籌學研究步驟、運籌學研究步驟 （1）掌握運籌學）掌握運籌學模型建立的基本技術(shù)模型建立的基本技術(shù)； （2）掌握運籌學）掌握運籌學模型求解的基本算法模型求解的基本算法；

6、 （3）熟練）熟練求解教材各章節(jié)的習題求解教材各章節(jié)的習題； （4）嚴禁無故曠課、遲到和早退嚴禁無故曠課、遲到和早退； （5）獨立、按時完成練習與作業(yè)獨立、按時完成練習與作業(yè)； 5 5、教學要求、教學要求 第一章 線性規(guī)劃（LP） 線性規(guī)劃問題及其模型建立； 兩元線性規(guī)劃問題圖解法； 線性規(guī)劃代數(shù)解的概念； 線性規(guī)劃問題的幾何特征； 線性規(guī)劃單純形算法； 第第1 1節(jié)節(jié) 線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃問題及其數(shù)學模型 1、線性規(guī)劃問題 2、線性規(guī)劃建模范例 3、線性規(guī)劃數(shù)學模型 引例引例11：資源配置問題資源配置問題 現(xiàn)有甲、乙兩種產(chǎn)品要在車間現(xiàn)有甲、乙兩種產(chǎn)品要在車間A A和車間和車間B

7、B加工，加工， 有關(guān)資料如下表。問：如何組織甲乙兩種產(chǎn)品的生有關(guān)資料如下表。問：如何組織甲乙兩種產(chǎn)品的生 產(chǎn)，使利潤最大？產(chǎn)，使利潤最大？ 產(chǎn)品在A車間 加工時數(shù) 在B車間 加工時數(shù) 單位 產(chǎn)品利潤 市場 容量限制 甲216/ 乙114=7 車間可用 工時 108 1 1、線性規(guī)劃問題、線性規(guī)劃問題 引例引例22：成本優(yōu)化問題成本優(yōu)化問題 某養(yǎng)雞廠的混合飼料由某養(yǎng)雞廠的混合飼料由A A、B B、C C三種配料組成三種配料組成 ，主要包括，主要包括D D、E E、F F三種營養(yǎng)成分，有關(guān)資料如下三種營養(yǎng)成分，有關(guān)資料如下 表。問：如何配置混合飼料，以使總成本最低？表。問：如何配置混合飼料，以使總

8、成本最低？ 配料/營養(yǎng)DEF單位成本單位成本 A11/226 B11/213 C11/412 每份飼料 營養(yǎng)標準 20610 引例引例33：運輸優(yōu)化問題運輸優(yōu)化問題 運輸問題有關(guān)資料如下表，在滿足各電廠發(fā)電用運輸問題有關(guān)資料如下表，在滿足各電廠發(fā)電用 煤的條件下，如何確定配送方案，使總運費最??？煤的條件下，如何確定配送方案，使總運費最?。?單位運價單位運價 （Cij） B1B2B3供應(yīng)量供應(yīng)量 A1 21350 A2 22430 需求量 401525 基本概念：基本概念： （1）決策變量；（2）目標函數(shù)； （3）約束條件；（4）非負約束。 線性規(guī)劃的基本特征線性規(guī)劃的基本特征: : （1）問題

9、的目標函數(shù)可以表示為一組決策 變量的線性函數(shù)； （2）問題的約束條件，可以用線性等式或 不等式表示。 具有上述特征的優(yōu)化問題，稱之為線性具有上述特征的優(yōu)化問題，稱之為線性 規(guī)劃問題（規(guī)劃問題（Linear Linear ProgramingPrograming ： LP LP ） 概念總結(jié)概念總結(jié) 例例1 1 合理利用線材問題合理利用線材問題 現(xiàn)在要做現(xiàn)在要做100100套鋼架，套鋼架， 每套用長每套用長2.92.9m m，2.1m2.1m，和和1.51.5m m的圓鋼。已知原料為的圓鋼。已知原料為 長長7.47.4m m的圓鋼，問如何合理利用的圓鋼，問如何合理利用7.47.4m m的圓鋼原料

10、，的圓鋼原料， 可以使原料最??？可以使原料最??？ 長度（長度（m) m) (1) (2) (3) (4) (5) (6) (7) (8)(1) (2) (3) (4) (5) (6) (7) (8) 2.9 2 1 1 1 0 0 0 0 2.9 2 1 1 1 0 0 0 0 2.1 0 2 1 0 3 2 1 0 2.1 0 2 1 0 3 2 1 0 1.5 1 0 1 3 0 2 3 4 1.5 1 0 1 3 0 2 3 4 剩料剩料( (m) 0.1 0.3 0.9 0 1.1 0.2 0.8m) 0.1 0.3 0.9 0 1.1 0.2 0.8 1 1.4.4 套裁方案套裁方案

11、 2 2、線性規(guī)劃建模范例、線性規(guī)劃建模范例 設(shè)按第設(shè)按第i i套方案下料的原材料根數(shù)為套方案下料的原材料根數(shù)為X Xi i，i=1,i=1,5;,5; 則線性規(guī)劃模型如下則線性規(guī)劃模型如下： S.T. 2XS.T. 2X1 1 +X +X2 2 +X +X3 3 +X +X4 4 =100 =100 2X 2X2 2 +X +X3 3 + 3X + 3X5 5 +2X +2X6 6 + X + X7 7 =100 =100 X X1 1 + X + X3 3 + 3X + 3X4 4 +2X +2X6 6 +3X +3X7 7 +4X +4X8 8 =100 =100 X X1 1, X,

12、X2 2, X, X3 3, X, X4 4, X, X5 5 , X , X6 6, X, X7 7, X, X8 8 =0 =0 Min Z=0XMin Z=0X1 1+0.3X+0.3X2 2+0.9X+0.9X3 3+1.1X+1.1X5 5+0.2X+0.2X6 6 + + 0.8X 0.8X7 7+1.4X+1.4X8 8 Min Z= XMin Z= X1 1 +X +X2 2 +X +X3 3 +X +X4 4 +X +X5 5 +X +X6 6 +X +X7 7 +X +X8 8 X X* *= (30 ,10, 0, 50, 0 ,0 ,0 ,0)= (30 ,10, 0,

13、 50, 0 ,0 ,0 ,0)T T Z Z* * =90 =90 S.T. 2XS.T. 2X1 1 +X +X2 2 +X +X3 3 +X +X4 4 =100 =100 2X 2X2 2 +X +X3 3 + 3X + 3X5 5 +2X +2X6 6 + X + X7 7 =100 =100 X X1 1 + X + X3 3 + 3X + 3X4 4 +2X +2X6 6 +3X +3X7 7 +4X +4X8 8 =100 =100 X X1 1, X, X2 2, X, X3 3, X, X4 4, X, X5 5 , X , X6 6, X, X7 7, X, X8 8 =

14、0 =0 例例2 2 連續(xù)投資問題連續(xù)投資問題 某部門在今后某部門在今后5 5年內(nèi)考慮投資以下年內(nèi)考慮投資以下A A，B B，C C，D D項目項目。 項目項目A A：從第一年到第四年每年年初需要投資，從第一年到第四年每年年初需要投資， 并于次年末收回本利并于次年末收回本利115%115%； 項目項目B B：從第三年初需要投資，到第五年末收回從第三年初需要投資，到第五年末收回 本利本利125%125%，但規(guī)定最大投資額不超過，但規(guī)定最大投資額不超過4 4萬元；萬元； 項目項目C C：第二年初需要投資，到第五年末收回本第二年初需要投資，到第五年末收回本 利利140%140%，但規(guī)定最大投資額不超

15、過，但規(guī)定最大投資額不超過3 3萬元；萬元； 項目項目D D：五年內(nèi)每年年初可購買公債，于當年末五年內(nèi)每年年初可購買公債，于當年末 歸還，加息歸還，加息6%6%； 該部門現(xiàn)有資金該部門現(xiàn)有資金1010萬元，問如何確定投資方案，萬元，問如何確定投資方案， 使到第五年末擁有的資金總額最大使到第五年末擁有的資金總額最大 ？ 設(shè)設(shè)X Xij ij第 第i i年初分配給給項目年初分配給給項目j j的投資額，的投資額，i=1,i=1,5;,5; j=A,B,C,Dj=A,B,C,D，則投資方案表示如下如下則投資方案表示如下如下： 項目項目 （1 1） （2 2） （ （3 3） （ （4 4） （ （5

16、5） A X A X1A 1A X X2A 2A X X3A 3A X X4A 4A B X B X3B 3B C X C X2C 2C D X D X1D 1D X X2D 2D X X3D 3D X X4D4D X X5D 5D 年初年初 S.T. XS.T. X1A 1A + X + X1D 1D =100000 =100000 -1.06 X -1.06 X1D 1D + + X X2A 2A + + X X2C 2C + + X X2D 2D =0 =0 -1.15 X -1.15 X1A 1A -1.06X -1.06X2D 2D+ + X X3A 3A +X +X3B 3B+ +

17、 X X3D3D =0 =0 -1.15 X -1.15 X2A 2A-1.06X -1.06X3D 3D+ + X X4A 4A + + X X4D4D =0 =0 -1.15 X -1.15 X3A 3A-1.06X -1.06X4D 4D+ + X X5D5D =0 =0 X X2C 2C =3000 =3000 X X3B 3B =4000 =0 =0，i=1,i=1,5;j=A,B,C,D,5;j=A,B,C,D， Max Z=1.15 XMax Z=1.15 X1A 1A +1.40 X +1.40 X2C 2C +1.25 X +1.25 X3B 3B +1.06X +1.06X

18、5D 5D X X1A 1A* *=34783, =34783, X X1D 1D* *=65217; =65217; X X2A 2A* *=39130, =39130, X X2C 2C* *=30000, =30000, X X2D 2D* *=0; =0; X X3A3A* *=0, =0, X X3B 3B* *=40000, =40000, X X3D 3D* *=0; X =0; X4A 4A* *=45000, X =45000, X4D 4D* *=0; X =0; X5D 5D* *=0. =0. 練習與習題練習與習題 目標函數(shù) ：max，min 約束條件：,=, 變量符號

19、：0, =0, 0 , unr 3 3、線性規(guī)劃數(shù)學模型、線性規(guī)劃數(shù)學模型 線性規(guī)劃一般型線性規(guī)劃一般型 Max(Min) z= cMax(Min) z= c1 1x x1 1+ c+ c2 2x x2 2 + + + c cj jx xj j + +c cn nx xn n a a11 11x x1 1+a +a12 12x x2 2+ +a +a1j 1jx xj j+ +a a1n1nx xn n (=, =,) b b1 1 a ai1 i1x x1 1+a +ai2 i2x x2 2+ + +a aijijx xj j+ +a aininx xn n (=, =,) b bi i a

20、 am1 m1x x1 1+a +am2 m2x x2 2+ + +a amjmjx xj j+ +a amnmnx xn n (=, =,) b bm m x xj j (=,=,) 0, j=1,2,0, j=1,2,n,n x xj j (=,=,) 0, j=1,2,0, j=1,2,n,n 1 n jj j C x Max(Min) z=Max(Min) z= 1 ( ,) n ijji j a xb i=1,2,i=1,2,m,m 若令：若令：A A.j .j=(a =(a1j 1j,a ,a2j 2j, , ,a amjmj) )T T， ， b=(b b=(b1 1,b,b2

21、2, , ,b bm m) )T T x xj j (=,=,) 0, j=1,2,0, j=1,2,n,n 1 n jj j C x Max(Min) z=Max(Min) z= 1 .( ,) n jj j Axb unr0，X b (=) AX . t . s XCzmax(min) T (=) 令令 C=(cC=(c1 1,c,c2 2, , ,c cj j, ,c cn n) )T T ; X=(x ; X=(x1 1,x,x2 2, , ,x xj j, ,x xn n) )T T a a11 11 a a12 12 a a1j 1j a a1n 1n A A = a = a21

22、21 a a22 22 a a2j 2j a a2n 2n ; ; a am1m1 a am2 m2 a amjmj a amnmn 目標函數(shù)：min 約束條件：= 變量符號：0 右邊常數(shù)：b0 線性規(guī)劃的標準型線性規(guī)劃的標準型 Min z= cMin z= c1 1x x1 1+ c+ c2 2x x2 2 + + + c cj jx xj j + +c cn nx xn n a a11 11x x1 1+a +a12 12x x2 2+ +a +a1j 1jx xj j+ +a a1n1nx xn n =b =b1 1 a ai1 i1x x1 1+a +ai2 i2x x2 2+ + +

23、a aijijx xj j+ +a aininx xn n =b =bi i a am1 m1x x1 1+a +am2 m2x x2 2+ + +a amjmjx xj j+ +a amnmnx xn n = =b bm m x xj j 0, j=1,2,0, j=1,2,n,n 0X bAX. t . s XCzmin T x xj j 0, j=1,2,0, j=1,2,n,n 1 n jj j C x Min z=Min z= 1 n ijji j a xb i=1,2,i=1,2,m,m x xj j 0, j=1,2,0, j=1,2,n,n 1 n jj j C x Min z

24、=Min z= 1 . n jj j Axb 線性規(guī)劃模型的標準化線性規(guī)劃模型的標準化 （1 1）MaxMin;MaxMin; (2) (2) 約束：松弛變量；約束：松弛變量； (3) (3) 約束：剩余變量；約束：剩余變量； (4) (4) 自由變量：非負變量；自由變量：非負變量； 練習練習1 1 Max Z=-2XMax Z=-2X1 1+X+X2 2-X-X3 3 s.t. X s.t. X1 1+3X+3X2 2-X-X3 3=30=12=12 X X1 1-4X-4X2 2-4X-4X3 3=2=2 X X1 1=0,X=0,X2 2=0,XB)BB) = 進基變量 離基變量 目標函

25、數(shù) 約束條件 右邊常數(shù) = = 目標函數(shù) 約束條件 新的基矩陣 右邊常數(shù) = = 進基變量 離基變量 目標函數(shù) 約束條件 基矩陣 = = 目標函數(shù) 約束條件 新的基矩陣 右邊常數(shù) = 第第4 4節(jié)節(jié) 線性規(guī)劃的幾何特征線性規(guī)劃的幾何特征 定理定理1 1：( (LP)LP)問題的可行域問題的可行域K=X|AX=b,X=0K=X|AX=b,X=0為為凸集凸集； 定理定理2 2：若若( (LP)LP)問題的可行域問題的可行域K K非空，則必有非空，則必有極點極點； 定理定理3 3：( (LP)LP)問題的基本可行解問題的基本可行解X X對應(yīng)于可行域?qū)?yīng)于可行域K K的的 極點；極點； 定理定理4 4

26、：( (LP)LP)問題若有最優(yōu)解問題若有最優(yōu)解X X* *，則一定可以在可行則一定可以在可行 域域K K的極點上找到。的極點上找到。 max z=x1+3x2D s.t. x1+ x2+x3=6 B -x1+2x2 +x4=8 x4=0 C x3=0 x1, x2,x3,x40 x1=0 E O x2=0 A OABCDE 基變量 x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3 非基變量 x1 x2x2 x3x3 x4x1 x4x1 x3x2 x4 xj0-x4x1 基本可行解是是是是否否 線性規(guī)劃的幾何特征線性規(guī)劃的幾何特征代數(shù)解之間的關(guān)系：代數(shù)解之間的關(guān)系： 滿足一個不等式

27、約束的解 滿足一組不等式約束的解： 可行解的集合 幾何概念代數(shù)概念 約束直線滿足一個等式約束的解 約束半平面 約束半平面的交集： 凸多邊形 約束直線的交點基本解 可行域的極點基本可行解 目標函數(shù)等值線： 一組平行線 目標函數(shù)值等于一個常 數(shù)的解 基變換 可行域相鄰極 點之間的變換 第第5 5節(jié)節(jié) 線性規(guī)劃的單純形算法（線性規(guī)劃的單純形算法（1 1） 算法思想算法思想 初始基本可行解求法初始基本可行解求法 關(guān)于關(guān)于X XB B的典式與單純形表的典式與單純形表 算法規(guī)則算法規(guī)則 基本算法步驟基本算法步驟 算法思想算法思想可行域可行域K K相鄰頂點迭代搜索相鄰頂點迭代搜索X X* * 確立初始基本可

28、行解確立初始基本可行解：X0 X 最優(yōu)？ X0 X， ， Y N X迭代至相鄰頂點迭代至相鄰頂點X|Z(X)=Z(X) X*結(jié)束 XX0 初始基本可行解求法初始基本可行解求法 1 1：“= ”= ”型約束（型約束（LPLP）問題；問題； Min z=cMin z=c1 1x x1 1+c+c2 2x x2 2+ + +c cn nx xn n s.t. as.t. a11 11x x1 1+a +a12 12x x2 2+ +a +a1n 1nx xn n= =b b1 1 a a21 21x x1 1+a +a22 22x x2 2+ +a +a2n 2nx xn n= =b b2 2 a

29、am1 m1x x1 1+a +am2 m2x x2 2+ + +a amnmnx xn n = =0=0 Min z=c Min z=c1 1x x1 1+c+c2 2x x2 2+ + +c cn nx xn n s.t. as.t. a11 11x x1 1+a +a12 12x x2 2+ +a +a1n 1nx xn n + +x xn n+1+1 =b =b1 1 a a21 21x x1 1+a +a22 22x x2 2+ +a +a2n 2nx xn n + +x xn n+2+2 =b =b2 2 a am1 m1x x1 1+a +am2 m2x x2 2+ +.+ .+

30、a amn mnx xn n + +x xn n+m+m= =b bm m x x1 1,x,x2 2, , , x xn n, ,x xn n+1, +1,x xn n+2,+2, ,x xn n+m+m=0 =0 取取X XB B= =（X Xn n+1 +1, ,X Xn n+2+2, , ,X Xn n+m+m) )T T， ，令令X XD D= =（X X1 1 , , , ,x xn n）T T =0 =0 則則X =X =（b b1 1,b,b2 2, , ,b bm m,0,0,0,0,0),0)T T 為初始基本可行解 為初始基本可行解X X0 0 初始基本可行解求法初始基本

31、可行解求法 2 2： “ “=”“=”“或或=” =” 型約束（型約束（LPLP）問題；問題； 見后續(xù)的大見后續(xù)的大M M法和兩階段法法和兩階段法 初始基本可行解求法初始基本可行解求法 （LPLP）關(guān)于關(guān)于X XB B的典式與單純形表的典式與單純形表典式典式 考察標準型（考察標準型（LPLP）問題問題： 0X bAX. t . s XCzmin T 設(shè)設(shè) X XB B= =（X XB1 B1, , ,X XBiBi, , ,X XBmBm) )T T X XD D= =（X XD1 D1, , ,X Xj j, , ,X XDnDn-m-m) )T T A=(B D) C A=(B D) CT

32、 T=(C=(CB BT T C CD DT T) ) 考察約束方程組：考察約束方程組： AX=b AX=b (B D|b) (B D|b) B B-1 -1 (B D|b) (B D|b) (E B (E B-1 -1 D D | B | B-1 -1 b) b) 取取: :B B-1 -1 D D =Y =Y , , B B-1 -1 b= b b= b (E Y|b)(E Y|b) EX EXB B+YX+YXD D=b =b i.e. Xi.e. XB B+YX+YXD D=b=b 等價變換后的約束方程組展開如下：等價變換后的約束方程組展開如下： X XB1 B1 +y +y1D1 1

33、D1X XD1 D1 + + +y +y1j 1jX Xj j + +y y1Dn- 1Dn-m mX XDnDn-m-m=b =b1 1 X XBi Bi +y +yiD1 iD1X XD1 D1 + + + +y yij ijX Xj j + +y yiDn iDn- -m mX XDnDn-m-m=b =bi i X XBm Bm +y +ymD1 mD1X XD1 D1 + + + +y ymj mjX Xj j + +y ymDn mDn- -m mX XDnDn-m-m= =b bm m （LPLP）關(guān)于關(guān)于X XB B的典式與單純形表的典式與單純形表典式典式 令：令： Z Z0

34、0 = C = CB BT T B B-1 -1 b b ， r rD D=C=CD DT T-C-CB BT T B B-1 -1 D D 則：則： Z = ZZ = Z0 0 + + r rD DT T X XD D 等價變換后的目標函數(shù)展開如下：等價變換后的目標函數(shù)展開如下： Z = ZZ = Z0 0 + r + rD1 D1 X XD1D1+ + + r rj jX Xj j + + + r rDnDn-m -m X XDnDn-m-m （LPLP）關(guān)于關(guān)于X XB B的典式與單純形表的典式與單純形表典式典式 考察目標函數(shù)的等價變換：考察目標函數(shù)的等價變換： 因：因：Z=CZ=CT

35、TX=CX=CB BT TX XB B+C+CD DT TX XD D； ； X XB B = = B B-1 -1 b B b B-1 -1 D D X XD D 所：所： Z = CZ = CB BT T B B-1 -1 b + b +（ C CD DT T-C-CB BT T B B-1 -1 D D ） ）X XD D （LPLP）標準型關(guān)于標準型關(guān)于X XB B等價變換如下：等價變換如下： Min Min Z = ZZ = Z0 0+r+rD1 D1 X XD1D1+ + + r rj jX Xj j + + + r rDnDn-m -m X XDnDn-m-m X XB1 B1

36、+y +y1D1 1D1X XD1 D1 + + +y +y1j 1jX Xj j + +y y1Dn- 1Dn-m mX XDnDn-m-m=b =b1 1 X XBi Bi +y +yiD1 iD1X XD1 D1 + + + +y yij ijX Xj j + +y yiDn iDn- -m mX XDnDn-m-m=b =bi i X XBm Bm +y +ymD1 mD1X XD1 D1 + + + +y ymj mjX Xj j + +y ymDn mDn- -m mX XDnDn-m-m= =b bm m x xB1 B1,x ,xB2 B2, , ,x xBmBm, , x x

37、D1D1,x ,xD2 D2, , ,x xDnDn-m,-m,=0 =0 （LPLP）關(guān)于關(guān)于X XB B的典式與單純形表的典式與單純形表典式典式 i.e.i.e. Min Min Z = ZZ = Z0 0+ + s.t. s.t. X XBi Bi + = b + = bi i i=1,2,m X Xj j=0|=0| 稱為（稱為（LPLP）關(guān)于關(guān)于X XB B的典式。的典式。 D ijj j I y X D jJ j I r X D j I 特征：特征：X X/ /Z Z均可由非基本變量均可由非基本變量X XD D線性表示。線性表示。 功能：功能：X X/ /Z Z均可依據(jù)典式令均可依

38、據(jù)典式令X XD D=0=0直接寫出。直接寫出。 令：令：W=-ZW=-Z，典式目標函數(shù)方程如下：典式目標函數(shù)方程如下： W+ =-Z W+ =-Z0 0 則則：（：（LPLP）的上述的上述典式可直觀表示如下表典式可直觀表示如下表T T（B B）。）。 （LPLP）關(guān)于關(guān)于X XB B的典式與單純形表的典式與單純形表單純形表單純形表 D jJ j I r X X XB B X XB B1 1 X XBi Bi X XBmBm X XD1 D1 X Xj j X XDnDn-m-m b b X XB B1 1 1 1 0 0 0 0 y y1D 1D1 1 y y1j 1j y y1Dn-m 1

39、Dn-m b b1 1 X XBi Bi 0 0 1 1 0 0 y yiD iD1 1 y yijij y yiDniDn-m-m b bi i X XBm Bm 0 0 0 0 1 1 y ymD mD1 1 y ymjmj y y1Dn-m 1Dn-m b bm m r r 0 0 0 0 0 0 r rD D1 1 r rj j r rDn Dn-m-m -Z -Z0 0 （ Y Y ） （ r rD D ） （ E E ） （ O O ） 算法規(guī)則算法規(guī)則最優(yōu)判別準則最優(yōu)判別準則 定理定理1 1：若若T T（B B）中中 r rj j=0| =0| ，則則X XB B對應(yīng)的對應(yīng)的 基

40、本可行解基本可行解X X* *= =（b b1 1,b,b2 2, ,b bm m,0,0,0,0,0),0)T T 一定是基本最優(yōu)解。一定是基本最優(yōu)解。 證：證： 設(shè)設(shè) X=X=（x x1 1，x x2 2，x xn n）T T為（為（LPLP）問題問題 的任意可行解，由典式可知其目標函數(shù)值的任意可行解，由典式可知其目標函數(shù)值 Z Z（X X）= Z= Z0 0+ + ； X X* *= =（b b1 1,b,b2 2, ,b bm m,0,0,0,0,0),0)T T對對 應(yīng)的應(yīng)的 目標函數(shù)值目標函數(shù)值Z Z（X X* *）= Z= Z0 0 ； Z Z（X X） - - Z Z（X X*

41、 *）= = =0=0 Z Z（X X） =Z=Z（X X* *），）， X X* *為最優(yōu)。為最優(yōu)。 D jI D jJ j I r X D jJ j I r X 算法規(guī)則算法規(guī)則最優(yōu)判別準則最優(yōu)判別準則 定理定理2 2：若若T T（B B）中中 存在存在r rt t0| 0| ，而且而且 y yt t= =（y y1t 1t,y ,y2t 2t, , ,y ymtmt) )T T=0, 0)| , =M(M0)| , XjXj=0| =0| 則由典式可知（則由典式可知（LPLP）問題的一個可行解：問題的一個可行解： X Xb bi i=b=bi i-y yit it* *M(=0_,I=1

42、,2, M(=0_,I=1,2,m,m X Xt t=M(0)=M(0) X Xj j=0,=0, 對應(yīng)的目標函數(shù)值對應(yīng)的目標函數(shù)值Z Z（X X）= Z= Z0 0+ +r rt t* *M M 顯然，顯然，M M無窮大時，無窮大時， Z Z（X X）無窮小，無下界。無窮小，無下界。 D tI D tI, D jIjt , D jIjt 算法規(guī)則算法規(guī)則基變換迭代準則基變換迭代準則 定理定理3 3：若若T T（B B）中中 存在存在r rt t=0| =0| ，而且而且 y yt t= =（y y1t 1t,y ,y2t 2t, , ,y ymtmt) )T T中 中存在 存在y ykt k

43、t0|1 0|1 k k m,m, 則則（LPLP）問題存在另一個問題存在另一個相鄰相鄰的基本可行基的基本可行基X XB B， 且且 Z Z（X XB B）=Z=Z（X XB B）。 證證：（一）構(gòu)造相鄰的基本可行基（一）構(gòu)造相鄰的基本可行基X XB B； （1 1）選擇進基變量；）選擇進基變量； 因為因為 r rt t=0|=0| Z = ZZ = Z0 0+ + X Xt t進基，進基，Z Z值減小值減小可選擇可選擇X Xt t作為進基變量；作為進基變量； D tI D tI D jJ j I r X 算法規(guī)則算法規(guī)則基變換迭代準則基變換迭代準則 X Xt t| | r rt t=Min=

44、Minr rj j| ,| ,r rj j00 或或 X Xt t| | t=Minj| ,t=Minj| ,r rj j00)| , 0)| , X Xj j=0| =0| 則由典式可知（則由典式可知（LPLP）問題的等價形式：問題的等價形式： Min ZMin Z（X X）= Z= Z0 0+ +r rt t* * X Xb bi i=b=bi i-y yit it* * , i=1,2, , i=1,2,m,m X Xt t= = (0)(0) X Xj j=0,=0, 顯然，顯然， ，Z Z（X X） 但但 必須滿足以下可行必須滿足以下可行 性要求：性要求： X Xb bi i=b=b

45、i i-y yit it* * =0=0 i=1,2,i=1,2,m,m , D jIjt （2 2）選擇出基變量；）選擇出基變量； , D jIjt 算法規(guī)則算法規(guī)則基變換迭代準則基變換迭代準則 =Minb=Minbi i/y yit it| |y yitit0, 0, i=1,2,i=1,2,m=,m=b bk k/y ykt kt ； 若令若令 = = b bk k/y ykt kt，則 則 X XBk Bk= =b bk k- -y ykt kt* *b bk k/ /y ykt kt=0, =0, 基本基本 變量變量X XBk Bk出基成為非基本變量。 出基成為非基本變量。 i.e.

46、i.e. =b=bi i/y yit it| |y yitit0, 0, i=1,2,i=1,2,m,m X XBk Bk | | b bk k/y ykt kt =Minb =Minbi i/y yit it| |y yitit0, 0, i=1,2,i=1,2,m,m, 出基規(guī)則：最小比值準則出基規(guī)則：最小比值準則 若若 b bk k/y ykt kt= = b bl l/y ylt lt= = b bp p/ /y ypt pt= = = Min,Min,則取下標則取下標 最小者出基。最小者出基。 出基規(guī)則：下標最小準則出基規(guī)則：下標最小準則 （二）目標函數(shù)值比較（二）目標函數(shù)值比較 Z

47、 Z（X XB B）= Z= Z0 0 Z Z（ （X XB B）= Z= Z0 0+ +r rt t* *b bk k/y ykt kt Z Z（X XB B）- Z- Z（X XB B）= = r rt t* *bkbk/y ykt kt=0 =0 Z Z（ （X XB B）= Z= Z（X XB B） 證畢。證畢。 算法規(guī)則算法規(guī)則基變換迭代準則基變換迭代準則 相關(guān)概念相關(guān)概念 r rj j檢驗數(shù)；檢驗數(shù)； X Xt t 進基變量；進基變量； X XBk Bk 出基變量； 出基變量； y yt t= =（y y1t 1t,y ,y2t 2t, , ,y ymtmt) )T T樞軸列； 樞

48、軸列； X XBk Bk所在第 所在第k k行行樞軸行；樞軸行；y ykt kt 樞軸元素； 樞軸元素； 轉(zhuǎn)軸運算轉(zhuǎn)軸運算由由T T（B B）至至T T（BB）所進行的方所進行的方 程程 組的等價變換。組的等價變換。 算法規(guī)則算法規(guī)則基變換迭代準則基變換迭代準則 算法規(guī)則算法規(guī)則轉(zhuǎn)軸運算準則轉(zhuǎn)軸運算準則 X XB B X XB B1 1 X XBiBi X XBkBk X XBmBm X Xt t X Xj j b b X XB B1 1 1 1 0 0 0 0 0 0 y y1t 1t y y1j 1j b b1 1 X XBi Bi 0 0 1 1 0 0 0 0 y yitit y yi

49、jij b bi i X XBk Bk 0 0 0 0 1 1 0 0 y yktkt y ykjkj b bk k X XBm Bm 0 0 0 0 0 0 1 1 y ymtmt y ymjmj b bm m r r 0 0 0 0 0 0 0 0 r rt t r rj j -Z-Z0 0 ( ( ) ) ( ( ) ) k kt b y (1) (1)L Lk k=L Lk k* *1/1/y ykt kt; ; (2)L (2)Li i=L=Li i+ +L Lk k* *(-(-y yit it)=L )=Li i+ +L Lk k* *(-(-y yit it/ /y yktkt

50、); ); (3)r=r+ (3)r=r+L Lk k* *(-(-r rt t)=r+)=r+L Lk k* *(-(-r rt t/ /y ykt kt); ); 算法規(guī)則算法規(guī)則轉(zhuǎn)軸運算準則轉(zhuǎn)軸運算準則 X XB B X XB B1 1 X XBiBi X XBkBk X XBmBm X Xt t X Xj j b b X XB B1 1 1 1 0 0 0 0 0 0 y y1t 1t y y1j 1j b b1 1 X XBi Bi 0 0 1 1 0 0 0 0 y yitit y yijij b bi i X XBk Bk 0 0 0 0 1/ 1/y ykt kt0 0 y y

51、ktkt y ykjkj b bk k X XBm Bm 0 0 0 0 0 0 1 1 y ymtmt y ymjmj b bm m r r 0 0 0 0 0 0 0 0 r rt t r rj j -Z-Z0 0 (1) (1)L Lk k=L Lk k* *1/1/y ykt kt; ; (2)L (2)Li i=L=Li i+ +L Lk k* *(-(-y yit it)=L )=Li i+ +L Lk k* *(-(-y yit it/ /y yktkt); ); (3)r=r+ (3)r=r+L Lk k* *(-(-r rt t)=r+)=r+L Lk k* *(-(-r r

52、t t/ /y ykt kt); ); 算法規(guī)則算法規(guī)則轉(zhuǎn)軸運算準則轉(zhuǎn)軸運算準則 X XB B X XB B1 1 X XBiBi X XBkBk X XBmBm X Xt t X Xj j b b X XB B1 1 1 1 0 0 0 0 0 0 y y1t 1t y y1j 1j b b1 1 X XBi Bi 0 0 1 1 0 0 0 0 y yitit y yijij b bi i X XBk Bk 0 0 0 0 1/ 1/y ykt kt0 0 1 1 y ykj kj b bk k X XBm Bm 0 0 0 0 0 0 1 1 y ymtmt y ymjmj b bm m

53、 r r 0 0 0 0 0 0 0 0 r rt t r rj j -Z-Z0 0 (1) (1)L Lk k=L Lk k* *1/1/y ykt kt; ; (2)L (2)Li i=L=Li i+ +L Lk k* *(-(-y yit it)=L )=Li i+ +L Lk k* *(-(-y yit it/ /y yktkt); ); (3)r=r+ (3)r=r+L Lk k* *(-(-r rt t)=r+)=r+L Lk k* *(-(-r rt t/ /y ykt kt); ); 算法規(guī)則算法規(guī)則轉(zhuǎn)軸運算準則轉(zhuǎn)軸運算準則 X XB B X XB B1 1 X XBiBi X

54、 XBkBk X XBmBm X Xt t X Xj j b b X XB B1 1 1 1 0 0 0 0 0 0 y y1t 1t y y1j 1j b b1 1 X XBi Bi 0 0 1 1 0 0 0 0 y yitit y yijij b bi i X XBk Bk 0 0 0 0 1/ 1/y ykt kt0 0 1 1 y ykjkj/ / y yktkt b bk k X XBm Bm 0 0 0 0 0 0 1 1 y ymtmt y ymjmj b bm m r r 0 0 0 0 0 0 0 0 r rt t r rj j -Z-Z0 0 (1) (1)L Lk k=

55、L Lk k* *1/1/y ykt kt; ; (2)L (2)Li i=L=Li i+ +L Lk k* *(-(-y yit it)=L )=Li i+ +L Lk k* *(-(-y yit it/ /y yktkt); ); (3)r=r+ (3)r=r+L Lk k* *(-(-r rt t)=r+)=r+L Lk k* *(-(-r rt t/ /y ykt kt); ); 算法規(guī)則算法規(guī)則轉(zhuǎn)軸運算準則轉(zhuǎn)軸運算準則 X XB B X XB B1 1 X XBiBi X XBkBk X XBmBm X Xt t X Xj j b b X XB B1 1 1 1 0 0 0 0 0

56、0 y y1t 1t y y1j 1j b b1 1 X XBi Bi 0 0 1 1 0 0 0 0 y yitit y yijij b bi i X XBk Bk 0 0 0 0 1/ 1/y ykt kt0 0 1 1 y ykjkj/ / y yktktb bk k / / y ykt kt X XBm Bm 0 0 0 0 0 0 1 1 y ymtmt y ymjmj b bm m r r 0 0 0 0 0 0 0 0 r rt t r rj j -Z-Z0 0 (1) (1)L Lk k=L Lk k* *1/1/y ykt kt; ; (2)L (2)Li i=L=Li i+

57、 +L Lk k* *(-(-y yit it)=L )=Li i+ +L Lk k* *(-(-y yit it/ /y yktkt); ); (3)r=r+ (3)r=r+L Lk k* *(-(-r rt t)=r+)=r+L Lk k* *(-(-r rt t/ /y ykt kt); ); 算法規(guī)則算法規(guī)則轉(zhuǎn)軸運算準則轉(zhuǎn)軸運算準則 X XB B X XB B1 1 X XBiBi X XBkBk X XBmBm X Xt t X Xj j b b X XB B1 1 1 1 0 0 0 0 0 0 y y1t 1t y y1j 1j b b1 1 X XBi Bi 0 0 1 1 0

58、 0 0 0 y yij ij b bi i X XBk Bk 0 0 0 0 1/ 1/y ykt kt0 0 1 1 y ykjkj/ / y yktktb bk k / / y ykt kt X XBm Bm 0 0 0 0 0 0 1 1 y ymtmt y ymjmj b bm m r r 0 0 0 0 0 0 0 0 r rt t r rj j -Z-Z0 0 (1) (1)L Lk k=L Lk k* *1/1/y ykt kt; ; (2) (2)L Li i=L=Li i+ +L Lk k* *(-(-y yit it)=L )=Li i+ +L Lk k* *(-(-y

59、yit it/ /y yktkt); ); (3)r=r+ (3)r=r+L Lk k* *(-(-r rt t)=r+)=r+L Lk k* *(-(-r rt t/ /y ykt kt); ); it kt y y 算法規(guī)則算法規(guī)則轉(zhuǎn)軸運算準則轉(zhuǎn)軸運算準則 X XB B X XB B1 1 X XBiBi X XBkBk X XBmBm X Xt t X Xj j b b X XB B1 1 1 1 0 0 0 0 0 0 y y1t 1t y y1j 1j b b1 1 X XBi Bi 0 0 1 1 0 0 0 0 . . . . X XBk Bk 0 0 0 0 1/ 1/y yk

60、t kt0 0 1 1 y ykjkj/ / y yktktb bk k / / y ykt kt X XBm Bm 0 0 0 0 0 0 1 1 y ymtmt y ymjmj b bm m r r 0 0 0 0 0 0 0 0 r rt t r rj j -Z-Z0 0 (1) (1)L Lk k=L Lk k* *1/1/y ykt kt; ; (2) (2)L Li i=L=Li i+ +L Lk k* *(-(-y yit it)=L )=Li i+ +L Lk k* *(-(-y yit it/ /y yktkt); ); (3)r=r+ (3)r=r+L Lk k* *(-(