数学建模常用算法

线性优化问题

min?fTx,?A*x?b,, ?s.t?Aeq*x?beq,?lb?x?ub.?其中c,x,b,beq,lb,ub位列向量；c称为价值向量；b称为资源向量；A,Aeq为矩阵。 Matlab中求解线性规划的命令为 [x,fval]=linprog(f,A,b)

[x,fval]=linprog(f,A,b,Aeq,Abq)

[x,fval]=linprog(f,A,b,Aeq,Abq,lb,ub)

中，x返回的是决策向量的取值；fval返回的是目标函数的最优值；f为价值向量；A和b对应的是线性不等式约束；Aeq和beq对应的是线性等式约束；lb和ub对应的是决策向量的下界向量和上界向量。 例1.2 求解下列线性规划问题

maxz?2x1?3x2?5x3

?x1?x2?x3?7?2x?5x?x?10?123 s..t??x1?3x2?x3?12??x1,x2,x3?0解：（1）化为Matlab标准型

minw??2x1?3x2?5x3

?x1???2,5,?1?????10?s.t???x2???12? 1,3,1???????x3?(2)求解Matlab程序如下： f=[-2;-3;5];

a=[-2,5,-1;1,3,1];b=[-10;12]; aeq=[1,1,1]; beq=7;

[x,y]=linprog(f,a,b,aeq,beq,zeros(3,1));

x,y=-y

(3)求解的Lingo程序如下： model: sets:

row/1..2/:b; col/1..3/:c,x;

links(row,col):a; endsets data:

c=2 3 -5;

a=-2 5 -1 1 3 1; b=-10 12; enddata

max=@sum(col:c*x);

@for(row(i):@sum(col(j):a(i,j)*x(j))

例1.3 求解下列线性规划问题

minz?2x1?3x2?x3

?x1?4x2?2x3?8?s.t.?3x1?2x2?6 ?x,x,x?0?123解：求解的Matlab程序如下： 2)求解Matlab程序如下： c=[2;3;1];

a=[1,4,2;3,2,0]; b=[8;6];

[x,y]=linprog(c,-a,-b,[],[],zeros(3,1));%这里没有等式约束，对应的矩阵为空矩阵 1.1.4 可以转化为线性规划的问题 例1.4 数学规划问题：

minx1?x2???xn,

s.t.Ax?b 取ui?xi?xi2,vi?Txi?xi2，则xiT?ui?vi,xi?ui?vi.

，则

记u??u1,?,un?,v??v1,?,vn?min?(ui?vi),

i?1n?A(u?v),s.t.?

?u,v?0.进一步改写为：

?u?min?1,?,1???,

?v???u??[A,?A]???b,s.t.? ?v??u,v?0.?

例1.5 求解下列数学规划问题：

minz?x1?2x2?3x3?4x4,

??x1?x2?x3?x4??2?s.t.?x1?x2?x3?3x4??1

?1?x1?x2?2x3?3x4??.2?解：（1）转化为标准型

做变量变换ui?xi?xi2T,vi?xi?xi2?u?,i?1,2,3,4并把新变量重新排序成一维向量y????v?=[u1,?,u4,v1,?,v4]，则可把模型变换为线性规划模型

min?cTy

??u?[A,?A]??v??bs.t??? ?y?0.?其中：c=[1,2,3,4,1,2,3,4]T;b=[-2,-1,-

1T];A=1?1?1 12

计算的Matlab程序如下： clc,clear

c=1:4;c=[c,c]';%构造价值列向量 a=[1 -1 -1 1;1 -11 -3;1,-1 -2 3]; a=[a,-a];%构造变换后新的系数矩阵 b=[-2 -1 -1/2]';

[y,z]=linprog(c,a,b,[],[],zeros(8,1)) x=y(1:4)-y(5:end)%变换到原来的问题，x=u-v 求的最优解x1=2,x2=x3=x4=0,最优解z=2.

该题用Lingo软件求解，Lingo程序如下： model: sets:

row/1..3/:b; col/1..4/:c,x; links(row,col):a; endsets data:

c=1 2 3 4;

a=1 -1 -1 1 1 -1 1 -3 1 -1 -2 3; b=-2 -1 -0.5; enddata

min=@sum(col:c*@abs(x));

@for(row(i):@sum(col(j):a(i,j)*x(j))

0-1规划模型

求解指派问题，已知指派矩阵为

[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]

这里需要把二维决策变量xij(I,j=1,……，5)变成一维决策变量yk（k=1,……，25），编写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,fval]=bintprog(c,[],[],a,b); x=reshape(x,[5,5]),fval 得最优解21

求解的Lingo程序如下： model: sets:

var/1..5/;

links(var,var):c,x; endsets data:

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;

enddata

min=@sum(links:c*x);

@for(var(i):@sum(var(j):x(i,j))=1); @for(var(j):@sum(var(i):x(i,j))=1);