实验六--整数规划14-15周.pdfVIP

实验六 整数规划实验 在实验三中我们介绍过数学规划的一般形式： 当模型 （），模型 （ ）中决策变量 的分量 中至少有一个只取整数数值时， 则该模型称为整数规划 （ ）。实验三、实验 四和实验五中介绍的都是 连续优化，而这个实验介绍的整数规划是组合优化 （离散优化）。 整数规划有不同的分类方法：当约束函数 和目标函数 都是决策变量 的 线性函数时，称为线性整数规划；否则称为非线性整数规划。当所有决策变量都只能在整数范 大工数模班 围内取值时，称为纯整数规划 （ ）；若某些决策变量可以再实数范 围内取值，而 另一些决策变量 只能在整数范 围内取值时，称为混合整数规划 （ ）。此外，当 整数决策变量只能取或时，相应的整数规划称为 规划。否则称为一般整数规划。 实验 目的 、熟悉掌握整数规划的求解方法； 、能够灵活编程来解决整数规划问题 ； 内部资料 实验基本知识 一般来说，整数规划 （ ）问题，即使是线性整数规划的求解也是非常困难的。虽然 的 可行解通常只有有限多个，可以通过枚举比较 出最优解，但是对于规模稍大些的实际问题，枚 举法 的计算量难以接受。我们知道，线性规划问题存在有效算法，那么为什么不先去去掉整数 限制，求解相应的线性规划问题 （一般称为整数规划的线性规划松弛问题，或者简称 松弛）， 然后将得到的解 四舍五入到最接近 的整数呢？在有些情况下，尤其 当 松弛的解是非常的实 数时，如果这些解对 四舍五入，那么这一策略可能是可行的。但在许多实际应用中，整数变量 的取值并不太大，特别是 规划问题，这一方法往往行不通。 求整数规划没有统一的有效方法，不同方法 的效果与问题 的性质有很大关系。下面介绍割 平面法、分支定界法、动态规划法和 规划。 整数规划解决方法 割平面法 算法原理 割平面法首先求解非整数约束的线性规划，再选择一个不是整数 的基变量，定义 新 的约束，增加到原来的约束中，新 的约束缩小了可行域，但是保留了原问题 的全部整数可行 解。 算法步骤 割平面法算法步骤 求 解 原 整 数 规 划 对 应 的 线 性 规 划 ，设最优解为 。 如果最优解 的分量均为整数，则 为原整数规划的最优解 ；否 则任选一个 中不是整数 的分量，设其对应的基变量为 ，定 义包含这 个基 变量 的切割约 束方 程 ，其 中 为非基变量。 令 ，其 中为高斯 函数符号， 表示不大于某数的最大整数。 大工数模班 将切割约束方程