运筹学-4-整数规划.ppt

运筹学 整数规划 IntegerProgramming 第四章 第四章整数规划 本章主要内容 整数问题规划及其数学模型整数规划问题的求解0 1型整数规划问题指派问题 第四章整数规划 在很多场合 我们建立最优化模型时 实际问题要求决策变量只能取整数值而非连续取值 此时 这类最优化模型就称为整数规划 离散最优化 模型 整数规划的求解往往比线性规划求解困难得多 而且 一般来说不能简单地将相应的线性规划的解取整来获得 第四章整数规划 线性规划模型 实际问题要求xi为整数 如机器的台数 人数等 第四章整数规划 例 胜利家具厂生产桌子和椅子两种家具 桌子售价50元 个 椅子售价30元 个 生产桌子和椅子需要木工和油漆工两种工种 生产一个桌子需要木工4个小时 油漆工2小时 生产一个椅子需要木工3个小时 油漆工1小时 该厂每月可用木工工时为120小时 油漆工工时为50小时 问该厂如何组织生产才能使每月的销售收入最大 第四章整数规划 纯整数规划 第四章整数规划 例 背包问题 一个旅行者 为了准备旅行的必备物品 要在背包里装一些有用的东西 但他最多只能携带b公斤的东西 而每件物品都只能整件携带 于是他给每件物品规定了一个 价值 以表示其有用程度 如果共有m件物品 第i件件物品的重量为bi 价值为ci 问题就变成 在携带的物品总重量不超过b公斤的条件下 携带哪些物品可使总价值最大 第四章整数规划 9 解 Z表示所带物品的总价值 携带物品的总重量 数学模型 0 1规划 第四章整数规划 第四章整数规划 解 数学模型 混合型整数规划 第四章整数规划 例工厂A1和A2生产某种物资 由于该种物资供不应求 故需要再建一家工厂 相应的建厂方案有A3和A4两个 这种物资的需求地有B1 B2 B3 B4四个 各工厂年生产能力 各地年需求量 各厂至各需求地的单位物资运费cij 见下表 工厂A3或A4开工后 每年的生产费用估计分别为1200万或1500万元 现要决定应该建设工厂A3还是A4 才能使今后每年的总费用最少 第四章整数规划 解 这是一个物资运输问题 特点是事先不能确定应该建A3还是A4中哪一个 因而不知道新厂投产后的实际生产物资 为此 引入0 1变量 再设xij为由Ai运往Bj的物资数量 单位为千吨 z表示总费用 单位万元 则该规划问题的数学模型可以表示为 第四章整数规划 混合整数规划问题 第四章整数规划 整数线性规划问题的种类 纯整数线性规划 指全部决策变量都必须取整数值的整数线性规划 混合整数线性规划 决策变量中有一部分必须取整数值 另一部分可以不取整数值的整数线性规划 0 1型整数线性规划 决策变量只能取值0或1的整数线性规划 第四章整数规划 纯整数规划的数学模型 0 1规划的数学模型 第四章整数规划 例 Z 130 可行且Z 140 不可行 可行 第四章整数规划 IP IP 问题的松弛问题 第四章整数规划 松弛问题的最优值是原整数规划的目标函数值的上界 第四章整数规划 例设整数规划问题如下 首先不考虑整数约束 得到线性规划问题 一般称为松弛问题 第四章整数规划 用图解法求出最优解为 x1 3 2 x2 10 3 且有Z 29 6 现求整数解 最优解 如用舍入取整法可得到4个点即 1 3 2 3 1 4 2 4 显然 它们都不可能是整数规划的最优解 x1 x2 3 3 3 2 10 3 按整数规划约束条件 其可行解肯定在线性规划问题的可行域内且为整数点 故整数规划问题的可行解集是一个有限集 如右图所示 其中 2 2 3 1 点的目标函数值最大 即为Z 4 第四章整数规划 分支定界法 1 求整数规划的松弛问题最优解 若松弛问题的最优解满足整数要求 得到整数规划的最优解 否则转下一步 2 分支与定界 任意选一个非整数解的变量xi 在松弛问题中加上约束 xi xi 和xi xi 1组成两个新的松弛问题 称为分枝 新的松弛问题具有特征 当原问题是求最大值时 目标值是分枝问题的上界 当原问题是求最小值时 目标值是分枝问题的下界 检查所有分枝的解及目标函数值 若某分枝的解是整数并且目标函数值大于 max 等于其它分枝的目标值 则将其它分枝剪去不再计算 若还存在非整数解并且目标值大于 max 整数解的目标值 需要继续分枝 再检查 直到得到最优解 分支定界法的解题步骤 上界 x1 x 01 x1 x 01 1 一 分枝定界法的原理 1 分枝 松弛问题的可行域 增加x1 3 增加x1 4 L1 L2 x1 3 x1 4 父问题 子问题 结论1 IP 的最优解一定在某个子问题中 父问题的最优值 3 子问题中的整数解都是 IP 的可行解 子问题的最优解 2 子问题的可行域 父问题的可行域 2 定界 1 LP 的最优值是 IP 的最优值的上界 IP 松弛问题L0 L1 L2 通过对 L0 分枝 使 IP 的最优值的上界不断下降 L3 L4 L5 L6 下界不断上升 上界 下界 得最优值 x1 3 x1 4 z 30 x1 20 x2 4x1 x2 16 5 2x1 3x2 14 5 x2 2 x2 3 x1 2 x1 3 混合型 x1 3 x1 4 L0的最优单纯型表 x5 x5 100013 000 x1 3 x1 4 x1 2 x1 3 x2 2 x2 3 x5 x5 100013 000 x5 x5 001 10 3 101 1 2 000 x4 x5 x2 2 x2 x6 2 x6 0100012 x6 0000 x2 3 X2 x6 3 x6 0 10001 3 x6 0000 X2 x6 3 x1 2 x1 x7 2 00 1 200 3 21 3 4 如何选择分枝的节点及分枝变量 1 分枝节点选择的原则 尽快找到好的整数解 减少搜索节点 提高搜索效率 方法 1 深探法 2 广探法 最后打开的节点最先选择 选择有最大目标函数值的节点继续向下分枝 2 分枝变量选择的原则 寻找那些对问题影响最大的变量首先分枝 1 按目标函数系数选择 选择目标函数系数绝对值最大的变量首先分枝 2 按非整数变量选择 选择与整数值相差最大的非整数变量进行分枝 3 按人为给定的顺序选择 x1 3 x1 4 x2 2 x2 3 x1 2 x1 3 第四章整数规划 割平面法 割平面法的基本思想 若整数规划IP的松弛规划L0的最优解不是整数解 对L0增加一个约束条件 得线性规划L1 此过程缩小了松弛规划的可行解域 在切去松弛规划的最优解的同时 保留松弛规划的任一整数解 因此整数规划IP的解均在L1中 若L1的最优解为整数解 则得IP的最优解 若L1的最优解不是整数解 重复以上步骤 由于可行解域在不断缩小 且保留IP所有的整数解 总可以在有限次后得到IP的最优解 割平面 39 问题 如何寻找割平面 增加的约束方程须满足什么条件才能使 1 割掉松弛规划的最优解 2 保留所有的整数解 40 二 割平面法 41 L0的最优单纯形表 源方程 42 对应于生成行i的割平面 43 L0的最优单纯形表 生成行 对应于生成行i的割平面 非基变量 44 b 010 500 0 51 00 1 75103 255 5 00 10113 10 0 25000 751 5 00 0 500 1 5z 9 对应第2行的割平面 对应第4行的割平面 45 非基变量 46 如何求解 47 s s 0 0 0 fim 1 fim j fin1 fi0 00 0 0 对偶单纯形法 48 割平面计算步骤 第一步 用单纯形法解整数问题IP的松弛问题L0 若L0没有最优解 则IP没有最优解 停止 若L0有最优解X0 1 X0是整数解 则X0也是IP的最优解 停止 2 X0不是整数解 转第二步 第二步 求割平面方程 49 第三步 将割平面加到L0得L1 第四步 解L1 在L0的最优单纯形表中增加一行一列 得L1的单纯形表 用对偶单纯形法求解 若其解是整数解 则该解也是原整数规划的最优解 否则将该解记为X0 返回第二步 50 例用割平面法求解IP 解 IP问题的松弛规划的标准型 X5 000 X5 00 0 125 0 3751 0 75 100013 010 3330 0 6672 00 1 6670 4 667z 34 整数 最优值 Z 34 51 例 用割平面法求解 解 IP的松弛规划的标准型 X5 00 7 22 1 221 1 2 X5 000 1001 7 1 732 7 010013 000 1 8Z 59 非整数 52 1001 7 1 732 7 010013 000 1 8Z 59 X6000 1 7 6 71 4 7 X6 0000 整数 最优值 Z 55 53 作业 分别用分枝定界法和割平面法求解整数规划 最优值为 Z 4 54 第四章整数规划 0 1整数规划 0 1型整数规划是整数规划中的特殊情形 它的变量xi仅取值0或1 这时xi称为0 1变量 或称二进制变量 xi仅取值0或1这个条件可由下述约束条件 xi 1xi 0 整数所代替 和一般整数规划的约束条件形式一致的 第四章整数规划 0 1整数规划 投资场所的选择 相互排斥的计划例 某公司拟在市东 西 南三区建立门市部 拟议中有7个位置 点 Ai i 1 2 7 可供选择 规定在东区 由A1 A2 A3三个点中至多选两个 在西区 由A4 A5两个点中至少选一个 在南区 由A6 A7两个点中至少选一个 如选用Ai点 设备投资估计为bi元 每年可获利润估计为Ci元 但投资总额不能超过B元 问应选择哪几个点可使年利润为最大 第四章整数规划 0 1整数规划 令xi 1 2 7 第四章整数规划 0 1整数规划 1 两个约束中 只有一个起作用 例 a11x1 a12x2 B1a21x1 a22x2 B2 例含有相互排斥的约束条件的问题 解 引入0 1变量Y1 Y2和足够大的正数M 则 a11x1 a12x2 B1 M1Y1a21x1 a22x2 B2 M2Y2Y1 Y2 1 第四章整数规划 0 1整数规划 2 互相排斥的多个约束中 只有一个起作用 ai1x1 ai2x2 ainxn bi i 1 m 互相排斥m个约束 只有一个起作用 3 若a个约束条件中只能有b个起作用 则令0 1变量之和为a b 注意 可用统一M 但M的取值必须足够的大 第四章整数规划 0 1整数规划 1问题的提出 已知 两种货物装箱每种货物装箱利润体积限制重量限制决策变量 两种货物各多少箱MaxZ 利润最大 箱数不能为分数 相互排斥的约束条件 第四章整数规划 0 1整数规划 互相排斥的约束条件 假设有车 船2种运输方式 用车运的体积约束用船运的体积约束 第四章整数规划 0 1整数规划 固定费用的问题在讨论线性规划时 有些问题是要求使成本为最小 那时总设固定成本为常数 并在线性规划的模型中不必明显列出 但有些固定费用 固定成本 的问题不能用一般线性规划来描述 但可改变为混合整数规划来解决 第四章整数规划 0 1整数规划 例固定费用问题 解 设Xj是第j种产品的产量 Yj是0 1变量 表示是 Yj 1 否 Yj 0 生产第j种产品 第四章整数规划 0 1整数规划 第四章整数规划 隐枚举法 在整数规划模型中 若变量取值为0或1两个特殊的数值 则称此类模型为0 1的使用及建立模型的方法 隐枚举法基本思想 隐枚举法是分枝定界法思想的延伸 通过放松主约束条件 而非变量符号限制条件 求得最优解 再检查是否满足约束条件 再经过分枝与剪枝等工作迭代出最优解 第四章整数规划 隐枚举法 在2n个可能的变量组合中 往往只有一部分是可行解 只要发现某个变量组合不满足其中一个约束条件时 就不必再去检验其他约束条件是否可行 对于可行解 其目标函数值也有优劣之分 若已发现一个可行解 则根据它的目标函数值可以产生一个过滤条件 对于目标函数值比它差的变量组合不必再去检验它的可行性 在以后的求解过程中 每当发现比原来更好的可行解 则替换原来的过滤条件 第四章整数规划 隐枚举法 0 1规划求解 MaxZ 3X1 2X2 5X3X1 2X2 X3 2 1 X1 4X2 X3 4 2 X1 X2 3 3 4X2 X3 6 4 X1 X2 X3 0或者1 5 解 观察 X1 X2 X3 1 0 0 满足约束 1 5 相应Z 3增加一个约束 目标值 33X1 2X2 5X3 3 称为过滤条件 FilteringConstraint 第四章整数规划 隐枚举法 于是最优解 X1 X2 X3 1 0 1 MaxZ 8 3X1 2X2 5X3 3 称为过滤条件 FilteringConstraint 第四章整数规划 隐枚举法 MaxZ 2X2 3X1 5X3目标函数按系数递增 2 3 5 约束条件也按上面决定的顺序 2X2 3X1 5X3 3 2X2 X1 X3 2 1 4X2 X1 X3 4 2 X2 X1 3 3 4X2 X3 6 4 X1 X2 X3 0或者1 5 解 变量 X1 X2 X3 按下面顺序容易更早发现最优解 0 0 0 0 0 1 0 1 0 0 1 1 改进过滤条件 用 3X1 2X2 5X3 5 为过滤条件 这里已经更换了x1 x2的位置 x2 x1 x3 再改进过滤条件 用 3X1 2X2 5X3 8 为过滤条件 这里已经更换了x1 x2的位置 x2 x1 x3 MaxZ 2X2 3X1 5X3目标函数按系数递增 2 3 5 约束条件也按上面决定的顺序 2X2 3X1 5X3 3 2X2 X1 X3 2 1 4X2 X1 X3 4 2 X2 X1 3 3 4X2 X3 6 4 X1 X2 X3 0或者1 5 解 变量 X1 X2 X3 按下面顺序容易更早发现最优解 1 0 1 对应目标函数系数 3 2 5 负系数的Xi取0 正系数的Xi取1这时目标函数达到最大值 但不一定满足约束条件 如果满足约束条件 则不必检验其他解 一步直达 这里已经更换了x1 x2的位置 第四章整数规划 隐枚举法 在解决0 1规划问题时 为了进一步减少运算量 常按目标函数中各变量系数的大小顺序重新排列各变量 以使最优解有可能较早出现 对于最大化问题 可按目标函数中各变量系数由小到大的顺序排列 对于最小化问题 可按目标函数中各变量系数由大到小的顺序排列 第四章整数规划 隐枚举法 求解0 1整数规划maxf x 3x1 2x2 5x3s t x1 2x2 x3 2x1 4x2 x3 4x1 x2 34x2 x3 6x1 x2 x3 0或1 第四章整数规划 隐枚举法 求解0 1整数规划minf x 3x1 7x2 x3 x4s t 2x1 x2 x3 x4 1x1 x2 6x3 4x4 85x1 3x2 x4 5x1 x2 x3 x4 0或1 设有n个工作 要由n个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的费用 求总费用最低的指派方案 费用 12 j n 12 i n 指派问题模型 i 1 2 n j 1 2 n 第i个人做第j件事 Z表示总费用 i 1 2 n j 1 2 n 第i个人不做第j件事 1 指派问题的数学模型 76 i 1 2 n j 1 2 n 当n 4时 有16变量 8个约束方程 77 例 现有4份工作 4个人应聘 由于各人技术专长不同 他们承担各项工作所需费用如下表所示 且规定每人只能做一项工作 每一项工作只能由一人承担 试求使总费用最小的分派方案 工作 人 费用 1234 1234 3545 6768 89810 1010911 1 0 第i人做第j件事 Z表示总费用 i 1 2 3 4 j 1 2 3 4 第i人不做第j件事 78 2 费用矩阵 设有n个工作 要由n个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的费用 求总费用最低的指派方案 费用 12 j n 12 i n cij表示第i个人做第j件事的费用 费用矩阵 79 例 现有4份工作 4个人应聘 由于个人的技术专长不同 他们承担各项工作所需费用如下表所示 且规定每人只能做一项工作 每一项工作只能由一个人承担 试求使总费用最小的分派方案 工作 人 收费用 1234 1234 3545 6768 89810 1010911 费用矩阵 对应一个5个人5个工作的指派问题 第2个人做第4个工作的费用 5 第4个人做第2个工作的费用 0 80 定理 在费用矩阵C cij 的任一行 列 中减去一个常数或加上一个常数不改变本问题的最优解 n个人n个工作的指派问题1 b 3 匈牙利法 n个人n个工作的指派问题2 81 i 1 2 n j 1 2 n i 1 2 n j 1 2 n b 82 83 b i 1 2 n j 1 2 n i 1 2 n j 1 2 n 84 任务 对C的行和列减去某个常数 将C化的尽可能简单 简单到可一眼看出该问题的最优解 b 85 指派问题的最优解 若C中有n个位于不同行不同列的零元素 则令这些零元素对应的变量取1 其余变量取零 既得指派问题的最优解 i 1 2 3 4 j 1 2 3 4 可行解 最优解 86 匈牙利法的基本思路 对费用矩阵C的行和列减去某个常数 将C化成有n个位于不同行不同列的零元素 令这些零元素对应的变量取1 其余变量取零 即得指派问题的最优解 87 例 有一份说明书要分别译成英 日 德 俄四种文字 现交给甲 乙丙 丁四个人去完成 每人完成一种 由于个人的专长不同 翻译成不同文字所需的时间 小时数 如右表 问应派哪个人去完成哪个任务 可使总花费时间最少 工作 人 时间 英日德俄 甲乙丙丁 215134 1041415 9141613 78119 2 4 9 7 最优方案 甲翻译俄文 乙翻译日文 丙翻译英文 丁翻译德文 总费用 28小时 4 2 88 2 4 9 7 4 2 最优解的取法 从含0元素最少的行或列开始 圈出一个0元素 用 表示 然后划去该 所在的行和列中的其余0元素 用 表示 依次类推 若能得到n个 则得最优解X0 89 例 求费用矩阵为右表的指派问题的最优解 工作 人 费用 ABCDE 甲乙丙丁戊 127979 89666 717121412 15146610 4107106 7 6 7 6 4 得4个 且不存在没打 的0 修改方法 90 对n阶费用矩阵C 若C有n个位于不同行不同列的零元素 即可得最优解X0 否则 对C进行调整 2 2 2 最优指派方案 甲做B工作 乙做C工作 丙做A工作 丁做D工作 戊做E工作 91 当C没有n个位于不同行不同列的零元素时 对C进行调整 第一步 做能复盖所有0元素的最小直线集合 1 对没有 的行打 号 2 对打 号的行上所有0元素的列打 号 3 再对打 号的列上所有 的行打 号 4 重复以上步骤直到得不出新的打 号为止 5 对没有打 号的行画横线 所有打 号的列画纵线 所得到的直线既是复盖所有0元素的最小直线集合 具体步骤 92 第二步 在没有被直线复盖的元素中找出最小元素 让打 号的列加上这个元素 打 号的行减去这个元素 第三步 对所得到的矩阵画 若能得到n个 则得最优解 否则重复以上步骤 直至得到n个 2 2 2 93 例 求费用矩阵为下表的指派问题的最优解 工作 人 费用 ABCDE 甲乙丙丁戊 127979 89666 717121412 15146610 4107106 7 6 7 6 4 2 2 2 最优指派方案 甲做B工作 乙做C工作 丙做A工作 丁做D工作 戊做E工作 32 94 匈牙利法的具体步骤 第一步 变换指派问题的费用矩阵 使其在各行各列都出现0元素 方法 首先每行元素减去该行的最小元素 然后每列减去该列的最小元素 第二步 进行试指派 画 方法 从含0元素最少的行或列开始 圈出一个0元素 用 表示 然后划去该 所在的行和列中的其余0元素 用 表示 依次类推 若矩阵中的 的个数等于n 则得最优解 若矩阵中的 的个数 n 则进行第三步 95 第三步 做能覆盖所有0元素的最小直线集合 1 对没有 的行打 号 2 对打 号的行上所有0元素的列打 号 3 再对打 号的列上所有 的行打 号 4 重复以上步骤直到得不出新的打 号为止 5 对没有打 号的行画横线 所有打 号的列画纵线 所得到的直线既是复盖所有0元素的最小直线集合 第四步 在没有被直线复盖的元素中找出最小元素 让打 号的列加上这个元素 打 号的行减去这个元素 转第一步 96 例 现有4份工作 4个人应聘 由于个人的技术专长不同 他们承担各项工作所需费用如下表所示 且规定每人只能做一项工作 每一项工作只能由一个人承担 试求使总费用最小的分派方案 工作 人 收费用 1234 1234 15182124 19232218 26171619 19212317 最优方案 第一个人做第一件事 第二个人做第四件事 第三个人做第三件事 第四个人做第二件事 总费用 70 97 98 4 一般的指派问题 1 求maxZ的指派问题 2 人数与工作数不等的指派问题 3 一个人可做几件事的指派问题 4 某事一定由 不能由 某人做的指派问题 99 收益 12 j n 12 i n 指派问题模型 i 1 2 n j 1 2 n 第i个人做第j人件事 Z表示总收益 i 1 2 n j 1 2 n 第i个人不做第j人件事 设有n个工作 要由n个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的收益 求总收益最大的指派方案 1 求maxZ的指派问题 100 工作 人 收益 12 j n 12 i n 指派问题最大化的数学模型 i 1 2 n j 1 2 n 指派问题最小化的数学模型 i 1 2 n j 1 2 n 用匈牙利法 101 i 1 2 n j 1 2 n i 1 2 n j 1 2 n 102 对maxZ的指派问题 工作 人 收益 12 j n 12 i n 用匈牙利法求C 103 例 现有4份工作 4个人应聘 由于个人的技术专长不同 他们承担各项工作的效益如下表所示 且规定每人只能做一项工作 每一项工作只能由一个人承担 试求使总效益最大的分派方案 工作 人 收益 1234 12797 7171214 151466 410710 1234 分派方案 第1个人第3项工作 第2个人第2项工作 第3个人第1项工作 第4个人第4项工作 总效益 9 17 15 10 51 104 2 人数与工作数不等的指派问题 设有n个工作 要由m个人来承担 每个工作只能由一个人承担 且每个人只能承担一个工作 cij表示第i个人做第j件事的费用 求总费用最低的指派方案 a m n 工作 人 费用 12 j n 12 i m n 1n 2 m 用匈牙利法求解 105 例 现有4份