2016年郑州大学管理工程学院运筹学(同等学力加试)考研复试题库
● 摘要
一、计算题
1． 求解六个城市旅行推销员问题，其距离矩阵如表所示，设推销员从l 城出发，经过每个城市一次 且仅一次，最后回到1城，问按怎样的路线走，使总的行程最短。
表
【答案】从1城出发最后回到l 城中间要经过五个城市，因此将该问题划分5个阶段，阶段变量k=l，2，3，4，5; 记从
达i 城之前中途所经过的城市的 集合，则有
表示由1城到i 城的中间城市集合; S 表示到。
因此，可选取（i ，S ）作为描述过程的状态变量，决策为由一个城市走到另一个城市，并定义最优值函数 人（i ，S ）为从1城开始经由k 个中间城市的S 集到i 城的最短路线的距离，则可写出动态规划的递推关系为
边界条件为由边界条件可知
（l ）当k=l时，从1城开始，中间经过一个城市到达i 城的最短距离为
。
为最优决策函数，它表示从1城开始经k 个中间城市的s 集到
i 城的最 短路线上紧挨着i 城前面的那个城市。
（2）
当k=2时，从1城开始，其间经过两个城市（此两城市的顺序任意）到达i 城的最短距离为
所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
所以，。
所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，
。
。
。
。
。
。
。
。
。
。
所以，所以，
。
。
所以，。
（3）当k=3时，从1城开始，其间经过三个城市（顺序任意）到达i 城的最短距离为
所以，。
相关内容
相关标签