01整数规划分析和总结.docx

0—1 型整数规划模型 0—1 型整数规划模型概述 整数规划指的是决策变量为非负整数值的一类线性规划，在实际问题的应用中，整数规划模型对应着大量的生产计划或活动安排等决策问题，整数规划的解法主要有分枝定界解法及割平面解法（这里不作介绍，感兴趣的读者可参考相关书籍）。在整数规划问题中，0—1 型整数规划则是其中较为特殊的一类情况， 它要求决策变量的取值仅为 0 或 1，在实际问题的讨论中，0—1 型整数规划模型也对应着大量的最优决策的活动与安排讨论，我们将列举一些模型范例，以说明这个事实。 0—1 型整数规划的的数学模型为： 目标函数 Max(Min)z ? c x 1 1 c x 2 2 ? ?? ? c x n n ? a x ? a x ???a x ? (?, ?)b ? a 11x1 ? a 12 x2 ???a1n xn ? (?, ?)b1 ? 21 1 ? ?a x ? a 22 2 x 2n n ???? ???a x 2 ? (?, ?)b ? m1 1 m2 2 mn n m ?x , x , ??, x ? 0 |1 约束条件为： 1 2 n 这里，0 | 1 表示 0 或 1。 0—1 型整数规划模型的解法 0—1 型整数规划模型的解法一般为穷举法或隐枚举法，穷举法指的是对决策变量 x , x 1 2 , ??, x n 的每一个 0 或 1 值，均比较其目标函数值的大小，以从中求出最优解。这种方法一般适用于决策变量个数 n 较小的情况，当 n 较大时，由于 n 个 0、1 的可能组合数为 2 n，故此时即便用计算机进行穷举来求最优解， 也几乎是不可能的。隐枚举法是增加了过滤条件的一类穷举法，该法虽能减少运算次数，但有的问题并不使用。此时，就只能用穷举法了。 应用实例 例 1 工程上马的决策问题 问题的提出 某部门三年内有四项工程可以考虑上马，每项工程的期望收益和年度费用（千元）如下表所示： 假定每一项已选定的工程要在三年内完成，是确定应该上马哪些工程，方能使该部门可能的期望收益最大。 费 用 费 用 工 程 期望收益 第 1 年 第 2 年 第 3 年 1 5 1 8 20 2 4 7 10 40 3 4 3 9 2 20 8 6 10 30 可用资金 18 22 24 模型分析与变量的假设 这是工程上马的决策问题，对任一给定的工程而言，它只有两种可能，要么上马，要么不上马，这两种情况分别对应二进制数中的 1、0，大凡这样的实际背景所对应的工程问题，大都可考虑用 0—1 型整数规划模型建立其相应的模型。 ?x ? ?0, 第j项工程可上马 ( j ? 1, 2, 3, 4, ) ? ?j 1, 第j项工程不上马 ? 设 因每一年的投资不超过所能提供的可用资金数 25 千元，故该 0—1 型整数规划问题的约束条件为： ?5x ? 4x ? 3x ? 8x ? 18 ? 1 2 3 4 ?x ? 7x ? 9x ? 6x ? 22 ? 1 2 3 4 ?8x ? 10x ? 1 2 2x 3 ? 10x 4 ? 24 ??x ? i ? 0 | 1, j ? 1, 2, 3, 4 由于期望收益尽可能大，故目标函数为： max z ? 20x 1 ? 40x 2 ? 20x 3 ? 30x 4 模型的建立与求解 至此，我们得到该问题的 0—1 型整数规划模型为： max z ? 20x 1 ? 40x 2 ? 20x 3 ? 30x 4 ?5x1 ? 4x2 ? 3x3 ? ?8x4 ? 18 (1) ? 1 2 3 4?x ? 7x ? 9x ? 6x ? 1 2 3 4 ? 约束条件为： ?8x1 ? 10x2 ? 2x3 ? 10x4 ? 24 ??xi ? 0 | 1, j ? 1, 2, 3, 4 (3) 下面用隐枚举法求其最优解。易知，该 0—1 型整数规划模型有一可行解（0，0，0，1），它对应的目标函数值为： z ? 30 。自然，该模型的最优解所对应的目标函数值应不小于 30，于是，我们增加一过滤条件 为： 20x 1 ? 40x 2 ? 20x 3 ? 30x 4 ? 30  （4） 在此过滤条件（过滤条件可不唯一）下，用隐枚举法求 0—1 型整数规划模型的最优解的步骤为： 先判断第一枚举点所对应的目标函数值是否满足过滤条件，若不满足，则转下一步；若满足，再判断该枚举点是否满足各约束条件，若有一个约束条件不满足，则转下一步，若均满足，则将该枚举点所对应 的 目 标 函 数 值 z （ 本 例 中 ， z ? 30 ） 作 为 新 的 目 标 值 ， 并 修 改 过 滤 条 件 为 ： 1 1 2