运筹学课件-ppt-复习资料-整数规划(运筹学).ppt

运筹学王莉莉四川农业大学数学系2012年11月 学习目标掌握一般整数规划问题概念及模型结构 掌握分支定界法与割平面法的原理 能够运用分支定界法与割平面法求解整数规划问题 熟练掌握0 1变量的应用 能够建立0 1规划模型 并能够用隐枚举法进行求解 掌握分配问题的概念和数学模型 并能用匈牙利算法熟练求解该类问题 第六章 整数规划 引言 整数规划是规划论中近几十年才发展起来的一个重要分支 主要是由于经济管理中的大量问题在抽象成模型时 人们发现许多量具有不可分割性 因此当它们被作为变量引入到规划中时 常要求满足取整条件 如生产计划中 生产机器多少台 整数 人力资源管理中 招聘员工多少人 整数 运输问题中 从一个港口到另一个港口的集装箱调运数量 整数 等 某公司拟以集装箱托运甲 乙两种货物 这两种货物每件的体积 重量 可获利润以及托运所受限制如下表 问两种货物各装多少箱 可使获得利润最大 背包问题 设甲 乙货物各装x1 x2箱 利润为zmaxz 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 x2为整数 某国外大型连锁超市集团准备全面进入某省会城市 拟从可供选择的10个店址中确定5个 每个备选店址用符号L1 L2 L10表示 经过调查 每个备选店址相应的前期预计投入和所覆盖的目标顾客数的综合值分别为C1 C2 C10 综合值越大越好 并且在店址选择上要满足以下条件 1 L1和L5必须同时选择 2 L8和L1二者必选其一 但不能同选 3 L3 L7不能同选 L4 L7不能同选 4 L5 L6 L7 L8最多只能选两个 试帮助该集团超市给出最佳地选址方案 选址问题 整数规划IntegerProgramming 整数规划数学模型的一般形式 整数规划问题的类型 纯整数规划 pureintegerprogramming 全部决策变量都必须取整数值 混合整数规划 mixedintegerprogramming 决策变量中一部分必须取整数值 另一部分可以不取整数值 0 1整数规划 zero oneintegerprogramming 决策变量只能取值0或1 整数规划的解法 从数学模型上看 整数规划似乎是线性规划的一种特殊形式 直觉认为 对于整数规划的求解可以先不考虑对变量的整数约束 作为一般的线性规划来求解 当解是非整数时 可用四舍五入或凑整方法寻找最优解 是否可行 线性规划模型maxz x1 4x2s t 14x1 42x2 196 x1 2x2 5x1 x2 0 整数规划模型maxz x1 4x2s t 14x1 42x2 196 x1 2x2 5x1 x2 0 x1 x2为整数 A 2 6 3 8 z 17 8 D 5 3 z 17 例如 B 2 3 z 14 C 3 4 整数规划与对应线性规划解得关系 整数规划之相应线性规划的最优解经四舍五入不能得到其最优解 整数规划的最优解不会优于其对应的线性规划的最优解 1 任何求max的整数规划的最优目标函数值小于或等于相应的线性规划的最优目标函数值 对应线性规划最优解为其上界 2 任何求min的整数规划的最优目标函数值大于或等于相应的线性规划的最优目标函数 对应线性规划最优解为其下界 整数规划的求解方法 整数规划的求解方法有以下三种 枚举法分支定界法割平面法 分支定界法branchandboundmethod 在20世纪60年代初LandDoing和Dakin等人提出了分支定界法 由于该方法灵活且便于用计算机求解 所以目前已成为解整数规划的重要方法之一 分支定界法可用来求解纯整数规划和混合整数规划问题 分支定界法的关键是分支和定界 首先 不考虑变量的整数约束 求解相应的线性规划 得到线性规划的最优解 如果线性规划的最优解恰好是整数解 则这个解就是整数规划的最优解 如果线性规划的最优解中至少有一个变量不是整数 选择其中一个将线性规划的可行域切割成两部分 分别求解两个线性规划的最优解 如果这两个线性规划的最优解还不是整数解 分别把每一个可行域再进行分割 这个过程 叫做 分枝 分枝过程得到的整数解中 目标函数值最大的一个叫做整数规划目标函数值的 界 分枝过程中非整数的线性规划的最优解 如果目标函数值小于或等于这个 界 就停止继续分枝 这个过程 叫做 定界 分枝定界法的思路 01234567 54321 z 15 z 19 z 24 z 28 9 例maxz 3x1 5x2 28 9 分枝 选择非整变量x1 将可行域分为x1 3和x1 4两部分 01234567 54321 z 15 z 19 z 24 z 28 9 28 9 maxz 3x1 5x2 分枝 选择非整变量x2 将可行域分为x2 3和x2 4两部分 01234567 54321 z 15 z 19 z 24 z 28 9 28 9 28 6 28 7 maxz 3x1 5x2 分枝 选择非整变量x1 将可行域分为x1 2 24 定界 z 24 01234567 54321 z 15 z 19 z 24 z 28 9 28 9 28 6 28 7 28 24 maxz 3x1 5x2 分枝 选择非整变量x2 将可行域分为x2 4 定界 z 24 01234567 54321 z 15 z 19 z 24 z 28 9 28 9 28 6 28 7 28 24 27 maxz 3x1 5x2 分枝 选择非整变量x2 将可行域分为x2 3 定界 z 24 定界 z 26 26 01234567 54321 z 15 z 19 z 24 z 28 9 28 9 28 6 28 7 28 24 27 26 maxz 3x1 5x2 分枝 选择非整变量x1 将可行域分为x1 4和x1 5两部分 定界 z 26 01234567 54321 z 15 z 19 z 24 z 28 9 28 9 28 6 28 7 28 24 27 26 28 最优解 x1 4 x2 3 maxz 27 定界 z 26 27 定界 z 27 设甲 乙货物各装x1 x2箱 利润为zmaxz 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 x1 x2为整数 例 解 1 不考虑整数约束条件 求解对应的线性规划问题maxz 4x1 3x2s t 3x1 4x2 124x1 2x2 9x1 x2 0 得最优解x1 1 2 x2 2 1 对应目标函数值z0 11 1显然它不满足整数条件 但可以确定最优的目标函数值0 z 11 1 2 分枝 取非整数变量x1 1 2 构造两个约束条件x1 1和x1 2 将原问题分解成两个子问题B1和B2B1 maxz 4x1 3x2B2 maxz 4x1 3x2s t 3x1 4x2 12s t 3x1 4x2 124x1 2x2 94x1 2x2 9x1 1x1 2x1 x2 0且为整数x1 x2 0且为整数 分别不考虑B1 B2整数约束条件 求解得最优解x1 1 x2 2 25 对应目标函数值z1 10 75最优解x1 2 x2 0 5 对应目标函数值z2 9 5显然它不满足整数条件 但可以确定0 z 10 75 3 再分枝 选出z较大的B1 对其再分枝 取非整变量x2 2 25 构造两个约束条件x2 2和x2 3 将原问题分解成两个子问题B11和B12B11 maxz 4x1 3x2B12 maxz 4x1 3x2s t 3x1 4x2 12s t 3x1 4x2 124x1 2x2 94x1 2x2 9x1 1 x2 2x1 1 x2 3x1 x2 0且为整数x1 x2 0且为整数 分别不考虑B11 B12整数约束条件 求解得最优解x1 1 x2 3 对应目标函数值z3 10最优解x1 0 x2 3 对应目标函数值z4 9从而B1的最优解为x1 1 x2 3 确定0 z 10 4 剪枝 由于分枝B2的最优非整数解小于B1的最优整数解 故分枝B2可剪去 从而原问题的最优解就为B1的最优解 即x1 1 x2 3 目标函数最优值z 10 作业 P1086 1 2 maxz 3x1 2x2s t 2x1 3x2 142x1 x2 9x1 x2 0 x1 x2为整数 解 1 不考虑整数约束条件 求解对应的线性规划问题maxz 3x1 2x2s t 2x1 3x2 142x1 x2 9x1 x2 0 添加松弛变量 转化成标准型minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x1 x2 x3 x4 0 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x1 x2 x3 x4 0 写出单纯形表 74 5 得最优解x1 13 4 x2 5 2 对应目标函数值z0 59 4显然它不满足整数条件 但可以确定最优的目标函数值0 z 59 4 2 59 2 分枝 取非整数变量x2 5 2 构造两个约束条件x2 2和x2 3 将原问题分解成两个子问题B1和B2B1 maxz 3x1 2x2B2 maxz 3x1 2x2s t 2x1 3x2 14s t 2x1 3x2 142x1 x2 92x1 x2 9x2 2x2 3x1 x2 0且为整数x1 x2 0且为整数 分别不考虑B1 B2整数约束条件 求解 对问题B1B1 maxz 3x1 2x2s t 2x1 3x2 142x1 x2 9x2 2x1 x2 0 对问题B1B1 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x2 x5 2x1 x5 0 添加松弛变量 转化为标准型 B1 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x2 x5 2x1 x5 0 写出单纯形表 74 5 2 592 B1最优解x1 7 2 x2 2 对应目标函数值z1 29 2显然它不满足整数条件 对B2问题 添加松弛变量 转化为标准型 对问题B2B2 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x2 x5 3x1 x5 0 B2 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x2 x5 3x1 x5 0 引入人工变量x6 B2 minz 3x1 2x2 Mx6s t 2x1 3x2 x3 142x1 x2 x4 9x2 x5 x6 3x1 x6 0 B2 minz 3x1 2x2 Mx6s t 2x1 3x2 x3 142x1 x2 x4 9x2 x5 x6 3x1 x6 0 B2 minz 3x1 2 M x2 Mx5 3Ms t 2x1 3x2 x3 142x1 x2 x4 9x2 x5 x6 3x1 x6 0 目标函数中消去基变量 B2 minz 3x1 2 M x2 Mx5 3Ms t 2x1 3x2 x3 142x1 x2 x4 9x2 x5 x6 3x1 x6 0 写出单纯形表 14 393 2 53 B2最优解x1 5 2 x2 3 对应目标函数值z2 27 2显然它不满足整数条件 B1最优解x1 7 2 x2 0 对应目标函数值z1 29 2显然它不满足整数条件 由于B1和B2都不满足整数条件 故还需要再分枝 同时 可以确定0 z 29 2 3 再分枝 选出z较大的B1 对其再分枝 取非整变量x1 7 2 构造两个约束条件x1 3和x1 4 将原问题分解成两个子问题B11和B12B11 maxz 3x1 2x2B12 maxz 3x1 2x2s t 2x1 3x2 14s t 2x1 3x2 142x1 x2 92x1 x2 9x1 3 x2 2x1 4 x2 2x1 x2 0且为整数x1 x2 0且为整数 分别不考虑B11 B12整数约束条件 求解 对问题B11B11 maxz 3x1 2x2s t 2x1 3x2 142x1 x2 9x1 3 x2 2x1 x2 0 对问题B11B11 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x1 x5 3x2 x6 2x1 x6 0 对B11问题 添加松弛变量 转化为标准型 对问题B11B11 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x1 x5 3x2 x6 2 写出单纯形表 74 53 8 33 2 B11最优解x1 3 x2 2 对应目标函数值z3 13 对B12问题 添加松弛变量 转化为标准型 对问题B12B12 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x1 x5 4x2 x6 2x1 x6 0 引入人工变量x7 B12 minz 3x1 2x2s t 2x1 3x2 x3 142x1 x2 x4 9x1 x5 4x2 x6 2 B12 minz 3x1 2x2 Mx7s t 2x1 3x2 x3 142x1 x2 x4 9x1 x5 x7 4x2 x6 2 目标函数中消去基变量 B12 minz 3 M x1 2x2 Mx5 4Ms t 2x1 3x2 x3 142x1 x2 x4 9x1 x5 x7 4x2 x6 2 B12 minz 3x1 2x2 Mx7s t 2x1 3x2 x3 142x1 x2 x4 9x1 x5 x7 4x2 x6 2 写出单纯形表 B12 minz 3 M x1 2x2 Mx5 4Ms t 2x1 3x2 x3 142x1 x2 x4 9x1 x5 x7 4x2 x6 2 74 54 30 5 2 5192 B12最优解x1 4 x2 1 对应目标函数值z4 14 B11最优解x1 3 x2 2 对应目标函数值z3 13 从而得B1最优解x1 4 x2 1确定0 z 14 4 剪枝 由于分枝B2的最优非整数解27 2小于B1的最优整数解14 故分枝B2可剪去 从而原问题的最优解就为B1的最优解 即x1 4 x2 1 目标函数最优值z 14 3 割平面法cuttingplaneapproach 在1958年由R E Gomory 柯莫雷 提出了割平面法 它是求解整数规划的另一个有效方法 通常用于求解纯整数规划和混合整数规划问题 割平面法的基础仍然是用解线性规划的方法求解整数规划 割平面法求解整数规划问题时 若其松驰问题的最优解X 不满足整数要求时 则从X 的非整分量中选取一个 用以构造一个线性约束条件 割平面 将其加入原松驰问题中 形成一个新的线性规划 然后求解之 割平面法的思路 其关键在于新增加的这个线性约束条件将切割掉部分非整数解 而不会切割掉问题的任何整数解 如何选取割平面 线性约束条件 maxz x1 x2s t x1 x2 14x1 x2 8x1 x2 0 x1 x2为整数 例 解 添加松弛变量 转化成标准型minz x1 x2s t x1 x2 x3 14x1 x2 x4 8x1 x2 x3 x4 0 且为整数 不考虑整数约束 写出单纯形表 18 5 7 得最优解x1 7 5 x2 12 5 对应目标函数值z 19 5 即maxz 19 5 显然它不满足整数条件 我们可以从上表中得到一个变量之间的关系式 由于任何实数都可以分解成一个整数与一个非负真分数的和 将上式变形得 由于x1 x3都有整数要求 因为等式左边为整数 右边括号里为正数 所以等式右边必为负数 得下式 引入松弛变量化为等式 将其作为约束条件 加到最优表的最后一行 3 42 得最优解x1 3 2 x2 2 对应目标函数值z 7 2 即maxz 7 2 显然它还不满足整数条件 我们继续作割平面 从上表中得到一个变量之间的关系式 同上 由于任何实数都可以分解成一个整数与一个非负真分数的和 将上式变形得 由于x1 x5都有整数要求 所以上式右端必为负数 得下式 引入松弛变量化为等式 将其作为约束条件 加到最优表的最后一行 11 得最优解x1 1 x2 2 满足整数条件 对应目标函数值z 3 即maxz 3 0123 21 x1 几何意义 x2 x2 2 x1 x2 3 作业 P1086 2 1 maxz 6x1 4x2s t 2x1 x2 72x1 4x2 13x1 x2 0 x1 x2为整数 解 添加松弛变量 转化成标准型minz 6x1 4x2s t 2x1 x2 x3 72x1 4x2 x4 13x1 x2 x3 x4 0 且为整数 不考虑整数约束 写出单纯形表 3 56 5 72 得最优解x1 5 2 x2 2 对应目标函数值z 23 即maxz 23 显然它不满足整数条件 我们可以从上表中得到一个变量之间的关系式 由于任何实数都可以分解成一个整数与一个非负真分数的和 将上式变形得 由于x1 x4都有整数要求 所以等式右边必为负数 得下式 引入松弛变量化为等式 将其作为约束条件 加到最优表的最后一行 42 5 得最优解x1 13 5 x2 9 5 对应目标函数值z 114 5 即maxz 114 5 显然它不满足整数条件 我们可以从上表中得到一个变量之间的关系式 由于任何实数都可以分解成一个整数与一个非负真分数的和 将上式变形得 由于x1 x5都有整数要求 所以等式右边必为负数 得下式 引入松弛变量化为等式 将其作为约束条件 加到最优表的最后一行 3 得最优解x1 11 4 x2 3 2 对应目标函数值z 45 2 即maxz 45 2 显然它不满足整数条件 我们可以从上表中得到一个变量之间的关系式 由于任何实数都可以分解成一个整数与一个非负真分数的和 将上式变形得 由于x2 x3都有整数要求 所以等式右边必为负数 得下式 引入松弛变量化为等式 将其作为约束条件 加到最优表的最后一行 1 得最优解x1 3 x2 1 对应目标函数值z 22 即maxz 22 0 1整数规划 0 1整数规划是整数规划中的特殊情形 它的变量仅取值0或者1 我们通常称0 1变量或逻辑变量 在实践中 许多问题只回答是或否 例如 对某个项目是否投资 对某个应聘者是否聘用 对某种新产品是否研发等 这类问题都可以用0 1变量来描绘 布点问题 某城市共有6个区 每个区都可以建消防站 市政府希望设置的消防站最少 但必须满足在城市任何地区发生火警时 消防车要在15分钟内赶到现场 据实地测定 各区之间消防车行驶的时间见下表 请帮助该市制定一个布点最少的计划 表消防车在各区间行驶时间表单位 min 本问题的约束方程是要保证每个地区都有一个消防站在15分钟行程内 如地区1 可知在地区1及地区2内设消防站都能达到此要求 即x1 x2 1 因此本问题的数学模型为 minz x1 x2 x3 x4 x5 x6x1 x2 1x1 x2 x6 1x3 x4 1x3 x4 x5 1x4 x5 x6 1x2 x5 x6 1xi 1或0 i 1 6 解 引入0 1变量xi作决策变量 令 指派问题 例设有n个人被分配去做n件工作 规划每个人只做一件工作 每件工作只有一个人去做 已知第i个人做第j件工作的效率为Cij i j 1 2 n 并且假设Cij 0 问应如何分配才能使得总效率最高 对于0 1整数规划问题 由于每个变量只取0或1两个值 一般用穷举法 即检查变量取值为0或1的每一种组合 比较目标函数值以求得最优解 这就需要检查变量取值的2n个组合 对于变量个数n较大 例如n 10 这几乎是不可能的 因此常设计一些方法 只检查变量取值的组合的一部分 就能求到问题的最优解 这样的方法称为隐枚举法 Implicitenumeration 分枝定界法也是一种隐枚举法 maxz 3x1 2x2 5x3s t x1 2x2 x3 2x1 4x2 x3 4x1 x2 34x2 x3 6x1 x2 x3 0或1 例 解 先通过试探的方法找一个可行解 容易看出 x1 x2 x3 1 0 0 是符合条件的一个解 相应的目标函数值z 3 对于极大化问题 希望z 3 于是增加一个约束条件 3x1 2x2 5x3 3 后加的条件称为过滤条件 原问题转化为 maxz 3x1 2x2 5x3s t x1 2x2 x3 2x1 4x2 x3 4x1 x2 34x2 x3 63x1 2x2 5x3 3x1 x2 x3 0或1 用全部枚举的方法 3个变量共有23 8个解 在计算过程中 若一旦遇到z值已超过过滤条件右边的值 应改变过滤条件 使右边为迄今为止最大者 然后继续作 例如当检查点 0 0 1 时因z 5 3 所以应将过滤条件换成 3x1 2x2 5x3 5这种对过滤条件的改进 更可以减少计算量 注 一般常重新排列xi的顺序使目标函数中xi的系数是递增 不减 的 在上一例中 改写z 3x1 2x2 5x3 2x2 3x1 5x3 因为系数 2 3 5是递增的 变量 x1 x2 x3 也按下述顺序取值 0 0 0 0 0 1 0 1 0 0 1 1 这样最优解容易比较早的发现 再结合过滤条件的改进 更可以减少计算量 maxz 2x2 3x1 5x3s t x1 2x2 x3 2x1 4x2 x3 4x1 x2 34x2 x3 6x1 x2 x3 0或1 maxz 2x2 3x1 5x3s t x1 2x2 x3 2x1 4x2 x3 4x1 x2 34x2 x3 6x1 x2 x3 0或1 至此 z值已不能改进 即得最优解z 8 指派问题AssignmentProblem 在生活中经常遇到这样的问题 某单位需完成n项任务 恰好有n个人可以承担这些任务 由于每人的专长不同 各人完成任务不同 或所费时间 效率也不同 于是产生应指派哪个人去完成哪项任务 使完成n项任务的总效率最高 或所需总时间最小 指派问题 例有一份中文说明书 需译成英 日 德 俄四种文字 分别记作E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成不同语种的说明书所需时间如下表 问应指派何人去完成何种工作 使所需总时间最少 设有n个人被分配去做n件工作 规划每个人只做一件工作 每件工作只有一个人去做 已知第i个人做第j件工作的效率为Cij i j 1 2 n 并且假设Cij 0 问应如何分配才能使得总效率最高 指派问题一般形式 指派问题的可行解xij可以写成表格或者矩阵的形式 称为解矩阵 如上一例的一个可行解矩阵是 显然 这不是最优的 解矩阵中各行各列的元素之和都为1 指派问题是0 1规划的特例 也是运输问题的特例 产地和销地个数相等 且产量和销量都为1 匈牙利解法 标准的指派问题可以用整数规划 0 1规划或运输问题的解法来求解 但是 这些方法都没有充分利用指派问题的特殊性质来有效减少计算量 1955年 库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理 提出了指派问题的一种解法 由此 习惯上称之为匈牙利解法 效率矩阵 将模型中目标函数的系数cij排成矩阵 称该矩阵为指派问题的效率矩阵 效率矩阵的性质 若从指派问题的系数矩阵C的某行 或某列 各元素分别减去一个常数k 得到一个新的系数矩阵C 则以C 和C为系数矩阵的两个指派问题有相同的最优解 利用这个性质 可使原系数矩阵C变换为含有很多0元素的新系数矩阵C 而最优解保持不变 在系数矩阵C 中 我们关心位于不同行不同列的0元素 简称独立零元素 康尼格定理 设矩阵C中一部分元素为0 另一部分不为0 则划去C所有0元素所需的最小直线数等于C中不同行不同列上0元素的个数 若在系数矩阵C 中找到n个独立零元素 则令解矩阵中这n个独立零元素的元素取值为1 其它元素取值为0 将其带入目标函数中得到的z值一定是最小的 即得指派问题的最优解 以上例说明步骤 2151341041415914161378119 01311260101105740142 2497 min cij 每行减去最小数 匈牙利解法的一般步骤 步骤一 变换系数矩阵 使其每行及每列至少有一个零元素 同时不出现负元素 01311260101104740142 0042 min 01370606905320100 c ij 每列减去最小数 步骤二 进行试指派 即确定独立零元素 1 从只有一个零元素的行 列 开始 给这个零元素加圈 表示这行所代表的人 只有一种任务可以指派 然后划去该零元素所在列 行 的其它零元素 表示这个任务已经指派完 不必考虑其他人 2 从只有一个零元素的列 行 的零元素加圈 划去该零元素所在行 列 的其它零元素 3 反复上面两步 直到所有零元素都被划出 4 若仍有没有化掉的零元素 则从剩余零元素最少的行或列开始 选择其中一个加圈 其余化掉 01370606905320100 此时加圈0元素