線性規(guī)劃linprog

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為初值點(diǎn),options為指定優(yōu)化參數(shù)進(jìn)行最小化。Options的參數(shù)描述：Display顯示水平。選擇off不顯示輸出；選擇Ite顯

3、示每一步迭代過程的輸出；選擇final顯示最終結(jié)果。MaxFunEvals函數(shù)評價的最大允許次數(shù)Maxiter最大允許迭代次數(shù)TolXx處的終止容限x,fval=linprog(左端)fval返回解x處的目標(biāo)函數(shù)值。x,fval,exitflag,output,lambda=linprog(f,A,b,Aeq,beq,lb,ub,x0)的輸出部分：exitflag描述函數(shù)計算的退出條件：若為正值，表示目標(biāo)函數(shù)收斂于解x處；若為負(fù)值，表示目標(biāo)函數(shù)不收斂；若為零值，表示已經(jīng)達(dá)到函數(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)實(shí)踐中，經(jīng)常會遇到如何利用現(xiàn)有資源來安排生產(chǎn)，以取得最大經(jīng)濟(jì)效益的問題。此類問題構(gòu)成了運(yùn)籌學(xué)的一個重要分支一數(shù)學(xué)規(guī)劃，而線性規(guī)劃（LinearProgramming簡記LP）則是數(shù)學(xué)規(guī)劃的一個重要分支。自從1947年G.B.D

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

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

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

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

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

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

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

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

13、值是向量x的值。還有其它的一些函數(shù)調(diào)用形式（在Matlab指令窗運(yùn)行helplinprog可以看到所有的函數(shù)調(diào)用形式），如：x,fval=linprog（c,A,b,Aeq,beq,LB,UB,X0,OPTIONS）這里fval返向目標(biāo)函秘的值，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指令窗運(yùn)行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ī)劃問題，只要注意到事實(shí)：對任意的xi,存在Ui,ViA0滿足Xi=Ui-Vi,|Xi|=Ui+Vi事實(shí)上，我們只要取Ui=xi.|xi|,Vi=區(qū)也就可以滿足上面的條件。22這樣，記U=U1UnT,V=V1VnT,從而我們可以把上面的問題變成nmin二(uivi)1 =1A(u-v)Wb5, t.6, v之0§2運(yùn)輸問題(產(chǎn)銷平衡)例5某商品有m個產(chǎn)地、n個銷地，各產(chǎn)地的產(chǎn)量分別為a1,，am,各銷地的需求量分別為匕,，bn。若該商品由i產(chǎn)地運(yùn)到j(luò)銷地的單位運(yùn)價為，問應(yīng)該如何調(diào)運(yùn)才能使總運(yùn)費(fèi)最?。拷?/p>

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

17、初始調(diào)運(yùn)方案）；再對現(xiàn)行解作最優(yōu)性判斷；若這個解不是最優(yōu)的，就在運(yùn)輸表上對它進(jìn)行調(diào)整改進(jìn)，得一新解；再判斷,再改進(jìn)，直到得到最優(yōu)解。§ 3 指派問題（又稱分配問題AssignmentProblem）3.1 指派問題的數(shù)學(xué)模型例6擬分配n人去干n項工作，每人干且僅干一項工作，若分配第i人去干第j項工作，需花費(fèi)cj單位時間，問應(yīng)如何分配工作才能使工人花費(fèi)的總時間最少？容易看出，要給出一個指派問題的實(shí)例，只需給出矩陣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),其非負(fù)可行解的分量只能取0或1,故約束xj=01可改寫為xj之0而不改變其解。此時，指派問題被轉(zhuǎn)化為一個特殊的運(yùn)輸問題，其中m=n,a=bj=1。3.2求解指派

19、問題的匈牙利算法由于指派問題的特殊性，又存在著由匈牙利數(shù)學(xué)家法一匈牙利算法。算法主要依據(jù)以下事實(shí)：如果系數(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、再減去其所在列的最小元素得以實(shí)現(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)指派還無法看出。此時等價變換還可進(jìn)行下去。步驟如下：(1)對未選出0元素的行打7,(2)對v行中0元素所在列打7;(3)對V列中選中的0元素所在行打M；重復(fù)(2)、(3)直到無法再打爐為止?？梢宰C明，若用直線劃沒有打的行與打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)為它的對偶問題。不太嚴(yán)謹(jǐn)?shù)卣f，對偶問題可被看作是原始問題的“行

23、列轉(zhuǎn)置”：(1) 原始問題約束條件中的第j列系數(shù)與其對偶問題約束條件中的第系數(shù)相同；(2) 原始目標(biāo)函數(shù)的系數(shù)行與其對偶問題右側(cè)的常數(shù)列相同；(3) 原始問題右側(cè)的常數(shù)列與其對偶目標(biāo)函數(shù)的系數(shù)行相同；(4) 在這一對問題中，除非負(fù)約束外的約束不等式方向和優(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è)£是原問題的可行解，？是對偶問題的可行解,當(dāng)cT?=bT?時，x,?是最優(yōu)解。5o對偶定理：若原問題有有限最優(yōu)解，那么對偶問題也有最優(yōu)解；且目標(biāo)函數(shù)值相同。6o互補(bǔ)松弛性：若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,則利用互補(bǔ)松弛性可求得（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的值代入約束條件，得，為嚴(yán)格不等式；設(shè)原問題的最優(yōu)解為*x=（x1，,x5）,由互補(bǔ)松弛性得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í)際上這些系數(shù)往往是估計值和預(yù)測值。如市場條件一變，q值就會變化；aj往往是因工藝條件的改變而改變；。是根據(jù)資源投入后的經(jīng)濟(jì)效果決定的一種決策選擇。因此提出這樣兩個問題：當(dā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ā)生變化的各臨