【国家级精品课程】中南大学数学建模lingomatlab优化建模数模培训全国赛论文货物运输问题

1、中南大学2008年暑期数学建模培训，第一次训练题我们参赛选择的题号是（从a/b/c/d中选择一项填写）： b 我们的参赛报名号为（如果赛区设置报名号的话）： 20004006 所属学校（请填写完整的全名）： 中南大学 参赛队员 (打印并签名) ：1. 钟 逸 2. 黄贵杰 3. 王树松 指导教师或指导教师组负责人 (打印并签名)： 日期： 2008 年 8月 5 日货物运输问题摘要本文对货物运输问题进行了研究并建立了模型。根据题意确定为图论、网络优化模型。对于问题1：寻求从2-10的最短路经。以v2为出发点，对附表1中的矩阵作行列变换（第二行第二列与第一行第一列交换）然后运用dijkstra算

2、法给出了从v2到其他各个点的最短路径，并运用matlab软件编写程序求出从v2到v10最短路径如图1表1所示。其最短路线：2-3-8-9-10总的行程为30+25+10+20=85为所求的最短行使路线。 对于第二问：从提货点出发遍行每个客户最后回到起点，类似旅行者问题。运用哈密顿算法给出“至少包含图g中每个顶点一次的最短回路”，具有最小总长度的哈密顿回路一定为推销问题的最优解，但反之结论不成立。从哈密顿回路中找出本问题中最短的行驶路线，通过matlab编写程序，计算得到一条从提货点出发，经过所有的点，又回到提货点，最优的路径，其结果为152348769101，最短路程为25+15+30+15+

3、20+30+25+35+20+35=250。对于第三问用两辆载重50单位的车运货，要求所走的路程和最短，可以借用第二问已经得出的模型，在进行模型的改进，在最短的循环中再插入一个起始点，从而形成两个循环，这领个循环的路径分别为：15234891 ；1 769101，由于都经过第9点，第一辆车可选择载重4050；第二辆可选择载重3646；且满足载重之和为86。第一辆路程为：135；第二辆路程：145；和路程为280。对于第四问每辆货车载重为25。各点所需的货物量同第三问，可知派车数目至少为四辆，每辆派车费100元，载货行使1元/公里。首先类似第一问运运用dijkstra算法给出了从v1到其他各个点

4、的最短路径，见图2、表2。根据约束条件结合图形。给出配车方案：共需四辆车。第一辆：载货15；载货行使路线：143；载货行使距离：55；耗费：100+55=155元；第二辆：载货25；载货行使路线：176；载货行使距离：55；耗费：100+55=155元；第三辆：载货21；载货行使路线：1910；载货行使距离：70；耗费：100+70=170元；第四辆：载货25；载货行使路线：1528或者15852；载货行使距离：100；耗费：100+100=200元；总共耗费：155+155+170+200=680元。 本文所建立的模型适用范围较广能比较精确解决一般问题。但对于更复杂、数据量更庞大的问题，求解

5、起来会比较吃力。关键字 图论 最短路径 哈密尔顿回路 dijkstra算法 模拟退火算法 一、问题重述随着经济的发展、交通网络的不断健全。运输行业得以快速发展，运输公司在满足客户要求与尽量减少成本（时间、金钱）之间面临更复杂决策。某运输公司为10个客户配送货物，已知提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）已知。用下面矩阵中的位置上的数表示（其中表示两个客户之间无直接的路线到达）。（见附表1）需解决的问题：（1）运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，给运送员设计一个到客户10的尽可能

6、短的行使路线 。（2）运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，给出货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。（3）因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析。（4）如果改用更小容量的车，每车容量为25个单

7、位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用），给出如何安排车辆能使得运输公司运货的总费用最省？二、问题假设与符号说明（一）问题假设1、不考虑塞车现象；2、不考虑运输车出现故障或事故对其运输量的影响；3、附录1中矩阵的一项i到j的距离。（二）符号说明1、g=（n，e）表示一个有向图2、v=（i=1.2.3.10）表示1、2、3.10十个客户；3、e=(i、j=1.2.3.10)表示第i个客户与第j个客户之间的边集：其中0表示从i不能直接到j；4、w= （i=1.2.3.10）表示第i个客户所需要的货物量（点

