2017年广东工业大学机电工程学院804运筹学考研题库
● 摘要
一、简答题
1． 什么是关于可行流f 的增广链?
【答案】设f 是一个可行流，v s 是网络的起点，v t 是网络的终点，若
满足下列条件: （l ）在弧（2）在弧称
是关于可行流f 的一条增广链。
即即
中每一前向弧是非饱和弧。 中每一后向弧是非零流弧。
是从v s 到v t ，的一条链，
2． 试简述求解整数规划模型的分枝定界法剪枝的几种情况。
【答案】（l ）某枝已经达到其范围内的最优解; （2）某枝域内没有可行解时，即是不可行域; （3）某枝所得数据不优于当前最优解时。
3． 在线性规划的灵敏度分析中，当基变量的价值系数变化后，最优表中哪些数据会发生变化，怎样变化。
【答案】基变量的价值系数变化后，可能会引起伏表中基变量检验数的变化。 设Cr 是基变量Xr 的系数。因
，当Cr 变化△Cr ，时，就引起C B 的变化，这时有:
可见，当Cr 变化成△Cr 后，最终表中的检验数是:
4． 什么是启发式方法? 说明用启发式方法解决实际问题的过程和步骤。
【答案】（1）对于结构不良问题，为得到近似可用的解，分析人员必须运用自己的感知和洞察力，从与其有关而 较基本的模型与算法中寻求其间的联系，从中得到启发，去发现适于解决该问题的思路和途径，这种方法称为启 发式方法。
（2）用启发式方法解决实际问题的过程和步骤:①系统观察和分析实际问题; ②抽象并明确提出问题; ③ 建立启发式数学模型; ④选择启发式策略，设计启发式方法，按照一定的搜索规则反复迭代逼近模型最优可行解，直到得到满意解; ⑤检验和修正模型及其满意解。
二、计算题
5． 试用乘子法求解非线性规划问题（取c=2）:
【答案】设定义拉格朗日函数
于是得到
解得，
6． 已知某个运输问题的产销平衡表、最优运输方案及单位运价表分别如表和表所示。由 于道路维修的原因，从产地戊到销售地残的运输暂时封闭，因此需要对表中的运输方案进行调整。试用尽可能简便的方法重新找最优运输方案。
表
表
【答案】由于产地A 2到销售地B 2的运输暂时封闭，因此两地运价定为∞，利用伏格尔法计算各行列的差额见表
表
，确定所在行最小元素2，即先选择A 2供给B l ，得表 选择最大差额4（第2行）
表
划掉B 2所在行，对上表反复利用伏格尔法进行表上作业法，最终求得产销平衡表如表所示:
表
7． 某规划线性规划问题:
（1）写出其对偶问题;
（2）推导出原问题与对偶问题中目标函数之间的关系。 【答案】（1）其对偶问题为:
（2）若原问题及其对偶问题均具有可行解，则两者均具有最优解，且它们最优解的目标函数值相等。
证明:由于两者均有可行解，根据弱对偶性的推论，对原问题的目标函数值具有上界，对偶问题的目标函数 值具有下界，因此两者均具有最优解。又知当原问题为最优解时，其对偶问题的解为可行解，且有z=w。由最优 性知，这时两者的解均为最优解。
8． 对表所示的运输问题（表内的数字表示单位货物从供应地i 运到需求地j 的运价，表右面和下面的 数字分别表示供应量和需求量）。
（l ）用西北角法计算初始基础可行解;
（2）从这个基础可行解出发，求出这个问题的最优解;
表
相关内容
相关标签