excel求解旅行商问题及实现

excel求解旅行商问题及实现

ID:24189036

大小:63.12 KB

页数:4页

时间:2018-11-12

excel求解旅行商问题及实现_第1页
excel求解旅行商问题及实现_第2页
excel求解旅行商问题及实现_第3页
excel求解旅行商问题及实现_第4页
资源描述:

《excel求解旅行商问题及实现》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库

1、Excel求解旅行商问题及实现摘要:旅行商问题历来是大家感兴趣的一个难题,对其求解也有各种算法。Excel中规划求解也是有效解决问题的方案之一,通过介绍其基本原理,求解思路和在旅行商问题中的具体实现步骤,希望能对读者学习Excel的高级应用有很好的借鉴作用。关键词:旅行商问题;规划求解;加载宏1引言旅行商问题(TSP),是假设一个旅行商出于业务需要,要到N个城市去,那么如何找出一条最佳的路径使其能既经过每个城市,又路径最短。旅行商问题在实际工作中有很多具体应用,如货物配送、家用管网规划、网络路由选择等。该类问题与普通的求最短路径的根本区别是:既要经过已知的所有节点,又要从起

2、点到终点形成封闭回路,在满足这两个前提下路径最短。对于较大规模的该类问题,需要通过智能算法(蝙蝠、蚁群等)求解,对于一定规模的旅行商问题可采用Excel的规划求解来解决。2方法概述规划求解是Excel的“可使用加载宏”的一种,它能够对存在多个变量的线性或非线性问题求解,以求出最优值。通过规划求解,可以帮助用户得到最优的设计方案。其工作原理是可以设计多个可调整的单元格,给出这些单元格需遵守的约束条件,同时给出目标单元格的公式,通过改变可变单元格的值,求出目标单元格的最大值、最小值或指定值。3解决方案:以下图为例,共有A、B、C、D、E、F六个城市,它们之间的路径及距离如图1所

3、示3.1打开Excel2010,建立一个工作簿,名为“旅行商问题”3.2在C4:C19单元格,用“9999”来替换如图所示,该步骤是给不存在的路径用一个很大的数来表示,防止以后选择该路径。3.3建立解决模型,如下图所示。在以上模型中,我们用“来源唯一性”限制出发地,用“目标唯一性”限制抵达地,以确保都任何时候只能走一条路径,不能同时存在多条路径。打开Excel2010的“加载宏”选择,选择其中的“规划求解加载项”前的复选框,然后“确定”,操作后我们再打开“数据”选项卡,就能看到“规划求解”。给单元格输入公式,其中,114单元格=sum(cl4:hl4),填充115:11C2

4、0单元格=sum(cl4:cl9),填充D20:H20J14单元格=sumproduct(c4:h4,cl4:hl4),填充jl5:J19J20单元格=sum(jl4:jl9)C14:H19的“单元格格式”我们可以设置为“数字”,选择“自定义”中的“0”,我们用该区域表示实际路径的选择情况,选择即为“1”,不选即为“0”,然后对应出发地、抵达地,形成一条回路。这个区域是可变区域,代表了不同路径的组合可能,j20是规划求解的目标单元格,即总路径,在这里,根据题意我们给j20选“最小值”。3.4观察求解结果,可以看到,选择的路径是:C-A-C,B-D-B,E-F-E,它们不能形

5、成封闭回路,所以不符合要求,为解决这个问题,我们需要加上限制条件,防止返回情况发生,也就是E14和C16不能同时为“1”,F15和D17不能同时为“1”,H18和G19不能同时为“1”在下面可选C23:C25输入这些“添加条件”,C22单元格录入“添加条件”,C23至C25录入公式。C23单元格=E14+C16C24单元格=F15+D17C25单元格=H18+G193.5继续规划求解,可以在“规划求解参数,,对话框中增加约束条件,设置C23:〔25

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。