第5章線性規(guī)劃問題

1、第5章 線性規(guī)劃方法Linear Programming線性規(guī)劃是最優(yōu)規(guī)劃模型的一種，在地理系統(tǒng)中，經(jīng)常碰到制定最優(yōu)規(guī)劃方案的問題，如： 在區(qū)域工業(yè)規(guī)劃中，要謀求制定最優(yōu)的工業(yè)結(jié)構(gòu)與投資規(guī)劃，使工業(yè)經(jīng)濟(jì)發(fā)展快，效益好。 在城市規(guī)劃中，要使社會(huì)、經(jīng)濟(jì)與環(huán)境協(xié)調(diào)起來，使城市達(dá)到最優(yōu)狀態(tài)。 任何規(guī)劃問題，均有兩個(gè)基本部分，即規(guī)劃目標(biāo)和約束條件。規(guī)劃目標(biāo)即為規(guī)劃方案優(yōu)劣的準(zhǔn)則；約束條件為規(guī)劃的限制條件，比如資源、資金、技術(shù)、政策限制等；解決問題的定量方法就是最優(yōu)規(guī)劃模型。最優(yōu)規(guī)劃模型是系統(tǒng)分析和系統(tǒng)設(shè)計(jì)中 最常見的一類數(shù)學(xué)模型，內(nèi)容極為豐富，應(yīng)用也極為廣泛。根據(jù)規(guī)劃目標(biāo)的多少根據(jù)約束條件與目標(biāo)函數(shù)的形

2、式根據(jù)規(guī)劃階段單目標(biāo)規(guī)劃多目標(biāo)規(guī)劃線性規(guī)劃、非線性規(guī)劃整數(shù)規(guī)劃、0-1規(guī)劃靜態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃 線性規(guī)劃問題的特征是目標(biāo)函數(shù)和約束條件都是線性關(guān)系。一 線性規(guī)劃問題及其數(shù)學(xué)模型二 圖解法解線性規(guī)劃問題三 線性規(guī)劃問題的標(biāo)準(zhǔn)形式四 線性規(guī)劃問題的單純形解法1.運(yùn)輸問題 某公司下屬3個(gè)冶煉廠B1,B2,B3, 需要某種礦石原料分別為17,18,15噸,公司從兩個(gè)采礦廠A1,A2分別采得此種礦石23,27噸,從各采礦廠到各冶煉廠的運(yùn)價(jià)列于表5.1中,問如何調(diào)運(yùn),可使總費(fèi)用最小?冶煉廠采礦廠運(yùn)費(fèi)(元/噸)B1 B2 B3A1 A2 50 60 7060 110 160表 5.1 設(shè)xij表示由采礦廠Ai(

3、i=1,2)運(yùn)往冶煉廠Bj (j=1,2,3)的礦石數(shù)量(噸),如表5.2所示.冶煉廠采礦廠B1 B2 B3A1 A2 x11 x12 x13x21 x22 x23收量(噸)17 18 15發(fā)量(噸)23 27 50表5.2 根據(jù)題意就是要求變量xij(i=1,2;j=1,2,3)的一組取值,滿足約束條件 并使總費(fèi)S=50 x11+60 x12+70 x13+60 x21+110 x22+160 x23的值最小冶煉廠采礦廠B1 B2 B3A1 A2 x11 x12 x13x21 x22 x23收量(噸)17 18 15發(fā)量(噸)23 27 50表5.2x11+x12+x13=23x21+x22

4、+x23=27x11+x21=17x12+x22=18x13+x23=15xij0(i=1,2;j=1,2,3)這個(gè)問題的數(shù)學(xué)模型可表示為:min S=50 x11+60 x12+70 x13+60 x21+110 x22+160 x23x11+x12+x13=23x21+x22+x23=27x11+x21=17x12+x22=18x13+x23=15xij0(i=1,2;j=1,2,3)2.資源最優(yōu)配置問題 某工廠生產(chǎn)兩種產(chǎn)品A,B,生產(chǎn)1千克A產(chǎn)品需用煤9噸,電力4千瓦,勞動(dòng)力3個(gè)(以工作日計(jì));生產(chǎn)1千克B產(chǎn)品需用煤4噸,電力5千瓦,勞動(dòng)力10個(gè).已知生產(chǎn)1千克A,B產(chǎn)品創(chuàng)造利潤分別為0

