利用Matlab解決數(shù)學(xué)問地題目

1、利用Matlab解決數(shù)學(xué)問題一、線性規(guī)劃求解線性規(guī)劃的Matlab解法單純形法是求解線性規(guī)劃問題的最常用、最有效的算法之一。單純形法是第一由GeorgeDantzig于1947年提出的，近60年來，雖有好多變形體已被開發(fā)，但卻保持著同樣的基本看法。由于有以下結(jié)論：若線性規(guī)劃問題有有限最優(yōu)解，則必然有某個最優(yōu)解是可行地域的一個極點?；诖?，單純形法的基本思路是：先找出可行域的一個極點，據(jù)必然規(guī)則判斷其可否最優(yōu)；若否，則變換到與之相鄰的另一極點，并使目標(biāo)函數(shù)值更優(yōu)；這樣下去，直到找到某一最優(yōu)解為止。這里我們不再詳細(xì)介紹單純形法，有興趣的讀者可以參看其余線性規(guī)劃書籍。下面我們介紹線性規(guī)劃的Matla

2、b解法。中線性規(guī)劃的標(biāo)準(zhǔn)型為mincTxsuchthatAxbx基本函數(shù)形式為linprog(c,A,b)，它的返回值是向量x的值。還有其余的一些函數(shù)調(diào)用形式（在Matlab指令窗運行helplinprog可以看到所有的函數(shù)調(diào)用形式），如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)這里fval返回目標(biāo)函數(shù)的值，Aeq和beq對應(yīng)等式拘束Aeq*xbeq，LB和UB分別是變量x的下界和上界，x0是x的初始值，OPTIONS是控制參數(shù)。例2求解以下線性規(guī)劃問題maxz2x13x25x3x1x2x372x15x2x310 x1,x2,x30解（i）編