8、上权重）.（第三、四问用到）；5、和分别表示自点1到点j和点k的最短有向路的长度，而表示弧（k，j）的长度，6、t有向图中的部分点集三、问题分析（一）背景分析 随着经济的发展、交通网络的不断健全。运输行业得以快速发展，运输公司在满足客户要求与尽量减少成本（时间、金钱）之间面临更复杂决策。某运输公司为10个客户配送货物，已知提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）已知。用下面矩阵中的位置上的数表示（其中表示两个客户之间无直接的路线到达）。（见附表1）（二）解题分析 第一问为最短路径问题，用dijkstra算法可解，第二问类似旅游推销员问题、采用模拟退火算法解答四

9、、问题一建模（一）问题提出 运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，给运送员设计一个到客户10的尽可能短的行使路经 。（二）问题分析 寻找给定起、终点v2、v10.的最短路径，道路长定义为各条边的权之和。考虑到可以用有向图求最短路径问题进行模型求解，在这里可以采用dijkstra算法来求本题的最短行驶道路。（三）建模（模型一）（为方便编程 将附表1的矩阵第一行第一列与第二行第二列交换。）跟据dijkstra算法：最短有向路满足以下条件，可以写成：=0=+ ,j=2,3,4,，10具体算法如下：第一步（开始）置u1=0

10、，=，j= j=2,3,4,，10，p1,t= j=2,3,4,，10第二步（指出永久标号）在t中寻找一点k，使得=置p=pk，t=t-k。若t=终始，否则进行第三步。第三步（修改临时标号）对t中每一点j，置=min+然后返回第一步。matlab软件编程程序输出结果如下（d表示点2到其他各点的最短距离）输出结果：d = 0 50 30 45 35 50 45 55 65 85index1 = 1 3 5 4 7 2 6 8 9 10index2 = 1 1 1 3 1 1 5 3 8 9结果示意图：图1：v2v1v3v4v5v6v7v8v9v10050303550605045355080559

11、0比较v4，v7504550455590比较v1，v65050558590558590659085v2v2v2v3v2v2v5v3v8v90503045355045556585v4v1v6v7v5v2v8v9v3v10 图1从上图可以知道v2到各个点的最短路径，其中v2到v10的最短路径为v2 v3 v8 v9 v10其最短路程为30+25+10+20=85，用matlab软件编程计算得到的结果完全吻合。可以说明这种方法可行。（部分源程序代码见附录2） 五、问题二建模 （一）问题提出 运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，给出货车从提

12、货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？（二）问题分析 本问题是一个求最短路径的问题，但是必须考虑走遍每个客户，并把货物送到每个客户的手中，即每个客户都要走一遍，并且要回到原来的送货点，考虑到最短的回路可能只有一条，即寻找一条哈密顿回路，找到最短的哈密顿回路。（三）建模（模型二） 哈密尔顿回路：包含g图中每个顶点只有一次的回路；具有最小总长度的哈密尔顿回路一定是推销员问题的最优解，但反之则不一定成立。任取一个哈密顿回路，所有顶点集表示为=，。在一个最优解中运送员离开顶点后，或通过不在中的某一顶点，或通过中的某一顶点。当时后者情况时，在送货员离开顶点后，有可能去不

13、在中的另一个顶点，如此等等，但是最优解一定存在于下述各图中。1、图g具有所有被删除去的边（v，y），y2、图g具有所有被删除去的边（v，y），y；以及所有被删去的边（，z），z；3、图g具有所有被删除去的边（，y），（，y），y，以及所有被删去的边（，z），z；4、图g具有所有被删除去的边（，y），（，y），（，y），y，以及所有被删去的边（，z），z；分别称上述各图为，。由于在每个带下标图中的一条弧长不会小于相应在图中相应弧长的长度，在图中一个最优的哈密顿回路的长度也不可能小于图中一个最优的哈密顿回路的长度。而且，图的一个最优解至少也是带下标的图，中的一个最优解。重复做下去，直到最终找到最短