5、.7萬元和1.2萬元。由于條件限制，工廠只有煤360噸，電力200千瓦，勞動(dòng)力300個(gè)，如表5.3所示。問如何安排生產(chǎn)，使工廠總利潤最大？表5.3產(chǎn)品資源A B （千克）煤（噸） 電力（千瓦）勞動(dòng)力（個(gè)） 9 4 4 5 3 10利潤(萬元) 0.7 1.2 現(xiàn)有資源(噸)360 200300 消耗定額設(shè)x1,x2分別為兩種產(chǎn)品A，B的計(jì)劃產(chǎn)量，根據(jù)題意就是要求x1,x2的一組取值，滿足約束條件：9x1+4x23604x1+5x2 2003x1+10 x2 300 x10 , x2 0產(chǎn)品資源A B （千克）煤（噸） 電力（千瓦）勞動(dòng)力（個(gè)） 9 4 4 5 3 10利潤(萬元) 0.7 1.

6、2 現(xiàn)有資源(噸)360 200300 消耗定額并使總利潤S= 0.7x1+1.2x2最大 max S= 0.7x1+1.2x2這個(gè)問題的數(shù)學(xué)模型可表示為:9x1+4x23604x1+5x2 2003x1+10 x2 300 x10 , x2 03.最小成本問題 某公司有兩個(gè)服裝加工廠B1，B2，生產(chǎn)種型號(hào)的服裝A1，A2，A3，預(yù)測市場對種型號(hào)的服裝最低需求量分別為12，8，24（百套），兩個(gè)工廠1，B2每日產(chǎn)量、生產(chǎn)成本列于表5.4中。問B1，B2兩廠生產(chǎn)多少天，即滿足市場的需求，又使總成本最低？表5.4工廠型號(hào)B1 B2A1 A2A3 6 2 2 2 4 12日成本(萬元) 2 1.6

7、需求量12 824 日產(chǎn)量 設(shè)x1,x2為工廠B1，B2的生產(chǎn)天數(shù)，根據(jù)題意就是求x1,x2的一組取值，滿足約束條件：表5.4工廠型號(hào)B1 B2A1 A2A3 6 2 2 2 4 12日成本(萬元) 2 1.6 最低需求量12 824 日產(chǎn)量6x1+2x2 122x1+2x2 84x1+12x2 24x10 , x2 0并使總成本S= 2x1+1.6x2最大這個(gè)問題的數(shù)學(xué)模型可表示為: minS= 2x1+1.6x26x1+2x2 122x1+2x2 84x1+12x2 24x10 , x2 0 線性規(guī)劃問題是滿足下述特點(diǎn)的最優(yōu)決策問題：每個(gè)問題的決策方案可用一組變量的取值表示，這組變量稱為決

