管理运筹学整数规划

管理运筹学 整数规划 2 第6章整数规划 线性规划的决策变量取值可以是任意非负实数 但许多实际问题中 只有当决策变量的取值为整数时才有意义 例如 产品的件数 机器的台数 装货的车数 完成工作的人数等 分数或小数解显然是不合理的 要求全部或部分决策变量的取值为整数的线性规划问题 称为整数线性规划 简称整数规划 IntegerProgramming 全部决策变量的取值都为整数 则称为全整数规划 AllIP 仅要求部分决策变量的取值为整数 则称为混合整数规划 MixedIP 要求决策变量只能取0或1值 则称为0 1规划 0 1Programming 3 第一节整数规划问题 为了满足整数要求 似乎可以把线性规划的小数最优解进行 舍入化整 以得到与最优解相近的整数解 舍入化整 一般是不可行的 化整后的解有可能成为非可行解 虽是可行解 却不是最优解 例如 一 问题的提出 问如何安排甲 乙两产品的产量 使利润为最大 4 第一节整数规划问题 解 设x1为甲产品的台数 x2为乙产品的台数 maxZ 6x1 5x22x1 x2 9 5x1 7x2 35x1 x2 0 x1 x2取整数不考虑整数约束则是一个LP问题 称为原整数规划的松弛问题 不考虑整数约束的最优解 x1 28 9 x2 25 9 Z 293 9舍入化整x1 3 x2 3 Z 33 不满足约束条件5x1 7x2 35 非可行解 x1 3 x2 2 Z 28 满足约束条件 是可行解 但不是最优解 x1 4 x2 1 Z 29 满足约束条件 才是最优解 5 步骤 在线性规划的可行域内列出所有决策变量可能取的整数值 求出这些变量所有可行的整数解 比较它们相应的目标函数值 最优的目标函数值所对应的解就是整数规划的最优解 实用性 只有两个决策变量 可行的整数解较少 3 3 第一节整数规划问题 二 整数规划的图解法 6 第一节整数规划问题 设备购置问题 某厂拟用M元资金购买m种设备 设备i的单价为pi 现有n个地点可装置这些设备 第j处最多可装置bj台 设备i装置在j处可获利cij元 如何购置 总利润最大 假设 购买第i种设备yi台数 将第i种设备安装在第j处的台数xij该问题的数学模型 三 整数规划问题举例 7 第一节整数规划问题 投资决策问题 某厂拟用b元资金投资n个项目 项目j需资金aj元 可获利cj元 应选择那些项目 获利最大 假设 xj 1表示投资项目j xj 0表示不投资项目j该问题的数学模型 8 第一节整数规划问题 工厂选址问题 某商品有n个销地 各销地的需求量为bj吨 天 现拟在m个地点中选址建生产厂 一个地方最多只能建一个工厂 若选i地建厂 生产能力为ai吨 天 固定费用为di元 天 已知i址至销地j的运价为cij元 吨 如何选址和安排调运 总费用最小 假设 yi 1 选择第i址建厂 yi 0 不选择第i址建厂 从厂址i至销地j运量为xij 该问题的数学模型 9 第一节整数规划问题 固定成本 费用问题 可用混合整数规划求解 某工厂生产几种产品 每种产品都存在一项固定成本 只要生产 就会产生 ki表示生产第j种产品的固定成本 假设 yi 1 生产第i种产品 yi 0 不生产第i种产品成本 xi为第i种产品的产量 该问题的数学模型maxz 4x1 5x2 6x3 100y1 150y2 200y3 M为充分大的数 等价为 总成本为 10 第一节整数规划问题 指派问题 把多项任务分给多个人来做 由于每个人做事的效率都不同 因些存在如何安排工作的问题 使总效率假设 xij 1时 指派第i个人去完成第j项工作 xij 0时 不指派第i个人去完成第j项工作 更改第166面例6 设甲乙两人均可安排完成两项工作 另外两人最多安排一项工作 部如何安排工作 使总工时最小 11 第一节整数规划问题 有两个相互排斥的约束条件的问题 为了统一在一个问题中 引入变量y 则上述约束条件可改写为 其中M是充分大的数 或 12 第二节分枝定界法 分枝定界法 BranchandBoundMethod 基本思想 先求出整数规划相应的LP 即不考虑整数限制 的最优解 若求得的最优解符合整数要求 则是原IP的最优解 若不满足整数条件 则任选一个不满足整数条件的变量来构造新的约束 在原可行域中剔除部分非整数解 然后 再在缩小的可行域中求解新构造的线性规划的最优解 这样通过求解一系列线性规划问题 最终得到原整数规划的最优解 13 第二节分枝定界法 定界的含义 整数规划是在相应的线性规划的基础上增加变量为整数的约束条件 整数规划的最优解不会优于相应线性规划的最优解 对极大化问题来说 相应线性规划的目标函数最优值是原整数规划函数值的上界 对极小化问题来说 相应线性规划的目标函数的最优值是原整数规划目标函数值的下界 14 第二节分枝定界法 例maxZ 6x1 5x22x1 x2 9 5x1 7x2 35x1 x2 0 x1 x2取整数第一步 不考虑变量的整数约束 求相应LP 问题1 的最优解 x1 28 9 x2 25 9 Z1 293 9第二步 定界过程这个解不满足整数约束 这时目标函值Z1是整数规划的目标上界 因为x1 x2 0是整数规划问题的可行解 所以下界为0 第三步 分枝过程将不满足整数约束的变量x1进行分枝 x1称为分枝变量 构造两个新的约束条件 x1 28 9 3 x1 28 9 1 4 15 第二节分枝定界法 这样就把相应的线性规划的可行域分成两个部分 如图所示 问题2 maxZ 6x1 5x2问题3 maxZ 6x1 5x22x1 x2 9 2x1 x2 95x1 7x2 355x1 7x2 35x1 3x1 4x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数 16 第二节分枝定界法 求解相应的线性规划的最优解问题2相应的线性规划的最优解 x1 3 x2 20 7 Z2 226 7问题3相应的线性规划的最优解 x1 4 x2 1 Z3 29第四步 定界过程LP3的解满足整数约束 不必再分枝 它的目标函数值是29 大于原有下界0 则新的下界为29 现有上界为未分枝子问题中目标函数最大值 即为226 7 LP2的解仍不满足整数约束的要求 它的目标函数值226 7大于现有下界 则应继续分枝 第五步 分枝过程将不满足整数约束的变量x2进行分枝 构造两个新的约束条件 x2 20 7 2 x2 20 7 1 3 17 第二节分枝定界法 问题4 maxZ 6x1 5x2问题5 maxZ 6x1 5x22x1 x2 9 2x1 x2 95x1 7x2 355x1 7x2 35x1 3x1 3x2 2x2 3x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数 18 第二节分枝定界法 求解相应的线性规划的最优解问题4相应的线性规划的最优解 x1 3 x2 2 Z4 28问题5相应的线性规划的最优解 x1 14 5 x2 3 Z5 159 5第六步 定界过程LP4的解满足整数约束 不必再分枝 它的目标函数值是28 小于原有下界29 则下界仍为29 现有上界为未分枝子问题中目标函数最大值 即为159 5 LP5的解仍不满足整数约束的要求 它的目标函数值159 5大于现有下界29 则应继续分枝 第七步 分枝过程将不满足整数约束的变量x1进行分枝 构造两个新的约束条件 x1 14 5 2 x1 14 5 1 3 19 第二节分枝定界法 问题6 maxZ 6x1 5x2问题7 maxZ 6x1 5x22x1 x2 9 2x1 x2 95x1 7x2 355x1 7x2 35x1 3x1 3x2 3x2 3x1 2x1 3x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数 20 第二节分枝定界法 求解相应的线性规划的最优解 问题6相应的线性规划的最优解 x1 2 x2 25 7 Z6 209 7问题7相应的线性规划的最优解 无最优解第八步 定界过程LP7的无最优解 不必再分枝 下界仍为29 现有上界为未分枝子问题中目标函数最大值 即为209 7 LP6的解仍不满足整数约束的要求 它的目标函数值209 7大于现有下界29 则应继续分枝 第九步 分枝过程将不满足整数约束的变量x2进行分枝 构造两个新的约束条件 x2 3 x2 4 21 第二节分枝定界法 问题8 maxZ 6x1 5x2问题9 maxZ 6x1 5x22x1 x2 9 2x1 x2 95x1 7x2 355x1 7x2 35x1 3x1 3x2 3x2 3x1 2x1 2x2 3x2 4x1 x2 0 x1 x2 0 x1 x2取整数x1 x2取整数 22 第二节分枝定界法 求解相应的线性规划的最优解问题8相应的线性规划的最优解 x1 2 x2 3 Z8 27问题9相应的线性规划的最优解 x1 7 5 x2 4 Z9 142 5第十步 定界过程LP8的最优解 满足整数约束 不必再分枝 下界