利用Matlab解决数学问地题目

利用Matlab解决数学识地题目利用Matlab解决数学识地题目利用Matlab解决数学识地题目利用Matlab解决数学识题

一、线性规划

求解线性规划的Matlab解法

纯真形法是求解线性规划问题的最常用、最有效的算法之一。纯真形法是第一由

GeorgeDantzig于1947年提出的，近60年来，虽有很多变形体已被开发，但却保持着相同

的基本见解。因为有以下结论：若线性规划问题有有限最优解，则必然有某个最优解是可行

地区的一个极点。鉴于此，纯真形法的基本思路是：先找出可行域的一个极点，据必然规则

判断其能否最优；若否，则变换到与之相邻的另一极点，并使目标函数值更优；这样下去，

直到找到某一最优解为止。这里我们不再详尽介绍纯真形法，有兴趣的读者能够参看其他线

性规划书本。下边我们介绍线性规划的Matlab解法。

中线性规划的标准型为

mincTxsuchthatAxbx

基本函数形式为linprog(c,A,b)，它的返回值是向量x的值。还有其他的一些函数调用形式（在

Matlab指令窗运转helplinprog能够看到全部的函数调用形式），如：

[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)

这里fval返回目标函数的值，Aeq和beq对应等式拘束Aeq*xbeq，LB和UB分别是变

量x的下界和上界，x0是x的初始值，OPTIONS是控制参数。

例2求解以下线性规划问题

maxz2x13x25x3x1x2x37

2x15x2x310

x1,x2,x30

解（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文件存盘，并命名为。

iii）在Matlab指令窗运转example1即可得所求结果。例3求解线性规划问题

minz2x13x2x3

x14x22x383x12x26x1,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))

二、整数规划

整数规划问题的求解能够使用

直接利用Matlab的函数，必然利用

Lingo等专用软件。关于一般的整数规划规划问题，没法

Matlab编程实现分枝定界解法和割平面解法。但关于指

派问题等特其他

0

1整数规划问题或拘束矩阵

A是幺模矩阵时，有时能够直接利用

Matlab

的函数

linprog。

例8求解以下指派问题，已知指派矩阵为

382103

87297

64275

84235

9106910

解：编写Matlab程序以下：

c=[382103;87297;64275

84235;9106910];

c=c(:);

a=zeros(10,25);

fori=1:5

a(i,(i-1)*5+1:5*i)=1;

a(5+i,i:5:25)=1;end

b=ones(10,1);

[x,y]=linprog(c,[],[],a,b,zeros(25,1),ones(25,1))

求得最优指派方案为x15x23x32x44x511，最优值为21。

三、非线性规划

Matlab中非线性规划的数学模型写成以下形式

minf(x)

AxB

AeqxBeq,C(x)0

Ceq(x)0

此中f(x)是标量函数，A,B,Aeq,Beq是相应维数的矩阵和向量，C(x),Ceq(x)是非线性向量函数。Matlab中的命令是X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)它的返回值是向量x，此中FUN是用M文件定义的函数f(x)；X0是x的初始值；A,B,Aeq,Beq定义了线性拘束A*XB,Aeq*XBeq，假如没有等式拘束，则

A=[],B=[],Aeq=[],Beq=[]；LB和UB是变量x的下界和上界，假如上界和下界没有拘束，则LB=[]，

UB=[]，假如x无下界，则LB=-inf，假如x无上界，则UB=inf；NONLCON是用M文件定义的

非线性向量函数C(x),Ceq(x)；OPTIONS定义了优化参数，能够使用Matlab缺省的参数设置。

例2求以下非线性规划问题

minf(x)x12x228x12x20x1x2220x1,x20.

（i）编写M文件

functionf=fun1(x);

f=x(1)^2+x(2)^2+8;

和M文件

function[g,h]=fun2(x);

g=-x(1)^2+x(2);

h=-x(1)-x(2)^2+2;%等式拘束

（ii）在Matlab的命令窗口挨次输入

options=optimset;

[x,y]=fmincon('fun1',rand(2,1),[],[],[],[],zeros(2,1),[],...

'fun2',options)

就能够求适合x11,x21时，最小值y10。

四、图论

两个指定极点之间的最短路径问题以下：给出了一个连结若干个城镇的铁路网络，在这个网络的两个指定城镇间，找

