2017年江苏师范大学智慧教育学院(计算机学院)运筹学考研复试核心题库
● 摘要
一、简答题
1． 简述求解整数规划分枝定界法的基本思想。
【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界
; 。分支定界法就是将B 的可行域分成
子区域（称为分支）的方法，逐步减小和增大:， 最终求到z*。
2． 试写出求解最短径路的Dijkstra 算法的步骤。
【答案】Dijkstra 算法的步骤为:
（l ）给v s 以p 标号，P （v S ）二0，其余各点均给T 标号，T （v i ）=+∞。
（2）若v i 点为刚得到P 标号的点，考虑这样的点v i ，（v i ，vj ）属于E ，且v i 为T 标号。对v j 的T 标号进行如下修改:T （v j ）=min[T（v i ），p （v i ）+lij ]
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以
上最小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
二、计算题
3． 某厂需用配件数量r 是一个随机变量，其概率服从泊松分布，时间t
内的需求概率为
平均每日需求为1（
）备货时间为
平均拖后时间
天，方差
。在生产循环周期内存储费C 1=1.25元，缺货费C 2=10元，
天的的概率服从正态分布
装配费 C 3=3元。问两年内应分多少批订货? 每次批量及缓冲存储量各为何值才能使总费用最小?
【答案】
下面计算L 及B ，各步算出的数值列于表中。
表
（四）需求量r>L，的概率为
（五）相应拖后时间及需求概率的乘积
表
根据表算出的P L ，B 和费用的各种数值均列于表
所以，该厂订购批量为42，订购点为23，两年内应分17次订货，其缓冲存储量为9。
4． 某工程由六道工序构成，有关资料如表所示，其中时间单位为天，费用单位为元
（1）画出工程网络图
（2）求出工程完工期及关键工序
（3）现若要求工程在正常工期基础上再提前二天完成. 求使应急费用量少的应急压缩方案
表 某工程有关资料表
【答案】（1）
图
（2）各工序的时间参数:
表
工程兄工期为45，关键工序为A ，C ，E ，F （3）要使工期缩短，即缩短关键工序的工期 若缩短A 的工期，费用增加240; 若缩短E 的工期，费用减少860; 若缩短F 的工期，费用不变。
故要使费用最少，应选择缩短E 的工期。
5． 试求解下列线性规划问题: