線性規(guī)劃linprog_第1頁
線性規(guī)劃linprog_第2頁
線性規(guī)劃linprog_第3頁
線性規(guī)劃linprog_第4頁
線性規(guī)劃linprog_第5頁
已閱讀5頁,還剩8頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、線性規(guī)劃是一種優(yōu)化方法,Matlab優(yōu)化工具箱中有現(xiàn)成函數(shù)linprog對如下式描述的LP問題求解:%minfx%s.t.(約束條件):Ax<=b%(等式約束條件):Aeqx=beq%lb<=x<=ublinprog函數(shù)的調(diào)用格式如下:x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Aeq,beq,lb,ub)x=linprog(f,A,b,Aeq,beq,lb,ub,x0)x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)x,fval=linprog(')x,fval,e

2、xitflag=linprog(')x,fval,exitflag,output=linprog()x,fval,exitflag,output,lambda=linprog()其中:x=linprog(f,A,b)返回值x為最優(yōu)解向量。x=linprog(f,A,b,Aeq,beq)作有等式約束的問題。若沒有不等式約束,則令A(yù)=、b=x=linprog(f,A,b,Aeq,beq,lb,ub,x0,options)中l(wèi)b,ub為變量x的下界和上界,x0為初值點,options為指定優(yōu)化參數(shù)進行最小化。Options的參數(shù)描述:Display顯示水平。選擇off不顯示輸出;選擇Ite顯

3、示每一步迭代過程的輸出;選擇final顯示最終結(jié)果。MaxFunEvals函數(shù)評價的最大允許次數(shù)Maxiter最大允許迭代次數(shù)TolXx處的終止容限x,fval=linprog(左端)fval返回解x處的目標函數(shù)值。x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,x0)的輸出部分:exitflag描述函數(shù)計算的退出條件:若為正值,表示目標函數(shù)收斂于解x處;若為負值,表示目標函數(shù)不收斂;若為零值,表示已經(jīng)達到函數(shù)評價或迭代的最大次數(shù)。output返回優(yōu)化信息:output.iterations表示迭代次數(shù);output.algo

4、rithm表示所采用的算晨;outprt.funcCount表示函數(shù)評價次數(shù)。lambda返回x處的拉格朗日乘子。它有以下屬性:lambda.lower-lambda的下界;lambda.upper-lambda的上界;lambda.ineqlin-lambda的線性不等式;lambda.eqlin-lambda的線性等式。第一章線性規(guī)劃§1線性規(guī)劃在人們的生產(chǎn)實踐中,經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn),以取得最大經(jīng)濟效益的問題。此類問題構(gòu)成了運籌學(xué)的一個重要分支一數(shù)學(xué)規(guī)劃,而線性規(guī)劃(LinearProgramming簡記LP)則是數(shù)學(xué)規(guī)劃的一個重要分支。自從1947年G.B.D

5、antzig提出求解線性規(guī)劃的單純形方法以來,線性規(guī)劃在理論上趨向成熟,在實用中日益廣泛與深入。特別是在計算機能處理成千上萬個約束條件和決策變量的線性規(guī)劃問題之后,線性規(guī)劃的適用領(lǐng)域更為廣泛了,已成為現(xiàn)代管理中經(jīng)常采用的基本方法之一。1.1線性規(guī)劃的實例與定義例1某機床廠生產(chǎn)甲、乙兩種機床,每臺銷售后的利潤分別為4000元與3000元。生產(chǎn)甲機床需用A、B機器加工,加工時間分別為每臺2小時和1小時;生產(chǎn)乙機床需用A、B、C三種機器加工,加工時間為每臺各一小時。若每天可用于加工的機器時數(shù)分另為A機器10小時、B機器8小時和C機器7小時,問該廠應(yīng)生產(chǎn)甲、乙機床各幾臺,才能使總利潤最大?上述問題的數(shù)

6、學(xué)模型:設(shè)該廠生產(chǎn)Xi臺甲機床和X2乙機床時總利潤最大,則Xi,X2應(yīng)滿足(目標函數(shù))maxz=4x13x2(1)s.t.(約束條件)(2)2x1+x2<10x1x2-8X2三7X1,x20這里變量Xi,X2稱之為決策變量,(1)式被稱為問題的目標函數(shù),(2)中的幾個不等式是問題的約束條件,記為s.t.(即subjectto)o上述即為一規(guī)劃問題數(shù)學(xué)模型的三個要素。由于上面的目標函數(shù)及約束條件均為線性函數(shù),故被稱為線性規(guī)劃問題??傊?,線性規(guī)劃問題是在一組線性約束條件的限制下,求一線性目標函數(shù)最大或最小的問題。在解決實際問題時,把問題歸結(jié)成一個線性規(guī)劃數(shù)學(xué)模型是很重要的一步,但往往也是困難