14、的哈密顿回路图，此时其他的回路图已经全部被删除（i）对于，构造新的hamilton圈: ,它是由中删去边和，添加边和而得到的。若，则以代替，叫做的改良圈。（ii）转（i），直至无法改进，停止。分析以上得到线性规划如下：min f（ ）通过matlab编写程序，计算得到一条从提货点出发，经过所有的点，又回到提货点的最优行使路径，其输出结果为： q = 99999circle = 1 5 2 3 4 8 7 6 9 10 1sum = 250从输出的结果很容易得到最短的行使路径为：152348769101，最短路程为25+15+30+15+20+30+25+35+20+35=250。（部分源程序代

15、码见附表3）六、问题三建模（一）问题提出 因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析（二）问题分析 假设车行至i点给客户的货物需给足除非车上载货不足。需考虑每个客户对货物量的需求，为此引入点权重（i=1.2.3.10）不需考虑时间问题。问题可等效于一辆容重50个单位的车跑两次：路径遍历每一点。寻找一条最短路径且满足每位客户

16、需要的货物量。从v1出发经过每个点然后回到v1.在模型二的基础上增加量的约束路径的约束。（三）建模对于路径：v1v1.v1前后半段路经过的各点运送货物之和均769101；15234891。路程分别为135和145；总路程为280。七、问题四建模（一）问题提出 改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用），给出如何安排车辆能使得运输公司运货的总费用最省？（二）问题分析 目标函数是 总费用 z=100x+yx:出车数量y：所有车辆载货行使的总路程（三）建模（模型四）1.货物

17、在1点，除第一点外其余9点所需货物之和为86，每辆车载重25，故至少要4辆车。且不考虑空车返回的费用。所以用dijkstra算法（程序见附录4）计算出1点到各点最短的距离：首先类似第一问，运用dijkstra算法计算出1点到各点最短的距离（具体参见模型一和附录）结果如下： d 0 40 55 40 25 55 30 55 50 70index1 = 1 5 7 4 2 9 3 6 8 10index2 = 1 2 4 1 1 7 1 5 1 9其中d表示从起始点到i点的最短距离，index2表示从1点到i最短路径上i点前一点的标号。结果如下表： 表2v1v2v3v4v5v6v7v8v9v100

18、50 402530504040 853055508040854055 555080比较v2，v4 (70)/555555 8055 70 70 v1v5v4v7v1v7v1v5v1v9040554025553055507011097584236 图2从图可以知道1点到各个点的最短距离。其中143路线的路程为：40+15=55，需要运送的货物量为：9+6=15176路线的路程为：30+25=55，需要运送的货物量为：10+15=251910路线的路程为：50+20=70，需要运送的货物量为：12+9=21158路线的路程为：25+30=55，需要运送的货物量为：7+5=12152路线的路程为：2

19、5+15=40，需要运送的货物量为：7+13=20；经过对158和152两条路线的分析，由于所需货物总和为25恰好是一辆货车最大载重量。结合个点之间的路径距离；比较求出载货行使的最短路径为1528或者15852；载货行使的长度为100； 根据上述分析结果得出车辆分配如下： 共需四辆车。第一辆：载货15；载货行使路线：143；载货行使距离：55；耗费：100+55=155元；第二辆：载货25；载货行使路线：176；载货行使距离：55；耗费：100+55=155元；第三辆：载货21；载货行使路线：1910；载货行使距离：70；耗费：100+70=170元；第四辆：载货25；载货行使路线：1528或

20、者15852；载货行使距离：100；耗费：100+100=200元；总共耗费：155+155+170+200=680元；八、模型评价与模型推广 模型一，运用dijkstra算法得到v2到其他各点的最短路径，将第二行、第二列同第i行第i列交换即可得到第i点到其他各点的最短路径。不足在于到目标仅需求两点之间最短路径时，得到是到各点的最短路径求出些多余量。模型二，运用形变问题的fleury算法得到从1点行遍所有的点，再从10返回1点，该模型应用性强，可以应用到循环旅行，及循环购物等众多现实问题，本模型的缺点是不适合大数据量的运算。模型三，运用模型二而所得到的结论，在进行分析，有一定的局限性，可以推广

