供应链网络建立与破坏数学建模

wordword20/20word目录一、问题重述2二、问题提出2三、问题分析3四、模型假设3五、主要符号说明4六、模型的建立与求解5问题一56.1.1蚁群算法的根本理论6模型求解9问题二11迪杰斯特拉算法11模型求解12问题三14独立事件模型建立14模型求解15七、模型的优缺点15动态规划15优点15缺点15蚁群算法16优点16缺点16八、参考文献17九、附录18一、问题重述全球化竞争的加剧促使越来越多的企业开始采用供给链管理策略，以实现企业的一体化管理。供给链是一个复杂的网状结构系统，每一局部都面临着各种潜在的风险，任何一局部出现问题都可能给整个供给链带来严重的影响，因此如何分析、评价和提高供给链系统的可靠性变得日益迫切。设施系统是供给链的核心，在供给链研究中有着极其重要的地位。在一个设施系统中，某些个设施由于自然灾害或者其他因素的影响可能失效，例如911恐怖袭击事件、2004年的印度洋海啸、2008年的汶川地震等都对诸多行业的设施系统造成了严重的破坏。现有某物流公司要在全国各城市之间建立供给链网络。需要选定局部城市作为供给点，将货物运输到各城市。通常每个供给点的货物是充足的，可以充分满足相应城市的需求。假设该公司共考虑49个城市的网络并假定作为供给点的城市其供给量可以满足有需要的城市的需求。现将要建立一个供给网络，为各城市提供货物供给。货物运输利用汽车进展公路运输。二、问题提出〔1〕现在要从49个城市中选取局部城市做为供给点供给本城市与其它城市。建立供给点会花费固定费用，从供给点运输到需求点会产生运输费用，要使总费用最小，问建立多少个供给点最好。给出选中作为供给点的城市，并给出每个供给点供给的城市。同时根据坐标作出每一个供给点到需求点的连接图。〔2〕假定有某组织对该供给网络的道路进展破坏。并非所有的道路都可以被破坏。当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。如果破坏方选取的策略是使对方总费用增加25%，而每破坏一条道路都需要本钱和代价，因此需要破坏最少的道路。问破坏方选取哪几条线路进展破坏。给出具体的破坏道路和总费用。〔3〕假定各道路能否被破坏具有随机性，当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。由于破坏方选取一些边进展破坏时，这些边不一定被破坏，而是服从一定的概率分布。运输时产生的费用可按照各种情况下的平均费用来考虑。如果破坏方选取的策略是使对方平均总费用增加最大。给出具体的破坏道路和平均总费用。三、问题分析问题一：对问题一中的运输调度问题进展分析，根据动态规划算法进展处理，利用lingo对其数学模型进展求解，但该方式给出的算法所搜索的空间容量很大，利用目前的计算机求此问题的准确解已很难实现，并且需要相当长的时间才有可能得到准确解，且其规模较小实际应用的意义不大。为此，我们结合蚁群算法在求解运输调度问题上的优势，在此根底上，将蚁群算法结合运输调度模型进展仿真实现。问题二：我们建立了基于迪杰斯特拉算法的模型。根据题目所给的的信息，对可破坏的道路进展逐一破坏分析，得到最短传输路径和相应多消耗的费用。再根据破坏方使对方总费用增加25%这一策略得到具体破坏的道路和总费用。问题三：该问题是在问题二的根底上的优化，由于破坏方选取一些边进展破坏时，这些边不一定被破坏，而是服从一定的概率分布。在考虑此问题时，要涉与到各边所破坏的概率，再根据破坏方选取的策略得到具体的破坏道路和平均总费用。四、模型假设〔1〕假设每个供给点的货物是充足的，可以充分满足相应城市的需求；〔2〕假设每辆车所服务的客户总的需求量不得大于车辆的最大载质量；〔3〕假设一个城市由只能有一个供给点供给；〔4〕忽略供给链网络中运输货物的不同对供给点设立的影响；〔5〕忽略货物需求量、发送量、交发货时间、车辆容量限制、行驶里程限制与时间限制的影响；〔6〕假设两城市之间除了公路运输没有其他运输方式

