供应链网络的建立与道路破坏问题讲解.doc
《供应链网络的建立与道路破坏问题讲解.doc》由会员分享，可在线阅读，更多相关《供应链网络的建立与道路破坏问题讲解.doc（28页珍藏版）》请在冰点文库上搜索。
2013高教社杯全国大学生数学建模竞赛
承诺书
我们仔细阅读了《全国大学生数学建模竞赛章程》和《全国大学生数学建模竞赛参赛规则》（以下简称为“竞赛章程和参赛规则”，可从全国大学生数学建模竞赛网站下载）。
我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛章程和参赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛章程和参赛规则，以保证竞赛的公正、公平性。
如有违反竞赛章程和参赛规则的行为，我们将受到严肃处理。
我们授权全国大学生数学建模竞赛组委会，可将我们的论文以任何形式进行公开展示（包括进行网上公示，在书籍、期刊和其他媒体进行正式或非正式发表等）。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）：
C
我们的参赛报名号为（如果赛区设置报名号的话）：
所属学校（请填写完整的全名）：
河南科技大学
参赛队员（打印并签名）
指导教师或指导教师组负责人（打印并签名）：
（论文纸质版与电子版中的以上信息必须一致，只是电子版中无需签名。
以上内容请仔细核对，提交后将不再允许做任何修改。
如填写错误，论文可能被取消评奖资格。
）
日期：
2013年8月27日
赛区评阅编号（由赛区组委会评阅前进行编号）：
2013高教社杯全国大学生数学建模竞赛
编号专用页
赛区评阅编号（由赛区组委会评阅前进行编号）：
赛区评阅记录（可供赛区评阅时使用）：
评
阅
人
评
分
备
注
全国统一编号（由赛区组委会送交全国前编号）：
全国评阅编号（由全国组委会评阅前进行编号）：
供应链网络的建立与道路破坏问题
摘要
全球化竞争的加剧促使越来越多的企业开始采用供应链管理策略，以实现企业的一体化管理。
供应链是一个复杂的网状结构系统，每一部分都面临着各种潜在的风险，任何一部分出现问题都可能给整个供应链带来严重的影响，因此如何分析、评价和提高供应链系统的可靠性变得日益迫切。
对于问题一：
问题一是一个优化问题，经过对题意和附表数据的分析，首先通过floyd算法用matlab编程算出任意两个城市间的最短距离，然后建立0—1规划模型，运用lingo编程进行求解，我们得到了需要建立的8个供应点和最小的基建费用及运输费用之和。
八个供应点依次为城市4、7、11、20、23、26、28、45，最小总费用为9197118元。
具体的分配方案见文中表1。
对于问题二：
问题二是破坏方对供应链进行破坏，在使对方损失费用达到总费用的条件下选择破坏最少的道路进行破坏。
首先考虑选择破坏一条道路计算破坏此条道路产生的附加费用，以产生的增加费用作为该道路的价值。
破坏方优先选择破坏价值最大的道路，在破坏最大价值道路后仍不满足要求，则保证破坏道路不变的情况下评估剩余道路价值，再优先增加其中最大的道路进行破坏。
经过lingo和matlab编程计算，最终计算得到破坏的道路为：
2、5、7、4、1、9。
对于问题三：
问题三和问题二相似，问题三是在服从一定的概率下，要求破坏道路后是使对方运输平均总费用增加100%，如何选择最少的道路进行破坏，对于平均总费用，可以建立两种定义即:
一、平均总费用理解各条道路均被考虑下增加的道路运输费用；二、平均总费用理解为仅考虑被破坏后受影响道路增加的运输费用。
经计算可得结果为：
定义一、除道路序号8以外的其它8条道路全部被破坏的平均总费用为2668656.5元；定义二、仅破坏道路序号2就满足，其平均总费用为570434元。
关键字：
0-1规划模型最短路优先选择matlablingo
问题重述
全球化竞争的加剧促使越来越多的企业开始采用供应链管理策略，以实现企业的一体化管理。
供应链是一个复杂的网状结构系统，每一部分都面临着各种潜在的风险，任何一部分出现问题都可能给整个供应链带来严重的影响，因此如何分析、评价和提高供应链系统的可靠性变得日益迫切。
设施系统是供应链的核心，在供应链研究中有着极其重要的地位。
在一个设施系统中，某些个设施由于自然灾害或者其他因素的影响可能失效，例如911恐怖袭击事件、2004年的印度洋海啸、2008年的汶川地震等都对诸多行业的设施系统造成了严重的破坏。
现有某物流公司要在全国各城市之间建立供应链网络。
需要选定部分城市作为供应点，将货物运输到各城市。
通常每个供应点的货物是充足的，可以充分满足相应城市的需求。
设该公司考虑共考虑49个城市的网络，城市的坐标见表1。
城市之间的道路连接关系见表2。
在每个城市建立配送中心的固定费用和需求量表3，并假定作为供应点的城市其供应量可以满足有需要的城市的需求。
现将要建立一个供应网络，为各城市提供货物供应。
货物运输利用汽车进行公路运输。
设每吨每公里运输费用为0.5元。
现提出如下问题：
现在要从49个城市中选取部分城市做为供给点供应本城市及其它城市。
建立供给点会花费固定费用，从供应点运输到需求点会产生运输费用，要使总费用最小，问建立多少个供应点最好。
给出选中作为供应点的城市，并给出每个供应点供应的城市。
同时根据坐标作出每一个供应点到需求点的连接图。
假定有某组织对该供应网络的道路进行破坏。
并非所有的道路都可以被破坏，可破坏的道路见表4。
当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。
如果破坏方选取的策略是使对方总费用增加25%，而每破坏一条道路都需要成本和代价，因此需要破坏最少的道路。
问破坏方选取哪几条线路进行破坏。
给出具体的破坏道路和总费用。
假定各道路能否被破坏具有随机性，当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。
由于破坏方选取一些边进行破坏时，这些边不一定被破坏，而是服从一定的概率分布。
设可破坏的边及各边破坏的概率见表4。
运输时产生的费用可按照各种情况下的平均费用来考虑。
如果破坏方选取的策略是使对方平均总费用至少增加100%，同样需要破坏最少的道路。
问破坏方将选取哪几条线路进行破坏。
给出具体的破坏道路和平均总费用。
问题分析
对于问题一主要是解决从49个城市中找到适当数量的供应点及其位置来使运输费用和基建费用的总费用达到最低的问题。
经分析，总费用由运输费用和基建费用组成，对题目中条件的分析可得，可以将其看作是0-1规划问题。
首先通过对题中数据进行整理，运用floyd算法求出每个城市到其他城市的最短距离，然后设立相应的约束条件，运用lingo进行求解，即可得确定的供应点。
最后可根据作为供应点城市的坐标和matlab作出每一个供应点到需求点的连接图。
对于问题二主要是研究破坏方选择那几条道路使对方总费用增加25%，而且使破坏道路数最少。
经分析，当第8（21-49）条路被破坏时，49号城市就无法供应货物，则不成立。
由于可供破坏方选择的道路的价值不同，所以可先由单个道路破后的最少运输费用作为评价标准来评估这8条路的价值，由大到小排列，选取价值最大的道路作为首选，再次以之前的破坏道路的基础上，再次评定其他各个道路的价值，选取次大的目标道路。
依次往下，直至破坏后的总运输费用达到破坏前的25%为止。
对于问题三主要研究当破坏道路具有随机性时，如何使破坏道路数最小时使破坏后的总运输费用增加100%。
经分析可得，即使在破坏一定能成功的情况下，破坏后的总费用也不能达到100%。
所以所谓的平均费用只能理解为每条道路上的平均运输费，可根据问题二的算法，在破坏服从一定的概率分布情况下，重新对各个道路进行评估，确定大小顺序，由此确定出能达到原运输费二倍的路径。
模型假设
1、在问题二的解决中，由于破坏道路序号8（21—>49），49城市将没有其他道路进行连通，而且货物单价未知，供货商损失的费用，不可计算，所以我们假设此道路不被破坏。
2、道路被破坏后，改道总是按最短路运输，其他供应点不分担原供应点的供应任务，即仍由原供应点沿最短路运输。
3、运输网络内的所有道路都是畅通无阻的。
4、两城市之间除了公路，没有其他的运输方式。
5、供应点的城市可以满足其所供应的有需要的城市需求。
6、需求城市的需求量在一段时间内需求不变。
7、假设某条边被破坏时，可以把该条边改为一个很大的值代替。
8、各个道路的破坏是随机的。
符号说明
第个城市是否向第个城市提供货物
是否在第个城市建立供货点
任意两个城市到间的最短路径矩阵
在第个城市建立供货点的固定费用
第个城市的需求量
模型建立及求解
对于问题一
数据预处理：
首先根据题中所给的城市的坐标和各个城市之间的距离用matlab将道路绘制图如下：
构造一个49*49的矩阵，根据表2中的数据对进行初始化，若从到有直线路径，则将路径数据赋给，否则将赋给，然后用floyed算法求出从到的最短路径。
通过floyed算法得到任意两个城市到间的最短路径，得到一个49*49的数据阵，矩阵如附录（下表是其中的一部分8*8）。
0
120
270
480
540
799
1129
1359
120
0
370
580
660
919
1249
1479
270
370
0
210
740
1069
1399
1629
480
580
210
0
530
1279
1609
1839
540
660
740
530
0
1339
1669
1899
799
919
1069
1279
1339
0
330
560
1129
1249
1399
1609
1669
330
0
230
1359
1479
1629
1839
1899
560
230
0
Floyed算法思想如下：
输入：
带权邻接矩阵
（1）赋初值：
对所有
（2）更新
对所有若则
（3）若，停止。
否则，转
（2）.
模型建立：
约束条件的确定:
由于第个城市只能接受一个供应点的货物，则可得：
（1）
对于是否在该城市建立供货点，则
对于任意城市，若不在此建立供货点，则若在此建立供货点，则，则可得下式：
（2）
目标函数的确立：
经过对题目的分析，可以确定所需总费用的目标函数如下;
则可得0-1整数线性规划模型为：
模型求解:
用lingo可解得：
供货点及该点供货的城市如下表：
表1:
供货分配表
编号
供货点城市
供货的城市
1
4
1,2,3,4，5,15,16，27,46,47
2
7
6,7，8,39,40,41,42
3
11
9,10,11，12,13,32,36,37,38,43
4
20
19,20，21,24,25,33,34,35,48,49
5
23
22，23
6
26
26
7
28
28,29,30,31
8
45
14,17,18,44,45
用matlab编程结合几何画板得出每个供货点城市到需要该点提供货物的城市的路线图如下：
按照lingo计算的结果得出，可建立8个供货点：
4，7,11,20,23,26,28,45
最小总费用为
元
表2：
供货点固定花费
供应点
4
7
11
20
23
26
28
45
总和
建立花费的费用
272080.00
457824.00
411616.00
526680.00
684608.00
31008.00
196384.00
243808.00
2824008.00
对于问题二
经对问题的分析可知若对第8条道路（21-49）进行破坏时，则49号城市则完全得不到货物供应，要使49号城市有充分的货物供应，就考虑在49号城市建立供应点，由于在题中的表中在此建立供应点的费用为1000000000，也就是说不能在此建立供货点。
在这种情况下没有数学讨论的意义,故在此不予考虑。
1、首先只破坏一条道路时，可以对这8条道路进行价值评估，即:
分别单独破坏这八条道路用matlab和lingo计算出各个道路的价值根据各个道路价值的大小，对各个道路进行由大到小的顺序排列如下表：
表三：
道路价值
优先破坏级
道路序号
价值
1
2
7454278
2
5
6754734
3
7
6587760
4
4
6571646
5
1
6464418
6
9
6450124
7
3
6408296
8
6
6373110
由此可以得到2号路段（3-4）的价值最大。
由问题的要求知道需满足的条件为：
2、然后可以在破坏2的基础上在对其他的七条路段进行价值评估（方法如上），找出第二次破坏的最大值，从而得出第二次优先破坏的路段为5号路段（19-20），依次可找出第三次、第四次、第五次、第六次、第七次、第八次破坏的路段可得出优先破坏顺序为:
表四：
破坏顺序
破坏道路数
破坏道路序号
破坏后运输总费用
损失增加率
1
2
7454278
11.76%
2
2、5
7835903
15.90%
3
2、5、7
8050553
18.24%
4
2、5、7、4
8319863
21.17%
5
2、5、7、4、1
8484425
22.96%
6
2、5、7、4、1、9
8753769
25.88%
7
2、5、7、4、1、9、3
8788956
26.27%
8
2、5、7、4、1、9、3、6
8788956
26.27%
由表可得当进行到第六次时：
则总费用为：
破坏的道路为：
道路序号2（3à4）、道路序号5（19à20）、道路序号7（17à45）
道路序号4（10à11）、道路序号1（4à5）、道路序号9（20à21）。
则可得在破坏后新的运输路的最短路径图：
对于问题三
在问题二中，我们由数据可知，在增加破坏道路序号6（24à25）,破坏后的总费用并未增加，因此在考虑破坏道路时，我们认为破坏此道路没有任何价值，故不考虑破坏此道路。
由于我们对“平均总费用至少增加100%”有两种不同的理解，故而我们给出了两种定义：
一、定义为破坏成功之后使对方增加的总费用（考虑了破坏概率）的平均值原计划总投入费用；
二、定义为破坏成功之后对应在每一条破坏道路上增加的费用的平均值（考虑了破坏概率）原计划在此道路上的投入费用。
（1）、按定义一来理解，我们可以由表求得原运输计划总投入费用，原运输计划总投入费用为各个路线原投入费用。
定义一：
平均总费用至少增加100%：
定义为破坏成功之后使对方
即：
由matlab和lingo得出数据如下表：
道路序号
破坏路线
原路程
原投入费用
1
4à5
530
136781
2
4à3
210
570434
3
7à40
429
67996.5
4
10à11
279
813939
5
19à20
710
705627
7
17à45
362
307374
9
20à21
560
66505
可得：
原运输计划总投入费用=2668656.5
再次由matlab和lingo得出未考虑破坏概率情况下的数据如下表：
破坏道路数
破坏道路序号
破坏后运输总费用
破坏后增加的费用
1
2
7454278
1081168
2
2、5
7835903
1462793
3
2、5、7
8050553
1677443
4
2、5、7、4
8319863
1946753
5
2、5、7、4、1
8484425
2111315
6
2、5、7、4、1、9
8753769
2380659
7
2、5、7、4、1、9、3
8788956
2415846
8
2、5、7、4、1、9、3、6
8788956
2415846
可知当不考虑破坏概率时，破坏8条道路时2415846<2668656.5
仍不能使成立。
那么，在考虑破坏概率之后，破坏后增加的费用期望会更低，更不满足使对方增加的总费用（考虑了破坏概率）的平均值原计划总投入费用。
即不能满足：
然而，我们未考虑道路序号8（21à49）的破坏，破坏道路序号8增加的费用未知，若考虑，假设使其损失增加则能达到要求，则：
此时破坏的道路为9条道路全部破坏，又因为道路序号6（24à25），破坏没有意义，因此破坏的道路最少次数为8。
分别为：
道路序号2（3à4）、道路序号5（19à20）、道路序号7（17à45）、道路序号3（7à40）、道路序号4（10à11）、道路序号1（4à5）、道路序号9（20à21）、道路序号8（21à49）。
（2）按定义二来理解，我们所比较的对象是此道路上的原运输计划总费用。
定义二：
破坏成功之后对应在每一条破坏道路上增加的费用的平均值（考虑了破坏概率）原计划在此道路上的投入费用。
即:
即：
同样，先考虑只破坏一条道路时：
求出
我们通过matlab和lingo的数据结果，进行数据处理，得到下面的表格：
道路序号
破坏路线
原投入费用
破坏后增加的费用
破坏概率
P
1
4à5
136781
1081168
0.6
80.07%
2
4à3
570434
1462793
0.7
152.83%
3
7à40
67996.5
1677443
0.45
23.29%
4
10à11
813939
1946753
0.5
12.23%
5
19à20
705627
2111315
0.55
29.75%
7
17à45
307374
2380659
0.5
55.13%
9
20à21
66505
2415846
0.6
69.48%
由表格可知，,只破坏道路序号2（4à3）就可以满足要求。
此时平均总费用为此道路的原投入费用，则平均运输费用为：
模型评价
模型优点:
在解决第一问时，建立了0-1整数规划，并用lingo很好的解决了问题。
对于问题二，采用了优先选择方法并结合matlab和lingo程序，使问题得到了简化。
对于问题三，充分考虑了平均费用的各种可能性，并论证了各种可能性的成立与否。
模型缺点：
对于问题二和问题三，由于总的可能性有200多种情况，可能没有遍历所有可能的结果，所以，这可能只是一个局部最优解。
参考文献
[1]薛毅《数学建模基础》，北京工业大学出版社，2004
[2]侯进军肖艳清谭敏高明柯《数学建模方法与应用》，东南大学出版社，2012
[3]林雪松周婧林德新《MATLAB7.0应用集锦》，机械工业出版社，2005
附录
问题一的lingo程序：
model:
sets:
weizhi/1..49/:
x,gufei,xuqiu;
assign（weizhi,weizhi）:
C,y;
endsets
data:
gufei=1123584100000000073340027208016948010000000004578241000000000100000000066393641161637012058003252668073324887673676060858550495577652668010000000002475320684608276640403560310089411841963841000000000114760100000000010000000001000000000100000000010000000001000000000100000000010000000001000000000289104100000000010000000007204806992002438081000000000100000000010000000001000000000;
xuqiu=12329749653582237157539891391624677487636495603721834642786693156325711263645315177432319415123424670155233174568761583317204272948115040122421736655;
C=？
;%由于数据庞大，不在此呈现
enddata
min=@sum（weizhi（k）:
x（k）*gufei（k））+@sum（weizhi（j）:
@sum（weizhi（i）:
xuqiu（j）*C（i,j）*y（i,j）））*0.5;
@for（weizhi（i）:
@bin（x（i）））;
@for（assign（i,j）:
@bin（y（i,j）））;
@for（weizhi（j）:
@sum（weizhi（i）:
y（i,j））=1）;
@for（weizhi（i）:
@for（weizhi（j）:
y（i,j）<=x（i）））;
End
Matlab程序：
#####散点图程序##############
x=[3639 3712 3488 3326 3238 4196 4312 4386 4177 3918 4061 3780 4029 3676 3715 3429 3507 3394 3439 2935 3140 2769 2545 2778 2370 1304 3007 2562 2381 2788 1332 4263 3538 3470 3526 3928 4201 4016 4089 4296 4095 4512 3751 3334 3229 3054 3089 3044 3053
];
y=[2685 2601 2465 2444 2771 2956 3210 3430 1756 1821 1630 1788 1162 1422 2322 2092 1624 1357 799 760 450 1508 1643 1174 1025 1688 2030 2244 2324 2509 3305 1069 702 696 737 971
升级会员 