7、的一步,模型建立得是否恰當,直接影響到求解。而選取適當?shù)臎Q策變量,是我們建立有效模型的關(guān)鍵之一。1.2 線性規(guī)劃的Matlab標準形式線性規(guī)劃的目標函數(shù)可以是求最大值,也可以是求最小值,約束條件的不等號可以是小于號也可以是大于號。為了避免這種形式多樣性帶來的不便,Matlab中規(guī)定線性規(guī)劃的標準形式為mincTxsuchthatAx-bx其中c和x為n維列向量,b為m維列向量,A為mn矩陣。例如線性規(guī)劃maxcTxsuchthatAx-bx的Matlab標準型為min-cTxsuchthat-Ax-bx1.3 線性規(guī)劃問題的解的概念一般線性規(guī)劃問題的標準型為nminz="CjXj(3

8、)jins.t.”aijXj<bii=1,2,m(4)j1可行解滿足約束條件(4)的解x=(x1,x2"xn),稱為線性規(guī)劃問題的可行解,而使目標函數(shù)(3)達到最小值的可行解叫最優(yōu)解??尚杏蛩锌尚薪鈽?gòu)成的集合稱為問題的可行域,記為R。1.4線性規(guī)劃的圖解法圖解法簡單直觀,有助于了解線性規(guī)劃問題求解的基本原理。我們先應(yīng)用圖解法來求解例1。如上圖所示,陰影區(qū)域即為LP問題的可行域Ro對于每一固定的值Z,使目標函數(shù)值等于Z的點構(gòu)成的直線稱為目標函數(shù)等位線,當Z變動時,我們得到一族平行直線。讓等位線沿目標函數(shù)值減小的方向移動,直到等位線與可行域有交點的最后位置,此時的交點(一個或多個

9、)即為LP的最優(yōu)解。對于例1,顯然等位線越趨于右上方,其上的點具有越大的目標函數(shù)值。不難看出,本例的最優(yōu)解為x*=(2,6)T,最優(yōu)目標值z*=26。從上面的圖解過程可以看出并不難證明以下斷言:(1)可行域R可能會出現(xiàn)多種情況。R可能是空集也可能是非空集合,當R非空時,它必定是若干個半平面的交集(除非遇到空間維數(shù)的退化)。R既可能是有界區(qū)域,也可能是無界區(qū)域。(2)在R非空時,線性規(guī)劃既可以存在有限最優(yōu)解,也可以不存在有限最優(yōu)解(其目標函數(shù)值無界)。(3)R非空且LP有有限最優(yōu)解時,最優(yōu)解可以唯一或有無窮多個。(4)若線性規(guī)劃存在有限最優(yōu)解,則必可找到具有最優(yōu)目標函數(shù)值的可行域R的“頂點”。上

10、述論斷可以推廣到一般的線性規(guī)劃問題,區(qū)別只在于空間的維數(shù)。在一般的n維n空間中,滿足一線性等式za4i=b的點集被稱為一個超平面,而滿足一線性不等式1 1nn£aixi<b(或£aixi>b)的點集被稱為一個半空間(其中(a1,an)為一n維行i1i1向量,b為一實數(shù))。有限個半空間的交集被稱為多胞形,有界的多胞形又被稱為多面體。易見,線性規(guī)劃的可行域必為多胞形(為統(tǒng)一起見,空集中也被視為多胞形)。在一般n維空間中,要直接得出多胞形“頂點”概念還有一些困難。二維空間中的頂點可以看成為邊界直線的交點,但這一幾何概念白推廣在一般n維空間中的幾何意義并不十分直觀。為此

