大学数学
大學數學
대학수학
COLLEGE MATHEMATICS
2012年
6期
78-82
,共5页
赋权完全图%最佳游览路线%最优配置
賦權完全圖%最佳遊覽路線%最優配置
부권완전도%최가유람로선%최우배치
completed graph with weight%the shortest tourist path%the best configuration
将某高校的校园示意图转化为赋权连通图，求得该连通图的邻接矩阵，利用Floyd算法及图论软件包构造一个最短路径矩阵，得到一个赋权完全图，将求校园最佳游览路线问题归结为图论中的最佳推销员回路问题，建立混合整数线性规划模型，并利用优化软件求得最优解．从而解决了校园开放日游览计划中提出的关于校园最佳游览路线和校园游览车最优配置问题．
將某高校的校園示意圖轉化為賦權連通圖，求得該連通圖的鄰接矩陣，利用Floyd算法及圖論軟件包構造一箇最短路徑矩陣，得到一箇賦權完全圖，將求校園最佳遊覽路線問題歸結為圖論中的最佳推銷員迴路問題，建立混閤整數線性規劃模型，併利用優化軟件求得最優解．從而解決瞭校園開放日遊覽計劃中提齣的關于校園最佳遊覽路線和校園遊覽車最優配置問題．
장모고교적교완시의도전화위부권련통도，구득해련통도적린접구진，이용Floyd산법급도론연건포구조일개최단로경구진，득도일개부권완전도，장구교완최가유람로선문제귀결위도론중적최가추소원회로문제，건립혼합정수선성규화모형，병이용우화연건구득최우해．종이해결료교완개방일유람계화중제출적관우교완최가유람로선화교완유람차최우배치문제．
A campuses sketch map is transfered into connected graph with weight and its adjacency matrix is gotten. The shortest path matrix is constructed and a completed graph with weight is gotten by Floyed arithmetic and the software package of graph. The best tourist route of campus problem is regarded as TSP problem, i. e. , find the best similar Hamilton circle in the completed graph with weight. It is solved three problems in the opening day of campus: 1. For visitors to choose the main buildings, spots or sites. 2. According to the sketch map, design the shortest four tourist paths. 3. Get the minimal number of sightseeing bus in the opening day of campus.
