[第4章整数规划.doc

第4章 整数规划 判断: 用分枝定界法求解一个极大化的整数规划问题，任何一个可行解的目标函数值是该问题目标函数值的下界；指派问题数学模型的形式同运输问题十分相似，故也可以用表上作用法求解；率矩阵的任一行（或列）减去（或加上）任一常数，指派问题最优解不会受到影响；牙利法只能用于平衡分配问题；于极大化问题，匈牙利法不能直接求解。数规划问题解的目标函数值优于其相应的线性规划问题的解的目标函数。割平面法求解整数规划问题，构造的割平面有可能切去一些不属于最优解的整数解。分枝定界法求解一个极大化的整数规划问题时，当得到多于一个可行解时，通常可任取其中一个作为下界值，在进行比较剪枝。配问题的每个元素都加上同一个常数k，并不会影响最优分配方案。配问题的每个元素都乘上同一个常数k，并不会影响最优分配方案。配问题域运输问题的数学模型结构形式十分相似，故也可以用表上作业法求解。枚举法也可以用来求解分配问题 简答试述分枝定界法求解问题的主要思想。试述隐枚举法的步骤。试讲述割平面方法的基本原理.例举三种应该剪枝的情况。 计算题 分枝定界法分枝定界法求解下列整数规划问题 分枝定界法求解下列整数规划问题 分枝定界法求解下列整数规划问题 用分枝定界法求解下列整数规划问题 用分枝定界法求解下列整数规划问题 分枝定界法解下列整数规划问题： 分枝定界法解下列整数规划问题 分枝定界法解下列整数规划问题 分枝定界法解下列整数规划问题 分枝定界法求解下列整数规划模型 且为整数 有如下整数规划问题 且为整数 试用分枝定界法求其最优解。要求画出分枝求解过程示意图。 隐枚举法隐枚举法求下列0－1规划问题 隐枚举法求下列0－1规划问题 隐枚举法求下列0－1规划问题 隐枚举法求下列0－1规划问题 隐枚举法求下列0－1规划问题 隐枚举法求下列0－1规划问题 隐枚举法求下列0－1规划问题 隐枚举法求下列0－1规划问题 隐枚举法求下列0－1规划问题 用隐枚举法求下列0－1规划模型的解 指派问题匈牙利法求解下述指派问题，已知效率矩阵分别如下： 匈牙利法求解下述指派问题，已知效率矩阵分别如下： 下列系数矩阵的最小分派问题： 下列系数矩阵的最小分派问题： 下列系数矩阵的最小分派问题： 下列系数矩阵的最小分派问题： 知下列五名运动员各种姿势的游泳成绩（各为50米）如下表所示，试问如何从中选拔一个参加200米混合泳的接力队，使预期比赛成绩为最好。 单位：秒 赵 钱 张 王 周 仰泳 蛙泳 蝶泳 自由泳 37.7 43.4 33.3 29.2 32.9 33.1 28.5 26.4 33.8 42.2 38.9 29.6 37.0 34.7 30.4 28.5 35.4 41.8 33.6 31.1 配甲、乙、丙、丁四个人去完成五项