2016年北京化工大学经济管理学院运筹学复试笔试最后押题五套卷
● 摘要
一、计算题
1． 6有九个城市v l ，v 2，…，v 8，v 9，其公路网如下图所示，弧旁数字是该公路的长度。有一批货物从v l 运 到v 9，问走哪条路最短?
图
【答案】用Dijkstra 算法进行求解。
（l ）对起点v l 进行P 标号，即P （v l ）=0; 对其余点进行T 标号，即
，T （v 4）}=T（v 2）=3，将v 2进行P 标号，且P （v 2）=3。 依据而min{T（v 2）
，，（2）v 2己进行了P 标号，（v 2，v 3）（v 2，v 5）（v 2，v 6
）行改写:
，T （v 4），T （v 5），T （v 6）}=T（v 4）=4，故将v 4进行P 标号.P （v 4）=4. 因为min{T（v 3）
（3）v 4已进行了P 标号，而
，修改v7的T 标号为
，T （v 5），T （v 6），T （v 7）}=5=T（v 5），故对v 5进行P 标号P （v 5）=5. 因为min{T（v 3）
（4）已对v 5进行了P 标号，而（v 5，v 6
）
A ，修改v 6的T 标号为
，T （v 6），T （v 7）}=6=T（v 3），故对v 3进行P 标号P （v 3）=6. 因为min{T（v 3）
（5））已对v 3进行了P 标号，而（v 3，v 9
）
A ，修改v 9的T 标号为
，T （v 7），T （v 9）}=6=T（v 6），故对v 6进行P 标号P （v 6）=6. 因为min{T（v 6）
，（6）已对v 6进行了P 标号，而（v 6，v 7）（v 6，v 9
）
A ，修改v 7，v 9的T 标号为
A ，所以应对v 3，v 5，v 6的T 标号进
。因为
，T （v 9）}=7=T（v 7），故对v 7进行P 标号P （v 7）=7. 因为min{T（v 7）
，（7）已对v 7进行了P 标号，而（v 7，v 8）（v 7，v 9
）
A ，修改v 8，v 9的T 标号为
，T （v 9）}=8.5=T（v 9），故对v 9进行P 标号P （v 9）=8.5。于是得到从v l 到v 9因为min{T（v 8）
的最短路程为8.5。 应用反向跟踪的方法可以得到，从v l 到v 9的最短路线为v 1→v 2→v 6→v 9。
2． 用动态规划方法求解非线性规划问题:
【答案】考虑到该题为整数动态规划，适合列表计算 （1）K=3时，
表
（2）k=2时，
表
（3）K=1时
表
所以，得到最大目标函数值16。
3． 求解六个城市旅行推销员问题，其距离矩阵如表所示，设推销员从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 城前面的那个城市。
相关内容
相关标签