运筹学-.整数规划与分配问题.ppt

第四章整数规划与分配问题 对于线性规划问题 最优解可能是分数或小数 但是对于某些问题 会要求解答必须是整数 称为整数解 对于所求解是机器的台数 完成工作的人数 装货的车数 集装箱数量等 对于一些决策变量必须取Boolean值时 如要不要在某地建工厂 可选用一个逻辑变量x 令x 0表示不在该地建厂 x 1表示在该地建厂 这时 分数或小数的解就不合要求 我们称这样的问题为整数规划 例 某厂拟用集装箱托运甲乙两种货物 每箱的体积 重量 可获利润以及托运所受限制如下表 问两种货物各托运多少箱 可使获得的利润为最大 能否先不考虑对变量的整数约束 作为一般线性规划来求解 当解为非整数的时候可以用 四舍五入 或 凑整 方法寻找最优解 对于变量取值很大时 用上述方法得到的解与最优解差别不大 但当变量取值较小时 得到的解就可能与实际整数最优解差别很大 当问题规模较大 决策变量较多 时 用 凑整 方法来算工作量很大 例 某线性规划问题最优解为 x1 x2 4 6 5 5 用凑整法需要比较与上述数据最接近的几种组合 4 5 4 6 5 5 5 6 共四种组合 若问题中有10个整数变量 则解组合达到210 1024个整数组合 且最优解未必在这些组合中 例 求整数规划问题的最优解 解 用图解法得最优解为 3 25 2 5 如果不考虑整数约束 称为整数规划问题的松弛问题 最优解为 4 1 z 14 凑整法求解 比较四个点 4 3 4 2 3 3 3 2 前三个都不是可行解 第四个虽然是可行解 但z 13不是最优解 4 1 主要内容 一 整数规划的特点及作用二 分配问题与匈牙利法三 分枝定界法四 应用举例 第一节整数规划的特点及作用 第四章整数规划及分配问题 一 整数规划的特点及作用1 1整数规划的概念 整数规划 IntegerProgramming 决策变量要求取整数的线性规划 如果所有的决策变量 技术系数和右端项都是非负整数 就称为纯整数规划 如果所有的决策变量都是非负整数 技术系数和右端项为有理数 称为全整数规划 如果仅一部分决策变量为整数 则称为混合整数规划 如果变量取值仅限于0或1 称为0 1整数规划 一 整数规划的特点及作用1 20 1整数规划 某公司拟在市东 西 南三区建立门市部 拟议中有7个位置 点 Ai供选择 规定在东区 由A1 A2 A3三个点中至多选两个 在西区 由A4 A5两个点中至少选一个 在南区 由A6 A7两个点中至少选一个 如选用Ai点 设备投资估计为bi元 每年可获利润估计为ci元 但投资总额不能超过B元 问 应如何选址 可使年利润为最大 一 整数规划的特点及作用1 20 1整数规划 0 1整数规划的一般形式 0 1整数规划一般都是纯整数规划 一 整数规划的特点及作用1 3整数规划的作用 0 1整数规划在管理领域具有重要作用m个约束条件中只有k个起作用 约束条件的右端项可能是r个值 b1 b2 br 中的某一个 两组条件中满足一组 用以表示含固定费用的函数 第二节分配问题与匈牙利法 第四章整数规划及分配问题 二 分配问题与匈牙利法2 1分配问题 1 指派n个人去完成n项任务 使完成n项任务的总效率最高 或所需总时间最少 这类问题称为指派问题或分配问题 安排工作 派工 有n项加工任务 怎样指派到n台机床上完成 有n条航线 怎样指定n艘船去航行的 二 分配问题与匈牙利法2 1分配问题 2 如果完成任务的效率表现为资源消耗 考虑的是如何分配任务使得目标函数极小化 如果完成任务的效率表现为生产效率的高低 则考虑的是如何分配使得目标函数最大化 在分配问题中 利用不同资源完成不同计划活动的效率 通常用表格形式表示为效率表 表格中数字组成效率矩阵 二 分配问题与匈牙利法2 2分配问题实例 1 例 有一份中文说明书 需要译成英 日 德 俄四种文字 现有甲 乙 丙 丁四人 他们将中文说明书译成不同语种的说明书所需时间如下 问应指派何人去完成工作 使所需总时间最少 二 分配问题与匈牙利法2 2分配问题实例 2 效率矩阵用 aij 表示 aij 0 i j 1 2 n 表示指派第j人去完成第i项任务时的效率 时间 成本等 二 分配问题与匈牙利法2 2分配问题实例 3 某项任务只能由1人完成 某人只能完成1项任务 建立整数规划模型 分配问题是0 1整数规划的特例 也是运输问题的特例 n m aj bj 1 二 分配问题与匈牙利法2 3匈牙利法 分配问题可以用单纯形法或运输表求解 库恩 W W Kuhn 于1955年提出了指派问题的解法 他引用了匈牙利数学家康尼格 D K nig 一个关于矩阵中零元素的定理 系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数 这个解法称为匈牙利法 二 分配问题与匈牙利法2 3匈牙利法的基本思想 如果效率矩阵的所有元素aij 0 而其中存在一组位于不同行不同列的零元素 则只要令对应于这些零元素位置的xij 1 其余的xij 0 则所得到的可行解就是问题的最优解 显然令x11 1 x23 1 x32 1 x44 1 即将第一项工作分配给甲 第二项给丙 第三项给乙 第四项给丁 这时完成总工作的时间为最少 如何寻找这组位于不同行不同列的零元素 二 分配问题与匈牙利法2 3匈牙利法的基本定理 定理1如果从分配问题效率矩阵 aij 的每一行元素中分别减去 或加上 一个常数ui 被称为该行的位势 从每一列分别减去 或加上 一个常数vj 被称为该列的位势 得到一个新的效率矩阵 bij 若其中bij aij ui vj 则 bij 的最优解等价于 aij 的最优解 定理2若矩阵A的元素可分为 0 和非 0 两部分 则覆盖 0 元素的最少直线数等于位于不同行不同列的 0 元素的最大个数 二 分配问题与匈牙利法2 4匈牙利法实例 1 第一步 找出每行的最小元素 每行对应减去这个元素 二 分配问题与匈牙利法2 4匈牙利法实例 2 第二步 找出矩阵每列的最小元素 再分别从各列中减去 必定满足 bij aij ui vj 二 分配问题与匈牙利法2 4匈牙利法实例 3 第三步 从第一行开始 若该行只有一个零元素 对零元素打上 括号 表示行所代表的任务已指派 用直线划去其所在列 若该行没有零元素或有两个以上零元素 已划去的不计在内 则转下一行 依次进行到最后一行为止 二 分配问题与匈牙利法2 4匈牙利法实例 4 第三步 从第一列开始 若该列只有一个零元素 对零元素打上 括号 同样不考虑已划去的零元素 再用直线划去其所在行 若该列没有零元素或有两个零元素 则转下一列 依次进行到最后一列为止 二 分配问题与匈牙利法2 4匈牙利法实例 5 效率矩阵每行都有一个打 的零元素 这些零元素都位于不同行不同列 令对应打 零元素的xij 1就得到最优解 矩阵中所有零元素或被划去 或被打上 但打 的零元素少于m个 这时转第四步 打 的零元素小于m 但未被划去的零元素之间存在闭回路 二 分配问题与匈牙利法2 4匈牙利法实例 6 顺着闭回路的走向 对每个间隔的零元素打 然后对所有打 的零元素或所在行或所在列画一条直线 同样得到最优解 二 分配问题与匈牙利法2 4匈牙利法实例 7 第四步 继续按照定理1 对矩阵进行变换 从矩阵未被直线覆盖的数字中找出一个最小的数k 对矩阵的每行 当该行有直线覆盖时 令ui 0 无直线覆盖的 令ui k 对矩阵中有直线覆盖的列 令vj k 对无直线覆盖的列 令vj 0 只有一条直线覆盖的元素保持不变 二 分配问题与匈牙利法2 4匈牙利法实例 8 第五步 回到第三步 迭代运算 直到矩阵的每一行都有一个打 的零元素为止 最优分配方案为 甲译俄文 乙译日文 丙译英文 丁译德文 所需时间为 4 4 9 11 28h 二 分配问题与匈牙利法2 5人数和任务数不相等的分配问题 有四项工作分配给六个人去完成 每个人分别完成各项工作的时间如下 依然规定每个人完成一项工作 每项工作只交给一个人去完成 即六个人中挑选哪四个人去完成 花费时间最少 二 分配问题与匈牙利法2 6目标函数最大化的分配问题 M为充分大的常数 可以得到bij 0 根据定理1 这种转换是等价的 bij aij ui vj aij M 若aij 0 转换后的效率矩阵不符合匈牙利法的条件 第四章整数规划及分配问题作业一 求下面指派问题的最优解 第三节分枝定界法 第四章整数规划及分配问题 三 分枝定界法3 1分枝定界法的基本思想 分枝定界法可用于全部类型的整数规划问题 设有最大化的整数规划问题A 对应的线性规划为问题B 从解问题B开始 若其最优解不符合A的整数条件 那么B的最优目标函数必是A的最优目标函数z 的上界 记作 而A的任意可行解的目标函数值将是z 的下界 分支定界法就是将B的可行域分成子区域 称为分枝 的方法 逐步减小和增大上 下界 最终得到整数规划问题A的z 三 分枝定界法3 2分枝定界法实例 1 求解B 其最优解为x1 3 25 x2 2 5 最优目标函数值为z 14 75 定界 令x1 0 x2 0作为初始整数解 其z 0 因此 分枝 在B的最优解中 任取一个非整数变量 如x2 2 5 因x2的最近邻整数解为x2 2或x2 3 其最优整数解区间只能是x2 3或x2 2 对B分别加上约束条件x2 3和x2 2 可得到两个子问题B1和B2 三 分枝定界法3 2分枝定界法实例 2 定界 用图解法可得B1的最优解为 3 5 2 z1 14 5 B2的最优解为 2 5 3 z2 13 5 没有整数最优解 上界其下界没有整数解 z1 z2 对B1再次分枝 三 分枝定界法3 2分枝定界法实例 3 三 分枝定界法3 2分枝定界法实例 4 再次分枝定界 B11的最优解为 3 2 z11 13 B12的最优解为 4 1 z12 14 这两个最优解都是A的可行解 此时A的上界和下界分别为14 5和14 得最优解 4 1 Z 14 三 分枝定界法3 2分枝定界法 剪枝 x2 2 x2 3 x1 3 x1 4 将各子问题边界值与保留的可行解的值进行比较 把边界值劣于可行解的分支减去 若除保留的可行解外 其他的分支均被减去 则得到最优解 三 分枝定界法3 3分枝定界法的解题思路 分枝定界法实际上是一种利用替代问题的解来逐渐逼近原问题最优解的方法 对替代问题的要求是 容易求解 且原问题的解集应无例外地包含在替代问题的解集中 如果替代问题 松弛 的最优解是原问题的可行解 这个解就是原问题的最优解 否则这个解的值是原问题最优解的上界 求极大时 或下界值 求极小时 三 分枝定界法3 4分枝定界法的解题步骤 1 解松驰问题B B没有可行解 这时A也没有可行解 停止 B有最优解 并符合问题A的整数条件 B的最优解即为A的最优解 停止 B有最优解 但不符合问题A的整数条件 将B的目标函数值为问题A的上界 用观察法找问题A的一个整数可行解 一般可取xj 0 j 1 n 求得其目标函数值 作为A的下界 开始迭代运算 三 分枝定界法3 4分枝定界法的解题步骤 2 分枝与定界 分枝 在B的最优解中任选一个不符合整数条件的变量xj 其值为bj 以 bj 表示小于bj的最大整数 构造两个约束条件xj bj 和xj bj 1 将这两个约束条件 分别加入问题B 求两个后继规划问题B1和B2 求解这两个后继松弛问题 定界 比较所有后继问题的最优解 最大的为A的新上界 从已符合整数条件的各分支中 找出目标函数值为最大者作为新的下界 若无可行解 令下界 0 三 分枝定界法3 4分枝定界法的解题步骤 3 比较与剪枝 各分支的最优目标函数若小于第三步得到的下界 则剪掉此分枝 用打 表示 以后不再考虑 若大于下界 且不符合整数条件 则重复第三步 选取所有边界值最优的分枝进行分枝与定界 一直到最后得到z A的下界为止 此时得到最优解 第四章整数规划及分配问题本章小结 什么是整数规划 什么是0 1整数规划 整数规划的作用什么是分配问题 指派问题 匈牙利法求解一般整数规划的方法分枝定界法