11、,我們將采用另一途徑來定義它。定義1稱n維空間中白區(qū)域R為一凸集,若Vx1,x2wR及V兒w(0,1),有九x1+(1九)x2運R。定義2設(shè)R為n維空間中的一個凸集,R中的點x被稱為R的一個極點,若不存在x1、x2wR及7uW(0,i),使得x=>.x1+(1-?0x2o定義1說明凸集中任意兩點的連線必在此凸集中;而定義2說明,若x是凸集R的一個極點,則x不能位于R中任意兩點的連線上。不難證明,多胞形必為凸集。同樣也不難證明,二維空間中可行域R的頂點均為R的極點(R也沒有其它的極點)。1.5 求解線性規(guī)劃的Matlab解法單純形法是求解線性規(guī)劃問題的最常用、最有效的算法之一。單純形法是首

12、先由GeorgeDantzig于1947年提出的,近60年來,雖有許多變形體已被開發(fā),但卻保持著同樣的基本觀念。由于有如下結(jié)論:若線性規(guī)劃問題有有限最優(yōu)解,則一定有某個最優(yōu)解是可行區(qū)域的一個極點?;诖?,單純形法的基本思路是:先找出可行域的一個極點,據(jù)一定規(guī)則判斷其是否最優(yōu);若否,則轉(zhuǎn)換到與之相鄰的另一極點,并使目標函數(shù)值更優(yōu);如此下去,直到找到某一最優(yōu)解為止。這里我們不再詳細介紹單純形法,有興趣的讀者可以參看其它線性規(guī)劃書籍。下面我們介紹線性規(guī)劃的Matlab解法。Matlab5.3中線性規(guī)劃的標準型為mincTxsuchthatAx工bx基本函數(shù)形式為linprog(c,A,b),它的返回

13、值是向量x的值。還有其它的一些函數(shù)調(diào)用形式(在Matlab指令窗運行helplinprog可以看到所有的函數(shù)調(diào)用形式),如:x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)這里fval返向目標函秘的值,Aeq和beq對應(yīng)等式約束Aeq*x=beq,LB和UB分別是變量x的下界和上界,x0是x的初始值,OPTIONS是控制參數(shù)。例2求解下列線性規(guī)劃問題ma»=2x13x2-5x3x1+x2+x3=72xi-5x2x3-10x1,x2,x3-0解(i)編寫M文件c=2;3;-5;a=-2,5,-1;b=-10;aeq=1,1,1;beq=7;x

14、=linprog(-c,a,b,aeq,beq,zeros(3,1)value=c'*x(ii)將M文件存盤,并命名為example1.m。(iii)在Matlab指令窗運行example1即可得所求結(jié)果。例3求解線性規(guī)劃問題minz=2x13x2x3x14x22x3.83x12x2_6Xi,X2,X3_0解編寫Matlab程序如下:c=2;3;1;a=1,4,2;3,2,0;b=8;6;x,y=linprog(c,-a,-b,zeros(3,1)1.6 可以轉(zhuǎn)化為線性規(guī)劃的問題很多看起來不是線性規(guī)劃的問題也可以通過變換變成線性規(guī)劃問題來解決。如:例4問題為min|X2|Xn|5. t

15、.AxMb其中x=x1xnT,A和b為相應(yīng)維數(shù)的矩陣和向量。要把上面的問題變換成線性規(guī)劃問題,只要注意到事實:對任意的xi,存在Ui,ViA0滿足Xi=Ui-Vi,|Xi|=Ui+Vi事實上,我們只要取Ui=xi.|xi|,Vi=區(qū)也就可以滿足上面的條件。22這樣,記U=U1UnT,V=V1VnT,從而我們可以把上面的問題變成nmin二(uivi)1 =1A(u-v)Wb5, t.6, v之0§2運輸問題(產(chǎn)銷平衡)例5某商品有m個產(chǎn)地、n個銷地,各產(chǎn)地的產(chǎn)量分別為a1,,am,各銷地的需求量分別為匕,,bn。若該商品由i產(chǎn)地運到j(luò)銷地的單位運價為,問應(yīng)該如何調(diào)運才能使總運費最???解

16、:引入變量xij,其取值為由i產(chǎn)地運往j銷地的該商品數(shù)量,數(shù)學(xué)模型為mnmin二:二ex。iWjW-nXjXj=a,i=1,,mj4ms.t.<£Xj=bj,j=1,2,ni4Xj之0顯然是一個線性規(guī)劃問題,當然可以用單純形法求解。對產(chǎn)銷平衡的運輸問題,由于有以下關(guān)系式存在:n工Xijnmmm二E2Xj|=EaiJj工y)id:習(xí)慣上稱為表上作業(yè)法(由其約束條件的系數(shù)矩陣相當特殊,可用比較簡單的計算方法,康托洛維奇和希奇柯克兩人獨立地提出,簡稱康一希表上作業(yè)法)表上作業(yè)法是單純形法在求解運輸問題時的一種簡化方法,其求解工作在運輸表上進行逐步迭代如下:先按某一規(guī)則找出一個初始解(

17、初始調(diào)運方案);再對現(xiàn)行解作最優(yōu)性判斷;若這個解不是最優(yōu)的,就在運輸表上對它進行調(diào)整改進,得一新解;再判斷,再改進,直到得到最優(yōu)解。§ 3 指派問題(又稱分配問題AssignmentProblem)3.1 指派問題的數(shù)學(xué)模型例6擬分配n人去干n項工作,每人干且僅干一項工作,若分配第i人去干第j項工作,需花費cj單位時間,問應(yīng)如何分配工作才能使工人花費的總時間最少?容易看出,要給出一個指派問題的實例,只需給出矩陣C=(cj),C被稱為指派問題的系數(shù)矩陣。引入變量Xj,若分配i干j工作,則取xj=1,否則取Xj=0。上述指派問題的數(shù)學(xué)模型為nnmin二二cjXji=1j=1/n工Xij=

