管理运筹学 第四章整数规划与指派问题PPT课件.ppt

第四章整数规划与指派问题 2017年4月 北京物资学院运筹学课件 线性规划的决策变量取值可以是任意非负实数 但许多实际问题中 只有当决策变量的取值为整数时才有意义 例如 产品的件数 机器的台数 装货的车数 完成工作的人数等 分数或小数解显然是不合理的 要求全部或部分决策变量的取值为整数的线性规划问题 称为整数线性规划 简称整数规划 IntegerProgramming 第一节整数线性规划问题的数学模型第二节整数规划的求解方法 第三节指派问题及匈牙利解法 本章内容的安排 第一节整数线性规划问题的数学模型 引例逻辑变量在整数规划建模中的作用整数规划问题的特征与性质整数规划模型的分类 例1 装载问题 有一辆卡车的最大载重量为b吨 现有n种货物可供装载 设第j种货物每件重aj吨 每件的装载费用为cj元 j 1 n 问应该采用怎样的装载方案才能使卡车一次装载货物的收入最大 解 设xj为卡车装载第j种货物的件数 j 1 2 n z表示卡车一次装载的收入 则该问题的数学模型为maxz c1x1 c2x2 cnxns t a1x1 a2x2 anxn bxj 0且为整数 j 1 2 n 1 引例 例2 选址问题 相互排斥的计划 某公司准备投资100万元在甲 乙两座城市修建健身中心 经过多方考察 最后选定A1 A2 A3 A4和A5五个位置 并且决定在甲城市的A1 A2 A3三个位置中最多投建两个 在乙城市的A4 A5两个位置中最少投建一个 如果已知各点的投资金额和年利润如下表 问 健身中心投建在哪些位置才会使总的年利润最大 解 设 则该问题的数学模型为 例3工厂选址问题 某商品有n个销地 各销地的需求量为bj吨 天 现拟在m个地点中选址建生产厂 一个地点最多只能建一个工厂 若选i地建厂 生产能力为ai吨 天 固定费用为di元 天 已知i地至第j销地的单位运费为cij元 吨 问如何选址和安排调运 才能使总费用最小 设 yi 1 表示选择第i地建厂 yi 0 表示不选择第i地建厂 从厂址i至销地j运量为xij 总费用为z 该问题的数学模型为 例4某公司制造小 中 大3种尺寸的金属容器 所用的资源为金属板 劳动力和机时 制造一只容器所需的各种资源数量如下表所示 不考虑固定费用 每售出一只小 中 大号容器所得的利润分别为4元 5元 6元 可使用的金属板有500张 劳动力有300个 机时有100小时 如果生产某种容器 不管生产数量多少 都要支付一笔固定费用 小 中 大号容器的固定费用分别为100元 150元 200元 现要制订一生产计划 使获得的利润最大 解 设x1 x2 x3分别表示小 中 大号容器的生产数量 M为很大的正数 z表示总利润 引入逻辑变量 若xj 0时 yj 0 若xj 0时 yj 1 2 逻辑变量在整数规划建模中的作用 1 m个约束条件中只有k个起作用 定义 则上述条件可以表示成 2 约束条件的右端可能是r个值中的某一个 定义 则上述条件可以表示成 3 两组条件中满足其中的一组 定义 则问题可以表示为 4用以表示含固定费用的函数 总费用 目标函数是总费用最小 定义 则目标函数可以表示成 3 整数规划问题的特征与性质 特征 变量整数性要求来源问题本身的要求引入的逻辑变量的需要性质 可行域是离散集合 4 整数规划的分类 纯整数规划要求全部决策变量的取值都为整数 则称为纯整数规划 AllIP 混合整数规划仅要求部分决策变量的取值为整数 则称为混合整数规划 MixedIP 0 1整数规划要求决策变量只能取0或1值 则称为0 1规划 0 1Programming 第二节整数规划的求解方法 分支定界法割平面法 1 分支定界法 整数规划ILP 放松的线性规划LP 分枝定界法是本世纪60年代初由LandDoig和Dakin等人提出的 可用于解纯整数规划或混合整数规划 整数规划问题的最优目标函数等值线 放松问题的最优目标函数等值线 整数规划的最优解不一定在顶点上达到 整数规划的最优解不一定是放松问题最优解的邻近整数解 整数可行解的个数远多于顶点个数 枚举法不可取 整数规划ILP和放松问题LP的关系ILP的可行区域是LP的可行区域的子集 如果LP无可行解 则ILP无可行解 LP的最优值是ILP的最优值的一个上界 若LP的最优解为整数向量 则它也是ILP的最优解 整数规划ILP 放松的线性规划LP 分枝定界法的基本思想 先求放松的LP的最优解 若放松LP问题无解 则原ILP问题也无解 若放松LP问题的最优解符合整数要求 则是原ILP的最优解 若放松LP问题的最优解含非整数分量 则将ILP问题分为几个子问题 试图做到 要么找到某个子问题的最优解 要么判断原问题ILP的最优解一定不在子问题的可行区域内 分枝定界法的算法流程 解LP 无可行解 问题无界 ILP无解或无界 解x0为整数向量 x0为ILP的解 x0有非整分量 将原问题分解为两个子问题 使得非整分量恰好排除在外而又没有去掉原问题的可行解 再分别判断两个子问题 如果最优解xi中某个分量非整 分枝定界法的两个要点 分枝和定界 如何分枝 分枝定界法的两个要点 分枝和定界 如何定界 整数规划ILP的最优解不会优于松弛LP的最优解 对极大化问题来说 松弛LP的目标函数最优值是原整数规划ILP目标函数值的上界 如果当前的ILP最好的整数解的目标函数值不小于某一子问题的目标函数值 则可剪枝 例5 求解下列整数线性规划问题 解 先求与之对应的线性规划问题 放松问题 18 11 40 11 z0 218 11 B 1 3 z1 16C 2 10 3 z2 56 3 分枝x1 1 x1 2 LP0 的解不是 ILP0 的解 LP0 z0 218 11x1 18 11 x2 40 11 LP1 z1 16x1 1 x2 3 LP2 z2 18 66x1 2 x2 10 3 x1 1 x1 2 LP1有整数解 已探明 剪枝 定下界z1 16LP2 z2 18 66 z1 16 可能有比z1更优的解分枝 在LP2中加入x2 3x2 4分成 LP3 LP4 LP3 maxz x1 5x2s t x1 x2 25x1 6x2 302 x1 4x2 3x1 0 x2 0 LP4 maxz x1 5x2s t x1 x2 25x1 6x2 302 x1 4x2 4x1 0 x2 0 LP0 z0 218 11x1 18 11 x2 40 11 LP1 z1 16x1 1 x2 3 LP2 z2 18 66x1 2 x2 10 3 x1 1 x1 2 LP3 z3 17 4x1 2 4 x2 3 LP4无可行解 LP5 z5 17x1 2 x2 3 LP6 z6 15 5x1 3 x2 5 2 分枝的方法 定界的方法 当前得到的最好整数解的目标函数值分枝后计算放松的线性规划的最优解 整数解 非整数解 目标值大于原有最好的目标值 替代原有目标值目标值小于原有最好的目标值 删除该分枝 目标值大于原有最好的目标值 继续分支目标值小于等于原有最好的目标值 删除该分枝 2 割平面解法 ILP LP0 割平面法的基本思想 如果放松问题 LP0 无解 则 ILP 无解 如果 LP0 的最优解为整数向量 则也是 ILP 的最优解 如果 LP0 的解含有非整数分量 则对 LP0 增加割平面条件 即对 LP0 增加一个线性约束 将 LP0 的可行区域割掉一块 使得非整数解恰好在割掉的一块中 但又没有割掉原问题 ILP 的可行解 得到问题 LP1 重复上述的过程 割平面法的算法流程 解LP0 无可行解 问题无界 ILP无解或无界 解x0为整数向量 x0为ILP的解 x0有非整分量 对LP0增加线性约束将LP0的可行区域割掉一块 使得x0在割掉的区域中 而原问题ILP的任意可行解都没有割去 得到LP1 例6 求解下列整数规划问题 1 去掉整数约束 得到松弛问题 化成标准形 初始单纯形表 最终单纯形表 最优解 3 4 7 4 不是整数向量 需要引入割平面以得到改进的松弛问题 如何引入割平面 由最终的单纯形表得到变量间的关系 将系数和常数项分解成整数和非负真分数之和 移项得 由于x1 x2是整数 由原问题可知 x3 x4也是整数 因此 上式左端必为整数 右端 内是正数 所以等式右端必为非正数 即 切割方程 引入松弛变量x5 得到等式 将这个新的约束加到最优单纯形表中 得到 用对偶单纯形法迭代得 割平面方程等价于 即 可见 割平面就是结合松弛问题的最优表和原问题的整数约束 而增加的线性约束 割平面割掉了包含非整数解的一块可行区域 但没有割掉任何整数格点 求割平面的步骤 把线性规划最优解中取值为非整数的基变量找出来 将该基变量在最优单纯形表中对应的约束的常数和变量系数分解成整数和非负真分数之和 提出变量为整数的条件构成切割方程 第三节指派问题及匈牙利解法 问题的提出及数学模型匈牙利解法两点说明指派问题的求解软件 1 问题的提出及数学模型 例7 设某工程有B1 B2 B3 B4四项任务 需由四个工人A1 A2 A3 A4去完成 由于任务性质和每个工人的技术水平不相同 他们完成各项任务所需的时间也不一样 见下表 问应当如何指派 即哪个人去完成哪项任务 才能使完成四项任务的总时间最少 设 该问题的解为 用矩阵形式表示为 解矩阵 设有n项任务 需有n个人去完成 每个人只能完成一项任务 每项任务只能由一个人去完成 设第i人完成第j项任务需要的时间是aij 问如何指派才能使完成任务的总时间最少 设 一般指派问题 指派问题是一种特殊的运输问题 特殊在哪里 高度退化 因而一般不使用表上作业法求解 2 匈牙利解法 定义1效率矩阵 其中aij 0表示第i人完成第j项任务的效率 时间 费用等 定义2任务的一种分配方法称为一个匹配 指派问题的一个解 使目标函数取得最小值的匹配称为最优匹配 最优解 特点 每行恰有一个1 每列恰有一个1 匈牙利方法的基本思想 如果效率矩阵的所有元素aij 0 而其中存在一组位于不同行不同列的0元素 则只要令对应于这些位置的xij 1 其余xij 0 就可以得到指派问题的最优解 效率矩阵 最优解 问题 如何产生这组独立0元素 定义3位于效率矩阵的不同行不同列的0元素称为独立0元素 定理1 如果从效率矩阵A的每一行元素中分别减去 或加上 一个常数ui 从每一列元素中分别减去 或加上 一个常数vj 得到一个新的效率矩阵B 其中bij aij ui vj 则B对应的指派问题与A对应的指派问题同解 定理2效率矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数 独立0元最多两个 至少需用两条直线覆盖所有0元素 证明 将B中的数据代入目标函数 有 匈牙利解法的基本步骤 第一步 初始变换获得0元素 从效率矩阵的每行减去该行的最小元素 然后从所得矩阵的每列减去该列的最小元素 令所得矩阵为B 第二步 在B中寻找位于不同行 不同列的0元素 1 检查B的每行每列 从中找出未加标记的0元素最少的一排 即行列的统称 在该排用 标出一个0元 若该排有多个0元 则任意标出一个即可 2 把刚得到 号标记的0元所在的行 列中的其余0元划去 用 表示 3 凡是 0 就成为加了标记的0元 返回 1 重复 1 2 3 直到所有0元都加上标记为止 若得到的加 号的0元素个数等于n 则结束 否则转第三步 第三步 找出能覆盖矩阵中所有0元素的最少直线集合 1 对没有 0 的行打 2 对已经打 的行中所有 元素所在的列打 3 再对打 的列中所有 0 元素所在的行打 4 重复 2 3 直到得不出新的打 的行 列为至 5 对没有打 的行和打 的列划线 即为覆盖所有0元素的最少直线 第四步 修改矩阵B以增加独立0元素的个数 1 在未被直线覆盖的所有元素中 找出最小元素 2 所有打 的行都减去此最小元素 然后所有打 的列都加上此最小元素 令这个新矩阵为B 返回第二步 例8 用匈牙利解法解例7 效率矩阵 第一步 初始变换 得解矩阵 找独立0元素 总时间为 4 4 9 11 28 例3 用匈牙利解法解下列指派问题 效率矩阵 第一步 初始变换 第二步 寻找独立0元素 最小元素为min 10 5 7 2 6 3 6 5 2 2 2 2 它有5个独立0元 得到最优解相应的解矩阵为 最优目标值 7 6 9 6 4 32 课堂练习 求解下列指派问题 效率矩阵 1 1 1 第一组最优解 第二组最优解 两点说明 1 效率矩阵不是方阵的情况 即人员与工作数不相等 处理方法 增加虚拟人或工作 使两者相等 虚拟人或工作对应的效率矩阵中元素为0 2 最大化指派问题的处理 如果给出的效率矩阵中的数字表示每个人完成各项任务的收益 则问题变成了如何指派任务才能使总收益最大 处理方法 用效率矩阵中的最大元减去矩阵中的各个元素得到一个新的矩阵 对这个新的矩阵用匈牙利方法求解 例9 有四项工作分配给六个人去完成 每个人分别完成各项工作的时间如下表所示 仍然规定每个人只能完成一项工作 每项工作只交给一个人去完成 问挑选哪四个人去完成工作 花费的总时间最少 例10指派甲 乙 丙 丁四个人去完成A B C D E五项任务 每个人完成各项任务的时间如下表 由于任务数多于人数 故考虑 1 任务E必须完成 其他4项中任选3项完成 2 其中有一人完成两项 其他每人