关于云南旅游路线的数学模型1

楚雄师范学院

2010数学建模培训第二次培训论文

题目：云南省旅游交通路线的最优规划模型

姓名：

系（院）：

专业：

2010年6月7日

【摘要】本文建立了适当的数学模型，利用计算机模拟求解后为在云南自驾

旅游者找到一条最佳的旅游路线——走尽量短的路程而所到达的景区尽量多。采用了图论的思想方法建立模型之后，利用MATLAB 和C 语言程序实现了floyd 算法，然后对执行的结果进行综合分析得到最佳路线与最短行程。

对模型的解进行灵敏度分析可以把此模型推广到在两个（不）相连景区之间寻找最短路径。

还可以把模型推广到具有相同需要的其他领域。

【关键词】最短路径、最佳路线、自驾旅游、景区、

Floyd 算法。

一、问题重述

云南地处我国的西南部，拥有丰富的旅游资源，吸引了大批的省外游客，随着越来越多的游客到云南来旅游，旅游线路成了一个焦点问题，请帮一个第一次来云南旅游的人制定一条合适的自驾旅游路线。

二、问题分析

本文旨在建立一个适当的数学模型，通过计算机模拟和求解，来确定从昆明出发，去往省内各景区旅游并最终回到昆明的最佳自驾旅游路线。

在建模时，采用的是图论的思想方法，并假设各景区为顶点，各景区间的距离为顶点之间的关联——即各景区之间的距离就是各点之间连线的权。在模型建立和模型求解的过程中，考虑到模型的可操作性与实用性，酌情的排出了某些不适合自驾旅游的景区。

三、模型假设与符号说明

（一）模型假设：某旅游者采用自驾游的旅游方式从昆明出发，前往省内各景区旅游，试图经过的路程尽量短而到达的景区尽量多。

假设：1、汽车的时速均为60km /h ；

2、到达景区后前往各个景点的距离不计在内；

3、在到达的每个景区停留2天(48h ) ；

4、用各州、市来把省内旅游景点化属16个景区，并分别用各州、市名来记；

5、各景区之间的道路都是双向通行的。

（二）、符号说明:

的权为估计值）。

四、模型建立

以各景区为顶点，各景区之间的距离为顶点之间权重得到下图：

找到适当的路线：使得从A 点出发并最终回到A 点且经过尽量多的点而权重尽量小。

模型分析：

设旅游者要游玩所有景点，即16个景区。用1，2, ……,16表示A,B, ……,P.

一个旅游者从昆明出发，要走完所有的景区，如果必要可以重复走相应道路，最后返回昆明。所有道路都是双向通行的，且每条道路都有一个长度值（∞表示两景区间没有直接道路连接的值）。

图G 中无边关系的用∞表示，简化旅游图得矩阵如下：

⎡087187∞[1**********]7∞∞∞∞∞∞∞⎢⎢870200∞∞∞∞389206345∞∞∞∞∞⎢⎢1872000157∞∞∞∞∞∞∞∞387∞∞⎢∞∞1570215∞∞∞∞∞∞364166∞175⎢⎢408∞∞2150∞∞∞∞∞∞∞∞∞∞⎢413∞∞∞∞0197∞∞∞∞∞∞∞∞⎢⎢130∞∞∞∞1970∞319∞∞∞∞∞∞⎢G =⎢

347389∞∞∞∞∞0105619∞∞∞∞∞⎢∞206∞∞∞∞3191050∞∞∞∞∞∞⎢⎢∞345∞∞∞∞∞619∞0259195∞∞∞⎢∞∞∞∞∞∞∞∞∞2590∞∞∞∞⎢⎢∞∞∞364∞∞∞∞∞195∞0∞∞∞⎢⎢∞∞387166∞∞∞∞∞∞∞∞0175∞⎢∞∞∞∞∞∞∞∞∞∞∞∞1750∞⎢⎢∞∞∞175∞∞∞∞∞∞∞∞∞∞0⎢⎣∞

∞

323

198

∞

356

五、模型求解

1、 Floyd 算法之MATLAB 实现：

求解思想 (1) D(i,j)：i 到j 的距离．

r(i,j)：i 到j 之间的插入点．输入: 带权邻接矩阵G =(G (i , j )) v ⨯v .

赋初值：对所有i,j, d(i,j)←G(i,j), r(i,j)←j, k←1 (2) 更新d(i,j), r(i,j): 对所有i,j ，若d(i,k)+d(k,j)

由公式d (k )

=min{d (k -1)

(k -1)

ij , d ik +d kj

},在由MA TLAB 中的Floyd 算法依次调用

实现得最短路径G 16(见附录G (13) =G (14) =G 15=G 16) 算法如下首先输入m-文件如下：

function [d,r]=floyd(a)

%floyd.m

