MATLAB課件第十一章線性極值

1、第十一章 線性極值MATLAB提供了很多求極值（或最優(yōu)值）的命令函數(shù)，既可以求無(wú)條件的極值，也可求有條件的極值，其中，條件可以是不等式，也可以是等式的，可以是線性的，也可以是非線性的，甚至可以是多個(gè)條件，目標(biāo)函數(shù)可以是線性的，也可以是非線性的，總之，MATLAB針對(duì)不同的類型，采用不同的函數(shù)命令去求解，以下將分類型來(lái)做些簡(jiǎn)單的介紹。1線性極值（又稱線性規(guī)劃）1.1線性規(guī)劃模型規(guī)劃問(wèn)題研究的對(duì)象大體可以分為兩大類：一類是在現(xiàn)有的人、財(cái)、物等資源的條件下，研究如何合理的計(jì)劃、安排，可使得某一目標(biāo)達(dá)到最大，如產(chǎn)量、利潤(rùn)目標(biāo)等；另一類是在任務(wù)確定后，如何計(jì)劃、安排，使用最低限度的人、財(cái)?shù)荣Y源，去實(shí)現(xiàn)該

2、任務(wù)，如使成本、費(fèi)用最小等。這兩類問(wèn)題從本質(zhì)上說(shuō)是相同的，即都在一組約束條件下，去實(shí)現(xiàn)某一個(gè)目標(biāo)的最優(yōu)（最大或最小）。線性規(guī)劃研究的問(wèn)題要求目標(biāo)與約束條件函數(shù)都是線性的，而目標(biāo)函數(shù)只能是一個(gè)。在經(jīng)濟(jì)管理問(wèn)題中，大量問(wèn)題是線性的，有的也可以轉(zhuǎn)化為線性的，從而使線性規(guī)劃有極大的應(yīng)用價(jià)值。線性規(guī)劃模型包含3個(gè)要素：（1）決策變量. 問(wèn)題中需要求解的那些未知量，一般用n維向量表示。（2）目標(biāo)函數(shù). 通常是問(wèn)題需要優(yōu)化的那個(gè)目標(biāo)的數(shù)學(xué)表達(dá)式，它是決策變量x的線性函數(shù)。（3）約束條件. 對(duì)決策變量的限制條件，即x的允許取值范圍，它通常是x的一組線性不等式或線性等式。線性規(guī)劃問(wèn)題的數(shù)學(xué)模型一般可表示為：mi

