第五章 整数规划

第五章整数规划 在求解线性规划问题时 得到的最优解可能是分数或小数 但许多实际问题要求得到的解为整数才行 这种要求线性规划有整数解的问题 称为整数规划 IntegerProgramming 或简称IP 第一节整数规划的数学模型及解的特点 引例 某厂拟用火车装运甲 乙两种货物集装箱 每箱的体积 重量 可获利润以及装运所受限制如下 货物集装箱体积 米3 重量 百斤 利润 百元 甲5220乙4510托运限制2413问两种货物各装运多少箱 可使获得利润最大 是不是可通过把不考虑整数要求求得的最优解经过 化整 得到满足整数要求的最优解呢 它和线性规划问题的区别在于条件 5 此例可解得x1 4 8 x2 0 凑整为x1 5 x2 0 这就破坏了条件 2 因而不是可行解 如截断小数变为x1 4 x2 0 这当然满足所有约束条件 但不是最优解 因为对x1 4 x2 0有z 80 而对x1 4 x2 1 也是可行解 有z 90 因此要专门研究整数规划的解法 整数规划的数学模型 若要求所有xj的解为整数 称为纯整数规划若要求部分xj的解为整数 称为混合整数规划对应没有整数解要求的线性规划称之为松弛问题整数规划的解是可数个的 最优解不一定发生在极点整数规划的最优解不会优于其松弛问题的最优解 第二节分支定界法 分枝定界法是20世纪60年代由Land Doig和Dakin等人提出的 这种方法既可用于纯整数规划问题 也可用于混合整数规划问题 而且便于用计算机求解 所以很快成为解整数规划的最主要的方法 1 用观察法求R的一个可行解 其目标值便是R的最优目标值z 的一个下界z 2 求解R0 得R0的最优解x 0 和最优值z0 若x 0 符合R的整数条件 则显然x 0 也是R的最优解 结束 否则 以R0作为一个分枝标明求解的结果 z0是问题R的最优目标值z 的一个上界z 3 分枝 取目标函数值最大的一个枝Rs 在Rs的解中任选一不符合整数条件的变量xj 其值为bj 构造两个约束条件xj bj 和xj bj 1 将两个约束条件分别加入问题Rs 得两个后继规划问题Rs1和Rs2 不考虑整数条件求解这两个后继问题 以每个后继问题为一分枝标明求解的结果 分支定界法的步骤 4 定界 在各分枝中找出目标函数值最大者作为新的上界z 从已符合整数要求的各分枝中 找出目标函数值最大者作为新的下界z 5 比较与剪枝 各分枝的最优目标函数值中如果有小于z者 则剪掉这一枝 用打 表示 即以后不再考虑了 若已没有大于z的分枝 则已得到R的最优解 结束 否则 转 3 下面看一具体的例题 R0 z0 356x1 4 81x2 1 82 R1 z1 349x1 4 00 x2 2 10 R2 z2 341x1 5 00 x2 1 57 R12 z12 327x1 1 42x2 3 00 x2 3 R11 z11 340 x1 4 00 x2 2 00 R21 z21 308x1 5 44x2 1 00 R22 无可行解 x1 4 x1 1 x1 5 x1 2 问题R0为 Maxz 40 x1 90 x29x1 7x2 567x1 20 x2 70 x1 x2 0 问题R2为 Maxz 40 x1 90 x29x1 7x2 567x1 20 x2 70 x1 5x1 x2 0 问题R1为 Maxz 40 x1 90 x29x1 7x2 567x1 20 x2 70 x1 4x1 x2 0 x2 2 问题R11为 Maxz 40 x1 90 x29x1 7x2 567x1 20 x2 70 x1 4x2 2x1 x2 0 问题R12为 Maxz 40 x1 90 x29x1 7x2 567x1 20 x2 70 x1 4x2 3x1 x2 0 第三节0 1整数规划 0 1型整数规划是整数规划的一种特殊形式 它的变量xj仅取值0或1 这种只能取0或1的变量称为0 1变量或二进制变量 下面通过过一个例子说明一下 例 某公司拟在市东 西 南三区建立门市部 拟议中有7个位置Ai i 1 2 7 可供选择 规定 1 在东区A1 A2 A3三个点中至多选两个 2 在西区A4 A5两个点中至少选一个 3 在南区A6 A7两个点中至少选一个 如选用Ai点 设备投资估计为bi元 每年可获利润估计为ci元 但投资总额不超过B元 问应选择哪几个点可使年利润为最大 建立模型如下所示 Maxz c1x1 c2x2 c7x7 b1x1 b2x2 b7x7 B x1 x2 x3 2 x4 x5 1 x6 x7 1 xi 0或1 i 1 2 7 于是建立下列模型 例求解0 1型整数规划问题Maxz 8x1 2x2 4x3 7x4 5x53x1 3x2 x3 2x4 3x5 45x1 3x2 2x3 x4 x5 4xj 0或1 j 1 2 5 变成标准型 要求如下 目标函数求极大化 对于目标函数为Minz的极小化问题 令z z 使其变为目标函数为Maxz 的极大化问题 目标函数中所有变量的系数都为正数 如果目标函数中变量xj的系数为负数 令xj 1 xj 把模型中的xj用xj 代换 变量的排列顺序按变量在目标函数中的系数值从小到大排列 求解0 1型整数规划 可使用分枝定界法 下面用实例说明 x2 x3 x5 x4 x1 1 z 10 不可行 z 6 不可行 z 5 不可行 z 3 不可行 z 2 不可行 x2 0 x1 0 z 4 可行 x3 0 x3 0 z 8 不可行 x5 0 x5 0 z 1 z 2 x4 0 x4 0 最优解为x2 0 x3 0 x5 1 x4 1 x1 1 于是 原问题的最优解为z 4 x1 1 x2 0 x3 1 0 1 x4 1 1 0 x5 1 1 0 令x3 1 x3 x4 1 x4 x5 1 x5 得Maxz 2x2 4x3 5x5 7x4 8x1 163x2 x3 3x5 2x4 3x1 2 3x2 2x3 x5 x4 5x1 6 x2 x3 x5 x4 x1 0或1 第四节指派问题 指派问题的标准形式及其数学模型匈牙利解法求解指派问题一般的指派问题 有n项任务 恰好n个人承担 第i人完成第j项任务的花费 时间或费用等 为cij 如何指派使总花费最省 一 指派问题的标准形式及其数学模型 指派问题的系数矩阵如下 Cij的含义可以不同 如费用 成本 时间等 系数矩阵C中 第i行中各元素表示第i人做各事的费用 第j列各元素表示第j事由各人做的费用 为建立标准指派问题的数学模型 引入n n个0 1变量 指派问题的数学模型可写成如下页形式 若派第i人做第j事0若不派第i人做第j事 ij 1 2 n 第j项工作由一个人做 第i人做一项工作 指派问题的每个可行解 可用矩阵表示如下 矩阵X中 每行各元素中只有1个元素为1 其余各元素等0 每列各元素中也只有1个元素为1 其余各元素等0 指派问题有n 个可行解 例1有一份中文说明书 需译成英 日 德 俄四种文字 分别记作E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成不同语种的说明书所需时间如下表 问应指派何人去完成何工作 使所需总时间最少 指派问题的数学模型如下 已知条件可用系数矩阵 效率矩阵 表示为 其可行解也可用每行仅有一个1 每列也仅有一个1的矩阵表示 如 匈牙利解法的关键是利用了指派问题最优解的如下性质 若从指派问题的系数矩阵C的某行 或某列 各元素分别减去一个常数k 得到一个新的矩阵C 则以C 和C为系数矩阵的两个指派问题有相同的最优解 系数矩阵的变化并不影响数学模型的约束方程组 而只是目标函数值减少了常数k 所以最优解不变 二 匈牙利法解题步骤 1955年 库恩利用匈牙利数学家康尼格的关于矩阵中独立零元素的定理 提出了解指派问题的一种算法 称为匈牙利解法 2 4 9 7 若某行 列 已有0元素 那就不必再减了 例1的计算为 1 使系数矩阵各行 各列出现零元素作法 系数矩阵各行元素减去所在行的最小元素 再从所得矩阵的各列减去所在列最小元素 因一行中xij取值一个1 其余为0 cij同时减去一常数不影响xij取值 匈牙利法解题步骤如下 4 2 这就保证每行每列至少有一个0元素 同时不出现负元素 2 试求最优解 如能找出n个位于不同行不同列的零元素 令对应的xij 1 其余xij 0 得最优解 结束 否则下一步 例2 求表中所示效率矩阵的指派问题的最小解 经行运算即可得每行每列都有0元素的系数矩阵 再按上述步骤运算 得到 3 作能覆盖所有0元素的最少直线数的直线集合 1 对没有的行打 号 2 对已打 号的行中所有0元素的所在列打 号 3 再对打有 号的列中0元素的所在行打 号 4 重复 2 3 直到得不出新的打 号的行 列 为止 5 对没有打 号的行画一横线 对打 号的列画一纵线 这就得到覆盖所有0元素的最少直线数 4 未被直线覆盖的最小元素为cij 在未被直线覆盖处减去cij 在直线交叉处加上cij Cij 2 解为 从系数矩阵C中 找出最大元素m 用m减去矩阵C中所有元素得以系数矩阵B 则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同最优解 1 最大化指派问题 三 一般的指派问题 例4有盈利矩阵C如下 求如何分配盈利最大 解 1 先找出最大元素m 即m 16 减去C中所有元素得 2 用求目标函数最小值的方法求解 略 若人数少事