运筹学课程设计

目录

一问题提出..........................................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模型，

zd

ij

x对模型进行求解。问题的目标函数为min

ij其中x

ij

0或1，ij



i1j

若x

ij

1表示周先生直接从i市到j市。建立整数目标规划，用Lindo软件求解，

找出所有x

ij

1，确定最短路的旅行方案。

第二问要求最经济，所以应从票价方面进行考虑，通过查阅资料可得各城市

之间航空、铁路（快车卧铺或动车）的不同票价，由于要求最经济的旅行互联网

上订票方案，所以选取三种类型票价中最低的票价，构建票价矩阵。用票价矩阵

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

第三问要求设定省时的方案就需要考虑时间因素，因为以上三种交通工具中

航空用时最短，选择飞机作为旅行交通工具。通过查阅资料得到各城市间航班的

时间矩阵，用时间矩阵代替第一问中的距离矩阵，求解一条最省时的路径。

nn

三模型建立

在具体的实现上，我们采用了整数规划法，并辅以LINGO软件编程实现

在下述意义下，引入一些0—1变量：



1

x

ij







0

巡回路线是从i到j,且ij

其他情况

1

其目标是使d

ij

x

ij

(ij)最小。（d

ij

表示i市到j市的距离）

i1j

nn

这里有两个明显的必须满足的条件：

访问城市i后必须要有一个即将访问的确切城市；访问城市j前必须要有一

个刚刚访问过的确切城市。用下面的两组约束分别实现上面的两个条件。

n

(ij,i1,2,,n)

x

ij

1

i1

n

x1(ij,j1,2,n)ij

j1

到此我们得到了一个模型，他是一个指派问题的整数规划模型。但以上两个

条件对于TSP来说并不充分，仅仅是必要条件。例如：

6

5

3

1

4

2

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

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

方法。把额外变量u

i

(i1,2,n)附加到问题中。可把这些变量看作是连续的。

现在附件下面形式的约束条件：

u

i

u

j

nx

ij

n1,2ijn.

为了证明该约束条件有预期的效果，必须证明：(1)任何含子巡回的路线都

不满足该约束条件；(2)全部巡回都满足该约束条件。

首先证明(1)，用反证法。假设还存在子巡回，也就是说至少有两个子巡回。

那么至少存在一个子巡回中不含城市1.把该子巡回记为i1,i2ik,i1，则必有：



u

i1

u

i2

nn1



uunn1

i2i3









u

ik

u

i1

nn1

把这k各式子相加，有nn1，矛盾。故假设不正确，结论1得证。

下面证明(2)，采用构造法。对于任意的总巡回1，i

1

…i

n1

，1，可取

u

i

为访问城市的顺序数，取值范围为{1,2,…,n-1}。

2

因此，u

i

u

j

n2,2ijn.下面来证明总巡回满足该约束条件。

(I)总巡回上的边



u

i1

u

i2

nn1n1



uunn1n1

i2i2









u

in

2u

in1

nn1n1

(II)非总巡回上的边

r1,2,n2,j{2,3,,n}{i

r

,i

r1

}



u

ir

u

j

n2n1,



uunn1n1,j{2,3,n}{i}

i2ri1

从而结论(2)得证。

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

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

minzd

ij

x

ijij



i1j

n

x

ij

1ij;j1,2,,n

i1

nij;i1,2,,n



x1

s.t.



ijij;i2,3,n;j2,3,,nj1



u

i

u

j

nx

ij

n1



x0或1,u0

iij

nn

3.1模型一的建立

虽然地球不是一个标准的球体，但南北与东西长度相差不大，可以假设地球

为一个球体，球体半径R6371229公里。

根据球面定理用两点之间的经度差计算出东西向的距离差为：

aaR180

ijij

根据球面定理用两点之间的纬度差计算出南北向的距离差为：

aa

ijbbRcos180

ijij2180

最后用勾股定理求出两点之间距离为：





22d

ij



ij



ij

3

沈阳1济南6呼和浩特7

沈阳10825.3897.1

北京2517.8364.8400.1

天津3520.6272.7494.2

石家庄4864.8276.5387.5

太原5992.5424.5335.1

济南6825.30662.5

呼和浩特7897.1662.50

知道两个城市之间的距离，周先生要自某一城市出发巡回旅游，使总行程