一条最短铁路线。

以各城镇为图G的极点，两城镇间的直通铁路为图G相应两极点间的边，得图G。对

G的每一边e，赋以一个实数w(e)—直通铁路的长度，称为e的权，获取赋权图G。G的

子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个极点u0,v0间的具最小权的轨。这条轨叫做u0,v0间的最短路，它的权叫做u0,v0间的距离，亦记作d(u0,v0)。

求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距u0从近到

远为次序，挨次求得u0到G的各极点的最短路和距离，直至v0（或直至G的全部极点），

算法结束。为防范重复并保存每一步的计算信息，采纳了标号算法。下边是该算法。

(i)令l(u0)0，对vu0，令l(v)，S0{u0}，i0。

(ii)对每个vSi（SiVSi），用

min{l(v),l(u)w(uv)}uSi

取代l(v)。计算min{l(v)}，把达到这个最小值的一个极点记为ui1，令Si1Si{ui1}。vSi(iii).若i|V|1，停止；若i|V|1，用i1取代i，转(ii)。

算法结束时，从u0到各极点v的距离由v的最后一次的标号l(v)给出。在v进入Si之前的标号l(v)叫T标号，v进入Si时的标号l(v)叫P标号。算法就是不停改正各项点的T标号，直至获取P标号。若在算法运转过程中，将每一极点获取P标号所由来的边在图上注明，则算法结束时，u0至各项点的最短路也在图上标示出来了。例9某企业在六个城市c,c,,c6中有分企业，从ci到cj的直接航程票价记在下述12矩阵的(i,j)地点上。（表示无直接航路），请帮助该企业设计一张城市c1到其他城市间的票价最廉价的路线图。

050402510500152025150102040201001025252010055102525550用矩阵ann（n为极点个数）寄存各边权的毗邻矩阵，行向量pb、index1、index2、d分别用来寄存P标号信息、标号极点次序、标号极点索引、最短通路的值。此中重量当第i极点已标号pb(i)；当第i极点未标号

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,:)=zeros(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)<length(a)

tb=find(pb==0);

d(tb)=min(d(tb),d(temp)+a(temp,tb));

tmpb=find(d(tb)==min(d(tb)));

temp=tb(tmpb(1));

pb(temp)=1;

index1=[index1,temp];

index=index1(find(d(index1)==d(temp)-a(temp,index1)));

iflength(index)>=2

index=index(1);

end

index2(temp)=index;

end

d,index1,index2

每对极点之间的最短路径计算赋权图中各对极点之间最短路径，明显能够调用Dijkstra算法。详尽方法是：每次

以不一样样的极点作为起点，用Dijkstra算法求出从该起点到其他极点的最短路径，频频履行n次

这样的操作，即可获取从每一个极点到其他极点的最短路径。这类算法的时间复杂度为

O(n3)。第二种解决这一问题的方法是由FloydRW提出的算法，称之为Floyd算法。

假定图G权的毗邻矩阵为A0，

a11a12a1na21a22a2nA0an1an2ann来寄存各边长度，此中：

aii0i1,2,,n；

aiji,j之间没有边，在程序中以各边都不能够能达到的充分大的数取代；

aijwijwij是i,j之间边的长度，i,j1,2,,n。关于无向图，A0是对称矩阵，aijaji。Floyd算法的基本思想是：递推产生一个矩阵序列A0,A1,,Ak,,An，此中Ak(i,j)表示从极点vi到极点vj的路径上所经过的极点序号不大于k的最短路径长度。计算时用迭代公式：Ak(i,j)min(Ak1(i,j),Ak1(i,k)Ak1(k,j))

k是迭代次数，i,j,k1,2,,n。

最后，当kn时，An即是各极点之间的最短通路值。例10用Floyd算法求解例1。

矩阵path用来寄存每对极点之间最短路径上所经过的极点的序号。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+a';path=zeros(length(b));

fork=1:6

fori=1:6

forj=1:6

ifb(i,j)>b(i,k)+b(k,j)

b(i,j)=b(i,k)+b(k,j);

path(i,j)=k;

endend

end

end

b,path

prim算法结构最小生成树