3、n（max） f T Xs.t A XbAeq X =beqlbXub其中X為n維未知向量，f T=f1,f2,fn為目標(biāo)函數(shù)系數(shù)向量，小于等于約束系數(shù)矩陣A為mn矩陣，b為其右端m維列向量，Aeq為等式約束系數(shù)矩陣，beq為等式約束右端常數(shù)列向量。lb,ub為自變量取值上界與下界約束的n維常數(shù)向量。特別注意：當(dāng)我們用MATLAB軟件作優(yōu)化問(wèn)題時(shí)，所有求maxf 的問(wèn)題化為求min(-f )來(lái)作。約束g i (x)0，化為 g i0來(lái)做。1.2線性規(guī)劃問(wèn)題求最優(yōu)解函數(shù)：調(diào)用格式：x=linprog(f,A,b)x=linprog(f,A,b,Aeq,beq)x=linprog(f,A,b,Ae

4、q,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, exitflag=linprog()x, fval, exitflag, output=linprog()x, fval, exitflag, output, lambda=linprog()說(shuō)明：x=linprog(f,A,b)返回值x為最優(yōu)解向量。x=linprog(f,A,b,Aeq,beq) 作有等式約束的問(wèn)題。若沒(méi)有不等式約束，則令A(yù)= 、b= 。x=linprog

5、(f,A,b,Aeq,beq,lb,ub,x0,options) 中l(wèi)b ,ub為變量x的下界和上界，x0為初值點(diǎn)，options為指定優(yōu)化參數(shù)進(jìn)行最小化。x,fval=linprog() 左端 fval 返回解x處的目標(biāo)函數(shù)值。x,fval,exitflag,output,lambda=linprog(f,A,b, Aeq,beq,lb,ub,x0) 的輸出部分： exitflag 描述函數(shù)計(jì)算的退出條件：若為正值，表示目標(biāo)函數(shù)收斂于解x處；若為負(fù)值，表示目標(biāo)函數(shù)不收斂；若為零值，表示已經(jīng)達(dá)到函數(shù)評(píng)價(jià)或迭代的最大次數(shù)。Output為關(guān)于優(yōu)化的一些信息。Lambda為解x的Lagrange乘子

6、?！纠?】求解線性規(guī)劃問(wèn)題：max f=2x1+5x2s.t 先將目標(biāo)函數(shù)轉(zhuǎn)化成最小值問(wèn)題：min(-f)=- 2x1-5x2具體程序如下：f=-2 -5;A=1 0;0 1;1 2;b=4;3;8;lb=0 0;x,fval=linprog(f,A,b,lb)f=fval*(-1)運(yùn)行結(jié)果：x = 2 3fval = -19.0000maxf = 19【例2】：minf=5x1-x2+2x3+3x4-8x5s.t 2x1+x2-x3+x4-3x562x1+x2-x3+4x4+x570xj15 j=1,2,3,4,5編寫(xiě)以下程序：f=5 -1 2 3 -8;A=-2 1 -1 1 -3;2 1

7、 -1 4 1;b=6;7;lb=0 0 0 0 0;ub=15 15 15 15 15;x,fval=linprog(f,A,b,lb,ub) 運(yùn)行結(jié)果：x = 0.0000 0.0000 8.0000 0.0000 15.0000minf = -104【例3】：假設(shè)某廠計(jì)劃生產(chǎn)甲、乙兩種產(chǎn)品，現(xiàn)庫(kù)存主要材料有A類3600公斤，B類2000公斤，C類3000公斤。每件甲產(chǎn)品需用材料A類9公斤，B類4公斤，C類3公斤。每件乙產(chǎn)品，需用材料A類4公斤，B類5公斤，C類10公斤。甲單位產(chǎn)品的利潤(rùn)70元，乙單位產(chǎn)品的利潤(rùn)120元。問(wèn)如何安排生產(chǎn)，才能使該廠所獲的利潤(rùn)最大。建立數(shù)學(xué)模型：設(shè)x1、x2分

8、別為生產(chǎn)甲、乙產(chǎn)品的件數(shù)。f為該廠所獲總潤(rùn)。max f=70x1+120x2s.t 9x1+4x236004x1+5x220003x1+10x23000x1,x20將其轉(zhuǎn)換為標(biāo)準(zhǔn)形式：min f=-70x1-120x2s.t 9x1+4x236004x1+5x220003x1+10x23000 x1,x20編寫(xiě)以下程序：f=-70 -120;A=9 4 ;4 5;3 10 ;b=3600;2000;3000;lb=0 0;x,fval,exitflag=linprog(f,A,b,lb); x, exitflag,maxf=-fval運(yùn)行結(jié)果： x = 200.0000 240.0000exi

9、tflag = 1maxf = 4.2800e+004【例4】：某公司有一批資金用于4個(gè)工程項(xiàng)目的投資，其投資各項(xiàng)目時(shí)所得的凈收益(投入資金百分比)如下表：工程項(xiàng)目收益表工程項(xiàng)目ABCD收益(%)1510812由于某種原因，決定用于項(xiàng)目A的投資不大于其他各項(xiàng)投資之和而用于項(xiàng)目B和C的投資要大于項(xiàng)目D的投資。試確定該公司收益最大的投資分配方案。建立數(shù)學(xué)模型：設(shè)x1、 x2 、x3 、x4分別代表用于項(xiàng)目A、B、C、D的投資百分?jǐn)?shù)。 max f=0.15x1+0.1x2+0.08 x3+0.12 x4s.t x1-x2- x3- x40x2+ x3- x40x1+x2+x3+ x4=1xj0 j=

