practice54｜第21章 整数规划自测

ONEPSOFT | 软考学习知识库

---

practice54｜第21章 整数规划自测

三题覆盖情境判断 / 概念辨析 / 综合连接。做完对照 " 教材依据 " 与 " 参考答案解读 "，再用底部自评表打分。

题目一（情境判断）

用分支定界法解：max Z = 3x₁ + 2x₂；x₁ + x₂ ≤ 4；x₁,x₂ ≥ 0 整数。已知 LP 松弛最优解 (2.5, 1.5)，Z=10.5。请写出第一步分支并说明首整数候选。

教材依据

分支定界：解 LP 松弛得上界；分数变量分 ≤⌊·⌋ 与 ≥⌈·⌉ 两支；先出现的整数解作候选下界。

参考答案解读

• LP 松弛 (2.5,1.5)，Z=10.5（分数）→ 分支。可任选 x₁ 或 x₂。
• 选 x₁：Node1 x₁≤2，Node2 x₁≥3。
• Node1（x₁≤2）：x₁=2,x₂≤2 取 (2,2) 整数，Z=3×2+2×2=10 → 首整数候选（下界=10）。
• Node2（x₁≥3）：x₁=3,x₂≤1 取 (3,1) 整数，Z=3×3+2×1=11 > 10 → 更新下界=11。
• 最优整数解 (3,1)，Z=11（首候选 10 不是最终最优，需继续搜）。

土木画像提示

像排 2 种班组共 ≤4 队，实数解说 2.5+1.5 队；拆成 "≤2 队 " 和 "≥3 队 " 两方案分别取整，先得 10 不是底，搜出更优 11。

---

题目二（概念辨析）

关于分支定界法，下列说法正确的是（ ）

A. LP 松弛给出的是原整数问题的下界

B. 分支时把分数变量拆成 ≤⌊x⌋ 与 ≥⌈x⌉ 两支，保证不漏解

C. 某分支 LP 上界比当前最好整数解小，应继续往下细分

D. 整数解一定出现在 LP 松弛的最优顶点上

教材依据

LP 松弛是上界（整数限制使可行域更小、最优值不增）；分支不漏解；子节点上界≤当前整数下界即剪枝；整数解需在分支树中搜索。

参考答案解读

选 B。A 错：LP 松弛是上界（整数最优 ≤ 松弛最优）；B 对：两分支覆盖该变量的全部整数可能，不漏解；C 错：上界 ≤ 当前整数下界说明该支不可能更优，应剪枝而非细分；D 错：整数解通常在分支后的子节点，不一定在松弛顶点。

土木画像提示

" 放宽松 " 算的是上限；分叉把 " 半台设备 " 拆成 " 整台及以下 " 和 " 整台及以上 " 两路，全包住；某路上限已经不如已知最好整数方案，直接砍。

---

题目三（综合连接）

上题中若 Node2（x₁≥3）分支后再出现一个子节点 LP 上界 Z=10.8，而当前整数下界已是 11。该子节点应如何处理？为什么？

教材依据

剪枝判据：子节点 LP 上界 ≤ 当前已知最好整数下界 → 其下不可能有更优整数解，剪枝。

参考答案解读

• 当前整数下界 = 11；该子节点 LP 上界 = 10.8 \< 11。
• 因为整数最优值 ≤ 该支 LP 上界（10.8），而 10.8 \< 11，所以该支任何整数解都不可能超过已知最好的 11。
• 处理：剪枝（停止细分该分支），不必再算。

土木画像提示

已知最好整数方案已值 11，这条路 " 理论最大 " 才 10.8，铁定追不上，直接放弃，省算力。

---

自评表（做完打 √ / 打分）

维度	自评分（1-5）	备注
我理解 LP 松弛是上界
我会做分支（≤⌊x⌋ / ≥⌈x⌉）
我理解 " 当前最好整数 " 作下界
我会判断剪枝（不可行/上界≤下界）
我知首整数候选未必是最终最优

低于 3 分的项目，回看 deepread54 的 ③ 段和 calculate54 分步解题再巩固一遍。