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

1、利用Matlab解決數(shù)學(xué)問(wèn)題一、線(xiàn)性規(guī)劃求解線(xiàn)性規(guī)劃的Matlab解法單純形法是求解線(xiàn)性規(guī)劃問(wèn)題的最常用、最有效的算法之一。單純形法是第一由GeorgeDantzig于1947年提出的，近60年來(lái)，雖有好多變形體已被開(kāi)發(fā)，但卻保持著同樣的基本看法。由于有以下結(jié)論：若線(xiàn)性規(guī)劃問(wèn)題有有限最優(yōu)解，則必然有某個(gè)最優(yōu)解是可行地域的一個(gè)極點(diǎn)?；诖耍瑔渭冃畏ǖ幕舅悸肥牵合日页隹尚杏虻囊粋€(gè)極點(diǎn)，據(jù)必然規(guī)則判斷其可否最優(yōu)；若否，則變換到與之相鄰的另一極點(diǎn)，并使目標(biāo)函數(shù)值更優(yōu)；這樣下去，直到找到某一最優(yōu)解為止。這里我們不再詳細(xì)介紹單純形法，有興趣的讀者可以參看其余線(xiàn)性規(guī)劃書(shū)籍。下面我們介紹線(xiàn)性規(guī)劃的Matla

2、b解法。中線(xiàn)性規(guī)劃的標(biāo)準(zhǔn)型為mincTxsuchthatAxbx基本函數(shù)形式為linprog(c,A,b)，它的返回值是向量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)函數(shù)的值，Aeq和beq對(duì)應(yīng)等式拘束Aeq*xbeq，LB和UB分別是變量x的下界和上界，x0是x的初始值，OPTIONS是控制參數(shù)。例2求解以下線(xiàn)性規(guī)劃問(wèn)題maxz2x13x25x3x1x2x372x15x2x310 x1,x2,x30解（i）編

3、寫(xiě)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文件存盤(pán)，并命名為。iii）在Matlab指令窗運(yùn)行example1即可得所求結(jié)果。例3求解線(xiàn)性規(guī)劃問(wèn)題minz2x13x2x3x14x22x383x12x26x1,x2,x30解編寫(xiě)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ī)劃問(wèn)題的求解可以使用直接利用Matlab的函數(shù)，必定利用Lingo等專(zhuān)用

4、軟件。對(duì)于一般的整數(shù)規(guī)劃規(guī)劃問(wèn)題，無(wú)法Matlab編程實(shí)現(xiàn)分枝定界解法和割平面解法。但對(duì)于指派問(wèn)題等特其余01整數(shù)規(guī)劃問(wèn)題或拘束矩陣A是幺模矩陣時(shí)，有時(shí)可以直接利用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。三、非線(xiàn)性規(guī)劃M(mǎn)atl

5、ab中非線(xiàn)性規(guī)劃的數(shù)學(xué)模型寫(xiě)成以下形式minf(x)AxBAeqxBeq,C(x)0Ceq(x)0其中f(x)是標(biāo)量函數(shù)，A,B,Aeq,Beq是相應(yīng)維數(shù)的矩陣和向量，C(x),Ceq(x)是非線(xiàn)性向量函數(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定義了線(xiàn)性拘束A*XB,Aeq*XBeq，若是沒(méi)有等式拘束，則A=,B=,Aeq=,Beq=；LB和UB是變量x的下界和上界，若是上界和下界沒(méi)有拘束，則LB=，UB=，

6、若是x無(wú)下界，則LB=-inf，若是x無(wú)上界，則UB=inf；NONLCON是用M文件定義的非線(xiàn)性向量函數(shù)C(x),Ceq(x)；OPTIONS定義了優(yōu)化參數(shù)，可以使用Matlab缺省的參數(shù)設(shè)置。例2求以下非線(xiàn)性規(guī)劃問(wèn)題minf(x)x12x228x12x20 x1x2220 x1,x20.（i）編寫(xiě)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時(shí)，最小值y10。四、圖論兩個(gè)指定極點(diǎn)之間的最短路徑問(wèn)題以下：給出了一個(gè)連接若干個(gè)城鎮(zhèn)的鐵路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定城鎮(zhèn)間，找一條最短鐵路線(xiàn)。以各城鎮(zhèn)為圖G的極點(diǎn)，兩城鎮(zhèn)間的直通鐵路為圖G相應(yīng)兩極點(diǎn)間的邊，得圖G。對(duì)G的每一邊e，賦以一個(gè)實(shí)數(shù)w(e)直通鐵路的長(zhǎng)度，稱(chēng)為e的權(quán)，獲得賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。問(wèn)題就是求賦權(quán)圖G中指定的兩個(gè)極點(diǎn)u0,v0間的具最小權(quán)的軌。這條軌叫做u0,v0間的最短路，它的權(quán)叫做u0,v0間的距離，亦記作d(u0,v0)。求最短路已有成熟的算法：迪

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

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

10、1、index2、d分別用來(lái)存放P標(biāo)號(hào)信息、標(biāo)號(hào)極點(diǎn)序次、標(biāo)號(hào)極點(diǎn)索引、最短通路的值。其中重量當(dāng)?shù)趇極點(diǎn)已標(biāo)號(hào)pb(i)；當(dāng)?shù)趇極點(diǎn)未標(biāo)號(hào)index2(i)存放始點(diǎn)到第i點(diǎn)最短通路中第i極點(diǎn)前一極點(diǎn)的序號(hào)；d(i)存放由始點(diǎn)到第i點(diǎn)最短通路的值。求第一個(gè)城市到其余城市的最短路徑的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每對(duì)極點(diǎn)之間的最短路徑計(jì)算賦權(quán)圖中各對(duì)極點(diǎn)之間最短路徑，顯然可以調(diào)用Dijkstra算法。詳細(xì)方法是：每次以不同樣的極點(diǎn)作為起點(diǎn)，用Dijkstra算法求出從該起點(diǎn)到其余極點(diǎn)的最短路徑，屢次執(zhí)行n次這樣的操作，即可獲得從每一個(gè)極點(diǎn)到其余極點(diǎn)的最短路徑。這

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