10、1,2,3,4將其轉(zhuǎn)換為標(biāo)準(zhǔn)形式：min z=-0.15x1-0.1x2-0.08 x3-0.12 x4s.t x1-x2- x3- x40 -x2- x3+ x40 x1+x2+x3+ x4=1xj0 j=1,2,3,4編寫(xiě)程序：f = -0.15;-0.1;-0.08;-0.12;A = 1 -1 -1 -1;0 -1 -1 1;b = 0; 0;Aeq=1 1 1 1;beq=1;lb = zeros(4,1); x,fval,exitflag = linprog(f,A,b,Aeq,beq,lb)fmax=-fval運(yùn)行結(jié)果：x = 0.5000 0.2500 0.0000 0.250

11、0fval = -0.1300exitflag = 1fmax =0.1300 即4個(gè)項(xiàng)目的投資百分?jǐn)?shù)分別為50%，25%，0, 25%時(shí)可使該公司獲得最大的收益，其最大收益可到達(dá)13%。過(guò)程正常收斂。【例5】：有A、B、C三個(gè)食品加工廠，負(fù)責(zé)供給甲、乙、丙、丁四個(gè)市場(chǎng)。三個(gè)廠每天生產(chǎn)食品箱數(shù)上限如下表：工廠ABC生產(chǎn)數(shù)604050四個(gè)市場(chǎng)每天的需求量如下表：市場(chǎng)甲乙丙丁需求量20353334從各廠運(yùn)到各市場(chǎng)的運(yùn)輸費(fèi)(元/每箱)由下表給出：收點(diǎn)發(fā)點(diǎn)市 場(chǎng)甲乙丙丁工廠A2132B1321C3411求在基本滿足供需平衡的約束條件下使總運(yùn)輸費(fèi)用最小。建立數(shù)學(xué)模型：設(shè)ai j為由工廠i運(yùn)到市場(chǎng)j的費(fèi)用

12、，xi j 是由工廠i運(yùn)到市場(chǎng)j的箱數(shù)。bi是工廠i的產(chǎn)量，dj是市場(chǎng)j的需求量。 b= ( 60 40 50 ) d= ( 20 35 33 34 )s.t x i j0編寫(xiě)程序： AA=2 1 3 2;1 3 2 1;3 4 1 1;f=AA(:);A= 1 0 0 1 0 0 1 0 0 1 0 00 1 0 0 1 0 0 1 0 0 1 00 0 1 0 0 1 0 0 1 0 0 1;Aeq=1 1 1 0 0 0 0 0 0 0 0 00 0 0 1 1 1 0 0 0 0 0 00 0 0 0 0 0 1 1 1 0 0 00 0 0 0 0 0 0 0 0 1 1 1;b=6

13、0;40;50;beq=20;35;33;34;lb=zeros(12,1);x,fval,exitflag=linprog(f,A,b,Aeq,beq,lb)運(yùn)行結(jié)果：x = 0.0000 20.0000 0.0000 35.0000 0.0000 0.0000 0.0000 0.0000 33.0000 0.0000 18.4682 15.5318fval =122.0000exitflag = 1即運(yùn)輸方案為：甲市場(chǎng)的貨由B廠送20箱；乙市場(chǎng)的貨由A廠送35箱；丙商場(chǎng)的貨由C廠送33箱；丁市場(chǎng)的貨由B廠送18箱，再由C廠送16箱。最低總運(yùn)費(fèi)為：122元。2 0-1整數(shù)規(guī)劃求極值形如： m

14、in f T X s.t A XbAeq X =beqxi為0或1 其中X為n維未知向量，f T=f1,f2,fn為目標(biāo)函數(shù)系數(shù)向量，小于等于約束系數(shù)矩陣A為mn矩陣，b為其右端m維列向量，Aeq為等式約束系數(shù)矩陣，beq為等式約束右端常數(shù)列向量。lb,ub為自變量取值上界與下界約束的n維常數(shù)向量。2.1分支定界法在Matlab中提供了bintprog函數(shù)實(shí)現(xiàn)0-1型線性規(guī)劃，采用的是分支定界法原理，其調(diào)用格式如下：x=bintprog(f,A,b)x=bintprog(f,A,b,Aeq,beq)x,fval=bintprog()x, fval, exitflag=bintprog()x,

