利用Matlab 解决数学问题
一、线性规划
求解线性规划的Matlab 解法
单纯形法是求解线性规划问题的最常用、最有效的算法之一。单纯形法是首先由
George Dantzig 于1947年提出的，近60年来，虽有许多变形体已被开发，但却保持着同样的基本观念。由于有如下结论：若线性规划问题有有限最优解，则一定有某个最优解是可行区域的一个极点。基于此，单纯形法的基本思路是：先出可行域的一个极点，据一定规则判断其是否最优；若否，则转换到与之相邻的另一极点，并使目标函数值更优；如此下去，直到到某一最优解为止。这里我们不再详细介绍单纯形法，有兴趣的读者可以参看其它线性规划书籍。下面我们介绍线性规划的Matlab 解法。
Matlab5.3中线性规划的标准型为
b
Ax x c T x ≤    such that      min 基本函数形式为linprog(c,A,b)，它的返回值是向量的值。还有其它的一些函数调用形式x （在 Matlab 指令窗运行 help linprog 可以看到所有的函数调用形式），如：
[x,fval]=linprog(c,A,b,Aeq,beq,LB,UB,X 0,OPTIONS)这里fval 返回目标函数的值，Aeq 和beq 对应等式约束，LB 和UB 分别是变beq x Aeq =*量的下界和上界，是的初始值，OPTIONS 是控制参数。
x 0x x 例2  求解下列线性规划问题
3
21532max x x x z -+=
⎪⎩⎪⎨⎧≥≥+-=++0,,105273
21321321x x x x x x x x x 解 （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即可得所求结果。
例3求解线性规划问题3
2132 min x x x z ++=
⎪⎩⎪⎨⎧≥≥+≥++0,,6
238243
如何用matlab将已知点连线2121321x x x x x x x x 解  编写Matlab 程序如下：
c=[2;3;1];
a=[1,4,2;3,2,0];
b=[8;6];
[x,y]=linprog(c,-a,-b,[],[],zeros(3,1))
二、整数规划
整数规划问题的求解可以使用Lingo 等专用软件。对于一般的整数规划规划问题，无法直接利用Matlab 的函数，必须利用Matlab 编程实现分枝定界解法和割平面解法。但对于指派问题等特殊的整数规划问题或约束矩阵是幺模矩阵时，有时可以直接利用10-A Matlab 的函数linprog 。
例8  求解下列指派问题，已知指派矩阵为
⎥⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎢⎣⎡10961095324
85724679278310283解：编写Matlab 程序如下：
c=[3 8 2 10 3;8 7 2 9 7;6 4 2 7 5
8 4 2 3 5;9 10 6 9 10];
c=c(:);
a=zeros(10,25);
for i=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))
求得最优指派方案为，最优值为21。
151********=====x x x x x
三、非线性规划
Matlab 中非线性规划的数学模型写成以下形式
)
(min x f
,⎪⎪⎩⎪⎪⎨⎧=≤=⋅≤0)(0
)(x Ceq x C Beq x Aeq B Ax 其中是标量函数，是相应维数的矩阵和向量，是非线)(x f Beq Aeq B A ,,,)(),(x Ceq x C 性向量函数。
Matlab 中的命令是
X=FMINCON(FUN,X0,A,B,Aeq,Beq,LB,UB,NONLCON,OPTIONS)
它的返回值是向量，其中FUN 是用M 文件定义的函数；X0是的初始值；x )(x f x A,B,Aeq,Beq 定义了线性约束，如果没有等式约束，则A=[],Beq X Aeq B X A =≤*,*B=[],Aeq=[],Beq=[]；LB 和UB 是变量的下界和上界，如果上界和下界没有约束，则x LB=[]，UB=[]，如果无下界，则LB=-inf ，如果无上界，则UB=inf ；NONLCON 是用M x x 文件定义的非线性向量函数；OPTIONS 定义了优化参数，可以使用Matlab )(),(x Ceq x C 缺省的参数设置。
例2  求下列非线性规划问题
⎪⎪⎩⎪⎪⎨⎧≥=+--≥-++=.0,0
208)( min 2
12212212221x x x x x x x x x f （i ）编写M 文件fun1.m
function f=fun1(x);
f=x(1)^2+x(2)^2+8;
和M 文件fun2.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)
就可以求得当时，最小值。
1,121==x x 10=y
四、图论
两个指定顶点之间的最短路径
问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，一条最短铁路线。
以各城镇为图的顶点，两城镇间的直通铁路为图相应两顶点间的边，得图。G G G 对的每一边，赋以一个实数—直通铁路的长度，称为的权，得到赋权图。G e )(e w e G 的子图的权是指子图的各边的权和。问题就是求赋权图中指定的两个顶点间的G G 00,v u 具最小权的轨。这条轨叫做间的最短路，它的权叫做间的距离，亦记作00,v u 00,v u 。
),(00v u d 求最短路已有成熟的算法：迪克斯特拉（Dijkstra ）算法，其基本思想是按距从近到0u 远为顺序，依次求得到的各顶点的最短路和距离，直至（或直至的所有顶点），0u G 0v G 算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。
(i) 令，对，令，，。
0)(0=u l 0u v ≠∞=)(v l }{00u S =0=i (ii) 对每个（），用
i S v ∈i i S V S \=)}()(),({min uv w u l v l i
S u +∈代替。计算，把达到这个最小值的一个顶点记为，令。)(v l )}({min v l i
S v ∈1+i u }{11++=i i i u S S  (iii). 若，停止；若，用代替，转(ii)。
1||-=V i 1||-<V i 1+i i 算法结束时，从到各顶点的距离由的最后一次的标号给出。在进入之0u v v )(v l v i S 前的标号叫T 标号，进入时的标号叫P 标号。算法就是不断修改各项点的T )(v l v i S )(v l 标号，直至获得P 标号。若在算法运行过程中，将每一顶点获得P 标号所由来的边在图上标明，则算法结束时，至各项点的最短路也在图上标示出来了。
0u 例9  某公司在六个城市中有分公司，从到的直接航程票价记在下621,,,c c c  i c j c 述矩阵的位置上。（表示无直接航路），请帮助该公司设计一张城市到其它城市),(j i ∞1c 间的票价最便宜的路线图。
⎥⎥⎥⎥⎥⎥⎥⎦
⎤⎢⎢⎢⎢⎢⎢⎢⎣⎡∞∞∞∞∞∞05525251055010202525100102040
2010015252015050102540500用矩阵（为顶点个数）存放各边权的邻接矩阵，行向量、
n n a ⨯n pb 、、分别用来存放标号信息、标号顶点顺序、标号顶点索引、最短通路1index 2index d P 的值。其中分量
；⎩
⎨⎧=顶点未标号当第顶点已标号当第i i i pb 01)( 存放始点到第点最短通路中第顶点前一顶点的序号；
)(2i index i i  存放由始点到第点最短通路的值。
)(i d 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;
while sum(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)));  if length(index)>=2
i ndex=index(1);
end
index2(temp)=index;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。