8、策變量；有一定的約束條件，約束條件是決策變量的線性等式或不等式；有一個(gè)可表示為決策變量的線性函數(shù)的決策目標(biāo)（稱為目標(biāo)函數(shù)），決策目的是使目標(biāo)函數(shù)達(dá)到最大或最小。線性規(guī)劃問題的一般數(shù)學(xué)模型為：n1jjjxcmin(max)Siijban1jjx)b,b(ii或或(i=1,2,m)其中aij, bi,cj (i=1,2,m; j=1,2,n)為已知量，xj(j=1,2,n)為決策變量，S為目標(biāo)函數(shù)。一 線性規(guī)劃問題及其數(shù)學(xué)模型二 圖解法解線性規(guī)劃問題三 線性規(guī)劃問題的標(biāo)準(zhǔn)形式四 線性規(guī)劃問題的單純形解法二 圖解法解線性規(guī)劃問題(一）線性規(guī)劃問題的可行解與最優(yōu)解1 可行解：滿足所有約束條件的決策變量

9、的一組值，稱為線性規(guī)劃問題的一個(gè)可行解。常寫成向量的形式：nxxxX212 可行域所有可行解的集合稱為可行域。3 最優(yōu)解使目標(biāo)函數(shù)取最優(yōu)值的可行解，稱為線性規(guī)劃問題的最優(yōu)解。4 若連接點(diǎn)集 中任意兩點(diǎn)x1,x2的線段S仍在D中，則稱D為凸集。nRD 5 極點(diǎn)若凸集中的點(diǎn)x不能成為D中任何段落的內(nèi)部點(diǎn)，則稱x為D的極點(diǎn)。定理1 線性規(guī)劃問題的可行域?yàn)橥辜?。定? 線性規(guī)劃問題在有最優(yōu)解時(shí)，最優(yōu)解可以在極點(diǎn)上取到。（二）線性規(guī)劃問題的圖解法 現(xiàn)有某一江段，沿江有兩個(gè)工廠，第1個(gè)工廠每日向江中排放污染物為20個(gè)單位，第2個(gè)工廠每日向江中排放污染物為14個(gè)單位.每處理掉一個(gè)單位的污水處理費(fèi)在第一個(gè)工廠

10、為1000元，第二個(gè)工廠為800元。兩個(gè)工廠沿江位置如圖。流經(jīng)第一個(gè)工廠的河流在經(jīng)過工廠以前為未受污染的河流，其江水流量Q1為5m3/s,在第1個(gè)工廠到第2個(gè)工廠之間又有一小支流匯入，其流量Q2為2m3/s,也未受污染。另外，在第1個(gè)工廠排入江中的污染物在未到第2個(gè)工廠以前由于自凈作用而自凈掉20%。按國家城鄉(xiāng)環(huán)保局的規(guī)定，這條江污染物的允許含量為每m3不得超過2個(gè)單位。工廠1工廠2Q1Q2既要滿足江河的防治污染的標(biāo)準(zhǔn)，又要使兩個(gè)工廠因處理污水而花費(fèi)的經(jīng)費(fèi)最少，試問這兩個(gè)工廠需要處理的污水單位是多少？工廠1工廠2Q1Q2解：設(shè)x1和x2分別為第1個(gè)工廠和第2個(gè)工廠的污水處理單位,兩個(gè)工廠所要花

11、費(fèi)的污水處理費(fèi)為1000 x1+800 x2,使其為最小，因此目標(biāo)函數(shù)為： Z=1000 x1+800 x2min工廠排污量（單位）單位污水處理費(fèi)河流來水量m3/s河流允許排放污染物標(biāo)準(zhǔn)最大允許容污量/單位排入處理剩余120 x120-x11000Q1=5252=10214x214-x2800Q1+ Q2=7272=14約束條件分析表（1）對于第1個(gè)工廠來說： 20-x110（2）對于第2個(gè)工廠來說：0.8( 20-x1)+(14-x2) 14 （3）兩個(gè)工廠處理掉的污水量既不能為負(fù)也不能超過它 們的總排放量，即 0 x120 0 x214因此這個(gè)問題的約束條件可歸納為：20-x1100.8(

12、 20-x1)+(14-x2) 140 x1200 x2140.8x1+x21610 x1 20 0 x2 141 求可行解x1x25101520510152000.8x1+x21610 x1 20 0 x2 14ABCD可行域2 尋找最優(yōu)解 在A、B、C、D 4個(gè)極點(diǎn)中選取。邊界點(diǎn) A B C D各點(diǎn)坐標(biāo) (10,8) (20,0) (20,14) (10,14)目標(biāo)函數(shù)值 16400 20000 31200 21200已知目標(biāo)函數(shù)為：1245800 xZx218001000 xxZ800Zk將目標(biāo)函數(shù)方程轉(zhuǎn)換為：1245xkx令則其中-5/4為目標(biāo)函數(shù)的斜率，依此斜率可在圖中畫一組平行線，

13、在這些具有相同斜率的平行線中，居于最低位置的目標(biāo)函數(shù)所切的點(diǎn)即為最優(yōu)解。ABCD可行域x1x25101520510152001245xx一 線性規(guī)劃問題及其數(shù)學(xué)模型二 圖解法解線性規(guī)劃問題三 線性規(guī)劃問題的標(biāo)準(zhǔn)形式四 線性規(guī)劃問題的單純形解法三 線性規(guī)劃問題的標(biāo)準(zhǔn)形式（一）線性規(guī)劃問題的標(biāo)準(zhǔn)形式 為給出線性規(guī)劃問題的一般解法，首先需要把線性規(guī)劃問題多樣形式的數(shù)學(xué)模型統(tǒng)一為標(biāo)準(zhǔn)形式。線性規(guī)劃問題數(shù)學(xué)模型的標(biāo)準(zhǔn)形式為：nnxcxcxcZ2211maxnjjjxcZ1max),2, 1(022112222212111212111njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn即

14、：目標(biāo)函數(shù)約束方程組), 2 , 1(0), 2 , 1, 0(1njxmibbxajnjiijij用矩陣的形式表示為：CXZ max0XbbAX)0(nxxxX21ncccC21mbbbb21mnmmnnaaaaaaaaaA212222111211其中：（二）非標(biāo)準(zhǔn)形化為標(biāo)準(zhǔn)形的方法1 將常數(shù)項(xiàng)都化為非負(fù)數(shù)； 若第i個(gè)約束條件右邊的常數(shù)bi0,則第i個(gè)約束式兩邊乘-1.2 化約束條件為等式若第k個(gè)約束方程為不等式，即 knknkkbxaxaxa)(2211引入變量 , 第K個(gè)方程改寫為：kknnknkkbxxaxaxa)(22110knx則目標(biāo)函數(shù)標(biāo)準(zhǔn)形式為：njnjknjjjjxoxcxc

15、Z11松弛變量3 將目標(biāo)函數(shù)化為求最大值njjjxcZ1minZZnjjjxcZ1max若目標(biāo)函數(shù)是求最小值令則目標(biāo)函數(shù)變?yōu)椋?變成標(biāo)準(zhǔn)形式的線性規(guī)劃問題與原線性規(guī)劃問題有相同的最優(yōu)解（去掉松弛變量的取值）。例：將以下線性規(guī)劃問題轉(zhuǎn)換成標(biāo)準(zhǔn)形式。2132maxxxZ0, 092123212121xxxxxx一 線性規(guī)劃問題及其數(shù)學(xué)模型二 圖解法解線性規(guī)劃問題三 線性規(guī)劃問題的標(biāo)準(zhǔn)形式四 線性規(guī)劃問題的單純形解法四 線性規(guī)劃問題的單純形解法 單純形法是求解線性規(guī)劃問題的一種有效方法，被譽(yù)為20世紀(jì)十大算法之一，是20世紀(jì)創(chuàng)造經(jīng)濟(jì)效益最多的算法。 是美國數(shù)學(xué)家丹捷格（Dantzig)于1947年提