18、1,i=1,2,,njTns.t.JZXij=1,j=1,2,n(5)iTXij=0或1,i,j=1,2,n,J(5)的可行解既可以用一個矩陣(稱為解矩陣)表示,其每行每列均有且只有一個元素為1,其余元素均為0,也可以用1,,n中的一個置換表示。(5)的變量只能取0或1,從而是一個0-1規(guī)劃問題。一般的0-1規(guī)劃問題求解極為困難。但指派問題并不難解,其約束方程組的系數(shù)矩陣十分特殊(被稱為全單位模矩陣,其各階非零子式均為±1),其非負可行解的分量只能取0或1,故約束xj=01可改寫為xj之0而不改變其解。此時,指派問題被轉(zhuǎn)化為一個特殊的運輸問題,其中m=n,a=bj=1。3.2求解指派

19、問題的匈牙利算法由于指派問題的特殊性,又存在著由匈牙利數(shù)學(xué)家法一匈牙利算法。算法主要依據(jù)以下事實:如果系數(shù)矩陣D.Konig提出的更為簡便的解C=(c/一行(或一列)中每一元素都加上或減去同一個數(shù),得到一個新矩陣B=(bj),則以C或B為系數(shù)矩陣的指派問題具有相同的最優(yōu)指派。利用上述性質(zhì),可將原系數(shù)陣C變換為含零元素較多的新系數(shù)陣B,而最優(yōu)解不變。若能在B中找出n個位于不同行不同列的零元素,令解矩陣中相應(yīng)位置的元素取值為1,其它元素取值為零,則所得該解是以B為系數(shù)陣的指派問題的最優(yōu)解,從而也是原問題的最優(yōu)解。由C到B的轉(zhuǎn)換可通過先讓矩陣C的每行元素均減去其所在行的最小元素得矩陣D,D的每列元素

20、再減去其所在列的最小元素得以實現(xiàn)。下面通過一例子來說明該算法。例7求解指派問題,其系數(shù)矩陣為1615192217211918C=24221817-17192216_解將第一行元素減去此行中的最小元素元素減去17,最后一行的元素減去16,得15,同樣,第二行元素減去17,第三行一107I0442513671100再將第3列元素各減去1,得一1*0341*50357【10*0以B2為系數(shù)矩陣的指派問題有最優(yōu)指派彳234、途134,由等價性,它也是例7的最優(yōu)指派。有時問題會稍復(fù)雜一些。例8求解系數(shù)矩陣C的指派問題12789C=|717151441079796661214126610106解:先作等價

21、變換如下-71279791-50*202-6896662300*0-7717121412T0*10575V-615146610980*04-4:4107106-1106362_V7容易看出,從變換后的矩陣中只能選出四個位于不同行不同列的零元素,最優(yōu)指派還無法看出。此時等價變換還可進行下去。步驟如下:(1)對未選出0元素的行打7,(2)對v行中0元素所在列打7;(3)對V列中選中的0元素所在行打M;重復(fù)(2)、(3)直到無法再打爐為止。可以證明,若用直線劃沒有打的行與打v的列,就得到了能夠覆蓋住矩陣中所有零元素的最少條數(shù)的直線集合,找出未覆蓋的元素中的最小者,令¥行元素減去此數(shù),爐列元

22、素加上此數(shù),則原先選中的0元素不變,而未覆蓋元素中至少有一個已轉(zhuǎn)變?yōu)?,且新矩陣的指派問題與原問題也等價。上述過程可反復(fù)采用,直到能選取出足夠的0元素為止。例如,對例5變換后的矩陣再變換,第三行、第五行元素減去2,第一列元素加上2,得70202430000835311800404140_現(xiàn)在已可看出,最優(yōu)指派為12345、上4135§4對偶理論與靈敏度分析4.1 原始問題和對偶問題考慮下列一對線性規(guī)劃模型:(P)maxcTxs.t.Axqb,x-0(D)j行的minbTys.t.ATy_c,y_0稱(P)為原始問題,(D)為它的對偶問題。不太嚴謹?shù)卣f,對偶問題可被看作是原始問題的“行

