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

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

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

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

4、水費(fèi)用最小。工廠1工廠2500萬立方米200萬立方米5例3： 下料問題 某工廠要做某工廠要做100套鋼架，每套有長(zhǎng)套鋼架，每套有長(zhǎng)2.9米、米、2.1米和米和1.5米的圓鋼組成，已知原料長(zhǎng)米的圓鋼組成，已知原料長(zhǎng)7.4米，米，問應(yīng)如何下料使需用的原材料最省。問應(yīng)如何下料使需用的原材料最省。方案方案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、合計(jì)合計(jì)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ù)價(jià)值系價(jià)值系數(shù)數(shù)資源系數(shù)資源系數(shù)例例1 某工廠在計(jì)劃期內(nèi)要安排某工廠在計(jì)劃期內(nèi)要安排、兩兩種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位產(chǎn)品種產(chǎn)品的生產(chǎn)，已知生產(chǎn)單位

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

7、bxaxaxat sxcxcxcz價(jià)值系數(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)解無可行解無可行解無界解無界解圖解法的局限與啟示圖解法的局限與啟示 局限局限：只能求解兩個(gè)變量的線性規(guī)劃問題只能求解兩個(gè)變量的線性規(guī)劃問題 啟示啟示: 通過圖解法，能夠直觀的看到，如果線性規(guī)通過圖解法，能夠直觀的看到，如果線性規(guī)劃問題有最優(yōu)解，一定能夠在其頂點(diǎn)上達(dá)到最優(yōu)。劃問題有最優(yōu)解，一定能夠在其頂點(diǎn)上達(dá)到最優(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ī)劃問題的標(biāo)準(zhǔn)形式我們規(guī)定的標(biāo)準(zhǔn)形式要求：我們規(guī)定的標(biāo)準(zhǔn)形式要求：w目標(biāo)函數(shù)求極大值目標(biāo)函數(shù)求極大值w所有約束為等式所有約束為等式w約束條件右端項(xiàng)都大于等于零約束條件右端項(xiàng)都大于等于零w所有變量都大于等于零所有變量都大于等于零 18練練 習(xí)習(xí)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一般形式簡(jiǎn)寫形式向量形式矩陣形式201.4 線性規(guī)劃問題解的概念可行解：滿足所有約束條件的解，稱為線性規(guī)劃問題的可行：滿足所有約束條件的解，稱為線性規(guī)劃問題的可行解。解。最優(yōu)解：使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解。：使目標(biāo)函數(shù)值達(dá)到最優(yōu)的可行解?；涸O(shè)：設(shè)A是約束方程組的是約束方程組的mn維系數(shù)矩陣，其秩為維系數(shù)矩陣，其秩為m。B是矩是矩陣中陣中m階非奇異子矩陣，則稱階非奇異子矩陣，則稱B是線性規(guī)劃問題的一個(gè)基。是線性規(guī)劃問題的一個(gè)基?；兞浚号c基向量對(duì)應(yīng)的變量。：與基向量對(duì)應(yīng)的變量。非基變量：與非基向量對(duì)應(yīng)的變量。：與非基向量對(duì)應(yīng)的變量。基解：令非基變量為零，求解方程組：令非基變

12、量為零，求解方程組,得到一個(gè)基解。得到一個(gè)基解。基可行解：滿足非負(fù)條件的基解。：滿足非負(fù)條件的基解?？尚谢簩?duì)應(yīng)于基可行解的基，為可行基。：對(duì)應(yīng)于基可行解的基，為可行基。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ù)列向量是否一定線性無關(guān)？基變量的系數(shù)列向量是否一定線性無關(guān)？22解之間的關(guān)系解之間的關(guān)系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 基本概念基本概念凸集凸集：設(shè)：設(shè)K是是n維歐式空間的一點(diǎn)集，若任意兩維歐式空間的一點(diǎn)集，若任意兩點(diǎn)的連線上的一切點(diǎn)都屬于點(diǎn)的連線上的一切點(diǎn)都屬于K；則稱；則稱K為凸集。為凸集。凸集凸集凸集凸集不是凸集不是凸集極點(diǎn)極點(diǎn)) 10()1 ()2()1(XXX26兩點(diǎn)連線上的點(diǎn)的數(shù)學(xué)表示方法兩點(diǎn)連線上的點(diǎn)的數(shù)學(xué)表示方法M1(x1)M(x)M2(x2)221xxxx121xxx01121MMMM(x,y)M2(x2,y2)M1(x1,y1

15、)yx0212:1MMM M222121,xxyyxxyy121211xxxyyy12121xxxyyy121MMM01212:1MMM M27282.2 幾個(gè)定理幾個(gè)定理例題例題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í)目標(biāo)函數(shù)可能在多個(gè)頂點(diǎn)處達(dá)到最大值有時(shí)目標(biāo)函數(shù)可能在多個(gè)

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

