数模A题论文-供应链网络的建立.doc

2013西北工业大学数模竞赛1供应链网络的建立供应链网络的建立摘要最短路程问题是现实生活中常见的最优化问题，在商业利润估算、生产生活、运输路线选择等方面都有重要意义。本题的实际情景为供应链网络的建设，在保证49个城市之间建设供应链网络费用最低的前提条件下，使供应点建设的最少。对于问题一:考虑到最终结果只算城市间的道路长度总和，所以本着“能用边缘就用边缘，不能则选用最短路径”的原则，第一步先算出相距较近若干点间距离，利用算法算出最短路径；第二步取任意一点，利用最小生成树的办法，依次取点；最Floyed后利用约束条件得到最短路程。对于问题二:第二问是在第一问的基础上进行了改进，有道路破坏，最短路路径会发生变化，运输成本有便可能增加，这里每破坏一条道路都需要成本和代价，因此需要破坏最少的道路，我理解的是破坏的道路条数小。总费用算法和第一问略有不同，再加上一个目标，min=Y(i)dstRoad(i)这里dst条Road(i)是要破坏的第i道路的长度，Y(i)为0-1变量。对于问题三:则在第二位的基础上再与实际生活进行靠拢，增加了各条道路被破坏的概率，不确定性增加，因此我们就需要将各种破坏道路情形综合起来求的最小平均费用。本着被破坏道路最少这一条件，我们便可以综合利用各种限制条件，然后采用枚举算法，贪心算法进行不断地优化计算，得出结果。关键词：FLOYD算法，供应链，枚举法，0-1规划，贪心算法。2013西北工业大学数模竞赛2目录目录1.问题重述问题重述.21.1问题背景.31.2问题提出.32基本假设基本假设.43.基本符号基本符号.44模型建立模型建立.54.1问题问题分析.54.1.2模型建立求解.64.2问题问题分析.104.2.2模型建立求解.114.3问题问题分析.134.3.2模型建立求解.135.模型评价和推广模型评价和推广.145.1问题1模型.145.2问题2模型.145.3问题3模型.145.4模型反思.166.参考文献参考文献.177.附录附录.172013西北工业大学数模竞赛31.问题重述问题重述1.1问题背景问题背景全球化竞争的加剧促使越来越多的企业开始采用供应链管理策略，以实现企业的一体化管理。供应链是一个复杂的网状结构系统，每一部分都面临着各种潜在的风险，任何一部分出现问题都可能给整个供应链带来严重的影响，因此如何分析、评价和提高供应链系统的可靠性变得日益迫切。设施系统是供应链的核心，在供应链研究中有着极其重要的地位。在一个设施系统中，某些个设施由于自然灾害或者其他因素的影响可能失效，例如911恐怖袭击事件、2004年的印度洋海啸、2008年的汶川地震等都对诸多行业的设施系统造成了严重的破坏。现有某物流公司要在全国各城市之间建立供应链网络。需要选定部分城市作为供应点，将货物运输到各城市。通常每个供应点的货物是充足的，可以充分满足相应城市的需求。设该公司考虑共考虑49个城市的网络，城市的坐标见表1，城市之间的道路连接关系见表2，在每个城市建立配送中心的固定费用和需求量表3，并假定作为供应点的城市其供应量可以满足有需要的城市的需求。现将要建立一个供应网络，为各城市提供货物供应。货物运输利用汽车进行公路运输，每吨每公里运输费用为0.5元。1.2问题提出问题提出1.现在要从49个城市中选取部分城市做为供给点供应本城市及其它城市。建立供给点会花费固定费用，从供应点运输到需求点会产生运输费用，要使总费用最小，问建立多少个供应点最好。给出选中作为供应点的城市，并给出每个供应点供应的城市。同时根据坐标作出每一个供应点到需求点的连接图。2.假定有某组织对该供应网络的道路进行破坏。并非所有的道路都可以被破坏，可破2013西北工业大学数模竞赛4坏的道路见表4。当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。如果破坏方选取的策略是使对方总费用增加25%，而每破坏一条道路都需要成本和代价，因此需要破坏最少的道路。问破坏方选取哪几条线路进行破坏。给出具体的破坏道路和总费用。3.假定各道路能否被破坏具有随机性，当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。由于破坏方选取一些道路的边进行破坏时，这些边不一定被破坏，而是服从一定的概率分布。设可破坏的边及各边破坏的概率见表4。运输时产生的费用可按照各种情况下的平均费用来考虑。如果破坏方选取的策略是使对方平均总费用增加最多，同样需要破坏最少的道路。问破坏方将选取哪几条线路进行破坏，给出具体的破坏道路和平均总费用。2基本假设基本假设1.在此假设各个城市之间的道路为直线相连（将实际曲线距离简单看成为直线距离），便于画图和分析问题。2.计算任意两城市之间的道路总长度与两城市连线距离关系时，将道路的长度算在其中。3.问题三中将破坏的概率视为道路破坏费用的权值并且将9条道路的破坏与否示为独立事件，即它们是否被破坏之间无关联。3.基本符号基本符号Vi任一城市点点V0、V1间的弧d(V0V1)弧V0V1的权值S道路长度总和V（i，j）点ij之间的路径2013西北工业大学数模竞赛5M运输每吨的费用W运输的总费用4模型建立模型建立4.1问题问题14.1.1问题分析问题分析该问题给出了49个城市的具体坐标，各个城市之间的连通度，各城市间距离和各城市作配送中心的固定费用、需求量。1.各城市间的运输费用不得高于建设配送中心及城市与城市之间费用总和.2.运输费用及建立费用之和最小。在这两个前提下我们考虑的问题是：如何使供应点数量最小。这显然是一个最优化问题，比较复杂，需要考虑多个方面的问题。因此我们在这里必须选取其中的一个因素为研究对象，兼考虑其他影响因素，将49个城市划分为几个区域但应该特别关注一些特别的点。在此我们将城市的连通程度视为主要因素，将采用枚举算法依次求取最少费用，最后比较得出最优解。我们简单画出个城市在二维坐标的位置以及连通程度图如下（见下页）：2013西北工业大学数模竞赛64.1.2模型建立求解模型建立求解由题所给出的条件可以看出，这与最短路问题联系密切，于是考虑用几何知识和Dijkstra算法以及Floyd算法建立问题的模型。由题将49个城市设为：12345678910111249。根据题意，相关性引入示意图2013西北工业大学数模竞赛7由于成本问题，部分城市不能建立配送中心，所以有效城市仅有28个。在此引入相关性概念：即某城市直达邻边城市的道路条数。如上图：A，B，C，D，E的相关性分别为3，1，2，2，2。列出28个有效城市的需求量及相关性如下图：表1有效城市相关性与需求量列表方法：任取城市节点Vi，以此点为起始点，由上面第二步所得的数据分别比较Vi与其他点的距离，得出Vi的最短路径Vij，再以j点为起始点用同样方法比较出最短路径Vjk.同理依次求的最短路径。再验证是否满足题目所需极值要求，若不满足，则再通过比较后添加最优路径。第一步：利用Matlab软件计算某一区域中若干相关城市间的距离。第二步：利用Floyd算法及Lingo软件求解出区域中作为配送中心的最佳城市。相关程序的代码见附录1。各城市间的距离见附录2。第三步：利用Dijkstra算法求解最优解对应的城市以及相关费用。引入对Dijkstra算法的描述：1.初始时令S=V0T=其余个城市点点，T中城市对应的城市的距离值为Vi，若存在，d(V0Vi)为连线上的权值，若不存在，d(V0Vi)为。2.从T中选取一个其距离值为最小的W且不在S中，加入S进一步重复上一步。2013西北工业大学数模竞赛83.对T中城市间的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值，重复上述步骤2、3，直到S中包含所有顶点，即S=T为止。步骤图如下：利用Matlab软件求取若干相关两城市间的距离利用Floyd算法及Lingo软件求出某一区域作为配送中心的城市最短路径分析筛选最优路径利用Dijkstra算法问题1求解示意图具体求解描述为：具体求解描述为：设Xi表示是否为供应点，Xi为0-1变量。Xi=1表示是供应点，反之为非供应点；2013西北工业大学数模竞赛9假设在一段时间内运输次数为T（这个可以固定），则总费用包括：运输费用，建立供应点费用。建立供应点总费用=（creatcost（i）Xi）式中：creatcost（i）为第i个城市建立供应点的费用。运输费用：每个需求点“就近取材”，即到最小路程地运输所需物品数据处理：计算各个城市之间的最小路程，可用floyd算法算法令=sitiiM表示i城市到最近的配送中心距离，表示i城市所需吨数。iSit则运输总数消耗费用M=4911iM建立配送中心费用：V=kijV1K为配送中心的个数，则总费用为W=M+V。根据附表程序及floyd算法计算所得，当K=8时，W取得最小值。为求得最优解，引入上述城市间相关性概念，为节省费用，综合考虑需求量，配送中心应优先选择相关性较大的城市，故所选的8个城市为：太原，长春，杭州，南宁，成都，拉萨，兰州，宜昌。城市供应点供应的城市关系为：太原：西安，郑州，呼市，包头，石家庄，北京，天津，济南，青岛，延安。长春：哈尔滨，沈阳，大连，白城，通辽，海拉尔。杭州：上海，南昌，宁波，福州，台北，厦门，南京，合肥，徐州。南宁：广州，海口，深圳，香港，三亚，柳州，贵阳，昆明，澳门。成都：重庆。2013西北工业大学数模竞赛10拉萨：（不对外供应）兰州：西宁，银川，乌市。宜昌：武汉，长沙，南阳。则所需的总费用为：W=min（W）=9.197106（元）。所以所得的配送中心分配图为（见下页）：上图中加粗点为配送中心城市上图中加粗点为配送中心城市4.2问题问题24.2.1问题分析问题分析在本问题中城市间需要破坏相应9条道路中的若干道路，题目要求在使对方费用增加25%（固定值为0.25W=2.3106）的条件下使得破坏的道路长度最短。因此我们2013西北工业大学数模竞赛11在本题中1.优先考虑货物需求量较大的城市；2.优先考虑相关性较低的城市。同时考虑到城市49的相关性为1，即只有一条道路与其连通。当破坏连通它的道路时，城市49就被孤立起来了。故：假设当破坏与城市49连通的道路时，必须额外增加一个配送中心（城市49建为配送中心），而城市49由于被建为配送中心费用费用（100000000）太高而不可用。因此本题中我们暂且认为城市49与21间的道路不被破坏。选择合适的算法结合题目所给的要求以及题干附表条件，进行数学建模。4.2.2模型建立求解模型建立求解。由于只有9条道路可以被破坏，则可以选择枚举以及贪心算法法进行求解。由于道路破坏，最短路矩阵会变化，运输成本有可能增加，这里每破坏一条道路都需要成本和代价，因此需要破坏最少的道路，我理解的是破坏的道路长度和最小。总费用算法和第一问一样，再加上一个目标，min=Y(i)DstRoad(i)这条DisRoad(i)是要破坏的第i道路的长度，Y(i)为0-1变量。步骤图如下：2013西北工业大学数模竞赛12利用几何知识及Matlab绘制将已知条件转化为0-1关系数理统计进一步筛选缩小所破坏的道路求解最佳破坏方式及最少费用利用C+语言程序与贪心算法问题2求解示意图具体求解描述：具体求解描述：2013西北工业大学数模竞赛131.如上图可标出能被破坏的九条道路，联系各条道路与周边道路的情况优先选择绕行距离最大的，及所需货物最多的城市。2.用进行计算多出的费用。tMW3.当破坏城市49相关的道路时（即道路8），需要多建立一个配送中心，则额外的费用为:（费用过大）149Vw所以道路8不能被破坏。故仅剩八条路可供破坏。4其中为增加费用的百分比。WW5.用枚举法进行编程运算。具体答案：得出，当破坏道路12459时，额外费用为2268087元，总费用为9197000元，所以百分比=额外费用总费用=24.68%，满足条件。故当不破坏道路8时，则要满足破坏条数最少的方案是：破坏道路12459即可。2013西北工业大学数模竞赛144.3问问题题34.3.1问题分析问题分析本题沿着问题2的的思路，添加了9条道路被破坏的概率，在要求使对方费用增加最多，但破坏道路条数最少。这事就需要考虑给运输费用加权，考虑求取各种情况下的加权平均费用（即期望），使平均费用最大即可。固定费用确定各城市所属供应点选择目标函数获得最优解0-1规划穷举法选择其中N个城市建供应点城市间主要道路最短路径算法进一步讨论模型的有效性和推广性供应点固定建设费用问题三求解示意图问题三求解示意图.4.3.2问题建模求解问题建模求解考虑到由于城市49相关性为1，则道路8被破坏后，它无法从其他城市获得货物，假设若破坏道路8，则城市49会增加一个配送中心。又因为城市49做配送中心的费用过大，由此我们首选破坏道路8。然后再依次添加一个被破坏。先对破坏两条道路探索求解思路：2013西北工业大学数模竞赛15若破坏两条道路则存在以下几种情况：1.两条都没有被破坏概率为，费用为。1P1W2.只有一条被破坏概率为，费用为。32PP或3.有两条都被破坏概率为费用为。4P4W所以平均费用为：。44332211WWPWPWPPW基于上述运算思想可采取以下步骤：Step1:从可选的9条路中任选取1条，有种可能。记道路为i为其被破坏的19CiP概率，（1）为其不被破坏的概率。记被破坏后费用为，破坏前费用为SUM，PiSi其期望为=SiPi+（1-Pi）SUM，取Estep1=MaxEi；iEStep2：从可选的9条路中任选取2条，有种可能。记概率为29CPij=Pi2+Pj2+2PiPj，重复step1求期望，取Estep2=EijStep3:重复前两部步骤，然后求的最大费用MaxEstep1Estep2Estep3所以求得的答案为：破坏道路1，道路2，道路4，道路5，道路7，道路9。平均费用为：W=1.06068107（元）。5.模型评价和推广模型评价和推广5.1问题问题1模型模型模型缺点模型缺点:问题1所建立的模型，在利用Dijkstra算法求解最优路径时，可能会遇到在求解的过程中在某一点会存在多支符合条件的分支路径时，这时需要进行主观分析判断取舍，可能会存在不严谨不精确之处，造成最后结果会出现误差。只可利用灵活多样的方式求的近似最优方案。模型优点模型优点:该模型从局部到整体进行优化从多个影响因素中选取一个主要因素进行研究，并2013西北工业大学数模竞赛16有几处创新以期待来减小主观性带来的不严谨性，从而具有可行性这些方法可以推广应用到运输生产领域。5.2问题问题2模型模型模型缺点模型缺点:（1）由于再破坏道路时，需考虑进行改道，这样数据的复杂程度过高，再加上需要用枚举算法。（2）在利用C+语言程序对已知区域进行微小量划分，并使交配送点在区域内进行穷举运算时，会存在固有的精度误差，结果导致最终的破坏选择方式出现误差，用此方法得出准确无误差值是不现实的，因此用近似估计法，尽可能的进行分析，期望得到近似最优方案。模型优点模型优点:（1）可操作性强，具有较强的逻辑性，能够在一定程度上减少运算量。（2）思想叫简洁，通俗易懂，使人容易理解5.3问题问题3模型模型此问题由于涉及概率问题并且题中的一条道路（即道路8）比较特殊，因此我们在建模时难以全面考虑仅将概率作为各种情形费用的权值进行计算而忽略各个道路的相关性。优点：编程运用LINGO软件，节约计算时间。2013西北工业大学数模竞赛175.4.反思供应链是适应市场全球化的客户需求多样化而产生的，它强调供应链上各企业及其活动的整体集成，从而更好的协调供应链上各企业的需求，使更好的实施供应链管理技术，让我们的企业在竞争激烈的经济环境下存活下来并得到更好的发展。在企业生产中和经济管理等领域中，人们常会遇到这样的问题，例如：如何从一切可能的方案中选择最好的、最优的方案。在我们数学上把这类问题称为最优化问题，如何解决这类问题，在当今商品经济的环境下，是关系到国计民生的问题。在解决上述不确定环境下供应链的生产与订购决策问题上，我们采用的是线性规划和概率论中的正态分布的方法。线性规划的理论和方法都比较成熟，并且是一个有广泛应用价值的统筹学分支，如果一个问题的限制条件可以写出某些决策变量的线性方程组或线性不等式组，那我们就可以应用lingo软件将该线性规划方程解出来得到最优解。而对于正态分布，一个变量如果是大量微小的、独立的随机因素的叠加结果，此时很多随机变量可以用正态分布描述或近似描述。应用数学知识中的线性规划和正态分布对于解决该不确定环境下供应链既简单又准确，在最优解的求解过程中是个很好的选择。但还是存在如下优缺点：本文把求解生产商和销售商利润的多目标问题转化成单目标问题，使得问题简化。、模型推广以上建立的模型，是在两级生产不确定的供应链中，并且产成品的市场需求量是一确定值，根据上述建立模型的方法再加以改进，综合正态分布和线性规划另建模型求在产成品的市场需求量也是一个随机变量（即也存在一个波动区间，并且有产成品市场需求量的期望值）时的二级生产商的最优订购量和一级生产商的最优计划量。2013西北工业大学数模竞赛186.参考文献参考文献1.数学建模基础，北京工业大学出版社，薛毅著；2.优化技术与Matlab优化工具箱，机械工业出版社，赵继俊著；3.控制系统Matlab计算与仿真，国防工业出版社，黄忠霖、黄京著；4.概率统计教程，清华大学出版社，姚孟臣著；5.MathematicalModelingforIndustryandEngineering机械工业出版社，ThomasSvobodny著；6.IntroductiontoAlgorithms（算法导论），机械工业出版社，ThomasH.Cormen著。7.附录附录附录1.Matlab绘制城市图标代码附录2.各点间的最小距离代码附录3.0-1规划算法代码2013西北工业大学数模竞赛19附录一附录一%城市坐标，共49个city=36392685371226013053261%城市之间的距离，共102条dis=12120132701554044454664647541%注：1000000000表示该点不用，费用太高%可建立配送中心的费用和承载量，其中有28个城市可以建立配送站的节点cost=112358412321000000000974100000000055%-city，城市坐标%-dis，城市间的距离%-cost，建立配送点的代价和其对应的承载量%画城市网络hfig=figure(1)plot(city(:1)city(:2)ro)pos_city=30fori=1:size(city1)text(city(i1)+pos_citycity(i2)+pos_citynum2str(i)endholdontitle(城市网络示意图，距离单位(km)xlabel(x)ylabel(y)set(gcfcolorw)2013西北工业大学数模竞赛20%标注配送点fori=1:size(cost1)ifcost(i1)=1000000000plot(city(i1)city(i2)roMarkerFaceColorr)endend%标注城市权重pos_dis=0fori=1:size(dis1)line(city(dis(i1)1)city(dis(i2)1)city(dis(i1)2)city(dis(i2)2)%格式为linex1x2y1y2text(city(dis(i1)1)+city(dis(i2)1)2+pos_dis(city(dis(i1)2)+city(dis(i2)2)2+pos_disnum2str(i)Colorr)endmarkcity=北京天津石家庄柳州三亚fori=1:30ifcost(i1)=1000000000text(47003500-i100strcat(num2str(i)-markcity(i:)Colorred)elsetext(47003500-i100strcat(num2str(i)-markcit