第7章 線性規(guī)劃

1、第七講 線性規(guī)劃Linear Programming 內(nèi)容提要 線性規(guī)劃定義線性規(guī)劃標準型與松馳型單純形算法重點與難點 重點:線性規(guī)劃定義線性規(guī)劃標準型與松馳型單純形算法難點:單純形算法的正確性證明學習目的與要求 理解線性規(guī)劃的概念.通過學習單純形算法,掌握線性規(guī)劃問題的求解及單純形算法正確性的證明方法.總統(tǒng)大選問題總統(tǒng)大選問題 一個政治家擁有市區(qū)、市郊及農(nóng)村三個選票區(qū)。選民人數(shù)分別是100000, 200000,及 50000. 為了在各區(qū)中贏得更多的選票，在不同的區(qū)域中宣傳主題的效果是不同的。主要的宣傳主題有：修路、控制槍械、農(nóng)業(yè)津貼、汽油稅賦?？梢愿鶕?jù)調(diào)研知道對于每個主題每花費1000元

2、廣告費所得到或失去的選票數(shù)。 上表中單位為千張。上表中單位為千張。 要在市區(qū)、市郊及農(nóng)村贏得的選票數(shù)分別要在市區(qū)、市郊及農(nóng)村贏得的選票數(shù)分別至少是至少是5000050000、100000100000、2500025000，問至少需，問至少需要多少廣告費。要多少廣告費。該問題的數(shù)學描述如下：該問題的數(shù)學描述如下：X1 ： 修路所花費的廣告費（千元）；X2 ：槍械控制所花費的廣告費（千元）； X3 ：農(nóng)業(yè)津貼所花費的廣告費（千元）； X4 ：汽油稅賦所花費的廣告費（千元）；相應(yīng)的約束如下： -2x1+8x2+0 x3+10 x450 (1) 5x1 +2x2+0 x3+0 x4100 (2) 3x

3、1 -5x2+10 x3-2x425 (3) 滿足不等式(1)-(3)的x1, x2,x3, x4 取值都是一個可行策略。求廣告費最少的可行策略。即最小化 x1+x2+x3+x4x10, x20,x30, x4 0.相應(yīng)的線性規(guī)劃：Minimize x1+x2+x3+x4 (4) subject to -2x1+8x2+0 x3+10 x450 (5) 5x1 +2x2+0 x3+0 x4100 (6) 3x1 -5x2+10 x3-2x425 (7) x1, x2,x3, x4 0. (8)規(guī)劃問題是一類最優(yōu)化問題，可以如下描述：在給定的一組資源約束下，最大化或最小化目標函數(shù)。線性規(guī)劃問題線

4、性規(guī)劃問題: : 目標函數(shù)為線性函數(shù)，資源約束是一組等式或不等式。一般的線性規(guī)劃問題 在一般的線性規(guī)劃問題中, 我們希望對在一組線性不等式約束的前提下對一個線性函數(shù)進行優(yōu)化（最大/最?。?。f(x1,x2,xn)=a1x1+ a2x2+ anxn =njjjxa1線性等式: f(x1,x2,xn)=b線性不等式: f(x1,x2,xn) b 或 f(x1,x2,xn) bb 是一個實數(shù).：在線性規(guī)劃問題中，不允許出現(xiàn)嚴格不等式約束.一般來說，線性規(guī)劃是對某個線性函數(shù)最小化或最大化使得它滿足一組有限的線性約束。 最小化線性規(guī)劃 最大化線性規(guī)劃下面我們將討論線性規(guī)劃的求解. 雖然已有若干的多項式時間

5、算法求解線性規(guī)劃問題，在本章中我們不討論它們，而是討論單純形算法。單純形算法是最早的用于求解線性規(guī)劃問題的算法。單純形算法的最壞時間復雜性不是多項式時間而是指數(shù)時間。但它在實際應(yīng)用中卻很有效，因此被廣泛使用。我們用兩種形式來表示線性規(guī)劃：標準型和松馳型。一個線性規(guī)劃的標準型是最大化線性目標函數(shù)使得它滿足一組線性不等式約束。而松馳型是最大化線性目標函數(shù)使得它滿足一組等式約束。我們常用標準型來表示線性規(guī)劃, 但是當我們描述用單純型算法來求解線性規(guī)劃時，我們采用松馳型來表示線性規(guī)劃。 從現(xiàn)在起，我們主要關(guān)注最大化n個決策變量的線性目標函數(shù)使得它滿足m個線性不等式。21xx 0 ,22510 2 8

