粮仓选址问题的数学模型.pdfVIP

第 27卷 第 1期 北 京 建 筑 工 程 学 院 学 报 V01．27 NO．1 2011年 3月 JournalofBeijingUniversityofCivilEngineeringandArchitecture Mar．2011 文章编 号 ：1004—6011(2011)01—0069—03 粮仓选址 问题的数学模型 代西武 (北京建筑工程学 院 理学院 ，北京 100044) 摘 要：提 出了计算加权 图中任意两点之 间最短距离的算法——Dijkstra矩阵算法，证 明了结论 ： 当粮仓可建在村庄里或道路上时，则粮仓建在村庄里可使总运费达到最小．因此 ，粮仓建在道路上 不能使 总运 费更少，不必要建在道路上．给 出了最优粮仓地址 的计算方法，对一个具体例子 ，求出 了最优 粮仓 地址 ． 关键词 ：粮仓选址 ；Dijkstra算法；最短路 问题 中图分类号 ：O157．6 文献标志码 ：A M athematicalM odelforSelectingGrain StorePosition DaiXiwu (SchoolofScience，BUCEA，Beijing，100044) Abstract：Inthispaper，theDijkstra’Smatrixalgorithm isproposed，whichistocalculatetheshortest distancebetweentwoarbitraryvertexesinaweightedgraph．Theprovedconclusion：Ifgrain storecanbe builtinavillageoron apath，theminimum transportcostswillbeachievedbybuildinggrain storeina village．The method fordetermining the bestposition ofgrain store is supplied，and an example is calculated． Keywords：grainstoreposition；dijkstra’Salgorithm；problem oftheshortestpath 1 问题提 出 某乡有 12个 村庄 ， ，…， 两村连线上的 数字表示两村之 间的公路距离 (单位 ：km)，各村上 缴粮食数量依次为 ：70t，80t，60t，30t，65t，100t， 图 1 12村 庄 图 20t，40t，30t，45t，35t，20t．现计划建一个粮仓来 算法——D stra矩阵算法，证 明了结论 ：当粮仓可 储存这些粮食 ，粮仓可以建在村庄里或道路上 ，请确 建在村庄里或道路上 时，则粮仓建在村庄里可使总 定粮仓 的地址 ，使运输的总费用最小 ，并求出最小的 运费达到最小．因此 ，粮仓建在道路上不能使总运 总运费．假设粮食的运费为 1．5元 ／km ·t． 费更少 ，不必要建在道路上．我们还给 出了最优粮 这就是粮仓选址 问题． 仓地址 的计算方法 ，对上面给出的具体例子 ，求出了 自然地 ，各村庄 、村庄之间的公路及距离可以看 最优粮仓地址为 村． 成是图论里的加权 图，可用图论知识来求解此 问题． 参考文献 [1]中，对粮仓选址问题进行 了探讨 ， 我们提出了计算加权图中任意两点之间最短距离的 给出的计算方法复杂 ，也没有给 出理论证明．我们 收稿 日期 ：20