15、fval, exitflag, output=bintprog()x, fval, exitflag, output, lambda=bintprog()說(shuō)明：x=bintprog(f,A,b)返回值x為最優(yōu)解向量。x=bintprog(f,A,b,Aeq,beq) 作有等式約束的問(wèn)題。若沒(méi)有不等式約束，則令A(yù)= 、b= 。x,fval=bintprog() 左端 fval 返回解x處的目標(biāo)函數(shù)值?！纠?】求解以下問(wèn)題：max z=x1+1.2x2+0.8x3st2.1x1+2x2+1.3x3=50.8x1+x2=5x1+2.5x2+2x3=82x2=8x1,x2,x3為0或1解答:首先，將其

16、改變成0-1整數(shù)規(guī)劃函數(shù)bintprog要求的標(biāo)準(zhǔn)形式：min z=-x1-1.2x2-0.8x3st2.1x1+2x2+1.3x3=50.8x1+x2=5x1+2.5x2+2x3=82x2=8x1,x2,x3為0或1Matlab求解：c=-1,-1.2,-0.8;A=2.1,2,1.3;0.8,1,0;1,2.5,2;0,2,0;b=5;5;8;8;x,fval=bintprog(c,A,b);xfmax=-fval運(yùn)行結(jié)果可得：x= 1 1 0fmax = 2.2000【例7】某快餐連鎖經(jīng)營(yíng)公司有7個(gè)地點(diǎn)（A1，A2，-，A7）可以設(shè)立快餐店，由于地理位置因素，設(shè)立快餐店時(shí)必須滿足以下要求

17、：A1，A2，A3三個(gè)地點(diǎn)最多可選兩個(gè)，A1和A5至少選取一個(gè)，A6和A7至少選取一個(gè)。已知各個(gè)地點(diǎn)設(shè)立快餐店的投入和預(yù)計(jì)收益如表所示。已知目前公司有650萬(wàn)元可以投資。問(wèn)怎樣投資才能使公司預(yù)計(jì)收益最高？地點(diǎn)A1A2A3A4A5A6A7利潤(rùn)/萬(wàn)元101181215125投資/萬(wàn)元1031409515019316080解：這是一個(gè)選址問(wèn)題。首先引入0-1變量xi;xi=1,選擇Ai地址；xi=0,不選擇Ai地址。則該問(wèn)題的數(shù)學(xué)模型可以表示如下：max z=10x1+11x2+8x3+12x4+15x5+12x6+5x7st(1)103x1+140x2+95x3+150x4+193x5+160x6

18、+80x7=650(2)x1+x2+x3=1(4)x6+x7=1(5)xi=0,1matlab求解程序如下：c=-10 -11 -8 -12 -15 -12 -5;A=103 140 95 150 193 160 80;1 1 1 0 0 0 0; 0 0 0 -1 -1 0 0;0 0 0 0 0 -1 -1;b=650;2;-1;-1;x,fval=bintprog(c,A,b);xf=fval*(-1)運(yùn)行程序得：x=1;1;0;1;0;1;1,fval=502.2 枚舉法除了采用分支定界法原理計(jì)算0-1整數(shù)規(guī)劃外，還可以采用枚舉法枚舉法程序bintLp_E.mfunction x,f=

19、bintLp_E(c,A,b,N)%x,f=bintLp_E(c,A,b,N):用枚舉法求解下列0-1線性規(guī)劃%min f=c*x,s.t.A*x=b,x的分量全為0或1%其中N表示約束條件A*x=b中的前N個(gè)是等式，N=0時(shí)可以省略%返回結(jié)果x是最優(yōu)解，f是最優(yōu)解處的函數(shù)值if nargin4 N=0;endc=c(:);b=b(:);m,n=size(A);x=;f=abs(c)*ones(n,1);i=1;while i0); t1=t11;t12; if isempty(t1) f=min(f,c*B); if c*B=f x=B; end end i=i+1;end注意：以上程序需保

