2017年河南大学运筹学与控制论综合(运筹学、常微分方程、概率论与数理统计)之运筹学考研复试核心题库
● 摘要
一、简答题
1． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
2． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
二、计算题
3． 现有线性规划问题
先用单纯形法求出最优解，然后分析在下列各种条件下，最优解分别有什么变化? （1）约束条件式②的右端常数由20变为30; （2）约束条件式②的右端常数由90变为70; （3）目标函数中x 3的系数由13变为8; （4）x 1的系数向量由
、变成
;
; 。
（5）增加一个约束条件式③:
（6）将原约束条件②改变为
【答案】在上述线性规划问题的第①，②个约束条件中分别引入松弛变量x 4，x 5，得
建立初始单纯形表，并利用单纯形法进行迭代计算，如表所示。
表
所以，原问题得到最优解为
（l ）约束条件式①的右端常数由20变为
30
，最优目标函数值为z*=100。
列出单纯形表，并利用对偶单纯形法求解，求解过程如表所示。
表
所以，线性规划为题的最优解变为（2） 约束条件②的右端常数由90变为70
，最优目标函数值为。
列出初始单纯形表，并利用对偶单纯形法进行迭代计算，求解过程如表所示。
所以，线性规划的最优解变为
（3）目标函数中x 3的系数由13变为8
，最优目标函数值为。
，
因为在最终单纯形表中x3是非基变量，其目标函数的系数变化后，对应的检验数仍小于0。所以，此时线性规划问题的最优解不发生变化。
（4）x 1的系数列向量由（l ，一2）变为（o ，5） x 在最终单纯形表中的系数列向量变为
其对应的检验数变为
所以线性规划问题的最优解不变。 （5）增加一个约束条件③：
在约束条件式③中加入松弛变量x 6，得纯形表，并进行 进一步迭代，求解过程如表所示。
表
l
T
T
。将此约束条件加入原单