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

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

2、線性規(guī)劃的Matlab解法。Matlab5.3中線性規(guī)劃的標準型為min cTx such that Ax 三 b x基本函數(shù)形式為linprog(c,A,b),它的返回值是向量 x的值。還有其它的一些函數(shù)調(diào)用形 式(在Matlab 指令窗運行help linprog可以看到所有的函數(shù)調(diào)用形式)，如：x,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0QPTIONS)這里fval返回目標函數(shù)的值，Aeq和beq對應等式約束 Aeq*x = beq, LB和UB分別是變量x的下界和上界，x0是x的初始值，OPTION能控制參數(shù)。例2求解下列線性規(guī)劃問題max z = 2x1

3、3x2 - 5x3Xi 2 3 = 7 2x1 -5x2 + x3 2 10x1, x 2, x3 0解(i )編寫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*x(ii )將 M文件存盤，并命名為 example1.m。(iii )在Matlab指令窗運行example1即可得所求結(jié)果。例3求解線性規(guī)劃問題min z =2x13x2x3x14x22x3 = 83x12x2 ,6Xl,X2,X3 -0解編寫Matlab程序如下：c=2；3；1；a=1,4,2;3,2

4、,0;b=8；6;x,y=linprog(c,-a,-b,口,zeros(3,1)、整數(shù)規(guī)劃整數(shù)規(guī)劃問題的求解可以使用 Lingo等專用軟件。對于一般的整數(shù)規(guī)劃規(guī)劃問題，無法直接利用Matlab的函數(shù)，必須利用Matlab編程實現(xiàn)分枝定界解法和割平面解法。但對于指派問題等特殊的0-1整數(shù)規(guī)劃問題或約束矩陣 A是幺模矩陣時，有時可以直接利用 Matlab 的函數(shù)linprog。例8求解下列指派問題，已知指派矩陣為3821038729764275842359106910-解：編寫Matlab程序如下：c=3 8 2 10 3;8 7 2 9 7;6 4 2 7 58 4 2 3 5;9 10 6

5、9 10;c=c(：)；a=zeros(10,25);for i=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)指派方案為x15 = x23 = x32 = x44 = x51 = 1 ,最優(yōu)值為21。三、非線性規(guī)劃Matlab中非線性規(guī)劃的數(shù)學模型寫成以下形式min f(x)Ax BAeq x = BeqC(x) 0 2 . 一 -x1 - x2 +2=0L. x1 , x2 0.(i )編寫 M文件fun1.mfunction f=f

6、un1(x);f=x(1)A2+x(2)A2+8;和M文件fun2.mfunction g,h=fun2(x);g=-x(1)A2+x(2);h=-x(1)-x(2)A2+2; %等式約束(ii )在Matlab的命令窗口依次輸入options=optimset;x,y=fmincon( fun1 ,rand(2,1)，口口口口zeros(2,1)口.fun2 , options)就可以求得當x1 = 1, x2 = 1時，最小值y = 10。四、圖論兩個指定頂點之間的最短路徑問題如下：給出了一個連接若干個城鎮(zhèn)的鐵路網(wǎng)絡，在這個網(wǎng)絡的兩個指定城鎮(zhèn)間，找一條最短鐵路線。以各城鎮(zhèn)為圖G的頂點，兩城

7、鎮(zhèn)間的直通鐵路為圖 G相應兩頂點間的邊，得圖 G。對 G的每一邊e,賦以一個實數(shù) w(e)直通鐵路的長度， 稱為e的權(quán)，得到賦權(quán)圖G。G的 子圖的權(quán)是指子圖的各邊的權(quán)和。 問題就是求賦權(quán)圖 G中指定的兩個頂點u0,v0間的具最小 權(quán)的軌。這條軌叫做 Uo,Vo間的最短路，它的權(quán)叫做 Uo,Vo間的距離，亦記作 d(Uo,Vo)。求最短路已有成熟的算法：迪克斯特拉( Dijkstra )算法，其基本思想是按距 u0從近到遠為順序，依次求得uo到G的各頂點的最短路和距離，直至vo (或直至G的所有頂點)算法結(jié)束。為避免重復并保留每一步的計算信息，采用了標號算法。下面是該算法。 令 l (Uo) =

8、0 ,對 v #Uo ,令 l (v) =g , So=uo, i=0。(ii) 對每個 v w Si ( S =V Si),用mipl(v),l (u) w(uv)口由，令ST=SiUu書。u Si代替l(v)。計算minl(v),把達到這個最小值的一個頂點記為 v：(iii) . 若 i =|V | 1,停止;若 i |V | 1,用 i +1 代替 i,轉(zhuǎn)(ii)算法結(jié)束時，從Uo到各頂點v的距離由v的最后一次的標號l(v)給出。在v進入Si之前的標號l(v)叫T標號，v進入Si時的標號l(v)叫P標號。算法就是不斷修改各項點的T標號，直至獲得P標號。若在算法運行過程中， 將每一頂點獲得

