2016年武汉轻工大学数学与计算机学院运筹学复试笔试仿真模拟题
● 摘要
一、计算题
1． 设有线性规划
在第一二约束电分别加入松弛变量x 3、x 4
，并用单纯形法求解，得到最优单纯形表如表所示。 表
（1）求出原规划LP 。
（2）写出LP 的对偶规划LD 。 （3）求LD 的最优解和最优目标值。 【答案】（l ）
（2）
（3）L p 的最优解为（3，l ），最优目标值为4x3+5xl=17 由强对偶性
T
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 城的最短距离为
所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
所以，。