目录一问题提出 (1)二问题分析 (1)三模型建立 (1)3.1模型一的建立 (3)3.2模型二的建立 (5)3.3模型三的建立 (6)四结果分析 (8)五模型评价 (8)5.1模型优点 (8)5.2模型缺点 (8)六参考文献 (9)旅游最短路一 问题提出周先生退休后想到各地旅游。

计划从沈阳走遍华北各大城市。

请你为他按下面要求制定出行方案：1. 按地理位置（经纬度）设计最短路旅行方案；2. 如果2010年5月1日周先生从沈阳市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案；3. 设计最省时的旅行方案，建立数学模型，修订你的方案；二 问题分析第一问要求按地理位置（经纬度）设计最短路旅行方案，求最短路径是一个典型的旅行售货商（TSP ）模型。

TSP 模型可解的是知道任意两个城市之间的距离，通过查阅资料可以华北各个城市所在的经纬度，所以首先就需要通过经纬度计算出任意两个城市之间的距离，得到一个距离矩阵，再建立()TSP 模型，对模型进行求解。

问题的目标函数为 ij n i nj ij x d z ∑∑==1min ()j i ≠其中10或=ij x ， 若1=ij x 表示周先生直接从i 市到j 市。

建立整数目标规划，用Lindo 软件求解，找出所有1=ij x ，确定最短路的旅行方案。

第二问要求最经济，所以应从票价方面进行考虑，通过查阅资料可得各城市之间航空、铁路（快车卧铺或动车）的不同票价，由于要求最经济的旅行互联网上订票方案，所以选取三种类型票价中最低的票价，构建票价矩阵。

用票价矩阵代替第一问中的距离矩阵，求解出一条最经济路径。

第三问要求设定省时的方案就需要考虑时间因素，因为以上三种交通工具中航空用时最短，选择飞机作为旅行交通工具。

通过查阅资料得到各城市间航班的时间矩阵，用时间矩阵代替第一问中的距离矩阵，求解一条最省时的路径。

