整数规划

5.2 整数规划的解题思路
1. 当人们开始接触整数规划问题时，常常会 有如下两种初始想法： 想法一：因为可行方案的数目常常是有限 的，因此，从理论上讲，经过一一比较后， 总能求得最好方案。例如背包问题充其量有 2n-1种方式。但是这种穷尽法是行不通的。假 设一台计算机每秒比较一百万个方式，那么 要比较20！种方式，大约需要800年，要比较 260种方式，需要360多个世纪。
可行域=空集
max f = x1 + 4 x2 s.t. - 2 x1 + 3x2 ≤3 x1 + 2 x2 ≤8 x2 ≤2 x1 , x2 ≥0 解得 x1 = 4, x2 = 2
2. 分枝定界法的最优解步骤：
第一步：首先将整数规划问题当作一般的线性规划问 题处理，如果得到的解是整数解，则停止，否则转入第 二步； 第二步：增加整数约束，分枝，对分枝用线性规划求 解。如果得到的最优整数解的目标函数比其他分枝的最 优整数解的目标函数值都要好，则停止，否则转第三步； 第三步：（Ⅰ）若未获整数解的目标函数值比同层的 分枝要差，则暂停分枝。 （Ⅱ）如果其他枝的整数解目标函数值比这样要好，此 枝再也不用再分枝。 （Ⅲ）如果其他分枝的整数解目标函数比这枝要差，回 过头来继续对此枝分枝，希望找到一个使目标函数值有 所改善的整数解，转回第二步。
原始结点
图示：
上述说法可用图表示
max f = x1 + 4 x2 - 2 x1 + 3x2 ≤3
s.t.
x1 + 2 x2 ≤8
x1 , x2 ≥0 解 x1 = 2.5, x2 = 2.7
分枝 1 分枝 2
x2 ≥3
结点 1
x2 ≤2
原始结点
max f = x1 + 4 x2 s.t. x + 2 x ≤8 1 2 - 2 x1 + 3x2 ≤3 x2 ≥3 x1 , x2 ≥0

运筹学整数规划运筹学是研究在资源有限的条件下，如何进行决策和优化的一门学科。

整数规划是运筹学中的一个重要分支，它解决的是决策变量必须为整数的问题。

整数规划在实际问题中具有广泛的应用，如生产计划、设备配置、选址问题等。

整数规划问题的数学模型可以表示为：max/min c^T xs.t. Ax ≤ bx ≥ 0x ∈ Z其中，c是目标函数的系数矩阵，x是决策变量的向量，A是约束条件的系数矩阵，b是约束条件的向量，Z表示整数集合。

整数规划问题与线性规划问题相似，但整数规划问题的约束条件多了一个整数限制，使得问题的解空间变得更为复杂。

由于整数规划问题的NP-hard性质，求解整数规划问题是一项困难的任务。

求解整数规划问题的常用方法有分支定界法、割平面法和启发式算法等。

分支定界法是一种穷举搜索的方法，它通过将整数规划问题不断分割成更小的子问题，从而逐步搜索解空间，直到找到最优解。

分支定界法对于规模较小的问题比较有效，但对于大规模复杂问题，效率较低。

割平面法是一种通过添加新的约束条件来减少解空间的方法。

它利用线性松弛问题（将整数约束条件放宽为线性约束条件）的解来构造有效的割平面，从而逐步缩小解空间，找到最优解。

割平面法通常比分支定界法更有效，但对于某些问题，可能需要添加大量的割平面才能收敛到最优解。

启发式算法是一种基于经验和启发式搜索的方法。

它通过设置初始解、搜索策略和邻域搜索等步骤，来快速找到近似最优解。

常见的启发式算法有遗传算法、模拟退火算法和禁忌搜索算法等。

启发式算法虽然不能保证找到全局最优解，但能够在可接受的时间内找到较优解。

综上所述，整数规划作为运筹学中的重要分支，解决的是决策变量必须为整数的问题。

整数规划问题具有广泛的应用，但由于其NP-hard性质，求解过程较为困难。