3、寫M文件c=2;3;-5;a=-2,5,-1;b=-10;aeq=1,1,1;beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1)value=c*xii）將M文件存盤，并命名為。iii）在Matlab指令窗運行example1即可得所求結(jié)果。例3求解線性規(guī)劃問題minz2x13x2x3x14x22x383x12x26x1,x2,x30解編寫Matlab程序以下：c=2;3;1;a=1,4,2;3,2,0;b=8;6;x,y=linprog(c,-a,-b,zeros(3,1)二、整數(shù)規(guī)劃整數(shù)規(guī)劃問題的求解可以使用直接利用Matlab的函數(shù)，必定利用Lingo等專用

4、軟件。對于一般的整數(shù)規(guī)劃規(guī)劃問題，無法Matlab編程實現(xiàn)分枝定界解法和割平面解法。但對于指派問題等特其余01整數(shù)規(guī)劃問題或拘束矩陣A是幺模矩陣時，有時可以直接利用Matlab的函數(shù)linprog。c=382103;87297;6427584235;9106910;c=c(:);a=zeros(10,25);fori=1:5a(i,(i-1)*5+1:5*i)=1;a(5+i,i:5:25)=1;endb=ones(10,1);x,y=linprog(c,a,b,zeros(25,1),ones(25,1)求得最優(yōu)指派方案為x15x23x32x44x511，最優(yōu)值為21。三、非線性規(guī)劃Matl

5、ab中非線性規(guī)劃的數(shù)學(xué)模型寫成以下形式minf(x)AxBAeqxBeq,C(x)0Ceq(x)0其中f(x)是標(biāo)量函數(shù)，A,B,Aeq,Beq是相應(yīng)維數(shù)的矩陣和向量，C(x),Ceq(x)是非線性向量函數(shù)。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量x，其中FUN是用M文件定義的函數(shù)f(x)；X0是x的初始值；A,B,Aeq,Beq定義了線性拘束A*XB,Aeq*XBeq，若是沒有等式拘束，則A=,B=,Aeq=,Beq=；LB和UB是變量x的下界和上界，若是上界和下界沒有拘束，則LB=，UB=，

6、若是x無下界，則LB=-inf，若是x無上界，則UB=inf；NONLCON是用M文件定義的非線性向量函數(shù)C(x),Ceq(x)；OPTIONS定義了優(yōu)化參數(shù)，可以使用Matlab缺省的參數(shù)設(shè)置。例2求以下非線性規(guī)劃問題minf(x)x12x228x12x20 x1x2220 x1,x20.（i）編寫M文件functionf=fun1(x);f=x(1)2+x(2)2+8;和M文件functiong,h=fun2(x);g=-x(1)2+x(2);h=-x(1)-x(2)2+2;%等式拘束（ii）在Matlab的命令窗口依次輸入options=optimset;x,y=fmincon(fun1

7、,rand(2,1),zeros(2,1),.fun2,options)就可以求合適x11,x21時，最小值y10。四、圖論兩個指定極點之間的最短路徑問題以下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個網(wǎng)絡(luò)的兩個指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖G的極點，兩城鎮(zhèn)間的直通鐵路為圖G相應(yīng)兩極點間的邊，得圖G。對G的每一邊e，賦以一個實數(shù)w(e)直通鐵路的長度，稱為e的權(quán)，獲得賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖G中指定的兩個極點u0,v0間的具最小權(quán)的軌。這條軌叫做u0,v0間的最短路，它的權(quán)叫做u0,v0間的距離，亦記作d(u0,v0)。求最短路已有成熟的算法：迪

8、克斯特拉（Dijkstra）算法，其基本思想是按距u0從近到遠(yuǎn)為序次，依次求得u0到G的各極點的最短路和距離，直至v0（或直至G的所有極點），算法結(jié)束。為防備重復(fù)并保留每一步的計算信息，采用了標(biāo)號算法。下面是該算法。(i)令l(u0)0，對vu0，令l(v)，S0u0，i0。(ii)對每個vSi（SiVSi），用minl(v),l(u)w(uv)uSi代替l(v)。計算minl(v)，把達(dá)到這個最小值的一個極點記為ui1，令Si1Siui1。vSi(iii).若i|V|1，停止；若i|V|1，用i1代替i，轉(zhuǎn)(ii)。算法結(jié)束時，從u0到各極點v的距離由v的最后一次的標(biāo)號l(v)給出。在v進入

9、Si之前的標(biāo)號l(v)叫T標(biāo)號，v進入Si時的標(biāo)號l(v)叫P標(biāo)號。算法就是不斷更正各項點的T標(biāo)號，直至獲得P標(biāo)號。若在算法運行過程中，將每一極點獲得P標(biāo)號所由來的邊在圖上注明，則算法結(jié)束時，u0至各項點的最短路也在圖上標(biāo)示出來了。例9某公司在六個城市c,c,c6中有分公司，從ci到cj的直接航程票價記在下述12矩陣的(i,j)地址上。（表示無直接航路），請幫助該公司設(shè)計一張城市c1到其余城市間的票價最低價的路線圖。050402510500152025150102040201001025252010055102525550用矩陣ann（n為極點個數(shù)）存放各邊權(quán)的毗鄰矩陣，行向量pb、index

10、1、index2、d分別用來存放P標(biāo)號信息、標(biāo)號極點序次、標(biāo)號極點索引、最短通路的值。其中重量當(dāng)?shù)趇極點已標(biāo)號pb(i)；當(dāng)?shù)趇極點未標(biāo)號index2(i)存放始點到第i點最短通路中第i極點前一極點的序號；d(i)存放由始點到第i點最短通路的值。求第一個城市到其余城市的最短路徑的Matlab程序以下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=z

11、eros(1,6);a=a+a;pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;whilesum(pb)=2index=index(1);endindex2(temp)=index;endd,index1,index2每對極點之間的最短路徑計算賦權(quán)圖中各對極點之間最短路徑，顯然可以調(diào)用Dijkstra算法。詳細(xì)方法是：每次以不同樣的極點作為起點，用Dijkstra算法求出從該起點到其余極點的最短路徑，屢次執(zhí)行n次這樣的操作，即可獲得從每一個極點到其余極點的最短路徑。這

12、種算法的時間復(fù)雜度為O(n3)。第二種解決這一問題的方法是由FloydRW提出的算法，稱之為Floyd算法。假設(shè)圖G權(quán)的毗鄰矩陣為A0，a11a12a1na21a22a2nA0an1an2ann來存放各邊長度，其中：aii0i1,2,n；aiji,j之間沒有邊，在程序中以各邊都不可以能達(dá)到的充分大的數(shù)代替；aijwijwij是i,j之間邊的長度，i,j1,2,n。對于無向圖，A0是對稱矩陣，aijaji。Floyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列A0,A1,Ak,An，其中Ak(i,j)表示從極點vi到極點vj的路徑上所經(jīng)過的極點序號不大于k的最短路徑長度。計算時用迭代公式：Ak(i,j

13、)min(Ak1(i,j),Ak1(i,k)Ak1(k,j)k是迭代次數(shù)，i,j,k1,2,n。最后，當(dāng)kn時，An即是各極點之間的最短通路值。例10用Floyd算法求解例1。矩陣path用來存放每對極點之間最短路徑上所經(jīng)過的極點的序號。Floyd算法的Matlab程序以下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);b=a

