供应链网络的建立与破坏问题汇总Word文档下载推荐.docx
- 文档编号:815069
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:31
- 大小:338.44KB
供应链网络的建立与破坏问题汇总Word文档下载推荐.docx
《供应链网络的建立与破坏问题汇总Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《供应链网络的建立与破坏问题汇总Word文档下载推荐.docx(31页珍藏版)》请在冰点文库上搜索。
在文中应用Floyd算法和分治法,通过matlab,C++编程语言编程计算,成功从这49个城市中计算最短距离,并最终选择出了8个最优供应中心城市,并给出了最优供应链。
在此基础上,本文从破坏者的角度,利用matlab等数学工具、C++编程语言和二分法、分治法的思想,分析了在使总费用增加一定数目的情况下,最少需要破坏道路的数目和具体道路,给企业提供了防范破坏的依据。
然后本文进一步从道路被破坏有一定概率的情况下出发,利用数据之间有无相关性,分析出了破坏哪些道路能使平均费用增加最多这一问题,给企业提供了更可靠的防范破坏依据。
关键字:
供应链Floyd算法分治法图论相关性
供应链网络的建立与破坏问题
一、问题重述
现有某物流公司要在全国各城市之间建立供应链网络。
需要选定部分城市作为供应点,将货物运输到各城市。
通常每个供应点的货物是充足的,可以充分满足相应城市的需求。
设该公司考虑共考虑49个城市的网络,城市的坐标见表1。
城市之间的道路连接关系见表2。
在每个城市建立配送中心的固定费用和需求量表3,并假定作为供应点的城市其供应量可以满足有需要的城市的需求。
现将要建立一个供应网络,为各城市提供货物供应。
货物运输利用汽车进行公路运输。
设每吨每公里运输费用为0.5元。
现提出如下问题:
现在要从49个城市中选取部分城市做为供给点供应本城市及其它城市。
建立供给点会花费固定费用,从供应点运输到需求点会产生运输费用,要使总费用最小,问建立多少个供应点最好。
给出选中作为供应点的城市,并给出每个供应点供应的城市。
同时根据坐标作出每一个供应点到需求点的连接图。
假定有某组织对该供应网络的道路进行破坏。
并非所有的道路都可以被破坏,可破坏的道路见表4。
当某条道路被破坏后,该条道路就不能再被使用,以前运输经过该道路的只有改道,但总是沿最短路运输。
如果破坏方选取的策略是使对方总费用增加25%,而每破坏一条道路都需要成本和代价,因此需要破坏最少的道路。
问破坏方选取哪几条线路进行破坏。
给出具体的破坏道路和总费用。
假定各道路能否被破坏具有随机性,当某条道路被破坏后,该条道路就不能再被使用,以前运输经过该道路的只有改道,但总是沿最短路运输。
由于破坏方选取一些边进行破坏时,这些边不一定被破坏,而是服从一定的概率分布。
设可破坏的边及各边破坏的概率见表4。
运输时产生的费用可按照各种情况下的平均费用来考虑。
如果破坏方选取的策略是使对方平均总费用至少增加100%,同样需要破坏最少的道路。
问破坏方将选取哪几条线路进行破坏。
给出具体的破坏道路和平均总费用。
二、问题分析
根据题目条件可知,供应中心的选择由建设费用和运输费用共同决定,而题中已给出各个城市建设供应中心的费用,所以首先要解决的问题是计算出每两个城市之间的最小距离(如果两个城市之间无直达道路,可绕道而行),此问题可用floyd算法解决。
为了使选择供应中心时的权值统一,即权值的单位一样,需将距离权值转化为成本权值,因为每两个城市之间的最小路程已经计算出来,并且每个城市的需求量和每公里的运费已知,则可通过简单的程序将距离权值转化为成本权值,即计算出有供应关系的城市之间所花费的运费。
这样一来,就可以着手选择供应中心。
首先给每个城市选择理想供应中心城市。
所谓理想的供应中心城市是指满足以下条件的其他城市:
比如给第i个城市选择理想供应中心城市j,则
1.j城市的供应中心建设费用不是1000000000,即可用作供应中心。
2.j给i供给货物所花的路费应该小于在第i个城市建设供应中心的费用(若路费大于建设供应中心的费用,则摒弃从j城市为第i个城市供应的做法,直接在第i个城市建立供应中心)
这样经过初步筛选,可得到第i个城市的全部理想供应城市j。
在此基础上,可根据贪心算法的思想,结合matlab绘制出来的坐标地图,人为地将区域划分成小块。
在每一个小块内可人为地选择一个供应中心,此供应中心为其他被供应城市供应货物的运费相对较小。
由此确定出大致的供应中心城市数目。
编程,在28个城市中输入所有的可能组合,画出总费用变化图,得出最终的最优解。
问题一中已求解出了最优解,绘制出了供应关系图。
由题可知,可被破坏的道路只有9条,数目较少,在此基础上,利用二分法的思想和问题一中求总费用的程序进行试验,得到满足要求的被破坏道路。
问题三相对问题二而言只是给可破坏道路附加了一定的成功概率,因此要解决破坏哪些道路可使平均总费用增加最多这一问题,可利用问题二中的程序和部分数据。
由绘制出的供应关系图可知,许多被破坏的道路之间是没有影响的,即无相关性,它们共同被破坏产生的总费用期望可以直接由它们单独被破坏产生的总费用期望相加得到。
而小部分有影响、有相关性的道路可利用程序运行得出它们共同作用的产生的总费用期望。
三、模型假设与符号说明
(1)供应中心的选择是任意的,不受政治、地理、环境等因素的影响;
(2)各地交通条件相同,运输过程中不受交通条件的影响;
i——第i个城市;
j——对第i个城市来说为理想供应中心的城市;
mi——第i个城市建立配送中心的固定费用;
Ri——第i个城市的需求量;
Z——表示总费用;
Sji——为第i个城市供应货物的理想供应中心j到第i个城市的路程;
Sji,max——为第i个城市供应货物的运费不超过在第i个城市建立供应中心时的最大供应离;
Smin———每两个城市之间的最小距离
E——期望值
PA——A事件发生的概率
A——A事件发生
max——平均总费用增加值
四、模型的建立与求解
(1)Floyd算法
Floyd算法又称为弗洛伊德算法,插点法,是一种用于寻找给定的加权图中顶点间最短路径的算法。
Floyd算法的基本思想如下:
从任意节点A到任意节点B的最短路径不外乎2种可能,1是直接从A到B,2是从A经过若干个节点X到B。
所以,我们假设Dis(AB)为节点A到节点B的最短路径的距离,对于每一个节点X,我们检查Dis(AX)+Dis(XB)<
Dis(AB)是否成立,如果成立,证明从A到X再到B的路径比A直接到B的路径短,我们便设置Dis(AB)=Dis(AX)+Dis(XB),这样一来,当我们遍历完所有节点X,Dis(AB)中记录的便是A到B的最短路径的距离。
(2)分治法:
分治法字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
分治策略是:
对于一个规模为n的问题,若该问题可以容易地解决(比如说规模n较小)则直接解决,否则将其分解为k个规模较小的子问题,这些子问题互相独立且与原问题形式相同,递归地解这些子问题,然后将各子问题的解合并得到原问题的解。
这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题,1<
k≤n,且这些子问题都可解并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。
由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。
在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
4.1.2模型建立与求解
(1)运用Floyd算法计算出每两个城市之间的最小距离Smin
根据Floyd算法,用matlab工具编程,计算出每两个城市之间的最小距离。
(代码见附录)
每两个城市之间的最小距离:
distance.txt
(2)求每个城市的最大供应距离Sji,max
如果其它城市给第i个城市供应货物所花费的运输费用大于在i城市建设供应中心的固定花费,显然不如直接在第i个城市建设供应中心。
因此,每个城市存在一个最大供应距离Sji,max。
Sji,max=mi/(Ri*0.5)
用C语言编程得到最大供应距离:
(3)运用分治法和matlab,求出局部地区的可能最优解
a.求理想供应中心城市
给每个城市选择理想供应中心城市。
比如给第i个城市选择理想供应中心城市j,则
a)j城市的供应中心建设费用不是1000000000,即可用作供应中心。
b)j给i供给货物所花的路费应该小于在第i个城市建设供应中心的费用(若路费大于建设供应中心的费用,则摒弃从j城市为第i个城市供应的做法,直接在第i个城市建立供应中心)
由这些条件可知,只要满足Smin≤Sji,max的城市j均是第i个城市的理想供应中心城市。
用matlab编程得到每个城市的的理想供应中心城市。
见下表:
理想供应中心城市选择表
城市
最大供应距离Sji,max
小于最大距离的点——理想供应中心城市j
1
1824
3457101112141516171827283040434445
2
1000000000
134571011121314151617181920222324252627283040434445
3
1520
1457101112141516171827283040434445
4
135101112141516171827283040434445
5
134151617272830404344
6
7
1216
140
8
9
10
2128
134511121314151617181920222427283040434445
11
1012131415161743
12
13410111314151617181927434445
13
10111214151617181920434445
14
134510111213151617181920222324272830434445
15
2432
134571011121314161718192022232427283040434445
16
134571011121314151718192022232427283040434445
17
134510111213141516181920222324272830434445
18
134101112131415161719202223242527434445
19
134101112131415161718202223242527434445
20
1718192223242545
21
22
1416171820232425274445
23
22242745
24
171819202223252745
25
20222324
26
27
13457101112131415161718192022232425283040434445
28
2730
29
134571011121314151617181920222324252627283040434445
30
13451516272844
31
32
33
34
35
36
37
38
39
40
13457151643
41
42
43
1345101112131415161718274445
44
13410121415161718274345
45
341012141516171822232744
46
47
48
49
注释:
最大供应距离为1000000000表示该城市可由任意一个能够建设供应中心的城市为其供应货物
b.用分治法思想结合上表得到的局部分区图:
使用分治法的思想,若想总体费用最低,则局部的费用应该最低。
上表已经得到每个城市的理想供应中心,每个城市真实的供应中心应该从理想供应中心中选择。
因此可以人为地将所有城市分为8块区域,在每一个区域内存在一个供应中心为此区域内的其他城市供应货物。
(部分处于中间地区的城市分区不太明显,可属于周围的任一区域)
由上图可知供应中心城市应该有8个。
它们的可能为:
[11,23,26,28,7,4,19,45]
[11,23,26,28,7,4,20,45]
[11,23,26,28,7,3,19,45]
[11,23,26,28,7,3,20,45]
[11,23,26,28,40,4,19,45]
[11,23,26,28,40,4,20,45]
[11,23,26,28,40,3,19,45]
[11,23,26,28,40,3,20,45]
(4)编程验证最优解
用C++语言编程,此程序功能为:
任意输入i个城市作为供应中心,输出以这些城市为供应中心所产生的总费用Z。
经过比较以上8组可能的最优解所产生的总费用,得出[4,7,11,20,23,26,28,45]这一组的总费用最低这一结论。
综上,[4,7,11,20,23,26,28,45]即为最优解。
用matlab绘制出供应关系图如下:
其中红色的点代表供应中心,箭头代表运输方向。
总费用:
Z=9197114(元)
4.2.1模型的建立与求解
本题的目标是破坏最少的道路产生至少25%的总费用增加,即△Z≥9197114*25%=2299278.5。
由供应关系图可知,在可破坏的9条道路中,破坏第6条和第8条对总费用没有影响。
因此只从1,2,3,4,5,7,9号道路中选择被破坏道路。
应用问题二中的程序,只需更改被破坏道路的数据,即可得到破坏后的总费用。
先从破坏一条道路开始尝试,结果见下表:
只破坏一条道路时的所有结果:
被破坏道路序号
破坏后的总费用Z1
总费用增长△Z
9288422
91278
10278283
1081139
9232301
35157
9395652
198508
9578739
381595
9411764
214620
9274129
76985
由表可知,当破坏一条道路时所产生的的总费用增长远远小于2299278.5元,因此从破坏7条道路开始尝试。
全部破坏时的结果:
破坏后的总费用Z1(元)
总费用增长△Z(元)
1,2,3,4,5,7,9
11612962
2415848
满足要求,继续尝试破坏6条道路的情况。
破坏六条道路后的所有结果:
2,3,4,5,7,9
11448400
2251286
1,3,4,5,7,9
10387766
1190652
1,2,4,5,7,9
11577775
2380661
1,2,3,5,7,9
11343651
2146537
1,2,3,4,7,9
11039008
1841894
1,2,3,4,5,9
11398312
2201198
1,2,3,4,5,7
11343618
2146504
其中,破坏1,2,4,5,7,9号道路满足要求。
继续运行程序,当破坏5条道路时没有满足条件的道路,因此,破坏方案为:
[1,2,4,5,7,9]
Z=11577775
4.3.1模型的建立与求解
a.根据供应关系图分析道路之间的相关性
由供应关系图可知,大部分道路都不在一个小的子区域内。
若不在一个小区域内,则其产生的影响是不相关的,即具有直接加和性。
在此现象的基础上,进行验证。
被破坏的道路序号
单条道路相加
有无相关性
91308
1081169
35187
198538
381625
9197114
214650
77015
1,2
10442815
1245701
1172477
有
2,3
10313440
1116326
无
2,4
10547564
1350450
1279707
2,7
10492903
1295789
2,5
10659878
1462764
2,9
10355268
1158154
1,7
9503042
305928
1,5
9670017
472903
1,3
9323
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 供应 网络 建立 破坏 问题 汇总