%采用floyd 算法计算图a 中每对顶点最短路

%d是矩离矩阵 %r是路由矩阵 n=size(a,1);

∞⎤

∞⎥⎥∞⎥323⎥⎥198⎥

⎥∞⎥∞⎥⎥∞⎥∞⎥⎥∞⎥⎥∞⎥∞⎥⎥∞⎥∞⎥⎥356⎥

⎥0⎥⎦

d=a; for i=1:n

for j=1:n

r(i,j)=j;

end end r for k=1:n for i=1:n for j=1:n

if d(i,k)+d(k,j)

end end end k d r end

并以“floyd ”为文件名保存；

在命令窗口中输入

a=[0 87 187 inf 408 413 130 347 inf inf inf inf inf inf inf inf; 87 0 200 inf inf inf inf 389 206 345 inf inf inf inf inf inf; inf inf 157 0 215 inf inf inf inf inf inf 364 166 inf 175 323; 408 inf inf 215 0 inf inf inf inf inf inf inf inf inf inf 198; 413 inf inf inf inf 0 197 inf inf inf inf inf inf inf inf inf; 130 inf inf inf inf 197 0 inf 319 inf inf inf inf inf inf inf; 347 389 inf inf inf inf inf 0 105 619 inf inf inf inf inf inf; inf 206 inf inf inf inf 319 105 0 inf inf inf inf inf inf inf; inf 345 inf inf inf inf inf 619 inf 0 259 195 inf inf inf inf; inf inf inf inf inf inf inf inf inf 259 0 inf inf inf inf inf; inf inf inf 364 inf inf inf inf inf 195 inf 0 inf inf inf inf; inf inf 387 166 inf inf inf inf inf inf inf inf 0 175 inf inf; inf inf inf inf inf inf inf inf inf inf inf inf 175 0 inf inf; inf inf inf 175 inf inf inf inf inf inf inf inf inf inf 0 356; inf inf inf 323 198 inf inf inf inf inf inf inf inf inf 356 0] floyd(a) 得到D

(12)

(1)

(16)

与R

(1)

(16)

（详见附录1），因为

(14)

≠G

(13)

, G (13) =G (14) =G 15=G 16，R

(12)

≠R

(13)

，R

(13)

=R ，所以可以通

过对G (12) ，G (13) 与R

，R

(13)

的追溯分析可得到任意两点之间的最短距离，所

以可以参考此解来获得任意两个景区之间的最佳路线和最短行程。

2、 C 语言程序实现：

Floyd 算法还可以通过C 语言程序来实现，如下：

因为C 语言程序不识别∞，故取∞为10000输入上述矩阵（因为10000已足够大，对模型求解不产生实质影响）。输入以下数据：

⎡[***********][***********][***********]0000⎢⎢[***********][***********][***********]010000⎢⎢[***********][***********][***********]000010000⎢[***********][***********][***********]0000175⎢⎢[***********][***********][***********][1**********]00⎢[***********][***********][***********][1**********]000⎢⎢[***********][***********][***********][1**********]0⎢⎢[***********][***********][***********]0000010000⎢[***********][***********][***********][1**********]⎢⎢[***********][***********][***********]000010000⎢[***********][***********][***********][**************]0⎢⎢[***********][***********][***********][1**********]00⎢⎢[***********][***********][***********][1**********]⎢[***********][***********][***********][**************]⎢⎢[***********][***********][***********][**************]⎢⎣10000

10000

323

198

10000

356

利用C 语言程序（见附录2）

由于调用程序过程所占空间太大，所以就直接得到执行结果：

最小路径权值和：5064 路径为：1→5 →16 →15→ 4→ 13 →14→ 13 →4 →12→ 10 →11→

10 →2→ 3 →2 → 8→ 9→ 7 →6→ 1

A →E →P →O →D →M →N →M →D →L →J →K →J →B →C →B →H →I →G →

F →A

3、综合分析求解

鉴于floyd 算法的局限性，我们综合分析得到要经过全部景区后回到出发点——昆明的最佳路线为：A →E →P →O →D →M →N →M →D →L →J →K →J →B →C →B →H →I →G →F →A 。相加此路线各相连两景区之间的距离可以得到最

⎤

⎥⎥⎥

323⎥⎥198⎥

⎥⎥

⎥⎥⎥

⎥⎥

⎥⎥⎥

⎥⎥356⎥

⎥0⎦

[***********][***********][***********]010000

小路程为：5064

六、灵敏度分析

对模型进行灵敏度分析，即为了旅游的效率更高，可以采取放弃旅游其中的某个或某几个景区：在省去一些相对孤立且知名度一般的景区之后，再用模型求解中的算法进行计算，得到如果不去某个或某几个景区的话，旅游中行程将大大减小。例如，选择不去F 、H 、L 、N 、J 、K 景区，则最短行成由原来的5064km 缩短为2545km ，最佳路线为A →E →P →O →D →M →C →B →I →G →A 。

