运输问题
摘要
本文主要研究的是货物运输的最短路径问题，利用图论中的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、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送
货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。
2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个
客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。
3、现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小
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 c ij :；
个客户所需的货物量第j a j :；
:z 总路程；
五、模型的建立与求解
5.1问题一模型的建立与求解
问题一是要找出从客户2到客户10的最短路径，本文利用Floyd 算法对此文进行求解。
为计算方便，令网络的权矩阵为j i ij n n ij v v l d D 到为,)(?=的距离。
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 的最短路长。 在本文计算中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的最短路径是：
总路程为85公里。
5.2问题二模型的建立与求解
运输公司为这10个客户配送货物问题实际上是寻找一条最短的行车路线。当不考虑
送货员返回提货点的时候，本文利用最小生成树问题中的Kruskal 算法结合题中所给的邻接矩阵，很快可以得到无回路的最短路线。
Kruskal 算法基本步骤：
每步从未选的边中选取边e ，使它与已选边不够成圈，且e 是未选边中的最小权边，
知道选够1-n 条边为止。
利用最小生成树问题中的Kruskal 算法结合题中所给的邻接矩阵，很快可以得到以下最小生成树：
这两棵生成树不同之处就在于从客户6到达客户8的路径不一样，而实际路程经过计算后是一样的，路线的总行程为175公里。利用问题一的Floyd 算法和程序，能求得从客户2到客户1（提货点）的最短路线是12v v →，路程为50公里。
这样该回路，即最短的行车路线为：
行车路线总行程为225公里。
以最小生成树法解决此问题速度快，结果较精确，但是只适合数目较少时，不适宜推广，因此本文又根据路程最短建立整数规划模型。
为了更好的防止子巡回的产生，根据哈米尔顿回路，须附加一个约束条件：
当访问客户i 后必须要有一个即将访问的确切客户；访问客户j 前必须要有一个刚刚
访问过的确切客户。依次设立约束条件。
利用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
由此可得，行程路线最短的回路：
总路程为225公里。
5.3问题三模型的建立与求解
用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内。此问与问题二有相似之处都要考虑回到提货点的情形,因此本文在模型2的基础上进行改进, 重新建立相应的整数线性规划模型。
目标函数：101011min ij ij i j z c
x ===?∑∑
利用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公里。
对于模型求解出来的结果，本文利用Kruskal 算法结合题中所给的邻接矩阵进行优化。
从起始点v 处，进行分析，用两辆小的货车配送货物，为了尽可能的减少两辆车的重
复路线， 1v 到5v 、7v 的路程最短，让两辆车分开运货，先根据货物承载量50的限制让其中的一辆车走完路程，再让另一辆车走剩余城市的最短路线，这样走出两条运货路线： 第一种情况：
第一辆车：15234891
v v v v v v v v ??→??→??→??→??→??→??→，包含的客户有5,2,3,4,8，从模型1可解得，从8v 回到1v 的最短路线是198v v v →→，运货总量为40单位，路程为145公里。
第二辆车：1769101v 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公里。
第二辆车：15238910v 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）可得：
从中可以发现：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
所以，可得到目标函数：
六、模型的评价与推广
6.1模型的评价
（1）在整个模型的建立过程中，本文考虑的比较全面客观，使模型具有较强的说服力，结果更合理。
（2）根据问题的特点，综合运用了多个软件，如lingo、matlab等等，使得在解决问题的过程中，更方便简单。
这种寻路方法有其局限性，只适用于一些顶点较少的情况，顶点多，寻找起来较为麻烦。
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, 7) 30.00000 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( 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, 1) 100000.0 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, 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, 5) 20.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( 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, 9) 0.000000 40.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, 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, 3) 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
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
25 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
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
69 0.000000 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
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 113 2.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#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;
C=0 50 999 40 25 999 30 999 50 999
50 0 30 999 35 50 999 60 999 999
999 30 0 15 999 30 50 25 999 60
40 999 15 0 45 30 55 20 40 65
25 15 999 45 0 60 10 30 999 55
999 50 30 30 60 0 25 55 35 999
30 999 50 999 10 25 0 30 45 60
999 60 25 20 30 55 30 0 10 999
20 999 999 40 999 15 25 45 0 20
35 20 10 45 20 999 60 999 30 0
;
enddata
end
附录4：
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;
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
请输入起点1 请输入终点2 1
5
2
多变量有约束最优化问题 摘要 本文以一家运输航空公司的一架飞机运载能力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辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。
运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的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个客户配送
数学建模--运输问题
运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的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个客户所需要的全部货物，请问货车从提货点出发给
华东交通大学数学建模 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元
冰山运输数学模型 摘 要 当今社会，水资源短缺已成为世界性问题，水资源紧张地区正不断扩大，除淡化海水的方法外，专家提出从相距9600千米以外的南极托运冰山到波斯湾，将其化成冰水从而取代淡化海水作为国民用水。本文所要解决的是选择合适的拖船与船速使得冰山到达目的地后得到每立方米水所花的费用最低的问题，由此建立了一个关于费用y 的数学模型。首先，根据表3中的拖船速率v 和拖船与南极的距离可知冰山融化速率，从而确定剩余的冰山体积。然后，根据表2中的船速 v 和运输过程中剩余冰山的体积N 可知每千米燃料消耗量0q ，从而可以求出所 需燃料总消耗量Q ，再分别选取小、中、大三种船型确定拖船的租金总费用M ,则运输总费用Y Q M =+，运输每立方米水所花费用即为 0.06260.85Y y N = =。 根据运输每立方米水所花的费用最低，将该问题归结 为优化问题，运用积分方法，通过Matlab 计算，得到最优解确定船型和船速,再与海水淡化的费用相比较，确定其可行性。 关键字：冰山体积 融化速率 燃料消耗量 最优化 1.问题重述 在以石油着称的波斯湾地区，浩瀚的沙漠覆盖着大地，水资源十分缺乏，不得不采用淡化海水的办法为国民提供用水。成本大约是每立方米英镑。有些专家提出从相距9600km 外的南极用拖船运送冰山到波斯湾，以取代淡化海水的办法。 在运送冰山的过程中，拖船的租金、运量、燃料消耗以及冰山运送过程中融化速率等方面的数据如下： （1）三种拖船的日租金和最大运量如表1.所示。
（2）燃料消耗（英镑/km），主要依赖于船速和所运冰山的体积，船型的影响可以忽略，如表2.所示。 （3）冰山运输过程中的融化速率（m/d）,指在冰山与海水接触处每天融化的深度。融化速率除与船速有关，还与运输过程中冰山到达与南极的距离有关，这是由于冰山要从南极运往赤道附近的缘故。如表3.所示。 表3. 本文所要解决的问题是：选择拖船的船型与船速，使冰山到达目的地后，可以得到的每立方米水所花的费用最低，并与海水淡化的费用相比较。拖船在拖运冰山的过程中，有以下假设： （1）拖船航行过程中船速不变，航行不考虑天气等任何因素的影响，总航行距离9600km； （2）冰山形状为球形，球面各点的融化速率相同； （3）冰山到达目的地后，13 m的冰可以融化成3m的水。 2.问题分析 为更好地计算冰山运输的费用，我们对问题进行了分析。 根据题目已给的资料和数据，我们发现：冰山的运输主要和拖船的租金、运量、燃料消耗及冰山运输过程中融化速率有关，因此，我们可以把问题分成以下五步来分析解决：
数学建模论文 题目:送货问题 学院(直属系):数学与计算机学院 年级、专业: 2010级信息与计算科学 姓名:杨尚安 刘洋 谭笑 指导教师:蒲俊 完成时间:2012年 3 月 20 日 摘要 本文讨论的是货运公司的运输问题，根据各公司需求和运输路线图，建立了线性规划模型和0-1规划模型，对货运公司的出车安排进行了分析和优化，得出运费最小的调度方案。 对于问题一，由于车辆在途中不能掉头，出车成本固定，要使得总成本最小，即要使在一定的车辆数下，既满足各公司的需求，又要尽量减小出车次数。故以最小出车数为目标函数，建立线性规划模型，并通过lingo求解，得出最小出车数27次。接着考虑车的方向问题，出车分为顺时针和逆时针，建立0-1模型，并求解，得出满足问题一的调度方案（见附录表1）。 对于问题二，车辆允许掉头，加上车辆装载货物和空装时运输费不同，，要使总成本最小，故可以通过修改原目标函数，建立线性规划模型和0-1规划模型，求解，得出最佳派出车辆3辆并列出满足问题二的调度方案。 对于问题三第一小问，增加了运输车辆的类型。即装载材料的方法很多，在上述分析的基础上，通过增加约束条件，建立新的线性规划模型，并求解，得出满足问题三的调度方案。在第二小问中，由于给出部分公司有道路相通，可采用 运筹学中的最短路问题的解决方法加以解决。 关键字：线性规划模型 0-1规划模型调度
一、问题重述 某地区有8个公司(如图一编号①至⑧)，某天某货运公司要派车将各公司所需的三种原材料A,B,C从某港口(编号⑨)分别运往各个公司。路线是唯一的双向道路(如图１)。货运公司现有一种载重 6吨的运输车，派车有固定成本20元/辆，从港口出车有固定成本为10元/车次(车辆每出动一次为一车次)。每辆车平均需要用15分钟的时间装车，到每个公司卸车时间平均为10分钟，运输车平均速度为60公里／小时(不考虑塞车现象)，每日工作不超过8小时。运输车载重运费1.8元/吨公里，运输车空载费用0.4元/公里。一个单位的原材料A,B,C 分别毛重4吨、3吨、1吨，原材料不能拆分，为了安全，大小件同车时必须小件在上，大件在下。卸货时必须先卸小件，而且不允许卸下来的材料再装上车，另外必须要满足各公司当天的需求量(见表１)。问题： 1、货运公司派出运输车6辆，每辆车从港口出发(不定方向)后运输途中不允许掉头，应如何调度(每辆车的运载方案，运输成本)使得运费最小。 2、每辆车在运输途中可随时掉头，若要使得成本最小，货运公司怎么安排车辆数？应如何调度？ 3、(1)如果有载重量为4吨、6吨、8吨三种运输车，载重运费都是1.8元/吨公里，空载费用分别为0.2，0.4，0.7元/公里，其他费用一样，又如何安排车辆数和调度方案？(2)当各个公司间都有或者部分有道路直接相通时，分析运输调度的难度所在，给出你的解决问题的想法(可结合实际情况深入分析)。 二、符号说明 x表示为一个车装一单位A和两单位C； 1 x表示为一个车装六单位C； 2 x表示为一个车装两单位B； 3 x表示为一个车装一单位B和三单位C； 4 S表示最小运输次数； x表示为一个车装一单位A和一单位C； 5
数学建模运输问题集团标准化工作小组 [Q8QX9QT-X8QQB8Q8-NQ8QJ8-M8QMN]
运输问题 摘要 本文主要研究的是货物运输的最短路径问题，利用图论中的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 个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线对所设计的算法进行分析。
垃圾运输问题 *** 信息工程学院计算机应用专业 ********** 摘要：本文通过对垃圾站点之间分布位置的分析，构造出解决垃圾运输问题的模型。 首先，我们对所给数据绘制其xy散点图，根据题设提出自己假设的条件，。 其次，结合已有的模型，对垃圾点之间的位置分布关系进行讨论及证明，从而确定最基本的行车路线原则。 然后，编写c语言程序，利用计算机进行算法的模拟，从而搜索出各运输车辆的数量以及最佳的分配方案，使得(1)在不考虑铲车的情况下运输费用最少、(2)考虑在有铲车的模型中的最佳解、(3)对不同运输量的运输车进行合理分配调度，使得总费用最少。 根据我们确定的解题思路，最终我们得到了一组可行解，如下： 第一问，求得全部的运输费用是2340.97元，花费的总时间是21.95小时； 第二问：求得需要3辆铲车； 第三问：求得总的运输费用是2323.77 元。其中8吨的车4辆，6吨的车3辆，4吨的车3辆。 具体的路线分配图，车辆调度图见正文部分。 本文讨论的解题方法模型简单，得出的结果只是一个近似最优解的可行解，所以还有很大的改进空间，比如我们可以采用更加智能的算法等。 关键词：计算机算法模拟优化 1．问题的重述 某城区有 37 个垃圾集中点，每天都要从垃圾处理厂（第 38号节点）出发将垃圾运回。现有一种载重 6 吨的运输车。每个垃圾点需要用 10 分钟的时间装车，运输车平均速度为40 公里／小时（夜里运输，不考虑塞车现象）；每台车每日平均工作 4 小时。运输车重载运费 2 元 / 吨公里；运输车和装垃圾用的铲车空载费用 0.5 元 / 公里；并且假定街道方向均平行于坐标轴。请你给出满意的运输调度方案以及计算程序。 问题： 1.运输车应如何调度（需要投入多少台运输车，每台车的调度方案，运营费用） 2.铲车应如何调度（需要多少台铲车，每台铲车的行走路线，运营费用） 3.如果有载重量为 4 吨、 6 吨、 8 吨三种运输车，又如何调度？ 2．模型的基本假设与符号说明 （一）基本假设 1．车辆在拐弯时的时间损耗忽略。 2．车辆在任意两站点中途不停车，保持稳定的速率。 3．只要平行于坐标轴即有街道存在。 4．无论垃圾量多少，都能在十分钟内装上运输车。 5．每个垃圾站点的垃圾只能由一辆运输车运载。 6. 假设运输车、铲车从A垃圾站到B垃圾站总走最短路线。 7. 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直角边之和。 8. 建设在运输垃圾过程中没有新垃圾入站。 9. 假设铲车、运输车载工作途中不发生意外也不遇到意外；