2016年中国矿业大学(徐州)管理学院830运筹学考研内部复习题及答案
● 摘要
一、填空题
1． 无向连通图G 是欧拉图的充要条件是___。
【答案】G 中无奇点
2． 若P （k ）是f （x ）在x （K ）处的下降方向，则满足_。
【答案】均有 【解析】若存在实数
，使对于任意的，就称方向）为均有下式成立:
点的一个下降方向。
3． 若x 为某极大化线性规划问题的一个基可行解，用非基变量表达其目标函数的形式为
则X 为该LP 最优解的条件是:_____。 【答案】
。 【解析】求极大化问题，则当所有非基变量的检验数均为非正时，即得最优解。线性规划最优时要求非基变 量检验数小于等于0，所以
4． 对于线性规划问题:MaxZ=CX.AX≦b.X ≧0，若B=（P 1，P 2，…，P m ）为A 中m 个线性无关的列向量, 且为该LP 的一个可行基，则对应于基B 的基可行解为:_____，该基可行解为最优解的条件是:_____。 【答案】，对于一切有。
【解析】若B=（P 1，P 2，…，P m ）为A 中m 个线性无关的列向量，此时令非基变
量
， 这时变量的个数等于线性方程组的个数，用高斯消去法，可求得对应
于基B 的基可行解
为。由最优解的判别定理，若对于一
切
, 则所求得的基可 行解为最优解。
二、简答题
5． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
6． 简述对偶问题的“互补松弛性”。
【答案】互补松弛性:若
仅当为
最优解。 分别是原问题和对偶问题的可行解。那么，当且
相关内容
相关标签