七、模型的评价与推广

模型的建立是根据实际情况抽象得到的（为方便模型求解此模型是在假设各景区之间道路情况一致以及不考虑各景区所有景点之间路程的条件下建立的）。

模型求解中的floyd 算法给出了任意两景区之间的最佳路线及相应的路程，故此模型可以推广到寻找任意两景区之间的最佳路线及最短路程。

另外，本模型的方法可以推广到旅游费用最小、只要把每条边的权改为旅游消费金额即可。

本模型还可推广到其他领域一些寻求最短行程和最佳路线的问题。

参考文献

[1] 姜启源·《数学模型（第三版）》·高等教育出版社·2008年8月 [2] 中国地图出版社·《云南省交通图册》·中国地图出版社·2008年1月 [3] 【丹】 J. 邦詹森、【英】 G . 古廷著，姚兵张忠辅·《有向图的理论、算

法、及其应用》·科学出版社·2009年1月 [4] 严蔚敏吴伟民·《数据结构（C 语言版）》·清华大学出版社·2009年2月

附录

1、floyd 算法的MATLAB 运行的部分结果（只给出需要通过对其进行追溯分析

来的到模型解的部分）为： k =12

d =Columns 1 through 8

0 87 187 344 408

87 187 344 408 327 130 347 293 432 691 627 510 Inf 519 606 Columns 9 through 16 293 327 130 347

0 200 357 414 217 311

200 0 157 514 317 511

357 157 0 671 474 668

495 372 215 735 538 755

414 514 671 0 197 621

217 317 474 197 0 424

311 511 668 621 424 0

206 406 563 516 319 105

345 545 559 759 562 619

604 804 818 1018 821 878

540 521 364 954 757 814

523 323 166 837 640 834

Inf Inf Inf Inf Inf

532 332 175 846 649 843

680 480 323 933 736 953

432 691 627 Inf 519 606

495

372

215

735 538

755

701

774

1033

579

381

Inf Inf 390

198

510

206 345 604 540 523

Inf 532 680

406 545 804 521 323

Inf 332 480

563 559 818 364 166

Inf 175 323

701 774 1033 579 381

Inf 390 198

516 759 1018 954 837

r =

1 1 1 3 1 7 319 105 0 551 810 746 729 Inf 738 886 2 3 2 3 2 3 3 3 1 4 7 7 Inf 562 Inf 619 Inf 551 Inf 0 Inf 259 Inf 195 Inf 725 Inf 0 734 Inf 882 Inf 3 5 2 3 3 1 10 3 4 4 4 4 4 5 12 13 4 5 4 4 7 7 7 7 846 821 649 878 843 810 738 259 734 0 993 454 539 984 341 Inf Inf 993 0 1141 356

7 7 14 3 1 1 14 3 1 1 14 4 3 3 14 15 1 1 14 4 6 7 14 7 933

757 736

814 953

746 886

195 882

454 0 687

530 489

Inf Inf

539 356

687 0 8 5

9 3

2 4

3 16

1 16

7 7

640

834

729

725

984

530

175

341

489

2 2 2

9 10 10

2 2 2

3 12 12

1 4 4

7 7 7

1141

175

1 1 1 1 1 6 7 9 9 1 1

1 1 14 1 1

1 9 9 9 1 9 9 8 9 10 10

10 9 14 9 1

2 2 2 2 2 7 7 8 9 2 2

2 2 14 2 2

2 2 2 12 12 2 2 8 2 10 11

12 12 14 12 12

10 10 10 10 10 10 10 10 10 10 11

10 10 4 4 4 4 1 2 3 4 4 4 5 4 4 d =Columns 1 through 8

0 87 187 344 408 327 130 347 293 432 691 10 10 14 10 4 4 10 10 12 4 14 4 4 4 4 4 4 13 14 4 4 5 6 7 12 13 14 15 4 4 4 4 4 4 14 15 4 5 5 5 4 4 14 15 k =13

87 187 327 130 0 200 414 217 200 0 514 317 357 157 671 474 495 372 735 538 414 514 0 197 217 317 197 0 311 511 621 424 206 406 516 319 345 545 759 562 604 804 10

10 10 4

4 4 4

8 9 16

4 4 16

5 4 16

344 347

357 311

157 511

0 668

215 755

671 621

474 424

668 0

563 105

559 619

818 10

4 4

408 495 372 215 0 735 538 755 701 774 1033

10 10

1018 821 878

627 540 521 364 579

954 757 814

510 523 323 166 381

837 640 834

685 698 498 341 556

1012 815 1009

519 532 332 175 390

846 649 843

