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

目录一、问题重述 一、问题重述1.1问题背景全球化竞争的加剧促使越来越多的企业开始采用供应链管理策略，以实现企业的一体化管理。供应链是一个复杂的网状结构系统，每一部分都面临着各种潜在的风险，任何一部分出现问题都可能给整个供应链带来严重的影响，因此如何分析、评价和提高供应链系统的可靠性变得日益迫切。1.2问题提出现有某物流公司要在全国各城市之间建立供应链网络。需要选定部分城市作为供应点，将货物运输到各城市。通常每个供应点的货物是充足的，可以充分满足相应城市的需求。设该公司考虑共考虑49个城市的网络，已知城市的坐标城市之间的道路连接关系、在每个城市建立配送中心的固定费用和需求量，并假定作为供应点的城市其供应量可以满足有需要的城市的需求。现将要建立一个供应网络，为各城市提供货物供应。设每吨每公里运输费用为0.5元。现提出如下问题：问题一：现在要从49个城市中选取部分城市作为供给点供应本城市及其它城市。建立供给点会花费固定费用，从供应点运输到需求点会产生运输费用，要使总费用最小，问建立多少个供应点最好。给出选中作为供应点的城市，并给出每个供应点供应的城市。同时根据坐标作出每一个供应点到需求点的连接图。问题二：现在要从49个城市中选取部分城市作为供给点供应本城市及其它城市。建立供给点会花费固定费用，从供应点运输到需求点会产生运输费用，要使总费用最小，问建立多少个供应点最好。给出选中作为供应点的城市，并给出每个供应点供应的城市。同时根据坐标作出每一个供应点到需求点的连接图。问题三：假定各道路能否被破坏具有随机性，当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。由于破坏方选取一些边进行破坏时，这些边不一定被破坏，而是服从一定的概率分布。设可破坏的边及各边破坏的概率见表。运输时产生的费用可按照各种情况下的平均费用来考虑。如果破坏方选取的策略是使对方平均总费用增加最大。给出具体的破坏道路和平均总费。二、问题分析2.1问题一的分析问题一研究的主要是从49个城市中找到适当数量的供应点及其位置来使运输费用和基建费用的总费用达到最低。总费用由运输费用和基建费用组成,随着选取供应点的数量的增多,运输费用减小,但基建费用会随之增加,很明显,这是一个0-1规划问题。我们可以先通过题中所给的数据运用Floyd算法求出每个城市到其他城市的最短距离，然后给出相应的约束条件,运用Lingo软件进行求解,即可得出确定的供应点,使总费用达到最低。最后根据选中作为供应点的城市的坐标作出每一个供应点到需求点的连接图。2.2问题二的分析问题二主要研究的是破坏尽可能少的道路来使总费用增加25%,于是可以假设当某条道路被破坏时，把该条道路的距离改成一个很大的值（例如把道路的距离改成1000000公里），这样就可以近似的看成这个道路是不通的。当某条道路被破坏时，根据新得到的数据用floyd算法重新求出各城市到其他城市的最短距离，然后求出其他没有供应点的城市距离最近的供应点及其之间的距离，最后就可以求出当该道路被破坏时的总费用。根据题中给出的数据，提炼出约束条件，建立模型求当总费用增加25%时破坏的道路数量最少的情况，这样就求出了最小的道路数和具体的道路。另外，在分析道路关系图时，发现9条可以被破坏的道路中城市21到城市49之间的路如果被破坏，供应点就无法供应城市49，所以这条道路不能被破坏。2.3问题三的分析问题三主要研究的是给出适当的破坏道路的方案，使得对方的平均总费用能够达到最大，平均总费用由建造供应点的基建费用和各种情况下运输的平均费用组成，当给出道路破坏的方案后，由于8个供应点是固定的，所以建造供应点的基建费用是不变的，变化的是运输的平均费用。由于破坏方选取一些道路进行破坏时，这些边不一定被破坏，而是服从一定的概率分布。所以求运输的平均费用其实就是根据相应的概率分布求运输费用的期望值。由于有8条道路可以被破坏，所以可以给出255种道路破坏方案。在一个具体的道路破坏的方案时，例如有确定的k条道路被破坏的情况下，由于破坏方选取一些道路进行破坏时，这些道路不一定被破坏，而是服从一定的概率分布，所以有2k种的情况，在2可以根据上面的分析建立模型，运用matlab编写相应的求平均总费用的程序来求出各种方案的平均总费用，最后就可以得到相应的方案使平均总费用达到最大。三、模型假设假设1：道路破坏但原供给点及其所供应的城市不变；假设2：假定各道路能否被破坏具有随机性。假设3：网络内的所有道路都是畅通无阻的；假设4：两城市之间除了公路运输没有其他的运输方式；假设5：运输单价不受燃料等因素影响；假设6：供应点的城市其供应量可以满足有需要的城市的需求；假设7：各城市的需求量在一段时间内固定不变；假设8：假设当某条边被破坏时，把该条边的距离改成一个很大的值（例如改成1000000公里）。四、定义与符号说明0-1变量，判断第i个城市是否建立供给点1表示0表示0-1变量，判断1表示0表示在第i个城市建立供给点的固定费用第j个城市的货物需求量第i个城市到底j个城市的最短路径r(i)代表i条可以被破坏的路y(i)0-1变量，判断是否破坏第i条路y(i)为1时，代表破坏这条路y(i)为0时，不破坏这条路道路破坏前的总费用费用道路破坏后的总费用△道路破坏前后的增加的总费用MM为平均总费用T运输的平均费用J8个供应点的基建费用五、模型建立及求解数据预处理1、根据表1和表2所给的数据，运用matlab软件，编写相应的程序（见附录），画出各个城市及其之间道路关系图。如图所示：图1各城市道路关系图2、构造一个49*49的矩阵C[i][j]，根据表2中的数据对C[i][j]进行初始化:若从i市到j市有直达路径，则将表格中的数据赋给C[i][j],否则将∞付给C[i][j]，然后用Floyed算法求出从i市到j市的最短路径。Floyed算法思想如下：（1）i=1;j=1;k=1;（2）u=C[i][k]+C[k][j],若u<C[i][j],则令C[i][j]=u，否则直接转到3。（3）若j<49,则令j=j+1，转到2；否则转到4。（4）若i<49，则令i=i=1，转到2；否则转到5。（5）若k<49，则令k=k+1，j=1，i=1，转到2；否则输出。通过这种算法最后得到的矩阵C[i][j]就是任意两个城市i和j之间的最短路径，得到一个的数据阵（附录表）。在此我们截取部分（10×10）的数据，详见下表2：表2任意两个城市间的最短路径12345678910101202704805407991129135912601094212003705806609191249147912001034327037002107401069139916291151985448058021005301279160918391361119555406607405300133916691899180016346799919106912791339033056020591893711291249139916091669330023023892223813591479162918391899560230026192453912601200115113611800205923892619028010109410349851195163418932223245328005.1问题一模型的建立与求解5.1.1、模型的建立1、约束条件的确立：1、第j个城市只能接受一个供应点给它提供货物，即：其中判断第i个城市是否给第j个城市提供货物供应。2、对于任意一个城市i，若不在该城市建配送点，则=0且，因此可得约束条件：；若在该城市建配送点，则=1且或1，因此也可得约束条件：。综上，我们有约束条件：其中表示是否在第i个城市建立供应点2、目标函数的确立经过对题目的分析，可总费等于建立供给点的花费固定费用与从供应点运输到需求点会产生运输费用之和，现在我们要求建立供给点的数量使使总费用最小其中表示第i个城市到底j个城市的最短路径，表示在第i个城市建立供给点的固定费用。3、0-1整数线性规划模型综上我们可得出：5.2、模型的求解1、用Lingo软件编写程序（附录问题一）求解得出结果，详见表3：表3建立供应点城市及其相应需求点建供应点的城市该供应点可以为提供货物的城市41，2,3,4，5,15,16,27,46,4776,7，8,39,40,41,42119,10,11,12,13,32,36,37,38,432019,20，21,24,25,33,34,35,48,492322,2326262828，29,30,31，4514,17,18,44,45，1、根据表1及表2所给的数据，首先对49个节点进行标注，再运用matlab软件，编写相应的程序（见附录），找出了49个城市中可以作为供应点以及不可以作为供应点城市，如图：图2城市及供应点分布图2、运用matlab编程序结合几何画图板得出每个供应点城市到需要该供应点提供货物的城市的线路图如下：图3供应点到需求点的连接图其中实心点即为可以建供应点的城市，箭头指向的点为接受货物供应的城市。有的城市和供应点并不直接相连，可以按照箭头所指的中转城市进行货物供应。3、按照lingo软件计算的结果和相应的的路径，可以知建立8个供应点：4,7,11,20,23,26,28，45可以使总费用最小为S1=9197118（元）5.2问题二模型的建立与求解5.2.1模型的建立约束条件的建立（1）破坏方选取的策略是使对方总费用增加25%，即：其中为道路破坏前的总费用费用，道路破坏后的总费用。由题意得，必须至少要比增加25%。（2）被破坏的道路上的数目小于8，即：目标函数的建立有问题知当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。因此需要破坏最少的道路。。其中r(i)代表8条可以被破坏的路，y(i)为0-1变量，当y(i)为1时，代表破坏这条路；y(i)为1时，不破坏这条路。minR为可破坏道路数的最小数量。3、模型的建立5.2.2模型的分析求解1、该问题的关键点在于对QUOTEC后的求解，这里我们运用matlab软件进行编程（见附录问题二），来对求解。当道路被破坏后，我们可以把相应的道路距离改为一个很大的值（例如1000000000），这样当我们在用floyd算法求最短路时就可以把这条道路绕过去，就可以近似把道路看成是被破坏的。从建立的道路关系图中可以看出到达城市49的路只有一条，从城市21出发，因此如果这条路被破坏的话，城市49将得不到供应，因此这条道路不能被破坏，这样可以被破坏的路就只有8条。当某几条道路被破坏后，这条道路的距离就相应的被赋以一个很大的值，然后用floyd算法求出破坏后的各城市到其他城市的最短路径，然后分别求出没有建立供应点的城市到41个城市到8个供应点的最短路，这样就可以求出总费用。当被破坏的道路只有一条时一共有C81种情况，当破坏的道路有两条时，一共有C82种情况，依次类推，一共有2、根据以上分析可以求出被破坏的道路序列号以及被破坏的道路见下表：表4被破坏道路的序列号及相关道路被破坏的道路序列号城市1城市2被破坏的道路1454→52344→34101111→105192020→197174545→179202120→21我们根据算出来的被破坏的道路以及第一问中得出来的供给方案，得出来改道后的供给运输道路图，见图4图4改道后的运输道路图其中：1、较细的实线表示不需要改道的运输路线；2、较粗的虚线表示改道后的运输路线；3、虚线连接的点表示需要作为中转点的城市，虚线的起点表示供应点，箭头指向的点表示被供应点。4、下表列出了道路被破坏后，建供应点城市给相应的被供应城市的货物运输道路的变化情况以及这种变化带来的费用的增加量，如表所示：表5新的运输道路及改道后增加的费用受影响的供应点道路破坏前的货物运输道路道路破坏后的货物运输道路增加的费用44→3→14→16→3→14065604→3→24→16→15→23116804→54→30→51059254→3→154→16→15102208.54→5→474→30→47648831111→1011→9→105959211→10→1211→9→10→1246508.511→10→3811→9→10→3872675.511→10→4311→9→10→43905342020→19→3320→48→18→19→33364149.520→19→3420→48→18→19→3428572.520→19→3520→48→18→19→35121043.520→1920→48→18→1940832720→2120→48→18→19→2113798220→21→4920→48→18→19→21→4948647.54545→1745→18→1721934245→17→1445→18→14127710增加的总费用△2380659据此，我们容易求得道路被破坏后，在满足题设条件下的总费用：=+△因此由以上我们可以得出第二问的解答为：破坏线路的序列号为：1,2,4,5,7,9破坏线路为：4→5，4→3，11→10，20→19，20→21，45→17；总费用：11577777（元）5.3问题三模型的建立与求解1、平均总费用由8个供应点的基建费用和运输的平均费用组成maxM=J+maxTM为平均总费用，J为8个供应点的基建费用，T为运输的平均费用。2、由于J为固定的，所以求平均总费用的最大值实际上只需求运输的平均费用的最大值。例如当只有一条边可能被破坏时（假设该边被破坏的概率为p），有2种情况，则t前为道路破坏前的运输费用，t后为道路破坏后的运输费用，当可能破坏的道路数为2时，有223、由于有8条边可以被破坏，所以可以给出256种道路破坏方案（包含8条道路都不被破坏的情况），每个道路破坏方案都可以产生一个平均总费用，只需求出256种平均总费用中的最大值即可。4、根据题目中的条件，运用matlab软件建立模型，来求解平均总费用。在这256种道路破坏方案中，可以分为8种情况来讨论，分别按破坏的道路的数目来区分。例如方案中破坏的边数目为k时，可以产生一个C8k种道路破坏方案，针对C8k种道路破坏方案的一种具体破坏方案时，由于有每种情况都对应相应的概率，可以用matlab的dec2bin的函数产生一个k列的0-1全排列（这个排列为2kk的矩阵），0代表不破坏该道路，1代表破坏该道路，每一行都代表2k种情况中的一种情况，再根据表4中的数据可以求出相应的概率，利用问题二中编写的求破坏的道路的总费用的程序可以求出2k种情况下的运输费用，再利用相应的概率，求出2然后就可以求出在破坏的道路的数目为k时，C8k种方案的平均总费用。再求出C8k种方案的平均总费用中的最大值。变换k的值，k由1变换到8，就可以求出在8表6破坏的边的数目及其相应的平均费用最大值破坏边的个数n有n条边被破坏时平均总费用中的最大值123456785、然后根据表中的数据画出了随着破坏的道路的数量的不同，相应的平均总费用最大值的变化趋势图，如下:图5最大平均费用中的最大值随破坏边数的变化图由图中可以看出随着破坏的道路的数量的增加，平均总费用的最大值大体上呈现出一个上升的趋势，但当破坏的道路数为7或8时，平均总费用的最大值相同，都为最大值。当破坏的道路数为7时。共有C87种情况，可以找出平均总费用最大时对应的道路破坏方案为因此如果要使对方平均总费用增加最大，可以有两种方案进行选择。方案一：1,2，3,4,5,7,9；方案二：1,2，3,4,5,6,7,9；但如果考虑到每破坏一条道路都需要成本和代价，最优的方案一即：1,2,3,4,5,7,9（数字代表破坏的道路序号）；。6、根据以上分析可以按方案二求出被破坏七条的道路序列号以及被破坏的道路见下表：表七被破坏道路的序列号及相关道路被破坏的道路序列号城市1城市2被破坏的道路1454→52344→337407→404101111→105192020→197174545→179202120→21无论按照方案一还是方案二得到的平均总费用均为:（元）。六、模型的评价、改进及推广6.1模型的评价在本文中，我们的思路、方法及数学模型的合理性主要体现在以下几个方面：1、假设的合理性：各城市的需求量在一段时间内固定不变,供应点的城市其供应量可以满足有需要的城市的需求,道路破坏但原供给点及其所供应的城市不变,各道路能否被破坏具有随机性.这些都是十分合理的假设。2、思维的合理性：本文我们按先后及由浅入深的逻辑关系展开了对问题求解的思路，思路的流程图如图所示：合理假设精确计算科学建模合理假设精确计算科学建模模型的进一步改进和评价模型的进一步改进和评价图6思路流程图3、模型的科学性：解决问题过程中我们采用Floyd算法，0-1整数规划算法分析问题。这都是科学的数学模型在解决图中任意两点间最短距离时我们采用了Floyd算法，精确性很高，对现实问题的出来还是可以满足要求的。4、模型的可靠性：除了论文中所用方法，我们在建模时还尝试使用过其他方法，诸如Dijkstra算法、蚁群算法，遗传算法等，都得到了比较相近的结果，可见我们的模型是可靠的。6.2模型的改进与推广在解决第一问时，我们尝试了穷举法，编写了matlab程序，但计算量太大，等待结果的时间很长。后来我们结合约束条件，运用lingo软件，把它转化为0-1规划问题，使模型大大简化，大大缩短了运行的时间。在解决第二问和第三问时，由于只有255种情况，我们根据题中的条件，通过matlab编写了相应的求总费用的程序，遍历了所有可能的结果。由于涉及到的情况比较少，可以用遍历法很快的求出结果，但当处理大量的数据时，这样的方法就会消耗很多的时间。七、参考文献[1]姜启源《数学模型》，高等教育出版社，2003。[2]赵静、但琦，《数学建模与数学实验》，高等教育出版社、施普林格出版社，2000年第一版。[3]谢金星、薛毅，《优化建模与LINDO/LINGO软件》，清华大学出版社，2005年7月第一版。[4]苏金明，《MATLAB工具箱应用》，电子工业出版社，2004年第一版。[5]肖华勇，《实用数学建模与软件应用》西北工业大学出版社。[6]西北工业大学数学建模指导委员会，《数学建模简明教程》高等教育出版社。八、附录问题一的程序model:sets:weizhi/1..49/:x,jijian,xuqiu;assign(weizhi,weizhi):D,l;endsetsdata:jijian=@ole('C:\Users\hjk123\Desktop\table3','cost');xuqiu=@ole('C:\Users\hjk123\Desktop\table3','need');D=@ole('C:\Users\hjk123\Desktop\shortestpath');enddatamin=@sum(weizhi(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问题二程序t=1:8;f=nchoosek(t,1);%´Ó1µ½8ÖÐÕÒ³ök¸öÊýµÄÈ«ÅÅÁÐ[m,n]=size(f);a=1;b=1;mn=0;fora=1:mtable5=table2;forb=1:nt=find(table4(f(a,b),1)==table5(:,1));s=find(table4(f(a,b),2)==table5(:,2));j=intersect(t,s);table5(j,3)=1000000000;end%°Ñ¶ÏµôµÄ·¸³Öµ1000000000A=table5;B=sparse([A(:,1)',A(:,2)'],[A(:,2)',A(:,1)'],[A(:,3)',A(:,3)']);C=zeros(49);fori=1:49[dist,path,pred]=graphshortestpath(B,i);C(i,:)=dist;end%ÕÒ³ö¸÷µãµ½ÆäËûµãµÄ×î¶Ì¾àÀël1=[47112023262845];l2=[123568910121314151617181921222425272930313233343536373839404142434446474849];fori=1:41k=min(C(l2(i),l1));g(i)=k*table3(l2(i),2)*0.5;endh=sum(g);mn(a)=h+272080+457824+411616+526680+684608+31008+196384+243808;%Çó³ö×Ü·ÑÓÃend问题三的程序k=8;str=dec2bin(0:2^k-1);table6=str;%ÐγÉk¸ö01µÄÈ«ÅÅÁÐth=1:8;f=nchoosek(th,k);[m,n]=size(f);[tc,tk]=size(table6);fg=zeros(1,m);forpl=1:mtable5=table2;forc=1:2^ntable5=table2;forab=1:tkiftable6(c,ab)=='1't=find(table4(f(pl,ab),1)==table5(:,1));