1、第一章第一章 線性規劃與單純形法線性規劃與單純形法本章重點內容本章重點內容線性規劃模型與解的主要概念線性規劃模型與解的主要概念線性規劃的單純形法，線性規劃多解分析線性規劃的單純形法，線性規劃多解分析線性規劃的運用線性規劃的運用建模建模第一節第一節 線性規劃問題及數學模型線性規劃問題及數學模型 一、實例 二、線性規劃問題LP問題的共同特征 三、兩變量線性規劃問題的圖解法 四、線性規劃問題的規范型 五、規范型LP問題解的概念 六、可行解、基解和基可行解舉例一、實例一、實例例例1 1 消費方案問題消費方案問題Step 1:Step 1:明確問題，設定決策變量明確問題，設定決策變量 設設I I、III

2、I兩種產品的產量分別為兩種產品的產量分別為x1, x2 x1, x2 。Step 2: Step 2: 確定約束條件確定約束條件產品 I II 資源限量設備 1 2 8臺時原料A 4 0 16公斤原料B 0 4 12公斤 利潤 2 38221 xx工工時時約約束束：1604A21 xx約約束束：原原料料1240B21 xx約約束束：原原料料0021 xx，變變量量非非負負約約束束：問應如何安排消費問應如何安排消費使該廠獲利最多？使該廠獲利最多？ 0124164823221212121x,xxxxx. t . sxxZmax:OBJ闡明：闡明：OBJ OBJ 表示表示Objective;Obje

3、ctive; s.t. s.t. 表示表示Subject to Subject to Step 3: Step 3: 給出目的函數給出目的函數2132xxZmax Step 4: Step 4: 整理數學模型整理數學模型例例2 現要做現要做100套鋼架，每套需套鋼架，每套需2.9米、米、2.1米和米和1.5米的元鋼各一根。米的元鋼各一根。知原料長知原料長7.4米，問如何下料，使余料最少？米，問如何下料，使余料最少？ 設設I, II, III, IV, V分別代表五種不同的原料用量方案分別代表五種不同的原料用量方案, x1, x2 , x3, x4 , x5分別代表采用各方案下料的元鋼的根數。分

4、別代表采用各方案下料的元鋼的根數。1234512434512351234512345:00.10.20.30.8210022100. .323100,030100500;16OBJMinZxxxxxxxxxxxs txxxxxxxxxxxxxxOBJ解得：，方案方案根數根數2.9米米2.1米米1.5米米合計合計余料余料I x11037.40IIx22017.30.1IIIx30227.20.2IVx41207.10.3Vx50136.60.8解：解：12345124345123512345:00.10.20.30.8210022100. .323100,0OBJ MinZxxxxxxxxxxx

5、stxxxxx x x x xLP(Linear Programming)LP(Linear Programming)是數學規劃的一個重要分支，數是數學規劃的一個重要分支，數學規劃著重處理資源的優化配置，普通可以表達成以下兩個問學規劃著重處理資源的優化配置，普通可以表達成以下兩個問題中的一個：題中的一個：1 1當資源給定時，要求完成的義務最多；當資源給定時，要求完成的義務最多；2 2當義務給定時，要求為完成義務所耗費的資源最少。當義務給定時，要求為完成義務所耗費的資源最少。 假設上述問題的目的假設上述問題的目的約束都能表達成變量的線性關系，約束都能表達成變量的線性關系，那么這類優化問題稱那么這

6、類優化問題稱LPLP問題。問題。 LP LP是一種處理在線性約束條件下追求最大或最小的線性是一種處理在線性約束條件下追求最大或最小的線性目的函數的方法。目的函數的方法。 目的函數用決策變量的線性函數來表示。按問題的不目的函數用決策變量的線性函數來表示。按問題的不同，要求目的函數實現最大化和最小化。同，要求目的函數實現最大化和最小化。 每一個問題變量都用一組決策變量每一個問題變量都用一組決策變量x1, x2, , x1, x2, , xnxn表示某一方案，這組決策變量的值代表一個詳細方表示某一方案，這組決策變量的值代表一個詳細方案，這些變量是非負且延續的。案，這些變量是非負且延續的。 存在一定的

7、約束條件，這些約束條件可以用一組線性存在一定的約束條件，這些約束條件可以用一組線性等式或線性不等式來表示。等式或線性不等式來表示。結論：線性規劃是研討在一組線性不等式或線性等式約束結論：線性規劃是研討在一組線性不等式或線性等式約束下，使得某一線性目的函數取最大或最小的極值問題。下，使得某一線性目的函數取最大或最小的極值問題。二、線性規劃問題二、線性規劃問題LPLP問題的共同特征問題的共同特征Max(Min) Z=c1x1+c2x2+cnxn (1) a11x1+a12x2+a1nxn ( =, ) b1 a21x1+a22x2+a2nxn ( =, ) b2 s.t. (2) am1x1+am

8、2x2+amnxn ( =, ) bm xj0, j=1,2, ，n (3)(1)目的函數；目的函數；(2)約束條件；約束條件；(3)決策變量非負決策變量非負n變量個數；變量個數； m約束行數；約束行數； cj價值系數；價值系數；bi右端項或限額系數；右端項或限額系數； aij技術系數；技術系數；xj決策變量決策變量線性規劃模型的普通方式為：線性規劃模型的普通方式為：線性規劃模型的緊縮方式線性規劃模型的緊縮方式11()( , )1,2,.01,2,njjjnijjijjMax Minzc xa xbims txjn n變量個數；變量個數； m約束行數；約束行數； cj價值系數；價值系數；bi右

