第14届西北工业大学数模校赛A题论文Word文档格式.docx
《第14届西北工业大学数模校赛A题论文Word文档格式.docx》由会员分享，可在线阅读，更多相关《第14届西北工业大学数模校赛A题论文Word文档格式.docx（20页珍藏版）》请在冰点文库上搜索。
二、问题的分析
（一）问题1的分析
现在要从49个城市中选取部分城市作为供应点供应本城市及其他城市。
问题1属于一个多目标规划的问题，就是使所求供应点固定费用最少以及从供应点运输到需求点产生的运输费用最少。
供应点固定费用与所求供应点的城市有关，而从供应点运输到需求点产生的运输费用，与供应点的个数、供应点到城市的距离、以及需求城市的需求量有关。
我们可以将总目标费用最少首先建立一个多目标规划的数学模型，然后建立一个目标最优化模型。
（二）问题2的分析
该问题是在问题一供应链网络的建立的基础下，某组织对该供应链网络的道路进行破坏，这是一个模拟退火问题。
由表4的道路破坏及概率情况可知，最多有九种可能，要求破坏最少的道路，并且使对方总费用增加25％。
我们可以采用局部搜索，利用邻域函数进行搜索，若找到一个比现有值更优的解就放弃前者而取后者。
（三）问题3的分析
该问题表面上看是问题一和问题二的综合，其实际情况比其综合还要复杂。
在该问题中道路的破坏不仅具有随机性，而且破坏还服从一定的概率分布，同时运输时产生的费用还要按照各种情况下的平均费用来考虑。
这是一个目标最优化以及模拟退火模型的综合问题，本题的难点在于如何随机地、更好地满足题目所要求的概率分布，从而达到使对方平均费用最大。
我们可以在问题二模型的基础上，对其进行修改，使其满足确立的目标。
三、模型的假设
假设1：
题目所给的数据真实可靠；
假设2：
作为供应点的城市其供应量可以满足有需要的城市的需求；
假设3：
某些城市做配送中心的固定费用太高不考虑在供应点城市之中；
假设4：
各城市之间运输货物仅仅与城市之间的距离有关，而不考虑其他因素的影响，并且各供应点间的运输是相互独立的。
四、符号说明
符号
说明
Z
供应链网络建立的总费用
Q
固定费用
P
运输路程
W
需求量
n
供应点的个数
i
供应点城市的序号
j
需求点城市的序号
Y
运输总费用
G
计算总运费的有向赋权图
单个道路被破坏后的总费用
各条道路的破坏概率
C（k）
平均总费用
k
具体的破坏道路序号
注：
其他符号将在下文中给出具体说明
五、模型的建立与求解
5.1问题一：
关于供应链网络的建立模型
5.1.1问题一的模型准备工作
由问题分析和假设3可知，在49个城市中能作为供应点城市的最多有28个， 而从供应点运输到需求点产生的运输费用，与供应点的个数、供应点到城市的距离、以及需求城市的需求量有关。
根据表一各城市的坐标可用Matlab作出如下图一的散点图，其中可作为供应点的城市用红色的点表示：
图一
5.1.2.问题一模型的建立
1、模型思想
首先，设有n个供应点，分别向（49-n）个城市供应货物，供应点城市可为自身供应货物，所以供应点城市只需计算固定费用，现最多有n*（49-n）个决策变量，设固定费用为Q，路程为P，需求量为W。
然后计算从供应点运输到需求点产生的运输费用：
其与供应点的个数、供应点到城市的距离、以及（需求点）城市的需求量有关。
将每个城市看做一个图的顶点，各城市之间的公路看作此图对应顶点间的边，各条公路的长度乘以需求量乘以0.5看作对应边上的权，所给各城市坐标以及城市之间的里程表就转化为加权网络图，即在给定的加权网络中选中作为供应点的城市以及它所要供应的城市，使得总权最小。
2、模型建立
（一）、根据题目所要求费用最小可建立如下的多目标规划问题：
其中设运费函数为
（0〈n≤28）
（二）、利用Matlab编出如下所需要求的程序：
即就是取出n个城市，这n个城市为供应点城市（i），再对这n个城市重新排序（1≤i≤n）；
对剩下（49-n）个需求点城市（j）进行重新排序。
再用
≤a,a为一个固定费用界限，来约束第二个函数的取值。
（3）、Kruskal算法求运输费用：
（其简单思想如下）
1）选择边
，使得
尽可能小；
2）若已选定边
则从
中选取
，使得：
.
3）当第2）步不能继续执行时，则停止。
5.1.3.问题一模型的求解和结论
通过利用Matlab和图论软件包进行编程分别求出了供应点城市的个数，以及每个供应点所供应的城市坐标图（如图二所示），并且求出了最小费用。
图二
n=8时，总费用Z=9197117.50000元
3、模型改进：
第一问我们运用了目标最优化模型，，以及在处理最短运费的问题上用了图论中的有向赋权图的思想来解决最优化问题，用固定费用函数提出一个可供选择的范围，把该目标函数作为约束条件而被排除出目标组，进入约束条件组中，总运费函数即为目标函数。
但是对于该模型我们可以运用目标规划的方法，得到的结果可能会更合理。
先对模型中的每一个目标函数赋予一个优先因子和权系数，已知模型中有K（K=2）个目标函数，假定有L个优先级（L≤2），目标规划模型的数学形式为：
式中：
di+和di－分别表示与fi相应的、与fi*相比的目标超过值和不足值，即正、负偏差变量；
pl表示第l个优先级；
lk+、lk-表示在同一优先级pl中，不同目标的正、负偏差变量的权系数。
5.2第二问：
关于道路破坏问题的模型
5.2.1.模型思想
该问题是在问题一供应链网络的建立的基础下，在某组织对该供应链网络的道路进行破坏的背景下，利用模拟退火算法求解全局最优解。
由如下表4的道路破坏及概率情况可知，最多有九种可能，我们可以先采用局部搜索，利用邻域函数进行搜索，若找到一个比现有值更优的解就放弃前者而取后者，从而达到全局最优解。
表4破坏道路及概率
道路序号
城市1
城市2
破坏概率
1
4
5
0.6
2
3
0.7
7
40
0.45
10
11
0.5
19
20
0.55
6
24
25
0.4
17
45
8
21
49
9
5.2.2.模型建立
设总费用Z是关于破坏的道路的条数m的函数（0≤m≤9），由第一问的结果得
Z（0）=9197117.50000元,
随着破坏道路条数m的不同，函数值Z（m）也会不同
设函数值Z（m）的增量为
若
>
0则接受m作为新的当前解，
5.2.3模型求解
对于上述的模拟退火算法，可以运用数学软件Lingo，通过编写程序来进行求解，得到最终破坏的三条线：
道路3、道路4、道路5，以及如下图三所示的新的配送中心位置及配送路线图。
图三
破坏上述三条线后的总费用为：
11615959.4025元。
5.3第三问：
关于道路破坏问题的模型
5.3.1模型思想
该问题同样是在问题一供应链网络的建立的基础下，对道路进行破坏，破坏具有随机性，且服从一定的概率分布，这是一个目标最优化以及模拟退火模型的综合问题，我们可以在问题二模型的基础上，对其进行修改，使其满足确立的目标。
5.3.2模型的建立
首先利用模拟退火算法算出费用最大值的m值（同问题二算法）
随着破坏道路条数m的不同，函数值Z（m）也会不同
若
0则接受m作为新的当前解，算出使Z值最大的m值，以及具体的破坏道路。
基于以上基础，设具体的破坏道路序号为k,总费用对应某一条单个道路被破坏以后的函数为
，（0≤k≤9），各条道路的破坏概率为
则平均总费用C（k）可以表达为：
5.3.4模型的求解
根据第二问的模拟退火算法，结合第三问的题目优化算法，利用Matlab软件计算得到破坏道路的最优化方案，示意图如下：
图四
最优化方案为除八外全部破坏，计算得到平均总费用为9559434.96667元。
5.3.5模型二和模型三的比较与分析
模型三是在模型二的基础上进行了修改，使其满足确立的目标。
即就是运用模型二所采用的模拟退火算法，再建立了一概率性模型，可以发现两种情况下，概率模型得出的结果比确定性模型得出的结果要大，即假设模型三要求的是总费用而不是平均费用，模型三的结果肯定较多。
究其原因，模型三所增加的概率模型考虑了破坏道路的随机性，而且还服从一定的概率分析，同时运输所产生的费用是按照各种情况下的平均费用来考虑，从而得到一个分布，用仿真模拟的方法得出具体的破坏路线。
虽然根据问题二模型得出的结果比问题三增加的概率模型小很多，但是不能就此认为问题二得出的结果更可取，实际上模型三的建立更加符合实际生活，更加接近真实情况，因此认为模型三所增加的概率模型的结果更加可靠。
6、模型的优缺点分析
1.模型的优点
（1）建立的多目标规划模型有成熟的理论基础，有相应的软件支持，可信度高，而且还利用了数据库知识、图论方法和模拟退火算法建立了模型，对三个问题做了明确的回答。
（2）文中有大量的网络结构图，这些图直观、可靠、可信度强，而且有很强的说服力，对数据的分析处理细致到位。
（3）在解决问题三时，运用了第一问和第二问的模型方法，按照已知的概率分布来平衡所建立的函数之间的关系。
2.模型的缺点
模型假设比较理想化，与实际情况存在加大的差距；
问题一所建立的模型决策变量太多，运算量太大，运算时间过长。
7、模型的推广应用
（1）对于供应链网络的问题，在供应链环境下,每个企业节点都面临着面向下游区域市场的产品组合优化问题。
所以供应链网络的建立与合理运用有着广泛的应用价值，也会带来一定的资金节约。
（2）在第二问对于总运费的求解问题上，我们运用了有向赋权图的方法解决了n的取值问题，而在实际生活中我们常利用图论知识寻找制定两点最短路径。
尽可能快速的解决实际问题。
（3）本文在解决问题二时，运用了模拟退火算法，模拟退火算法是一种适合解决大规模组合优化问题的算法，特别是在现代的计算机科学、图像处理、超大规模集成电路设计、生物学等科学领域中的组合优化问题，所以有广泛的应用价值。
八、参考文献
[1]姜启源，谢金星，叶俊.数学建模（第三版）.北京：
高等教育出版社，2003。
[2]楼顺天，陈生潭，雷虎民.Matlab5.X程序语言设计.西安：
西安电在科技大学出版社，2000。
[3]刘三阳，马建荣，杨国平.线性代数.北京：
高等教育出版社，2009。
九、【附录】
附录一：
表1各城市坐标
编号
城市
坐标X（公里）
坐标Y（公里）
北京
3639
2685
天津
3712
2601
石家庄
3488
2465
太原
3326
2444
呼市
3238
2771
沈阳
4196
2956
长春
4312
3210
哈尔滨
4386
3430
上海
4177
1756
南京
3918
1821
杭州
4061
1630
12
合肥
3780
1788
13
福州
4029
1162
14
南昌
3676
1422
15
济南
3715
2322
16
郑州
3429
2092
武汉
3507
1624
18
长沙
3394
1357
广州
3439
799
南宁
2935
760
海口
3140
450
22
重庆
2769
1508
23
成都
2545
1643
贵阳
2778
1174
昆明
2370
1025
26
拉萨
1304
1688
27
西安
3007
2030
28
兰州
2562
2244
29
西宁
2381
2324
30
银川
2788
2509
31
乌市
1332
3305
32
台北
4263
1069
33
香港
3538
702
34
澳门
3470
696
35
深圳
3526
737
36
厦门
3928
971
37
宁波
4201
1603
38
青岛
4016
2285
39
大连
4089
2613
通辽
4296
2920
41
白城
4095
3374
42
海拉尔
4512
2710
43
徐州
3751
2055
44
南阳
3334
1893
宜昌
3229
1633
46
延安
3054
2290
47
包头
3089
2749
48
柳州
3044
919
三亚
3053
261
表2各公路段及里程表
序号
距离（公里）
120
270
540
420
844
370
360
210
311
440
530
430
630
720
1521
186
330
387
727
230
429
347
819
280
190
840
279
160
660
680
598
325
880
640
153
610
650
435
1020
490
266
592
860
50
51
361
52
349
53
54
550
55
473
56
285
57
380
58
406
59
362
60
780
61
1010
62
508
63
664
64
710
65
580
66
130
67
127
68
688
69
560
70
71
820
72
305
73
74
340
75
76
1090
77
910
78
795
79
990
80
2170
81
920
82
83
84
2320
85
1940
86
2672
87
700
88
89
637
90
304
91
92
500
93
1980
94
554
95
96
591
97
368
98
99
929
100
669
101
466
102
541
表3各城市作配送中心的固定费用
费用（元）
需求量（吨）
1123584
1232
1000000000
974
733400
965
272080
358
169480
223
715
457824
753
989
1391
663936
624
411616
677
370120
487
580032
636
526680
495
733248
603
876736
721
760608
834
585504
642
955776
786
693
156
2475320
3257
684608
1126
276640
364
403560
531
31008
941184
774
196384
323
194
114760
151
10000
升级会员 