6、421212121xxxxxxxxMaximize Subject to (9) (10)(11)(12)(13)我們稱滿足約束滿足約束(9-13)(9-13)的的x x1 1 和和 x x2 2 為線性規(guī)為線性規(guī)劃的劃的可行解可行解。如果我們將約束（913）在笛卡兒直角坐標系中畫出來,我們將會看到可行解的集合（圖中陰影部分）形成二維空間中的一個凸區(qū)域。我們稱這個凸區(qū)域為 可行可行區(qū)域區(qū)域. 而我們要最大化的函數(shù)就稱為目目標函數(shù)標函數(shù). . 我們可以計算目標函數(shù)x1+x2 在可行區(qū)域中每一點的取值。我們稱目標函數(shù)在某點處的取值為. 我們將確定一個具有最大目標值的點即最優(yōu)解?？尚袇^(qū)域中包含無數(shù)多

7、個點，我們要找出一個有效的方法用以尋找一個具有最大目標值尋找一個具有最大目標值的點的點。而不用遍歷可行域中的每個點。如果我們有n 個變量, 則每個約束決定了n維空間中的一個半空間。由這些半空間所構(gòu)成的可行區(qū)域稱為一個單純形一個單純形。目標函數(shù)就是一個超平面，由于凸特性凸特性，最優(yōu)解最優(yōu)解就出現(xiàn)在單純形的某個頂點頂點上。單純形算法的輸入是一個線性規(guī)劃，其輸出是該線性規(guī)劃的最優(yōu)解最優(yōu)解。它從單純形上的某個頂點出以，并進行一系列的迭代。在每次迭代中，它沿著單純形的一條邊從當前頂點移到一個相鄰頂點并保證該相鄰頂點的目標函數(shù)值不小于當前頂點的目標函數(shù)值。(通常比當前頂點的目標函數(shù)值要大)。當?shù)竭_一個局部

8、最大頂點（其所有相鄰頂點有更小的目標值）時單純形算法終止。因為可行區(qū)域是凸區(qū)域，而目標函數(shù)是線因為可行區(qū)域是凸區(qū)域，而目標函數(shù)是線性函數(shù)，性函數(shù)，因此這個局部最優(yōu)解實際上就是全局最優(yōu)解全局最優(yōu)解。標準型在標準型中，給定n個實數(shù)。 m 個實數(shù)和mn個實數(shù)i=1,2,m， j=1,2,n. 我們希望尋找n個實數(shù)滿足:nccc,21mbbb,21ijanxxx,21 njjjxcimize1v maxn.,1,2,jfor 0 x m,1,2,ifor jn1j ijijbxasubject to 標準型Maximize v+cTxSubject to Axb x0A=(aij) mn 矩陣 b=(

9、bi) m-維向量c=(cj), x=(xj) n-維向量v是一個實數(shù)。 把線性規(guī)劃化成標準型可以將任給定的線性規(guī)劃轉(zhuǎn)化為標準型。1.最小化目標函數(shù);2.有的變量沒有約束;3.有等式約束;4.不等式約束中不等號為. 的如果L的每個可行解x有目標值z, 必有L的可行解x”也有目標值z,反之亦然。一個最小化線性規(guī)劃L和一個最大化線性規(guī)劃 等價如果對于L的每個可行解 有目標值z, 必有 對應(yīng)的可行解 有目標值z，反之亦然。 x L Lx線性規(guī)劃轉(zhuǎn)化為松馳型為了用單純形算法有效地求解線性規(guī)劃, 我們把線性規(guī)劃表示為有的約束是等式約束。更細致地說，我們將把它轉(zhuǎn)化為這樣一種形式，在這種形式中，非負約束是唯

10、一的不等式約束，其余約束是等式約束。injjijbxa101sxabsnjjijis-a slack variableinjjijbxa101innjjijiinxxabxxn+i -松馳變量松馳變量舉例 0 , 422 7 7 332 max321321321321321 xxxxxxxxxxxxtosubjectxxximize 0 , 224 7 -7 332 max654321321632153214321 ,xxxxxxxxxxxxxxxxxxtosubjectxxximize標準型松馳型 0 , 224 7 -7 332 max654321321632153214321 ,xxxx

11、xxxxxxxxxxxxxxtosubjectxxximize在松馳型中,等式左邊的變量稱為基變量基變量，右邊的變量稱為非基變量非基變量。在單純形算法運行過程中，基變量和非基變量的集合會發(fā)生變化。我們用N N記非基變量下標的集合，用B B記基變量下標的集合。記基變量下標的集合。 則|N|=n, |B|=m, NB=1,2,n+m. 用(N,B,A,b,c,v), 表示松馳型BNiforxxabxxcvziNjjijiiNjjj 0 28 ,2/3- 1/6- 6/1c c cc ,1848 0 1/2- 1/2 1/3- 2/3 8/3 1/3 1/6- 6/1a a aa a aa a aA