9、端項或限額系數；右端項或限額系數； aij技術系數；技術系數；xj決策變量決策變量練習題：能否為線性規劃模型？練習題：能否為線性規劃模型？123123123233. .4790,1,2,3jzxxxxxxstxxxxj1231231233233. .4790,1,2,jMinzxxxxxxstxxxxjx符號不限11( , )1,2,.01,2,njjjnijjijjMaxzc xa xbimstxjn 1.1.線性不等式的幾何意義線性不等式的幾何意義 半平面半平面作出作出LPLP問題的可行域問題的可行域作出目的函數的等值線作出目的函數的等值線挪動等值線到可行域邊境得到最優點挪動等值線到可行域

10、邊境得到最優點2.2.圖解法步驟圖解法步驟三、兩變量線性規劃問題的圖解法三、兩變量線性規劃問題的圖解法2132xx 212xx 0,12416482. .32max:21212121xxxxxxtsxxZOBJ4x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30例例1Q2(4,2)Z=2x1+3x2 做目的函數做目的函數2x1+3x2的等值線，的等值線，與陰影部分的邊境相交于與陰影部分的邊境相交于Q2(4,2)點，闡明最優消費方點，闡明最優消費方案為：消費案為：消費I產品產品4件，消費件，消費II產品產品2件。件。Q3 目的函數目的函數z=ax1+bx2的值遞增的方向與系數的

11、值遞增的方向與系數a、b有關有關a 0 , b0a 0X1X2a 0 , b 0 , b0z=ax1+bx2目的函數等值線：目的函數等值線：ax1+bx2=k移項移項x2=-a/bx1+k/b目的函數等值線在縱軸目的函數等值線在縱軸上的截距為上的截距為k/b例例4 4 0,78102.46max212212121xxxxxxxtsxxZ1187654322x1876543O109x2A BCEDFGH123Z=363662:21 Zxx最優解最優解例例 用圖解法求解線性規劃問題用圖解法求解線性規劃問題12121212max2428416. .412,0Zxxxxxs txxx 4x1=164x

12、2=12x1+2x2=8x1x248Q1 4 Q4 30Q2(4,2)Z=2x1+4x2當當Z Z值由小變大時，將與值由小變大時，將與Q2Q3Q2Q3重合重合Q2Q3Q2Q3上恣意一點都是最優解上恣意一點都是最優解有無窮多最優解多重解有無窮多最優解多重解Q3(2,3)例例 用圖解法求解線性規劃問題用圖解法求解線性規劃問題可行域無界可行域無界無界解無界解 “無有限最優解或無有限最優解或“最優解無界最優解無界約束條件過分寬松約束條件過分寬松留意：可行域不閉合不一定就會出現留意：可行域不閉合不一定就會出現無界解，這要看目的函數的性質。無界解，這要看目的函數的性質。假設目的函數是假設目的函數是minm

13、in，那么有最優解。，那么有最優解。無論有無最優解，一定有可行解。無論有無最優解，一定有可行解。121212221. .200,1,2jMaxZxxxxstxxxjx2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00例例 用圖解法求解線性規劃問題用圖解法求解線性規劃問題可行域無界可行域無界獨一最優解獨一最優解X X* *=(1,0)=(1,0)，對應于點，對應于點A A121212221. .200,1,2jMinZxxxxstxxxjx2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00例例 用圖解法求解線性規劃問題用圖解法求解線性規劃問題可行域無界可行域無界無窮多

14、最優解無窮多最優解對應于點對應于點B B沿著沿著OBOB向右上方向右上方發出的射線上的一切點發出的射線上的一切點12121221. .200,1,2 jMaxZxxxxstxxxjx2x1x1-x2=1B(2,1)A(1,0)-x1+2x2=00例例 用圖解法求解線性規劃問題用圖解法求解線性規劃問題 無可行解可行域為空無可行解可行域為空121212122328416. . 412240,1,2jMaxZxxxxxs txxxxjx14x1=164x2=12x1+2x2=8x248Q1 4Q4 30-2-2x1+x2=4 無最優解無最優解3.3.圖解法的作用圖解法的作用 能處理少量問題能處理少量

15、問題 提示了線性規劃問題的假設干規律提示了線性規劃問題的假設干規律解的類型解的類型可行域類型可行域類型獨一最優解獨一最優解無窮多最優解無窮多最優解最優解無界最優解無界無有限最優解無有限最優解無解無解不存在可行域不存在可行域非空有界非空有界無界無界空集空集規律規律1 1：規律規律2 2： 線性規劃問題的可行域為凸集線性規劃問題的可行域為凸集 線性規劃問題凸集的頂點個數是有限的線性規劃問題凸集的頂點個數是有限的 最優解可在凸集的某頂點處到達最優解可在凸集的某頂點處到達 012012021(01)SXSXXSXXXXS（ ）（ ）（ ）（ ）（ ）（ ）（ ）（ ）頂點：設 為凸集，若不存在兩點，使

