供应链网络的建立及破坏问题汇总

装订线目录TOC\o"1-4"\h\u19772摘要229523供给链网络的建立与破坏问题313367一、问题重述316705二、问题分析3121462.1问题一：3224392.2问题二：4119312.3问题三：4818三、模型假设与符号说明4247093.1模型假设：4166323.2符号说明：422858四、模型的建立与求解5149774.1问题一：5211924.1.1算法描述：5263354.1.2模型建立与求解586484.2问题二：1186224.2.1模型的建立与求解1134684.3问题三：12202154.3.1模型的建立与求解1225749五、模型评价176987六、参考文献1716614七、局部程序代码17摘要在全球化竞争加剧的情况下，越来越多的企业开场采用供给链管理策略，以实现企业的一体化管理。而供给链是一个复杂的网状构造系统，包括供给中心和供给路线，它的每一局部都面临着各种潜在的风险，都有可能出现问题从而给整个供给链带来严重的影响。因此如何分析、评价和提高供给链系统的可靠性变得日益迫切。 本论文根据在城市建立供给中心的费用和运输货物的运费对全国49个城市和其之间的道路进展了研究。在文中应用Floyd算法和分治法，通过matlab，C++编程语言编程计算，成功从这49个城市中计算最短距离，并最终选择出了8个最优供给中心城市，并给出了最优供给链。在此根底上，本文从破坏者的角度，利用matlab等数学工具、C++编程语言和二分法、分治法的思想，分析了在使总费用增加一定数目的情况下，最少需要破坏道路的数目和具体道路，给企业提供了防破坏的依据。然后本文进一步从道路被破坏有一定概率的情况下出发，利用数据之间有无相关性，分析出了破坏哪些道路能使平均费用增加最多这一问题，给企业提供了更可靠的防破坏依据。关键字：供给链Floyd算法分治法图论相关性供给链网络的建立与破坏问题一、问题重述现有*物流公司要在全国各城市之间建立供给链网络。需要选定局部城市作为供给点，将货物运输到各城市。通常每个供给点的货物是充足的，可以充分满足相应城市的需求。设该公司考虑共考虑49个城市的网络，城市的坐标见表1。城市之间的道路连接关系见表2。在每个城市建立配送中心的固定费用和需求量表3，并假定作为供给点的城市其供给量可以满足有需要的城市的需求。现将要建立一个供给网络，为各城市提供货物供给。货物运输利用汽车进展公路运输。设每吨每公里运输费用为0.5元。现提出如下问题：现在要从49个城市中选取局部城市做为供给点供给本城市及其它城市。建立供给点会花费固定费用，从供给点运输到需求点会产生运输费用，要使总费用最小，问建立多少个供给点最好。给出选中作为供给点的城市，并给出每个供给点供给的城市。同时根据坐标作出每一个供给点到需求点的连接图。假定有*组织对该供给网络的道路进展破坏。并非所有的道路都可以被破坏，可破坏的道路见表4。当*条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。如果破坏方选取的策略是使对方总费用增加25%，而每破坏一条道路都需要本钱和代价，因此需要破坏最少的道路。问破坏方选取哪几条线路进展破坏。给出具体的破坏道路和总费用。假定各道路能否被破坏具有随机性，当*条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。由于破坏方选取一些边进展破坏时，这些边不一定被破坏，而是服从一定的概率分布。设可破坏的边及各边破坏的概率见表4。运输时产生的费用可按照各种情况下的平均费用来考虑。如果破坏方选取的策略是使对方平均总费用至少增加100%，同样需要破坏最少的道路。问破坏方将选取哪几条线路进展破坏。给出具体的破坏道路和平均总费用。二、问题分析2.1问题一：根据题目条件可知，供给中心的选择由建立费用和运输费用共同决定，而题中已给出各个城市建立供给中心的费用，所以首先要解决的问题是计算出每两个城市之间的最小距离〔如果两个城市之间无直达道路，可绕道而行〕，此问题可用floyd算法解决。为了使选择供给中心时的权值统一，即权值的单位一样，需将距离权值转化为本钱权值，因为每两个城市之间的最小路程已经计算出来，并且每个城市的需求量和每公里的运费，则可通过简单的程序将距离权值转化为本钱权值，即计算出有供给关系的城市之间所花费的运费。这样一来，就可以着手选择供给中心。首先给每个城市选择理想供给中心城市。所谓理想的供给中心城市是指满足以下条件的其他城市：比方给第i个城市选择理想供给中心城市j，则1.j城市的供给中心建立费用不是1000000000，即可用作供给中心。2.j给i供给货物所花的路费应该小于在第i个城市建立供给中心的费用〔假设路费大于建立供给中心的费用，则摒弃从j城市为第i个城市供给的做法，直接在第i个城市建立供给中心〕这样经过初步筛选，可得到第i个城市的全部理想供给城市j。在此根底上，可根据贪心算法的思想，结合matlab绘制出来的坐标地图，人为地将区域划分成小块。在每一个小块可人为地选择一个供给中心，此供给中心为其他被供给城市供给货物的运费相对较小。由此确定出大致的供给中心城市数目。编程，在28个城市中输入所有的可能组合，画出总费用变化图，得出最终的最优解。2.2问题二：问题一中已求解出了最优解，绘制出了供给关系图。由题可知，可被破坏的道路只有9条，数目较少，在此根底上，利用二分法的思想和问题一中求总费用的程序进展试验，得到满足要求的被破坏道路。2.3问题三：问题三相对问题二而言只是给可破坏道路附加了一定的成功概率，因此要解决破坏哪些道路可使平均总费用增加最多这一问题，可利用问题二中的程序和局部数据。由绘制出的供给关系图可知，许多被破坏的道路之间是没有影响的，即无相关性，它们共同被破坏产生的总费用期望可以直接由它们单独被破坏产生的总费用期望相加得到。而小局部有影响、有相关性的道路可利用程序运行得出它们共同作用的产生的总费用期望。三、模型假设与符号说明3.1模型假设：〔1〕供给中心的选择是任意的，不受政治、地理、环境等因素的影响；〔2〕各地交通条件一样，运输过程中不受交通条件的影响；3.2符号说明：i——第i个城市；j——对第i个城市来说为理想供给中心的城市；mi——第i个城市建立配送中心的固定费用；Ri——第i个城市的需求量；Z——表示总费用；Sji——为第i个城市供给货物的理想供给中心j到第i个城市的路程；Sji，ma*——为第i个城市供给货物的运费不超过在第i个城市建立供给中心时的最大供给离；Smin———每两个城市之间的最小距离E——期望值PA——A事件发生的概率A——A事件发生ma*——平均总费用增加值四、模型的建立与求解4.1问题一：算法描述：〔1〕Floyd算法Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短路径的算法。Floyd算法的根本思想如下：从任意节点A到任意节点B的最短路径不外乎2种可能，1是直接从A到B，2是从A经过假设干个节点*到B。所以，我们假设Dis(AB)为节点A到节点B的最短路径的距离，对于每一个节点*，我们检查Dis(A*)+Dis(*B)<Dis(AB)是否成立，如果成立，证明从A到*再到B的路径比A直接到B的路径短，我们便设置Dis(AB)=Dis(A*)+Dis(*B)，这样一来，当我们遍历完所有节点*，Dis(AB)中记录的便是A到B的最短路径的距离。(2)分治法：分治法字面上的解释是“分而治之〞，就是把一个复杂的问题分成两个或更多的一样或相似的子问题，再把子问题分成更小的子问题直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。分治策略是：对于一个规模为n的问题，假设该问题可以容易地解决〔比方说规模n较小〕则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式一样，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计谋略叫做分治法。如果原问题可分割成k个子问题，1<k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，则这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。模型建立与求解〔1〕运用Floyd算法计算出每两个城市之间的最小距离Smin根据Floyd算法，用matlab工具编程，计算出每两个城市之间的最小距离。〔代码见附录〕每两个城市之间的最小距离：distance.t*t〔2〕求每个城市的最大供给距离Sji，ma*如果其它城市给第i个城市供给货物所花费的运输费用大于在i城市建立供给中心的固定花费，显然不如直接在第i个城市建立供给中心。因此，每个城市存在一个最大供给距离Sji，ma*。Sji，ma*=mi/(Ri*0.5)用C语言编程得到最大供给距离：(3)运用分治法和matlab，求出局部地区的可能最优解a.求理想供给中心城市给每个城市选择理想供给中心城市。所谓理想的供给中心城市是指满足以下条件的其他城市：比方给第i个城市选择理想供给中心城市j，则 a〕j城市的供给中心建立费用不是1000000000，即可用作供给中心。b〕j给i供给货物所花的路费应该小于在第i个城市建立供给中心的费用〔假设路费大于建立供给中心的费用，则摒弃从j城市为第i个城市供给的做法，直接在第i个城市建立供给中心〕由这些条件可知，只要满足Smin≤Sji，ma*的城市j均是第i个城市的理想供给中心城市。用matlab编程得到每个城市的的理想供给中心城市。见下表：理想供给中心城市选择表城市最大供给距离Sji，ma*小于最大距离的点——理想供给中心城市j11824345710111214151617182728304043444521000000000134571011121314151617181920222324252627283040434445315201457101112141516171827283040434445415201351011121415161718272830404344455152013415161727283040434461000000000134571011121314151617181920222324252627283040434445712161408100000000013457101112131415161718192022232425262728304043444591000000000134571011121314151617181920222324252627283040434445102128134511121314151617181920222427283040434445111216101213141516174312152013410111314151617181927434445131824101112141516171819204344451421281345101112131516171819202223242728304344451524321345710111213141617181920222324272830404344451624321345710111213141517181920222324272830404344451718241345101112131415161819202223242728304344451818241341011121314151617192022232425274344451924321341011121314151617182022232425274344452015201718192223242545211000000000134571011121314151617181920222324252627283040434445221520141617182023242527444523121622242745241520171819202223252745251520202223242612162724321345710111213141516171819202223242528304043444528121627302910000000001345710111213141516171819202223242526272830404344453015201345151627284431100000000013457101112131415161718192022232425262728304043444532100000000013457101112131415161718192022232425262728304043444533100000000013457101112131415161718192022232425262728304043444534100000000013457101112131415161718192022232425262728304043444535100000000013457101112131415161718192022232425262728304043444536100000000013457101112131415161718192022232425262728304043444537100000000013457101112131415161718192022232425262728304043444538100000000013457101112131415161718192022232425262728304043444539100000000013457101112131415161718192022232425262728304043444540182413457151643411000000000134571011121314151617181920222324252627283040434445421000000000134571011121314151617181920222324252627283040434445431520134510111213141516171827444544121613410121415161718274345451216341012141516171822232744461000000000134571011121314151617181920222324252627283040434445471000000000134571011121314151617181920222324252627283040434445481000000000134571011121314151617181920222324252627283040434445491000000000134571011121314151617181920222324252627283040434445注释：最大供给距离为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问题二：模型的建立与求解此题的目标是破坏最少的道路产生至少25%的总费用增加，即△Z≥9197114*25%=2299278.5。由供给关系图可知，在可破坏的9条道路中，破坏第6条和第8条对总费用没有影响。因此只从1,2,3,4,5,7,9号道路中选择被破坏道路。应用问题二中的程序，只需更改被破坏道路的数据，即可得到破坏后的总费用。先从破坏一条道路开场尝试，结果见下表：只破坏一条道路时的所有结果：被破坏道路序号破坏后的总费用Z1总费用增长△Z1928842291278210278283108113939232301351574939565219850859578739381595794117642146209927412976985由表可知，当破坏一条道路时所产生的的总费用增长远远小于2299278.5元，因此从破坏7条道路开场尝试。全部破坏时的结果：被破坏道路序号破坏后的总费用Z1〔元〕总费用增长△Z〔元〕1,2,3,4,5,7,9116129622415848满足要求，继续尝试破坏6条道路的情况。破坏六条道路后的所有结果：被破坏道路序号破坏后的总费用Z1〔元〕总费用增长△Z2,3,4,5,7,91144840022512861,3,4,5,7,91038776611906521,2,4,5,7,91157777523806611,2,3,5,7,91134365121465371,2,3,4,7,91103900818418941,2,3,4,5,91139831222011981,2,3,4,5,7113436182146504其中，破坏1,2,4,5,7,9号道路满足要求。继续运行程序，当破坏5条道路时没有满足条件的道路，因此，破坏方案为：[1,2,4,5,7,9]总费用：Z=115777754.3问题三：模型的建立与求解a.根据供给关系图分析道路之间的相关性由供给关系图可知，大局部道路都不在一个小的子区域。假设不在一个小区域，则其产生的影响是不相关的，即具有直接加和性。在此现象的根底上，进展验证。被破坏的道路序号破坏后的总费用Z1〔元〕总费用增长△Z单条道路相加有无相关性19288422913082102782831081169392323013518749395652198538595787393816256919711407941176421465089197114099274129770151,21044281512457011172477有2,31031344011163261116326无2,41054756413504501279707有2,71049290312957891295789无2,51065987814627641462764无2,91035526811581541158154无1,79503042305928305928无1,59670017472903472903无1,39323579126465126465无1,49486930289816289816无1,99365407168293168293无3,9930928611217235217有3,49430809233695233695无3,79446921249807249807无3,59613896416782416782无4,79610272413158413158无4,59777247580133580133无4,99472637275523275523无7,99488749291635291635无5,99848053650939458640有5,79793359596245596245无注释：红色代表有相关性的道路，其余为无相关性道路。由上表可知，〔1,2〕〔2,4〕〔3,9〕〔5,9〕之间具有相关性，而其他道路之间则没有相关性。进一步分析三条道路的相关性，得出〔1,2,4〕〔3,5,9〕之间有相关性，其它则没有相关性。与供给关系图对应可知，没有相关性的道路之间距离较远，当其中任何一条被破坏时，其它道路不受影响。有相关性的道路之间距离则较近，其中一条被破坏时会影响其它道路，包括其他道路被破坏时所绕行的道路。由此得出结论：没有相关性的道路之间运费可以进展叠加，进而期望值也可以进展叠加。而有相关性的道路之间运费不能进展叠加，期望值也不能进展叠加，只能用公式进展计算。计算公式为：E=∑PA*A根据计算公式和期望的叠加性，得出：当破坏的道路为一条时：被破坏的道路序号平均总费用增加值154784.82756818.3315834.154992695209893.7560710732580946209当破坏的道路为两条时：被破坏的道路序号平均总费用增加值1,2421165.51,335293.71,477010.51,51323221,781038.51,9504792,33863092,44404042,5483337.52,7432053.52,94014943,457537.53,51128493,761565.53,941277.34,5154565.54,71032824,972722.55,7158593.55,9159768.57,976750.5当破坏的道路为三条时：被破坏的道路序号平均总费用增加值1,2,3286050.53331,2,4321328.94331,2,53507361,2,73165471,2,92961742,3,42906242,3,5327498.33332,3,7293309.33332,3,9272936.33332,4,5363561.66672,4,7329372.66672,4,9308999.66672,5,73579952,5,93376222,7,9303432.66673,4,5108317.33333,4,768854.666673,4,953755.333333,5,7111002.53333,5,9111788.79333,7,956440.666674,5,7138813.66674,5,9103043.66674,7,999648.666675,7,9175688由上表绘制出下面的折线图。并且分析每种情况下的平均总费用增加值的最大值：当破坏一条道路时：ma*1=756818.3当破坏两条道路时：ma*2=483337.5当破坏三条道路时：ma*3=363561.6667因此得出结论，被破坏道路越多，平均费用增加值越少。由上图可知，假设当道路破坏代价较大时，应该持“少破坏、多增加〞的原则进展破坏。当道路破坏代价较小时，持“多破坏，多增加〞的原则。故结合上图给出以下结论：当破坏道路的代价较大时，选择2号道路进展破坏。平均总费用增加为756797元。总费用当破坏道路代价较小时，选择[1，2，3，4，5，7，9]道路进展破坏。平均总费用增加为1406663.21五、模型评价此模型利用了Floyd算法和分治法进展计算，利用了matlab和C++等语言进展编程，成功解决了三个问题，是一个可行的数学模型。但是，此模型在应运分治法人为地得到局部最优解的过程中容易产生错误，且计算量较大，需要强大的编程能力。六、参考文献[1]管志忠.典型数模与matlab编程.中国科学技术大学.2010.6[2]周永正.数学建模.同济大学.2010.8七、局部程序代码1.用Floyd算法计算最短距离，以文件的形式输出，实现代码〔matlab〕n=49;%总共49个点A=zeros(n,n);fori=1:nforj=1:nif(i==j)A(i,j)=0;elseA(i,j)=100000;endendendA(1,2)=120;A(1,3)=270;A(1,5)=540;A(1,6)=799;A(1,15)=420;A(1,40)=844;A(2,3)=370;A(2,15)=360;A(3,4)=210;A(3,15)=311;A(3,16)=440;A(4,5)=530;A(4,16)=430;A(4,27)=630;A(4,30)=760;A(5,30)=720;A(5,40)=1521;A(5,47)=186;A(6,7)=330;A(6,39)=387;A(6,40)=727;A(7,8)=230;A(7,40)=429;A(7,41)=347;A(8,42)=819;A(9,10)=280;A(9,11)=190;A(9,15)=840;A(10,11)=279;A(10,12)=160;A(10,14)=660;A(10,15)=680;A(10,38)=598;A(10,43)=325;A(11,13)=880;A(11,14)=640;A(11,37)=153;A(12,14)=610;A(12,16)=650;A(12,17)=540;A(12,43)=435;A(13,14)=680;A(13,19)=1020;A(13,32)=490;A(13,36)=266;A(13,37)=592;A(14,17)=270;A(14,18)=640;A(14,19)=860;A(15,16)=430;A(15,43)=349;A(15,38)=361;A(16,17)=540;A(16,27)=550;A(16,43)=473;A(16,44)=285;A(17,18)=380;A(17,44)=406;A(17,45)=362;A(18,19)=780;A(18,24)=1010;A(18,45)=508;A(18,48)=664;A(19,20)=710;A(19,21)=580;A(19,34)=130;A(19,35)=127;A(19,36)=688;A(20,21)=560;A(20,24)=650;A(20,25)=820;A(20,48)=305;A(21,49)=270;A(22,23)=340;A(22,24)=490;A(22,25)=1090;A(22,27)=910;A(22,45)=795;A(23,25)=990;A(23,26)=2170;A(23,27)=920;A(24,25)=650;A(24,48)=560;A(25,26)=2320;A(26,29)=1940;A(26,31)=2672;A(27,28)=700;A(27,30)=640;A(27,44)=637;A(27,46)=304;A(28,29)=230;A(28,30)=500;A(28,31)=1980;A(30,47)=554;A(33,35)=36;A(35,36)=591;A(38,43)=368;A(40,41)=304;A(40,42)=929;A(41,42)=669;A(44,45)=466;A(46,47)=541;forj=1:nfori=1:j-1A(j,i)=A(i,j);%使对称endend[m,n]=size(A);B=zeros(m,n);B=A;fork=1:nfori=1:nforj=1:nt=B(i,k)+B(k,j);ift<B(i,j)B(i,j)=t;endendendend%输出距离矩阵fid=fopen('distance.t*t','w');fori=1:nforj=1:nfprintf(fid,'%4d',B(i,j));sendfprintf(fid,'\n');endfclose(fid);2.将距离权值转换为本钱权值的程序代码：*include<fstream>*include<iostream>*include<mem.h>usingnamespacestd;ifstreamfin_dem("*uqiu.t*t");ifstreamfin_dis("distance.t*t");ofstreamfout("APSP.out");intmain(){inta,b,c;int*uqiu[49];intjuli[49][49];intmoney[49][49];for(inti=0;i<49;i++){*uqiu[i]=0;for(intj=0;j<49;j++){juli[i][j]=0;}}for(inti=0;i<49;i++){fin_dem>>a;*uqiu[i]=a;cout<<*uqiu[i];}for(inti=0;i<49;i++){for(intj=0;j<49;j++){fin_dis>>b;juli[i][j]=b;cout<<b;}}for(inti=0;i<49;i++){for(intj=0;j<49;j++){money[i][j]=juli[i][j]**uqiu[j]*0.5;fout<<money[i][j]<<"";}fout<<endl;}return0;}3.输入任意的8个城市，输出总的费用和每个供给中心到相应被供给点的费用：*include<fstream>*include<iostream>*include<string>*defineN8*defineM49usingnamespacestd;ifstreamfin_dem("benjin.t*t");ifstreamfin_dis("APSP.out");ifstreamfin_dic("city.t*t");intmain(){inta,b;intjuli[M][M];intjilu[M];intbenjin[M];intbenjinhe=0;stringstr,tem;stringcity[49];intzuobiao[49];