旅行商问题数学建模

./理工学院数学建模大型作业2011—2012学年第1学期目录一．摘要二．旅行问题问题描述符号说明模型设计建模求解模型分析三．建模过程及心得体会四．参考文件一．摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一,是一个依赖与每个城市去一次且仅去一次的路线确定问题,问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。关键词：HAMILTON回路LINGO最优旅行路线0-1模型二．旅行问题问题描述某人要在假期从城市A出发,乘火车或飞机到城市B,C,D,E,F旅游购物。他计划走遍这些城市各一次且仅一次,最后返回城市A。已知城市间的路费数据见附表1,请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市,该怎样修订旅行路线？在城市间旅游时他计划购买照相机,衣服,书籍,摄像机,渔具,白酒,食品,而受航空行重量的限制以及个人体力所限,所买物品的总重量不能超过15kg,各种物品的价格见附表2.请你为他决策买哪些物品,使所买物品价值最大。附表1：ABCDEFA0120250330210150B120098350225300C250980520430280D3303505200270185E2102254302700420F1503002801854200附表2照相机衣服书籍摄像机渔具白酒食品香烟重量〔kg12434221价格<元>1300275032043501400300120600模型设计首先给出一个定义：设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。则旅行问题的数学模型可表示为一个整数规划问题。minz=<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:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..6/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=0120250330210150120098350225300250980520430280330350520027018521022543027004201503002801854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果：总费用为1163路线：A-B-C-F-D-E-A问题2.临时因故只能去4个城市,那么应该怎样安排旅行路线。分析：在B,C,D,E,F五个城市中选4个城市,显然有5种可能,按照问题一中的模型,将费用矩阵稍作修改,运用LINGO分别解除5种可能的费用,进行比较,即得结果。〔1选取B,D,E,F,计算旅行费用：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=01203302101501200350225300330350027018521022527004201503001854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果：总费用：950路线：A-B-E-D-F-A<2>选取B,C,E,F,计算旅行费用：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025021015012009822530025098043028021022543004201503002804200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果：总费用：963路线：A-E-B-C-F-A<3>选取B,C,D,F,计算旅行费用：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025033015012009835030025098052028033035052001851503002801850;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果：总费用：1013路线：A-B-C-F-D-A<4>选取路线:B,C,D,E,计算旅行费用：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=012025033021012009835022525098052043033035052002702102254302700;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果：总费用：1173路线:A-C-B-E-D-A<5>选取C,D,E,F,计算旅行费用：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..5/:U;!U<I>=sequenceno.ofcity;LINK<CITY,CITY>:COST,!Thecostmatrix;X;!X<I,J>=1ifweuselinkI,J;ENDSETSDATA:!Costmatrix,itneednotbesymmetric;COST=02503302101502500520430280330520027018521043027004201502801854200;ENDDATAN=SIZE<CITY>;MIN=SUM<LINK:COST*X>;FOR<CITY<K>:!Itmustbeentered;SUM<CITY<I>|I#NE#K:X<I,K>>=1;!Itmustbedeparted;SUM<CITY<J>|J#NE#K:X<K,J>>=1;!Weakformofthesubtourbreakingconstrains;!Thesearenotverypowerfulforlargeproblems;FOR<CITY<J>|J#GT#1#AND#J#NE#K:U<J>>=U<K>+X<K,J>-<N-2>*<1-X<K,J>>+<N-3>*X<J,K>>;>;FOR<LINK:BIN<X>>;!MaketheX's0/1;!Forthefirstandlaststopweknow...;FOR<CITY<K>|K#GT#1:U<K><=N-1-<N-2>*X<1,K>;U<K>>=1+<N-2>*X<K,1>>;END得到结果：总费用：1195路线：A-C-F-D-E-A因此,总结以上〔1,〔2,〔3,〔4,〔5五种情况可得:应该选用路线：A-B-E-D-F-A。总费用花费最少,为950.问题3.在城市间旅游时他计划购买照相机、衣服、书籍、摄像机、渔具、白酒、食品、香烟等物品,而受航空行重量的限制以及个人体力所限,所买物品的总重量不能超过15kg,各种物品的价格见附表2。请你为他决策买哪些物品,使所买物品总价值最大？分析:解读题意,实际上此题涉及背包问题,题目转化为一个限重15公斤的背包,要求在8件可带可不带的物品中做出合理的方法。模型建立：将照相机,衣服,书籍,摄像机,渔具,酒,食品和香烟编号为1,2,3,4,5,6,7,8。设总容量为b,为每个物品的重量,为每个物品各自的价格。定义一个变量,当=1是,表示装第i件物品,当=0时,则不装〔i=1,2,……,8.则约束条件为：maxz==0或1,〔i=1,2,……,8模型求解：利用LINGO软件求解,在LINGO中输入以下程序：model:sets:M/1..8/:W;price/1..8/:p;number/1..8/:x;endsetsda