2017年华北理工大学035运筹学考研复试核心题库
● 摘要
一、简答题
1． 试写出求解最短径路的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）。
2． 在线性规划的灵敏度分析中，当基变量的价值系数变化后，最优表中哪些数据会发生变化，怎样变化。
【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因
，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:
可见，当Cr 变化成△Cr 后，最终表中的检验数是:
二、计算题
3． 对含参数线性规划问题（参数t ≥0）:
（1）令t=0用单纯形法求解。
（2）讨论t 对最优解、最优值的影响（即给出t 在不同取值范围内的最优解、最优值）。 【答案】（l ）令t=0，标准化为:
采用单纯形法求解，如表所示。
表
（2）
代入（l ）中最优单纯形表，继续求解，如表所示。
表
当2-t ≥0时，即0≤t ≤2时，最优基不变，则:
当t 增大时，2-t<0，采用对偶单纯形法，继续求解。 当
, 即2＜t ≤6时, 有:
当t 再增大时，即t>6时，无可行解。
4． 某厂对原料需求的概率如表所示。
表
每次订购费C 3=500元，原料每吨价格为K=4田元，每吨原料存储费用为C 1=50元，缺货费每吨为 C 2=600元，该厂希望制订（s ，S ）型存储策略，试求s 及S 的值。
【答案】（l ）计算临界值:
（2）求s :
所以S=40 （3）求s :
因为S=40，所以不等式右端为
当s=20时，不等式左端为’
所以s=20，不符合条件，舍去。 当s=30时，不等式左端为
=400*30+50*（30-20）*0.1+600*[（40-30）*0.3+（50-30）*0.3+（60-30）*0.1] =8000+600*21=20 600>19 700 所以s=30。
因此，该厂的存储策略为:当存储量I ≤30时，补充存储量，使存储量达到40吨，而每当存储量I>30时， 则不需要补充。