数学建模.docx
《数学建模.docx》由会员分享,可在线阅读,更多相关《数学建模.docx(23页珍藏版)》请在冰点文库上搜索。
数学建模
数学建模答案(转)
Lindo/Lingo软件是美国Lindo系统公司开发的一套专门用于求解优化模型的软件。
Lindo系统公司面向全社会免费提供该软件的“演示版”,我们现在使用的就是这个演示版。
占领硬盘空间大约20MB.
下载大学授课视频,新东方英语四六级视频,计算机三级视频,就到
一.Lingo入门
1.编写简单的Lingo程序
Lingo程序:
在“模型窗口”中,按Lingo语法格式,输入一个完整的优化模型。
(注意:
一个程序就是一个优化模型)
例1要求解线性规划问题
输入程序:
max=2*x+3*y;
4*x+3*y<=10;
3*x+5*y<=12;
例2求解
输入程序:
max=98*x1+277*x2-x1^2-0.3*x1*x2-2*x2^2;
x1+x2<=100;
x1<=2*x2;
@gin(x1);
@gin(x2);
2.语法格式
(1)目标函数max=或min=
(2)每个语句的结尾要有“;”
(3)程序中,各个语句的先后次序无关
(4)自动默认各个变量均为大于等于零的实数
(5)不区分大写、小写
(6)程序中的“<=”、“<”等同于原模型中的“
”
程序中的“>=”、“>”等同于原模型中的“
”
(7)对一个特定的变量x,进行限制:
@free(x):
把x放宽为任意实数
@gin(x):
限制x为整数
@bin(x):
限制x只能取0或1
@bnd(-6,x,18):
限制x为闭区间[-6,18]上的任意实数
例3:
某学校游泳队要从5名队员中选4名参加4乘100米混合泳接力赛。
5名队员4种泳姿的百米成绩(单位:
秒)
-----------------------------------------------------------------------------------
李王张刘赵
蝶泳66.857.2787067.4
仰泳75.66667.874.271
蛙泳8766.484.669.683.8
自由泳58.65359.457.262.4
-----------------------------------------------------------------------------------
如何选拔?
(1)请建立“0----1规划”模型;
(2)用Lingo求解。
解:
若第i名队员参加第j种泳姿比赛,则令
;否则令
;
共有20个决策变量
。
第i名队员的第j种泳姿成绩记为
,则
目标函数为:
约束条件有:
每名队员顶多能参加一种泳姿比赛
;
每种泳姿有且仅有一人参加
这样就能建立如下“0----1规划”模型:
s.t.
Lingo程序如下:
min=66.8*x11+57.2*x21+78*x31+70*x41+67.4*x51+75.6*x12+66*x22+67.8*x32+74.2*x42+71*x52+87*x13+66.4*x23+84.6*x33+69.6*x43+83.8*x53+58.6*x14+53*x24+59.4*x34+57.2*x44+62.4*x54;
x11+x12+x13+x14<=1;
x21+x22+x23+x24<=1;
x31+x32+x33+x34<=1;
x41+x42+x43+x44<=1;
x51+x52+x53+x54<=1;
x11+x21+x31+x41+x51=1;
x12+x22+x32+x42+x52=1;
x13+x23+x33+x43+x53=1;
x14+x24+x34+x44+x54=1;
@bin(x11);@bin(x21);@bin(x31);@bin(x41);@bin(x51);
@bin(x12);@bin(x22);@bin(x32);@bin(x42);@bin(x52);
@bin(x13);@bin(x23);@bin(x33);@bin(x43);@bin(x53);
@bin(x14);@bin(x24);@bin(x34);@bin(x44);@bin(x54);
答:
均等于1,即,依次取第2个人王、第3个人张、第4个人刘、第1个人李参加蝶泳、仰泳、蛙泳、自由泳,成绩为253.2秒。
再介绍本题的另一个解法:
用遍历法求出最佳组队方案。
从5人中任取4人,随意安排各人的泳姿,则共有5!
=120种方案,取成绩最佳的方案。
Matlab程序为
clear
c=[66.8,75.6,87,58.6;57.2,66,66.4,53;78,67.8,84.6,59.4;70,74.2,69.6,57.2;67.4,71,83.8,62.4];
zxcj=888;
fora1=1:
5
fora2=1:
5
fora3=1:
5
fora4=1:
5
aabb=(a1-a2)*(a1-a3)*(a1-a4)*(a2-a3)*(a2-a4)*(a3-a4);
ifaabb~=0
cj=c(a1,1)+c(a2,2)+c(a3,3)+c(a4,4);
ifcjzxcj=cj;
fa=[a1,a2,a3,a4];
end
end
end
end
end
end
fa,zxcj
执行结果:
fa=2341zxcj=253.2000
二.Lingo中使用集合
前面题3中的Lingo程序,其目标函数含有大规模的变量(20个),约束条件也很繁琐。
现在,利用集合的概念,可使程序大大简化。
例4:
某帆船制造公司要决定下两年八个季度的帆船生产量。
八个季度的帆船需求量分别是40条、60条、75条、25条、30条、65条、50条、20条,这些需求必须按时满足,既不能提前也不能延后。
该公司每季度的正常生产能力是40条帆船,每条帆船的生产费用为400美元。
如果是加班生产的,则每条生产费用为450美元。
帆船跨季度库存的费用为每条20美元。
初始库存是10条帆船。
如何生产?
(注:
本题当然可以用动态规划方法求解;接下来你将看到,建立优化模型用Lingo软件求解比较省事。
)
解:
八个季度的需求量数组记为xuqiu,则xuqiu=[40,60,75,25,30,65,50,20]。
类似地,用数组zhengchang,jiaban,kucun分别表示八个季度的正常生产量、加班生产量、季度末库存量。
目标函数是全部费用之和:
约束条件:
生产能力
;
数量平衡
以上是模型。
怎样用Lingo编程呢?
把下标的范围当作集合,本题的集合是{1,2,3,4,5,6,7,8};定义在集合上的一个个数组,都分别称为该集合的属性,本题这个集合有四个属性,分别是xq,zc,jb,kc.
先看本题的Lingo程序,再看注解:
model:
sets:
jihe/1..8/:
xuqiu,zhengchang,jiaban,kucun;
endsets
data:
xuqiu=40,60,75,25,30,65,50,20;
enddata
min=@sum(jihe:
400*zhengchang+450*jiaban+20*kucun);
@for(jihe:
zhengchang<=40);
kucun
(1)=10+zhengchang
(1)+jiaban
(1)-xuqiu
(1);
@for(jihe(i)|i#gt#1:
end
注解:
(1)一个完整的Lingo程序必然以“model:
”开始,以“end”结束。
(2)集合定义部分(从“sets:
”到“endsets”):
内容是定义集合及其属性,命令格式为“集合名/集合的全部元素/:
全体属性”。
本程序中jihe/1..8/:
xuqiu,zhengchang,jiaban,kucun;,这里的“1..8”等同于“1,2,3,4,5,6,7,8”。
(3)数据输入部分(从“data:
”到“enddata”):
内容是输入已知数据。
(4)其它部分:
包括目标函数、约束条件。
本程序中,@sum(jihe:
400*zhengchang+450*jiaban+20*kucun);是求和函数,
@for(jihe:
zhengchang<=40);是循环函数,zhengchang的所有分量都不大于40,
@for(jihe(i)|i#gt#1:
kucun(i)=kucun(i-1)+zhengchang(i)+jiaban(i)-xuqiu(i));表示对集合jihe中的所有大于1的i,都满足该项约束。
答:
八个季度正常生产量zc=[40,40,40,40,40,40,40,20]
八个季度加班生产jb=[0,10,35,0,0,0,10,0]最小成本为145750.0美元。
练习题:
解线性规划问题。
三.Lingo中的基本集合与派生集合
例5:
料场选址问题
六个建筑工地的位置(用平面坐标a、b表示,距离单位:
km)及其对水泥的日用量(用d表示,单位:
t)由下表给出:
工地的位置(a,b)及水泥日用量d
--------------------------------------------------------------------------------------------------
工地编号123456
a1.258.750.55.7537.25
b1.250.754.7556.57.75
d3547611
--------------------------------------------------------------------------------------------------
现有两个临时料场位于P(5,1),Q(2,7),每日提供水泥的最大能力分别为20t.假设从料场到各工地均有直线道路连接,运输费用与距离、重量成正比。
(1)请制定运输计划,使总运费尽量低。
(2)进一步调整这两个临时料场的位置,使总运费最低。
解:
第i号工地:
位置
,水泥日用量
,i=1,2,3,4,5,6.
第j号料场:
位置
,水泥日供应能力
,j=1,2.
从j号料场向i号工地的日运输水泥量记为
.
注意:
在问题
(1)中,
为已知数据,故决策变量为
,共12个;
在问题
(2)中,
待定,故决策变量为
,共16个。
从j号料场到i号工地,距离为
,送去重量为
的水泥,二者乘积即为运输费。
目标函数:
约束条件:
满足需求:
供应能力:
,j=1,2
非负性:
这就是本题的优化模型。
尝试用Lingo求解该模型时,六个建筑工地作为一个集合gdjh,两个料场作为一个集合lcjh。
接下来就会遇到困难:
决策变量
不仅是依赖于集合gdjh的属性,而且是依赖于集合lcjh的属性,这样的属性应该如何定义呢?
根据两个基本集合gdjh与lcjh构造一个派生集合gdlcjh,再把
定义为这个集合的属性。
先看本题第
(1)问的Lingo程序,再看注解:
model:
sets:
gdjh/1..6/:
a,b,d;
lcjh/1,2/:
x,y,e;
gdlcjh(gdjh,lcjh):
c;
endsets
data:
a=1.25,8.75,0.5,5.75,3,7.25;
b=1.25,0.75,4.75,5,6.5,7.75;
d=3,5,4,7,6,11;
x,y=5,1,2,7;e=20,20;
enddata
min=@sum(gdlcjh(i,j):
c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^0.5);
@for(gdjh(i):
@sum(lcjh(j):
c(i,j))=d(i));
@for(lcjh(j):
@sum(gdjh(i):
c(i,j))<=e(j));
end
注解:
(1)定义派生集合及其属性的命令格式为
派生集合名(基本集合1,基本集合2):
属性
(2)赋值语句“x,y=5,1,2,7”的赋值顺序是“x
(1)=5,y
(1)=1,x
(2)=2,y
(2)=7”,而不是“x
(1),x
(2),y
(1),y
(2)”;在程序中,该语句可换成“x=5,2;y=1,7”,功能相同。
(3)当表达式中出现的下标符号多于1个时,必须指明针对哪个符号做运算。
答:
从1号料场分别向第1、2、4、6号工地运输水泥3571;
从2号料场分别向3、5、6号工地运输水泥4610;
可以使总运输量(质量乘距离)达到最小136.2275(t*km).
再来解决本题第
(2)问,料场位置
也是需要优化的决策变量。
先看Lingo程序,再看注解:
model:
sets:
gdjh/1..6/:
a,b,d;
lcjh/1,2/:
x,y,e;
gdlcjh(gdjh,lcjh):
c;
endsets
data:
a=1.25,8.75,0.5,5.75,3,7.25;
b=1.25,0.75,4.75,5,6.5,7.75;
d=3,5,4,7,6,11;
e=20,20;
enddata
init:
x,y=5,1,2,7;
endinit
min=@sum(gdlcjh(i,j):
c(i,j)*((x(j)-a(i))^2+(y(j)-b(i))^2)^0.5);
@for(gdjh(i):
@sum(lcjh(j):
c(i,j))=d(i));
@for(lcjh(j):
@sum(gdjh(i):
c(i,j))<=e(j));
@for(lcjh:
@free(x);@free(y));
end
注解:
(1)编写Lingo程序时,应尽可能地为决策变量提供初始值,这样可以节省机器工作量。
(2)初始值部分(从“init:
”到“endinit”):
内容是给决策变量赋初值。
本程序中,把原来的料场位置(5,1),(2,7)作为初值。
重新解前面例3之“0----1规划”模型:
(第i名队员的第j种泳姿成绩记为
表示第i名队员参加第j种泳姿比赛)
s.t.
程序如下:
model:
sets:
dyjh/1..5/;
yzjh/1..4/;
cjjh(dyjh,yzjh):
c,x;
endsets
data:
c=66.8,75.6,87,58.6,57.2,66,66.4,53,78,67.8,84.6,59.4,70,74.2,69.6,57.2,67.4,71,83.8,62.4;
enddata
min=@sum(cjjh:
c*x);
@for(dyjh(i):
@sum(yzjh(j):
x(i,j))<=1);
@for(yzjh(j):
@sum(dyjh(i):
x(i,j))=1);
@for(cjjh:
@bin(x));
end
四.稠密集合与稀疏集合
前面例4中,由两个基本集合gdjh与lcjh,构造了一个派生集合gdlcjh,这里gdlcjh的元素定义为gdjh与lcjh的笛卡儿积,即包含了两个基本集合构成的所有二元有序对,这种派生集合称为稠密集合(简称稠集)。
在实际应用中,某些时候,有的属性只在笛卡儿积的一个真子集上定义,而不是在整个稠集上定义。
Lingo允许把一个派生集合定义为笛卡儿积上的真子集,这种派生集合称为稀疏集合(简称疏集)。
例6:
最短路问题
在纵横交错的公路网中,货车司机希望找到一条从一个城市到另一个城市的最短路。
下图标出9个城市:
A1B1C1
SA2B2C2T
A3
城市之间的公路有:
S----A1:
60kmS----A2:
30kmS----A3:
30km
A1----B1:
60kmA1----B2:
50kmA2----B1:
80km
A2----B2:
60kmA3----B1:
70kmA3----B2:
40km
B1----C1:
60kmB1----C2:
70kmB2----C1:
80km
B2----C2:
90kmC1----T:
50kmC2----T:
60km
求从S到T的最短路。
说明:
就这个小题而言,我们很容易用“动态规划”或“图论”的方法求出最短路。
这里的目的不是这个题本身,而是要借用本题介绍“在Lingo中使用稀疏集”。
定义一个集合city,其元素就是这9个城市,从S到每个城市的最短距离定义为该集合的属性,记为
。
先看程序,再看注解:
model:
sets:
city/s,a1,a2,a3,b1,b2,c1,c2,t/:
l;
gljh(city,city)/s,a1s,a2s,a3a1,b1a1,b2a2,b1a2,b2a3,b1a3,b2b1,c1b1,c2b2,c1b2,c2c1,tc2,t/:
d;
endsets
data:
l=0,,,,,,,,;
d=60,30,30,60,50,80,60,70,40,60,70,80,90,50,60;
enddata
@for(city(i)|i#gt#1:
l(i)=@min(gljh(j,i):
l(j)+d(j,i)));
end
注解:
(1)根据基本集合city生成一个派生集合gljh用来表示城市之间的一条条公路,因为并不是每两个城市之间都直接有公路相连(如:
从A2到C1),所以这个派生集合不能定义为稠密集。
本程序中,用枚举法列出了稀疏集gljh的全部15条公路,d是其属性,代表每条公路的长度。
(2)l(i)表示集合city中第i个元素的属性,即从S到第i个城市的最短距离,显然l
(1)=0,而其余的l(i)正是本题所要求的,
。
程序中,对l赋值时,第一个数是0,其余8个未知数必须用逗号给空出来。
(3)Lingo程序中,允许没有目标函数。
此例中,稀疏集的元素是用枚举法给出的,若元素较多,就太麻烦了。
Lingo提供了另一种方法:
“元素过滤”法,能够从稠密集中系统地过滤出部分真正需要的元素构成稀疏集。
请看下面例子。
例7:
现要将8名同学分成4个调查队(每组2人)前往4个地区进行社会调查。
假设他们任意两人组成一队的工作效率为已知,见下表(由于对称性,只须列出上三角部分):
任意两人组成一队的工作效率
学生S1S2S3S4S5S6S7S8
S19342156
S2173521
S344292
S41552
S5876
S623
S74
问如何组队可以使总效率最高?
解:
构造一个效率集合xljh,其属性xl就是上表中那28个数据,如:
xl(S1,S5)=2,xl(S3,S7)=9。
用y(Si,Sj)=1表示Si与Sj组成一个队;用y(Si,Sj)=0表示Si与Sj不是一个队。
目标函数:
约束条件:
每名学生必须且只能参加某一个队,即,对于第k名同学而言,他与其他人所组成的队的个数必须等于1,故有
,k=1,2,3,…,8
另外,
(以上就是本题的优化模型,是“0----1线性规划”)
model:
sets:
xsjh/1..8/;
xljh(xsjh,xsjh)|&2#gt#&1:
xl,y;
endsets
data:
xl=9,3,4,2,1,5,6,1,7,3,5,2,1,4,4,2,9,2,1,5,5,2,8,7,6,2,3,4;
enddata
max=@sum(xljh(i,j):
xl(i,j)*y(i,j));
@for(xsjh(k):
@sum(xljh(i,j)|(i#eq#k)#or#(j#eq#k):
y(i,j))=1);
@for(xljh(i,j):
@bin(y(i,j)));
end
注解:
(1)根据基本集合xsjh构造效率集合xljh时,我们只需要二元对(i,j)中那些当i这里,若你坚持不用“元素过滤”法而用枚举法,则命令为xljh(xsjh,xsjh)/1,21,31,41,51,61,71,82,32,4(太长了,你得把28个下标对一一列出)7,8/:
xl,y;。
(2)过滤命令(i#eq#k)#or#(j#eq#k)表示i=k或j=k.
五.集合的使用小结
1.集合的不同类型及其关系
集合
基本集合派生集合
稠密集合稀疏集合
直接列举法隐式列举法枚举法元素过滤法
2.基本集合的定义格式
(以下命令格式中,凡是在方括号“[]”中的内容,就表示在语法上是可有可无的)
集合名/元素列表/[:
属性列表];
其中:
(1)元素列表可以是直接列举(列出全部元素,元素间用逗号分开),也可以隐式列举;
(2)属性列表可以缺省,缺省时,对应的集合只用来作循环变量或用来做父集合。
3.派生集合的定义格式
(以下命令格式中,凡是在方括号“[]”中的内容,就表示在语法上是可有可无的)
集合名(父集合列表)[/元素列表/][:
属性列表];
其中:
(1)当“/元素列表/”缺省时,表示稠密集合;
(2)元素列表可以是用枚举法或元素过滤法。
六.运算符和函数
1.运算符及其优先级
算术运算符:
(数与数之间的运算,结果还是数)+-*/^.
逻辑运算符:
Lingo中的逻辑运算通常作为过滤条件来使用,分两类
第一类:
#and##or##not#
与或非
(逻辑值与逻辑值之间的运算,结果还是逻辑值)
第二类:
#eq##ne##gt##ge##lt##le#
等于不等于大于大于等于小于小于等于
(数与数之间的运算,结果是逻辑值)
关系运算符:
<=>
小于等于等于大于等于
(Lingo中的关系运算式通常作为约束条件来使用,用来规定数与数之间的大小关系)
优先级:
#not#-(负号)
^
*/
+-
#eq##ne##gt##ge##lt##le#
#and##or#
<=>
2.基本的数学函数(对于给定的数x,可以计算其函数值)
sin(x)cos(x)tan(x)exp(x)log(x)sqrt(x)abs(x)
3.集合循环函数
(下面5个函数,其括号中的格式为集合名:
表达式)
@for()@sum()
@max()@min()@prod()
积
4.变量定界函数
@free(x):
把x放宽为任意实数
@gin(x):
限制x为整数
@bin(x):
限制x只能取0或1
@bnd(-6,x,18):
限制x为闭区间[-6,18]上的任意实数
七.练习题
题1.总运力问题
某卡车公司拨款800万元用于购买新的运输工具,有3种运输工具可供选择:
A的载重量10吨,平均时速45千米,价格26万元;
B的载重量20