；〔7〕假设运输单价不受天气和油价等因素影响

；〔8〕假设各城市的需求量在一段时间内固定不变。五、主要符号说明元素i在t时刻存在的蚂蚁数量路径(i，j)上t时刻的信息素浓度数值n城市数目m蚁群算法的规模即蚁群中的蚂蚁总数t时刻所有城市间路径上的信息素残留量的集合蚂蚁k下一步允许选择的城市信息素强度影响因子启发函数dist[n]存放从源点到每个终点当前最短路径的长度path[n]存放相应路径S已求得最短路径的终点的集合cos(i)表示以第i个城市建立供给点所需的固定费用w(i)表示第i个城市所需的货物重量d(i)Total[i]以i为供给中心和周围城市构成网络所需的总费用ans[i]表示破坏道路要多序号i后要多花费的费用六、模型的建立与求解供给链网络中一个重要的网络节点是供给点设立。一般来讲，如果用户较为固定，按照配送费用最小或者到各个消费地的距离之和最小的原如此，即供给点处于使物流网路运营费用最小的位置或者供给点所处位置与各城市位置的通行距离之和应为各待选位置中的最低者。此时，供给链网络应设为辐射型网络布局。辐射型网络布局如如下图所示，供给点位于需求点的几何中心位置，构成需求地环绕供给点的布局格式。物料从此供给点向周围各方向消费者配送，形成辐射型。需求地需求地需求地需求地供给点图1：辐射型格局设立辐射型的格局应满足两个方面的条件。一是需求地在供给点周围几乎是均匀分布，并且供给点周围是用户相对集中的经济区域；二是供给点是连接主干输送线路和配送线路的一个转运站，把货物送到指定地点。根据题中所给出的各城市坐标和各公路段与里程表，得到49个城市的分布图如下。图2：城市的分布图对问题一中的运输调度问题进展分析，根据动态规划算法进展处理，利用lingo对其数学模型进展编程并求解，但该方式给出的算法所搜索的空间容量很大，利用目前的计算机求此问题的准确解已很难实现，并且需要相当长的时间才有可能得到准确解，且其规模较小实际应用的意义不大。在实际应用中的时候不是非要得到一个准确的解，在大多数时候近似的解就已经满足了实际的需求，为此我们结合蚁群算法在求解运输调度问题上的优势，在此根底上，将蚁群算法结合运输调度模型进展仿真实现。6.1.1蚁群算法的根本理论蚂蚁觅食时，会在所经过路线上留下一种称为信息素的物质，以此来标识路线，其它蚂蚁可以并且习惯追踪此信息素爬行。在确定位置的食物和蚁穴之间，较近的路线，蚂蚁重复爬行的次数就更高些，由于每只蚂蚁每经过一次都要释放信息素，这样重复次数多的路线由于其信息素浓度较大就更容易被其它蚂蚁选中，这样整个蚁群就由开始的多路线爬行逐渐集中到最短的路线上爬行，使路线得到优化选择。蚁群算法是一种模拟自然界蚂蚁觅食行为的启发式搜索算法，由意大利学者M.Dorigo模拟此过程提出。其主要特点正反应、并行式搜索。它尤其适用于处理传统搜索方法难于解决的复杂和非线性问题，可广泛用于组合优化、机器学习、自适应控制、规划设计和人工生命等领域，是21世纪有关智能计算中的关键技术之一。首先我们要对蚂蚁的搜索环境进展一些假设并设定一些具体参数，设：①为元素i在t时刻存在的蚂蚁数量；②为路径(i，j)上t时刻的信息素浓度数值；③n表示城市数目；④m表示蚁群算法的规模即蚁群中的蚂蚁总数，；⑤是t时刻所有城市间路径上的信息素残留量的集合。蚁群算法的初始时刻各个路径上的信息素通常设定为一个常数。蚂蚁k(k=1,2,…，m)在路径的搜索过程中，根据不同路径上的信息素浓度来决定其下一步的搜索路径。表示在t时刻蚂蚁k由元素(城市)i转移到元素(城市)j的选择概率。式中，表示蚂蚁k下一步允许选择的城市，为信息素强度影响因子，表示蚂蚁对于信息素浓度的敏感程度也明确此路径的相对重要性。其值越大，此时蚂蚁在选择下一搜索路径时，容易受到信息素浓度的影响，蚂蚁更趋向于信息素浓度较高的路径，也就是有更多蚂蚁走过的路径同时也是增强了蚂蚁间的交流信息使彼此间的协调机制更明显。为能见度因子又称期望因子，表示蚂蚁本身的能见度对在路径选择中的重要性。其值越大如此蚂蚁选择路径时越是依赖于能见度信息。当取值很高时蚂蚁如此是以一种几乎贪婪的规如此选择下一步的搜索路径，而忽略信息素影响。为启发函数，其表达式如下:式中，表示两个相邻元素间的距离。的数值越小，说明两城市相距越近同时越大，也就越大，蚂蚁下一步选择这一个城市的概率也就越高，这也就说该函数表征了蚂蚁从一个城市到另一个城市的期望度数值。随着蚂蚁的不断搜索，很多路径上都会留下信息素，为了防止各个路径上的大量残留信息素不断积累从而导致蚂蚁忽略能见度信息，当每只蚂蚁每完成一步搜索或者蚂蚁完成对n个城市的搜索(也就是算法完成一次迭代)后，需要对每条路径上残留的信息素量进展更新。这样在t+n时刻路径(i，j)上的信息素浓度可以按照下面的公式调整。式中表示信息素挥发因子，如此表示信息素残留因子。为了更加贴近自然界中的蚂蚁群体，并防止信息素的过度累积，通常的取值X围为:；在完成一次迭代后用表示路径(i，j)上的信息素增量，初始时刻，如此表示蚂蚁k在本次搜索过程中于路径(i，j)上留下的信息素量。在蚁群算法中，信息素的更新策略直接关系着算法的效率和成功与否，而信息素更新的策略也会根据待解决的问题特点来选择。DorigoM曾经提出了三种不同的根本蚁群算法模型。这三种模型分别是:Ant-Cycle模型、Ant-Quantity模型和Ant一Density模型。其中三种模型的差异在于信息素增量的求法的不同。在Ant-Cycle模型中式中，Q表示信息素强度，它在一定程度上影响算法的收敛速度;表示k只蚂蚁在本次循环中所走路径的总长度。在Ant-Quanity模型中在Ant-Density模型中其中Ant-Quanity模型和Ant-Density模型采用的是局部信息素更新策略，也就是说蚂蚁在每走完一步到达下一城市就对刚刚走过的路径信息素进展更新；而Ant-Cycle模型中如此是采用全局的信息素更新策略，当一只蚂蚁访问过所有城市以后才会对所走过的路径进展信息素更新。用蚁群算法对问题一进展分析，得到最优结果为：选择出某某、某某、某某、某某、某某、某某、某某、某某这八个城市为供给点，总费用为9304885元。每个供给点供给的城市与每一个供给点到需求点的连接图如下：图3：供给点供给X围图每个供给点供给的城市与费用情况如下表：表1：供给点供给城市与费用情况表1某某无310082某某某某—某某，某某，某某—海拉尔，某某11401063某某乌市，某某，某某，某某—某某8714524某某呼市—某某，某某—，某某—某某，某某—某某，某某14004005某某某某，某某，某某8257806某某某某12382987某某某某，某某，某某，某某—某某，某某—某某—澳门，某某—台北16906378某某某某，某某，某某—某某，某某—台北，某某，某某—某某，某某—某某，某某—某某2107604总费用共计：9304885其中费用的计算过程如下：Total[2]=cos(7)+w(40)*d(23)+w(41)*d(24)+w(8)*d(22)+w(6)*d(19)+w(39)*(d(20)+d(19))+w(42)*(d(100)+d(24))=1140106Total[3]=cos(28)+w(31)*d(93)+w(29)*d(91)+w(30)*d(92)+w(27)*d(87)+w(46)*(d(90)+d(87))=871452Total[4]=cos(4)+w(16)*d(13)+w(5)*d(12)+w(47)*(d(18)+d(12))+w(3)*d(9)+w(1)*(d(2)+d(9))+w(2)*(d(7)+d(9))+w(15)*(d(10)+d(9))=1400400Total[5]=cos(45)+w(44)*d(101)+w(17)*d(59)+w(18)*d(62)=825780Total[6]=cos(23)+w(22)*d(74)=1238298Total[7]=cos(20)+w(25)*d(71)+w(24)*d(70)+w(48)*d(72)+w(21)*d(69)+w(19)*d(64)+w(49)*(d(69)+d(73))+w(34)*(d(66)+d(64))+w(35)*(d(67)+d(64))+w(33)*(d(67)+d(64)+d(95))=1690637Total[8]=cos(11)+w(10)*d(29)+w(9)*d(27)+w(37)*d(37)+w(13)*d(35)+w(14)*d(36)+w(12)*(d(30)+d(29))+w(43)*(d(34)+d(29))+w(38)*(d(33)+d(29))+w(36)*(d(45)+d(35))+w(32)*(d(44)+d(35))=2107604假定有某组织对该供给网络的道路进展破坏。并非所有的道路都可以被破坏。当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。如果破坏方选取的策略是使对方总费用增加25%，而每破坏一条道路都需要本钱和代价，因此需要破坏最少的道路。对于此问题，我们采用迪杰斯特拉算法进展求解。迪杰斯特拉算法是典型最短路径算法，用于计算图或网中某个特定顶点到其他所有顶点的最短路径。主要特点是以起始点为中心向外，层层扩展，直到扩展覆盖所有顶点。迪杰斯特拉算法思想设G=(V,E)为一个带全有向图，把图中顶点集合V分成两组。第一组为已求出最短路径的顶点集合〔用S表示，初始时S中只有一个源点，以后每求得一条最短路径，就将所到达最短路径的顶点参加到集合S中，直到全部顶点都参加到S中〕。第二组为其余未确定最短路径的顶点集合〔用U表示，U=V-S，U中的顶点不断的参加到S中，直到U为空，S=V〕。在U参加S的过程中，始终保持源点到S中各顶点的最短路径长度小于或等于源点到U中任意顶点的最短路径长度。迪杰斯特拉算法执行步骤设n为图G=(V,E)中的顶点数，dist[n]存放从源点到每个终点当前最短路径的长度，path[n]存放相应路径，S为已求得最短路径的终点的集合，U为V-S，初始为不含有源点的所有顶点。〔1〕初始化已求的最短路径的集合S为只含有元素源点a，S=｛a｝。〔2〕从U中选取一个距离源点v最小的顶点k，把k参加S中〔该选定的距离就是v到k的最短路径长度〕。〔3〕以k为新考虑的中间点，修改U中各顶点的距离；假如从源点v到顶点u〔uU〕的距离〔经过顶点k〕比原来距离〔不经过顶点k〕短，如此修改顶点u的距离值，修改后的距离值为顶点k的距离加上顶点k到u边上的权。〔4〕重复步骤〔2〕和〔3〕直到所有顶点都包含在S中。假定有某组织对该供给网络的道路进展破坏。并非所有的道路都可以被破坏，可破坏的道路见下表。表2：破坏道路表1452343740410115192062425717458214992021根据第一题得到的供给X围的分布图并结合上表，我们运用迪杰斯特拉算法对破坏后道路进展分析，求得了改道后的最短路运输路径和破坏道路后所多消耗的费用。表3：破坏道路后路线更改与多消消耗用表14-55-45-1-3-410780047-5-447-5-1-3-423-43-43-16-410811201-3-41-5-42-3-42-1-5-415-3-415-16-433-4和4-55-45-30-28130039047-5-447-5-30-283-43-16-41-3-41-3-16-42-3-42-3-16-415-3-415-16-447-4040-740-41-738357510-1110-1110-9-1123951412-10-1112-10-9-1113-10-1113-10-9-1138-10-1138-10-9-11619-2019-2019-21-2038162534-19-2034-19-21-2035-19-2035-19-21-2033-35-19-2033-35-19-21-20724-25无影响无影响不产生817-4517-4517-44-45212670921-49无影响无影响不产生1020-2120-2121-19-207701549-21-2049-21-19-201119-20和20-2119-2019-18-4565096934-19-2034-19-18-4535-19-2035-19-18-4533-35-19-2033-35-19-18-4521-2021-19-18-4549-21-2049-21-19-18-45其中，破坏道路后多消耗的费用计算过程如下：ans[1]=w(5)*(d(3)+d(2)+d(9)-d(12))+w(47)*(d(3)+d(2)+d(9)-d(12))=107800ans[2]=w(3)*(d(11)+d(13)-d(9))+w(1)*(-d(2)-d(9)+d(3)+d(12))+w(2)*(d(1)+d(3)+d(12)-d(7)-d(9))+w(15)*(d(50)+d(13)-d(9)-d(10))=1081120ans[3]=w(5)*(d(16)+d(92)-d(12))+w(47)*(d(16)+d(92)-d(12))+w(3)*(d(11)+d(13)-d(9))+w(1)*(d(11)+d(13)-d(9))+w(2)*(d(11)+d(13)-d(9))+w(15)*(d(50)+d(13)-d(9)-d(10))=1300390ans[4]=w(40)*(d(24)+d(98)-d(23))=38357ans[5]=w(10)*(d(26)+d(27)-d(29))+w(12)*(d(27)+d(26)-d(29))+w(13)*(d(27)+d(26)-d(29))+w(38)*(d(27)+d(26)-d(29))=239514ans[6]=w(19)*(d(65)+d(69)-d(64))+w(34)*(d(65)+d(69)-d(64))+w(35)*(d(65)+d(69)-d(64))+w(33)*(d(65)+d(69)-d(64))=381625ans[8]=w(17)*(d(58)+d(101)-d(59))=212670ans[10]=w(21)*(d(65)+d(64)-d(69))+w(49)*(d(64)+d(65)-d(69))=77015ans[11]=w(19)*(d(60)+d(62)-d(64))+w(34)*(d(60)+d(62)-d(64))+w(35)*(d(60)+d(62)-d(64))+w(33)*(d(60)+d(62)-d(64))+w(21)*(d60)+d(62)+d(65)-d(69))+w(49)*(d(60)+d(62)+d(65)-d(69))=650969第一问得到的总费用为9304885元，如果破坏方选取的策略是使对方总费用增加25%，而每破坏一条道路都需要本钱和代价，因此需要破坏最少的道路。根据上表我们发现，破坏3-4和4-5，10-11，17-45，19-20和20-21这六条道路，得到的总费用情况最接近使对方总费用增加25%这一策略。破坏后六条道路后的供给分布图如下：图4：破坏道路后的供给分布图破坏3-4和4-5，10-11，17-45，19-20和20-21这六条道路多消耗的费用为2403543元(接近9304885*25%=元)。道路破坏是独立事件，相互之间不影响。根据问题一中的供给分布图可以看到破坏6,8对费用无影响，固破坏道路序号为1、2、3、4、5、7、9，此时，增加的最大平均费用为：其中：r[i]为破坏道路序号；i增加的费用；p[i]为破坏道路i的概率；max_crease为破坏道路增加费用的最大平均值。r=[107800,1081120,38357,239514,381625,0,212670,0,77015]p=[0.6,0.7,0.45,0.5,0.55,0.4,0.5,0.6,0.6]max_crease=r(3)*p(3)+r(4)*p(4)+r(7)*p(7)+r(1)*p(1)*(1-p(2))+r(2)*p(2)*(1-p(1))+1300390*p(1)*p(2)+r(5)*p(5)*(1-p(9))+r(9)*p(9)*(1-p(5))+650969*p(5)*p(9)得到：max_crease=1431200根据以上分析可以得到：破坏道路的序号为1、2、3、4、5、7、9，平均总费用为1431200元七、模型的优缺点〔1〕可以解决线性,非线性,整数规划无法有效求解的复杂问题；〔2〕容易找到全局最优解；〔3〕可以得到一组解。〔1〕没有标准的模型可供给用,构模依赖于个人的经验和技巧；〔2〕状态变量需满足无后效性,有较大的局限性；〔3〕动态规划的维数灾难限制了对规模较大问题的求解效率。〔1〕不依赖于所求问题的具体数学表达式描述，具有很强的找到全局最优解的优化能力；〔2〕该算法具有正反应、较强的鲁棒性、全局性、普遍性、优良的分布式并行计算机制、易于与其他方法相结合等诸多优点。〔1〕蚁群算法的成功主要在实验层次上，很少有理论来解释利用蚁群算法为什么能够成功地解决这些问题，它没有坚实的数学根底；〔2〕蚁群算法的模型普适性不强，其模型不能直接应用于实际优化问题；〔3〕蚁群算法的局部搜索能力较弱，易于出现停滞和局部收敛、收敛速度慢等问题，因而往往需要嵌入一些专门的辅助技巧；〔4〕长时间花费在解的构造上，从而导致搜索时间过长；〔5〕算法最先基于离散问题，不能直接解决连续优化问题。八、参考文献［1］CHRISTOPHERM．通过降低本钱和增加服务的物流与供给链管理策略(第二版)［M］．:电子工业，2003．［2］赵启兰，王稼琼，X宏志．物流规划中的需求与潜在需求分析［J］．中国软科学，2004(2):92—95．［3］肖月，倪梅，李伊松．物流需求分析指标研究［J］．铁道物资科学管理，2003(2):33—34．［4］X波，孙林岩．从供给链到需求流动网［J］．工业工程，2007，10(2):1—6．［5］陈剑，蔡连侨．供给链建模与优化［J］．系统工程理论与实践，2001(6):26—33．［6］任鸣鸣．供给链系统节点设施选址研究［D］．某某:华中科技大学，2008．[7]李嘉.一类特殊车辆路径问题[J].东北大学学报〔自然科学版〕，2001,22〔3〕[8]X涛，X明杰，王梦光.不确定车辆数的车辆路径问题模型和混合算法[J].系统工程理论方法应用，2003〔2〕[9]王正彬，杜文.考虑线路安排的物流配送方案模型与其算法研究[J].技术交流，2003〔12〕[10]尹晓峰，杜艳萍.车辆路径问题的蚁群算法研究[J].某某科技大学学报，2005,26〔4〕九、附录%画49个城市散点图的代码x=[3639,3712,3488,3326,3238,4196,4312,4386,4177,3918,4061,3780,4029,3676,3715,3429,3507,3394,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]y=[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,2509,3305,1069,702,696,737,971,1603,2285,2613,2920,3374,2710,2055,1893,1633,2290,2749,919,261]a=[1,3,4,5,7,10,11,12,13,14,15,16,17,18,19,20,22,23,24,25,26,27,28,30,40,43,44,45]fori=1:49ifismember(i,a)==1plot(x(i),y(i),'.red','MarkerSize',10);elseplot(x(i),y(i),'.black','MarkerSize',10);endholdontext(x(i),y(i),num2str(i));end%求邻接矩阵的代码s=[11111122333444455566677789991010101010101111111212121213131313131414141515151616161617171718181818191919191920202020212222222222232323242425262627272727282828303335384040414446]d=[23561540315415165162730304047739408404142101115111214153843131437141617431419323637