旅行商问题数学建模.docVIP

黄石理工学院 数学建模 大型作业 2011—2012 学年 第1学期  目录 一．摘要 二．旅行问题 问题描述 符号说明 模型设计 建模求解 模型分析 三．建模过程及心得体会 四．参考文件 一．摘要 本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。 关键词：HAMILTON回路 LINGO 最优旅行路线 0-1模型 二．旅行问题 问题描述 某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F旅游购物。他计划走遍这些城市各一次且仅一次，最后返回城市A。已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市，该怎样修订旅行路线？ 在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。 附表1： A B C D E F A 0 120 250 330 210 150 B 120 0 98 350 225 300 C 250 98 0 520 430 280 D 330 350 520 0 270 185 E 210 225 430 270 0 420 F 150 300 280 185 420 0 附表2 照相机 衣服 书籍 摄像机 渔具 白酒 食品 香烟 重量（kg） 1 2 4 3 4 2 2 1 价格(元) 1300 2750 320 4350 1400 300 120 600 模型设计 首先给出一个定义：设v1,v2,......,vn是图G中的n个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON回路。 问题1. 分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。 模型建立： 对于6个城市的旅行问题设A,B,C,D,E,F六个城市分别对应v1,v2,v3,v4,v5,v6。假设表示从城市i到城市j的费用。定义0-1整数型变量=1表示从城市i旅行到城市j，否则=0。则旅行问题的数学模型可表示为一个整数规划问题。 min z= (ij) s.t. =1 （ij；j=1,2,……,6） =1 (ij；i=1,2,……,6) (ij;i=2,3,……,6;j=2,3,……6) 其中辅助变量（i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。事实上，在最优解中，=访问城市的顺序数。 模型求解 运用LINGO，输入程序： MODEL: !Traveling Sales Problem for the cities of six city; SETS: CITY / 1..6/: U; ! U( I) = sequence no. of city; LINK( CITY, CITY): COST, ! The cost matrix; X; ! X( I, J) = 1 if we use link I, J; ENDSETS DATA: !Cost matrix, it need not be symmetric; COST= 0 120 250 330 210 150 120 0 98 350 225 300 250 98 0 520 430 280 330 350 520 0 270 185 210 225 430 270 0 420 150 300 280 185