1、1第一章第一章線性規劃與單純形法線性規劃與單純形法2第一節第一節 線性規劃問題及其數學模型線性規劃問題及其數學模型1.1 問題的提出問題的提出例例1 某工廠在計劃期內要安排某工廠在計劃期內要安排、兩種產品的生產，兩種產品的生產，已知生產單位產品所需的設備臺時及已知生產單位產品所需的設備臺時及A、B兩種原材料兩種原材料的消耗以及資源的限制，如下表：的消耗以及資源的限制，如下表：問題：如何安排生產才能使工廠獲利最多？問題：如何安排生產才能使工廠獲利最多？ 資資源源限限制制 設設 備備 1 2 8 臺臺時時 原原料料 A 4 0 16 千千克克 原原料料 B 0 4 12 千千克克 單單位位產產品品

2、獲獲利利 2 元元 3 元元 3線性規劃模型三個要素決策變量決策變量 目標函數目標函數約束條件約束條件4例例2 靠近某河流有兩個化工廠，流經第一化工廠的河流流量為每靠近某河流有兩個化工廠，流經第一化工廠的河流流量為每天天500萬立方米，在兩個工廠之間有一條流量為每天萬立方米，在兩個工廠之間有一條流量為每天200萬立方米萬立方米的支流。第一化工廠每天排放含有某種有害物質的工業污水的支流。第一化工廠每天排放含有某種有害物質的工業污水2萬萬立方米，第二化工廠每天排放這種工業污水立方米，第二化工廠每天排放這種工業污水1.4萬立方米。從第一萬立方米。從第一化工廠排出的工業污水流到第二化工廠以前，有化工廠

3、排出的工業污水流到第二化工廠以前，有20可自然凈化。可自然凈化。根據環保要求，河流中工業污水的含量應不大于根據環保要求，河流中工業污水的含量應不大于0.2。這兩個工。這兩個工廠都需各自處理一部分工業污水。第一化工廠處理工業污水的成廠都需各自處理一部分工業污水。第一化工廠處理工業污水的成本是本是1000元元/萬立方米，第二化工廠處理工業污水的成本是萬立方米，第二化工廠處理工業污水的成本是800元元/萬立方米。現在要問在滿足環保要求的條件下，每廠各應處理多萬立方米。現在要問在滿足環保要求的條件下，每廠各應處理多少工業污水，使這兩個工廠總的處理工業污水費用最小。少工業污水，使這兩個工廠總的處理工業污

4、水費用最小。工廠1工廠2500萬立方米200萬立方米5例3： 下料問題 某工廠要做某工廠要做100套鋼架，每套有長套鋼架，每套有長2.9米、米、2.1米和米和1.5米的圓鋼組成，已知原料長米的圓鋼組成，已知原料長7.4米，米，問應如何下料使需用的原材料最省。問應如何下料使需用的原材料最省。方案方案1 1方案方案2 2方案方案3 3方案方案4 4方案方案5 5方案方案6 6方案方案7 7方案方案8 82.92.9m m1 12 20 01 10 01 10 00 02.12.1m m0 00 02 22 21 11 13 30 01.51.5m m3 31 12 20 03 31 10 04 4

