deepread23｜第21章 整数规划详解

ONEPSOFT | 软考学习知识库

---

deepread23｜第21章 整数规划详解

一、定位

• 章节位置：第 21 章 项目管理科学基础 → 21.2 运筹学（整数规划，教材目录含 " 线性规划、运输、指派、动态规划…" 分支；整数规划/排队论本次 fetch 未单列正文）。
• 知识链条：在线性规划基础上加 " 变量必须为整数 " 的限制（如设备台数、班组数、项目个数不能劈开）。解法：分支定界法（Branch and Bound）。
• 考试分量：综合知识考 " 整数规划研究什么 "；计算/案例偶尔考分支定界的思想与几步迭代（松弛→分支→定界→剪枝）。

二、教材原文精摘

fetch 不全标注：本次对第 21 章的 fetch 在运筹学子节目录中未列 " 整数规划 " 独立小节（仅列线性规划、运输、指派、动态规划、图与网络、博弈论、决策分析），无原文与例题。下方用标准分支定界法的典型例题完整演示，数字均经手算核对，方法来源为运筹学标准算法（非教材杜撰）。

• 问题：max Z = 40x₁ + 90x₂，约束 9x₁+7x₂ ≤ 56，7x₁+20x₂ ≤ 70，x₁,x₂ ≥ 0 且为整数。
• 核心思想：先解 " 放宽整数限制 " 的线性规划（LP 松弛）得一个上界；若解非整数，则选一个分数变量 " 分两叉 "（≤向下取整、≥向上取整），递归求解；用 " 当前最好整数解 " 做下界，凡子问题上界 ≤ 下界或不可行就剪枝。

三、系统解读（平实分点）

1. 一句话理解：规划产量时发现 " 设备只能整台买、班组只能整队上 "，变量必须是整数。分支定界就是 " 先当实数算个上限，再逼它取整，不划算的分支砍掉 "。
2. LP 松弛：暂时允许变量取实数，解普通线性规划，得到一个 " 最优可能值的上界 "。若碰巧解出来刚好是整数 → 直接最优。
3. 分支（Branch）：若某变量解为分数（如 x₂=1.817），就拆成两支：一支强制 x₂ ≤ 1（向下取整），一支强制 x₂ ≥ 2（向上取整）。两支都搜，不漏解。
4. 定界与剪枝（Bound）：维护 " 当前已知最好整数解 " 作下界。某支的 LP 上界 ≤ 下界 → 它下面不可能更好，剪枝；分支后不可行 → 剪枝；得到更好整数解 → 更新下界。
5. 终止：所有活分支处理完，最后的下界解就是全局最优整数解。

四、工程举例（土木类比 + 数值）

例题：max Z = 40x₁ + 90x₂；9x₁+7x₂ ≤ 56；7x₁+20x₂ ≤ 70；x₁,x₂ ≥ 0 整数。（x₁,x₂ 可理解为两种构件/班组的整数产量）

分支定界树：

• Node0（LP 松弛）：解得 (x₁,x₂)≈(4.809, 1.817)，Z≈355.89（分数）→ 分支 x₂。
• Node1（x₂≤1）：LP 解 (5.44,1)，Z=307.78（分）→ 分支 x₁。
• Node3（x₁≤5, x₂≤1）：(5,1) 可行且整数，Z=290 → 首个整数候选（下界=290）。
• Node4（x₁≥6, x₂≤1）：9×6+7×1=61>56 → 不可行，剪枝。
• Node2（x₂≥2）：LP 解 (4.286,2)，Z=351.43（分）→ 分支 x₁。
• Node5（x₁≤4, x₂≥2）：LP 解 (4, 2.1)，Z=349（分）→ 分支 x₂。
• Node7（x₂≤2, x₁≤4）：(4,2) 可行且整数，Z=340 > 290 → 更新下界=340。
• Node8（x₂≥3, x₁≤4）：LP 上界 Z=327.2 < 340 → 剪枝。
• Node6（x₁≥5, x₂≥2）：7×5+20×2=75>70 → 不可行，剪枝。
• 最优整数解：(x₁,x₂)=(4,2)，Z=340。

高项概念	土木 / 施工类比
整数变量	设备台数、班组数（不能劈开）
LP 松弛上界	先当实数算的 " 理论最优 "
分支	把分数产量拆成 "≤整 " 和 "≥整进 1" 两方案
剪枝	该方案上限已不如此前最好整数方案 → 放弃

五、追问引导

• 为什么先解 " 放宽整数 " 的 LP 松弛？它给的是上界还是下界？为什么（整数限制只会让可行域变小，最优值不增）？
• 分支时为什么选 " 分数变量 "、且拆成 ≤⌊x⌋ 和 ≥⌈x⌉ 两支？这样为什么保证不漏解？
• " 当前最好整数解 " 充当什么角色？为什么说 " 子节点上界 ≤ 它 " 就可以剪枝？
• 哪些情况直接剪枝？（不可行；上界 ≤ 当前整数下界）还有别的情况吗（得到更好整数解则更新下界继续）？
• 本题为什么最终最优是 (4,2)=340，而不是更早找到的整数解 (5,1)=290？（290 只是首个候选，分支树继续搜出了更优的 340）