已阅读5页,还剩5页未读, 继续免费阅读
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第四讲旅行商问题,讲授:白丹宇,1,问题描述,货郎担问题在运筹学里是一个著名的命题。有一个串村走户卖货郎,他从某个村庄出发,通过若干个村庄一次且仅一次,最后仍回到原出发的村庄。问应如何选择行走路线,能使总的行程最短。类似的问题有旅行路线问题,应如何选择行走路线,使总路程最短或费用最少等。,现在把问题一般化。设有n个城市,以v1,v2,vn表示之。dij表示从vi城到vj城的距离。一个推销员从城市v1出发到其他每个城市去一次且仅仅是一次,然后回到城市v1。问他如何选择行走的路线,使总的路程最短。这个问题属于组合最优化问题,当n不太大时,利用动态规划方法求解是很方便的。,2,动态规划模型,设S表示从V1到Vi中间所有可能经过的城市集合,S实际上是包含除V1与Vi两个点之外其余点的集合,但S中的点的个数要随阶段数改变。状态变量(i,S)表示:从V1点出发,经过S集合中所有点一次最后到达到Vi最有指标函数fk(i,S)为从V1出发经由k个城镇的S到Vi的最短距离决策变量Pk(i,S)表示:从V1经由k个中间城镇的S到Vi城镇的最短路线上邻接Vi的前一个城镇,则动态规划的顺序递推关系为,3,例:求解四个城市旅行推销员问题,其距离矩阵如表所示。当推销员从v1城出发,经过每个城市一次且仅一次,最后回到v1城,问按怎样的路线走,使总的行程距离最短。,4,解:由边界条件可知:,当k=1时,即从v1城开始,中间经过一个城市到达vi城的最短距离是:,5,当k=2时,即从v1城开始,中间经过二个城市(它们的顺序随便)到达vi城的最短距离是:,6,当k=3时,即从v1城开始,中间经过三个城市(顺序随便)回到v1城的最短距离是:,由此可知,推销员的最短旅行路线是12431,最短总距离为23。,7,旅行商问题应用,物资运输路线问题自动焊机割咀路线问题管道铺设路线问题,8,课堂练习,求解四个城市的旅行商问题。问应如何选择行进路线,使从v1的出发到其他城
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2023年10月高教自考《市场营销策划》试卷含解析
- 2024年电磁传感器项目合作计划书
- 2024年智能配网产品项目合作计划书
- 铁路扣件试验方法 第6部分:恶劣环境条件的影响 编制说明
- 2024年智能型低压电器、智能型低压开关柜项目合作计划书
- 安徽省国家电网-2024年《信息安规》科目 单选题+多选题+判断题+简答题真题冲刺卷下半年A卷
- 《会展平面设计基础》-课程教学大纲
- 2024年风电电缆项目建议书
- 2024年10月自考00045企业经济统计学押题
- 运城市2024-2025 学年高三摸底调研测试(一模) 物理试卷(含答案)
- 2024-2030年全球与中国跑步袜市场应用规模与未来销售渠道趋势研究报告
- 商家线下引流推广合同协议书
- lt隧道施工安全步距要求
- 人教版美术六年级上册《第3课 远去的路》说课稿6
- 2024年青海省中考英语试卷真题(含答案解析)
- 2024年越南热塑性弹性体(TPE)行业现状及前景分析2024-2030
- 2024秋八年级英语上册 Unit 3 Im more outgoing than my sister教案 (新版)人教新目标版
- CJT 511-2017 铸铁检查井盖
- 2024年吉林省中考语文真题
- 《卵圆孔未闭规范化诊疗中国专家共识2024》解读课件
- 高中数学必修第一册《第二章 等式与不等式》单元测试卷(含解析)
评论
0/150
提交评论