12、3,5,6,N 1,2,4,B have we2218332384366832662865342146454326252316151353465326531653 vandbbbbxxxxxxxxxxxxxxzTT單純型算法幾個實例例例1 1 用單純形算法求解線性規(guī)劃2 , 1, 0 225 102 84 to maximize21212121 ixxxxxxxsubjectxxi相應(yīng)的松馳型為:5 , 4 , 3 , 2 , 1, 0 252 x2-10 x4-8 x to z21521421321ixxxxxxxsubjectxxi令x1=0,x2=0,得X3=8,x4=10,x5=2.(

13、0,0,8,10,2)是超多面體的一個頂點.對應(yīng)的目標值為0.選x1基變量進行PIVOT操作后所得的松馳型為:令x2=0, x3=0得X1=2,x4=6,x5=12.(2,0,0,6,12)是超多面體的一個頂點.對應(yīng)的目標值為2.5 , 4 , 3 , 2 , 1, 0 454321x 2123-6x 41412x to 41542 z32532432132 ixxxxxxxsubjectxxi選x2基變量進行PIVOT操作后所得的松馳型為:令x3=0, x4=0得X1=3,x2=4,x5=9.(3,4,0,0,9)是超多面體的一個頂點.對應(yīng)的目標值為7.5 , 4 , 3 , 2 , 1,

14、0 21239x 32314x 61613x to 65617 z43543243143 ixxxxxxxsubjectxxi選x3基變量進行PIVOT操作后所得的松馳型為:令x4=0, x5=0得x1=2,x2=6,x3=6.(2,6,6,0,0)是超多面體的一個頂點.對應(yīng)的目標值為8.5 , 4 , 3 , 2 , 1, 0 32316x 92956x 91922x to 91978 z54354254154 ixxxxxxxsubjectxxi0 x,x,x 36 2xx4x 245x2x2x 30 3xxx tosubject 2xx3x maximize 32132132132132