606 Columns 9 through 16

293 206 406 563 701 516 319 105 0 551 810 746 729 904 738 680 933 432 685 345 698 545 498 559 341 774 556 759 1012 562 815 619 1009 551 904 0 900 259 1159 195 705 725 175 900 0 734 516 480 736

691 519 604 532 804 332 818 175 1033 390 1018 846 821 649 878 843 810 738 259 734 0 993 454 539 984 341 1159 516 993 0 323 953

627 606

540 680

521 480

364 323

579 198

954 933

757 736

814 953

746 886

195 882

454 1141

0 687

530 489

705 664

539 356

198

510

523

323

166

381

837

640

834

729

725

984

530

175 341

886 882 1141 687 489

664 356 0 r =

1 2 3 3 5 7 7 8 2 2 2

2 3 3 3 5

1 2 3 3 1 1 1 9 9 10 10

10 3 3 3 3

1 2 3 4 4 1 1 2 2 2 2

4 4 4 4 4

3 3 3 4 12 1 1 4 4 4 7 7 7 7 7 1 1 1 1 1 1 9 9 9 10 2 2 2 2 2 2 2 2 12 12 10 10 10 10 10 10 10 4 4 12 4 4 4 4 4 13 13 13 13 13 4 4 4 4 4 5 4 4 4 4 2、Floyd 算法的C 语言程序：

#include #define N 16 struct line {

int value; int vertex; }

main(void)

5 3 13 13 5 1 4 4 7 6 7 7 1 6 1 1 1 9 9 9 2 7 2 2 12 2 12 12 10 10 10 10 4 10 4 4 4 4 14 13 13 13 14 4 4 4 4 5 5 4 4 3 3 15 16

1 1 4 16

7 7 7 7

7 9 1 1

9 8 9 1

7 8 2 2

2 8 12 12

10 10 10 10

10 10 4 4

4 4 4 4

13 13 13 13

4 4 16

5 5 16

3 12 1 4 7 7 9 1 9 10 9 2 2 10 10 10 10 10 4 4 13 13 4 4 4 4 12

13 15 15

{

line a[N][N-1]; //输入

for(int i=0;i

for(int j=0;jj)

{

a[i][j].vertex=j;

cout

{

a[i][j].vertex=j+1;

cout

cin>>a[i][j].value; }

//对矩阵插入排序 for(i=0;i

for(int j=0;j

for(int k=j+1;k

line temp;temp.value=0;temp.vertex=0; if(a[i][j].value>a[i][k].value) {

temp.value=a[i][j].value; a[i][j].value=a[i][k].value; a[i][k].value=temp.value; temp.vertex=a[i][j].vertex; a[i][j].vertex=a[i][k].vertex; a[i][k].vertex=temp.vertex; } }

//DFS核心算法 //初始化 bool visit[N];

for(i=0;i

visit[i]=false;//标记是否访问过 int path[N+1]={0};//存储搜索路径 int M=0;//标记路径值

int Min=65563;//标记最短路径值 int top=0;//控制访问过的顶点数 int Path[N+1]={0};//存储最短路径

//从u 点出发搜索

int u=0;int v=0;visit[u]=true; while(u>=0&&u=0) {

while(v=0&&visit[a[u][v].vertex]) v++;//向后搜索

if(v==N-1&&u>0)//若v 点全部搜索完毕，回朔到前一顶点u {

visit[u]=false; int temp=u; if(top>0) top--; else

break;

u=path[top];

for(int i=0;i

v=i+1; break; }

M-=a[u][v-1].value; continue; }

if(v==N-1&&u==0) break;//出口

if(!visit[a[u][v].vertex]&&a[u][v].value+M>=Min) {

visit[u]=false; int temp=u; if(top>0) top--; else

break;

u=path[top];

for(int i=0;i

v=i+1; break; }

M-=a[u][v-1].value; continue; }

if(!visit[a[u][v].vertex]&&a[u][v].value+M

M+=a[u][v].value;top++; path[top]=a[u][v].vertex; visit[a[u][v].vertex]=true; if(top==N-1)

{

//考察v 点是否可以回到原点且较小 for(int i=0;i

if(a[a[u][v].vertex][i].vertex==0&&M+a[a[u][v].vertex][i].value

{

Min=M+a[a[u][v].vertex][i].value; for(int i=0;i

M-=a[u][v].value;

visit[a[u][v].vertex]=false;top--; // path[top]=a[u][v].vertex; visit[u]=false; int temp=u; top--;

u=path[top];

for(i=0;i

if(a[u][i].vertex==temp) {

v=i+1; break; }

M-=a[u][v-1].value; continue; } else {

u=a[u][v].vertex; v=0; } }

//输出结果

cout

cout"; cout

关于云南旅游路线的数学模型1

相关内容

热门内容