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

摘 要 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，即高质量高速度的完成送货任务，针对本案例，我们采用了大量的科学分析方法，并进行了反复验证，得出如下结果： 问题1：根据所给问题与数据，我们将题目中给出的城市，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路.在此基础上，我们通过观察分析计算对上述结果进行修正，然后我们再采用穷举法对问题结果进行验证，结果相吻合。最终得到如下路线： 北京à香港 à 湖南à海南à 广西 à重庆 à 河南 à云南 à西藏 à新疆 à 青海 à 甘肃 à宁夏 à江苏à 福建 à上海 à台湾 à上海 à黑龙江 à内蒙古 à黑龙江à吉林 à北京。（最短时间为61小时） 问题2：由于题中有货物重量与体积限制，货机一次最多只能载50件产品，考虑19个城市的总需求为114，这就估算出至少需要返回2次，采用逆向求解的方法，相当于3架货机同时送货，要设计线路使总共花费的时间最短，尽量使送货任务均衡，最大限度不超过50件货物，最后得出结果为：北京 ? 吉林 ? 黑龙江 ? 内蒙古 ? 新疆 ? 西藏 ? 云南 ? 河南 ? 北京 ? 重庆 ? 广西 ? 海南 ? 湖南 ? 香港 ? 北京 ? 重庆 ? 青海 ? 甘肃 ? 宁夏 ? 江苏 ? 福建 ? 上海 ? 台湾 ? 上海 ? 北京。（总的时间为71.77777）（其中红色表示只路过不送货） 问题3：要求问题1，2的花费最少，只需对前两个模型做进一步优化即可，经过优化计算我们得到如下结果： 问题1的最少花费为584250（元），路线如下：北京à香港 à 湖南à海南à 广西 à重庆 à 河南 à云南 à西藏 à新疆 à 青海 à 甘肃 à宁夏 à江苏à 福建 à上海 à台湾 à上海 à黑龙江 à内蒙古 à黑龙江à吉林 à北京 问题2的最少花费为711750（元），线路如下：北京 ? 吉林 ? 黑龙江 ? 内蒙古 ? 新疆 ? 西藏 ? 云南 ? 河南 ? 北京 ? 重庆 ? 广西 ? 海南 ? 湖南 ? 香港 ? 北京 ? 重庆 ? 青海 ? 甘肃 ? 宁夏 ? 江苏 ? 福建 ? 上海 ? 台湾 ? 上海 ? 北京。 关键词：关键字：最短路径 送货线路优化 赋权连通简单无向图 Excel 最小生成树 §1 问题的重述 一、问题背景 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，现有实业公司，该实业公司专业生产某专用设备产品，专用设备产品每件重达5吨（其长5米，宽4米，高6米），该实业公司库房设在北京，所有货物均由一货机送货，该机种飞机翼展88.40米（机身可用宽20米），机长84米（可用长50米），机高18.2米（可用14米），最多可装载250吨货物，起飞全重达600吨，平均速度为900公里/小时，将货物送至全国各个省辖市（图1所示红色圆点，除北京之外共19个省辖市），假定货机只能沿这些连通线路飞行，而不能走其它任何路线；但由于受重量和体积限制，货机可中途返回取货。经过的各个省市都要一定的停靠费用和停靠时间（停靠时间为常量2小时），假设经过某个省市的停靠费用为： 停靠费用=5000元×该省市的消费指数. 二、相关数据 1、各个城市间的通路和权数 1、上图1描述了中国各个省市之间的航班以及权重以图中标注为准； 2、有些省市之间是没有航班，需要中转。 2、城市消费指数和需求量数据表 表1 省辖市 新疆 青海 宁夏 云南 北京 湖南 海南 福建 台湾 吉林 需求量（件） 1 3 5 4 0 10 3 4 9 8 消费指数 1.2 1.1 1.05 1.3 1.9 1.4 1.7 1.6 1.9 1.2 省辖市 甘肃 西藏 重庆 内蒙古 河南 广西 香港 江苏 上海 黑龙江 需求量（件） 7 9 12 5 4 5 6 9 7 3 消费指数 1.3 1.0 1.5 1.2 1.3 1.2 1.8 1.5 1.8 1.3 三、要解决的问题 1、问题一：若图示中19个省辖市每个省辖市只要一件产品请设计送货方案，使所用时间最少，标出送货线路。 2、 问题二：若图示中19个省辖市需求量见表1，请设计送货方案，使所用时间最少。 3、问题三：若该实业公司为了花费最少，针对问题1和问题2分别求出花费、标出送货线路。 §2 问题的分析 现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个需要以最快的速度及时将送达，重量体积限制平均速度为公里/小时 北京 A11 甘肃 A2 青海 A12 西藏 A