15、1 例例2 2 用單純形算法求解線性規(guī)劃. 0),36,24,30, 0 , 0 , 0(0 x,x,x,x,x,x 2xx4x-36x5x2x2x-24x3xxx30 x2xx3x z654321321632153214321 z目標值目標值基本初始可行解基本初始可行解相應(yīng)的松馳型為相應(yīng)的松馳型為: :4254321 3x-x-)4249(-30 33042496323263232146321xxxxxxxxxxxxxx 2423642543214249432427z632563246321632xxxxxxxxxxxxxxx 初始基本可行解為(9,0,0,21,6,0),z=27。選擇 x

16、1168516346984832316581643316118164111z652465236521652xxxxxxxxxxxxxxx 選擇 x3初始基本可行解初始基本可行解(33/4,0,3/2,69/4,0,0), z=111/4.22183323843668326628z53465326531653xxxxxxxxxxxxxx 初始基本可行解為初始基本可行解為( (8,4,0,8,4,0,18,0,018,0,0), z=28), z=28.選擇 x2leelleljelleleeaaaaaeNja b b xelvcbABNPIVOT/1 5/ do 4 eachfor 3/ 2 v

17、ariablebasicnew for equation theof tscoefficien theCompute/ 1),(elieilejieijijeieiiaaaaaaaeNjbabblBi 11 do 10 eachfor 9 do 8 eachfor 7s.constraint remaining the of tscoefficien the Compute /6 elelejejjeeaccaccceNjbcvv 16 do 15 eachfor 14 13function. objective the te /Compu12 ) , ,( return 20 19 18va

18、riables. nonbasic and nonbasic and basic of sets new te /Compu17vcbABNelBBleNN 詳細的推導過程如下：leleNjjejelleeNjjleljleleeleeNjjljlNjjljllxaxabxaxaaabxxaxabxabx 1 lileNjjijilelieeNjjejieijeieileleNjjejeieeNjjijieieeNjjijiNjjijiixaxabxaaxaaababxaxabaxabxaxabxabxlBi )()()( ) ( lleNjjjleleeNjjejejeeleleNjjeje

19、eeNjjjeeeNjjjNjjjxcxcvxacxaccbcvxaxabcxcvxcxcvxcvz )()()( ) ( 引理引理 29.1考慮一次調(diào)用考慮一次調(diào)用PIVOT(N,B,A,b,c,v,l,e)其中其中 ale0 令調(diào)用返回令調(diào)用返回 記調(diào)用后所得的基本解為記調(diào)用后所得的基本解為 . 則則) , ,(vcbABNx-eBfor each i b-abx. ./abx. .Nj for each x. eieiilelej 3201 SIMPLEX(A,b,c)1. (N,B,A,b,c,v) INITIALIZE-SIMPLEX(A,b,c)2. while some inde

20、x 3. do choose an index 4. for each index 5. do if 6. then 7. else 8. choose an index that minimizes 0jc hasNj0ec whichfor NeBi0ieaieiiab /iBli9. if 10. then return “unbounded”11 Else (N,B,A,b,c,v) PIVOT(N,B,A,b,c,v, , )12. For i 1 to n13. Do if 14. Then 15. Else 16. Return lleBi iibx 0ix),(21nxxx 如

21、何確定線性規(guī)劃是否可行?如果線性規(guī)劃可行而基本解不可行怎么辦?如何確定線性規(guī)劃是無界的?如何選擇進入與離開的變量?與單純形算法相關(guān)的問題：與單純形算法相關(guān)的問題：INITIALIZE-SIMPLEX(A,b,c) -初始單純形算法初始單純形算法初始單純形算法的輸入是一個線性規(guī)劃標準型，即一個mn矩陣A=(aij),一個m-維向量b=(bi), 和一個n-維向量c=(cj).如果線性規(guī)劃不可行, 則算法返回“不可行”并停機。否則,它返回一個初始基本解可行的松馳型。,0)v,c,b,A,B,PIVOT(N, -v)c,b,A,B,(N, 7variables. basic m and variab

22、les nonbasic 1n has /L6Lfor form slack resulting the be v)c,b,A,B,(N,let 5x- to function objective the setting and equation each of side hand-left the tox- adding byL form 4)0 ,m,n,1,nn,(1,2, return then 3feasible? solution basic initial /the, 0 2 minimum the ofindex the be let 1),(aux aux 0 0aux lc

23、bAbifblcbASIMPLEXINITIALIZEli infeasible return else 12restored function objective original theand removed x withformslack final thereturn hen t110 x sets solution basic theif 10found is L tosolution optimal an until SIMPLEX of 11-2 line of loop while thete /itera9for L feasiblenow is solution basic

24、 /The800aux aux.則線性規(guī)劃是無界的。則線性規(guī)劃是無界的。返回返回行中行中在第在第如果如果規(guī)劃的可行解。規(guī)劃的可行解。解是線性解是線性行中返回一個解，這個行中返回一個解，這個在第在第則如果則如果的。的。返回一個基本解是可行返回一個基本解是可行行調(diào)用行調(diào)用算法中第算法中第假設(shè)在單純形假設(shè)在單純形給定一個線性規(guī)劃給定一個線性規(guī)劃引理引理 , unbounded 10SIMPLEX 16SIMPLEX SIMPLEX-INITIALIZE c),b,(A,29.2 1 證明：證明： 我們利用下面三個循環(huán)不變性我們利用下面三個循環(huán)不變性:在第在第2行至第行至第11行行while循環(huán)的每次

25、迭代開循環(huán)的每次迭代開始時，松馳型與始時，松馳型與INITIALIZE-SIMPLEX返返回的松馳型等價回的松馳型等價,1.對于對于 iB, bi0, 且且 2.松馳型的基本解是可行的松馳型的基本解是可行的.引理引理 29.3令 I 是下標集. 對每個 iI, 令 和 為實數(shù), 是一個實變量。 是任意實數(shù)，假設(shè) 的任意取值有，i i ix ix.I, and i for eachxxiIiiiIiii0 i 則則引理引理 29.4令 (A,b,c) 線性規(guī)劃標準型. 給定一個基變量的集合B,相應(yīng)的松馳型唯一確定.引理引理 29.529.5則它必陷入死循環(huán)。則它必陷入死循環(huán)。迭代仍不停止迭代仍不

26、停止至多在至多在如果如果 , SIMPLEXmmnC 引理引理 29.629.6如果SIMPLEX中的第3和第8行選擇最小下標變量，則SIMPLEX一定會停止。引理引理 29.729.7假設(shè)INITIALIZE-SIMPLEX 返回一個基本解是可行的松馳型, 則SIMPLEX 要么報告規(guī)劃是無界的, 要么在至多 迭代后返回一個可行解。mmnC 原始線性規(guī)劃原始線性規(guī)劃 njjjxcimize1 maxn.,1,2,jfor 0 x m,1,2,ifor jn1j ijijbxasubject to 對偶線性規(guī)劃對偶線性規(guī)劃 miiiybimize1 minm.,1,2,ifor 0y n,1,2,jfor im1i jiijcyasubject to 引理引理 29.8 29.8 ( (弱線性規(guī)劃對偶性弱線性規(guī)劃對偶性) )令 是原始規(guī)劃的任一可行解， 是對偶規(guī)劃的任一可行解。則 miiinjjjybxc11xy推論推論 29.9 令 是原始規(guī)劃(A,b,c)的任一可行解， 是相應(yīng)對偶規(guī)劃的可行解。如果則 和