14、+a;path=zeros(length(b);fork=1:6fori=1:6forj=1:6ifb(i,j)b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;endendendendb,pathprim算法構(gòu)造最小生成樹設(shè)置兩個會集P和Q,其中P用于存放G的最小生成樹中的極點，會集Q存放G的最小生成樹中的邊。令會集P的初值為Pv（假設(shè)構(gòu)造最小生成樹時，從極點v出發(fā)），11會集Q的初值為Q。prim算法的思想是，從所有pP，vVP的邊中，采用擁有最小權(quán)值的邊pv，將極點v加入會集P中，將邊pv加入會集Q中，這樣不斷重復(fù)，直到PV時，最小生成樹構(gòu)造達(dá)成

15、，這時會集Q中包含了最小生成樹的所有邊。prim算法以下：（i）Pv1，Q；ii）whilePVpvmin(wpv,pP,vVPPvQpvend例11用prim算法求右圖的最小生成樹。我們用result3n的第一、二、三行分別表示生成樹邊的起點、終點、權(quán)會集。Matlab程序以下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=

16、;p=1;tb=2:length(a);whilelength(result)=length(a)-1temp=a(p,tb);temp=temp(:);d=min(temp);jb,kb=find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresultKruskal算法構(gòu)造最小生成樹科茹斯克爾（Kruskal）算法是一個好算法。Kruskal算法以下:(i)選e1E(G)，使得w(e1)min。(ii)若e1,e2,ei已選好，則從E(G)e1,e2,ei中采用ei1，使得Ge1,e

17、2,ei,ei1中無圈，且w(ei1)min。直到選得e1為止。例12用Kruskal算法構(gòu)造例3的最小生成樹。我們用index2n存放各邊端點的信息，當(dāng)選中某一邊此后，就將此邊對應(yīng)的極點序號中較大序號u改記為此邊的另一序號v，同時把后邊邊中所有序號為u的改記為v。此方法的幾何意義是：將序號u的這個極點縮短到v極點，u極點不復(fù)存在。后邊連續(xù)尋查時，發(fā)現(xiàn)某邊的兩個極點序號同樣時，認(rèn)為已被縮短掉，失去了被采用的資格。Matlab程序以下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,

18、5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;i,j=find(a=0)&(a=M);b=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;whilelength(result)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag)=;endresult旅游商（TSP）問題一名銷售員準(zhǔn)備前往若干城市銷售產(chǎn)品，爾后回到他的出發(fā)地。如何為他設(shè)計一條最短的旅游路線（

19、從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地）這個問題稱為旅游商問題。用圖論的術(shù)語說，就是在一個賦權(quán)完好圖中，找出一個有最小權(quán)的Hamilton圈。稱這種圈為最優(yōu)圈。與最短路問題及連線問題相反，目前還沒有求解旅游商問題的有效算法。所以希望有一個方法以獲得相當(dāng)好（但不用然最優(yōu)）的解。一個可行的方法是第一求一個Hamilton圈C，爾后合適更正C以獲得擁有較小權(quán)的另一個Hamilton圈。更正的方法叫做改良圈算法。設(shè)初始圈Cv1v2vnv1。（i）對于1i1jn，構(gòu)造新的Hamilton圈:Cijv1v2vivjvj1vj2vi1vj1vj2vnv1,它是由C中刪去邊vivi1和vjvj1，增加

20、邊vivj和vi1vj1而獲得的。若w(vivj)w(vi1vj1)w(vivi1)w(vjvj1)，則以Cij代替C，Cij叫做C的改良圈。（ii）轉(zhuǎn)（i），直至無法改良，停止。用改良圈算法獲得的結(jié)果幾乎可以必然不是最優(yōu)的。為了獲得更高的精確度，可以選擇不同樣的初始圈，重復(fù)進行幾次算法，以求得較精確的結(jié)果。這個算法的利害程度有時能用Kruskal算法加以說明。假設(shè)C是G中的最優(yōu)圈。則對于任何極點v，Cv是在Gv中的Hamilton軌，所以也是Gv的生成樹。由此推知：若T是Gv中的最優(yōu)樹，同時e和f是和v關(guān)系的兩條邊，并使得w(e)w(f)盡可能小，則w(T)w(e)w(f)將是w(C)的一個下界。這里介紹的方法已被進一步發(fā)展。圈的修悔悟程一次代替三條邊比一次僅代替兩條邊更為有效；可是，有點奇怪的是，進一步實行這一想法，就不利了。例13