16、得（），則為 的一個頂點。（除頂點外，集合中任何兩點的連線段都不通過頂點）基本概念基本概念12121101KnXXKXXKKaaa刮+-撾（ ）（ ）（ ）（ ）（）凸集：設 為 維空間一點集，任取兩點，若（），則 為一凸集。(要求集合中的任何兩點的連線段落在這個集合中) 小結：圖解法的根本步驟：小結：圖解法的根本步驟：1 1在直角坐標系作出可行域在直角坐標系作出可行域S S的區域的區域 普通是一個凸多邊形普通是一個凸多邊形2 2令目的函數值取一個知的常數令目的函數值取一個知的常數k k，作等值線：，作等值線：c1x1+c2x2=kc1x1+c2x2=k3 3對于對于maxmax問題，讓目的函

17、數值問題，讓目的函數值k k由小變大，即讓等值線進展由小變大，即讓等值線進展平移，假設它與可行域平移，假設它與可行域S S最后交于一個點普通是最后交于一個點普通是S S的一個頂的一個頂點，那么該點就是所求的最優點，假設與點，那么該點就是所求的最優點，假設與S S的一條邊境重的一條邊境重合，此時邊境限上的點均是最優點合，此時邊境限上的點均是最優點4 4將最優點所在的兩條邊境限所代表的方程聯立求解，即得將最優點所在的兩條邊境限所代表的方程聯立求解，即得最優解最優解X X* *，把最優解，把最優解X X* *帶入目的函數，得最優值帶入目的函數，得最優值Z Z* *=CX=CX* *留意：假設是求目的

18、函數最小值，等值線向反方向挪動留意：假設是求目的函數最小值，等值線向反方向挪動四、線性規劃問題的規范型四、線性規劃問題的規范型112211112211211222221122max. .0,1,2,0,1,2,nnnnnnmmmnnmjiZc xc xc xa xa xa xba xaxaxbs taxaxaxbxjnbim1.1.規范型規范型 1目的函數：目的函數：max2約束條件：等式約束條件：等式3變量約束：非負變量約束：非負 xj04資源限量：非負資源限量：非負bi 0規范型的構成要素規范型的構成要素2.2.線性規劃規范型的緊縮方式線性規劃規范型的緊縮方式111,2,.01,2,01,

19、2,Maxnjjjnijjijjizc xa xbimst xjnbim技術系數右端項價值系數約束行數變量個數: ;: ;: ;: ;:ijijabcmn3.3.線性規劃規范型的向量和矩陣表達式線性規劃規范型的向量和矩陣表達式矩陣式矩陣式: Max Z=CTX s.t. AX=b X0 n向量式: Max Z= cjxj j=1 n s.t. Pjxj=b j=1 xj 0, j=1,2, . ,n1111112122221222121212:,( ,.,) nnnmmmnnmnjjjmjcbxaaacbxaaaCbXAP PPaaacbxaaPa其中的的最最優優目目標標函函數數值值。問問題題

20、函函數數值值變變號號即即為為最最小小化化最最大大化化問問題題的的最最優優目目標標。求求出出最最優優解解后后，可可轉轉換換成成令令，小小化化問問題題根根據據這這一一原原理理，對對于于最最，最最優優值值絕絕對對值值相相同同。同同為為上上述述例例子子中中，最最優優解解相相CXZZZCXZx maxmin*4.一切一切LP問題均可化為規范型問題均可化為規范型1最小轉換成最大最小轉換成最大y1=f(x)y2=-f(x)xyx*y1*y2*成成一一個個約約束束。這這樣樣就就把把兩兩個個約約束束轉轉換換，則則此此時時，則則，令令若若；，無無限限制制，令令若若，則則，令令若若abxxabxxaxxbxaxxx

