供应网络地建立与道路破坏问题

1、wordword23/23word供给网络的建立与道路破坏问题摘要本文针对供给链网络的建立与道路破坏问题，运用Floyd算法、0-1整数规划、遍历法等多种方法，借助Lingo、Matlab等软件，综合分析了49个城市的供给链网络的相关数据，建立了线性规划模型、影响度模型以与优先选择模型，得到了城市运输供给链中最优供给点与破坏道路时破坏程度不同情况下的最优破坏方案。针对问题一，由于49个城市中某些城市的建站费用过高，不适合建立供给点。将这些城市剔除后共有28个城市可以作为供给点。通过题中所给的数据运用floyd算法，借助MATLAB软件求出每个城市到其他城市的最短距离，然后写出目标函数与相应的约

2、束条件,采用0-1整数规划法建立现行规划模型,使用Lingo软件得到建立8个供给点费用最少，供给点城市编号分别为4、7、11、20、23、26、28、45。针对问题二，研究破坏道路的方案，使对方平均总费用增加25%,将被破坏的道路间的距离改成一个很大的值，近似看作这条路是不通的。运用floyd算法，借助MATLAB软件求出道路破坏后供给点城市与各城市之间的最短距离，再建立目标函数与约束条件，建立影响度模型，运用Lingo软件得出道路破坏后的最短运输路线，进一步得到破坏后的运输费用，与破坏前费用相减可以得到道路破坏后增加的费用，当使总费用增加25%时最少破坏道路的序列号为1、2、4、5、7、9，

3、总费用增加11577797元。针对问题三，主要研究的是破坏尽可能少的道路来使对方平均总费用至少增加100%，供给点的基建费用是固定不变的，决定平均总费用的只是运输的平均总费。所以求运输的平均费用其实就是根据相应的概率分布求运输费用的期望值。由于有8条道路可以被破坏，所以可以给出255种道路破坏方案。由于破坏方选取一些道路进展破坏时，这些道路不一定被破坏，而是服从一定的概率分布，可以根据上面的分析建立优先选择模型，运用MATLAB编写相应的求平均总费用的程序来求出各种方案的平均总费用，107元。 最后，对本文解决问题的方法和模型进展推广，分析了在其他领域的应用，并且综合评价了模型的优缺点。关键词

4、：供给链网络；道路破坏；0-1整数规划；Floyd算法；LINGO1问题的重述全球化竞争的加剧促使越来越多的企业开始采用供给链管理策略，以实现企业的一体化管理。供给链是一个复杂的网状结构系统，每一局部都面临着各种潜在的风险，任何一局部出现问题都可能给整个供给链带来严重的影响，因此如何分析、评价和提高供给链系统的可靠性变得日益迫切。设施系统是供给链的核心，在供给链研究中有着极其重要的地位。在一个设施系统中，某些个设施由于自然灾害或者其他因素的影响可能失效，例如911恐怖袭击事件、2004年的印度洋海啸、2008年的汶川地震等都对诸多行业的设施系统造成了严重的破坏。现有某物流公司要在全国各城市之间

5、建立供给链网络。需要选定局部城市作为供给点，将货物运输到各城市。通常每个供给点的货物是充足的，可以充分满足相应城市的需求。设该公司考虑共考虑49个城市的网络，并假定作为供给点的城市其供给量可以满足有需要的城市的需求。现将要建立一个供给网络，为各城市提供货物供给。货物运输利用汽车进展公路运输，。1.49个城市的网络坐标详见表1；2.城市之间的道路连接关系详见表2；3.每个城市建立配送中心的固定费用和需求量详见表3；4.可破坏的道路详见表4。1.现在要从49个城市中选取局部城市做为供给点供给本城市与其它城市。建立供给点会花费固定费用，从供给点运输到需求点会产生运输费用，要使总费用最小，问建立多少个

6、供给点最好。给出选中作为供给点的城市，并给出每个供给点供给的城市。同时根据坐标作出每一个供给点到需求点的连接图。2.假定有某组织对该供给网络的道路进展破坏。并非所有的道路都可以被破坏，可破坏的道路见表4。当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。如果破坏方选取的策略是使对方总费用增加25%，而每破坏一条道路都需要本钱和代价，因此需要破坏最少的道路。问破坏方选取哪几条线路进展破坏。给出具体的破坏道路和总费用。3.假定各道路能否被破坏具有随机性，当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。由于破坏

7、方选取一些边进展破坏时，这些边不一定被破坏，而是服从一定的概率分布。设可破坏的边与各边破坏的概率见表4。运输时产生的费用可按照各种情况下的平均费用来考虑。如果破坏方选取的策略是使对方平均总费用至少增加100%，同样需要破坏最少的道路。问破坏方将选取哪几条线路进展破坏。给出具体的破坏道路和平均总费用。2问题的分析通过对题目所提供的49个城市的运输供给链数据进展分析，运用Floyd算法求出每个城市到其他城市的最短距离，再根据题意列出目标函数与相关的约束条件，利用Lingo程序求解出最优解。对于对供给网络的道路进展破坏问题中，由于破坏程度不同，即破坏的成功率并不一定是百分之百，当破坏是百分之百时，把

