最短路径问题在城市超市选址中的应用.doc

毕业论文〔设计〕

最短路径问题在城市超市选址中的应用

院系:

数学与计算机学院

专业:

数学与应用数学

年级〔班级〕:

2010级

姓名:

陈妹珠

学号:

20104041011

指导教师:

谭秋月

职称:

讲师

完成日期:

2014年5月20日

摘要

对于最短路径问题的探索研究,向来都是数学界和计算机科学界所热衷研究的一个方向.它不仅在学术上具有重要的理论意义,更对于实际生活的生产有着举足轻重的实用价值.例如在医疗平安上的应急急救系统、政府的城市规划系统、卫星电子导航系统等其他领域.同时,最短路径问题又可以进一步引申为最少时间问题、最低费用问题等,但它们的核心解题算法都是最短路径算法.

本文利用了图论中最短路径问题的相关知识及重要定理,对假设干最短路径算法进行归纳,同时研究城市超市选址的影响因素,最后将最短路径问题的局部知识应用到了城市超市选址中,建立数学模型并求解,由此解决了超市经营的首要前提——选址.

关键词:图论;最短路径;超市;选址

Abstract

Theresearchandexplorationoftheshortestpathproblemisalwaysbeahotspotforpassionateaboutmathsandcomputerscience.Itnotonlyhasimportanttheoreticalsignificanceinacademic,butalsohassignificantpracticalvaluefortheactualproductionoflife.Suchasemergencyfirstaidsystemonmedicalsafety,thegovernmentsurbanplanningsystem,electronicnavigationsatellitesystemandotherfields.Atthesametime,theshortestpathproblemandcanbefurtherextendedtoaminimumtimeproblem,theminimumcostproblem,etc.Butforthecoreofthealgorithm,itstheshortestpathalgorithm.

Inthispaper,theuseoftheshortestpathproblemingraphtheoryknowledgeandtheimportanttheorem,thenumberofshortestpathalgorithmsaresummarized,atthesametime,studyfortheinfluencefactorsofcitysupermarketsiteselection,thefinalwillbeappliedtotheshortestpathproblemofcitysupermarketsiteselection,establishmathematicalmodelandsolving,thussolvedthefirstpremiseofsupermarketbusiness-location.

Keywords:Graphtheory;Theshortestpath;Thesupermarket;Siteselection

目录

TOC\o1-2\h\z\u1引言1

2相关概念2

图的相关定义2

2.2最短路径3

3最短路径问题的相关介绍4

单源单汇最短路径问题4

单源多汇最短路径问题4

多源多汇最短路径问题5

4最短路径问题的相关算法6

Dijkstra算法6

SPFA算法7

Floyd算法8

5选址问题10

相关知识10

引用定理:11

6最短路径问题在超市选址中的应用12

问题提出12

问题分析13

模型假设14

符号说明14

模型原理14

模型建立与求解16

模型结果20

7结论21

谢辞22

参考文献23

最短路径问题在城市超市选址中的应用

1引言

最短路