最短路径最少费用数学建模论文

《最短路径最少费用数学建模论文》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，即高质量高速度的完成送货任务，针对本案例，我们采用了大量的科学分析方法，并进行了反复验证，得出如下结果：问题1：根据所给问题与数据，我们将题目中给出的城市，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路.在此基础上，我们通过观察分析计算对上述结果进行修正，然后我们再采用穷举法对问题结果进行验证，结果相吻合。最终得到如下路线：北京à香港à湖南à海南à广西à重庆à河南à云南à西藏à新疆à青海à

2、甘肃à宁夏à江苏à福建à上海à台湾à上海à黑龙江à内蒙古à黑龙江à吉林à北京。（最短时间为61小时）问题2：由于题中有货物重量与体积限制，货机一次最多只能载50件产品，考虑19个城市的总需求为114，这就估算出至少需要返回2次，采用逆向求解的方法，相当于3架货机同时送货，要设计线路使总共花费的时间最短，尽量使送货任务均衡，最大限度不超过50件货物，最后得出结果为：北京à吉林à黑龙江à内蒙古à新疆à西藏à云南à河南à北京à重庆à广西à海南à湖南à香港à北京à重庆à青海à甘肃à宁夏à江苏à福建à上海à台湾à上海à北京。（总的时间为71.77777）（其中红色表示只路过不送货）

3、问题3：要求问题1，2的花费最少，只需对前两个模型做进一步优化即可，经过优化计算我们得到如下结果：问题1的最少花费为584250（元），路线如下：北京à香港à湖南à海南à广西à重庆à河南à云南à西藏à新疆à青海à甘肃à宁夏à江苏à福建à上海à台湾à上海à黑龙江à内蒙古à黑龙江à吉林à北京问题2的最少花费为711750（元），线路如下：北京à吉林à黑龙江à内蒙古à新疆à西藏à云南à河南à北京à重庆à广西à海南à湖南à香港à北京à重庆à青海à甘肃à宁夏à江苏à福建à上海à台湾à上海à北京。关键词：关键字：最短路径送货线路优化赋权连通简单无向图Excel最小生成树12§1问题的

4、重述一、问题背景现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，现有实业公司，该实业公司专业生产某专用设备产品，专用设备产品每件重达5吨（其长5米，宽4米，高6米），该实业公司库房设在北京，所有货物均由一货机送货，该机种飞机翼展88.40米（机身可用宽20米），机长84米（可用长50米），机高18.2米（可用14米），最多可装载250吨货物，起飞全重达600吨，平均速度为900公里/小时，将货物送至全国各个省辖市（图1所示红色圆点，除北京之外共19个省辖市），假定货机只能沿这些连通

5、线路飞行，而不能走其它任何路线；但由于受重量和体积限制，货机可中途返回取货。经过的各个省市都要一定的停靠费用和停靠时间（停靠时间为常量2小时），假设经过某个省市的停靠费用为：停靠费用=5000元×该省市的消费指数.二、相关数据1、各个城市间的通路和权数1、上图1描述了中国各个省市之间的航班以及权重以图中标注为准；122、有些省市之间是没有航班，需要中转。2、城市消费指数和需求量数据表表1省辖市新疆青海宁夏云南北京湖南海南福建台湾吉林需求量（件）13540103498消费指数1.21.11.051.31.91.41.71.61.91.2省辖市甘肃西藏重庆内蒙古河南广西香港江

6、苏上海黑龙江需求量（件）79125456973消费指数1.31.01.51.21.31.21.81.51.81.3三、要解决的问题1、问题一：若图示中19个省辖市每个省辖市只要一件产品请设计送货方案，使所用时间最少，标出送货线路。2、问题二：若图示中19个省辖市需求量见表1，请设计送货方案，使所用时间最少。3、问题三：若该实业公司为了花费最少，针对问题1和问题2分别求出花费、标出送货线路。§2问题的分析现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，在有限的单次最大载重的前提下，考

7、虑在时间允许的范围内如何将货物最快、最省钱的送到客户手中。我们要研究制定既省时又省钱的最佳送货计划。一、对问题的具体分析1、对问题一的分析：我们对第一问要求时间最短，我们最短时间转化最短距离，围绕货物所要运到的地址数据及这些地址之间的距离，采用Floyd算法进行求解得到任意两地之间的最短距离，再根据最小生成树的求法可以求出该图G的最小生成树，由于该问题研究的是闭合回路，所以又需要对问题进行整体优化，最后得出了最佳飞行线路。2、对问题二的分析：根据重量、体积和各个城市的需求量的限制，货机一次最多只能载50件产品，考虑19个城市的