20、存至搜索路徑之下才可以調(diào)用?！纠?】 求解下列0-1型整數(shù)線性規(guī)劃。解：分別采用二種算法計(jì)算如下：c=3 -2 5;a=1 2 -1;1 4 -1 ;1 1 0;0 4 1;b=2;4;3;6;x,fval=bintprog(c,a,b)xx,ffval=bintLp_E(c,a,b)計(jì)算結(jié)果如下：x = 0 1 0fval = -2xx = 0 1 0ffval = -2【例9】A1加工B1,A2加工B3,A3加工B2配件時(shí)所需總時(shí)間最少,只需10小時(shí).練習(xí)2:某公司有A1,A2,A3三項(xiàng)業(yè)務(wù)需要B1,B2,B3三位業(yè)務(wù)員處理,每個(gè)業(yè)務(wù)員處理業(yè)務(wù)的費(fèi)用如表所示,其中業(yè)務(wù)員B2不能處理業(yè)務(wù)A1

21、,問(wèn)應(yīng)指派何人去完成何項(xiàng)業(yè)務(wù),使所需總費(fèi)用最少?B1B2B3A11500不能處理800A21200900750A3900800900解:設(shè)xij表示第i項(xiàng)業(yè)務(wù)被第j位業(yè)務(wù)員處理，其中不能處理時(shí)可以認(rèn)為費(fèi)用非常高，比如元，則依題意可得如下模型：min z=1500x11+x12+800x13+1200x21+900x22+750x23+900x31+800x32+900x33stx11+x12+x13=1x21+x22+x23=1x31+x32+x33=1x11+x21+x31=1x12+x22+x32=1x13+x23+x33=1xij=0,1編寫(xiě)matlab程序：c=1500 800 120

22、0 900 750 900 800 900;Aeq=1 1 1 0 0 0 0 0 0; 0 0 0 1 1 1 0 0 0; 0 0 0 0 0 0 1 1 1; 1 0 0 1 0 0 1 0 0; 0 1 0 0 1 0 0 1 0; 0 0 1 0 0 1 0 0 1;beq=ones(6,1);x,fval=bintprog(c,Aeq,beq)xx,ffval=bintLp_E(c,Aeq,beq,6)運(yùn)行程序可得：x=xx=0 0 1 0 1 0 1 0 0;fval=ffval2600答案:A1被B3處理，A2被B2處理，A3被B1處理時(shí)總費(fèi)用最少,只需2600元.3 整數(shù)規(guī)劃

23、求極值MATLAB關(guān)于整數(shù)規(guī)劃沒(méi)有內(nèi)帶的函數(shù)，目前關(guān)于整數(shù)規(guī)劃的自編程序已編好，以下是其中之一：functionx,val,status=ip(f,A,b,Aeq,beq,lb,ub,M,e)options=optimset(display,off); bound=inf;x0,val0=linprog(f,A,b,Aeq,beq,lb,ub,options);x,val,status,b=rec(f,A,b,Aeq,beq,lb,ub,x0,val0,M,e,bound); functionxx,val,status,bb=rec(f,A,b,Aeq,beq,lb,ub,x,v,M,e,bo

24、und)options=optimset(display,off);x0,val0,status0=linprog(f,A,b,Aeq,beq,lb,ub,options);if status0bound xx=x;val=v;status=status0;bb=bound; return;endind=find(abs(x0(M)-round(x0(M)e);if isempty(ind) status=1; if val0br_value br_var=tempbr_var; br_value=tempbr_value; endendif isempty(A) r c=size(Aeq);

25、else r c=size(A);endA1=A;zeros(1,c);A1(end,br_var)=1;b1=b;floor(br_value);A2=A;zeros(1,c);A2(end,br_var)=-1;b2=b;-ceil(br_value);x1,val1,status1,bound1=rec(f,A1,b1,Aeq,beq,lb,ub,x0,val0,M,e,bound);status=status1;if status10&bound10&bound2bound status=status2; xx=x2; val=val2; bb=bound2;end注意：請(qǐng)先將以上程序保存至搜索路徑之下，函數(shù)名為ip.m 函數(shù)調(diào)用規(guī)則如下：x,val,status=ip(c,A,b,Aeq,beq,lb,ub