188宝金博页面版

2017 年南京航空航天大学经济与管理学院 824 运筹学考研导师圈点必考题汇编?一? 说明?①本资料为 VIP 学员内部使用?整理汇编了历届导师圈点的重点试题及常考试题。 —————————————————————————————————————————— 一、简答题 1? 试简述求解整数规划模型的分枝定界法剪枝的几种情况。 【答案】?l?某枝已经达到其范围内的最优解; ?2?某枝域内没有可行解时?即是不可行域; ?3?某枝所得数据不优于当前最优解时。 2? 简述求解整数规划分枝定界法的基本思想。 【答案】设有最大化的整数规划问题 A?与它对应的线性规划为问题 B?从解问题 B 开始?若其最优解不符合 A 的整数条件?那么 B 的最优目标函数必是 A 的最优目标函数 z*的上界?记作 ;而 A 的任意可行解的目标函数值将是 z*的一个下界 ;。分支定界法就是将 B 的可行域分成子区域?称为分支?的方法?逐步减小 和增大 :? 最终求到 z*。 3? 什么是可行流? 【答案】满足下列条件的网络流 f 称为可行流 ?l?容量限制条件:对每一弧?v i ?v j ? ?2?平衡条件 对于中间点?流出量=流入量?即对每个 对于起点 Vs?记 对于终点 V t?记 式中?V?f?称为这个可行流 f 的流量?即发点的净输出量?或收点的净输入量?。 二、计算题 4? 有一运输问题?它有 3 个重载点和 2 个车场?其运输表如表所示。表中小方框内的数字为两点 间的车辆空驶距离?1、2 和 3 三项运输业务的重载里程?己将装卸车时间折算在内?分别为 7?8 和 9?其他有关情况如表中所示。此外?要求车辆的每条行车路线总长度?包括重驶、空驶及装卸车所用时间的折算长度?L 在 45~ 60 之间。试用本章给出的车辆优化调度启发式算法?求出其满意的可接受可行解?并据此排出行车路线。 表