数学建模铺路问题最优化模型Word格式.docx
- 文档编号:3655487
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:27
- 大小:23.15KB
数学建模铺路问题最优化模型Word格式.docx
《数学建模铺路问题最优化模型Word格式.docx》由会员分享,可在线阅读,更多相关《数学建模铺路问题最优化模型Word格式.docx(27页珍藏版)》请在冰点文库上搜索。
在给定三种地质条件上每千M的修建费用的情况如下:
地质条件沙土沙石土沙石岩石
费用(万元/千M>
12161828
试解决以下几个问题:
(1>
图中直线AB显然是路径最短的,但不一定最便宜;
而路径ARSB过岩石和沙石的路径最短,但是否是最好的路径呢?
试建立一个数学模型,确定最便宜的管线铺设路
线。
<
若C1=6,C2=4,C3=5,C4=6,C5=5,确定最便宜的管线铺设路线。
)xHAQX74J0X
(2>
铺设管线时,如果要求管线转弯时,角度至少为,确定最便宜的管线铺设路
(3>
铺设管线时,如果要求管线必须通过位于沙石地质带或岩石地质带中的某一已知点P<
位于A地正南面18km和正东30km交汇处)时,确定最便宜的铺设路线。
LDAYtRyKfE
二.模型假设
1、修建费用仅与管线长度和不同地质的造价有关,不含其他费用;
2、在无特殊要求情况下,管线可以向任意方向延伸;
3、不考虑管线宽度;
4、所有管线都铺设在同一水平面上;
2/15
三.符号说明
为修建总费用
为管线与沙土层中东西方向上的投影长度
为管线与沙石层
中东西方向上的投影长度
为管线与岩石层
为管线与沙石土层
中东西方向上的投影长度<
在问题三中指在过
P点的东西方
向的直线上的P点以西的投影长度)
为管线与沙土层
P点的东西方向
的直线上的P点以东的投影长度)
为沙土层每千M的修建费用
为沙石层每千M的修建费用
为岩石层每千M的修建费用
为沙石土层每千M的修建费用
为沙土层每千M的修建费用(在问题三中指在沙石土层每千M的修建费用>
为问题三中沙土层每千M的修建费用
在问题一、二中指沙石土层的宽度,在问题三中指沙石土层P点以上的半层的
宽度
在问题一、二中指沙石土层的宽度,在问题三中指沙石土层P点以下的半层的宽度
问题三中最下面的沙土层的宽度
四.问题分析
3/15
4.1问题一:
本问题主要围绕由A点到B点铺设管线展开,要求花费最少。
根据不同地质条件的花费,确定在某一土层中铺设管线的长度。
我们采用了两种方法求得最少的花费,分别为非线性规划模型和逐点遍历模型。
Zzz6ZB2Ltk
4.1.1方案一
我们首先利用非线性规划求解,可以得出一个关于工程总造价的目标函数f(x>
,
而且可知f(x>
在整个区域连续且可微,f(x>
符合在某一点有局部极小点的条件。
因此我们用迭代法求出极小值<
用Matlab实现),我们分别选用了几组不同的初始值来保证所得到的极小值也是整个区域上的最小值。
dvzfvkwMI1
4.1.2方案二
我们又用穷举法另外建立了一个模型,用来确保模型一的结果是最小值,采用C
语言实现,我们先在每两种不同地质间的交界线上每隔0.1km确定一个点,然后每条
交界线都任取一点,连线,得出一条路径。
之后将每一条可能的路径都遍历一遍,将最小值和对应的点保存,得出结果。
rqyn14ZNXI
4.2问题二
本问题与问题一相比,增加了约束条件“要求管线转弯时,角度至少为”,
我们在问题一所建立的两种模型的基础上均增加相应约束条件,通过求出管线转弯处的管线角度的正切值,并利用反正切函数得出管线角度,从而对管线的铺设方向加以限制,得出最少花费的管线铺设线路。
EmxvxOtOco
4.3问题三
本问题要求铺设管线一定要经过一确定点P,因此可以将此问题分为两步,即从A
到P的路径为第一步,从P到B的路径为第二步。
因为从A到P的路径选择及其花费
与从P到B的路径选择及其花费无关,所以求出第一步从A到P的最优解,以及第二
步求从P到B的最优解,这两的最优解之和便为整个管线铺设的最优解。
SixE2yXPq5
五.模型建立与求解
5.1问题一
5.1.1方案一.
根据题意,在第个土层中的管线长度为
所以,在该层中的修建花费为
则总花费为
4/15
因此得到目标函数
然后所要修建的地区为A地正南面26km和正东40km所表示的区域,在每个土层中管线在东西方向的投影长度应大于0km小于40km,且所有土层中管线在东西方向上的投影长度之和小于40km,因此可确定约束条件:
6ewMyirQFL
运用MATLAB软件编程,得到计算结果为总费用最小为748.6244万元,管线在各土
层中在东西方向上的投影长度分别为15.6786km,3.1827km,2.1839km,
5.8887km,13.0661km。
kavU42VRUs
5.1.2方案二
先在每两种不同土层的交界线上每隔0.1km确定一个点,然后在每条交界线上
都任取一点,并连线,得出一条可能路径。
再将每一条可能的路径按公式y6v3ALoS89
逐一计算花费,找到花费的最小值和其对应的点,确定最优路径。
在此方案中,采
用C语言编程进行遍历,所得最优解为最小花费为748.625602万元,管线在各土
层中在东西方向上的投影长度分别为15.70km,3.20km,2.20km,5.90km,13.00km。
M2ub6vSTnP
5.2问题二
本题也为确定最便宜的管线铺设路线,所以与问题一有相同的目标函数
及约束条件:
。
根据本题中所要求的管线转弯角度大于,利用管线在各土层中在东西方向上
5/15
的投影长度与相应土层宽度得出管线转弯所形成的角的正切值,即,再利用反正切
函数算出具体角度。
由此得到新的约束条件:
0YujCfmUCw
在问题一建立的模型的基础上,依据本题中新增非线性约束条件,建立新的模
型,利用MATLAB编程,所得计算结果为最小花费为750.6084万元,管线在各土层中在东西方向上的投影长度分别为14.4566km,4.3591km,2.5984km,6.5387km,12.0472km。
eUts8ZQVRd
利用相同的约束条件,利用C语言编程遍历,所得最优解为最小花费为
750.821154万元,管线在各土层中在东西方向上的投影长度分别为
14.10km,4.30km,2.70km,6.70km,12.20km。
sQsAEJkW5T
5.3问题三
根据本题中管线必须通过已知点P<
位于A地正南面18km和正东30km交汇处)的约束条件,我们将整个区域依据P点位置分成两部分,即以A点正东30km处为界,将
沙土层分成两部分,使整个修建区域变成6个土层。
在问题一所建立的模型上加以改进,使目标函数变为:
GMsIasNXkA
并将约束条件改为:
利用非线性规划模型,MATLAB编程,所得最优解为:
最小花费为752.6432万元,管线在各土层中在东西方向上的投影长度分别为
21.2613km,3.3459km,2.2639km,TIrRGchYzg
3.1288km,2.4102km,7.5898km
利用遍历模型,C语言编程,所得最优解为:
最小花费为
752.649007万元,管线
在各土层中在东西方向上的投影长度分别为21.30km,3.30km,2.30km,3.10km,2.40km,7EqZcWLZNX
6/15
7.60km。
六.模型的评价与改进
对于模型一,存在的缺点是用Matlab中的fmincon函数所求最优解可能只是局部最优解,必须代入几组不同的初始迭代值,来确定所求解为全局最优解,但仍有可能
遗漏。
对于模型二,缺点是精度不够小,当精度取到0.1时,计算机要用几分钟才能得出结果,精度更小时所需时间更长,而且在问题二中,模型二因为精度太低而跳过
了最优路径,所以与模型一所得结果有一定差距。
但模型二的结果可用于检验模型一所得结果是否为最优解。
lzq7IGf02E
七.参考文献
[1]曹卫华郭正,最优化设计方法及MATLAB的实现,北京:
化学工业出版社,
2005.
[2]孙辉吴润秀,C语言程序设计,北京:
中国铁道出版社,2007.
[3]李尚志,数学建模竞赛教程,南京:
江苏教育出版社,1996.
[4]何文章,大学数学实验,哈尔滨:
哈尔滨工程大学出版社,2000.
[5]边馥萍,数学模型方法与算法,北京:
高等教育出版社,2005.
[6]姜启源,数学模型,北京:
高等教育出版社,1993.
附件
附件一:
问题一的Matlab语言源代码:
先建立目标函数的M文件:
functionf=fun(x>
。
f=12*sqrt(x(1>
^2+36>
+18*sqrt(x(2>
^2+16>
+28*sqrt(x(3>
^2+25>
+16*sqrt(x(4>
^2
+36>
+12*sqrt(x(5>
zvpgeqJ1hk
主程序:
x0=[0。
0。
0]。
A=[10000。
01000
00100。
00010。
00001]。
NrpoJac3v1
b=[4040404040]。
Aeq=[11111]。
beq=[40]。
[x,z]=fmincon('
fun'
x0,A,b,Aeq,beq>
运算结果:
x=
15.6786
7/15
3.1827
2.1839
5.8887
13.0661
z=
748.6244
附件二:
问题一的C语言源代码:
#include<
stdio.h>
math.h>
#defineJD0.1//取精度为0.1
main(>
{
doublex[6]={0,0,0,0,0,40},s=0,min=100000,best[5]。
//s用来
临时保存每一条路径的价格,x用来临时保存每一条路径1nowfTG4KI
inti,j,k,l,n,c[5]={6,4,5,6,5},p[5]={12,18,28,16,12},D。
//min用来
记录最小价格,best用来记录最佳路径fjnFLDa5Zo
D=40/JD。
//D为每一条交界线上可分的段数
for(i=0。
i<
D。
i++>
//用五个循环对每一条可能的路径进行遍历
for(j=i。
j<
j++>
for(k=j。
k<
k++>
for(l=k。
l<
l++>
for(n=1。
n<
6。
n++>
s+=sqrt((x[n]-x[n-
1]>
*(x[n]-x[n-1]>
+c[n-1]*c[n-1]>
*p[n-1]。
tfnNhnE6e5
}
if(s<
min>
//如果s比上一
次最小的价格更小,
{//
则将其存在min中,同时路径保存
min=s。
//
8/15
在best中。
for(n=0。
5。
best[n]=x[n]。
s=0。
x[4]+=JD。
x[3]+=JD。
x[4]=x[3]。
x[2]+=JD。
x[3]=x[2]。
x[1]+=JD。
x[2]=x[1]。
printf("
最少花费为%f\n"
min>
for(i=0。
i<
5。
在第%d条交界线上的位置为%f\n"
i,best[i]>
最少花费为748.625602
在第0条交界线上的位置为0.000000
在第1条交界线上的位置为15.700000
在第2条交界线上的位置为18.900000
在第3条交界线上的位置为21.100000
在第4条交界线上的位置为27.000000
附件三:
问题二的Matlab语言源代码:
HbmVN777sL
然后建立非线性约束条件的M文件:
function[c,ceq]=mycon(x>
c(1>
=pi*70/180-pi*0.5+atan(x(1>
/6>
-atan(x(2>
/4>
c(2>
=pi*70/180-pi*0.5+atan(x(2>
-atan(x(3>
/5>
c(3>
=pi*70/180-pi*0.5+atan(x(3>
-atan(x(4>
c(4>
=pi*70/180-pi*0.5+atan(x(4>
-atan(x(5>
c(5>
=pi*0.5-atan(x(1>
+atan(x(2>
-pi*110/180。
c(6>
=pi*0.5-atan(x(2>
+atan(x(3>
9/15
c(7>
=pi*0.5-atan(x(3>
+atan(x(4>
c(8>
=pi*0.5-atan(x(4>
+atan(x(5>
ceq=[]。
x0=[0.1。
0.1。
0.1。
0.1]。
A=[10000。
01000。
V7l4jRB8Hs
b=[40,40,40,40,40]。
x0,A,b,Aeq,beq,[],[],'
mycon'
>
14.4566
4.3591
2.5984
6.5387
12.0472
750.6084
附件四
问题二的C语言源代码:
inttj(doublea,doubleb,doublec1,doubled,doublee>
//满足转弯处至少
为160度的条件83lcPA59W9
intn,f,c[5]={6,4,5,6,5}。
doublex[6]={0,a,b,c1,d,e}。
n<
if(3.1416*0.5-atan((x[n]-x[n-1]>
/c[n-
+atan((x[n+1]-x[n]>
/c[n]>
=1.221731&
&
3.1416*0.5-atan((x[n]-x[n-
/c[n-1]>
<
=1.919863>
mZkklkzaaPf=1。
else
return0。
returnf。
10/15
//s用来临时保存
每一条路径的价格,x用来临时保存每一条路径AVktR43bpw
记录最小价格,best用来记录最佳路径ORjBnOwcEd
s+=sqrt((x[n]-x[n-1]>
+c[n-1]*c[n-
2MiJTy0dTT
min&
tj(x[1],x[2],x[3],x[4],x[5]>
如果s比上一次最小的价
格更小,
gIiSpiue7A
//且满足转弯处
不小于160度的条件,
//则将其
存在min中,同时路径保存
//在best中。
best[n]=x[n]
11/15
最少花费为750.821154
在第1条交界线上的位置为14.100000
在第2条交界线上的位置为18.400000
在第4条交界线上的位置为27.800000
附件五:
问题三的Matlab
语言源代码:
先建立目标函数的
M文件:
functionf=fun3(x>
+9>
+16*sqrt(x(5>
^2+9>
+12*sqrt(x(6>
uEh0U1Yfmh
A=[100000。
010000。
001000
000100。
000010。
000
001]。
IAg9qLsgBX
b=[303030301010]
Aeq=[111100
000011]。
beq=[30。
10]。
fun3'
21.2613
3.3459
2.2639
3.1288
2.4102
7.5898
752.6432
12/15
附件六:
问题三的C语言源代码:
#defineJD0.1//取精度为0
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 铺路 问题 优化 模型