2017年南昌大学线性规划考研复试核心题库
● 摘要
一、简答题
1． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
2． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，
若满足下列条件:
（l ）在弧（2）在弧称
是关于可行流f 的一条增广链。 即即中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。 是从v s 到v t ，的一条链，二、计算题
3． 某工厂备购置一台新机器来扩大生产，新机器安装使用期为三年，在此之后不再使用。然而工作的三年内，负荷较大，随着时间的增长，运行和保修费用将有较大幅度增加。因此，在机器使用1年或2年后再购置一台新机器来代替它可能更经济，表给出了第i 年底购进一台新机器并在第j 年底将其卖掉所花费的总费用（购 置费加运行和保修费减残值，万元）。试将该问题描述成最短路问题，并求解。
表
【答案】把这个问题化为最短路问题。
图
用点v i 表示第i 年年初购进一台新设备，虚设一个点v 4，表示第3年年底。
边（v i ，v j ）表示第i 年初购进的设备一直使用到第j 年年初。
这样设备更新问题就变为:求从v 1，到v 4的最短路问题，计算结果表明:为最短路，路长为14. 即在第二年底更换新设备为最优决策，这时总费用为14万元。
4． 用表上作业法求表1至表4中给出的运输问题的最优解（表中数字M 为任意大正数）。
表1 表
2
表3 表
4
【答案】（l ） 解表1
第一步:用伏格尔法求初始可行解（过程类似于上一题，不再赘述），求得的初始解如表5所示。
表
5
第二步:用位势法进行最优解的判断。在对应于表5的数字格处填入单位运价，并增加一行一列，在行中填入v j ，在列中填入
示。
表6 表
7 ，。令v 1=0，并按照求出所有的和v j ，如表6所示。对于表16中的空格，依据计算其检验数，如表7所
由表7可知，所有空格处的检验数均为非负。所以，表5中的运输方案，即为此问题的最优
最小运价为32。调运方案，由于非基变量的检验数中
（2）解表2
第一步:用伏格尔法求初始可行解，求得的初始解，如表8所示。
表
8 ，所以该运输问题有无穷多最优解。
第二步:用位势法进行最优解的判断。在对应于表8的数字格处填入单位运价，并增加一行一列，在行 中填入v j ，在列中填入。令u 1=0，按照表9
求出所有的和v j ，
并依据计算所 有空格处的检验数，计算结果如表9所示。