21、xxxxxxxnjjjjjjjjjjjjjjjj 3000;00 為為剩剩余余變變量量若若為為松松弛弛變變量量若若0,0,2211ninjijijijninjijijijxbxxabxaxbxxabxa2不等式約束條件轉換成等式約束條件不等式約束條件轉換成等式約束條件3變量約束轉換變量約束轉換。，即即方方程程兩兩邊邊同同乘乘以以則則，即即若若1000 ijijijijibxabxab4把把bi0轉換成轉換成bi0例例5 5 化規范型化規范型 0,12416482.3221212121xxxxxxtsxxMaxZ )5 , 1( 01241648200032524132154321jxxxxxx

22、xxxxxxxMaxZj可化為可化為1.1.處置決策變量處置決策變量2.2.處置約束條件右端處置約束條件右端 常數項常數項3.3.約束條件不等式約束條件不等式4.4.處置目的函數處置目的函數例例6 6 化規范型化規范型型型即即可可得得到到該該問問題題的的標標準準改改為為求求，把把求求令令號號的的左左端端減減去去剩剩余余變變量量在在第第二二個個約約束束不不等等式式號號的的左左端端加加入入松松弛弛變變量量在在第第一一個個約約束束不不等等式式以以滿滿足足非非負負約約束束條條件件；號號兩兩端端同同乘乘以以在在第第三三個個約約束束條條件件；，令令其其中中令令;. 4;. 3, 1. 20;0, 0,.

23MaxMinZZZxxxxxxxxxx 無無約約束束例例：321321321321321, 0, 053327.32xxxxxxxxxxxxtsxxxMinZ1.1.處置決策變量處置決策變量2.2.處置約束條件右端處置約束條件右端 常數項常數項3.3.約束條件不等式約束條件不等式4.4.處置目的函數處置目的函數Max Z =x1+2x2+3x4-3x5+0 x6+0 x7 s.t. x1 - x2 + x4 - x5+x6 = 7 x1+x2 + x4 - x5 - x7 = 2 -3x1 -x2+3x4 -3x5 = 5 x20 , xj0, j=1,4,5,6,7

24、Max Z =x1+2x2+3(x4-x5)+0 x6+0 x7 s.t. x1 - x2 +(x4 - x5 ) +x6 = 7 x1+x2 +(x4 - x5 ) - x7 = 2 -3x1 -x2+3(x4 -x5) = 5 x20 , xj0, j=1,4,5,6,7 無約束無約束例：例：321321321321321, 0, 053327.32xxxxxxxxxxxxtsxxxMinZ最終結果最終結果中間結果中間結果 0;4 ,2 , 1,0417431432.42;8424040,2343321321321321434333xjxxxxxxxxxtsxxxZMaxxxxMaxZxx

25、xxxxj即即所所以以，滿滿足足；且且則則有有解解：令令課堂練習課堂練習 62 , 0,25432032.42321321321321xxxxxxxxxtsxxxMaxZ五、規范型五、規范型LPLP問題解的概念問題解的概念1111121222122212(1)(2) . .0(3),(, ( )231TnnmmmnnnMaxZC XAXbstXcxaaacxaaaCXAmn r AmaaacxLPA其中，滿足（ ）、（ ）的解；滿足可行解（）的可行解，為問題的最優解；優解基設最( ),0m nm mLPr Am BABBLP為問題的系數矩陣，為 的非奇異矩陣（），則稱 為問題的一個基。 ) 5

26、 , 1( 01241648200032max524132154321jxxxxxxxxxxxxxZj123 100400100400121A約束系數矩陣：約束系數矩陣：x1x2x3x4x5例：例： 100400100400121A約束系數矩陣：約束系數矩陣：能夠的基矩陣是能夠的基矩陣是A中恣意三個列的組合，共中恣意三個列的組合，共10個。個。 0400041211B01 B 0401040212B02 B 1400040213B03 B 0001040114B04 B 1000040115B05 B 1000140016B06 B 0041000127B07 B 1040000128B08

27、B 1040100029B09 B 10001000110B010 B令令B = =( P1 , P2 , , Pm ) 且且| B | 0 ，那么稱，那么稱Pj (j=1,2,m) 為基向量。為基向量。與基向量與基向量Pj對應的變量對應的變量xj稱為基變量，稱為基變量，記為記為XB = ( x1 , x2 , , xm )T，其他的變量稱為非基變量，其他的變量稱為非基變量，記為記為XN = ( xm+1 , xm+2 , , xn ) T 。1112112mmmmmaaaaaa為為非非基基變變量量。、為為一一組組基基變變量量，、則則對對應應的的時時，矩矩陣陣為為如如在在典典型型示示例例中中，

28、當當基基543211040004121xxxxxB 為為非非基基變變量量。、一一組組基基變變量量，為為、時時，則則對對應應的的而而當當基基矩矩陣陣為為2154310100010001xxxxxB 化化。而而是是隨隨著著基基的的變變化化而而變變一一成成不不變變的的，問問題題中中，基基變變量量并并不不是是由由此此可可見見，同同一一個個LP 100400100400121A ()()00NBTTBNBXXXXXX令，求得一組基變量的值，則（，）（， ）為基本解。（頂點）既是基本解，又是可行解。既是基可行解，又是使目標函數值達到最優的解。基可行解對應的基。基 本 解基 本 可行解基最優基最優解解可行基

29、最優基對應的基。B1=(P1,P2)：基：基1212243510 xxxx 令：令：XB1=(x1,x2)x1=0， x2=2X=(0, 2, 0, 0)XB1=(0, 2)12123124243510. .0,1,2,3,4jMaxZxxxxxxxxs txj 例例：134(,)BNXxx 134(,)0BNXxx 對應于對應于B1的基解為的基解為線性規劃規范型問題解的關系線性規劃規范型問題解的關系約束方程的約束方程的解空間解空間基解基解可行解可行解非可行解非可行解基可基可行解行解例例7 7 Max Z =2x1+3x2 Max Z =2x1+3x2 s.t. x1+ s.t. x1+ 2x

30、282x28 4x1 4x1 16 16 4x2 124x2 12 x1, x2 0 x1, x2 0 六、可行解、基解和基可行解舉例六、可行解、基解和基可行解舉例非基非基變量變量基變量基變量圖中的點圖中的點x4, x5x1=4x2=3x3= -2 A基解基解x3, x5x1=2x2=3x4=8B基可行解基可行解x3, x4x1=4x2=2x5=4C基可行解基可行解x2, x4x1=4x3=4x5=12D基可行解基可行解x2, x3x1=8x4= -16x5=12E基解基解x1, x5x2=3x3=2x4=16F基可行解基可行解x1, x3x2=4x4=16x5= -4 G基解基解x1, x2

31、x3=8x4=16x5=12H基可行解基可行解4x1=164x2=12x1+2x2=8x1x20Z=2x1+3x2ABCDEFGH ) 5 , 1( 01241648200032524132154321jxxxxxxxxxxxxxMaxZj規范型規范型例例8 81187654322x1876543O109x2A BCEDFGH123f(x)=36K 0,78102.46max212212121xxxxxxxtsxxZ第二節第二節 LP LP問題的根本實際問題的根本實際一、根本概念一、根本概念12121101( )( )( )( ).,(),SnXXSXXXSS凸凸集集：設設 為為 維維歐歐氏氏

32、空空間間一一點點集集 若若任任意意兩兩點點、兩兩點點連連線線上上的的一一切切點點則則稱稱 為為一一凸凸集集。的的一一頂頂點點。為為則則稱稱成成立立使使，對對于于若若不不存存在在為為一一凸凸集集凸凸集集頂頂點點：設設）（）（SXXXXSXXSXS)0()2()1(0)2()1(0,)1(),10(,. 2 的的一一個個凸凸組組合合。為為則則稱稱使使得得若若存存在在個個點點，維維空空間間中中的的為為凸凸組組合合：設設）（）（）（）（）（）（）（)(211221121)(21,)1, 10( ,. 3kkiiikkkkXXXXXXXXknXXX 判別以以下圖形哪些是凸集，哪些不是凸集？判別以以下圖形

33、哪些是凸集，哪些不是凸集？前往前往定理定理1 LP1 LP問題的可行域為一凸集。問題的可行域為一凸集。 121122(1)(2)(1)(2)|0,000 1,(1)(1)(1)0,()SXAXbXXXSAXbXAXbXXXXAXAXXbbbXXSS（ ）（ ）（ ）（ ）（ ）（ ）證明：記，任取則，；，對于， 作則顯然則因此 為一凸集。凸集的交集一定是凸集，而凸集的并集不一定是凸集二、根本定理二、根本定理引理引理 線性規劃問題的可行解線性規劃問題的可行解X=(x1, x2, , xn)T是基可行解是基可行解的充要條件為的充要條件為X的正分量所對應的系數列向量是線性獨立的。的正分量所對應的系數

34、列向量是線性獨立的。為為基基可可行行解解。所所以以由由定定義義。解解恰恰為為構構成成極極大大無無關關組組，對對應應個個與與向向量量中中取取出出時時，一一定定可可以以從從其其余余列列為為相相應應基基可可行行解解時時，它它們們恰恰為為一一個個基基，線線性性獨獨立立，必必有有由由于于向向量量。所所對對應應的的系系數數列列向向量量為為其其中中不不妨妨設設先先證證充充分分性性：XXPPPkmmkxxxXmkmkPPPPPPxxxkixxxxXkkkkkik,)()0 , 0 ,(,), 2 , 1(0),0 , 0 ,()1(212121212121 。由由基基可可行行解解的的定定義義可可知知再再證證必

35、必要要性性：)2(定理定理2 2 線性規劃問題的基可行解對應于可行域的頂點。線性規劃問題的基可行解對應于可行域的頂點。I,XXLP證明：第 步先證“若是基可行解 則是問題的可行域頂點”。反證法成成立立。）（使使（）（問問題題的的可可行行解解為為、則則存存在在不不同同的的兩兩個個點點）（不不是是頂頂點點，設設）（）（）（）（）（）（）（）（）（）（）（）（)1 , 0(,1),;,212222121121112121 XXXxxxXxxxXLPXXxxxXXnnn即：假設即：假設X是是LP問題的可行解，那么問題的可行解，那么“X是是LP問題的基可行解問題的基可行解等價于等價于“X是是LP問題可行

36、域頂點問題可行域頂點設設X是基可行解，那么其對應的向量組是基可行解，那么其對應的向量組a1,a2, ,am線性無關線性無關(mm時，有時，有xj=xj(1)= xj(2)= 0.不不是是基基可可行行解解。所所以以線線性性相相關關，與與假假設設矛矛盾盾所所以以不不全全為為零零又又得得）（）（）（）（）（）（）（）（XaaaxxXXxxaxxamjjmmm,)(0)()(:),2()1(2121212121111 )2()1(,22221211212111)2()1(baxaxaxbaxaxaxXXmmmm ）（）（）（）（）（）（是可行域的兩點，所以是可行域的兩點，所以因為因為)5(;00,40

37、)0()3(2211211212211baxaxaxbxxxaaaaabAXLPxaaakkknkkkk ）即即（問問題題的的可可行行解解，則則是是由由于于）（得得：IIXX第 步：用反證法證“若是可行域頂點，則是基可行解”)3(0,., 2 , 1, 0,)0 , 0 ,(221121 kkiiiikaaaaxkixxxxX使使數數即即存存在在一一組組不不全全為為零零的的線線性性相相關關。所所對對應應的的系系數數列列向向量量則則但但不不是是基基可可行行解解。其其中中是是可可行行解解設設）（）（令令0 , 0 ,0 , 0 ,2211)2(2211)1(kkkkxxxXxxxX 連連線線的的中

38、中點點。、是是即即可可得得：、由由）（）（）（）（21)2()1(21,2121XXXXXXXX 不不是是可可行行域域的的頂頂點點。是是可可行行解解。這這證證明明、即即充充分分小小時時，可可保保證證另另外外，當當）（）（XXXmixii21),2, 1(0 111222111222(5) (4),()()()(5) (4),()()()kkkkkkxaxaxabxaxaxab得： 得： ）（處處達達到到最最優優數數在在也也是是可可行行解解，且且目目標標函函若若問問題題可可行行域域的的頂頂點點為為證證明明：設設0*)0()0()()2()1(,CXZXXLPXXXk 達達到到最最大大值值。，即即

39、目目標標函函數數在在頂頂點點為為最最優優值值，所所以以只只能能又又。所所以以則則中中最最大大者者。，使使之之為為所所有有的的到到某某一一個個頂頂點點在在所所有有的的頂頂點點中中必必能能找找。因因此此其其中中表表示示成成：不不是是頂頂點點，所所以以它它可可以以因因）（）（）（)()()0()0()()0()(1)(1)()(1)(011)(0)0(1, 0,mmmmkimikiiiimkiiikiiikiiiXCXCXCXCXCXCXCXaCXaCXXCXaCXaaXaXX 定理定理3 3 假設可行域有界，那么假設可行域有界，那么LPLP問題的目的函數一定可以在問題的目的函數一定可以在其可行域的

40、頂點上到達最優。其可行域的頂點上到達最優。引理引理 假設假設S是有界凸集，那么任何一點是有界凸集，那么任何一點XS可表示為可表示為S的頂的頂點的凸組合。點的凸組合。 線性規劃問題的可行域是凸集線性規劃問題的可行域是凸集( (定理定理1)1)；凸集的頂點對應；凸集的頂點對應于基可行解于基可行解( (定理定理2)2)，基可行解，基可行解( (頂點頂點) )的個數是有限的；假設的個數是有限的；假設線性規劃有最優解，必在可行域某頂點上到達線性規劃有最優解，必在可行域某頂點上到達( (定理定理3)3)。因此。因此, ,我們可以在有限個基可行解中尋覓最優解。我們可以在有限個基可行解中尋覓最優解。 由線性代

41、數知，對規范形由線性代數知，對規范形LP問題，用枚舉法可以求出一切問題，用枚舉法可以求出一切基解，再經過察看找出其中的可行解基可行解，進而找基解，再經過察看找出其中的可行解基可行解，進而找出最優解。但假設變量和方程較多，比如出最優解。但假設變量和方程較多，比如m=50，n=100，一，一切基解有能夠達切基解有能夠達1029個，即使計算機每秒能求解個，即使計算機每秒能求解1億個這樣億個這樣的方程組，也需求的方程組，也需求30萬億年！因此，必需尋求有效的算法。萬億年！因此，必需尋求有效的算法。 為加快計算速度，算法必需具有兩個功能，一是每得到一個為加快計算速度，算法必需具有兩個功能，一是每得到一個

42、解，就來檢驗能否曾經最優，假設是停頓。二是假設不是最優，解，就來檢驗能否曾經最優，假設是停頓。二是假設不是最優，要保證下一步得到的解不劣于當前解。這就是線性規劃的單純要保證下一步得到的解不劣于當前解。這就是線性規劃的單純形法。形法。 第三節第三節 單純形法單純形法根本思想根本思想檢驗解的檢驗解的最優性最優性終了終了Y旋轉運算消元運算旋轉運算消元運算確定另一個根本可行解確定另一個根本可行解N化化LP問題為規范型，問題為規范型，確定一個初始根本可行解確定一個初始根本可行解 化化LP問題為規范型，從可行域的某問題為規范型，從可行域的某個基可行解一個頂點開場，轉換到個基可行解一個頂點開場，轉換到另一個

43、基可行解另一個頂點，并使另一個基可行解另一個頂點，并使目的函數值得到改善，如此反復，從而目的函數值得到改善，如此反復，從而求得問題的最優解。其本質是逐漸迭代求得問題的最優解。其本質是逐漸迭代逼近法。逼近法。一、確定初始基可行解一、確定初始基可行解Max Z=CXs.t. AX=b X0我們首先引見求初始基可行解的方法。我們首先引見求初始基可行解的方法。1.1.假設給定問題規范化后且假設給定問題規范化后且 系數矩陣系數矩陣A A中存在中存在m m個線性無個線性無關的單位列向量，那么以這關的單位列向量，那么以這m m個單位列向量構成的單位子矩陣作為個單位列向量構成的單位子矩陣作為初始基初始基B B

44、，那么，那么 ，其他，其他xj=0 xj=0是基可行解。是基可行解。2.2.大大M M法人工變量法法人工變量法0b 10BXB bb以以x2x2為主元素為主元素以以x1x1為主元素為主元素例例 2x1+ x2+ 2x3=10 (1) 3x1+ 3x2+ x3= 6 (2) x1+ 1/2x2+ x3= 5 (1)0 x1+ 3/2x2-2x3= -9 (2)(1)/ 2 ,(2)-(1)3 x1+ 0 x2+ 5/3x3= 8 (1)0 x1+ x2 - 4/3x3= -6 (2)(2) 2/3 , (1)-(2) /2二、旋轉運算二、旋轉運算三、檢驗數的意義三、檢驗數的意義結論：假設結論：假

45、設LPLP問題經過單純形法迭代到某步時，一切檢驗數問題經過單純形法迭代到某步時，一切檢驗數0,0,那么該那么該LPLP問題已得到最優解。問題已得到最優解。Max Z=CXs.t. AX=b X0假設假設cj-CBB-1Pj=j0, 那么那么ZZ0, Z0即為最優解即為最優解. (基變量的檢驗數基變量的檢驗數必為必為0)令令A=(B,N), X= XB A=(B,N), X= XB ,C=(CB,CN),C=(CB,CN) XN XN由由AX=b (B,N) XB =b BXB+NXN=b B-1BXB+B-AX=b (B,N) XB =b BXB+NXN=b B-1BXB+B-1NXN=B-1

46、b1NXN=B-1b XN XN XB=B-1b XB=B-1bB-1NXN (2)B-1NXN (2)將將(2)(2)式代入目的函數得式代入目的函數得Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B-1b-B-1NXN)+CNXN Z=CX = (CB,CN) XB =CBXB+CNXN= CB (B-1b-B-1NXN)+CNXN XN XN = CBB-1b+(CN-CBB-1N)XN = CBB-1b+(CN-CBB-1N)XN = Z0 + (cj-CBB-1Pj)xj = Z0 + (cj-CBB-1Pj)xj xj xj為非基變量為非基變量 單純形法舉例單純

47、形法舉例 0,121684243221221121xxxxxxxxMaxZ化為規范型化為規范型 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj約束方程的系數矩陣約束方程的系數矩陣123451 2 1 0 0( ,)4 0 0 1 00 4 0 0 1AP P P P P 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj3451 0 0(,)0 1 00 0 1BP P P是基,對應于B的變量x3，x4，x5為基變量，312415282164124xxxxxxx1將將1代

48、入目的函數后得到代入目的函數后得到z=0+2x1+3x2，令非基變量令非基變量x1=x2=0.得到得到z=0，及一個基可行解，及一個基可行解X(0)=(0,0,8,16,12)T 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZjx2=3， x5為換出變量為換出變量324528216124xxxxx3將將3代入目的函數后得到代入目的函數后得到z=9+2x13/4x5，令非基變量令非基變量x1=x5=0.得到得到z=9，及一個基可行解，及一個基可行解X(1)=(0,3,2,16,0)T當將當將x2定為換入變量后，必需從定為換入變量后，必

49、需從x3，x4，x5中確定一個換出變量，并保證中確定一個換出變量，并保證x3，x4，x50，當當x1=0時，由時，由1式得到式得到2用高斯消元法，將用高斯消元法，將x2的系數列向量變換為單位列向量，得到的系數列向量變換為單位列向量，得到3154125122164134xxxxxxx 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj這時目的函數的表達式是這時目的函數的表達式是z=141.5x30.125x4，當將當將x1定為換入變量后，繼續利用上述方法定為換入變量后，繼續利用上述方法確定換出變量，繼續迭代，再得到一個基可確定換出變量，

50、繼續迭代，再得到一個基可行解行解X(2)=(2,3,0,8,0)T再經過一次迭代，再得到一個基可行解再經過一次迭代，再得到一個基可行解X(3)=(4,2,0,0,4)T4x1=164x2=12x1+2x2=8x1x248Q1 4Q4 30Q2 (4,2)Z=2x1+3x2 Q3對于線性規劃問題：對于線性規劃問題：Max Z=CTX AX=bMax Z=CTX AX=b，X0X0，可用如下三，可用如下三個判別定理來判別線性規劃問題能否曾經獲得最優解或為無個判別定理來判別線性規劃問題能否曾經獲得最優解或為無界解。界解。 判別定理判別定理1 1 設設X X為線性規劃的一個基可行解，且對于一為線性規劃

51、的一個基可行解，且對于一切切jJjJJ J為非基變量的下標集有為非基變量的下標集有j0j0，那么，那么X X為為線性規劃的最優解。線性規劃的最優解。 判別定理判別定理2 2 設設X X為線性規劃的一個基可行解，且對于一為線性規劃的一個基可行解，且對于一切切jJjJJ J為非基變量的下標集有為非基變量的下標集有j 0j 0，同時有，同時有某個非基變量的檢驗數某個非基變量的檢驗數k=0( kJ)k=0( kJ)，那么該線性規，那么該線性規劃有無窮多最優解。劃有無窮多最優解。 判別定理判別定理3 3 設設X X為線性規劃的一個基可行解，假設有為線性規劃的一個基可行解，假設有k0 ( kJ) k0 (

52、 kJ) ，且，且pk0pk0，即，即aik 0aik 0i=1,mi=1,m，那么該線性規劃問題具有無界解無最優解。那么該線性規劃問題具有無界解無最優解。一、步驟一、步驟Step 1. 化化LP問題為規范型問題為規范型,建立初始單純形表建立初始單純形表;Step 2. 假設一切檢驗數假設一切檢驗數0,那么最優解已到達。那么最優解已到達。 否那么否那么,計算計算 , 選取選取k 所對應的變量所對應的變量xk 為換入變量進基變量為換入變量進基變量;最大最大檢驗數規那么檢驗數規那么Step 3. 計算計算 ,選取選取l 所對應所對應的變量的變量xl 為換出變量出基變量為換出變量出基變量;最小比值規

53、那么最小比值規那么Step 4. 以以alk為主元素進展旋轉運算為主元素進展旋轉運算,轉轉Step 2;min|0illikiiklkbbaaa= = = =max|0kjjj= = 第四節第四節 單純形法的步驟單純形法的步驟cj CB XB b x1 x2 xm xm+1 xn j 基可行解：基可行解： x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 01.1.初始單純形表初始單純形表c1 c2 cm cm+1 cnc1 x1 c2 x2 cm xmb1 b2 bm1 0 0 a1, m+1 a1n0 1 0 a2, m+1 a2n 0 0 1 am, m+1

54、 amn0 0 0 m+1 n-CBTB-1b對于上述單純形表：對于上述單純形表：1 1一個基對應一個單純形表，且單純形表中必需有一一個基對應一個單純形表，且單純形表中必需有一個初始單位基。個初始單位基。2 2從單純形表中，可立刻得到一個基可行解：從單純形表中，可立刻得到一個基可行解： x1=b1, x1=b1, x2=b2, , xm=bm , xm+1=xm+2= =xn= 0 x2=b2, , xm=bm , xm+1=xm+2= =xn= 03 3用檢驗數的計算公式很容易計算檢驗數，并可根據用檢驗數的計算公式很容易計算檢驗數，并可根據三個判別定理判別上述基可行解能否為最優解或線性三個判

55、別定理判別上述基可行解能否為最優解或線性規劃問題無最優解。規劃問題無最優解。2.2.換入變量進基變量的選擇換入變量進基變量的選擇cj c1 c2 cm cm+1 ck cn CB XB b x1 x2 xm xm+1 xk xn c1 x1 c2 x2 cm xmb1 b2 bm 1 0 0 a1, m+1 a1k a1n 0 1 0 a2, m+1 a2k a2n 0 0 1 am, m+1 amk amnj -CBTB-1b 0 0 0 m+1 k n選取選取 所對應的變量所對應的變量xk xk 為換入變量。為換入變量。max|0kjjj= = 3.3.換出變量出基變量的選擇換出變量出基變

56、量的選擇cj c1 cl cm cm+1 ck cn CB XB b x1 xl xm xm+1 xk xn c1 x1 cl xl cm xmb1 bl bm 1 0 0 a1, m+1 a1k a1n 0 1 0 al, m+1 alk aln 0 0 1 am, m+1 amk amn1 l mj -CBTB-1b 0 0 0 m+1 k n選取選取 所對應的變量所對應的變量xl xl 為換出變量。為換出變量。min|0illikiiklkbbaaa= = = =4.4.旋轉運算旋轉運算cj c1 cl cm cm+1 ck cn CB XB b x1 xl xm xm+1 xk xn

57、c1 x1 cl xl cm xmb1 bl bm 1 0 0 a1,m+1 a1k a1n 0 1 0 al,m+1 alk aln 0 0 1 am,m+1 amk amnj ck xkbl /alk0 1/alk 0 al, m+1/alk1 aln/alk b11 -a1k/alk 0 a1, m+1 0 a1nbm0 -amk/alk1 am, m+1 0 amn二、實例二、實例 0,121684243221221121xxxxxxxxMaxZ化為規范型化為規范型 5 , 4 , 3 , 2 , 1, 01241648232524132121jxxxxxxxxxxMaxZj單純形表算

58、法單純形表算法cj CB XB b x1 x2 x3 x4 x5 j 以以4為主元素進展旋為主元素進展旋轉運算，轉運算，x2為換入變為換入變量，量，x5為換出變量為換出變量cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 0 x3 0 x4 3 x2 2 16 3 1 0 1 0 -1/2 2 4 0 0 1 0 4 0 1 0 0 1/4 -j -9 2 0 0 0 -3/4以以11為主元素進展為主元素進展運算，運算，x1x1為換入變為換入變量，量， x3 x3為換出變量為換出變量0 x3 0 x4 0 x52 3 0 0 0 8 1612 1 2 1 0 0 4 0

59、0 1 0 0 4 0 0 1 2 3 0 0 004-3cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x4 3 x2 2 8 3 1 0 1 0 -1/2 - 0 0 -4 1 2 4 0 1 0 0 1/4 12j -13 0 0 -2 0 1/4 以以22為主元素進展運為主元素進展運算，算，x5x5為換入變量，為換入變量， x4x4為換出變量為換出變量cj 2 3 0 0 0 CB XB b x1 x2 x3 x4 x5 2 x1 0 x5 3 x2 4 4 2 1 0 0 1/4 0 0 0 -2 1/2 1 0 1 1/2 -1/8 0 j -

60、14 0 0 -3/2 -1/8 0此時到達最優解：此時到達最優解：X*=(4, 2)T, Max Z=14。4x1=164x2=12x1+2x2=8x1x2484O三、單純形表與圖解法的對應關系三、單純形表與圖解法的對應關系X1=(0,0)T, Z1=0X2=(0,3)T, Z2=9X3=(2,3)T, Z3=13X4=(4,2)T, Z4=14Q1Q2QQ3基可行解基可行解 基可行解基可行解 迭代迭代 頂點頂點 相鄰的頂點相鄰的頂點迭代迭代 圖解法：圖解法：單純形表算法：單純形表算法：對于極小化問題，其最優解的斷定定理和進基變量的選取和對于極小化問題，其最優解的斷定定理和進基變量的選取和極