设置两个会合P和Q,此中P用于寄存G的最小生成树中的极点，会合Q寄存G的最小生成树中的边。令会合P的初值为P{v}（假定结构最小生成树时，从极点v出发），11会合Q的初值为Q

。prim算法的思想是，从全部pP，vVP的边中，采纳拥有

最小权值的边pv，将极点v加入会合P中，将边pv加入会合Q中，这样不停重复，直到

PV时，最小生成树结构完成，这时会合Q中包括了最小生成树的全部边。

prim算法以下：

（i）P{v1}，Q；

ii）whileP~V

pvmin(wpv,pP,vVP}

P{v}

Q{pv}

end例11用prim算法求右图的最小生成树。

我们用result3n的第一、二、三行分别表示生成树边的起点、终点、权会合。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=[];p=1;tb=2:length(a);

whilelength(result)~=length(a)-1

temp=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))=[];end

result

Kruskal算法结构最小生成树

科茹斯克尔（Kruskal）算法是一个好算法。Kruskal算法以下:

(i)选e1E(G)，使得w(e1)min。

(ii)若e1,e2,,ei已选好，则从E(G){e1,e2,,ei}中采纳ei1，使得

G[{e1,e2,,ei,ei1}]中无圈，且

②w(ei1)min。

直到选得e1为止。

例12用Kruskal算法结构例3的最小生成树。

我们用index2n寄存各边端点的信息，入选中某一边今后，就将此边对应的极点序号中

较大序号u改记为此边的另一序号v，同时把后边边中全部序号为u的改记为v。此方法的

几何意义是：将序号u的这个极点缩短到v极点，u极点不复存在。后边连续寻查时，发现

某边的两个极点序号相同时，以为已被缩短掉，失掉了被采纳的资格。

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;

[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)<loop

temp=min(data(3,:));

flag=find(data(3,:)==temp);

flag=flag(1);

v1=data(1,flag);v2=data(2,flag);

ifindex(1,flag)~=index(2,flag)

result=[result,data(:,flag)];

end

ifv1>v2

index(find(index==v1))=v2;else

index(find(index==v2))=v1;

end

data(:,flag)=[];

index(:,flag)=[];

end

result

旅行商（TSP）问题

一名销售员准备前去若干城市销售产品，此后回到他的出发地。怎样为他设计一条最短

的旅行路线（从驻地出发，经过每个城市恰巧一次，最后返回驻地）这个问题称为旅行商问

题。用图论的术语说，就是在一个赋权完满图中，找出一个有最小权的Hamilton圈。称这

种圈为最优圈。与最短路问题及连线问题相反，当前还没有求解旅行商问题的有效算法。所

以希望有一个方法以获取相当好（但不用然最优）的解。

一个可行的方法是第一求一个Hamilton圈C，此后适合改正C以获取拥有较小权的另

一个

Hamilton

圈。改正的方法叫做改进圈算法。设初始圈

Cv1v2

vnv1。

（i）关于

1

i

1

j

n，结构新的

Hamilton

圈:

Cij

v1v2

vivjvj1vj2

vi1vj1vj2

vnv1,

它是由

C

中删去边

vivi1

和

vjvj

1

，增添边

vivj

和vi

1vj1

而获取的。若

w(v

ivj)

w(vi

1vj1)

w(vivi1)

w(v

jvj1)，则以

Cij

取代

C，Cij

叫做

C的改进圈。（ii）转（i），直至没法改进，停止。

用改进圈算法获取的结果几乎能够必然不是最优的。为了获取更高的精准度，能够选择

不一样样的初始圈，重复进行几次算法，以求得较精准的结果。

这个算法的利害程度有时能用Kruskal算法加以说明。假定C是G中的最优圈。则关于

任何极点v，Cv是在Gv中的Hamilton轨，因此也是Gv的生成树。由此推知：若T

是Gv中的最优树，同时e和f是和v关系的两条边，并使得w(e)w(f)尽可能小，则

w(T)w(e)w(f)将是w(C)的一个下界。

这里介绍的方法已被进一步发展。圈的修悔过程一次取代三条边比一次仅取代两条边更

为有效；但是，有点奇异的是，进一步推行这一想法，就不利了。

例13从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅行，每城市恰去一次再回北京，应怎样安排旅行线，使旅途最短各城市之间的航线距离以下表：

LMNPaPeTL5635215160M5621577870N35213