主题:求助MATLAB解数学最优化问题
问题五 空运路线规划
在东南亚有一个国家正在遭受广泛的洪灾。在国际援助下,该国政府决定建立一个空运补给系统。不幸的是,在这个国家只有七条还可以使用的跑道,其中一条在首都。
该国政府决定让飞机从首都起飞,然后访问所有其他六个机场,最后回到首都。下表列出了机场之间的距离。机场A1位于首都。应采取什么顺序一次到达各个机场才能使总行程最短?
表5.1 机场之间的距离(千米)
A2 A3 A4 A5 A6 A7
A1 786 549 657 331 559 250
A2 668 979 593 224 905
A3 346 607 472 467
A4 890 769 499
A5 386 559
A6 681
对问题分析的提示:我们知道这类问题被称之为“旅行商问题”。也就是在几个城市中,找到最优的方案是旅行者能获得最大的效率。
要注意的是,对于大规模的TSP,其求解属于NP问题,有一定的困难性。但是该国只有七个能用的机场。于是可知这是一个规模较小的TSP问题,因而可以考虑用优化方法来求解。
在东南亚有一个国家正在遭受广泛的洪灾。在国际援助下,该国政府决定建立一个空运补给系统。不幸的是,在这个国家只有七条还可以使用的跑道,其中一条在首都。
该国政府决定让飞机从首都起飞,然后访问所有其他六个机场,最后回到首都。下表列出了机场之间的距离。机场A1位于首都。应采取什么顺序一次到达各个机场才能使总行程最短?
表5.1 机场之间的距离(千米)
A2 A3 A4 A5 A6 A7
A1 786 549 657 331 559 250
A2 668 979 593 224 905
A3 346 607 472 467
A4 890 769 499
A5 386 559
A6 681
对问题分析的提示:我们知道这类问题被称之为“旅行商问题”。也就是在几个城市中,找到最优的方案是旅行者能获得最大的效率。
要注意的是,对于大规模的TSP,其求解属于NP问题,有一定的困难性。但是该国只有七个能用的机场。于是可知这是一个规模较小的TSP问题,因而可以考虑用优化方法来求解。