16、出的，單純形法的提出使線性規(guī)劃理論趨于成熟。單純形法的理論依據(jù)： 線性規(guī)劃問題的可行域是n維向量空間R中的多面凸集D，其最優(yōu)值存在必在該凸集D的某極點(diǎn)處達(dá)到。 這個(gè)重要的定理啟發(fā)了Dantzig的單純形法， 即將尋優(yōu)的目標(biāo)集中在D的各個(gè)頂點(diǎn)上。轉(zhuǎn)移條件：轉(zhuǎn)移條件：使使停止準(zhǔn)則：停止準(zhǔn)則：LPLP可行域可行域基本可基本可行解行解單純形法的基本思路：（一）單純形法的基本原理： 對于線性規(guī)劃問題：CXZ max0XbbAX)0(假設(shè)R(A)=m0,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )x 換出變量的確定換出變量的確定 最小比值原則最小比

17、值原則 如果確定為換入變量，方程如果確定為換入變量，方程其中為中與對應(yīng)的系數(shù)列向量。其中為中與對應(yīng)的系數(shù)列向量?，F(xiàn)在需在現(xiàn)在需在 中確定一個(gè)基變量為換中確定一個(gè)基變量為換出變量。出變量。 B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B b)min/(B P) 0,1im =(B P)(B P)ll m+kx-1-1-1-1BNBm+km+kX=B b-B NXX=B b-B Pxm+kPm+kxm+kx則選取對應(yīng)的基變量則選取對應(yīng)的基變量 為換出變量。為換出變量。 xlBX當(dāng)由零慢慢增加到某個(gè)值時(shí)，當(dāng)由零慢慢增加到某個(gè)值時(shí)， 的非負(fù)性可能被打破。

18、的非負(fù)性可能被打破。為保持解的可行性，可以按最小比值原則確定換出變量：為保持解的可行性，可以按最小比值原則確定換出變量：若1 化為標(biāo)準(zhǔn)形式：2132maxxxZ0, 092123212121xxxxxx43210032maxxxxxZ0, 09212321421321xxxxxxxx2 約束方程系數(shù)陣432110120131PPPPA則B=P3,P4是線性規(guī)劃問題的一個(gè)基；P3,P4是基向量，P1,P2是非基向量x3,x4是基變量，x1,x2是非基變量代入目標(biāo)函數(shù)： Z=2x1+3x2令非基變量x1,x2=0Z=0 ,x3=12,x4=9基可行解X0=0 0 12 9T43210032maxx

