2016年军事交通学院军事后勤学801运筹学考研必备复习题库及答案
● 摘要
一、简答题
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 ，p （v i ）+lij ] 标号进行如下修改:T （v j ）=min[T（v i ）
（3）比较所有具有T 标号的点，把最小者改为P 标号，即:
当存在两个以上最
小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
2． 在解决实际问题时应如何运用启发式策略? 除本书上列出的几个启发式策略之外，你认为还有什么样的策略可以使用?
【答案】在解决实际问题时，可根据实际问题的性质和要求来选用某一启发式策略; 为得到理想效果，也可将几个策略联合起来使用。除本书上列出的几个启发式策略之外，还有计算机仿真、模拟策略、类比策略、近似策略等可以使用。
3． 用表上作业法解运输问题时，在什么情况下会出现退化解? 当出现退化解时如何处理? 【答案】当运输问题某部分产地的产量和，与某一部分销地的销量和相等时，在迭代过程中间有可能在某个格填入一个运量时需同时划去运输表的一行和一列，这时就出现了退化。
当出现退化时，为了使表上作业法的迭代工作能顺利进行下去，退化时应在同时划去的一行或一列中的某个 格中填入数字0，表示这个格中的变量是取值为0的基变量，使迭代过程中基变量个数恰好为（m+n-l）个。
4． 简述目标规划单纯形法求解的基本思想。
【答案】第一步，建立初始单纯形表，在表中将检验数行按优先因子个数分别列成K 行，置k=l; 第二步，检查该行中是否存在负数，且对应的前k 一1行的系数是零。若有负数取其中最小者对应的变量为换入变量，转第三步。若无负数。则转第五步;
第三步，按最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别 的变量为换出变量;
第四步，按单纯形法进行基变换运算，建立新的计算表，返回第二步;
第五步，当k=K时，计算结束。表中的解即为满意解。否则置k=k+l，返回到第二步。
二、计算题
5． 某公司现拥有资金3万元。现做今后3年的投资计划每年允许投资额不能超过5万元. 若某年投资x 元， 当年有l/3可能性损失x 元，而有2/3可能性增收x 元。现要确定能使3年后将拥有资金超过5万元的可能性 最大的投资力案
试结合题中说明，当用动态规划方法求解时的下列基本概念（不必计算）: （l ）阶段变量:
（2）状态变量、状态集台: （3）决策变量、允许决策范围 （4）状态转移关系: （5）递推方程。
【答案】（l ）阶段变量k :按三年的投资计划，分为3个阶段; （2）状态变量s k :表示第k 年初投资时剩余的全部资金金额 状态集合为:s 1=3
（3）决策变量x k :表示第k 年初用于投资的金额（4）状态转移关系为:
（5）递推方程:
6． 有一线性方程组如下
现欲用无约束极小化方法求解，试建立数学模型并说明计算原理。 【答案】（1）建立数学模型
（2） ①令②
若
以梯度法为例解无约束极值问题，计算原理如下：
为初始近似点，取精度=0.02 ，则极小点
为
。一般，
若
，则要找下一点
③设迭代至
，若
，需要求步长
。
，
若
，则要找下一
点
，则极小点
为
。
若
或者对止。
求导，并令等于0，则可求得最佳步长
。以②为判断准则，重复迭代，直至满足精度为
7． 在图中，分别求v l 至v 6，v l 至V 4，v6至vZ 和vZ 至vs 的最短路和最短距离。
图
【答案】用Floyd 方法求解 令网络的权矩阵为
其中，
为
到
的距离
由表示从v i 到v j 点的或直接
有边或借v 1点为中间点是的最短路长，括弧中元素为更新元素，得
相关内容
相关标签