2017年北京化工大学运筹学考研复试核心题库
● 摘要
一、简答题
1． 试写出标准指派问题的线性规划问题。
【答案】
A ij 表示工作人员i 做工作j 时的工作效益 则得线性规划模型为:
2． 试将Norback 和love 提出的几何法与C 一W 节约算法进行比较。
【答案】（1）几何法:首先找出凸包，然后考查以不在旅行线路上的点为角顶，以线路上的点的连线为对边的角的大小，选出最大者所对应的角顶，插入到旅行线路中，反复进行直至形成哈密尔顿回路。
（2）C 一W 节约算法:首先以某一点为基点，确定初始解，然后考查基点之外的其它点的连线所构成的弧的 节约值的大小，选出节约值最大者所对应的弧，插入到旅行线路中，直至旅行线路中包含所有的点。
二、计算题
3． 某航空公司售票处开展电话订票业务。据统计分析，电话到达过程服从泊松分布，平均到达率为每小时 20个，平均每个业务员每小时可以处理10个电话订票业务。请问该公司应该安装多少台电话，才能使因电话占 线而损失的概率小于10%。
【答案】
假设公司应该安装c 台电话，故
所有电话都占线的概率为:
解得c=5
4． 求解六个城市旅行推销员问题，其距离矩阵如表所示，设推销员从1城出发，经过每个城市一次且仅一次，最后回到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 城的最短距离为
所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，所以，
。
。
。
。
。
。
。
。
。
。
。
。
。
。
。
相关内容
相关标签