23、列轉(zhuǎn)置”:(1) 原始問題約束條件中的第j列系數(shù)與其對偶問題約束條件中的第系數(shù)相同;(2) 原始目標函數(shù)的系數(shù)行與其對偶問題右側(cè)的常數(shù)列相同;(3) 原始問題右側(cè)的常數(shù)列與其對偶目標函數(shù)的系數(shù)行相同;(4) 在這一對問題中,除非負約束外的約束不等式方向和優(yōu)化方向相反。考慮線性規(guī)劃:mincTxs.t.Ax=b,x_0把其中的等式約束變成不等式約束,可得tAbmincxs.t.xI,x_0AIL-b它的對偶問題是maxbTs.t.AT-人口|"1代>2>2.其中y1和y2分別表示對應(yīng)于約束Axib和一Ax之-b的對偶變量組。令y=y1-y2,則上式又可寫成maxbTys.t

24、.ATy-c原問題和對偶的對偶問題約束之間的關(guān)系:minmax>0仔變量W0行約束之無限制=一一°行約束變量(W0=無限制4.2 對偶問題的基本性質(zhì)1o對稱性:對偶問題的對偶是原問題。y是對偶問題的可行解。則恒有:2o弱對偶性:若x是原問題的可行解,TT-cx工by。3o無界性:若原問題(對偶問題)為無界解,則其對偶問題(原問題)無可行解。4o可行解是最優(yōu)解時的性質(zhì):設(shè)£是原問題的可行解,?是對偶問題的可行解,當cT?=bT?時,x,?是最優(yōu)解。5o對偶定理:若原問題有有限最優(yōu)解,那么對偶問題也有最優(yōu)解;且目標函數(shù)值相同。6o互補松弛性:若x,y?分別是原問題和對偶問

25、題的最優(yōu)解,則?T(A2-b)=0,x5T(AT?-c)=0由上述性質(zhì)可知,對任一LP問題(P),若它的對偶問題(D)可能的話,我們總可以、一.,.一*通過求解(D)來討論原問題(P):若(D)無界,則(P)無可行解;若(D)有有限最優(yōu)解w,取優(yōu)值wb,則利用互補松弛性可求得(P)的所有取優(yōu)解,且(P)的取優(yōu)值為wb。例如對只有兩個彳T約束的LP,其對偶問題只有兩個變量,總可用圖解法來求解。例9已知線性規(guī)劃問題min=2x13x25x32x43x5s.t.x.|x22x3x43x5-42x1-x23x3x4x5_3x-0,j=1,2,54*3*已知其對偶問題的最優(yōu)解為y=一,丫2=一,最優(yōu)值為

26、z=5。試用對偶理論找出原55問題的最優(yōu)解。解先寫出它的對偶問題maxz=4yl3y2s.t.必+2y2M2y-y2M32y1+3y3<5y1+y2M23y1+y293y1,y2-0*將y1,y2的值代入約束條件,得,為嚴格不等式;設(shè)原問題的最優(yōu)解為*x=(x1,,x5),由互補松弛性得x2=x3=x4=0。因y1,y2>0;原問題的兩個約束條件應(yīng)取等式,故有*.3x1x5=42x1x5=3求解后得到Xi=1,x5=1;故原問題的最優(yōu)解為_*_,.*X=10001';最優(yōu)值為w=5。4.3 靈敏度分析靈敏度分析是指對系統(tǒng)或周圍事物因周圍條件變化顯示出來的敏感程度的分析。在以前討論線性規(guī)劃問題時,假定aj,b,6都是常數(shù)。但實際上這些系數(shù)往往是估計值和預(yù)測值。如市場條件一變,q值就會變化;aj往往是因工藝條件的改變而改變;。是根據(jù)資源投入后的經(jīng)濟效果決定的一種決策選擇。因此提出這樣兩個問題:當這些參數(shù)有一個或幾個發(fā)生變化時,已求得的線性規(guī)劃問題的最優(yōu)解會有什么變化;或者這些參數(shù)在什么范圍內(nèi)變化時,線性規(guī)劃問題的最優(yōu)解不變。這里我們就不討論了。4.4 參數(shù)線性規(guī)劃參數(shù)線性規(guī)劃是研究a。,bi,Cj這些參數(shù)中某一參數(shù)連續(xù)變化時,使最優(yōu)解發(fā)生變化的各臨

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論