型整数规划ppt课件.ppt

第四节0 1整数规划 决策变量只能取0或1的整数规划 叫做0 1整数规划 决策变量称为0 1变量 二进制变量 逻辑变量 0 1变量作为逻辑变量 常被用来表示系统是否处于某个特定状态 或者决策时是否取某个特定方案 一 什么是0 1整数规划 第四节0 1整数规划 1 投资场所的选定 相互排斥的计划例 某公司拟在市东 西 南三区建立门市部 拟议中有7个位置Ai i 1 2 7 可供选择 规定在东区 由A1 A2 A3三个点中至多选两个 在西区 由A4 A5两个点中至少选一个 在南区 由A6 A7两个点中至少选一个 如选用Ai点 设备投资估计为bi元 每年可获利润估计为ci元 但投资总额不能超过B元 问应选择哪个点可使年利润最大 0 1规划的实际问题 建模如下 st 2 相互排斥的约束条件 如果有m个互相排斥的约束条件 型 为了保证这个约束条件只有一个起作用 我们引入m个0 1变量和一个充分大的常数M 而下面这一组m 1个约束条件 符合要求 第四节0 1整数规划 2 相互排斥的约束条件例 本章例1中 关于货运的体积限制为5x1 4x2 24 车 今设运货有车运和船运两种方式 上面的条件系用车运时的限制条件 如用船运时关于体积的限制条件为7x1 3x2 45 船 这两条件是互相排斥的 例1 某厂拟用集装箱托运甲 乙两种货物 每箱的体积 重量 可获利润以及托运所受限制如右表所示 问两种货物各托运多少箱 可使获得利润为最大 解 设甲 乙两种货物的托运箱数分别为x1 x2 设变量y表示运货的方式 当y为1时 用车运 y为0时 用船运 1 y M yM 互相排斥的约束条件 用车运的体积约束用船运的体积约束 第五章 0 1整数规划 例 某公司有5个项目列入投资计划 各项目的投资额和期望的投资收益见下表 该公司只有600万元可用于投资 由于技术上的原因 投资受到以下约束 1 在项目1 2和3中必须只有一项被选中 2 在项目3和4中只能选中一项 3 项目5选中的前提是项目1必须被选中 如何在上述条件下选择一个最好的投资方案 是投资收益最大 只有600万元可用于投资 在项目1 2和3中必须只有一项被选中 在项目3和4中只能选中一项 项目5选中的前提是项目1必须被选中 3固定费用问题 例有三种资源被用于生产三种产品 资源量 产品单件可变费用及售价 资源单耗量及组织三种产品生产的固定费用如表 要求制定一个生产计划 使总收益最大 解 设xj是第j种产品的产量 j 1 2 3 再设 若生产第j种产品 即xj 0 若不生产第j种产品 即xj 0 j 1 2 3 则问题的模型为 且为整数 j 1 2 3 j 1 2 3 应用举例 例A东方大学计算机实验室聘用4名大学生 代号1 2 3 4 和2名研究生 代号5 6 值班答疑 已知每人从周一至周五每天最多可安排的值班时间及每人每h值班的报酬如下表 该实验室开放时间是上午8点至晚上10点 开放时间内须有且仅需一名学生值班 规定大学生每周值班不少于8h 研究生每周不少于7h 每名学生每周值班不超过3次 每次值班不少于2h 每天安排值班的学生不超过3人且其中必须有一名研究生 试为该实验室安排一张人员的值班表 使总支付的报酬最少 解 设xij为学生i在周j的值班时间 安排学生i在周j值班 否则 用aij代表学生i在周j最多可安排的值班时间 ci为学生i的每h的报酬 则其数学模型为 不超过可安排时间 大学生每周值班不少于8h 研究生每周值班不少于7h 实验室每天开放14h 每名学生一周值班不超过3次 每天值班不超过3人 每天有一名研究生值班 最优结果为总支付报酬每周727 5元值班方案为 例B清远市下设八个区 下表给出救护车从一个区至另一个区的车程时间 min 该市拟建救护中心 要求各区离救护中心的车程时间必须在8min之内 是为该市提供决策建议 至少建多少个救护中心 建于何处 解 先根据表整理出若救护中心建于该区时 救护车程8min内所能覆盖的区 见于下表 设 该区设救护中心 否则 列出数学模型如下 求解的结果为x1 1 x6 1 即至少在1 6两个区各设一救护中心 第四节0 1整数规划 二 0 1整数规划的解法 隐枚举法 只检查变量取值的组合的一部分的方法 0 0 0 0 Z 0 0 0 1 5 Z 5 0 1 0 2 0 1 1 3 1 0 0 3 Z 8 1 0 1 1 1 0 8 1 1 1 1 6 按目标函数中各变量系数的大小重新排列各变量最大化问题 由小到大最小化问题 由大到小 解法二 重新排列xj的顺序 系数递减 0 1型整数规划计算表 目标函数z 3x1 2x2 5x3 5x3 3x1 2x2最大值的上限是8 第二大的值是5 5x3 3x1 2x2 8 隐枚举法 共计算5次 均满足约束条件 最优解为1 0 1 最优值8 可根据计算逐渐改变过滤条件 该例因最大值的点满足其他四个约束 即找到最大化问题的最好的整数解 就不需验证计算第二大值的点是否满足约束条件 例 求解下面的0 1型整数规划 解 按递增序列排列 因为xi取0或1 最小下界点为 0 0 0 z值为0 其次为 0 0 1 点 z值为2 0 1 0 点 z值为3 0 1型整数规划计算表 最优解为 0 0 1 最优值为 2 最小值0对应的点不满足 约束 改变过滤条件 再验证计算次小值2对应的点满足 约束 即找到最小化问题的最好的整数解 逐渐改变过滤条件 第五节指派问题 一 什么是指派问题 某单位需完成任务n项任务 恰好有n个人可承担这些任务 由于每人的专长不同 各人完成不同任务效率也不同 于是产生应指派哪个人去完成哪项任务 使完成n项任务的总效率最高 这类问题称为指派问题 分派问题 分配问题 人 任务 cij表示第i个人完成第j项任务的效率 第五节指派问题 二 指派问题的数学模型 Cij 人 任务 解 设 例 某单位现在 四项工作需完成 现在甲 乙 丙 丁四个人均可完成这四项任务 每人完成各项任务所用的时间如右表所示 问应指派何人去完成何项任务 使所需时间最少 A B C D 任务 人员 满足所有约束条件的可行解xij也可写成表格或矩阵形式 称为解矩阵 xij 就是上例的一个可行解矩阵 第五节指派问题 cij 第五节指派问题 指派问题数学模型的性质 若从指派问题的系数的系数矩阵 cij 的一行 列 各元素中分别减去该行 列 的最小元素 得到新矩阵 bij 那么以 bij 为系数矩阵求得的最优解和用原系数矩阵求得的最优解相同 独立的0元素 位于不同行不同列的0元素称为独立的0元素 结论 若能在系数矩阵 bij 中找出n个独立的0元素 则令解矩阵 xij 中对应这n个独立的0元素取值为1 其它元素取值为0 将其代入目标函数中得到zk 0 它一定是最小 这就是以 bij 为系数矩阵的指派问题的最优解 也就得到了问题的最优解 第五节指派问题 三 指派问题的解法 匈牙利法 第一步 使指派问题的系数矩阵经变换 在各行各列都出现 元素 从系数矩阵的每行元素减去该行的最小元素 再从所得系数矩阵的每列元素中减去该列的最小元素 min min 经第一步变换后 系数矩阵中每行每列都已有了0元素 只需找出n个独立的0元素 若能找出 就以这些独立的0元素对应解矩阵中的元素为1 其作为0 这就得到最优解 找独立0元素的步骤如下 第二步 进行试指派 以寻求最优解 第五节指派问题 3 反复 1 2 两步 直到所有0元素都被圈出和划掉为止 4 若各行各列均有多于2个的0元素未被圈出或划掉 中任选其中任意一个0元素加圈 5 若 元素的数目m等于矩阵的阶数n 那么指派问题的最优解已得到 若m n 则转入下一步 min 第五节指派问题 第五节指派问题 第三步 作最少的直线覆盖所有0元素 以确定该系数矩阵中能找到最多的独立0元素数 5 对没有打 号的行画一横线 有打 号的列画一纵线 这就得到覆盖所有0元素的最少直线 1 对没有 的行打 号 2 对已打 号的行中所有含划0元素的列打 号 3 再对打有 号的列中含 元素的行打 号 4 重复 2 3 直到得不出新的打 号的行 列为止 第五节指派问题 第四步 对第三步所得矩阵进行变换 目的是增加0元素 在没有被直线覆盖的部分中找出最小元素 然后在打 行各元素中都减去该最小元素 而在打 列的各元素都加上该最小元素 以保证原来的0元素不变 这样得到新系数矩阵 重复第二步 独立0元素的个数等于效率矩阵的阶数 得到了最优解 最优解矩阵为 第五节指派问题 练习 有4个工人 要指派他们分别完成4项工作 每人做各项工作所消耗的时间如下表 工作 工人 解 用匈牙利法求解过程如下 min min 1 第五节指派问题 第五节指派问题 四 非标准形式的指派问题 1 最大化指派问题2 人数和事数不等的指派问题3 一个人可做几件事的指派问题4 某事一定不能由某人做的指派问题 第五节指派问题 1 求最大化的指派问题 令bij M cij其中 M是足够大的常数 cij中最大元素 用匈牙利法求解 bij 即可 所得最小解就是原问题的最大解 第五节指派问题 2 人数和任务数不等的指派问题 若人少任务多 则添上一些虚拟的 人 这些虚拟的 人 完成各任务的费用系数可取0 理解为这些费用实际上不会发生 若人多任务少 则添上一些虚拟的 任务 这些虚拟的 任务 由各人完成的费用系数同样也取0 第五节指派问题 3 一个人可以完成几项任务的指派问题 若某个人可完成几项任务 则可将人化作相同的几个 人 来接受指派 这几个 人 完成同一项任务的费用系数都一样 4 某项任务一定不能由某人完成的指派问题 若某项任务一定不能由某个人完成 则可将相应的费用系数取作足够大的数M 例 分配甲 乙 丙 丁四个人去完成五项任务 每人完成各项任务时间如下表所示 由于任务数多于人数 故规定其中有一个人可兼完成两项任务 其余三人每人完成一项 试确定总花费时间为最少的指派方案 第五节指派问题 第六节应用举例 1 m约束条件中只有k个起作用 设m个约束条件可表示为 定义 又M为任意大的正数 得 第六节应用举例 定义 第六节应用举例 3 两组条件中满足其中一组 若x1 4 则x2 1 否则 即x1 4 x2 3 又M为任意大正数 则问题可表达为 第六节应用举例 4 用以表示固定费用的函数 生产费用函数 引入变量yj 复习题 一 判断下列说法是否正确 1 整数规划的目标函数值一般优于其相应的线性规划问题 松弛问题 的解的目标函数值 2 用分枝定界法求解一个极大化的整数规划问题时 任何一个可行解的目标函数值是该问题目标函数值的下界 3 用分枝定界法求解一个极大化的整数规划问题 当得到多于一个可行解时 通常可任取其中一个作为下界值 再进行比较 剪枝 4 用割平面法求解整数规划时 构造的割平面有可能切去一些不属于最优解的整数解 复习题 一 判断下列说法是否正确 5 用割平面法求解纯整数规划时 要求包括松弛变量在内的全部变量必须取整数