5、合計合計7.47.47.37.37.27.27.17.16.66.66.56.56.36.36.06.0剩余料頭剩余料頭0 00.10.10.20.20.30.30.80.80.90.91.11.11.41.46線性規劃的一般模型線性規劃的一般模型 0,),(),(),(. max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxat sxcxcxcz技術系數技術系數價值系價值系數數資源系數資源系數例例1 某工廠在計劃期內要安排某工廠在計劃期內要安排、兩兩種產品的生產，已知生產單位產品種產品的生產，已知生產單位

6、產品所需的設備臺時及所需的設備臺時及A、B兩種原材料兩種原材料的消耗以及資源的限制，如下表：的消耗以及資源的限制，如下表：問題：如何安排生產才能使工廠獲問題：如何安排生產才能使工廠獲利最多？利最多？7 資資源源限限制制 設設 備備 1 2 8 臺臺時時 原原料料 A 4 0 16 千千克克 原原料料 B 0 4 12 千千克克 單單位位產產品品獲獲利利 2 元元 3 元元 0,12416482.32max21212121xxxxxxtsxxz0,),(),(),(. max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxa

7、bxaxaxat sxcxcxcz價值系數技術系數資源系數34840 x2x1A1.2 線性規劃的圖解法0,12416482.32max21212121xxxxxxtsxxz1.畫可行域2.畫等值線3.找最優解步驟惟一最優解34840 x2x1AB0,12416482.42max21212121xxxxxxtsxxz無窮多最優解（多重最優解）34840 x2x1-2420,12416482.32max2121212121xxxxxxxxtsxxz無可行解x1x20240,242.max21212121xxxxxxtsxxz無界解無界解解的情況總結解的情況總結12有最優解有最優解無最優解無最優解

8、惟一最優解惟一最優解無窮多最優解無窮多最優解無可行解無可行解無界解無界解圖解法的局限與啟示圖解法的局限與啟示 局限局限：只能求解兩個變量的線性規劃問題只能求解兩個變量的線性規劃問題 啟示啟示: 通過圖解法，能夠直觀的看到，如果線性規通過圖解法，能夠直觀的看到，如果線性規劃問題有最優解，一定能夠在其頂點上達到最優。劃問題有最優解，一定能夠在其頂點上達到最優。131434840 x2x1A惟一最優解1534840 x2x1AB無窮多最優解（多重最優解）160,4150105.3max) 1 (212212121xxxxxxxtsxxz0,233.5 . 1min)2(21212121xxxxxxt

9、sxxz0,25 . 01.22max) 3(21212121xxxxxxtsxxz0,330.max)4(21212121xxxxxxtsxxz171.3 線性規劃問題的標準形式我們規定的標準形式要求：我們規定的標準形式要求：w目標函數求極大值目標函數求極大值w所有約束為等式所有約束為等式w約束條件右端項都大于等于零約束條件右端項都大于等于零w所有變量都大于等于零所有變量都大于等于零 18練練 習習123123123123123min2372.325,0,zxxxxxxxxxstxxxx xx 無約束052222. .max121212121xxxxxxxtsxxz0,522327.332m

10、in765421542175421654215421xxxxxxxxxxxxxxxxxxxxtsxxxxz7 , 6 , 5 , 4 , 3 , 1; 0522222. .max743164315431431ixxxxxxxxxxxxxtsxxxzi191 12211 11221121 1222221 12212max.,0nnnnnnmmmnnmnzc xc xc xa xa xa xba xa xa xbsta xa xa xbx xx11jmax i=1,2,m.x0 j=1,2,nnjjjnijjijzc xa xbst1max.0 j=1,2,nnjjjjzCXP xstxbmax.

11、0zCXAXstXb一般形式簡寫形式向量形式矩陣形式201.4 線性規劃問題解的概念可行解：滿足所有約束條件的解，稱為線性規劃問題的可行：滿足所有約束條件的解，稱為線性規劃問題的可行解。解。最優解：使目標函數值達到最優的可行解。：使目標函數值達到最優的可行解。基：設：設A是約束方程組的是約束方程組的mn維系數矩陣，其秩為維系數矩陣，其秩為m。B是矩是矩陣中陣中m階非奇異子矩陣，則稱階非奇異子矩陣，則稱B是線性規劃問題的一個基。是線性規劃問題的一個基。基變量：與基向量對應的變量。：與基向量對應的變量。非基變量：與非基向量對應的變量。：與非基向量對應的變量。基解：令非基變量為零，求解方程組：令非基

12、變量為零，求解方程組,得到一個基解。得到一個基解。基可行解：滿足非負條件的基解。：滿足非負條件的基解。可行基：對應于基可行解的基，為可行基。：對應于基可行解的基，為可行基。12341234282440(1,2,3,4)jxxxxxxxxxj21例題12341234282440(1,2,3,4)jxxxxxxxxxjTXB)0 , 0 , 2 , 6(,4211)1 (1TXB)0 ,12, 0 , 4(,1211)2(2TXB)512, 0 , 0 ,516(,1221)3(3TXB)0 ,536,54, 0(,1411)4(4TXB)736, 0 ,716, 0(,1421)5(5TXB)3

