仓库选址问题论文 数学建模

王智、余万科、傅天赋仓库选址模型11/18仓库选址问题目录摘要..........................................................................................................................2关键词......................................................................................................................2一、问题提出.....................................................................................................3二、模型假设.....................................................................................................4三、求解最短路径问题的数学背景介绍..............................................................5四、模型的建立和求解.......................................................................................74.1如果整个公路的运费相同，则确定建库位置，使总运费最少........................................74.2若各段公路的单位运费不同，仓库在各处的造价不同且仓库能造在各村或公路上，则确定建库位置，使总运费最少.......................................................................................................................84.3模型的评价..........................................................................................................................114.3.1.模型的优点..................................................................................................................114.3.2.模型的缺点..................................................................................................................11五、参考文献...................................................................................................12六、附录..........................................................................................................136.1dataScript.m代码文件........................................................................................................136.2dataScript2.m代码文件......................................................................................................146.3Dijkstra.m代码文件.............................................................................................................146.4findCost.m代码文件............................................................................................................166.5findCost2.m代码文件..........................................................................................................166.6main.m代码文件.................................................................................................................176.7main2.m代码.......................................................................................................................17王智、余万科、傅天赋仓库选址模型22/18摘要仓库地址的选择是一个最优化问题，因此我们利用“图论的最短路”问题思想，对模型作出了简化，提出了一般的解法，另外我们还简便的确定了物理模拟的方法确定了总费用最少的位置。对于问题1，我们确定了建立仓库的最优位置在E村庄，运输总费用最少为65925元；对问题2，最优位置在E村庄，运输的总费用与建库费用之和为83525元。关键词仓库选址、最短路、图论、Dijkstra算法王智、余万科、傅天赋仓库选址模型33/18一、问题提出实际问题：某镇有十二个村子A，B，C、、、、、、L，任何两个村子之间都是相通的，只是有的村是有道路直接相连，有的是通过其他村子联系在一起，直接相连的村子和它们之间的距离如表1-1所示：ABBCBFCDCIDEDGEFEKGFHIHKIJJKJL5853105328246353表1-1各个村庄之间的距离（单位：千米）各村应上缴粮食数量如表1-2所示：ABCDEFGHIJKL7080603065100204030453520表1-2各个村庄应上缴的粮食量现计划在村内建一仓库来储存这些粮食.现要求如下：若整个公路上的运费为15元/(t·km)，确定建立仓库的位置，使运输的总费用最少.若公路BF、FE、ED、DG、GH上的运费为20元/(t·km)，而其余公路上的运费为15元/(t·km)，各村的建库费分别为5100、5000、5200、5150、5400、5300、5200、5250、5400、5110、5010、5120元，而公路上的建库费与最近的村相同.设计确定使总费用之和最少的仓库位置的方案.王智、余万科、傅天赋仓库选址模型44/18二、模型假设不考虑在各村各村的仓库的经济寿命问题不考虑各村的实际尺度，简化为点处理假设各村之间可以随意经过王智、余万科、傅天赋仓库选址模型55/18三、求解最短路径问题的数学背景介绍在带权图G=(V，E)中，若顶点𝑉𝑖𝑉𝑗是图G的两个顶点，从顶点𝑉𝑖到𝑉𝑗的路径长度定义为路径上各条边的权值之和。从顶点𝑉𝑖到𝑉𝑗可能有多条路径，其中路径长度最小的一条路径称为顶点𝑉𝑖到𝑉𝑗的最短路径最短路径问题有一种简单的结构使得我们可以用非常直观的方法来求解。考虑如下物理类比。给定一个有两个特定定点u和v的最短距离，我们将全部用细绳来做模型。把绳子通过不会滑落的打结系在一起。结与顶点对应，而绳子就是边。绳子的长度等于边的权重（距离）（吧绳子加到足够长打结就可以了）。当然，如果图中表示的距离以千米计的话，那么我们就要，例如说，按比例把千米改成厘米，来建立我们的绳子模型。现在为了求解最短路径的长度，我们握紧表示顶点u和v的两个结，并把所有的绳子向外拉开直到有些绳子被拉紧为止。于是，原来图中的最短路径长度就对应于两个结之间的距离。而且这个模型还显示了哪些路径是最短的（那些拉紧的绳子）。松的绳子称为有“松弛”，这说明即使他们稍微短一点，最短路径的长度也不会改变。这个类比就是我们要用到算法的基础。注意，我们将要提出的求对所有的𝑖𝑗ϵE𝐺满足𝐶ij≥0的任何图的最短路径的步骤都是可行的。给定非负边长𝐶ij≥0，下面步骤将求的图G中从顶点s到顶点t的最短路径的长度。Dijkstra最短路径算法输入图G=(V，E)有一个原顶点s和一个原汇点t，以及对所有的边𝑖𝑗ϵE(𝐺)的非负边长𝐶ij输出G中从s到t的最短路径的长度第一步从对每个顶点做临时标记L开始，做法如下：L(s)=0，且对除s外所有的顶点L（i）=∞。第二步找带有最小临时标记的顶点（如果有结，随机取一个）。使该标记变王智、余万科、傅天赋仓库选址模型66/18成永久标记，亦即该标记不会改变第三步对每个没有永久标记但有与带有永久标记的顶点相邻的顶点j,按如下方法计算一个新的临时标记：𝐿(𝑗)=min{𝐿(𝑖)+𝐶ij},求最小是对所有带有永久标记的顶点i做的。重复第二步和第三步，直到所有的顶点都打上了永久标记为止。王智、余万科、傅天赋仓库选址模型77/18四、模型的建立和求解4.1如果整个公路的运费相同，则确定建库位置，使总运费最少对此问题，我们应用图论中的Dijkstra最短路径算法。作图，令每个村庄为一个点（分别用1,2,3，„„，12表示），如果连村庄之间有公路，则在该两点之间连线。因为整个公路的运费相同，所以可以用相邻两村庄（例如i村庄和j村庄）的路程来作为每条边的权重𝑑ij。第一步假设在第i个村庄建设仓库，则第j个村庄到第i个村庄的最短距离可根据Dijkstra最短路径算法求解,得𝐿ij。𝐿ij组成一个12×12的对角方阵。V1V2V3V4V5V6V7V8V9V10V11V12V10513161210192123252028V25081175141618201523V3138038106810131416V416113057359121115V512785028101413816V610510720101216151018V71914638100269812V821168510122047610V923181091416640386V10252013121315973053V1120151411810868508V1228231615161812106380表4-1利用Dijkstra算法求出的最短路径表第二步根据上一步解出的任意两个村庄的最短距离𝐿ij，求解在第i村庄建设仓库，各个村庄到i村庄的运费总和Cost𝑖。Cost𝑖可根据如下公式求的：Cost𝑖=𝑊𝑗·𝐿ij·𝑝12𝑗=1其中：𝑊𝑗为第j个村庄应上缴粮食数量（单位为:吨t）,𝐿ij为则第j个村庄到第i个村庄的最短距离（单位为：千米km），𝑝=15元/(t·km)为题中所给的单位运费。王智、余万科、傅天赋仓库选址模型88/18第三步根据第二步中求的的Cost𝑖（i=1,2,3，„„，12）这12个数，找出最小的情况。解得最小运费Q。𝑄=Min(Cost𝑖)运行matlab脚本程序main，即可获得如下输出：costs=Columns1through61160258190079425744006592