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 标号，即:2． 试写出M/M/1排队系统的Little 公式。 【答案】M/M/1排队系统的Little 公式为
3． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
4． 在线性规划的灵敏度分析中，当基变量的价值系数变化后，最优表中哪些数据会发生变化，怎样变化。
【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因
，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:
可见，当Cr 变化成△Cr 后，最终表中的检验数是:
当存在两个以上最
小者时，可同时改为P 标号。若全部点均为P 标号时停止，否则用代V i 转回（2）。
二、计算题
5． 下述论断正确与否:可行流f 的流量为零，即v （f ）=0，当且仅当f 是零流。 【答案】论断错误。 流量
但f 不是零流。
6． 某厂生产一种产品，估计该产品在未来四个月的销售量分别为400件，500件，300件，200件，该项 产品的生产准备费用每批为500元，每件的生产费用为1元，存储费用每件每月l 元。假定1月初的存货为100 件，4月底的存货为零。试求该厂在这四个月内的最优生产计划。 【答案】（1）生产成本函数为:
（单位：百元）
，只表明发点的净输出量为零，可能流出等于流入，此时
，
库存费用函数为权h i （v i ）=vi ，可视为凹函数，用再生产点性质解此题。
（2）
（3） 除l 月初原有库存货100件外，总成本最低为3000元，最优生产计划有以下三种: 计划即计划即计划即
时，
时，
时，
时，
7． 某公司现拥有资金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）递推方程:
8． 表1和表2中，分别给出两个运输问题的产销平衡表和单位运价表，试用伏格尔（Vogel ）法直接给出近似最优解。
表1 表
2
【答案】（l ） 第一步:在表1中分别求各行和各列的最小运价和次小运价的差额，并分别填入该表的最右列和最下行，如表3所示。
表
3
第二步: 从行差额或列差额中选出最大者，选择它所在行或列中的最小元素。在表5中，第3列是最大差额所在列。第3列中最小元素为1，可确定产地2的产品优先供应销地3的需要，得表6。同时将运价表中的第3 列数字划去，如表5所示。
表4 表5