数学模型（线路设计问题）高手进

2010数学模型期终考试试题
考试说明：
1、建立模型，求解模型，形成论文，论文格式仿照全国赛格式，请务必写上学号和姓名；
2、以小组(人数小于等于3)或个人为单位上交论文；
3、论文上交截时间：
信工，物理，机械： 由张老师决定；
数学院学生：第16周周一上午（2010-6-14）9:50-10:10；
过期不交，成绩为0；
4、只用上交纸质打印版的论文，请在附录中附上论文中用的代码；
5、论文上交地点：
信工，物理，机械： 由张老师决定；
数学院学生：上数学模型课课时直接交；或者主楼B103 实验中心；
6、发现雷同论文，雷同论文成绩一律为0。
最优线路设计
某货运公司，仓库地点见图1中的红色小圆圈，某送货员需将一批货物从仓库送至城市内各目的
地。 76个位置的坐标见表3，编号为1的点是出发点，编号2-76的点是目的地，散点图见图1：红色*
号的是编号2-41目的地。蓝色*号是剩下的目的地。
1．如果76个位置之间的任意连线都是通路，请设计送货线路，使送货距离最短，并用画图的方
式展示所求结果。
2．如果相互通路信息如图2所示，请设计送货线路，使送货距离最短，并用画图的方式展示所求
结果。
3．在第2问的基础上，如果每次最多带40个目的地货物，而且排序在前面的目的地必须优先送
货，请设计送货路线，使送货距离最短，并用画图的方式展示所求结果。
4．如果要求算法在普通PC上求结果不超过两分钟，请给出你的算法代码。
图1送货示意图
图2相互联系信息
表3：坐标信息
序号X坐标Y坐标
1 3600 2300
2 3100 3300
3 4700 5750
4 5400 5750
5 5608 7103
6 4493 7102
7 3600 6950
8 3100 7250
9 4700 8450
10 5400 8450
11 5610 10053
12 4492 10052
13 3600 10800
14 3100 10950
15 4700 11650
16 5400 11650
17 6650 10800
18 7300 10950
19 7300 7250
20 6650 6950
21 7300 3300
22 6650 2300
23 5400 1600
24 8350 2300
25 7850 3300
26 9450 5750
27 10150 5750
28 10358 7103
29 9243 7102
30 8350 6950
31 7850 7250
32 9450 8450
33 10150 8450
34 10360 10053
35 9242 10052
36 8350 10800
37 7850 10950
38 9450 11650
39 10150 11650
40 11400 10800
41 12050 10950
42 12050 7250
43 11400 6950
44 12050 3300
45 11400 2300
46 10150 1600
47 13100 2300
48 12600 3300
49 14200 5750
50 14900 5750
51 15108 7103
52 13993 7102
53 13100 6950
54 12600 7250
55 14200 8450
56 14900 8450
57 15110 10053
58 13992 10052
59 13100 10800
60 12600 10950
61 14200 11650
62 14900 11650
63 16150 10800
64 16800 10950
65 16800 7250
66 16150 6950
67 16800 3300
68 16150 2300
69 14900 1600
70 19800 800
71 19800 10000
72 19800 11900
73 19800 12200
74 200 12200
75 200 1100
76 200 800
有意者密我，，图发不上去！！谢谢密我我把图发给您，，谢谢