第一章線性規(guī)劃與單純形法

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

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

3、排出的工業(yè)污水流到第二化工廠以前，有20可自然凈化?？勺匀粌艋８鶕?jù)環(huán)保要求，河流中工業(yè)污水的含量應不大于根據(jù)環(huán)保要求，河流中工業(yè)污水的含量應不大于0.2。這兩個工。這兩個工廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成廠都需各自處理一部分工業(yè)污水。第一化工廠處理工業(yè)污水的成本是本是1000元元/萬立方米，第二化工廠處理工業(yè)污水的成本是萬立方米，第二化工廠處理工業(yè)污水的成本是800元元/萬立方米?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應處理多萬立方米?，F(xiàn)在要問在滿足環(huán)保要求的條件下，每廠各應處理多少工業(yè)污水，使這兩個工廠總的處理工業(yè)污水費用最小。少工業(yè)污水，使這兩個工廠總的處理工業(yè)污

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線性規(guī)劃的一般模型線性規(guī)劃的一般模型 0,),(),(),(. max(min)21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxat sxcxcxcz技術(shù)系數(shù)技術(shù)系數(shù)價值系價值系數(shù)數(shù)資源系數(shù)資源系數(shù)例例1 某工廠在計劃期內(nèi)要安排某工廠在計劃期內(nèi)要安排、兩兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位

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

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

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

9、sxxz0,25 . 01.22max) 3(21212121xxxxxxtsxxz0,330.max)4(21212121xxxxxxtsxxz171.3 線性規(guī)劃問題的標準形式我們規(guī)定的標準形式要求：我們規(guī)定的標準形式要求：w目標函數(shù)求極大值目標函數(shù)求極大值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 xaxa xbx xx11jmax i=1,2,m.x0 j=1,2,nnjjjnijjijzc xa xbst1max.0 j=1,2,nnjjjjzCXP xstxbmax.0

11、zCXAXstXb一般形式簡寫形式向量形式矩陣形式201.4 線性規(guī)劃問題解的概念可行解：滿足所有約束條件的解，稱為線性規(guī)劃問題的可行：滿足所有約束條件的解，稱為線性規(guī)劃問題的可行解。解。最優(yōu)解：使目標函數(shù)值達到最優(yōu)的可行解。：使目標函數(shù)值達到最優(yōu)的可行解?；涸O：設A是約束方程組的是約束方程組的mn維系數(shù)矩陣，其秩為維系數(shù)矩陣，其秩為m。B是矩是矩陣中陣中m階非奇異子矩陣，則稱階非奇異子矩陣，則稱B是線性規(guī)劃問題的一個基。是線性規(guī)劃問題的一個基?；兞浚号c基向量對應的變量。：與基向量對應的變量。非基變量：與非基向量對應的變量。：與非基向量對應的變量。基解：令非基變量為零，求解方程組：令非基變

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)34

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

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

15、)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有時目標函數(shù)可能在多個頂點處達到最大值有時目標函數(shù)可能在多個

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

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

18、xxxxxxxstxxx 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+2

19、x2=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無窮多最優(yōu)解舉例無窮多最優(yōu)解舉例3912123142512345max2428416

20、.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 x

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

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

23、的所有系數(shù)都小于等于零，則該線性規(guī)劃問題具有無界解（無最優(yōu)解）。劃問題具有無界解（無最優(yōu)解）。433.4 基變換（一個頂點變換到另一個頂點）w換入變量確定：一般選擇絕對值最大的，但換入變量確定：一般選擇絕對值最大的，但也可以任選或按最小號碼選。也可以任選或按最小號碼選。w換出變量確定：最小比值原則。其原理是保換出變量確定：最小比值原則。其原理是保證所有變量都為非負。證所有變量都為非負。443.5 迭代（旋轉(zhuǎn)運算） 利用系數(shù)的增廣矩陣進行初等變換來實現(xiàn)。利用系數(shù)的增廣矩陣進行初等變換來實現(xiàn)。w將主元素變?yōu)閷⒅髟刈優(yōu)?。w將入基變量所對應的列向量變?yōu)閱挝幌蛄俊⑷牖兞克鶎牧邢蛄孔優(yōu)閱挝幌蛄?/p>

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

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目標函數(shù)求極大目標函數(shù)求極大w初始可行基（單位陣）初始可行基（單

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

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

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

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

30、數(shù)，要求其實現(xiàn)最小化。用單純形法求解此模型，若目標函數(shù)值等于零，單純形法求解此模型，若目標函數(shù)值等于零，說明原問題有基可行解，可以進行第二階段計說明原問題有基可行解，可以進行第二階段計算，否則原問題無可行解，應停止計算。算，否則原問題無可行解，應停止計算。w第二階段：將第一階段得到的最終表，除去人工第二階段：將第一階段得到的最終表，除去人工變量，將目標函數(shù)行的系數(shù)，換原問題的目標函數(shù)變量，將目標函數(shù)行的系數(shù)，換原問題的目標函數(shù)系數(shù)，作為第二階段計算的初始表。系數(shù)，作為第二階段計算的初始表。 實質(zhì)是：第一階段為原問題找出了一個基可行解。實質(zhì)是：第一階段為原問題找出了一個基可行解。56例例9123

31、12312313123min3211423.21,0zxxxxxxxxxstxxx xx 1231234123513123min3211423.21,0zxxxxxxxxxxxstxxx x x 0,12324112.min2132123115321432121yyxxxyxxyxxxxxxxxtsyyz第一階段原問題1.6123123123123max2357.2510,0zxxxxxxstxxxx x x0,10527.532max43214321321321xxxxxxxxxxxtsxxxz0,10527.min21432124321132121yyxxxxyxxxxyxxxtsyyw0,10527.532max21432124321132121321yyxxxxyxxxxyxxxtsMyMyxxxz第一階段605.2 退化 單純形法計算中，用最小比值原則確定出基變單純形法