21、到权数比较简单的分配问题，本模型也不适合大数据量的问题。模型四，类似模型一先运用dijkstra算法得出v1到各个点的最短路径，结合个约束条件分析筛选出最优方案。方法较普通适用范围较广。九、参考文献1.姜启源.数学模型（第三版）. 北京：北京高等教育出版社，20052.吴 翊 吴孟达. 数学建模的理论与实践. 长沙：国防科技大学出版社，19993.周义仓 赫孝良. 数学建模实验. 西安：西安交通大学出版社，20004.赵东方. 数学模型与计算. 北京：科学出版社，20075.王冬琳. 数学建模及实验. 北京：国防工业出版社，20046.楼顺天 于 卫. matlab程序设计语言. 西安：西安电

22、子科技大学出版社，1999附录 附表1附录2 clear;clc;m=10000;a(1,:)=0,50,30,m,35,50,m,60,m,m;a(2,:)=zeros(1,2),m,40,25,m,30,m,50,m;a(3,:)=zeros(1,3),15,m,30,50,25,m,60;a(4,:)=zeros(1,4),45,30,55,20,40,65;a(5,:)=zeros(1,5),60,10,30,m,55;a(6,:)=zeros(1,6),25,55,35,m;a(7,:)=zeros(1,7),30,45,60;a(8,:)=zeros(1,8),10,m;a(9,:

23、)=zeros(1,9),20;a(10,:)=zeros(1,10);a=a+a;pb(1:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=m;d(1)=0;temp=1;while sum(pb)=2 index=index(1); end index2(temp)=index;endd, index1, index2 输出结果：d = 0 50 30 45 35 50 45 55 65 85index1 = 1 3 5 4 7 2 6 8 9 10index2 = 1 1 1 3 1 1 5 3 8 9

24、附录3行遍的编程clc,clearq=99999a(1,2)=50;a(1,3)=q;a(1,4)=40;a(1,5)=25;a(1,6)=q;a(1,7)=30;a(1,8)=q;a(1,9)=50;a(1,10)=q;a(2,1)=50;a(2,3)=30;a(2,4)=q;a(2,5)=35;a(2,6)=50;a(2,7)=q;a(2,8)=60;a(2,9)=q;a(2,10)=q;a(3,1)=q;a(3,2)=30;a(3,4)=15;a(3,5)=q;a(3,6)=30;a(3,7)=50;a(3,8)=25;a(3,9)=q;a(3,10)=60;a(4,1)=40;a(4,

25、2)=q;a(4,3)=15;a(4,5)=45;a(4,6)=30;a(4,7)=55;a(4,8)=20;a(4,9)=40;a(4,10)=65;a(5,1)=25;a(5,2)=15;a(5,3)=q;a(5,4)=45;a(5,6)=60;a(5,7)=10;a(5,8)=30;a(5,9)=q;a(5,10)=55;a(6,1)=q;a(6,2)=50;a(6,3)=30;a(6,4)=30;a(6,5)=60;a(6,7)=25;a(6,8)=55;a(6,9)=35;a(6,10)=q;a(7,1)=30;a(7,2)=q;a(7,3)=50;a(7,4)=q;a(7,5)=1

26、0;a(7,6)=25;a(7,8)=30;a(7,9)=45;a(7,10)=60;a(8,1)=q;a(8,2)=60;a(8,3)=25;a(8,4)=20;a(8,5)=30;a(8,6)=55;a(8,7)=30;a(8,9)=10;a(8,10)=q;a(9,1)=20;a(9,2)=q;a(9,3)=q;a(9,4)=40;a(9,5)=q;a(9,6)=15;a(9,7)=25;a(9,8)=45;a(9,10)=20;a(10,1)=35;a(10,2)=20;a(10,3)=10;a(10,4)=45;a(10,5)=20;a(10,6)=q;a(10,7)=60;a(10,8)=q;a(10,9)=30;a=a+a;c1=1 2:10 9;l=length(c1);flag=1;while flag0 flag=0; for m=1:l-3 for n=m+2:l-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n