9、 P標號所由來的邊在圖上標 明，則算法結(jié)束時，u0至各項點的最短路也在圖上標示出來了。例9某公司在六個城市 Ci, C2 ,，C6中有分公司，從Ci到Cj的直接航程票價記在下述矩陣的(i, j)位置上。(g表示無直接航路)，請幫助該公司設計一張城市G到其它城市間的票價最便宜的路線圖。一050C3O4025105001520oO25cd1501020004020100102525O020100551025oO25550用矩陣anM( n為頂點個數(shù))存放各邊權(quán)的鄰接矩陣，行向量 pb、index1、inde”、d分別用來存放 P標號信息、標號頂點順序、標號頂點索引、最短通路的值。其中分量1當?shù)趇頂

10、點已標號pb(i)=，；0當?shù)趇頂點未標號index?。)存放始點到第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,:)=zeros(1,6);a=a+a;pb(1:length(a)=0;pb(1)=1;index1=1

11、;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2index=index(1);endindex2(temp)=index;endd, index1, index23.2每對頂點之間的最短路徑計算賦權(quán)圖中各對頂點之間最短路徑，顯然可以調(diào)用 Dijkstra 算法。具體方法是：每 次以不同的頂點作為起點，用Dijkstra 算法求出從該起點到其余頂點的最短路徑，反復執(zhí)行n次這樣的操作，就可得到從每一個頂點到其它頂點的最短路徑。這種算法的時間復雜度為O(n3)。第二種解決這一問題的方法是由Floyd R W提

12、出的算法，稱之為 Floyd算法。假設圖G權(quán)的鄰接矩陣為A0 ,a11a12a1n 1a2ia22a2nAo 99an1an2ann來存放各邊長度，其中：aii 0 i 1,2,，n ；a。=6 i,j之間沒有邊，在程序中以各邊都不可能達到的充分大的數(shù)代替；a。=WjWij 是 i,j 之間邊的長度，i,j=1,21，n。對于無向圖，Ao是對稱上!陣，aj=aji。Floyd算法的基本思想是：遞推產(chǎn)生一個矩陣序列A0,A1,，Ak,，An,其中Ak(i,j)表示從頂點Vi到頂點Vj的路徑上所經(jīng)過的頂點序號不大于k的最短路徑長度。計算時用迭代公式：Ak(i, j) =min(，(i, j), A

13、(i,k) Ay(k,j)k是迭代次數(shù)，i, j,k =1,2，n。最后，當k=n時，An即是各頂點之間的最短通路值。例10用Floyd算法求解例1。Floyd 算法的 Matlab矩陣path用來存放每對頂點之間最短路徑上所經(jīng)過的頂點的序號。 程序如下：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+a;path=ze

14、ros(length(b);for k=1:6for i=1:6for j=1:6if b(i,j)b(i,k)+b(k,j) b(i,j)=b(i,k)+b(k,j);path(i,j尸k;endendendendb, path4.2.1 prim算法構(gòu)造最小生成樹設置兩個集合P和Q,其中P用于存放G的最小生成樹中的頂點，集合 Q存放G的最小生成樹中的邊。令集合 P的初值為P=5（假設構(gòu)造最小生成樹時，從頂點Vi出發(fā)），集合Q的初值為Q =6。prim算法的思想是，從所有 pP, vV -P的邊中，選取具有最小權(quán)值的邊 pv,將頂點v加入集合P中，將邊pv加入集合Q中，如此不斷重復，直Q中包

15、含了最小生成樹的所有邊。到P =V時，最小生成樹構(gòu)造完畢，這時集合prim算法如下：(i ) P =v1 , Q =；(ii ) while P =Vpv = min( wpv, p P, v V - PP = P vQ = Q pvend例11用prim算法求右圖的最小生成樹。我們用result3珀的第一、二、三行分別表示生成樹邊的起點、終點、權(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

16、(5,6)=70;a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);while length(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)戶口；endresult4.2.1 Kruskal算法構(gòu)造最小生成樹科茹斯克爾(Kruskal )算法是一個好算法。Kruskal算法如下：(i)選 e w

17、 E(G),使得 w(e1) =min。(ii)若ee,，已選好，則從E(G) ee,，ej中選取e書，使得G e, e2,，ei e書中無圈,且 w(e +) =min。(iii) 直到選得ev為止。例12用Kruskal算法構(gòu)造例3的最小生成樹。我們用index2M存放各邊端點的信息，當選中某一邊之后，就將此邊對應的頂點序號中較大序號u改記為此邊的另一序號v,同時把后面邊中所有序號為u的改記為v。此方法的幾何意義是：將序號 u的這個頂點收縮到 v頂點，u頂點不復存在。后面繼續(xù)尋查時，發(fā)現(xiàn) 某邊的兩個頂點序號相同時，認為已被收縮掉，失去了被選取的資格。Matlab程序如下：clc;clear

18、;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;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=;while length(result)v2index(find(index=v1)=v2;elseindex(find(index=v2)=v1;enddata(:,flag)=;index(:,flag戶口； endresult旅行商(TSP)問題一名推銷員準備前往若干城市推銷產(chǎn)品，然后回到他的出發(fā)地。如何為他設計一條最短的旅行路線(從駐地出發(fā)，經(jīng)過每個城市恰好一次，最后返回駐地)？這個問題稱為旅行商 問題。用圖論的術(shù)語說，就是