数学建模--运输问题
运输问题
摘要
本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo 编程求解出最终结果。
关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。
关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。
关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。
关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。
关键词： Floyd算法 Kruskal算法整数规划旅行商问题
一、问题重述
某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i 个客户到第j 个客户的路线距离（单位公里）用下面矩阵中的(,)i j (,1,,10)i j =位置上的数表示（其中∞表示两个客户之间无直接的路线到达）。
1
234567891010
5040253050250
03035506033001530502560440
1504530552040655251545060103055650303060025553573050102503045608602520305530010920401525450201035201045206030
0∞∞∞∞??∞∞∞∞??∞∞∞?∞??∞∞?∞
∞??∞∞?∞
∞?∞∞∞∞∞????????????????????
1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。
2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。
3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析。
4、如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用），请问如何安排车辆才能使得运输公司运货的总费用最省？
二、问题分析
关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd 算法对
其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab 软件对其进行编程求解。
关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际
上是寻找一条最短的行车路线。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal 算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：21098436751v v v v v v v v v v →→→→→→→→→；然后利用问题一的Floyd 算法和程序，能求得从客户2到客户1（提货点）的最短路线是：12v v →，路程为50公里。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文又根据路程最短建立以路程最短为目标函数的整数规划模型；最后，利用LINGO 软件对其进行编程求解。
关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。
这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal 算法结合题中所给的邻接矩阵进行优化。
关于问题四，我们首先用Matlab 软件编程确定提货点到每个客户点间的最
短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。
三、模型假设
1.假设客户级别平等；
2.假设不考虑装卸车费用；
3.假设货车不发生意外事故；
4.假设运输过程中货物无损失；
四、符号说明
:ij v 不同的客户102.1;102.1 ==j i ；
:ij l 从客户i v 到客户j v 的距离；
???=；个客户无直接的路到达
个客户到第从第：；个客户有直接的路到达个客户到第从第：j i j i x ij 01 个客户的距离个客户到第从第j i c ij :；
个客户所需的货物量第j a j :；
:z 总路程；
五、模型的建立与求解
5.1问题一模型的建立与求解
5.1.1模型的建立
问题一是要找出从客户2到客户10的最短路径，本文利用Floyd 算法对此
文进行求解。
为计算方便，令网络的权矩阵为j i ij n n ij v v l d D 到为,)(?=的距离。
???∞∈=其他
）当（其中
E v v l d j i ij ij , Floyd 算法基本步骤为： （1）输入权矩阵D D =)0(。
（2）计算),,3,2,1()()()(n k d D n n k ij k ==?
其中 ],min[)1(
)1()1()(---+=k jk k ik k ij k ij d d d d
（3）n n n ij n d D ?=)()()(中元素)(n ij
d 就是i v 到j v 的最短路长。 5.1.2模型的求解
在本文计算中10=n ，对Floyd 算法进行编程（程序见附录1），利用Matlab
软件进行求解。运行结果如下：
a =
0 40 55 40 25 55 30 55 50 70
50 0 30 45 35 50 45 55 65 85
55 30 0 15 55 30 50 25 35 55
40 45 15 0 45 30 50 20 30 50
25 15 45 45 0 35 10 30 40 55
55 50 30 30 35 0 25 50 35 55
30 25 50 50 10 25 0 30 40 60
30 45 25 20 30 25 30 0 10 30
20 40 30 40 35 15 25 45 0 20
35 20 10 25 20 40 30 35 30 0
path =
1 5 4 4 5 7 7 5 9 9
1 2 3 3 5 6 5 3 3 3
4 2 3 4 8 6 7 8 8 8
1 3 3 4 5 6 8 8 8 8
1 2 2 4 5 7 7 8 8 10
7 2 3 4 7 6 7 4 9 9
1 5 3 8 5 6 7 8 8 10
9 5 3 4 5 9 7 8 9 9
1 10 10 4 7 6 7 8 9 10
1 2 3 3 5 3 5 3 9 10
请输入起点2
请输入终点10
2
3
8
9
10
由运行结果可以得出运货员从客户2到客户10的最短路径是：
109832v v v v v →→→→
总路程为85公里。
5.2问题二模型的建立与求解
5.2.1模型的建立
运输公司为这10个客户配送货物问题实际上是寻找一条最短的行车路线。
当不考虑送货员返回提货点的时候，本文利用最小生成树问题中的Kruskal 算法结合题中所给的邻接矩阵，很快可以得到无回路的最短路线。
Kruskal 算法基本步骤：
每步从未选的边中选取边e ，使它与已选边不够成圈，且e 是未选边中的最
小权边，知道选够1-n 条边为止。
利用最小生成树问题中的Kruskal 算法结合题中所给的邻接矩阵，很快可以得到以下最小生成树：
21098436751v v v v v v v v v v →→→→→→→→→
这两棵生成树不同之处就在于从客户6到达客户8的路径不一样，而实际路程经过计算后是一样的，路线的总行程为175公里。利用问题一的Floyd 算法和程序，能求得从客户2到客户1（提货点）的最短路线是12v v →，路程为50公里。
这样该回路，即最短的行车路线为：
121098436751v v v v v v v v v v v →→→→→→→→→→
行车路线总行程为225公里。
以最小生成树法解决此问题速度快，结果较精确，但是只适合数目较少时，不适宜推广，因此本文又根据路程最短建立整数规划模型。
为了更好的防止子巡回的产生，根据哈米尔顿回路，须附加一个约束条件：
n j i n x n u u ij j i ≤≠≤-≤+-2,1
当访问客户i 后必须要有一个即将访问的确切客户；访问客户j 前必须要有
一个刚刚访问过的确切客户。依次设立约束条件。
()
()()()()
???????
????????=≥≤≠≤-≤*+-=====*=∑∑∑∑====10,,2,1021
1,01010,,2,1110,,2,11.min :10110
110110
1 i u n j i n Xi n u u X j X i X t s X C Z i j j i ij
i ij j ij i j ij
ij 变量或目标函数
5.2.2模型的求解
利用Lingo 求解模型部分结果（附录2）：
Global optimal solution found. Objective value: 225.0000
Objective bound: 225.0000
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 86
Variable Value Reduced Cost X( 1, 5) 1.000000 25.00000
X( 2, 1) 1.000000 50.00000
X( 3, 4) 1.000000 15.00000
X( 4, 8) 1.000000 20.00000
X( 5, 7) 1.000000 10.00000
X( 6, 3) 1.000000 30.00000
X( 7, 6) 1.000000 25.00000
X( 8, 9) 1.000000 10.00000
X( 9, 10) 1.000000 20.00000
X( 10, 2) 1.000000 20.00000
由此可得，行程路线最短的回路：
121098436751v v v v v v v v v v v →→→→→→→→→→
总路程为225公里。
5.3问题三模型的建立与求解
5.3.1模型的建立
用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户
总需求量在50个单位以内。此问与问题二有相似之处都要考虑回到提货点的情形,因此本文在模型2的基础上进行改进, 重新建立相应的整数线性规划模型。
目标函数：101011min ij ij i j z c
x ===?∑∑
.s t 10
1
10
1
i j ij 1010111010221
(1,210)1
(1,210)01u -u +n x 136501,1,ij i ij j ij ij ij i j ij ij j i x j x i x n x a x x -=====?≤=???≤=???=???≤-?
?≤?≤?
?
??==??
∑∑∑∑∑∑或 5.3.2模型的求解
利用Lingo 求解模型部分结果（附录3）：
Global optimal solution found.
Objective value: 155.0000
Objective bound: 155.0000
Infeasibilities: 0.2220446E-15
Extended solver steps: 0
Total solver iterations: 224
Variable Value Reduced Cost X( 1, 5) 1.000000 25.00000 X( 2, 3) 1.000000 30.00000
X( 3, 6) 1.000000 30.00000
X( 5, 2) 1.000000 15.00000
X( 6, 7) 1.000000 25.00000
X( 7, 1) 1.000000 30.00000
Global optimal solution found.
Objective value: 135.0000
Objective bound: 135.0000
Infeasibilities: 0.2220446E-15
Extended solver steps: 0
Total solver iterations: 224
Variable Value Reduced Cost X( 1, 4) 1.000000 40.00000
X( 4, 8) 1.000000 20.00000
X( 5, 1) 1.000000 25.00000 X( 8, 9) 1.000000 10.00000 X( 9, 10) 1.000000 20.00000
X( 10, 5) 1.000000 20.00000
由此可得，两辆车的行车路线及路程：
第一辆车：1763251v v v v v v v →→→→→→，包含的客户有2,3,6,7，运货总量为44，路程为155公里。
第二辆车：15109841v v v v v v v →→→→→→，包含的客户有4,8，9,10,5运货总量为42单位，路程为135公里。总路程为290公里。
5.3.3模型的优化
对于模型求解出来的结果，本文利用Kruskal 算法结合题中所给的邻接矩阵进行优化。
从起始点1v 处，进行分析，用两辆小的货车配送货物，为了尽可能的减少两辆车的重复路线， 1v 到5v 、7v 的路程最短，让两辆车分开运货，先根据货物承载量50的限制让其中的一辆车走完路程，再让另一辆车走剩余城市的最短路线，这样走出两条运货路线：
第一种情况：
第一辆车：15234891v v v v v v v v ??
→??→??→??→??→??→??→，包含的客户有5,2,3,4,8，从模型1可解得，从8v 回到1v 的最短路线是198v v v →→，运货总量为40单位，路程为145公里。
第二辆车：176910v v v v v v ??→??→??→??→??→，包
含的客户有7,6,9,10，运货总量为46，路程为135公里。这种情况下总路程为280公里。 第二种情况：
第一辆车：17634891v v v v v v v v ??
→??→??→??→??→??→??→，包含的客户有7,6,3,4,8，从模型1可解得，从8v 回到1v 的最短路线是198v v v →→，运货总量为45单位，路程为150公里。
第二辆车：152389101v v v v v v v v ??
→??→??→??→??→??→??→，包含的客户5,2,9,10，运货总量为41单位，路程为160。这种情况下总路程为310公里。 对这两种情况对比，分析，可以看出第一种情况优于第二种情况。因此选择第一种情况的路线。
5.4问题四模型的建立与求解
题目要求我们运费最省，所以要考虑到需要的车最少，以及每辆车行驶的路程最短，而且还要保证送到每个客户手中。根据客户总需求量和货车的容量，所以，公司可派4辆货车去送货。在此，我们假设：
从提货点1到各客户点最短路为j p 1)103,2( =j
从提货点1到各客户点的最短路程)103,2(1 =j L j
提货点1到各客户点路径客户所需要货物量的总和)103,2(1 =j G j
运用matlab 程序（见附录4）可得：
1091:91:851:71:6
71:51:4
1:3
41:2
51:1101918171615141312--------------p p p p p p p p p
从中可以发现：251≤j G ，所以我们要继续对其进行分析：
首先为了保证送到每个客户手里，所以必须走11016p p 和，那样就可以删除1917p p 和；然后考虑到货车的路程最短，所以要走12p ，删除1815p p 和；最后，就只能走1-4-3-8路线。
图1 四辆货车路线图
经过计算可得下表： 表1：4辆车的情况表
每辆车的路线 每辆车的路程 每辆车所载的货物量
1-5-2 40 20
1-4-3-8 80 20
1-7-6 55 25
1-9-10 70 21
所以，可得到目标函数：
j L z 1*1100*4min +=
645)70558040(*1100*4min =++++=z
六、模型的评价与推广
6.1模型的评价
6.1.1模型的优点
（1）在整个模型的建立过程中，本文考虑的比较全面客观，使模型具有较强的说服力，结果更合理。
（2）根据问题的特点，综合运用了多个软件，如lingo 、matlab 等等，使得在解决问题的过程中，更方便简单。
6.1.2模型的缺点
这种寻路方法有其局限性，只适用于一些顶点较少的情况，顶点多，寻找起来较为麻烦。
6.2模型的推广
模型的建立比较客观，在现实中也可以广泛的应用，与现实情况紧密相连；比如：最优路径问题与哈密顿回路问题，这些在现实中应用范围已经很广了。
七、参考文献
[1] 胡运权，运筹学教程第四版，北京：清华大学出版社，2012。
[2] 朱道元，数学建模案例精选，北京：科学出版社，2005。
[3] 姜启源，谢金星。叶俊．数学模型北京：高等教育出版杜，2004。 I4] 吴祈宗．运筹学与最优化方法fM ．北京：机械工业出版社，2003。
附录
附录1：
clear;
clc;
M=10000;%不能直接到达是将距离赋值给M
a(1,:)=[0,50,M,40,25,M,30,M,50,M];
a(2,:)=[50,0,30,M,35,50,M,60,M,M];
a(3,:)=[M,30,0,15,M,30,50,25,M,60];
a(4,:)=[40,M,15,0,45,30,55,20,40,65];
a(5,:)=[25,15,M,45,0,60,10,30,M,55];
a(6,:)=[M,50,30,30,60,0,25,55,35,M];
a(7,:)=[30,M,50,M,10,25,0,30,45,60];
a(8,:)=[M,60,25,20,30,55,30,0,10,M];
a(9,:)=[20,M,M,40,M,15,25,45,0,20];
a(10,:)=[35,20,10,45,20,M,60,M,30,0];%建立a 矩阵
path=zeros(length(a)); %建立一个与矩阵a 同大小的全零矩阵
for i=1:10
for j=1:10
path(i,j)=j; %用path矩阵记录走过的点
end
end
for k=1:10
for i=1:10
for j=1:10
if a(i,j)>a(i,k)+a(k,j)
a(i,j)=a(i,k)+a(k,j);
path(i,j)=path(i,k); % floyd算法
end
end
end
end
a, path
i1=input('请输入起点');
i2=input('请输入终点');
disp(i1);
while i1~=i2
i1=path(i1,i2);
disp(i1);
end;
附录2：
MODEL:
SETS:
CUSTOMERS / 1.. 10/: U;
LINK( CUSTOMERS, CUSTOMERS):
DIST,X;
ENDSETS
DATA:
DIST =
0 50 100000 40 25 100000 30 100000 50 100000
50 0 30 100000 35 50 100000 60 10000 100000
100000 30 0 15 100000 30 50 25 100000 60
40 10000 15 0 45 30 55 20 40 65
25 15 100000 45 0 60 10 30 100000 55
100000 50 30 30 60 0 25 55 35 1000000
30 100000 50 100000 10 25 0 30 45 60
100000 60 25 20 30 55 30 0 10 100000
20 100000 100000 40 100000 15 25 45 0 20
35 20 10 45 20 100000 60 100000 30 0;
ENDDATA
N = @SIZE( CUSTOMERS);
MIN = @SUM( LINK: DIST * X);
@FOR( CUSTOMERS( K):
@SUM( CUSTOMERS( I)| I #NE# K: X( I, K)) = 1;
@SUM( CUSTOMERS( J)| J #NE# K: X( K, J)) = 1;
@FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) >= U( K) + X ( K, J) -
( N - 2) * ( 1 - X( K, J)) +
( N - 3) * X( J, K)
);
);
@FOR( LINK: @BIN( X));
@FOR( CUSTOMERS( K)| K #GT# 1:
U( K) <= N - 1 - ( N - 2) * X( 1, K);
U( K) >= 1 + ( N - 2) * X( K, 1)
);
END
Global optimal solution found.
Objective value: 225.0000
Objective bound: 225.0000
Infeasibilities: 0.000000
Extended solver steps: 0
Total solver iterations: 86
Variable Value Reduced Cost N 10.00000 0.000000 U( 1) 0.000000 0.000000 U( 2) 9.000000 0.000000 U( 3) 4.000000 0.000000 U( 4) 5.000000 0.000000 U( 5) 1.000000 0.000000 U( 6) 3.000000 0.000000 U( 7) 2.000000 0.000000 U( 8) 6.000000 0.000000 U( 9) 7.000000 0.000000 U( 10) 8.000000 0.000000 DIST( 1, 1) 0.000000 0.000000 DIST( 1, 2) 50.00000 0.000000 DIST( 1, 3) 100000.0 0.000000 DIST( 1, 4) 40.00000 0.000000 DIST( 1, 5) 25.00000 0.000000 DIST( 1, 6) 100000.0 0.000000
DIST( 1, 8) 100000.0 0.000000 DIST( 1, 9) 50.00000 0.000000 DIST( 1, 10) 100000.0 0.000000 DIST( 2, 1) 50.00000 0.000000 DIST( 2, 2) 0.000000 0.000000 DIST( 2, 3) 30.00000 0.000000 DIST( 2, 4) 100000.0 0.000000 DIST( 2, 5) 35.00000 0.000000 DIST( 2, 6) 50.00000 0.000000 DIST( 2, 7) 100000.0 0.000000 DIST( 2, 8) 60.00000 0.000000 DIST( 2, 9) 10000.00 0.000000 DIST( 2, 10) 100000.0 0.000000 DIST( 3, 1) 100000.0 0.000000 DIST( 3, 2) 30.00000 0.000000 DIST( 3, 3) 0.000000 0.000000 DIST( 3, 4) 15.00000 0.000000 DIST( 3, 5) 100000.0 0.000000 DIST( 3, 6) 30.00000 0.000000 DIST( 3, 7) 50.00000 0.000000 DIST( 3, 8) 25.00000 0.000000 DIST( 3, 9) 100000.0 0.000000 DIST( 3, 10) 60.00000 0.000000 DIST( 4, 1) 40.00000 0.000000 DIST( 4, 2) 10000.00 0.000000 DIST( 4, 3) 15.00000 0.000000 DIST( 4, 4) 0.000000 0.000000 DIST( 4, 5) 45.00000 0.000000 DIST( 4, 6) 30.00000 0.000000 DIST( 4, 7) 55.00000 0.000000 DIST( 4, 8) 20.00000 0.000000 DIST( 4, 9) 40.00000 0.000000 DIST( 4, 10) 65.00000 0.000000 DIST( 5, 1) 25.00000 0.000000 DIST( 5, 2) 15.00000 0.000000 DIST( 5, 3) 100000.0 0.000000 DIST( 5, 4) 45.00000 0.000000 DIST( 5, 5) 0.000000 0.000000 DIST( 5, 6) 60.00000 0.000000 DIST( 5, 7) 10.00000 0.000000 DIST( 5, 8) 30.00000 0.000000 DIST( 5, 9) 100000.0 0.000000 DIST( 5, 10) 55.00000 0.000000
DIST( 6, 2) 50.00000 0.000000 DIST( 6, 3) 30.00000 0.000000 DIST( 6, 4) 30.00000 0.000000 DIST( 6, 5) 60.00000 0.000000 DIST( 6, 6) 0.000000 0.000000 DIST( 6, 7) 25.00000 0.000000 DIST( 6, 8) 55.00000 0.000000 DIST( 6, 9) 35.00000 0.000000 DIST( 6, 10) 1000000. 0.000000 DIST( 7, 1) 30.00000 0.000000 DIST( 7, 2) 100000.0 0.000000 DIST( 7, 3) 50.00000 0.000000 DIST( 7, 4) 100000.0 0.000000 DIST( 7, 5) 10.00000 0.000000 DIST( 7, 6) 25.00000 0.000000 DIST( 7, 7) 0.000000 0.000000 DIST( 7, 8) 30.00000 0.000000 DIST( 7, 9) 45.00000 0.000000 DIST( 7, 10) 60.00000 0.000000 DIST( 8, 1) 100000.0 0.000000 DIST( 8, 2) 60.00000 0.000000 DIST( 8, 3) 25.00000 0.000000 DIST( 8, 4) 20.00000 0.000000 DIST( 8, 5) 30.00000 0.000000 DIST( 8, 6) 55.00000 0.000000 DIST( 8, 7) 30.00000 0.000000 DIST( 8, 8) 0.000000 0.000000 DIST( 8, 9) 10.00000 0.000000 DIST( 8, 10) 100000.0 0.000000 DIST( 9, 1) 20.00000 0.000000 DIST( 9, 2) 100000.0 0.000000 DIST( 9, 3) 100000.0 0.000000 DIST( 9, 4) 40.00000 0.000000 DIST( 9, 5) 100000.0 0.000000 DIST( 9, 6) 15.00000 0.000000 DIST( 9, 7) 25.00000 0.000000 DIST( 9, 8) 45.00000 0.000000 DIST( 9, 9) 0.000000 0.000000 DIST( 9, 10) 20.00000 0.000000 DIST( 10, 1) 35.00000 0.000000 DIST( 10, 2) 20.00000 0.000000 DIST( 10, 3) 10.00000 0.000000 DIST( 10, 4) 45.00000 0.000000
DIST( 10, 6) 100000.0 0.000000 DIST( 10, 7) 60.00000 0.000000 DIST( 10, 8) 100000.0 0.000000 DIST( 10, 9) 30.00000 0.000000 DIST( 10, 10) 0.000000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 50.00000 X( 1, 3) 0.000000 100000.0 X( 1, 4) 0.000000 40.00000 X( 1, 5) 1.000000 25.00000 X( 1, 6) 0.000000 100000.0 X( 1, 7) 0.000000 30.00000 X( 1, 8) 0.000000 100000.0 X( 1, 9) 0.000000 50.00000 X( 1, 10) 0.000000 100000.0 X( 2, 1) 1.000000 50.00000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 30.00000 X( 2, 4) 0.000000 100000.0 X( 2, 5) 0.000000 35.00000 X( 2, 6) 0.000000 50.00000 X( 2, 7) 0.000000 100000.0 X( 2, 8) 0.000000 60.00000 X( 2, 9) 0.000000 10000.00 X( 2, 10) 0.000000 100000.0 X( 3, 1) 0.000000 100000.0 X( 3, 2) 0.000000 30.00000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 1.000000 15.00000 X( 3, 5) 0.000000 100000.0 X( 3, 6) 0.000000 30.00000 X( 3, 7) 0.000000 50.00000 X( 3, 8) 0.000000 25.00000 X( 3, 9) 0.000000 100000.0 X( 3, 10) 0.000000 60.00000 X( 4, 1) 0.000000 40.00000 X( 4, 2) 0.000000 10000.00 X( 4, 3) 0.000000 15.00000 X( 4, 4) 0.000000 0.000000 X( 4, 5) 0.000000 45.00000 X( 4, 6) 0.000000 30.00000 X( 4, 7) 0.000000 55.00000 X( 4, 8) 1.000000 20.00000
X( 4, 10) 0.000000 65.00000 X( 5, 1) 0.000000 25.00000 X( 5, 2) 0.000000 15.00000 X( 5, 3) 0.000000 100000.0 X( 5, 4) 0.000000 45.00000 X( 5, 5) 0.000000 0.000000 X( 5, 6) 0.000000 60.00000 X( 5, 7) 1.000000 10.00000 X( 5, 8) 0.000000 30.00000 X( 5, 9) 0.000000 100000.0 X( 5, 10) 0.000000 55.00000 X( 6, 1) 0.000000 100000.0 X( 6, 2) 0.000000 50.00000 X( 6, 3) 1.000000 30.00000 X( 6, 4) 0.000000 30.00000 X( 6, 5) 0.000000 60.00000 X( 6, 6) 0.000000 0.000000 X( 6, 7) 0.000000 25.00000 X( 6, 8) 0.000000 55.00000 X( 6, 9) 0.000000 35.00000 X( 6, 10) 0.000000 1000000. X( 7, 1) 0.000000 30.00000 X( 7, 2) 0.000000 100000.0 X( 7, 3) 0.000000 50.00000 X( 7, 4) 0.000000 100000.0 X( 7, 5) 0.000000 10.00000 X( 7, 6) 1.000000 25.00000 X( 7, 7) 0.000000 0.000000 X( 7, 8) 0.000000 30.00000 X( 7, 9) 0.000000 45.00000 X( 7, 10) 0.000000 60.00000 X( 8, 1) 0.000000 100000.0 X( 8, 2) 0.000000 60.00000 X( 8, 3) 0.000000 25.00000 X( 8, 4) 0.000000 20.00000 X( 8, 5) 0.000000 30.00000 X( 8, 6) 0.000000 55.00000 X( 8, 7) 0.000000 30.00000 X( 8, 8) 0.000000 0.000000 X( 8, 9) 1.000000 10.00000 X( 8, 10) 0.000000 100000.0 X( 9, 1) 0.000000 20.00000 X( 9, 2) 0.000000 100000.0
X( 9, 4) 0.000000 40.00000 X( 9, 5) 0.000000 100000.0 X( 9, 6) 0.000000 15.00000 X( 9, 7) 0.000000 25.00000 X( 9, 8) 0.000000 45.00000 X( 9, 9) 0.000000 0.000000 X( 9, 10) 1.000000 20.00000 X( 10, 1) 0.000000 35.00000 X( 10, 2) 1.000000 20.00000 X( 10, 3) 0.000000 10.00000 X( 10, 4) 0.000000 45.00000 X( 10, 5) 0.000000 20.00000 X( 10, 6) 0.000000 100000.0 X( 10, 7) 0.000000 60.00000 X( 10, 8) 0.000000 100000.0 X( 10, 9) 0.000000 30.00000 X( 10, 10) 0.000000 0.000000
Row Slack or Surplus Dual Price
1 0.000000 0.000000
2 225.0000 -1.000000
3 0.000000 0.000000
4 0.000000 0.000000
5 10.00000 0.000000
6 12.00000 0.000000
7 13.00000 0.000000
8 0.000000 0.000000
9 11.00000 0.000000
10 10.00000 0.000000
11 14.00000 0.000000
12 15.00000 0.000000
13 16.00000 0.000000
14 0.000000 0.000000
15 0.000000 0.000000
16 3.000000 0.000000
17 4.000000 0.000000
18 0.000000 0.000000
19 2.000000 0.000000
20 1.000000 0.000000
21 5.000000 0.000000
22 6.000000 0.000000
23 0.000000 0.000000
24 0.000000 0.000000
26 13.00000 0.000000
27 0.000000 0.000000
28 5.000000 0.000000
29 0.000000 0.000000
30 6.000000 0.000000
31 10.00000 0.000000
32 11.00000 0.000000
33 12.00000 0.000000
34 0.000000 0.000000
35 0.000000 0.000000
36 12.00000 0.000000
37 0.000000 0.000000
38 4.000000 0.000000
39 6.000000 0.000000
40 5.000000 0.000000
41 0.000000 0.000000
42 10.00000 0.000000
43 11.00000 0.000000
44 0.000000 0.000000
45 0.000000 0.000000
46 16.00000 0.000000
47 11.00000 0.000000
48 12.00000 0.000000
49 10.00000 0.000000
50 0.000000 0.000000
51 13.00000 0.000000
52 14.00000 0.000000
53 15.00000 0.000000
54 0.000000 0.000000
55 0.000000 0.000000
56 14.00000 0.000000
57 0.000000 0.000000
58 10.00000 0.000000
59 6.000000 0.000000
60 0.000000 0.000000
61 11.00000 0.000000
62 12.00000 0.000000
63 13.00000 0.000000
64 0.000000 0.000000
65 0.000000 0.000000
66 15.00000 0.000000
67 10.00000 0.000000
68 11.00000 0.000000
70 0.000000 0.000000
71 12.00000 0.000000
72 13.00000 0.000000
73 14.00000 0.000000
74 0.000000 0.000000
75 0.000000 0.000000
76 11.00000 0.000000
77 6.000000 0.000000
78 0.000000 0.000000
79 3.000000 0.000000
80 5.000000 0.000000
81 4.000000 0.000000
82 0.000000 0.000000
83 10.00000 0.000000
84 0.000000 0.000000
85 0.000000 0.000000
86 10.00000 0.000000
87 5.000000 0.000000
88 6.000000 0.000000
89 2.000000 0.000000
90 4.000000 0.000000
91 3.000000 0.000000
92 0.000000 0.000000
93 0.000000 0.000000
94 0.000000 0.000000
95 0.000000 0.000000
96 0.000000 0.000000
97 4.000000 0.000000
98 5.000000 0.000000
99 1.000000 0.000000 100 3.000000 0.000000 101 2.000000 0.000000 102 6.000000 0.000000 103 0.000000 0.000000 104 0.000000 0.000000 105 0.000000 0.000000 106 5.000000 0.000000 107 3.000000 0.000000 108 4.000000 0.000000 109 4.000000 0.000000 110 0.000000 0.000000 111 0.000000 0.000000 112 6.000000 0.000000
114 7.000000 0.000000 115 1.000000 0.000000 116 3.000000 0.000000 117 5.000000 0.000000 118 2.000000 0.000000 119 6.000000 0.000000 120 1.000000 0.000000 121 7.000000 0.000000 附录3：
model:
sets:
v / 1.. 10/: u,D;
link( v, v):C,y, x;
endsets
min = @sum( link: C*x);
@sum(v( I)| I #ne# 1: x(I, 1))=1;
@sum(v( I)| I #ne# 1: x(1,I))=1;
@FOR( v(K):
@sum( v( I)| I #ne# K: x( I, K))<1;
@sum( v( J)| J #ne# K: x(K,J))<1);
@FOR( v(K):
@bin(@sum( v( I)| I #ne# K: x( I, K)));
@bin(@sum( v( J)| J #ne# K: x(K,J))));
@sum(v(I)| I #ne#6 :x(I,6))=1;
!@sum(v(I)| I #ne#10 :x(I,10))=1;
!@sum(v(I)| I #ne#4 :x(I,4))=1;
!@sum(v(I)| I #ne#2:x(I,2))=1;
!@sum(v(I)| I #ne#3:x(I,3))=1;
!@sum(v(I)| I #ne#5:x(I,5))=1;
!@sum(v(I)| I #ne#8:x(I,8))=1;
!@sum(v(I)| I #ne#7:x(I,7))=1;
!@sum(link(I,J)|I #ne# J:x(I,J))>4
@sum(link(I,J)|I #ne# J:x(I,J)*D(J))>36
@sum(link(I,J)|I #ne# J:x(I,J)*D(J))<50;
@for(v(I):
@sum(v(J): x(I,J))-@sum(v(J): x(J,I))=0);
@for(v(I)|I #gt# 1:
@for( v( J)| J#gt#1 #and# I #ne# J:
u(I)-u(J)+10*x(I,J)<=9));
@for( link: @bin( x));
@for( link: @gin( x));
data:
D=8,13,6,9,7,15,10,5,12,9;
数学建模竞赛简介
数学建模竞赛简介 数学建模就是建立、求解数学模型的过程和方法，首先要通过分析主要矛盾，对各种实际问题进行抽象简化，并按照有关规律建立起变量，参数间的明确关系，即明确的数学模型，然后求出该数学问题的解，并通过一定的手段来验证解的正确性。 数学建模竞赛于1985年起源于美国，起初竞赛题目通常由工业部门、军事部门提出，然后由数学工作者简化或修正。1989年我国大学生开始参加美国大学生数学建模竞赛，1990年我国开始创办我国自己的大学生数学建模竞赛。1993年国家教委（现教育部）高教司正式发文，要求在全国普通高等学校中开展数学建模竞赛。从1994年开始，大学生数学建模竞赛成为教育部高教司和中国工业的应用数学学会共同主办，每年一届的，面向全国高等院校全体大学生的一项课外科技竞赛活动。2010年全国共有30省(市、自治区)九百多所院校一万多个队三万多名大学生参赛，成为目前全国高等学校中规模最大的课外科技活动。数学建模竞赛是教育主管部门主办的大学生三大竞赛之一。 现在的竞赛题目来源于更广泛的领域，都是各行各业的实际问题经过适当简化，提炼出来的极富挑战性的问题，每次两道题，学生任选一题，可以使用计算机、软件包，可以参阅任何资料(含上网参阅任何资料)。竞赛以三人组成的队为单位，三人之间通力合作，在三天三夜内完成一篇论文。不给论文评分，而是按论文的水平为四档：全国一等奖、全国二等奖、赛区一等奖，赛区二等奖，成功参赛奖。我校于2001年开始参加这项竞赛活动。多次获全国一等奖、二等奖、湖北赛区一等奖、二等奖。 数学建模竞赛活动培养了学生的创造力、应变能力、团队精神和拼搏精神，适应了21世纪经济发展和人才培养的挑战。不少参加过全国大学生数学建模竞赛的同学都深有感触，他们说：“参加这次活动是我们大学四年中最值得庆幸的一件事，我们真正体会这几年内学到了什么，自己能干什么。”“那不寻常的三天在我们记忆中留下了永恒的一瞬，真是一次参赛，终身受益。”团队精神贯穿在数学建模竞赛的全过程，它往往是成败的关键。有些参赛队员说：“竞赛使我们三个人认识到协作的重要性，也学会了如何协作，在建模的三天中，我们真正做到了心往一处想，劲往一处使，每个人心中想的就是如何充分发挥自己的才华，在短暂的时间内做出一份尽量完善的答卷。三天中计算机没停过，我们轮流睡觉、轮流工作、轮流吃饭，可以说是抓住了每一滴可以抓住的时间。”“在这不眠的三天中，我们真正明白了团结就是力量这个人生真谛，而这些收获，将会伴随我们一生，对我们今后的学习，工作产生巨大的影响。”
数学建模飞机运输问题
多变量有约束最优化问题 摘要 本文以一家运输航空公司的一架飞机运载能力100吨和运载货物的容量50000立方英尺有限的情况下，有三种货物（即x1、x2、x3）需要运输，公司规定每吨货物收取一定的费用，而要运输的每种货物的吨数都有规定的上限（最多不超过30吨、40吨、50吨），并且公司规定由于飞机需要保养与维护，飞机须停飞115天，因此每年只有250天的工作时间。在此情况下每天怎样安排运输三种货物使公司每年获得最大利润w。对于此问题只用线性规划的一般方法建立相应的数学模型，在用数学软件求出在给定限行区域内的最优解（w、x1、x2、x3），在对这些最优解进行分析与讨论，确定其为有效最优解。并以此作为公司对三种货物运输安排方式。 对于问题一，求使得运输航空公司获得最大利润w的x1、x2、x3三种货物的吨数，建立相应的数学模型。再根据运输能力最多100吨和运载货物容积的最大50000立方英尺，还有每天公司规定的每种货物的运输上限即x1种货物最多运输30吨，x2种货物最多运输40吨，x3种货物最多50吨，建立约束条件。并用数学软件mathematica进行求解，即为所求的最优解（也就是w=21875，x1=30，x2=7.5，x3=50）。
对于问题二中，要求计算每个约束的影子价格。我们将利用问题一中建立的目标函数和约束条件，将其编写成源程序输入到Lindo软件中进行求解。再将得到的界进行讨论与和模型的稳健性分析并且通过其在题意的理解，解释其含义。 问题三中，对于公司将耗资改装飞机以扩大运货区来增加运输能力，且旧飞机使用寿命为5年，每架飞机的改造要花费200000美元，可以增加2000立方英尺的容积。重量限制仍保持不变。假设飞机每年飞行250天，这些旧飞机剩余的使用寿命约为5年。根据此问题我们将建立数学规划模型，利用Lindo软件计算其影子价格和利润并且与前面进行比较，进行分析。 关键词：线性规划、mathematica软件的应用、Lindo的软件应用。
数学建模大赛货物运输问题
数学建模大赛货物运输 问题 SANY标准化小组 #QS8QHH-HHGX8Q8-GNHHJ8-HHMHGN#
货物配送问题 【摘要】 本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题 提出的方案。我们首先考虑在满足各个公司的需求的情况下，所需要的运输的 最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了 较为合理的优化模型，求出较为优化的调配方案。 针对问题一，我们在两个大的方面进行分析与优化。第一方面是对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公司逆时针送货为最佳方案。第二方面我们根据车载重相对最大化思想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。 耗时为小时，费用为元。 针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。我们采取与问题一相同的算法，得出耗时最少，费用最少的方 案。耗时为小时，费用为元。 针对问题三的第一小问，我们知道货车有4吨、6吨和8吨三种型号。我们经过简单的论证，排除了4吨货车的使用。题目没有规定车子不能变向，所 以认为车辆可以掉头。然后我们仍旧采取①~④公司顺时针送货，⑤~⑧公司逆 时针送货的方案。最后在满足公司需求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：第一，使8吨车次满载并运往同一公司；第二，6 吨位车次满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6吨货 车运输，若在7~8吨内用8吨货车运输。最后得出耗时最少、费用最省的方 案。耗时为小时，费用为。 一、问题重述 某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司 所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的 双向道路(如图１)。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输 车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费元/吨公里，运输车空载费用元/公里。一个单位的原材料A,B,C分 别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车， 另外必须要满足各公司当天的需求量(见表１)。问题： 1、货运公司派出运输车6辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。 2、每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数应如何调度
数学建模大赛货物运输问题
货物配送问题 【摘要】 本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题提出的方案。我们首先考虑在满足各个公司的需求的情况下，所需要的运输的最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了较为合理的优化模型，求出较为优化的调配方案。 针对问题一，我们在两个大的方面进行分析与优化。第一方面是对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公司逆时针送货为最佳方案。第二方面我们根据车载重相对最大化思想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。耗时为小时，费用为元。 针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。我们采取与问题一相同的算法，得出耗时最少，费用最少的方案。耗时为小时，费用为元。 针对问题三的第一小问，我们知道货车有4吨、6吨和8吨三种型号。我们经过简单的论证，排除了4吨货车的使用。题目没有规定车子不能变向，所以认为车辆可以掉头。然后我们仍旧采取①~④公司顺时针送货，⑤~⑧公司逆时针送货的方案。最后在满足公司需求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：第一，使8吨车次满载并运往同一公司；第二，6吨位车次满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6吨货车运输，若在7~8吨内用8吨货车运输。最后得出耗时最少、费用最省的方案。耗时为小时，费用为。 一、问题重述 某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的双向道路(如图１)。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费元/吨公里，运输车空载费用元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表１)。问题：
#蔬菜运输问题--数学建模
蔬菜运输问题 2012年8月22日 摘要 本文运用floyd算法求出各蔬菜采购点到每个菜市场的最短运输距离，然后用lingo软件计算蔬菜调运费用及预期短缺损失最小的调运方案，紧接着根据题目要求对算法加以修改得出每个市场短缺率都小于20%的最优调运方案，并求出了最佳的供应改进方案。 关键词 最短路问题 floyd算法运输问题 一、问题重述 光明市是一个人口不到15万人的小城市。根据该市的蔬菜种植情况，分别在花市（A），城乡路口（B）和下塘街（C）设三个收购点，再由各收购点分送到全市的8个菜市场，该市道路情况，各路段距离（单位：100m）及各收购点，菜市场①L⑧的具体位置见图1，按常年情况，A,B,C三个收购点每天收购量分别为200，170和160（单位：100 kg）,各菜市场的每天需求量及发生供应短缺时带来的损失（元/100kg）见表 1.设从收购点至各菜市场蔬菜调运费为1元/(100kg.100m). ①7 ② 5 4 8 3 7 A 7 ⑼ 6 B ⑥ 6 8 5 5 4 7 11 7 ⑾ 4 ③ 7 5 6 6 ⑤ 3 ⑿ 5 ④ ⑽ 8 6 6 10 C 10 ⑧ 5 11 ⑦图1 表1 菜市场每天需求（100 kg）短缺损失（元/100kg） ①75 10 ②60 8 ③80 5 ④70 10 ⑤100 10 ⑥55 8 ⑦90 5 ⑧80 8 (a)为该市设计一个从收购点至个菜市场的定点供应方案，使用于蔬菜调运及预
期的短缺损失为最小； (b)若规定各菜市场短缺量一律不超过需求量的20%，重新设计定点供应方案 (c)为满足城市居民的蔬菜供应，光明市的领导规划增加蔬菜种植面积，试问增 产的蔬菜每天应分别向A,B,C三个采购点供应多少最经济合理。 二、问题分析 求总的运费最低，可以先求出各采购点到菜市场的最小运费，由于单位重量运费和距离成正比，题目所给的图1里包含了部分菜市场、中转点以及收购点之间的距离，（a）题可以用求最短路的方法求出各采购点到菜市场的最短路径，乘上单位重量单位距离费用就是单位重量各运输线路的费用，然后用线性方法即可解得相应的最小调运费用及预期短缺损失。 第二问规定各菜市场短缺量一律不超过需求量的20%，只需要在上题基础上加上新的限制条件，即可得出新的调运方案。 第三问可以在第二问的基础上用灵敏度分析进行求解，也可以建立新的线性问题进行求解。 三、模型假设 1、各个菜市场、中转点以及收购点都可以作为中转点； 2、各个菜市场、中转点以及收购点都可以的最大容纳量为610吨； 3、假设只考虑运输费用和短缺费用，不考虑装卸等其它费用； 4、假设运输的蔬菜路途中没有损耗； 5、忽略从种菜场地到收购点的运输费用。 四、符号说明 A收购点分送到全市的8个菜市场的供应量分别为a1,b1,c1,d1,e1,f1,g1,h1, B收购点分送到全市的8个菜市场的供应量分别为a2,b2,c2,d2,e2,f2,g2,h2, C收购点分送到全市的8个菜市场的供应量分别为a3,b3,c3,d3,e3,f3,g3,h3, 8个菜市场的短缺损失量分别为a,b,c,d,e,f,g,h(单位均为100kg)。 五、模型的建立和求解 按照问题的分析，首先就要求解各采购点到菜市场的最短距离，在图论里面关于最短路问题比较常用的是Dijkstra算法，Dijkstra算法提供了从网络图中某一点到其他点的最短距离。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。但由于它遍历计算的节点很多，所以效率较低，实际问题中往往要求网络中任意两点之间的最短路距离。如果仍然采用Dijkstra算法对各点分别计算，就显得很麻烦。所以就可以使用网络各点之间的矩阵计算法，即Floyd 算法。 Floyd算法的基本是：从任意节点i到任意节点j的最短路径不外乎2种可能，1是直接从i到j，2是从i经过若干个节点k到j。i到j的最短距离不外乎存在经过i和j之间的k和不经过k两种可能，所以可以令k=1，2，3，...，n(n是城市的数目)，在检查d(i,j)和d(i,k)+d(k,j)的值；在此d(i,k)和d(k,j)分别是目前为止所知道的i到k和k到j的最短距离。因此d(i,k)+d(k,j)就是i到j经过k的最短距离。所以，若有d(i,j)>d(i,k)+d(k,j)，就表示从i出发经过k再到j的距离要比原来的i到j距离短，自然把i到j的d(i,j)重写为
数学建模城市垃圾运输问题概论
货运公司运输问题 数信学院14级信计班魏琮 【摘要】 本文是针对解决某港口对某地区8个公司所需原材料A、B、C的运输调度问题提出的方案。首先考虑在满足各个公司的需求的情况下，所需要的运输的最小运输次数，然后根据卸载顺序的约束以及载重费用尽量小的原则，提出了较为合理的优化模型，求出较为优化的调配方案。 针对问题一，在两个大的方面进行分析与优化。第一方面是对车次安排的优化分析，得出①~④公司顺时针送货，⑤~⑧公司逆时针送货为最佳方案。第二方面根据车载重相对最大化思 想使方案分为两个步骤，第一步先是使每个车次满载并运往同一个公司，第二步采用分批次运输的方案，即在第一批次运输中，我们使A材料有优先运输权；在第二批次运输中，我们使B材料有优先运输权；在第三批次中运输剩下所需的货物。最后得出耗时最少、费用最少的方案。耗时为40.3333小时，费用为4864.0元。 针对问题二，加上两个定理及其推论数学模型与问题一几乎相同，只是空载路径不同。采取与问题一相同的算法，得出耗时最少，费用最少的方案。耗时为26.3小时，费用为4487.2元。 针对问题三的第一小问，知道货车有4吨、6吨和8吨三种型号。经过简单的论证，排除了4吨货车的使用。题目没有规定车
子不能变向，所以认为车辆可以掉头。然后仍旧采取①~④公司 顺时针送货，⑤~⑧公司逆时针送货的方案。最后在满足公司需 求量的条件下，采用不同吨位满载运输方案，此方案分为三个步骤：第一，使8吨车次满载并运往同一公司；第二，6吨位车次 满载并运往同一公司；第三，剩下的货物若在1~6吨内，则用6 吨货车运输，若在7~8吨内用8吨货车运输。最后得出耗时最少、费用最省的方案。耗时为19.6833小时，费用为4403.2元。 一、问题重述 某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的双向道路(如图１)。货运公司现有一种载重6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表１)。问题： 1、货运公司派出运输车6辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。
数学建模常见评价模型简介
常见评价模型简介 评价类数学模型是全国数学建模竞赛中经常出现的一类模型，如2005年全国赛A题长江水质的评价问题，2008年B题高校学费标准评价体系问题等。主要介绍三种比较常用的评价模型：层次分析模型，模糊综合评价模型，灰色关联分析模型，以期帮助大家了解不同背景下不同评价方法的应用。 层次分析模型 层次分析法(AHP)是根据问题的性质和要求，将所包含的因素进行分类，一般按目标层、准则层和子准则层排列，构成一个层次结构，对同层次内诸因素采用两两比较的方法确定出相对于上一层目标的权重，这样层层分析下去，直到最后一层，给出所有因素相对于总目标而言，按重要性程度的一个排序。其主要特征是，它合理地将定性与定量决策结合起来，按照思维、心理的规律把决策过程层次化、数量化。 运用层次分析法进行决策，可以分为以下四个步骤： 步骤1 建立层次分析结构模型 深入分析实际问题，将有关因素自上而下分层(目标—准则或指标—方案或对象)，上层受下层影响，而层内各因素基本上相对独立。 步骤2构造成对比较阵 对于同一层次的各元素关于上一层次中某一准则的重要性进行两两比较，借助1~9尺度，构造比较矩阵； 步骤3计算权向量并作一致性检验 由判断矩阵计算被比较元素对于该准则的相对权重，并进行一致性检验，若通过，则最大特征根对应的特征向量做为权向量。
步骤4计算组合权向量(作组合一致性检验) 组合权向量可作为决策的定量依据 通过一个具体的例子介绍层次分析模型的应用。 例(选择旅游地决策问题)如何在桂林、黄山、北戴河3个目的地中按照景色、费用、居住条件、饮食、旅途条件等因素进行选择。 步骤1 建立系统的递阶层次结构 将决策问题分为3个层次：目标层O，准则层C，方案层P；每层有若干元素，各层元素间的关系用相连的直线表示。
数学建模--运输问题
数学建模--运输问题
运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo 编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第 一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题
数学建模运输问题
数学建模运输问题公司内部档案编码：[OPPTR-OPPT28-OPPTL98-OPPNN08]
运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd 算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd 算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需
求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：-1，第二辆车：，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的(,) i j=位置上的数表示（其中∞表示两个客户之间无直接的 i j(,1,,10) 路线到达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让 他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车 一次能装满10个客户所需要的全部货物，请问货车从提货点出发给
数学建模简介
数学建模简介 当需要从定量的角度分析和研究一个实际问题时，人们就要在深入调查研究、了解对象信息、作出简化假设、分析内在规律等工作的基础上，用数学的符号和语言作表述，也就是建立数学模型，然后用通过计算得到的结果来解释实际问题，并接受实际的检验。这个建立数学模型的全过程就称为数学建模。 数学建模的广泛应用 数学建模的应用逐渐变的广泛，数学建模大量用于一般工程技术领域，用于代替传统工程设计中的现场实验、物理模拟等手段；在高新科技领域，成为必不可少的工具，无论是在通信、航天、微电子、自动化都是创新工艺、开发新 产品的必要手段；在新的科研领域在用数学方法研究 其中的定量关系时，数学建模就成为首要的、关键的 步骤和这些学科发展和应用的基础。 将计算机技术和数学建模进行紧密结合，使得原 本抽象的数学模型生动具体的呈现在研究者面前，使 得问题得到更好的解决。 数学建模的分支——数据挖掘 数据挖掘（Data Mining，DM）是目前人工智能和数 据库领域研究的热点问题，所谓数据挖掘是指从数据库 的大量数据中揭示出隐含的、先前未知的并有潜在价值 的信息的非平凡过程。数据挖掘是一种决策支持过程， 它主要基于人工智能、机器学习、模式识别、统计学、 数据库、可视化技术等，高度自动化地分析企业的数据， 做出归纳性的推理，从中挖掘出潜在的模式，帮助决策 者调整市场策略，减少风险，做出正确的决策。 数据挖掘是通过分析每个数据，从大量数据中寻找其规律的技术，主要有数据准备、规律寻找和规律表示3个步骤。数据准备是从相关的数据源中选取所需的数据并整合成用于数据挖掘的数据集；规律寻找是用某种方法将数据集所含的规律找出来；规律表示是尽可能以用户可理解的方式（如可视化）将找出的规律表示出来。 数据挖掘的任务有关联分析、聚类分析、分类分析、异常分析、特异群组分析和演变分析，等等。
数学建模运输问题
运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo 编程求解出最终结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进行分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进行编程求解，运行得到结果：2-3-8-9-10总路程为85公里。 关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1（提货点）的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进行编程求解，求解出的回路与Kruskal算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进行优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。 关于问题四，在问题一的基础上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。 关键词： Floyd算法 Kruskal算法整数规划旅行商问题 一、问题重述 某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的 i j=L位置上的数表示（其中∞表示两个客户之间无直接的路线到i j(,1,,10) (,) 达）。 1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给 客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能 装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送
数学建模运输问题
华东交通大学数学建模 2012年第一次模拟训练题 所属学校：华东交通大学（ECJTU ） 参赛队员：胡志远、周少华、蔡汉林、段亚光、 李斌、邱小秧、周邓副、孙燕青 指导老师：朱旭生（博士） 摘要： 本文的运输问题是一个比较复杂的问题，大多数问题都集中在最短路径的求解问题上，问题特点是随机性比较强。 根据不同建模类型 针对问题一 ，我们直接采用Dijkstra 算法（包括lingo 程序和手算验证），将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：109832V V V V V →→→→，总行程85公里。 针对问题二，我们首先利用prim 算法求解得到一棵最小生成树： 121098436751V V V V V V V V V V V →→→→→→→→→→ 再采用Dijkstra 算法求得客户2返回提货点的最短线路为12V V →故可得到一条理想的回路是：121098436751V V V V V V V V V V V →→→→→→→→→→ 后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线： 121098436751V V V V V V V V V V V →→→→→→→→→→。 针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）； 针对问题四，
数学建模的介绍
一、数学建模的意义 数学建模是一种数学的思考方法，是运用数学的语言和方法，通过抽象、简化建立能近似刻画并"解决"实际问题的一种强有力的数学手段。 数学建模就是用数学语言描述实际现象的过程。这里的实际现象既包涵具体的自然现象比如自由落体现象，也包涵抽象的现象比如顾客对某种商品所取的价值倾向。这里的描述不但包括外在形态，内在机制的描述，也包括预测，试验和解释实际现象等内容。 我们也可以这样直观地理解这个概念：数学建模是一个让纯粹数学家（指只懂数学不懂数学在实际中的应用的数学家）变成物理学家，生物学家，经济学家甚至心理学家等等的过程。 数学模型一般是实际事物的一种数学简化。它常常是以某种意义上接近实际事物的抽象形式存在的，但它和真实的事物有着本质的区别。要描述一个实际现象可以有很多种方式，比如录音，录像，比喻，传言等等。为了使描述更具科学性，逻辑性，客观性和可重复性，人们采用一种普遍认为比较严格的语言来描述各种现象，这种语言就是数学。使用数学语言描述的事物就称为数学模型。有时候我们需要做一些实验，但这些实验往往用抽象出来了的数学模型作为实际物体的代替而进行相应的实验，实验本身也是实际操作的一种理论替代。 应用数学去解决各类实际问题时，建立数学模型是十分关键的一步，同时也是十分困难的一步。建立教学模型的过程，是把错综复杂的实际问题简化、抽象为合理的数学结构的过程。要通过调查、收集数据资料，观察和研究实际对象的固有特征和内在规律，抓住问题的主要矛盾，建立起反映实际问题的数量关系，然后利用数学的理论和方法去分析和解决问题。这就需要深厚扎实的数学基础，敏锐的洞察力和想象力，对实际问题的浓厚兴趣和广博的知识面。数学建模是联系数学与实际问题的桥梁，是数学在各个领械广泛应用的媒介，是数学科学技术转化的主要途径，数学建模在科学技术发展中的重要作用越来越受到数学界和工程界的普遍重视，它已成为现代科技工作者必备的重要能力之。为了适应科学技术发展的需要和培养高质量、高层次科技人才，数学建模已经在大学教育中逐步开展，国内外越来越多的大学正在进行数学建模课程的教学和参加开放性的数学建模竞赛，将数学建模教学和竞赛作为高等院校的教学改革和培养高层次的科技人才的个重要方面，现在许多院校正在将数学建模与教学改革相结
数学建模运输问题
华东交通大学数学建模2012年第一次模拟训练题 所属学校：华东交通大学（ECJTU ） 参赛队员：胡志远、周少华、蔡汉林、段亚光、 李斌、邱小秧、周邓副、孙燕青 指导老师：朱旭生（博士） 摘要： 本文的运输问题是一个比较复杂的问题，大多数问题都集中在最短路径的求 解问题上，问题特点是随机性比较强。 根据不同建模类型 针对问题一 ，我们直接采用Dijkstra 算法（包括lingo 程序和手算验证），将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：109832V V V V V →→→→，总行程85公里。 针对问题二，我们首先利用prim 算法求解得到一棵最小生成树： 121098436751V V V V V V V V V V V →→→→→→→→→→ 再采用Dijkstra 算法求得客户2返回提货点的最短线路为12V V →故可得到一条理想的回路是：121098436751V V V V V V V V V V V →→→→→→→→→→ 后来考虑到模型的推广性，将问题看作是哈密顿回路的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线： 121098436751V V V V V V V V V V V →→→→→→→→→→。 针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）； 针对问题四，
基于运输问题的数学建模
数学建模一周论文论文题目：基于运输问题的数学模型 1：学号： 2：学号： 3：学号： 专业： 班级： 指导教师： 2011年12 月29 日
（十五）、已知某运输问题的产销平衡表与单位运价表如下表所示 （1）求最优调拨方案； （2）如产地的产量变为130，又B地区需要的115单位必须满足，试重新确定最优调拨方案。 一论文摘要 一般的运输问题就是要解决把某种产品从若干个产地调运到若干个销地，在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，如何确定一个使得总的运输费用最小的方案的问题。本论文运用线性规划的数学模型来解决此运输问题中总费用最小的问题。引入x变量作为决策变量，建立目标函数，列出约束条件，借助MATLAB软件进行模型求解运算，得出其中的最优解，使得把某种产品从3个产地调运到5个销地的总费用最小。 针对模型我们探讨将某产品从3个产地调运到5个销地的最优调拨方案，通过运输问题模，得到模型 Z=1011x+1512x+2013x+2014x+4015x+2021x+4022x+1523x+3024x min x+3031x+3532x+4033x+5534x+2535x +30 25 Z= 并用管理运筹学软件软件得出最优解为： min
关键词：运输模型最优化线性规划 二．问题的重述和分析 A（i=1,2,3）和五个销地j B（j=1,2,3,4,5），已知产地i A的产量有三个产地 i s和销地j B的销量j d，和将物品从产地i运到销地j的单位运价ij c，请问：i 将物品从产地运往销地的最优调拨方案。 A，2A，3A三个产地的总产量为50+100+150=300单位；1B，我们知道， 1 B，3B，4B，5B五个销地的总销量为25+115+60+30+70=300单位，总2 A,2A,3A的产量全产量等于总销量，这是一个产销平衡的运输问题。把产地 1 B,2B,3B,4B,5B，正好满足这三个销地的需要。先将安排的部分配给销地 1 运输量列如下表中：
垃圾运输问题
B题：垃圾运输问题 某城区有３６个垃圾集中点，每天都要从垃圾处理厂（第３７号节点）出发将垃圾运回。现有一种载重 6吨的运输车。每个垃圾点需要用１０分钟的时间装车，运输车平均速度为40公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4小时。运输车重载运费1.8元/吨公里；运输车和装垃圾用的铲车空载费用0.4元/公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。 问题： 1. 运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用） 2. 铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用） 3. 如果有载重量为4吨、6吨、8吨三种运输车，又如何调度？
垃圾运输问题的模型及其求解 摘要:本文通过垃圾运输问题的模型建立与求解,总结出这类问题的一般性解法,即根据实际问题构造恰当的有向或无向赋权图,把问题转化成图论中的TSP问题,通过解决这类TSP问题,从而使原问题获得满意的解答. 关键词:垃圾运输问题; TSP问题 图论是一支应用性很强的学科分支,它对自然科学、工程技术、经济管理和社会现象等诸多问题,能够提供很好的数学模型加以解决,所以,在国内外大学生数学建模竞赛中,常会出现用图论模型去解决的实例,如垃圾运输问题,统筹问题等. 1有关概念 定义1[ 1 ] 设G = (V, E) 是连通无向图, (1) 经过G的每一个顶点正好一次的路,称为G的一条哈密顿路或H路; (2) 经过G的每一个顶点正好一次的圈,称为G的一条哈密顿圈或H圈; (3) 含H圈的图称为哈密顿图或H图. 定义2[ 1 ] 设D = (V, A ) 是连通有向图, (1) 经过D的每一个顶点正好一次的圈,称为D的生成圈; (2) 含生成圈的图称为哈密顿图或H图. 定义3[ 1 ] 设G是完全(有向或无向) 赋权图,在G中寻找权最小闭迹的问题称为TSP问题(即Trave ling Salesman Problem) . 若此闭迹是H圈,则称此闭迹为最佳H圈. 容易证明:在满足条件w ( vi vj ) +w ( vj vk ) 下, TSP问题可转化为寻找最佳H圈的问题,这可通过构造一个完全图来实现. 2垃圾运输问题 例1某城区有若干个垃圾集中点,每天都要从垃圾处理厂(第37号节点)出发将垃圾运回. 假定运输 图1运输车线路图 车的线路已确定下来共10条(如图1所示). 为了节省费用, 运输车在每条线路上总是先从远离处理厂的垃圾集中点开始运送垃圾. 现有6辆载重6吨的运输车及装垃圾用的铲车, 它们的平均速度为40 km /h (夜里运输,不考虑塞车现象) ,每个垃圾点需要用10 min的时间装车,每台运输车每日平均工作4 h. 运输车重载运费1. 8元/吨km;运输车和装垃圾用的铲车空载费用0. 4元
数学建模课程简介
《数学建模》课程简介 20053025 数学建模 4.5 Mathematical Modeling 4-1 预修要求：微积分、线性代数 面向对象：竺可桢学院工程高级班 内容简介： 本课程以物理、生态、环境、医学、管理、经济、信息技术等领域的一些典型实例为背景，阐述如何通过建立数学模型的方法来研究、解决实际问题的基本方法和技能。开设本课程的目的是，在传授知识的同时，通过典型建模实例的分析和参加建模实践活动，培养和增强学生自学能力、创新素质。参加数学建模课的学习，应自己动手解决一、二个实际问题，以求在实际参与中获取真知。 本课程包括一定学时的讨论班，学生可利用课外时间自己参与建模实践活动并自愿参加由指导教师组织的讨论班活动。选修本课程的本科生经双向选择还有机会参加全国大学生数学建模竞赛（每年约90人）和美国大学生数学建模竞赛（每年为21人）。 推荐教材或参考书： “数学建模”，杨启帆、谈之奕、何勇编著，浙江大学出版社出版，2006年7月 《数学建模》教学大纲 20053025 数学建模 4.5 Mathematical Modeling 4-1 预修要求：微积分、线性代数 面向对象：竺可桢学院工程高级班 一、教学目的与基本要求： 通过典型数学模型分析和课外建模实践，使学生基本掌握运用数学知识建立数学模型来研究科研问题或实际课题的基本技能与基本技巧，本课程教学除传授知识外还要求学生在实际建模中注意培养和提高自身的能力，以便提高自己的综合素质与实际本领。 二、主要内容及学时分配： 1.数学建模概论，3学时 2.初等模型，8学时：舰艇的汇合，双层玻璃的功效，崖高的估算，经验模型，参数 识别，量纲分析法建模，方桌问题、最短路径与最速方案等 3.微分方程建模，14学时：马尔萨斯模型和罗杰斯蒂克模型，为什么要用三级火箭发 射人造卫星，药物在体内的分布，传染病模型，捕食系统的P-P模型，双种群生态 系统研究等
线性规划与数学建模简介
第十三章线性规划与数学建模简介 【授课对象】理工类专业学生 【授课时数】6学时 【授课方法】课堂讲授与提问相结合 【基本要求】1、了解数学模型的基本概念、方法、步骤； 2、了解线性规划问题及其数学模型； 3、了解线性规划问题解的性质及图解法. 【本章重点】线性规划问题. 【本章难点】线性规划问题、线性规划问题解的性质、图解法. 【授课内容】 本章简要介绍数学建模的基本概念、方法、步骤，并以几个典型线性规划问题为例，介绍构建数学模型的方法及其解的性质。 §1 数学建模概述 一、数学建模 数学建模是构造刻划客观事物原型的数学模型并用以分析、研究和解决实际问题的一种科学方法。运用这种科学方法，必须从实际问题出发，遵循从实践到认识再实践的认识规律，围绕建模的目的，运用观察力、想象力的抽象概括能力，对实际问题进行抽象、简化，反复探索，逐步完善，直到构造出一个能够用于分析、研究和解决实际问题的数学模型。因此，数学建模是一种定量解决实际问题的创新过程。 二、数学模型的概念
模型是人们对所研究的客观事物有关属性的模拟。例如在力学中描述力、 量和加速度之间关系的牛顿第二定律F＝ma就是一个典型的（数学）模型。一般地，可以给数学模型下这样的定义：数学模型是磁于以部分现实世界为一定目的而做的抽象、简化的数学结构。 通俗而言，数学模型是为了一定目的对原型所作的一种抽象模拟，它用数学式子，数学符号以及程序、图表等描述客观事物的本质特征与内在联系。 三建立数学模型的方法和步骤 建立数学模型没有固定模式。下面介绍一下建立模型的大体过程： 1.建模准备 建模准备是确立建模课题的过程。这类课题是人们在生产和科研中为了使 认识和实践过一步发展必须解决的问题。因此，我们首先要发现这类需要解决的实际问题。其次要弄清所解决问题的目的要求并着手收集数据。进行建模筹划，组织必要的人力、物力等，确立建模课题。 2．模型假设 作为建模课题的实际问题都是错综复杂的、具体的。如果不对这些实际问题进行抽象简化，人们就无法准确把握它的本质属性，而模型假设就是根据建模的目的对原型进行抽象、简化，抓住反映问题本质属性的主要因素，简化掉那些非本质的次要因素。有了这些假设，就可以在相对简单的条件下，弄清各因素之间的关系，建立相应的模型。 合理的假设是建立理想模型的必要条件和基本保证。如果假设是合理的，则模型切合实际，能解决实际问题；如果假设不合理中或过于简化，则模型与实际情况不符或部分相符，就解决不了问题，就要修改假设，修改模型。 3．构造模型