《运筹学整数规划》PPT课件.ppt

第五章整数规划IntegerProgramming 第五章整数规划 第1节整数规划的数学模型及解的特点第2节分支定界法第3节0 1型整数规划第4节指派问题 第1节整数规划的数学模型及解的特点 一 整数规划的含义要求一部分或全部决策变量必须取整数值的规划问题 第1节整数规划的数学模型及解的特点 整数规划的松弛问题不考虑整数条件 由余下的目标函数和约束条件构成的规划问题 若松弛问题是一个线性规划 则称该整数规划为整数线性规划 第1节整数规划的数学模型及解的特点 整数线性规划的数学模型 第1节整数规划的数学模型及解的特点 整数线性规划问题的类型 1 纯 全 整数线性规划 全部决策变量都必须取整数值的整数线性规划 2 混合整数线性规划 决策变量中有一部分必须取整数值 另一部分可以不取整数值的整数线性规划 3 0 1型整数线性规划 决策变量只能取值0或1的整数线性规划 第1节整数规划的数学模型及解的特点 例1 某服务部门各时段 每2h为一时段 需要的服务员人数见下表 按规定 服务员连续工作8h 即四个时段 为一班 现要求安排服务员的工作时间 使服务部门服务员总数最少 第1节整数规划的数学模型及解的特点 例1 解 设在第j时段开始时上班的服务员人数为xj 第1节整数规划的数学模型及解的特点 二 整数规划的解的特点整数规划问题的可行域是它的松弛问题可行域的子集整数规划问题的可行解是它的松弛问题的可行解整数规划问题最优解的目标函数值不优于它的松弛问题最优解的目标函数值 第1节整数规划的数学模型及解的特点 三 整数规划的解法例2 某宝石加工厂最近新到6粒大小 质量等级相似的钻石毛料 管理层有两种选择 一是切磨成一般的皇冠形 每粒可获利2 5千元 一是切磨成虽然较难切磨但当前市场较流行的心形 每粒可获利4千元 若切磨成皇冠形则每粒需要5个工作日 若切磨成心形则每粒需要9个工作日 由于工厂切工师傅较忙 最多只有45个工作日来做这批工作 另外 由于毛料自身形状的关系 其中只有4粒毛料可以切磨成皇冠形 而6粒毛料中任何一粒都可以切磨成心形 那么 管理层应如何决策才能使这批钻石获利最大 第1节整数规划的数学模型及解的特点 例2 解 设x1 x2分别为切磨成皇冠形和切磨成心形的钻石粒数maxz 2 5x1 4x2x1 x2 65x1 9x2 45x1 4x1 x2 0 x1 x2整数 第1节整数规划的数学模型及解的特点 完全枚举法对于可行域有界的整数规划问题 整数规划的可行解是一个有限集 将这个集内的每一个点对应的目标函数值都一一计算出来 然后从中找出最优者 则为整数规划的最优解 第1节整数规划的数学模型及解的特点 例3 用完全枚举法求解下述整数规划问题 maxz x1 4x2 2x1 3x2 3x1 2x2 8x1 x2 0 x1 x2整数 第1节整数规划的数学模型及解的特点 小结 1 对整数规划问题的松弛问题的最优解中不符合整数要求的分量进行简单地取整 所得到的整数解可能不一定是整数规划问题的最优解 甚至也不一定是整数规划问题的可行解 2 对于复杂的模型 完全枚举法费时 甚至不可能实现 第2节分支定界法 一 分支定界法的思路分支定界法是先求解整数规划的松弛问题 如果其最优解不符合整数条件 则用增加约束的办法求出整数规划问题的上下界 并把松弛问题的可行域分成互不重叠的子区域 再求解这些子区域的松弛问题 不断缩小整数规划问题上下界的差距 最后取得整数规划问题的最优解 第2节分支定界法 二 分支定界法的含义分支定界法是一种部分枚举法 通过不断地分割松弛问题的可行域并进行比较 最终求得整数规划问题的最优解 第2节分支定界法 三 分支定界法的步骤第一步 求解松弛问题 1 松弛问题无可行解 则整数规划问题无可行解 计算停止 2 松弛问题有最优解 并且符合整数规划问题的整数条件 则松弛问题的最优解就是整数规划问题的最优解 计算停止 3 松弛问题有最优解 但是不符合整数规划问题的整数条件 则松弛问题的最优值是整数规划问题最优值的上界值 求极大时 或下界值 求极小时 下界值 求极大时 可暂定为 或上界值 求极小时 可暂定为 第2节分支定界法 第二步 分支 在松弛问题的最优解中任选一个不符合整数条件的变量xi 其值为bi 用 bi 表示小于bi的最大整数 构造以下两个约束条件 将这两个约束条件分别加入整数规划问题 形成两个子问题 再求解这两个子问题的松弛问题 第2节分支定界法 第三步 定界 以每个子问题的松弛问题为一分支标明求解的结果 与其他问题的解的结果相比较 1 若解满足子问题的整数条件 则找到了一个整数规划问题的可行解 为新的下界值 求极大时 或上界值 求极小时 若计算中同时出现两个及以上整数规划问题可行解 则选取其中最大 求极大时 或最小 求极下时 的一个保留 2 若解不满足子问题的整数条件 则为新的上界值 求极大时 或下界值 求极下时 若所有子问题的最优解都不是整数规划问题可行解 则选取边界值最大 求极大时 或最小 求极下时 的子问题进一步再细分子问题 并求解 第2节分支定界法 第四步 比较与剪支 各分支的目标函数值中 若小于下界值 求极大时 或大于上界值 求极小时 则剪去该分支 用打 表示 若大于下界值 求极大时 或小于上界值 求极小时 且不符合整数条件 则回到第二步 对该分支继续分支 若除保留下来的可行解外 其余分支都被剪去 则该可行解是整数规划问题的最优解 第2节分支定界法 例4 用分支定界法求解例3 第2节分支定界法 例5 用分支定界法求解下述整数规划问题 maxz 3x1 2x22x1 3x2 14x1 0 5x2 4 5x1 x2 0 x1 x2整数 第2节分支定界法 小结分支定界法 仅检查可行的整数组合的一部分 从而定出最优整数解 作业13 作业13 用分支定界法求解例2 作业13答案 第3节0 1型整数规划 一 0 1型变量的含义变量只能取值0或1 第3节0 1型整数规划 二 0 1型变量的特点表示是或否表示系统是否处于某个特定状态表示决策时是否取某个特定方案当问题含有多项要素 每项要素都有两种选择表示二进制变量 第3节0 1型整数规划 例 令 第3节0 1型整数规划 例 设问题有有限项要素E1 E2 En 其中每项Ej有两种选择Aj和 j 1 2 n 令 第3节0 1型整数规划 例 变量x可取0与9之间的任意整数 令 第3节0 1型整数规划 例6 现有资金总额为B 可供选择的投资项目有7个 项目j所需投资额和预期收益分别为aj和cj j 1 2 7 此外 由于种种原因 有三个附加条件 第一 若选择项目1 就必须同时选择项目2 反之 则不一定 第二 项目3和4中至少选择一个 第三 项目5 6和7中恰好选择两个 应当怎样选择投资项目 才能使总预期收益最大 第3节0 1型整数规划 例6 解 第3节0 1型整数规划 例7 工厂A1和A2生产某种物资 由于该种物资供不应求 故需要再建一家工厂 相应的建厂方案有A3和A4两个 这种物资的需求地有B1 B2 B3 B4四个 各工厂年生产能力 各地年需求量 各厂至各需求地的单位物资运费cij i j 1 2 3 4 见下表 工厂A3或A4开工后 每年的生产费用估计分别为1200万元或1500万元 现要决定应该建设工厂A3还是A4 才能使今后每年的总费用 即全部物资运费和新工厂生产费用之和 最少 第3节0 1型整数规划 例7 解 第3节0 1型整数规划 三 0 1型整数规划的解法1 完全枚举法定义 含有n个变量 产生2n个可能的变量组合 每一个组合即变量取值为0或1 比较目标函数值确定最优解特点 适于变量个数n 10的0 1型整数规划 第3节0 1型整数规划 2 部分枚举法定义 只检查2n个可能的变量组合的一部分 确定问题的最优解 第3节0 1型整数规划 解题思路 1 某个变量组合不满足其中一个约束条件时 就不必再去检验其他约束条件是否可行 2 确定一个可行解的目标函数值 对于目标函数值比它差的变量组合就不必再去检验它的可行性 对于目标函数值比它好的变量组合再去检验它的可行性 第3节0 1型整数规划 解题步骤第一 按目标函数中各变量系数的大小顺序排列各变量 然后把约束条件做相应的调整 第二 在表中列出变量取值的全部组合 2n个 并分别计算各自的目标函数值 第三 以第一个可行解计算得出的目标函数值作为一个过滤条件 比较表中其它目标函数值与该过滤条件 比它差的变量取值组合舍弃 比它好的变量取值组合保留 并检验约束条件 同时以其计算得出的目标函数值作为新的过滤条件替换上一个过滤条件 重复这个过程 直至所有变量取值组合的目标函数值都比较完成 从而得到最优解 第3节0 1型整数规划 要求 用部分枚举法求解下列0 1型整数规划 例8 maxz 3x1 2x2 5x3x1 2x2 x3 2x1 4x2 x3 4x1 x2 34x1 x3 6x1 x2 x3 0或1 第3节0 1型整数规划 例8 解 maxz 2x2 3x1 5x32x2 x1 x3 24x2 x1 x3 4x2 x1 34x1 x3 6x1 x2 x3 0或1 第3节0 1型整数规划 例9 minz 2x1 5x2 3x3 4x4 4x1 x2 x3 x4 0 2x1 4x2 2x3 4x4 4x1 x2 x3 x4 1x1 x2 x3 x4 0或1 第3节0 1型整数规划 例9 解 minz 5x2 4x4 3x3 2x1x2 x4 x3 4x1 04x2 4x4 2x3 2x1 4x2 x4 x3 x1 1x1 x2 x3 x4 0或1 第3节0 1型整数规划 小结采用部分枚举法求解0 1型整数规划 可以减少计算次数 使最优解能较快地被发现 第4节指派问题 一 指派问题的标准形式含义 将n项工作交给n个人去做 由于每个人做每一项工作所用的时间等成本不同 指派问题的目标是如何安排工作 使总的时间等成本最小 标准形式 有n个人和n件事 已知第i人做第j事的费用为cij i j 1 2 n 要求确定人和事之间的一一对应的指派方案 使完成这n件事的总费用最少 基本要求 在满足特定的指派要求条件下 使指派方案的总体效果最佳 第4节指派问题 二 指派问题的假设条件执行工作的人数和要完成的工作数量是相同的每个人只能做一件工作每件工作只能由一个人来完成第i i 1 2 n 个人完成第j j 1 2 n 项工作所需的成本是cij目标是如何分配工作 使总的成本最小 第4节指派问题 例10 有一份中文说明书 需译成英 日 德 俄四种文字 分别记作E J G R 现有甲 乙 丙 丁四人 他们将中文说明书翻译成不同语种的说明书所需时间如下表所示 问应指派何人去完成何工作 使所需总时间最少 第4节指派问题 例10 解 第4节指派问题 三 指派问题的数学模型系数矩阵 C cij n n 1 矩阵C表示费用 成本 时间等 2 元素cij表示指派第i人去完成第j项任务时的费用 或时间 成本等 第4节指派问题 数学模型 第4节指派问题 解矩阵 X xij n n 1 矩阵每行各元素中都有且只有一个1 表示每个人必做且只做一件事 2 矩阵每列各元素中都有且只有一个1 表示每件事必有且只有一个人去做 3 有n 个可行解 第4节指派问题 数学模型的特点 1 特殊的0 1型整数规划问题 2 特殊的运输问题 第4节指派问题 四 指派问题的解题方法 匈牙利法解题思路 1 若从指派问题的系数矩阵 cij 的某行 或某列 各元素分别减去一个常数k 得到一个新的矩阵 cij 则以 cij 和 cij 为系数矩阵的两个指派问题有相同的最优解 2 独立0元素 位于不同行不同列的0元素 3 若在系数矩阵中找到n个独立0元素 则对应的指派方案总费用 或时间 成本等 为零 即为原指派问题的最优解 第4节指派问题 匈牙利法的解题步骤1 变换系数矩阵 具体做法 1 从系数矩阵的每行元素减去该行的最小元素 2 再从所得的系数矩阵的每列元素减去该列的最小元素 变换后 指派问题的系数矩阵中每行及每列都出现0元素 同时不出现负元素 得新的系数矩阵 第4节指派问题 2 在变换后的系数矩阵中确定独立0元素 具体做法 1 从只有1个0元素的行开始 给这个0元素加圈 记作 然后划去 所在列的其它0元素 记作 2 给只有1个0元素的列的0元素加圈 记作 然后划去 所在行的其它0元素 记作 3 重复1 2 直到所有0元素都被圈出或划掉为止 元素即为独立0元素 4 若 元素有n个 则已得最优解 若 元素少于n 则转入3 最优解矩阵 独立0元素对应位置上的元素为1 其他元素为0 第4节指派问题 例10 解 最优解为z 28 第4节指派问题 3 用最少的直线覆盖所有0元素 以确定该系数矩阵中能找出最多的独立0元素 具体作法 1 对没有 元素的行打 号 2 对已打 号的行中所有 元素所在的列打 号 3 再对打 号的列中所有 元素所在的行打 号 4 重复2 3 直到得不出新的打 号的行和列为止 5 对没有打 号的行划一横线 对已打 号的列划一竖线 得到覆盖所有0元素的最少直线数 6 若直线数少于n 则转入4 若直线数等于n 而 元素少于n 则回到2 另行试指派 矩阵中独立0元素的定理 系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数 第4节指派问题 4 继续变换系数矩阵 具体作法 1 在没有被直线覆盖的元素中找出最小元素 2 打 号的行的各元素减去最小元素 3 打 号的列的各元素加上最小元素 4 得新的系数矩阵 重复2 若找出n个独立0元素 则得最优解 否则返回3 重复3 4 第4节指派问题 例11 求下表所示系数矩阵的指派问题的最小解 第4节指派问题 例11 解 多重最优解 为z 32 第4节指派问题 小结 1 当指派问题的系数矩阵经过变换 遇到在所有的行和列中 0元素都不止一个时 可任选其中一个0元素加圈 并同时划去同行和同列中其他0元素 其最优解为多重最优解 2 匈牙利法充分利用指派问题的特殊性质 有效地减少计算量 第4节指派问题 例12 某商业公司计划开办五家新商店 为了尽早建成营业 商业公司决定由5家建筑公司分别承建 已知建筑公司Ai i 1 2 5 对新商店Bj j 1 2 5 的建造费用的报价 万元 为cij i j 1 2 5 如下表所示 商业公司应当对5家建筑公司怎样分配建造任务 才能使总的建造费用最少 第4节指派问题 例12 解 最优解为z 34 第3节指派问题 五 非标准形式的指派问题处理方法 将非标准形式转化为标准形式 然后应用匈牙利法求解 第3节指派问题 最大化指派问题设最大化指派问题系数矩阵C cij n n 令矩阵B bij n n M cij n n 其中M是足够大的正数 通常选M max cij 则以B为系数矩阵的最小化指派问题和以C为系数矩阵的最大化指派问题有相同最优解 第3节指派问题 例13 某建筑公司所属五个工程队 现有五项工程需要该公司承包 考虑各方面原因 规定每个工程队只能包其中一项工程 由于各队施工质量和技术水平的差异 其承包后各队的报酬不同 如下表所示 试问如何分配任务 使得该建筑公司获得最好的经济效益 第3节指派问题 例13 解 转化为求极小化问题 系数矩阵为 第3节指派问题 最优解为z 60 第3节指派问题 人数和事数不等的指派问题若人少事多 则添上一些虚拟的 人 虚拟的 人 做各事的费用cij取 0 表示这些费用实际上不会发生 若人多事少 则添上一些虚拟的 事 虚拟的 事 被各人做的费用cij仍取 0 第3节指派问题 例14 求下列系数矩阵的最小化指派问题 第3节指派问题 例14 解 转化为平衡指派问题 系数矩阵为 第3节指派问题 最优解为z 22 第3节指派问题 某事一定不能由某人做的指派问题若某事一定不能由某个人做 则将相应的费用cij取 M M是足够大的正数 第3节指派问题 例15 分配甲 乙 丙 丁四个人去完成A B C D E五项任务 每个人完成各项任务的时间如下表所示 由于任务数多于人数 故考虑任务E必须完成 其他4项中可任选3项完成 试确定最优分配方案 使完成任务的总时间最少 第3节指派问题 例15 解 转化为平衡指派问题 系数矩阵为 第3节指派问题 最优解为z 105 第3节指派问题 例16 6个人完成4项工作任务 由于个人的技术专长不同 他们完成4项工作任务所获得的收益如下表所示 且规定每人只能做一项工作 一项工作只需1人操作 试求使总收益最大的分派方案 第3节指派问题 例16 解 转化为平衡指派