2016年军事交通学院交通运输工程(专业型)801运筹学考研冲刺密押卷及答案
● 摘要
一、计算题
1． 某工厂有两条生产线生产某一产品，第一生产线每小时生产2个单位产品，第二生产线每小时生产生单 1/2 位产品，正常开工每周40小时，每单位产品获利100元。 设:
（l ）第1目标是生产180个单位产品:
（2）第2目标是限制第一条生产线每周加班不得超过ro 小时: （3）第3目标避免开工不足;
（4）最后目标是加班时数达到最少。假定两条生产线的开工费用相同。 试建立上面问题的数学模型。
【答案】设第一条生产线每周开工x 1小时，第二条生产线每周开工x 2小时， 分别赋予四个目标P 1、P 2、P 3、P 4优先因子。
2． 求解六个城市旅行推销员问题，其距离矩阵如表所示，设推销员从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 城的最短距离为
所以，所以，
。
。
所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，
。
。
。
。
。
。
。
。
。
。
所以，所以，所以，
。
。
。
。
。
。
。
。