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

《供应链网络地建立与道路破坏问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实用文案供应链网络的建立与道路破坏问题1、问题重述全球化竞争的加剧促使越来越多的企业开始采用供应链管理策略，以实现企业的一体化管理。供应链是一个复杂的网状结构系统，其中设施系统是供应链的核心，在供应链研究中有着极其重要的地位。现有某物流公司要在全国49个城市之间建立供应链网络。为各城市提供货物供应。货物运输利用汽车进行公路运输。在该背景下，我们的目标在于给出合适的数学模型，通过模型能解决以下三个问题：问题1：现要从49个城市中选取部分城市作为供给点供应本城市及其它城市。费用产生包括建立供应点和运输费用，求出当总费用最少时，应当将

2、哪些城市作为供应点，并得到它们分别供应的城市以及此时的总费用。问题2：假定有某组织只能对该供应网络的某些道路进行破坏。当某条道路被破坏后，该条道路就不能再被使用，以前运输经过该道路的只有改道，但总是沿最短路运输。如何通过破坏最少的道路使对方总费用至少增加25%，给出具体的道路破坏方案和总费用。问题3：假定各道路能否被破坏具有随机性，即破坏成功与否服从一定的概率分布，运输方式和2中一样，运输时产生的费用按照各种情况下的平均费用来计算。如何破坏才能使对方的平均总费用增加最多，给出具体的道路破坏方案和平均总费用。文案大全实用文案1、符

3、号说明符号解释使用符号建立供应点费用城市需求量记录各供应点的取舍情况存储每个城市所对应的供应点临时存储每各城市到28个供应点的最短路径各城市到28个供应点最短路径建立供应站费用运输费用总费用49个城市到8个供应站的最短路径49个城市到最近供应站的距离存储道路被破坏情况各条道路被成功破坏的概率文案大全实用文案1、模型假设1.假定每个供应点货物充足，可以充分满足相应城市需求。2.问题二、三中的供应点不变，仍是问题一中求得的供应点。3.在问题二、三中，当某条道路被破坏后，该条道路就不能被使用，以前获取供应需经过该道路的城市需要改道，根

4、据当前可用路径，选择最近的供应点获取供应。4.问题所得结果均由计算机运算得出，问题三中由于存在小数计算，存在一定的运算误差。5.由于城市49获取供应必须经过路径21--49，因此，问题三中不考虑21--49道路，即该道路不能被破坏(问题二考虑)。6.不考虑所有外部因素，如天气，其他运输方式等等。2、模型的建立及求解模型表示：输入数据弗洛伊德算法求解最短路径回溯法遍历所有情况输出运算结果文案大全实用文案模型一——对于问题一的求解1.1模型的建立一、思路分析该问要求从28个城市中选取部分城市作为供应点供应全国49个城市，使总费用最小

5、，而该费用包括建立供应站的费用和运输的费用，因此我们利用穷举的方法，分别对28个城市进行取舍，求出各种情况下的总费用，比较得到最小总费用，从而得到对应的最优解。二、模型建立的步骤在二维坐标系中根据各节点之间的可达性及距离建立一个无向图，表示为G(V,E)。图的顶点由1，2，3，4，…，49共49个点组成，如图4.1.1所示。图4.1.1然后根据各节点之间的可达性及距离，利用弗洛伊德算法分别求解每个节点到其余48个节点的最短路径。弗洛伊德算法思想如下（程序部分源代码见附录）：1.从文案大全实用文案任意一条单边路径开始。所有两点之间

6、的距离是边的权，如果两点之间没有边相连，则权为无穷大。1.对于每一对顶点u和v，看看是否存在一个顶点w使得从u到w再到v比已知的路径更短。如果是，则更新它。2.将图用邻接矩阵G表示出来，如果从到有路可达，则，d表示该路的长度；否则，。3.定义一个矩阵D用来记录所插入点的信息，表示从到需要经过的点，初始化。4.把各个顶点插入图中，比较插入点后的距离与原来的距离，，如果的值变小，则。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。得到结果后，我们从中筛选出所有城市到这28个可作为供应点城市的最短路径，并将该结果

7、赋值给一个二维数组。利用穷举法穷举出28个可作为供应站的节点的取舍情况。针对每种情况，求出全国49个城市到各供应站的最短路径,求得的最小值，将其对应的供应点城市标号存于,然后分别计算sum1与sum2的值，公式如下：将sum1与sum2相加：得到该种情况对应的总费用。在程序中我们还设定了一个min来记录最小值，将每次的结果与该值比较，最后得到该最小值以及作为供应点的城市以及各供应点所供应的城市。文案大全实用文案上述步骤可以建立一个求最优解的模型，通过回溯算法得到所有情况下的结果，利用计算机的运算高速以及可以处理海量数据的优点，通

8、过编写程序来得到结果。1.2利用模型求解建立模型后可编写出解决本问题的程序，通过运行程序我们得到了最终结果，供应点为4,7,11,20,23,26,28,45。总花费为9197114元。程序部分源代码见附录。同样地，利用所建立的模型，对程序稍作修改，即可解决类似