8、该条路的距离改成一个很大的值，将得到的新数据运用Floyd算法求出每个城市到其他城市的最短距离，然后给出相应的约束条件建立模型求满足条件的最优解。假如破坏不是百分之百时，即破坏服从一定的概率时，根据相应的概率分布求运输费用即为运输的平均费用，利用Matlab程序得到满足条件的最优解。对问题1的分析问题一研究的主要是从49个城市中找到适当数量的供给点来使运输费用和基建费用的总费用达到最低。我们可以先通过题中所给的数据运用floyd算法求出每个城市到其他城市的最短距离，然后给出相应的约束条件,运用Lingo软件进展求解,即可得出确定的供给点,使总费用达到最低。最后根据选中作为供给点的城市的坐标作出

9、每一个供给点到需求点的连接图。对问题2的分析问题二主要研究的是破坏尽可能少的道路来使总费用增加25%,于是可以假设当某条道路被破坏时，把该条道路的距离改成一个很大的值，这样就可以近似的看成这个道路是不通的。当某条道路被破坏时，根据新得到的数据用floyd算法重新求出各城市到其他城市的最短距离，然后求出其他没有供给点的城2市距离最近的供给点与其之间的距离，最后就可以求出当该道路被破坏时的总费用。然后给出相应的约束条件，建立模型求当总费用增加25%时破坏的道路数量最少的情况，这样就求出了最少的道路数和具体的道路与总费用。对问题3的分析问题三主要研究的是给出适当的破坏道路的方案，对方平均总费用至少增

10、加100%，平均总费用由建造供给点的基建费用和各种情况下运输的平均费用组成，当给出道路破坏的方案后，由于8个供给点是固定的，所以建造供给点的基建费用是不变的，变化的是运输的平均费用。由于破坏方选取一些道路进展破坏时，这些边不一定被破坏，而是服从一定的概率分布。所以求运输的平均费用其实就是根据相应的概率分布求运输费用的期望值。由于有6条道路可以被破坏，所以可以给出64种道路破坏方案。由于破坏方选取一些道路进展破坏时，这些道路不一定被破坏，而是服从一定的概率分布，所以有种情况，在种的情况下运输费用的期望值就是运输的平均总费用。根据上面的分析建立模型，求出各种方案的平均总费用，最后就可以得到相应的方

11、案使得在破坏道路最少的情况下平均总费用达到最大。3模型的假设1假设各道路能否被破坏具有随机性；2假定所有城市之间均可以通过公路运输进展物资运输；3假设问题二中对任意道路破坏的成功率为百分之百；4假设各城市的需求量固定不变；5假设在运输网络简单设期间和某组织破坏期间不会遭遇地震，海啸等自然灾害的影响；6所有数据来源真实可靠。4名词解释与符号说明1.供给链网络：供给链网络是由与核心企业相连的成员组织构成的，这些组织直接或间接与他们的供给商或客户相连，从起始端到消费端。必须分类并确定哪些成员对公司以与供给链的成功起着决定作用，以便对它们给予关注和合理分配资源。1：是一种物流结点，它不以贮藏仓库的这种

12、单一的形式出现，而是发挥配送职能的流通仓库。也称做基地、据点或流通中心。配送中心的目的是降低运输本钱、减少销售机会的损失，为此建立设施、设备并开展经营、管理工作1。3.floyd算法：floyd HYPERLINK baike.baidu./view/7420.htm t _blank 算法又称为 HYPERLINK baike.baidu./view/8789410.htm t _blank 弗洛伊德算法、插点法，是一种用于寻找给定的 HYPERLINK baike.baidu./view/606176.htm t _blank 加权图中顶点间 HYPERLINK baike.baidu./

13、view/349189.htm t _blank 最短路径的算法。通过一个图的权值 HYPERLINK baike.baidu./view/10337.htm t _blank 矩阵求出它的每两点间的 HYPERLINK baike.baidu./view/349189.htm t _blank 最短路径 HYPERLINK baike.baidu./view/10337.htm t _blank 矩阵，从图的带权 HYPERLINK baike.baidu./view/549589.htm t _blank 邻接矩阵开始， HYPERLINK baike.baidu./view/96473.

14、htm t _blank 递归地进展n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；以此类推，最后又用同样的公式由D(n-1)构造出 HYPERLINK baike.baidu./view/10337.htm t _blank 矩阵D(n)。 HYPERLINK baike.baidu./view/10337.htm t _blank 矩阵D(n)的i行j列元素便是i号顶点到j号顶点的 HYPERLINK baike.baidu./view/349189.htm t _blank 最短路径长度，称D(n)为图的 HYPERLINK bai

