Ch3整数规划ppt课件.ppt

3 1整数规划数学模型MathematicalModelofIP3 2纯整数规划的求解SolvingPureIntegerProgramming3 30 1规划的求解SolvingBinaryIntegerProgramming Chapter3整数规划IntegerProgramming 运筹学OperationsResearch 3 1整数规划数学模型MathematicalModelofIP 2020年4月7日星期二 一个规划问题中要求部分或全部决策变量是整数 则这个规划称为整数规划 当要求全部变量取整数值的 称为纯整数规划 只要求一部分变量取整数值的 称为混合整数规划 如果模型是线性的 称为整数线性规划 本章只讨论整数线性规划 很多实际规划问题都属于整数规划问题 1 变量是人数 机器设备台数或产品件数等都要求是整数2 对某一个项目要不要投资的决策问题 可选用一个逻辑变量x 当x 1表示投资 x 0表示不投资 3 人员的合理安排问题 当变量xij 1表示安排第i人去做j工作 xij 0表示不安排第i人去做j工作 逻辑变量也是只允许取整数值的一类变量 3 1整数规划的数学模型MathematicalModelofIP 2020年4月7日星期二 例3 1 某人有一背包可以装10公斤重 0 025m3的物品 他准备用来装甲 乙两种物品 每件物品的重量 体积和价值如表3 1所示 问两种物品各装多少件 所装物品的总价值最大 表3 1 解 设甲 乙两种物品各装x1 x2件 则数学模型为 3 1 3 1整数规划的数学模型MathematicalModelofIP 2020年4月7日星期二 如果不考虑x1 x2取整数的约束 称为 3 1 的松弛问题 线性规划的可行域如图3 1中的阴影部分所示 3 1整数规划的数学模型MathematicalModelofIP 图3 1 2020年4月7日星期二 用图解法求得点B为最优解 X 3 57 7 14 Z 35 7 由于x1 x2必须取整数值 实际上整数规划问题的可行解集只是图中可行域内的那些整数点 用凑整法来解时需要比较四种组合 但 4 7 4 8 3 8 都不是可行解 3 7 虽属可行解 但代入目标函数得Z 33 并非最优 实际上问题的最优解是 5 5 Z 35 即两种物品各装5件 总价值35元 由图3 1知 点 5 5 不是可行域的顶点 直接用图解法或单纯形法都无法求出整数规划问题的最优解 因此求解整数规划问题的最优解需要采用其它特殊方法 还有些问题用线性规划数学模型无法描述 但可以通过设置逻辑变量建立起整数规划的数学模型 3 1整数规划的数学模型MathematicalModelofIP 2020年4月7日星期二 例3 2 在例3 1中 假设此人还有一只旅行箱 最大载重量为12公斤 其体积是0 02m3 背包和旅行箱只能选择其一 建立下列几种情形的数学模型 使所装物品价值最大 1 所装物品不变 2 如果选择旅行箱 则只能装载丙和丁两种物品 价值分别是4和3 载重量和体积的约束为 解 此问题可以建立两个整数规划模型 但用一个模型描述更简单 引入0 1变量 或称逻辑变量 yi 令 i 1 2分别是采用背包及旅行箱装载 3 1整数规划的数学模型MathematicalModelofIP 2020年4月7日星期二 1 由于所装物品不变 式 3 1 约束左边不变 整数规划数学模型为 2 由于不同载体所装物品不一样 数学模型为 3 1整数规划的数学模型MathematicalModelofIP 2020年4月7日星期二 式中M为充分大的正数 从上式可知 当使用背包时 y1 1 y2 0 式 b 和 d 是多余的 当使用旅行箱时 y1 0 y2 1 式 a 和 c 是多余的 上式也可以令 同样可以讨论对于有m个条件互相排斥 有m m m 个条件起作用的情形 3 1整数规划的数学模型MathematicalModelofIP 2020年4月7日星期二 1 右端常数是k个值中的一个时 类似式 3 2 的约束条件为 2 对于m组条件中有k m 组起作用时 类似式 3 3 的约束条件写成 这里yi 1表示第i组约束不起作用 如y1 1式 3 3b 3 3d 不起作用 yi 0表示第i个约束起作用 当约束条件是 符号时右端常数项应为 3 对于m个条件中有k m 个起作用时 约束条件写成 3 1整数规划的数学模型MathematicalModelofIP 2020年4月7日星期二 例3 3 试引入0 1变量将下列各题分别表达为一般线性约束条件 1 x1 x2 6或4x1 6x2 10或2x1 4x2 20 2 若x1 5 则x2 0 否则x2 8 3 x2取值0 1 3 5 7 解 1 3个约束只有1个起作用 3 1整数规划的数学模型MathematicalModelofIP 或 2020年4月7日星期二 3 右端常数是5个值中的1个 3 1整数规划的数学模型MathematicalModelofIP 2 两组约束只有一组起作用 2020年4月7日星期二 例3 4 企业计划生产4000件某种产品 该产品可自己加工 外协加工任意一种形式生产 已知每种生产的固定费用 生产该产品的单件成本以及每种生产形式的最大加工数量 件 限制如表3 2所示 怎样安排产品的加工使总成本最小 表3 2 解 设xj为采用第j j 1 2 3 种方式生产的产品数量 生产费用为 3 1整数规划的数学模型MathematicalModelofIP 2020年4月7日星期二 式中kj是固定成本 cj是单位产品成本 设0 1变量yj 令 数学模型为 3 1整数规划的数学模型MathematicalModelofIP 3 4 式 3 4 中是处理xj与yj一对变量之间逻辑关系的特殊约束 当xj 0时yj 1 当xj 0时 为使Z最小化 有yj 0 例3 4是混合整数规划问题 用WinQSB软件求解得到 X 0 2000 2000 T Y 0 1 1 T Z 25400 2020年4月7日星期二 作业 教材P751 2 3 4 5 6 1 线性整数规划模型的特征2 什么是纯 混合 整数规划3 0 1规划模型的应用 3 1整数规划的数学模型MathematicalModelofIP 下一节 纯整数规划的求解 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 分枝定界法的步骤 1 求整数规划的松弛问题最优解 2 若松弛问题的最优解满足整数要求 得到整数规划的最优解 否则转下一步 3 任意选一个非整数解的变量xi 在松弛问题中加上约束xi xi 及xi xi 1组成两个新的松弛问题 称为分枝 新的松弛问题具有特征 当原问题是求最大值时 目标值是分枝问题的上界 当原问题是求最小值时 目标值是分枝问题的下界 4 检查所有分枝的解及目标函数值 若某分枝的解是整数并且目标函数值大于 max 等于其它分枝的目标值 则将其它分枝剪去不再计算 若还存在非整数解并且目标值大于 max 整数解的目标值 需要继续分枝 再检查 直到得到最优解 3 2 1求解纯整数规划的分枝定界法 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 例3 5 用分枝定界法求解例5 1 解 先求对应的松弛问题 记为LP0 用图解法得到最优解X 3 57 7 14 Z0 35 7 如下图所示 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 8 33 10 松弛问题LP0的最优解X 3 57 7 14 Z0 35 7 x1 x2 o A B C 10 3 2纯整数规划的求解SolvingPureIntegerProgramming 10 10 x1 x2 o A B C LP1 LP2 3 4 LP1 X 3 7 6 Z1 34 8 LP2 X 4 6 5 Z2 35 5 10 10 x1 x2 o A B C LP1 LP3 3 4 LP3 X 4 33 6 Z3 35 33 6 LP1 X 3 7 6 Z1 34 8 10 10 x1 x2 o A C LP1 3 4 6 LP4 X 4 6 Z4 34 LP5 X 5 5 Z5 35 5 LP1 X 3 7 6 Z1 34 8 LP3 LP5 尽管LP1的解中x1不为整数 但Z5 Z因此LP5的最优解就是原整数规划的最优解 上述分枝过程可用下图表示 LP0 X 3 57 7 14 Z0 35 7 LP1 X 3 7 6 Z1 34 8 LP2 X 4 6 5 Z2 35 5 x1 3 x1 4 LP3 X 4 33 6 Z3 35 33 x2 6 LP4 X 4 6 Z4 34 LP5 X 5 5 Z5 35 x1 4 x1 5 无可行解 x2 7 2020年4月7日星期二 设纯整数规划 松弛问题 的最优解 设xi不为整数 3 2 2求解IP的割平面法 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 将分离成一个整数与一个非负真分数之和 则有 等式两边都为整数并且有 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 加入松弛变量si得 此式称为以xi行为源行 来源行 的割平面 或分数切割式 或R E Gomory 高莫雷 约束方程 将Gomory约束加入到松弛问题的最优表中 用对偶单纯形法计算 若最优解中还有非整数解 再继续切割 直到全部为整数解 则 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 例如 x1行 移项 令 加入松弛变量s1得 同理 对于x2行有 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 例3 6 用割平面法求解下列IP问题 解 放宽变量约束 对应的松弛问题是 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 加入松弛变量x3及x4后 用单纯形法求解 得到最优表3 3 最优解X 0 5 2 15 4 不是IP的最优解 选择表3 3的第一行 也可以选第二行 为源行 3 2纯整数规划的求解SolvingPureIntegerProgramming 表3 3 2020年4月7日星期二 分离系数后改写成 加入松弛变量x5得到高莫雷约束方程 将式 3 8 作为约束条件添加到表3 3中 用对偶单纯形法计算 如表3 4所示 3 2纯整数规划的求解SolvingPureIntegerProgramming 2020年4月7日星期二 最优解X 1 3 3 最优值Z 21 所有变量为整数 X 1 就是IP的最优解 如果不是整数解 需要继续切割 重复上述计算过程 3 2纯整数规划的求解SolvingPureIntegerProgramming 表3 4 如果在对偶单纯形法中原切割方程的松弛变量仍为基变量 则此松弛变量所在列化为单位向量后就可以去掉该行该列 再切割 2020年4月7日星期二 作业 教材P76T7 8 1 理解分枝与定界的含义2 选择合适的 枝 生 枝 3 掌握何时停止生 枝 4 领会割平面法的基本原理5 分离源行 求出Gomory约束6 在最优表中增加Gomory约束 用对偶单纯形法迭代 3 2纯整数规划的求解SolvingPureIntegerProgramming 下一节 0 1规划的求解 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 3 3 1求解0 1整数规划的隐枚举法 隐枚举法的步骤 1 找出任意一可行解 目标函数值为Z0 2 原问题求最大值时 则增加一个约束 当求最小值时 上式改为小于等于约束 3 列出所有可能解 对每个可能解先检验式 若满足再检验其它约束 若不满足式 则认为不可行 若所有约束都满足 则认为此解是可行解 求出目标值 4 目标函数值最大 最小 的解就是最优解 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 例3 7 用隐枚举法求解下列BIP问题 解 1 不难看出 当所有变量等于0或1的任意组合时 第一个约束满足 说明第一个约束没有约束力 是多余的 从约束条件中去掉 还能通过观察得到X0 1 0 0 1 是一个可行解 目标值Z0 11是BIP问题的下界 构造一个约束 原BIP问题变为 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 2 列出变量取值0和1的组合 共24 16个 分别代入约束条件判断是否可行 首先判断式 3 9a 是否满足 如果满足 接下来判断其它约束 否则认为不可行 计算过程见表3 7所示 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 表3 5 3 由表3 5知 BIP问题的最优解 X 1 0 1 1 最优值Z 14 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 选择不同的初始可行解 计算量会不一样 一般地 当目标函数求最大值时 首先考虑目标函数系数最大的变量等于1 如例3 8 当目标函数求最小值时 先考虑目标函数系数最大的变量等于0 在表3 7的计算过程中 当目标值等于14时 将其下界11改为14 可以减少计算量 3 3 2分枝 隐枚举法求解BIP问题 将分枝定界法与隐枚举法结合起来用 得到分枝 隐枚举法 计算步骤如下 1 将BIP问题的目标函数的系数化为非负 如 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 当变量作了代换后 约束条件中的变量也相应作代换 3 求主枝 目标函数是max形式时令所有变量等于1 得到目标值的上界 目标函数是min形式时令所有变量等于0 得到目标值的下界 如果主枝的解满足所有约束条件则得到最优解 否则转下一步 4 分枝与定界 从第一个变量开始依次取 1 或 0 求极大值时其后面的变量等于 1 求极小值时其后面的变量等于 0 用分枝定界法搜索可行解和最优解 分枝 隐枚举法是从非可行解中进行分枝搜索可行解 第 1 步到第 3 步用了隐枚举法的思路 第 4 步用了分枝定界法的思路 3 30 1规划的求解SolvingBIP 2 变量重新排序 变量依据目标函数系数值按升排序 2020年4月7日星期二 停止分枝和需要继续分枝的原则 1 当某一子问题是可行解时则停止分枝并保留 2 不是可行解但目标值劣于现有保留分枝的目标值时停止分枝并剪枝 3 后续分枝变量无论取 1 或 0 都不能得到可行解时停止分枝并剪枝 4 当某一子问题不可行但目标值优于现有保留分枝的所有目标值 则要继续分枝 例3 8 用分枝 隐枚举法求解下列BIP问题 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 解 1 目标函数系数全部非负 直接对变量重新排序 2 求主枝 令X 1 1 1 1 得到主枝1 检查约束条件知 3 10c 不满足 则进行分枝 3 令x2 0同时令x3 0及x3 1得到分枝2和分枝3 X2和X3是可行解 分枝停止并保留 如表3 8及图3 8所示 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 表3 8 令x2 1同时令x3 0得到分枝4 X4是可行解 分枝停止并保留 令x2 1 x3 1 x4取 0 和 1 得到分枝5和6 分枝5不可行并且Z5 11小于Z3和Z4 分枝停止并剪枝 注意到分枝6 x4 1时只有x1 0 x1 1就是主枝 X6不可行并且Z6 10小于Z3和Z4 分枝停止并剪枝 分枝过程结束 整个计算过程可用图3 2和表3 8表示 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 搜索到3个可行解 3个目标值中Z3最大 因此X3是最优解 转换到原问题的最优解为X 1 0 1 1 最优值Z 14 计算结束 图3 2 3 30 1规划的求解SolvingBIP 2020年4月7日星期二 例3 9 用分枝 隐枚举法求解下列BIP问题 解 1 令x2 1 x 2及x5 1 x 5 代入模型后整理得 3 30 1规划的求解Solv