三 模型建立在具体的实现上，我们采用了整数规划法，并辅以LINGO 软件编程实现在下述意义下，引入一些0—1变量：⎩⎨⎧≠=其他情况且到巡回路线是从0,1j i j i x ij其目标是使∑∑=n i nj ij ij x d 1)(j i ≠最小。

（ij d 表示i 市到j 市的距离）这里有两个明显的必须满足的条件：访问城市i 后必须要有一个即将访问的确切城市；访问城市j 前必须要有一个刚刚访问过的确切城市。

用下面的两组约束分别实现上面的两个条件。

⎪⎪⎩⎪⎪⎨⎧=≠==≠=∑∑==n j ij ni ij n j j i x n i j i x 11),2,1,(1),,2,1,(1 到此我们得到了一个模型，他是一个指派问题的整数规划模型。

但以上两个条件对于TSP 来说并不充分，仅仅是必要条件。

例如：以上两个条件都满足，但它显然不是TSP 的解，它存在两个子巡回。

这里，我们将叙述一种在原模型上附加充分的约束条件以避免产生子巡回的方法。

把额外变量i u ),2,1(n i =附加到问题中。

可把这些变量看作是连续的。

现在附件下面形式的约束条件：,1-≤+-n nx u u ij j i .2n j i ≤≠≤为了证明该约束条件有预期的效果，必须证明：(1)任何含子巡回的路线都不满足该约束条件；(2)全部巡回都满足该约束条件。

首先证明(1)，用反证法。

假设还存在子巡回，也就是说至少有两个子巡回。

那么至少存在一个子巡回中不含城市1.把该子巡回记为 1,2,1i ik i i ，则必有：⎪⎪⎩⎪⎪⎨⎧-≤+--≤+--≤+-11113221n n u u n n u u n n u u i ik i i i i 把这k 各式子相加，有1-≤n n ，矛盾。

故假设不正确，结论1得证。

下面证明(2)，采用构造法。

对于任意的总巡回1，1i … 1-n i ，1，可取 i u 为访问城市的顺序数，取值范围为{1,2,…,n-1}。

1 234 56因此，,2-≤-n u u j i .2n j i ≤≠≤下面来证明总巡回满足该约束条件。

(I)总巡回上的边⎪⎪⎩⎪⎪⎨⎧-≤-=+---≤-=+--≤-=+--112111112221n n n u u n n n u u n n n u u in in i i i i(II)非总巡回上的边⎩⎨⎧-∈-≤-=+--∈-=-≤-≤-+}{},3,2{,11},{},,3,2{,2,2,1,12211r i i r r j ir i n j n n n u u i i n j n r n n u u 从而结论(2)得证。

这样我们把TSP 转化成了一个混合整数线性规划问题。

我们就可以利用数学软件LINGO 来求解该问题。

ij n i njij x d z ∑∑==1min ()j i ≠ s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=-≤+-==∑∑==0,1011111i ij ij j i n j ij n i ij u x n nx u u x x 或 ()()()n j n i j i n i j i n j j i ,,3,2;,3,2;,,2,1;,,2,1; ==≠=≠=≠ 3.1模型一的建立虽然地球不是一个标准的球体，但南北与东西长度相差不大，可以假设地球为一个球体，球体半径6371229=R 公里。

根据球面定理用两点之间的经度差计算出东西向的距离差为： ()180÷⨯⨯-=R a a ji ij πλ 根据球面定理用两点之间的纬度差计算出南北向的距离差为： ()()1801802cos ÷⨯⨯-⨯⨯⨯-=ππμj i j i ij a a R b b 最后用勾股定理求出两点之间距离为： 22ij ij ij d μλ+=所有城市之间的距离矩阵 沈阳1 北京2 天津3 石家庄4 太原5 济南6 呼和浩特7 沈阳1 0 517.8 520.6 864.8 992.5 825.3 897.1 北京2 517.8 0 113.8 283.9 408.9 364.8 400.1 天津3 520.6 113.8 0 259.8 428.9 272.7 494.2 石家庄4 864.8 283.9 259.8 0 165.4 276.5 387.5 太原5 992.5 408.9 428.9 165.4 0 424.5 335.1 济南6 825.3 364.8 272.7 276.5 424.5 0 662.5 呼和浩特7 897.1 400.1 494.2 387.5 335.1662.5 0知道两个城市之间的距离，周先生要自某一城市出发巡回旅游，使总行程最短，可以看出就是在一个赋权完全图中，找一个最小权的Humilton 回路问题。

以点0 表示周先生的出发城市,称为源点,点N,,2,1 ,表示n 个周先生需访问的城市。

1=ij x 表示周先生需要从点i 到点j ，因外周先生一定离开某一个城市去另一个城市所以 j i ≠，0=ij x 表示不需要从点i 到点j ；i u 表示旅游城市的顺序数；ij d 表示对应城市j i →的距离。

建立目标函数以及约束条件为： ij n i njij x d z ∑∑==1min ()j i ≠ s.t.⎪⎪⎪⎩⎪⎪⎪⎨⎧≥=-≤+-==∑∑==0,1011111i ijij j i n j ij n i ij u x n nx u u x x 或 ()()()n j n i j i n i j i n j j i ,,3,2;,3,2;,,2,1;,,2,1; ==≠=≠=≠ 其中辅助条件()n i u i ,,2,1 =可以是连续变化的，虽然这些变量在最优解中是普通的整数值。

该模型的第一个约束条件是保证每一个城市必须旅游到，第二个约束条件表示旅行者必须离开每个城市。

若模型只有这两个约束，则是一个标准的分配问题，但其解会存在子回路，因此最后的约束是为了防止子回路出现的约束。

以总路线最短为原则，利用整数规划模型求得各城市的旅行优先顺序。

LINDO 软件求解结果如下：LAST INTEGER SOLUTION IS THE BEST FOUNDRE-INSTALLING BEST SOLUTION...OBJECTIVE FUNCTION V ALUE1) 2488.200V ARIABLE V ALUE REDUCED COSTX12 1.000000 517.799988X27 1.000000 400.100006X31 1.000000 520.599976X46 1.000000 276.500000X54 1.000000 165.399994X63 1.000000 272.700012X75 1.000000 335.100006U3 5.000000 0.000000U4 3.000000 0.000000U5 2.000000 0.000000U6 4.000000 0.000000U7 1.000000 0.000000运行结果只摘取1=ij x 的结果，求得目标函数的最优解为2488.200公里，最短路径为：沈阳→北京→呼和浩特→太原→石家庄→济南→天津→沈阳周先生的最短路的旅游路线如图所示，行程为2488.200公里。

显然这是一个循环圈，无论从哪个城市开始，顺序或逆序最总所走的路径总长度都是2488.200公里。

3.2模型二的建立由于要求最经济，所以可以从票价方面进行考虑，通过查阅资料可以得到各个城市之间航空、铁路（快车卧铺或动车）的不同票价，由于要求最经济，的旅行互联网上订票方案，所以选取三种类型票价中最低的票价，构建票价矩阵。

用票价矩阵代替第一问中的距离矩阵作为回路的边权值。

各城市之间票价数据如表（单位：元）沈阳 北京 天津 石家庄 太原 济南 呼和浩特 沈阳 0 121.86 119.43 170.91 210.95 181.31 241.12 北京 126.54 0 20.80 48.02 88.06 85.80 111.46 天津 119.43 20.80 0 67.08 112.67 61.88 135.21 石家庄 170.91 48.02 67.08 0 39.00 52.70 161.21 太原 210.95 88.06 112.67 39.00 0 91.70 110.94 济南 181.31 85.80 61.88 52.70 91.70 0 209.05 呼和浩特 241.12 111.46 135.21 161.21 110.94 209.05 0呼和浩特 太原 北京 天津 沈阳石家庄 济南知道两个城市之间的票价，周先生要自某一城市出发巡回旅游，使总费用最少，可以看出就是在一个赋权完全图中，找一个最小权的回路问题。