15、ke.baidu./view/2039125.htm t _blank 距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。符号符号说明0-1变量，判断第i个城市是否建立供给点0-1变量，判断从第i个城市是否给第j个城市配送货物在第i个城市建立供给点的固定费用第j个城市的货物需求量第i个城市到第j个城市的最短路径代表i条可以破坏的路0-1变量，判断是否破坏第i条路道路破坏前的总费用道路破坏后的总费用道路破坏前后的增加的总费用平均总费用运输的平均费用8个供给点基建费用5模型的建立与求解对于问题一，研究的主要是从49个城市中找到适当数量的供给点与其位置来使运输费用和基建费用的总费

16、用达到最低。总费用由运输费用和基建费用组成,随着选取供给点的数量的增多,运输费用减小,但基建费用会随之增加,很明显,这是一个0-1规划问题。我们先通过题中所给的数据运用floyd算法求出每个城市到其他城市的最短距离，然后给出相应的约束条件,运用Lingo软件进展求解,即可得出确定的供给点,使总费用达到最低。最后根据选中作为供给点的城市的坐标作出每一个供给点到需求点的连接图。从49个城市中选取n个作为供给点，一共是有种方案，但由于某些城市的建站费用过高，不适合建立供给点，我们将这些城市剔除后共有28个城市可以作为供给点，再运用MATLAB软件编程见程序1，画出各城市之间道路关系图如图1所示图中1

17、-49为各城市编号。图1 各城市之间道路关系图通过对问题的分析与数据的整理可以根据Floyd算法2-3求出任意两个城市之间的最短公路长度，得到一个4949的矩阵Cij，根据表2中的数据对Cij进展初始化，假如从i市到j市有直达路径，如此将表格中的数据赋给Cij,否如此将付给Cij，然后用Floyed算法求出从i市到j市的最短路径。Floyed算法思想如下：1i=1;j=1;k=1;2u=Cik+ Ckj,假如uCij,如此令Cij=u，否如此直接转到3。3假如j49,如此令j=j+1，转到2；否如此转到4。4假如i49，如此令i=i=1，转到2；否如此转到5。5假如ka(i,k)+a(k,j)

18、a(i,j)=a(i,k)+a(k,j);path(i,j)=k;endendendenda, path程序3:sets: weizhi/1.49/:x,jijian,xuqiu; assign(weizhi,weizhi):D,l; endsetsdata: jijian=ole(C:UsersAdministratorDesktop数据源,cost); xuqiu=ole(C:UsersAdministratorDesktop数据源,need); D=ole(C:UsersAdministratorDesktop数据源,shortestpath); enddatamin=sum(weizh

19、i(k):x(k)*jijian(k)+sum(weizhi(j):sum(weizhi(i):xuqiu(j)*D(i,j)*l(i,j)*0.5; for(weizhi(i):bin(x(i); for(assign(i,j):bin(l(i,j);for(weizhi(j):sum(weizhi(i):l(i,j)=1);for(weizhi(i):for(weizhi(j):l(i,j)=x(i);End程序4:A=3639 3712 3488 3326 3238 4196 4312 4386 4177 3918 4061 3780 4029 3676 3715 3429 3507 3

20、394 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;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

21、 2509 3305 1069 702 696 737 971 1603 2285 2613 2920 3374 2710 2055 1893 1633 2290 2749 919 261;a=26,28,23,20,4,45,7,11;x1=A(1,a);y1=A(2,a);b=1,2,3,5,6,8,9,10,12,13,14,15,16,17,18,19,21,22,24,25,27,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,46,47,48,49;x2=A(1,b);y2=A(2,b);plot(x1,y1,o,MarkerFace

22、Color,b),hold on, plot(x2,y2,o)text(3639,2685 ,1)text( 3639 , 2685 , 2 );text( 3712 , 2601 , 3 );text( 3488 , 2465 , 4 );text( 3326 , 2444 , 5 );text( 3238 , 2771 , 6 );text( 4196 , 2956 , 7 );text( 4312 , 3210 , 8 );text( 4386 , 3430 , 9 );text( 4177 , 1756 , 10 );text( 3918 , 1821 , 11 );text( 406

23、1 , 1630 , 12 );text( 3780 , 1788 , 13 );text( 4029 , 1162 , 14 );text( 3676 , 1422 , 15 );text( 3715 , 2322 , 16 );text( 3429 , 2092 , 17 );text( 3507 , 1624 , 18 );text( 3394 , 1357 , 19 );text( 3439 , 799 , 20 );text( 2935 , 760 , 21 );text( 3140 , 450 , 22 )text( 2769 , 1508 , 23 );text( 2545 , 1643 , 24 );text( 2778 , 1174 , 25 );text( 2370 , 1025 , 26 );text( 1304 , 1688 ,