最短，可以看出就是在一个赋权完全图中，找一个最小权的

Humilton

回路问题。

以点0表示周先生的出发城市,称为源点,点

1

,表示

n

个周先生需访

,2,,N

问的城市。x

ij

1表示周先生需要从点

i

到点

j

，因外周先生一定离开某一个城市

去另一个城市所以ij

，

x

ij

0表示不需要从点

i

到点

j

；u

i

表示旅游城市的顺

序数；d

ij

表示对应城市

ij

的距离。建立目标函数以及约束条件为：

所有城市之间的距离矩阵

北京2天津3石家庄4太原5

517.8520.6864.8992.5

0113.8283.9408.9

113.80259.8428.9

283.9259.80165.4

408.9428.9165.40

364.8272.7276.5424.5

400.1494.2387.5335.1

minzd

ij

x

ijij



i1j

n

x

ij

1ij;j1,2,,n

i1

nij;i1,2,,n



x

ij

1

s.t.





ij;i2,3,n;j2,3,,nj1



u

i

u

j

nx

ij

n1



x0或1,u0

iij

i1,2,,n

其中辅助条件

u可以是连续变化的，虽然这些变量在最优解中

i

nn

是普通的整数值。

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

示旅行者必须离开每个城市。若模型只有这两个约束，则是一个标准的分配问题，

但其解会存在子回路，因此最后的约束是为了防止子回路出现的约束。

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

LINDO软件求解结果如下：

LASTINTEGERSOLUTIONISTHEBESTFOUND

RE-INSTALLINGBESTSOLUTION...

OBJECTIVEFUNCTIONVALUE

1)2488.200

VARIABLEVALUEREDUCEDCOST

X121.000000517.799988

X271.000000400.100006

X311.000000520.599976

X461.000000276.500000

4

X541.000000165.399994

X631.000000272.700012

X751.000000335.100006

U35.0000000.000000

U43.0000000.000000

U52.0000000.000000

U64.0000000.000000

U71.0000000.000000

运行结果只摘取x

ij

1的结果，求得目标函数的最优解为2488.200公里，最

短路径为：沈阳北京呼和浩特太原石家庄济南天津沈阳

沈阳

呼和浩特

北京

天津

石家庄

济南

太原

周先生的最短路的旅游路线如图所示，行程为2488.200公里。显然这是一

个循环圈，无论从哪个城市开始，顺序或逆序最总所走的路径总长度都是

2488.200公里。

3.2模型二的建立

由于要求最经济，所以可以从票价方面进行考虑，通过查阅资料可以得到各

个城市之间航空、铁路（快车卧铺或动车）的不同票价，由于要求最经济，的旅

行互联网上订票方案，所以选取三种类型票价中最低的票价，构建票价矩阵。用

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

各城市之间票价数据如表（单位：元）

沈阳北京天津石家庄太原济南呼和浩特

沈阳0121.86119.43170.91210.95181.31241.12

北京126.54020.8048.0288.0685.80111.46

天津119.4320.80067.08112.6761.88135.21

石家庄170.9148.0267.08039.0052.70161.21

太原210.9588.06112.6739.00091.70110.94

济南181.3185.8061.8852.7091.700209.05

呼和浩特241.12111.46135.21161.21110.94209.050

5

知道两个城市之间的票价，周先生要自某一城市出发巡回旅游，使总费用最

少，可以看出就是在一个赋权完全图中，找一个最小权的回路问题。

以点0表示周先生的出发城市,称为源点,c

ij

表示对应城市

ij

的票价。建

立目标函数以及约束条件为：

minzc

ijij

x

ij



i1j

n

x

ij

1ij;j1,2,,n

i1

nij;i1,2,,n



x1

s.t.



ijij;i2,3,n;j2,3,,nj1



u

i

u

j

nx

ij

n1



x0或1,u0

iij

nn

以总费用最少为原则建立整数规划模型，用Lindo求解结果如下：

LASTINTEGERSOLUTIONISTHEBESTFOUND

RE-INSTALLINGBESTSOLUTION...

OBJECTIVEFUNCTIONVALUE

1)617.2700

VARIABLEVALUEREDUCEDCOST

X121.000000121.860001

X271.000000111.459999

X311.000000119.430000

X461.00000052.700001

X541.00000039.000000

X631.00000061.880001

X751.000000110.940002