13、)min(Ak1(i,j),Ak1(i,k)Ak1(k,j)k是迭代次數(shù)，i,j,k1,2,n。最后，當(dāng)kn時(shí)，An即是各極點(diǎn)之間的最短通路值。例10用Floyd算法求解例1。矩陣path用來(lái)存放每對(duì)極點(diǎn)之間最短路徑上所經(jīng)過(guò)的極點(diǎn)的序號(hào)。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ù)設(shè)置兩個(gè)會(huì)集P和Q,其中P用于存放G的最小生成樹(shù)中的極點(diǎn)，會(huì)集Q存放G的最小生成樹(shù)中的邊。令會(huì)集P的初值為Pv（假設(shè)構(gòu)造最小生成樹(shù)時(shí)，從極點(diǎn)v出發(fā)），11會(huì)集Q的初值為Q。prim算法的思想是，從所有pP，vVP的邊中，采用擁有最小權(quán)值的邊pv，將極點(diǎn)v加入會(huì)集P中，將邊pv加入會(huì)集Q中，這樣不斷重復(fù)，直到PV時(shí)，最小生成樹(shù)構(gòu)造達(dá)成

15、，這時(shí)會(huì)集Q中包含了最小生成樹(shù)的所有邊。prim算法以下：（i）Pv1，Q；ii）whilePVpvmin(wpv,pP,vVPPvQpvend例11用prim算法求右圖的最小生成樹(shù)。我們用result3n的第一、二、三行分別表示生成樹(shù)邊的起點(diǎn)、終點(diǎn)、權(quán)會(huì)集。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)造最小生成樹(shù)科茹斯克爾（Kruskal）算法是一個(gè)好算法。Kruskal算法以下:(i)選e1E(G)，使得w(e1)min。(ii)若e1,e2,ei已選好，則從E(G)e1,e2,ei中采用ei1，使得Ge1,e

17、2,ei,ei1中無(wú)圈，且w(ei1)min。直到選得e1為止。例12用Kruskal算法構(gòu)造例3的最小生成樹(shù)。我們用index2n存放各邊端點(diǎn)的信息，當(dāng)選中某一邊此后，就將此邊對(duì)應(yīng)的極點(diǎn)序號(hào)中較大序號(hào)u改記為此邊的另一序號(hào)v，同時(shí)把后邊邊中所有序號(hào)為u的改記為v。此方法的幾何意義是：將序號(hào)u的這個(gè)極點(diǎn)縮短到v極點(diǎn)，u極點(diǎn)不復(fù)存在。后邊連續(xù)尋查時(shí)，發(fā)現(xiàn)某邊的兩個(gè)極點(diǎn)序號(hào)同樣時(shí)，認(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）問(wèn)題一名銷(xiāo)售員準(zhǔn)備前往若干城市銷(xiāo)售產(chǎn)品，爾后回到他的出發(fā)地。如何為他設(shè)計(jì)一條最短的旅游路線(xiàn)（

19、從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地）這個(gè)問(wèn)題稱(chēng)為旅游商問(wèn)題。用圖論的術(shù)語(yǔ)說(shuō)，就是在一個(gè)賦權(quán)完好圖中，找出一個(gè)有最小權(quán)的Hamilton圈。稱(chēng)這種圈為最優(yōu)圈。與最短路問(wèn)題及連線(xiàn)問(wèn)題相反，目前還沒(méi)有求解旅游商問(wèn)題的有效算法。所以希望有一個(gè)方法以獲得相當(dāng)好（但不用然最優(yōu)）的解。一個(gè)可行的方法是第一求一個(gè)Hamilton圈C，爾后合適更正C以獲得擁有較小權(quán)的另一個(gè)Hamilton圈。更正的方法叫做改良圈算法。設(shè)初始圈Cv1v2vnv1。（i）對(duì)于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），直至無(wú)法改良，停止。用改良圈算法獲得的結(jié)果幾乎可以必然不是最優(yōu)的。為了獲得更高的精確度，可以選擇不同樣的初始圈，重復(fù)進(jìn)行幾次算法，以求得較精確的結(jié)果。這個(gè)算法的利害程度有時(shí)能用Kruskal算法加以說(shuō)明。假設(shè)C是G中的最優(yōu)圈。則對(duì)于任何極點(diǎn)v，Cv是在Gv中的Hamilton軌，所以也是Gv的生成樹(shù)。由此推知：若T是Gv中的最優(yōu)樹(shù)，同時(shí)e和f是和v關(guān)系的兩條邊，并使得w(e)w(f)盡可能小，則w(T)w(e)w(f)將是w(C)的一個(gè)下界。這里介紹的方法已被進(jìn)一步發(fā)展。圈的修悔悟程一次代替三條邊比一次僅代替兩條邊更為有效；可是，有點(diǎn)奇怪的是，進(jìn)一步實(shí)行這一想法，就不利了。例13