19、xxxZ0, 09212321421321xxxxxxxx檢驗(yàn)系數(shù)=CN-CBB-1N=CN=2 3檢驗(yàn)系數(shù)均0,所以Z=0不是最優(yōu)解。目標(biāo)函數(shù)用非基變量表示時(shí)，非基變量的系數(shù)稱為檢驗(yàn)系數(shù)?；兞坑梅腔兞勘硎荆?x3=12-x1-3x2 x4=9-2x1-x23 換入、換出變量換入變量（最大增加原則）因?yàn)閤2的系數(shù)大，所以x2為換入基變量。換出變量（最小比值原則為保持基變量的非負(fù)性）換出。3419312minx43210032maxxxxxZ0, 09212321421321xxxxxxxx4基變量用非基變量表示：3143123135531314xxxxxx代入目標(biāo)函數(shù)： Z=12+x1x3

20、令非基變量x1,x3=0Z=12 ,x2=4,x4=5基可行解X1=0 4 0 5Tx1檢驗(yàn)系數(shù)1 =10所以Z=12不是最優(yōu)解。43210032maxxxxxZ0, 09212321421321xxxxxxxx5 換入、換出變量換入變量（最大增加原則）x1為換入基變量。換出變量(最小比值原則）換出。43531354minx6 基變量用非基變量表示：4324315152353513xxxxxx令非基變量x3,x4=0Z=15 ,x1=3,x2=3基可行解X2=3 3 0 0Tx3, x4檢驗(yàn)系數(shù)3 , 4 均0中，所對應(yīng)的Xk系數(shù)列向量0,則此問題無解，停止計(jì)算。否則轉(zhuǎn)入下一步； 4 選入、選

21、出變量；用一個(gè)原非基變量替換一個(gè)原基變量成為一個(gè)新的基變量，然后求出新的基可行解； 選入變量（最大增加原則最大限度地接近最優(yōu)目標(biāo)）檢驗(yàn)系數(shù)較大的值所在的列的非基變量為換入變量。換出變量（最小比值原則為了確保XB0)求解向量中基變量的取值與換入變量的系數(shù)列向量中對應(yīng)的正分量之比，取最小比值所對應(yīng)的基變量為換出變量。X X3 3為為換入變量，換入變量，X X4 4為換出變量為換出變量 1 2 2 1 08x4-1 3 0 4 0 01-Z 3 4 1 0 17x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C8/27/1123451234123512345maxZ=5x2x3x

22、xxx2x2xx83x4xxx7 x ,x ,x ,x ,x0基本可行解基本可行解 ，Z= 15Z= 15，X = (0,0,4, 0, 3)T1/2 1 1 1/2 04x33 1 -4 0 -2 0-15-Z5/2 3 0 -1/2 13x51 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C5 主元素轉(zhuǎn)換得到新的單純形表主元素轉(zhuǎn)換就是用初等行變換的方法將主元素變?yōu)?，主元素所在列的其他元素變?yōu)?（包括檢驗(yàn)系數(shù)），即把主元素所在列轉(zhuǎn)化為單位列向量。 1 2 2 1 08x4-1 3 0 4 0 01-Z 3 4 1 0 17x51 x1 x2 x3 x4 x5bXBCB 5

23、2 3 -1 1C8/27/1最優(yōu)解最優(yōu)解 最優(yōu)值最優(yōu)值 617X,0,0,055T換入變量，換出變量，換入變量，換出變量，/ /為主元進(jìn)行旋轉(zhuǎn)變換為主元進(jìn)行旋轉(zhuǎn)變換1x5xNNB=C-C N081Z54/1/21/2 1 1 1/2 04x33 1 -4 0 -2 0-15-Z3/5/25/2 3 0 -1/2 13x51x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C 0 2/5 1 3/5 -1/517/5x33 0 -26/5 0 -9/5 -2/5-81/5-Z 1 6/5 0 -1/5 2/56/5x15 x1 x2 x3 x4 x5bXBCB 5 2 3 -1 1C6 回到第2步 定理定理3 3：無最優(yōu)解判別定理：無最優(yōu)解判別定理 若若 是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù)是一個(gè)基本可行解，有一個(gè)檢驗(yàn)數(shù) ，但是，則該線性規(guī)劃問題無最，但是，則該線性規(guī)劃問題無最優(yōu)解。優(yōu)解。1B bX=0-1m+kB P0m+k0-1-1-1-1BNB