U20.0000000.000000

U35.0000000.000000

U43.0000000.000000

U52.0000000.000000

U64.0000000.000000

U71.0000000.000000

根据Lindo求得结果，设计周先生旅行的最经济的路径为：沈阳北京呼

和浩特太原石家庄济南天津沈阳。

3.3模型三的建立

现在再讨论最省时的订票方案。三种交通工具的速度分别为：民航飞机行驶

6

一般为800公里/小时，动车速度在150公里/小时—200公里/小时，快速列车

在120公里/小时以内，特快在160公里/小时以内，可见飞机最快，其次动车，

最慢是快车。假设三种交通方式的速度是不变的，则单位里程三种交通方式所花

费的时间分别为航空最短，其次是动车，最长的为快车。所以以时间最省为原则

时，我们采用全程均用飞机为交通工具的方案。

根据匀速运动物体速度与路程的关系（T=S/V）可以在已知两地直线距离的

基础上求得民航飞机在任意两城市之间的飞行时间。这样，我们就将最短路线的

模型在改变权数的基础上成功的转化到了求解时间最省的问题上来。

各城市之间航行时间数据表（单位：小时）

呼和浩

沈阳北京天津石家庄太原济南特

沈阳00.64720.65081.08101.24061.03161.1214

北京0.647200.14220.35490.51110.45600.5001

天津0.65080.142200.32480.53610.34090.6178

石家庄1.08100.35490.324800.20680.34560.4844

太原1.24060.51110.53610.206800.53060.4189

济南1.03160.45600.34090.34560.530600.8281

呼和浩1.12140.50010.61780.48440.41890.82810

特

以点0表示周先生的出发城市,称为源点,s

ij

表示对应城市

ij

的飞行时

间。建立目标函数以及约束条件为：

minzs

ij

x

ijij



i1j

n

x

ij

1ij;j1,2,,n

i1

nij;i1,2,,n



x1

s.t.



ijij;i2,3,n;j2,3,,nj1



u

i

u

j

nx

ij

n1



x0或1,u0

iij

nn

以用时最短为原则建立整数规划模型，用Lindo求解结果如下：

OBJECTIVEFUNCTIONVALUE

1)3.110300

VARIABLEVALUEREDUCEDCOST

X131.0000000.650800

X211.0000000.647200

X361.0000000.340900

X451.0000000.206800

X571.0000000.418900

X641.0000000.345600

7

X721.0000000.500100

U26.0000000.000000

U30.0000000.000000

U42.0000000.000000

U53.0000000.000000

U61.0000000.000000

U74.0000000.000000

根据Lindo求得结果为周先生设计最省时的旅行方式，周先生选择飞机为交

通工具，的旅行路线是：沈阳天津济南石家庄太原呼和浩特北

京沈阳。

四结果分析

本题为一个小规模的旅行商问题，可能存在的路径共有(n-1)!/2条。利用城

市的经纬度确定城市的直接距离，写出城市间的距离矩阵，查询资料得到最低票

价矩阵和时间矩阵，构建整数规划模型并引入0—1变量，并引进变量u

i

表示城

市的旅游顺序，约束条件u

i

u

j

nx

ij

n1避免产生子回路。采用分枝定界法

并使用Lindo软件求的最优解。可以从时间，路程，经济的某一个方面考虑，为

旅行者设计符合自己要求的旅行方案。

五模型评价

5.1模型优点：

(1)建立的旅行商模型实用性强，对问题求解有很好的针对性。

(2)利用lindo软件可以求解小规模的旅行商问题，可以有效避免陷入局优，克

服初值依赖性，描述简单，使用灵活，运用广泛，运行效率高。

5.2模型缺点：

(1)利用lindo软件求解具有一定的局限性，无法求得大规模的问题；

(2)问题三中最省时方案所得的结果与最优解有一定相差，原因在于模型片面过

于依赖城市间空间直线距离。

8

六参考文献

[1]胡运权，《运筹学基础及应用（第四版）》：高等教育出版社，2003年11

月。

[2]王树禾《图论》，科学教育出版社，2004年1月第一版

[3]姜启源，谢金星，叶俊，《数学模型》（第三版），北京：高等教育出版社，

2003.8

[4]谢金星、薛毅《优化模型与LINDO/LINGO软件》，清华大学出版社2005年

7月第一版

9