2016年湖北大学数学与统计学学院运筹学考研复试题库
● 摘要
一、计算题
1． 考虑采用分枝定界法求解的一个整数规划问题（目标函数为最大化问题），其中变量x 1，x 2取整数。该 问题的求解由子问题1开始，如图所示。
图
请回 【答案】
（1）在当前状态下，如何对整数规划的最优解进行定界。
（2）如果进行分枝，应该在哪个问题（从子问题2和子问题3中选择）上附加约束? 附加的两个约束分别是什么?
答:（l ）设整数规划的最优目标值为Z*，则对其定界范围为:
（2）如果进行分支，从子问题2开始附加约束，附加的两个约束为:
2． 某线性规划问题有m 个小等号约束条件等号约束条件
【答案】对于m 个小等号约束条件，令:
，P 个大
，现要求在m 个小等号约束条件中取L
个，P 个大等号约束条件取q 个，试将这些条件写在一个模型中。
对于P 个大等号约束条件，令:
3． 用单纯形法求解下列线性规划问题。
【答案】将上述线性规划问题化为标准型为:
用单纯形表计算如表所示，
表
所以，最优解为x*=（40，5，0，0，0，15），最优目标函数值为z*=750。
4． 甲、乙、丙三个铁矿石开采基地向A 、B 、C 、D 四个工厂供应原料，各供应地的供应量（万，各需 求地需求量（万吨）和相互之间的运价（百万元万吨）如表所示。由于外在的原因，吨）
工厂D 的原料只能由 铁矿石开采基地丙来供应。请求解满足这一要求的最优调运方案，要求采用最小元素法建立初始调运方案，采用位势法进行方案检验。
表
T
【答案】该问题属于运输平衡问题。因为工厂D 的原料只能由铁矿石开采基地丙来供应，所以这里规定甲、乙 和D 之间的运价为M ，M 表示足够大的正数。
采用最小元素法得初始调运方案如表所示:（因为基格个数=7-1=6个，故在一空格中填入0）
表
用位势法检验得各空格的检验数（括号内）如表所示:
在初始方案中，存在两个非基变量的检验数小于0，所以该方案不是此问题的最优方案，需进行
相关内容
相关标签