第1个回答 2013-08-26
模型一：利用“图”的知识，将送货点抽象为“图”中是顶点，由于街道和坐标轴平行，即任意两顶点之间都有路。在此模型中，将两点之间的路线权值赋为这两点横纵坐标之和。如A（x1，y1），B（x2，y2）两点，则权值为Q=|x2-x1|+|y2-y1|。并利用计算机程序对以上结果进行了校核。经典的Dijkstra算法和
Floyd算法思路清楚、
方法简便,但随着配送点数的增加,计算的复杂性以配送点数的平方增加,并具有一定的主观性.
所以本研究在利用动态规划法的基础上引入扑食搜索法的原理,提高辆车的装载率,从而减少车辆的需求,达到降低成本的目的.
模型二：根据题意（B题），建立动态规划的数学模型。然后用动态规划的知识求得最优化结果。
根据所建立的两个数学模型，对满足设计要求的送货策略和费用最省策略进行了模拟，在有标尺的坐标系中得到了能够反映运送最佳路线的模拟图。最后，对设计规范的合理性进行了充分和必要的论证。
快递公司送货策略
1
问题的提出
在快递公司送货策略中，确定业务员人数和各自的行走路线是本题的关键。这个问题可以描述为:一中心仓库(或配送调度中心)
拥有最大负重为25kg的业务员m人,
负责对30个客户进行货物分送工作,
客户i
的货物需求为以知
,
求满足需求的路程
最短的人员行驶路径,且使用尽量少的人数,并满足以下条件:
1)
每条配送路径上各个客户的需求量之和不超过个人最大负重。
2)
每个客户的需求必须满足,
且只能由一个人送货.
3）每个业务员每天平均工作时间不超过6小时，在每个送货点停留的时间为10分钟，途中速度为25km/h。
4）为了计算方便，我们将快件一律用重量来衡量，平均每天收到总重量为184.5千克。
处于实际情况的考虑,
本研究中对人的最大行程不加限制.本论文试图从最优化的角度，建立起满足设计要求的送货的数学模型，借助于计算机的高速运算与逻辑判断能力，求出满足题意（B题）要求的结果。
2
问题的分析
2.
1根据题意（B题）的要求，每个人的工作时间不超过6小时，且必须从早上9点钟开始派送，到当天17点之前（即在8小时之内）派送完毕。
表一列出了题中任意两配送点间的距离。
表一：任意两点间的距离矩阵
因为距离是对称的，即从送货点i到送货点j的距离等于从j到i的距离。记作：di,j.
表二给出了产品的需求，为了完成配送任务，每个人在工作时间范围内，可以承担两条甚至更多的配送线路。表中给出了送货点编号，快件量T，以及送货点的直角坐标。
表二
对于上述的路线确定和费用优化问题，应用如下启发
从公司总部配出一个人，到任意未配送的送货点，然后将这个人配到最近的未服务的送货点范围之内的邻居，并使送货时间小于6小时，各送货点总重量不超过25kg。
继续上述指派，直到各点总重量超过25kg，或者送货时间大于6小时。最后业务员返回总部，记录得到的可行行程（即路线）。
对另一个业务员重复上述安排，直到没有未服务的送货点。对得到的可行的行程安排解中的每一条路径，求解一个旅行商问题，决定访问指派给每一条行程的业务员的顺序，最小化运输总距离。得到可行解的行程安排解后退出。
上面的方法通过以下两种方法实现：
（1）
每一个行程的第一个送货点是距离总部最近的未服务的送货点。用这种方法，即可得到一组运行路线，总的运行公里数，以及总费用。
（2）
每一个行程的第一个送货点是距离总部最远的未服务的送货点。然后以该点为基准，选择距它最近的点，加上约束条件，也可得到一组数据。
然后比较两组结果，通过函数拟合即可得到最优化结果。
3
模型假设
（1）假设每个人的送货路线一旦确定，再不更改。
（2）送货期间，每个人相互之间互不影响。
（3）如果到某一个点距离最近的点不至一个，就按下面的方法进行确定：考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但路线中各点总重量加上该点的快件量超过25kg的上限时，该点舍去。如距离4最近的点有2，5，6，7四个点，其中，0-1-3-4路线易确定，且各点重量之和为
19.5kg，因此对于2，7两点，直接舍去，选5最合适。
4
符号说明
A：所有配送点的集合，A={0，1，2，3，…….，n}，其中0代表配送中心
m:
业务员人数
C：任意一点到原点（总部）的距离
C总：表示一条路线所运行的总公里数
i,j:
表示送货点，如i点，j点
K：表示K条路线
qi:
点i的需求量，q0=0，表示总部的需求量
B总K:
K条路线的总运行费用
X：校核时的适应度
Xij:
业务员路线安排
5
模型的建立及求解
5.1
TSP模型的数学描述为：
其顶点集合为A
顶点间的距离为C={Cij|
i,j∈N,1≤i,j≤n}
m
n
min
∑
∑
CijXij
i=1j=1
满足
n
∑
Xij=1,ⅰi=1,2,⋯n
j=1
m
∑
Xij=1,j=1,2,⋯n
j=1
Xij∈{0,1},
i=1,2⋯n,j=1,2⋯n，而根据题意，任意两点之间都有通路，即不存在Xij=0的情况。
根据上述所列的启发式方法生成一个行程安排解。每一个行程的第一个送货点是距离总部最近的未服务的送货点。
第一条行程中访问了节点0-1-3-4-5-0，是因为1距离原点最近，因此由1
出发，3是距离1点最近的点，而且两处快件量之和为14kg，小于每个人最大负重量，可以继续指配。接着，4是距离3最近的点，而且三处快件量之和为
19.5kg，仍小于25kg,还可以继续指配。在剩下未服务送货点中，5距离4最近（其实距离4最近的点有2，5，6，7四个点，然后考虑该点需求的快件量，将其从大到小依次排列，快件量需求大者优先，但超过25kg上限的点舍去。这里2，7被舍去，故选择了5）总快件量之和为24kg。再继续扩充，发现就会超出“25kg”这个上限，因此选择返回，所以0-1-3-4-5就为第一条路线所含有的送货点。
现在0-1-3-4-5这四个送货点之间的最优访问路径安排就是一个典型的单回路问题。可以通过单回路运输模型-TSP模型求解。一般而言，比较简单的启发式算法求解TSP模型求解有最邻近法和最近插入法两种。由RosenkrantzStearns等人在1977年提出的最近插入法，能够比最近邻点法，取得更满意的解。由于0-1-3-0
已经先构成了一个子回路，现在要将节点4
插入，但是客户4有三个位置可以插入，现在分析将客户4插入到哪里比较合适:
1.插入到（0，1）间，C总=
7+4+5+1+4+9=30。
2.插入到（1，3）间，C总=5+6+4+9=24。
3.插入到（3，0）间，C总=5+4+4+11=24。
比较上述三种情况的增量，插入到（3，0）间和（1，3）间增量最小，考虑到下一节点插入时路程最小问题，所以应当将4插入到送货点3和总部0之间。接下来，用同样的方法，将5插到4和0之间，能使该条路线总路程最小，该路线总路程为32km，历时1.96667h。结果子回路为T=
{0-1-3-4-5-0}.因为街道平行于坐标轴方向，所以它就是最优化路线。
第二条行程这中，由于所剩下节点中，2距离0点最近，因此由2出发，就可以找到最近点13，接着是7，然后6.这样，第二条优化路线0-2-13-7-6-0就确定了。用这种方法，依次可确定以下剩余六条路线。
具体参看如下图表三（一，二，三，……为路线编号；总重量为该路线所有
节点快件量之和）：
由启发式方法得到的可行的行程安排解一：
表三
直观的具体路线图如下：
图一
然后，根据所经历的时间进行划分，确定运送人数。在工作时间小于6小时的前提下，可作如下分类：
这样，将确定的五种组合情况分别分配给五个业务员去送即可。
这个解是第一个中间最好解。在选择可行解1每条行程中的第一个送货点时，选择了距离总部最近的未服务的点。接下去通过选择距离仓库最远的未服务的点为每条行程的第一个客户生成了可行解2。为了方便遗传算法的分析，编号将连续进行。如果继续增加的新的标签的行程和前面可行解1
中的重复，就是用原先的标签号。
由启发式方法得到的可行的行程安排解二：
表四
直观的具体路线图如下：
图二
注意：通过上述方法，最后剩两个点1，9还没有被列入路线。于是问题就出来了，如何将这两个点插入进这八条路线？
除第十条路线之外，其余各条均能将9号点纳入，而1号点没有办法纳进去，只能作为第十七条路线出现。那么，9号点应纳入哪一条呢？显然，纳入第十六条比较合适，原因是他对总路程的大小没影响，顺便可以带上。
由此可以看到，可行解2没有替代中间最优解，以总路程518km,历时25.72h高于492km和24.68h。
通过对上面的两个可行解进行交叉操作。其中每个解的行程已经按照他们送每千克快件量在每一千米的路程范围内的送货成本的大小降序重新排列，这个参数是对每一行程质量的比较好的测度。本文以此作为适应值（X）。
在对两个解中的行程进行交叉分析时，根据适应值计算的接受每条行程的概率附加到每条行程上。P(X)=Ke-
λx
，然后通过设定参数对结果进行拟合。具体而言。如果一条行程的选择概率P(select)值至少和exel相应行的随机概率一样大，那么他就被选择出来可能在交叉分析中被包括进去。
在本题中，根据上述要求，求出了两种可行解，但是由于本题的特殊性（即街道和坐标轴平行），两条路径中没有相同的运行路线，也就是说最终的拟合结果就是解一的结果。因此，可行解一就是本题中的最优解。
至此，B题中的第一问已经解决了。即需要5个业务员，每个业务员的运行线路如下：
第一个人：0-1-3-4-5-0和0-18-26-28-0；
第二个人：0-2-13-7-6-0和0-19-25-24-0；
第三个人：0-10-12-8-9-0和0-16-17-20-14-0；
第四个人：0-22-32-23-15-11-0；
第五个人：0-27-29-30-0.
总的运行公里数为：C总K=32+42+42+72+68+56+88+92=492km。
5．2
下面我们求解B题中的第二个问题：
根据上面设计的最优化路线，容易算出每条路线运行费用及运行第二时间（这里的第二时间指的是在问题2中的新速度的前提下算出的）。具体参看下表五和表六：
表五
表六
从表五和表六的比较来看，解法二以总费用15241.3元和总时间27.36667h高于解一的12208.4元和26.26667h。因此我们选择了解一的优化结果。
从上表（表五）很容易看出：B总K=12208.4元。然后根据第二时间的大小，我对运行路线和人员个数做以下调整，具体参看表五。这样，就需六个人就才能完成任务。考虑到人员工作时间不能一边倒（即部分线路组合工作时间太长，部分太短）的情况，每个人的组合路线如下：
第一个人：0-1-3-4-5-0和0-19-25-24-0；
第二个人：0-2-13-7-6-0和0-10-12-8-9-0；
第三个人：0-16-17-20-14-0；
第四个人：0-22-32-23-15-11-0；
第五个人：0-18-26-28-0；
第六个人：0-27-29-30-0。
第2个回答 2013-08-22
层次分析法
层次分析法
层次分析法（Analytic
Hierarchy
Process,简称AHP法）是美国运筹学家沙旦（T.L.Saaty）于70年代提出的，是一种定性定量分析相结合的多目标决策分析方法。特别是将决策者的经验判断给予量化，对目标（因素）结构复杂且缺乏必要的数据情况下更为实用，所以近几年来此法在我国应用中发展较快。
一、
AHP法原理
例如某工厂在扩大企业自主权后，有一笔企业留成的利润，这时厂领导要合理使用这笔资金，根据各方面反映和意见，提出可供领导决策的方案有：（1）作为奖金发给职工；（2）扩建职工食堂、托儿所；（3）开办职工业余技术学校和培训班；（4）建立图书馆；（5）引进新技术扩大生产规模等等。领导在决策时，要考虑到调动职工劳动生产积极性，提高职工文化技术水平，改善职工物质文化生活状况等方面。对这些方案的优劣性进行评价，排队后，才能够做出决策。
面对这些复杂的决策问题，处理的方法是，先对问题所涉及的因素进行分类，然后构造一个各因素之间相互联结的层次结构模型。因素分类：一为目标分类，二为准则类，这是衡量目标能否实现的标准，三为措施类，是指实现目标的方案、方法、手段等。按目标到措施自上而下地将各类因素之间的直接影响关系排列于不同层次，并构成一个层次结构图，如附图1
目标层A
想要图先多给点分吧
准则层B
措施层P
附图1
层次结构图
构造好各类结构的层次结构图是一项细致的分析工作，要有一定的经验，根据层次结构图确定每一层的各因素的相对重要性的权数，直至计算出措施层各方案的相对权数，这就给出了各方案的优劣次序，以便领导决策，这个方法的原理是这样的：
设有n件物质A1，A2，A3，……,An;它们的重量分别为w1,w2,
……,wn,若将他们两两地比较重量，其比值可构成n*n矩阵A。
w1/w1
w1/w2
…w1/
wn
A=
w2/w1
w2/w2
…w2/
wn
(31)
…
…
…
…
wn/w1
wn/w2
…wn/
wn
A矩阵据有如下性质：若用重量向量
W=（w1，w2，…wn
）T
(32)
右乘A矩阵，得到
w1/w1
w1/w2
…w1/
wn
w1
w1
AW=
w2/w1
w2/w2
…w2/
wn
.
w2
=
n
w2
=n
W
(33)
…
…
…
…
…
…
wn/w1
wn/w2
…wn/
wn
wn
wn
即
(A-n1)W=0
(34)
由矩阵理论可知，W为特征向量，n为特征值。若W为未知时，则可根据决策者对物体之间两两对比的关系，主观作出比值的判断，或用Delphi法来确定这些比值，使A矩阵为已知，故判断矩阵记为A。根据正矩阵理论，可以证明：若A矩阵有以下特点（设aij=wi/wj）:
aij
=1
(35)
aij=1/aji(i,j=1,2,…n)
(36)
aij=aik/ajk(i,j=1,2,…,n)
(37)
则该矩阵具有唯一非零的最大特征值=λmax,且λmax=n.
若给出的判断矩阵A具有上述特征，则该矩阵具有完全一致性。然而人们对复杂
事物的各因素，采用两两比较时，比可能做到判断的完全一致性，而存在估计误差，这必然导致特征值及特征向量也有偏差。这问题由AW=n
W变成AW=λmaxW’,这就是由判断不相容而引起的误差。为了避免误差太大，所以要衡量A矩阵的一致性。当A矩阵完全一致时，因aij=1,
=
=n,
(38)
存在唯一的非零解λ=λmax
=n
而当A矩阵存在判别不一致时，一般是λmax≥n，这时，
λmax+
=
=n于是λmax=-
(39)
以其平均值作为检验判断矩阵一致性指标
C．I=(λmax-n)/(n-1)=
(40)
当λmax
=n，C．I=0，为完全一致；C．I值越大，判断矩阵的完全一致性越差，一般只要C．I≤0.1，认为判断矩阵的一致性可以接受，否则重新进行两两比较判断。判断矩阵的维数n越大，判断的一致性将越差，故应放宽对高维判断矩阵一致性的要求。于是引入修正值R.I,并取更为合理的C.R为衡量判断矩阵一致性的指标。
C.R=C．I/R.I
(41)
二、
标度
为了使各因素之间进行两两比较得到量化的判断矩阵，引入1-9的标度。根据心理学家的研究指出：人们区分信息等级的极限能力为7±2，特制定附录表2。可见n*n矩阵，只需要给出n(n-1)/2
个判断数值。除附表2的标度方法外，还可以用其他标度方法。
附表2
1-9的标度表
标度aij
定义
1
i因素与j
因素相同重要
3
i因素比j
因素略重要
5
i因素比j
因素较重要
7
i因素比j
因素非常重要
9
i因素比j
因素绝对重要
2，4，6，8
为以上两判断之间的中间状态对应的标度值
倒数
若j因素比i
因素比较，得到判断值为aji=1/aij,aii=1
第3个回答 2013-08-23
5个人完成4项工作任务。由于个人的技术专长不同，他们每人完成4项工作任务所用的时间如表所示。规定每人最多只能做一项工作，每项任务需且仅需一人操作。试求使花费总时间最小的分配方案。
人员编号
工作I
工作II
工作III
工作IV
1
12
7
9
7
2
8
9
6
6
3
7
17
12
14
4
15
14
6
6
5
4
10
7
10
第2题
最佳给药时机
众所周知，抗癌药在杀死癌细胞的同时对于自身也有毒副作用。其中，杀伤白细胞尤为严重。一般来说，白细胞在4000—10000个/mm3时为正常，低于4000个/mm3时则需要治疗，而低于1000个/mm3时就会危及生命了。所以，在癌症的治疗中一直伴随着“升血”治疗。“升血”是指给病人使用一些药物，以达到刺激骨髓造血、增加血液中白细胞数量的目的。
升血药是十分昂贵的，通常每25g为1900元。因而，合理地掌握使用升血药的时机，会为癌症的治疗节省大笔的金钱。附表是从北京胸部肿瘤研究所中选取的49个病案实例，描述了以不同的白细胞浓度x(单位：100个/mm3)作为给药起点，使白细胞恢复到正常所需的用药量y(单位：25g)。
请根据上述背景和附表的数据，指出最佳的给药时机。
编号
x
y
编号
x
y
编号
x
y
1
4
36
18
14
20
35
27
20
2
6
33
19
16
18
36
28
14
3
6
22
20
16
10
37
29
16
4
7
36
21
18
27
38
30
18
5
7
32
22
18
18
39
30
14
6
7
30
23
18
16
40
30
9
7
9
48
24
19
24
41
31
22
8
9
36
25
19
18
42
31
15
9
9
28
26
19
16
43
32
15
10
10
32
27
19
12
44
33
21
11
11
26
28
20
12
45
33
14
12
11
12
29
21
18
46
35
18
13
12
24
30
22
15
47
35
12
14
13
30
31
22
14
48
36
12
15
14
30
32
22
8
48
37
14
16
14
28
33
24
12
17
14
24
34
25
10
第3题
工作分配问题计算平均学分绩点
下面表格中是某学生所修各门课程的学分和成绩。请编写一个Matlab程序，计算出这名学生的平均学分绩点。
课程序号
学分
成绩
1
2.5
78
2
2.0
87
3
1.0
通过
4
3.5
80
5
1.0
89
6
6.0
81
7
1.0
优秀
8
2.0
90
9
2.5
91
10
2
优秀
11
2.0
82
12
2.0
90
13
3.0
75
14
1.0
良好
15
1.0
优秀
16
0.5
94
17
3.5
80
18
2.0
80
19
4.0
78
20
5.0
90
21
2.0
70
22
3.0
79
23
1.5
93
24
3.5
87
25
2.0
75
26
1
通过
27
4.0
90
28
1.0
良好
29
1.0
良好
30
3.0
90
31
0.5
90
32
2
74
33
1.0
76
34
2.5
80
35
3.5
76
36
2.0
86
37
4.0
78
38
3.0
88
39
4.0
83
40
0.5
通过
41
2.0
92
42
1.0
82
43
1.0
优秀
44
2
中等
45
0.5
96
46
1.0
76
47
1.5
通过
48
3.5
87
49
3.5
75
50
1
85
51
4.5
68
52
3.0
99
53
2.5
81
54
2.0
90
55
4
87
56
1.5
76
57
4.0
91
58
2.0
77
59
1.0
优秀
60
1.5
良好
61
0.5
93
62
1.0
通过
63
2.0
82
64
2.0
良好
65
2.0
良好
66
2.5
80
67
2.5
62
68
3.0
76
69
2.0
90
70
0.5
通过
71
2.0
83
72
1.0
优秀
73
2.5
63
74
0.5
87
75
2.5
87
问题补充：对齐不太好，大家见谅，补充一下，第三题里的通过中等良好优秀分别对应70，80，85，95，平均学分绩点计算方法为（学分×绩点
）／学分总数。绩点为五分制，100分对应5，60分对应1。不明白的Q543667530.谢谢各位了