常用的求解方法包括分支定界法、割平面法和启发式算法等。

这些方法各有优劣，根据具体问题的特点选择合适的方法进行求解。

运筹学中的整数规划问题分析运筹学是运用数学和定量分析方法，通过对系统的建模和优化，来解决实际问题的学科。

其中整数规划是运筹学中的一个重要分支，它在许多实际情况中得到广泛应用。

本文将对整数规划问题进行分析，并探讨其解决方法与应用领域。

一、整数规划问题定义及特点整数规划是一类线性规划问题的扩展，其目标函数和约束条件中的变量取值限定为整数。

通常，整数规划问题可以形式化表示为：Max/Min Z = c₁x₁ + c₂x₂ + ... + cₙxₙs.t.a₁₁x₁ + a₁₂x₂ + ... + a₁ₙxₙ ≤ b₁a₂₁x₁ + a₂₂x₂ + ... + a₂ₙxₙ ≤ b₂...aₙ₁x₁ + a₂₂x₂ + ... + aₙₙxₙ ≤ bₙx₁, x₂, ..., xₙ ∈ Z其中，Z为目标函数值，x₁, x₂, ..., xₙ为待求解的整数变量，c₁, c₂, ..., cₙ为目标函数的系数，aᵢₙ为约束条件的系数，b₁, b₂, ..., bₙ为约束条件的右端常数。

整数规划问题的特点在于整数约束条件的引入，使其解空间变得有限，增加了问题的复杂性。

与线性规划问题相比，整数规划问题更接近实际情况，能够更准确地描述和解决很多实际问题。

二、整数规划问题的解决方法解决整数规划问题的方法主要有以下几种：穷举法、剪枝法、分支定界法、动态规划法等。

具体使用哪种方法需要根据问题的规模和特点来确定。

1. 穷举法是最简单直观的方法，通过枚举搜索整数解空间中的每一个可能解来寻找最优解。

然而，由于整数解空间往往非常大，这种方法在实际问题中往往是不可行的。

2. 剪枝法是一种通过对解空间进行剪枝操作，减少搜索空间的方法。

通过合理选择剪枝条件，可以避免对明显无解的解空间进行搜索，从而提高求解效率。

3. 分支定界法是一种将整数规划问题不断分解为子问题，并对子问题进行界定的方法。

通过不断缩小问题规模，并计算上下界确定最优解的位置，可以有效地求解整数规划问题。

第四章
整数规划
整数规划问题的提出
整数规划模型与一般的线性规划模型 的区别仅在于： 的区别仅在于：整数规划的变量要求 部分的或全部的为整数。例如： 部分的或全部的为整数。例如：
m Z = x + x2 ax 1 14 1 x +9x2 ≤ 51 −6x +3x2 ≤1 1 x , x ≥ 0且 整 为 数 1 2
(纯整数规划问题) 纯整数规划问题)
解：设xi为第i天开始上班的人数： 为第i天开始上班的人数： Min： Min：z=x1+x2+x3+x4+x5+x6+x7 s.t. x1 +x4+x5+x6+x7≥17 +x5+x6+x7≥13 x1+x2 x1+x2+x3 +x6+x7≥15 x1+x2+x3+x4+ +x7≥19 x1+x2+x3+x4+x5 ≥14 x2+x3+x4+x5+x6 ≥16 x3+x4+x5+x6+x7≥11 xi≥0 （ i=1,2,…,7） i=1,2,…,7）
例：某市6 例：某市6个区，希望设 置最少消防站以便节省 费用。条件：
必须保证在城区任何地方发 生火警时，消防车能在15 生火警时，消防车能在15分 15分 钟之内赶到现场。各区之间 消防车行驶的时间见右表。
请确定设站方案。
布点问题的数学模型： 0－1规划 布点问题的数学模型：
设0−1为决策变量，当表示i地区设站，表示i 为决策变量，当表示i地区设站，表示i 地区不设站。这样根据消防车15分钟赶到现 地区不设站。这样根据消防车15分钟赶到现 场的限制，可得到如下模型