13、4,316, 0 , 0(,1121)6(6思考思考w非基變量取值是否為零？非基變量取值是否為零？w取值為零的變量是否一定為非基變量？取值為零的變量是否一定為非基變量？w大于零的變量是否是基變量？大于零的變量是否是基變量？w基變量的系數列向量是否一定線性無關？基變量的系數列向量是否一定線性無關？22解之間的關系解之間的關系23可行解基解非可行解基可行解例題例題249 , 2 , 1, 002226.9832763154321jxxxxxxxxxxxxxxtsjTTTXXX)0 , 0 , 0 , 0 , 0 , 0 ,27,47,43()0 , 0 , 0 , 0 , 3 , 0 , 2 ,

14、1 , 0()0 , 0 , 2 , 0 , 6 , 0 , 0 , 0 , 0()3()2()1(25第二節第二節 線性規劃問題的幾何意義線性規劃問題的幾何意義2.1 基本概念基本概念凸集凸集：設：設K是是n維歐式空間的一點集，若任意兩維歐式空間的一點集，若任意兩點的連線上的一切點都屬于點的連線上的一切點都屬于K；則稱；則稱K為凸集。為凸集。凸集凸集凸集凸集不是凸集不是凸集極點極點) 10()1 ()2()1(XXX26兩點連線上的點的數學表示方法兩點連線上的點的數學表示方法M1(x1)M(x)M2(x2)221xxxx121xxx01121MMMM(x,y)M2(x2,y2)M1(x1,y

15、1)yx0212:1MMM M222121,xxyyxxyy121211xxxyyy12121xxxyyy121MMM01212:1MMM M27282.2 幾個定理幾個定理例題例題299 , 2 , 1, 002226.9832763154321jxxxxxxxxxxxxxxtsjTTTXXX)0 , 0 , 0 , 0 , 0 , 0 ,27,47,43()0 , 0 , 0 , 0 , 3 , 0 , 2 , 1 , 0()0 , 0 , 2 , 0 , 6 , 0 , 0 , 0 , 0()3()2()1(30特殊情況特殊情況n有時目標函數可能在多個頂點處達到最大值有時目標函數可能在多

16、個頂點處達到最大值。這時在這些頂點的凸組合上也達到最大值。這時在這些頂點的凸組合上也達到最大值。稱這種線性規劃問題有無限多個（無窮多。稱這種線性規劃問題有無限多個（無窮多個）最優解。個）最優解。n若可行域無界，則可能無最優解，也可能有若可行域無界，則可能無最優解，也可能有最優解，若有也必定在某頂點上得到。最優解，若有也必定在某頂點上得到。31結論結論 線性規劃問題的所有可行解構成的集合線性規劃問題的所有可行解構成的集合是凸集，也可能為無界域，它們有有限個頂是凸集，也可能為無界域，它們有有限個頂點，線性規劃問題的每個基可行解對應可行點，線性規劃問題的每個基可行解對應可行域的一個頂點；若線性規劃問

17、題有最優解，域的一個頂點；若線性規劃問題有最優解，必在某頂點上得到。必在某頂點上得到。33第三節第三節 單純形法單純形法 單純形法的基本思路單純形法的基本思路：根據問題的標準，從：根據問題的標準，從可行域中某個基可行解（一個頂點）開始，可行域中某個基可行解（一個頂點）開始，轉換到另一個基可行解（頂點），并且使目轉換到另一個基可行解（頂點），并且使目標函數值達到最優時，問題就得到了最優解。標函數值達到最優時，問題就得到了最優解。343.1 舉例舉例12121212max2328416.412,0zxxxxxstxx x12345123142512345max2300028416.412,0zxx

18、xxxxxxxxstxxx x x x x12,34512100,4001004001AP P P P P35312415282164124xxxxxxx12023zxx3154125122164134xxxxxxx153924zxx 10,3,2,16,0TX 0(0,0,8,16,12)TX52534531413248212)3(xxxxxxxxTX)0 , 8 , 0 , 3 , 2()2(5341213xxZ43243541812122124414)4(xxxxxxxx 34,2,0,0,4TX43812314xxZ(1)(2)36幾何意義分析 12345678910123456x1+

19、2x2=84x2=124x1=16x2x1Q1Q2Q3Q437312415282164124xxxxxxx12023zxx 0(0,0,8,16,12)TX(1)25414234124144124)2(xxxxxxx422138)12, 0 , 4 , 0 , 4(xxZXT43541432212441481212)3(xxxxxxxx43812314)4 , 0 , 0 , 2 , 4(xxZXT38幾何意義分析 12345678910123456x1+2x2=84x2=124x1=16x2x1Q1Q2Q3Q4無窮多最優解舉例無窮多最優解舉例3912123142512345max242841

20、6.412,0zxxxxxxxstxxx x x x x312415282(1)164124xxxxxxx12024zxx 0(0,0,8,16,12)TX324145214241(2)44124xxxxxxx(1)24(4,0,4,0,12)1842TXZxx43541432212441481212)3(xxxxxxxx(2)3(4,2,0,0,4)162TXZx251354351341(4)22842xxxxxxxx(3)3(2,3,0,8,0)162TXZx(2)(3)(1)0,1XXX無界解舉例無界解舉例40121231241234max24.2,0zxxxxxst xxxx x x

21、x3124124 2(1)2xxxxxx (0)12(0,0,4,2)TXZxx32412482(2)2xxxxxx (1)24(2,0,8,0)22TXZxx入基，由方程組可知， 可以無限增加，所以目標函數可以趨向于無窮大，此時為無界解。2x2x413.2 初始可行基的確定1.直接觀察直接觀察2.對所有約束條件是對所有約束條件是“”的不等式，可在每的不等式，可在每個不等式左端引入一個松弛變量，變成標準個不等式左端引入一個松弛變量，變成標準型，從而得到一個初始基可行解。型，從而得到一個初始基可行解。3.不存在單位陣時，采用人造基方法。不存在單位陣時，采用人造基方法。423.3 最優性檢驗與解的

22、判別（目標函數求極大）（目標函數求極大）w最優解判別定理：最優解判別定理： 若非基變量的系數（檢驗數）都小于等于零，則為若非基變量的系數（檢驗數）都小于等于零，則為最優解。最優解。w無窮多最優解判別準則：無窮多最優解判別準則： 若非基變量的檢驗數都小于等于零，且其中至少有若非基變量的檢驗數都小于等于零，且其中至少有一個為零，則線性規劃問題有無窮多個最優解。一個為零，則線性規劃問題有無窮多個最優解。w無界解（無最優解）判別定理：無界解（無最優解）判別定理： 對于一個基可行解，若有一個檢驗數大于零，且該對于一個基可行解，若有一個檢驗數大于零，且該檢驗數對應的所有系數都小于等于零，則該線性規檢驗數對

23、應的所有系數都小于等于零，則該線性規劃問題具有無界解（無最優解）。劃問題具有無界解（無最優解）。433.4 基變換（一個頂點變換到另一個頂點）w換入變量確定：一般選擇絕對值最大的，但換入變量確定：一般選擇絕對值最大的，但也可以任選或按最小號碼選。也可以任選或按最小號碼選。w換出變量確定：最小比值原則。其原理是保換出變量確定：最小比值原則。其原理是保證所有變量都為非負。證所有變量都為非負。443.5 迭代（旋轉運算） 利用系數的增廣矩陣進行初等變換來實現。利用系數的增廣矩陣進行初等變換來實現。w將主元素變為將主元素變為1。w將入基變量所對應的列向量變為單位向量。將入基變量所對應的列向量變為單位向

24、量。1234512100 840010 1604001 12xxxxx b1234510101/2 2400101601001/4 3xxxxxb45第四節第四節 單純形法的計算步驟單純形法的計算步驟4.1 單純形表若線性規劃問題目標函數為：若線性規劃問題目標函數為：約束條件為：約束條件為：1 122maxnnzc xc xc x11,111122,1122,110,1,2,mmnnmmnnmm mmmnnmjxaxa xbxaxa xbxaxa xbxjn增廣矩陣為：mmnmmnmnmbbbaaaaaa212,22, 211, 110001000146根據增廣矩陣設計計算表根據增廣矩陣設計計

25、算表473.1 舉例舉例12121212max2328416.412,0zxxxxxstxx x12345123142512345max2300028416.412,0zxxxxxxxxxxstxxx x x x x12,34512100,4001004001AP P P P P484.2 計算步驟計算步驟49例題例題121211212min232.321,0zxxxxxstxxx x121231412512345zmax 232.321,0zzxxxxxxxstxxxx x x x x 令50單純形法的求解步驟單純形法的求解步驟w目標函數求極大目標函數求極大w初始可行基（單位陣）初始可行基（

26、單位陣）w解的判別解的判別w所有非基變量檢驗數都小于零小于零，得惟一最優解w所有非基變量檢驗數都小于等于零小于等于零，且至少有一個為零，得無窮多最優解。w如果有一個非基變量的檢驗數大于大于零，而其在方程組中的系數都小于等于零，為無界解。w迭代迭代w入基變量：檢驗數大于大于零w出基變量：最小比值原則方程組求解（矩陣初等行變換）方程組求解（矩陣初等行變換）w目標函數求極小目標函數求極小w初始可行基（單位陣）初始可行基（單位陣）w解的判別解的判別w所有非基變量檢驗數都大于零大于零，得惟一最優解w所有非基變量檢驗數都大于等于零大于等于零，且至少有一個為零，得無窮多最優解。w如果有一個非基變量的檢驗數小

27、于小于零，而其在方程組中的系數都小于等于零，為無界解。w迭代迭代w入基變量：檢驗數小于小于零w出基變量：最小比值原則方程組求解（矩陣初等行變換）方程組求解（矩陣初等行變換）5152例例812312312313123min3211423.21,0zxxxxxxxxxstxxx x x 123123412351312345min3211423.21,0zxxxxxxxxxxxstxxx x x x x 0,12324112.21321231153214321yyxxxyxxyxxxxxxxxts第五節第五節 單純形法的進一步討論單純形法的進一步討論531.大大M法法w在一個線性規劃問題的約束條件中

28、加入人工在一個線性規劃問題的約束條件中加入人工變量后，要求人工變量對目標函數取值沒有變量后，要求人工變量對目標函數取值沒有影響，為此假定人工變量在目標函數中的系影響，為此假定人工變量在目標函數中的系數為（數為（-M）（）（M為任意大的數），為任意大的數），（若目標函數值為求最小值，則人工變量在目（若目標函數值為求最小值，則人工變量在目標函數中的系數為標函數中的系數為M）。）。w這樣目標函數要實現最大化時，必須把人工這樣目標函數要實現最大化時，必須把人工變量從基變量換出，否則目標函數不可能實變量從基變量換出，否則目標函數不可能實現最大化。現最大化。 54例例812312312313123min3

29、211423.21,0zxxxxxxxxxstxxx x x (4,1,9,0,0,0,0)2TXZ 123123412351312345min3211423.21,0zxxxxxxxxxxxstxxx x x x x 0,12324112.3min2132123115321432121321yyxxxyxxyxxxxxxxxtsMyMyxxxz原問題新問題552.兩階段法兩階段法w第一階段：不考慮原問題是否存在基可行解，第一階段：不考慮原問題是否存在基可行解，給原線性規劃問題加入人工變量，并構造僅含給原線性規劃問題加入人工變量，并構造僅含人工變量的目標函數，要求其實現最小化。用人工變量的目標

30、函數，要求其實現最小化。用單純形法求解此模型，若目標函數值等于零，單純形法求解此模型，若目標函數值等于零，說明原問題有基可行解，可以進行第二階段計說明原問題有基可行解，可以進行第二階段計算，否則原問題無可行解，應停止計算。算，否則原問題無可行解，應停止計算。w第二階段：將第一階段得到的最終表，除去人工第二階段：將第一階段得到的最終表，除去人工變量，將目標函數行的系數，換原問題的目標函數變量，將目標函數行的系數，換原問題的目標函數系數，作為第二階段計算的初始表。系數，作為第二階段計算的初始表。 實質是：第一階段為原問題找出了一個基可行解。實質是：第一階段為原問題找出了一個基可行解。56例例912312312313123min3211423.21,0zxxxxxxxxxs txxxxx 1231234123513123min3211423.21,0zxxxxxxxxxxxstxxx x x 0,12324112.min2132123115321432121yyxxxyxxyxxxxxxxxtsyyz第一階段原問題1.6123123123123max2357.2510,0zxxxxxxstxxxx x x0,10527.532max43214321321321xxxxxxxxxxx