17、有最優(yōu)解，域的一個(gè)頂點(diǎn)；若線性規(guī)劃問題有最優(yōu)解，必在某頂點(diǎn)上得到。必在某頂點(diǎn)上得到。33第三節(jié)第三節(jié) 單純形法單純形法 單純形法的基本思路單純形法的基本思路：根據(jù)問題的標(biāo)準(zhǔn)，從：根據(jù)問題的標(biāo)準(zhǔn)，從可行域中某個(gè)基可行解（一個(gè)頂點(diǎn)）開始，可行域中某個(gè)基可行解（一個(gè)頂點(diǎn)）開始，轉(zhuǎn)換到另一個(gè)基可行解（頂點(diǎn)），并且使目轉(zhuǎn)換到另一個(gè)基可行解（頂點(diǎn)），并且使目標(biāo)函數(shù)值達(dá)到最優(yōu)時(shí)，問題就得到了最優(yōu)解。標(biāo)函數(shù)值達(dá)到最優(yōu)時(shí)，問題就得到了最優(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入基，由方程組可知， 可以無限增加，所以目標(biāo)函數(shù)可以趨向于無窮大，此時(shí)為無界解。2x2x413.2 初始可行基的確定1.直接觀察直接觀察2.對(duì)所有約束條件是對(duì)所有約束條件是“”的不等式，可在每的不等式，可在每個(gè)不等式左端引入一個(gè)松弛變量，變成標(biāo)準(zhǔn)個(gè)不等式左端引入一個(gè)松弛變量，變成標(biāo)準(zhǔn)型，從而得到一個(gè)初始基可行解。型，從而得到一個(gè)初始基可行解。3.不存在單位陣時(shí)，采用人造基方法。不存在單位陣時(shí)，采用人造基方法。423.3 最優(yōu)性檢驗(yàn)與解的判

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

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

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

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

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

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

28、入人工在一個(gè)線性規(guī)劃問題的約束條件中加入人工變量后，要求人工變量對(duì)目標(biāo)函數(shù)取值沒有變量后，要求人工變量對(duì)目標(biāo)函數(shù)取值沒有影響，為此假定人工變量在目標(biāo)函數(shù)中的系影響，為此假定人工變量在目標(biāo)函數(shù)中的系數(shù)為（數(shù)為（-M）（）（M為任意大的數(shù)），為任意大的數(shù)），（若目標(biāo)函數(shù)值為求最小值，則人工變量在目（若目標(biāo)函數(shù)值為求最小值，則人工變量在目標(biāo)函數(shù)中的系數(shù)為標(biāo)函數(shù)中的系數(shù)為M）。）。w這樣目標(biāo)函數(shù)要實(shí)現(xiàn)最大化時(shí)，必須把人工這樣目標(biāo)函數(shù)要實(shí)現(xiàn)最大化時(shí)，必須把人工變量從基變量換出，否則目標(biāo)函數(shù)不可能實(shí)變量從基變量換出，否則目標(biāo)函數(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)造僅含人工變量的目標(biāo)函數(shù)，要求其實(shí)現(xiàn)最小化。用人工變量的目標(biāo)函

30、數(shù)，要求其實(shí)現(xiàn)最小化。用單純形法求解此模型，若目標(biāo)函數(shù)值等于零，單純形法求解此模型，若目標(biāo)函數(shù)值等于零，說明原問題有基可行解，可以進(jìn)行第二階段計(jì)說明原問題有基可行解，可以進(jìn)行第二階段計(jì)算，否則原問題無可行解，應(yīng)停止計(jì)算。算，否則原問題無可行解，應(yīng)停止計(jì)算。w第二階段：將第一階段得到的最終表，除去人工第二階段：將第一階段得到的最終表，除去人工變量，將目標(biāo)函數(shù)行的系數(shù)，換原問題的目標(biāo)函數(shù)變量，將目標(biāo)函數(shù)行的系數(shù)，換原問題的目標(biāo)函數(shù)系數(shù)，作為第二階段計(jì)算的初始表。系數(shù)，作為第二階段計(jì)算的初始表。 實(shí)質(zhì)是：第一階段為原問題找出了一個(gè)基可行解。實(shí)質(zhì)是：第一階段為原問題找出了一個(gè)基可行解。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 退化 單純形法計(jì)算中，用最小比值原則確定出基變單純形法