第3章-最短路径编程.doc

2004高教社杯全国大学生数学建模竞赛 承 诺 书 我们仔细阅读了中国大学生数学建模竞赛的竞赛规则. 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。 我们的参赛报名号为： 参赛队员 (签名) ： 指导教师或指导教师组负责人 (签名)： 赛区评阅编号（由赛区组委会评阅前进行编号）： 2004高教社杯全国大学生数学建模竞赛 编 号 专 用 页 赛区评阅编号（由赛区组委会评阅前进行编号）： 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）：奥运会临时超市网点的优化设计 摘要：本文运用Matlab软件详细分析了图3的原始数据，求出其规律。为了求出观众最短的出行线路，我们对原题中的图2进行简化处理，得到无向加权图，并运用Floyd算法得到每个看台上的人到其目的地的最短路径。依据此图提出了人流量统计模型：既当各个看台上的人沿着最短路径行进时，根据问题1的求解反映出的规律，统计其所经过的商业区的人流量和潜在消费总额。根据其结果得到如下规律：一般地，人流量大的商业区，其消费总金额也多，人流量小的商业区，其所消费总金额也相应少。人流量最大的是A6区，其消费总金额也最大，但总金额并不与人流量成线形关系。 根据人流量和消费总金额的分布规律，考虑两种Ms的成本，我们提出了MS最优化规划模型：所有MS的占地面积之和不能大于商区的使用面积；所有MS所能接纳的客流量要大于等于商区的人流量；所有MS所能提供的购物总额要大于等于商区的购物欲望；目标函数为求最大利润。对于该模型，我们采用Matlab和Lindo软件相结合来进行求解，得出了较好的结果： 本文由word软件进行排版，并用运用Matlab进行编程，使用了大量的编程技巧，同时，本文还运用了Excel，Lindo等软件进行处理。 一、问题重述 根据原题图3的问卷调查数据分析出观众在出行、用餐和购物等方面所反映的规律。由此规律，在原题图2中表示的比赛主场馆的周边地区布置两种类型的MS,并且要求这种MS，在地点、大小类型和总量等三个方面满足奥运会期间顾客的购物需求、分布基本均衡和商业上赢利。 二、模型假设 1、观众来看比赛的交通方式与看完比赛后离去的交通方式是相同的。 2、对于一个观众来说，他一天的出行线路分为三段：(1)选择某种交通方式来到下车地点，下车后沿最短路径原则进入比赛场馆；(2)看完比赛后沿最短路径原则进入就餐场所(中餐馆、西餐馆、商场三者之一)；(3)就餐完后沿最短路径原则返回到原来的下车地点，选择相同的交通方式离去。观众没有到其他场地参观等活动。 以上三段行走线路中，观众可以到行走路线所经过的商区购物。即：如果观众行走线路中的某一段包含于一个商区的商圈中，则观众可以到此商区中的商店购物。如果观众行走线路中的某一段不包含于一个商区的商圈中，则观众不可以到此商区中的商店购物。 所有MS具有相同的竞争力。即：所有MS的商品种类和每种商品的价格是一样的。两种MS的区别只在于他们的商品的数量的多少。对于所有的MS，并不存在这样一种商品，它在这个MS买不到而在另一个MS买得到。 对于一个场馆，各个看台的满员率(实际观众数与看台容量之比)是相同的；每个看台的观众只通过与此看台相对应的出入口出入场馆。根据此假设，则一个场馆各个出入口的人流量是相同的。 所有场馆的满员率相同。为了确定MS的分布和数量，简化计算，进一步假设，在奥运期间所有场馆均满员。 不同看台的观众选择交通方式或就餐方式的比率是相同的。 由于奥运会的短期性，可假设MS的成本只与固定投资有关。 对于一个商区，每种MS的个数取决与此商区的人流量。因此，满足人流量的建设MS的方案也会满足分布要求。 10、性别和年龄不会影响人流量和消费欲望。 三、符号说明 1、交通方式T： A:私车 B:出租 C:公交(东西) D:公交(南北) E:地铁(西) F:地铁(东) 餐方式R: a:中餐 b:西餐 c:商场 消费档次：level (1≤level≤6) 商圈i的潜在销售量：si Ma(Mb): 大MS(小MS)每天可提供的购物总额(单位：元), Pa(Pb): 大MS(小MS)每天可接纳的人流量(单位：人次), Ca(Cb): 大MS(小MS)建设这种MS的固定投资成本(单位:元), Sa(Sb): 大MS(小MS)营业