6.整数0-1规划4.10.ppt

整数规划 人们探讨某些线性规划问题 有时必须把全部或部分决策变量限制为整数 这样的线性规划问题 通常称为整数规划 作为线性规划的特殊情况 整数规划也有最小化和最大化之别 此外 整数规划还可以分成纯整数规划和混整数规划 二者的区别在于 前者的决策变量必定全部取整数 而后者的决策变量只是部分取整数 一 整数规划的一般形式 1 实例 例1某厂拟用集装箱托运甲乙两种货物 每箱的体积 重量 可获利润以及托运所受限制如表5 1 问两种货物各托运多少箱 可使获得的利润为最大 解 设托运甲 乙两种货物x1 x2箱 用数学式可表示为 例2做图分析例1的最优解 直观 x1 x2 4 8 4 0 Z 96 1 2 3 5 6 7 3 1 2 5x1 4x2 24 2x1 5x2 13 C 4 8 0 Z 90 最优解 B 4 1 Z 80 1 求解方法方面 3 与LP问题的区别 在例1中 此IP问题的最优解 值 为 LP问题的最优解 值 为 要求一部分或全部决策变量必须取整数值的规划问题称为整数规划在整数规划中去掉取整数的约束 剩下的目标函数和约束条件构成的规划问题称为该整数规划的松弛问题若整数规划的松弛问题是线性规划 则称该整数规划为整数线性规划 二 整数规划的一般模型 整数线性规划的数学模型 松弛问题 整数线性规划问题解的特点 整数规划的可行解集合是它的松弛问题可行解集合的一个子集 即整数规划的可行解一定是其松弛问题的可行解 反之不然 整数规划问题的最优目标函数值不会优于其松弛问题最优解的目标函数值若松弛问题的可行解满足整数约束 则它也是整数规划的可行解整数规划问题的最优解不能由其松弛问题最优解经过简单取整得到 松弛问题最优解 整数规划最优解 不能通过舍入取整地方法 由松弛问题的解得到整数规划的最优解 整数线性规划的几种类型 纯整数线性规划混合整数线性规划0 1型整数线性规划 0 1型整数规划 0 1变量 只能取值0或1的变量 0 1变量也称为逻辑变量 它常用来表示两个选项中非此即彼的选择 如P是一个方案 则 类似 设A1 A2 A3是三个方案 则可以用 x1 x2 x3 0 1 1 表示采用方案A2 A3但不用方案A1 x1 x2 x3 1 0 1 表示采用方案A1 A3但不用方案A2 再比如x1 x2 x3 1表示方案A1 A2 A3中恰好采用一个x1 x2 x3 2表示方案A1 A2 A3中最多采用两个x1 x2 x3 2表示方案A1 A2 A3中至少采用两个x1 x3表示如果采用方案A3 则必采用方案A1 0 1整数规划的一般形式 例8某公司拟在市东 西 南三区建立门市部 拟议中有7个位置 点 Ai供选择 规定在东区 由A1 A2 A3三个点中至多选两个 在西区 由A4 A5两个点中至少选一个 在南区 由A6 A7两个点中至少选一个 如选用Ai点 设备投资估计为bi元 每年可获利润估计为ci元 但投资总额不能超过B元 问应选择那几个点可使年利润为最大 则0 1规划模型为 2 0 1整数规划的一般形式 0 1型整数规划问题的解法 枚举法 列出变量取值为0或1的可能的组合 若有n个变量则有2n个组合 再逐一验证它们是否满足约束条件 然后对满足约束条件的可行解计算目标函数值 其中目标函数值最优的就是最优解方法的改进 通过设置过滤条件有效地减少验证组合为可行解的次数 二 隐枚举法求解0 1整数规划的思路 3 不断更换过滤条件 1 把目标函数的系数按升序排列 max 约束条件做相应调整 2 把所有的解x按一定的次序排列 例 用隐枚举法求解下列0 1规划问题 解 目标函数的系数按升序排列 通过试探可行解 x1 x2 x3 1 0 0 引入下列过滤条件 改进过滤条件 改进过滤条件 0 0 0 0 0 1 0 5 YYYY YYYY 0 1 0 2 YYYY 0 1 1 3 YNYY 1 0 0 3 YYYY 1 0 1 8 YYYY 1 1 0 1 YNYY 1 1 1 6 YNYY z 0 z 5 z 8 例 在暑假期间 某同学准备徒步回家探亲 他把要带的物品装进包后 觉得还能多放5个单位重量的东西 为此 他列出了拟放物品的清单 见下表 他认为 应使所增加的物品总价值为最大 基于以上的考虑 他到底还要带哪些东西呢 物品重量 价值表 解设 y为所增加的物品总价值 于是该问题的数学模型为 指派问题 指派问题的标准形式 有n个人和n件事 已知第i个人做第j件事的费用为cij i j 1 2 n 要求确定人和事之间的一一指派方案 使完成这n件事的总费用最小 标准形式的特点 每个人必须承担也仅承担一项任务 每项任务必须有人承担承担任务的人数与任务数相同目标函数最小化对何人做何事没有限制 指派问题数学模型 若引入如下的0 1型变量 则数学模型为 每个人必须承担也只能承担一项工作 每项工作必须指派给一人也只能指派给一人 明显地不同的n阶指派问题 有相同的可行解 但最优解可能不同 区别在于它们目标函数的系数不同 称指派问题的目标函数系数构成的矩阵为系数矩阵 指派问题的解可以用矩阵表示 若矩阵X是指派问题的一个可行解 则它的每一行恰好有一个元素等于1其余元素为零 每一列也恰好有一个元素等于1其余元素为零 因此指派问题有n 个可行解 例 系数矩阵 系数矩阵的性质 系数矩阵C cij 的某行 列 各元素分别减去一个常数k 得到一个新的矩阵C c ij 则以C 和C为系数矩阵的两个指派问题有相同的最优解 匈牙利解法 1 变换系数矩阵 使变换后的矩阵各行各列出现零元素 47666 01300 减去每行最小者 减去每列最小者 匈牙利解法 2 确定独立的零元素 若独立零元素的个数小于矩阵的阶数 转下一步 否则按独立零元素进行指派 对有唯一零元素的行 列 将零元素圈起来 再划去其所在列 行 的其他零元素 匈牙利解法 3 用最少的直线覆盖所有的零元素 对没有独立零元素的行打 在已打 行中 选择划去零元素的列打 在已打 列中 选择圈住了的零元素的行打 用线条覆盖没打 的行和已打 的列 匈牙利解法 4 继续变换矩阵 使其中出现新的零元素 选择没有被覆盖的元素中最小的元素 没有