旅行商问题数学建模

0黄石理工学院数学建模大型作业2011—2012学年第1学期1目录一．摘要二．旅行问题1.问题描述2.符号说明3.模型设计4.建模求解5.模型分析6.三．建模过程及心得体会四．参考文件2一．摘要本文是一个围绕旅行商问题和背包问题这两个经典问题的论文。问题一，是一个依赖与每个城市去一次且仅去一次的路线确定问题，问题二类似于问题一。问题三是一个依赖于可背重量限制的背包问题。关键词：HAMILTON回路LINGO最优旅行路线0-1模型二．旅行问题问题描述某人要在假期内从城市A出发，乘火车或飞机到城市B,C,D,E,F旅游购物。他计划走遍这些城市各一次且仅一次，最后返回城市A。已知城市间的路费数据见附表1，请你设计一条旅行路线使得他的总路费最少。如果临行他因故只能去4个城市，该怎样修订旅行路线？在城市间旅游时他计划购买照相机，衣服，书籍，摄像机，渔具，白酒，食品，而受航空行李重量的限制以及个人体力所限，所买物品的总重量不能超过15kg，各种物品的价格见附表2.请你为他决策买哪些物品，使所买物品价值最大。附表1：ABCDEFA0120250330210150B120098350225300C250980520430280D3303505200270185E2102254302700420F1503002801854200附表2照相机衣服书籍摄像机渔具白酒食品香烟重量（kg）12434221价格(元)13002750320435014003001206003模型设计首先给出一个定义：设v1,v2,......,vn是图G中的n个顶点，若有一条从某一顶点v1出发，经过各节点一次且仅一次，最后返回出发点v1的回路，则称此回路为HAMILTON回路。问题1.分析：这个优化问题的目标是使旅行的总费用最少，要做的决策是如何设定旅行路线，决策受的约束条件：每个城市都必须去，但仅能去一次。按题目所给，将决定变量，目标函数和约束条件用数学符号及式子表示出来，就可得一下模型。模型建立：对于6个城市的旅行问题设A,B,C,D,E,F六个城市分别对应v1,v2,v3,v4,v5,v6。假设ijd表示从城市i到城市j的费用。定义0-1整数型变量ijx=1表示从城市i旅行到城市j，否则ijx=0。则旅行问题的数学模型可表示为一个整数规划问题。minz=661ijijijdx(ij)s.t.61ijix=1（ij；j=1,2,……,6）61ijjx=1(ij；i=1,2,……,6)1ijijuunxn(ij;i=2,3,……,6;j=2,3,……6)其中辅助变量iu（i=2,3,……,6）可以是连续变化的，虽然这些变量在最优解中取普通的整数值（从而在约束条件中，可以限定这些变量为整数）。事实上，在最优解中，iu=访问城市的顺序数。模型求解运用LINGO，输入程序：MODEL:!TravelingSalesProblemforthecitiesofsixcity;SETS:CITY/1..6/:U;!U(I)=sequenceno.ofcity;4LINK(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;ENDSETS5DATA:!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);6@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;7!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