数学建模常用算法.docx

文档介绍：线性优化问题
,
其中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)化为Matlab标准型
(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))<b(i));
***@sum(col:x)=7;
End
求解下列线性规划问题
解:求解的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)转化为标准型
做变量变换并把新变量重新排序成一维向量=,则可把模型变换为线性规划模型
其中:c=[1,2,3,4,1,2,3,4];b=[-2,-1,-];A=1-1-1 1
计算的Matlab程序如下:
clc,clear
c=1:4;c=[c,c]';%构造价值列向量
a=[1 -1 -1 1;1 -1 1 -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 -;
enddata
min=***@sum(col:c****@abs(x));
***@for(row(i):***@sum(col(j):a(i,j)*x(j))<b(i));
***@for(col:***@free(x));!x的分量可正可负;
End
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