0-1规划

0-1 规划（0-1 Programming, Binary Programming）是整数规划中最特殊、也最常用的一类：每个决策变量只能取 0 或 1，即"选"与"不选"。项目是否投资、物品是否装包、人员是否派遣、站点是否建设——凡是"做不做"的两难决策，几乎都能写成 0-1 规划。它既可以用分支定界法精确求解，也常与贪心、动态规划等算法对比印证，是数学建模竞赛中方案选择类、资源分配类、选址类题目的核心工具。本文从模型、逻辑约束建模技巧、评价指标、可视化到可运行代码，完整梳理 0-1 规划的竞赛实战用法。

一、算法含义

1.1 通俗理解

生活中大量决策是"二选一"的开关型决策：

• 投资组合：每只股票买或不买；
• 0-1 背包：每件物品装或不装；
• 志愿者分配：每个人派或不派到某任务；
• 设施选址：每个候选点建或不建仓库；
• 旅行商问题：城市 $i$ 到 $j$ 的路走或不走。

把这些"是/否"决策用变量 $x_i \in \{0,1\}$ 表示（$x_i=1$ 表示"选"，$x_i=0$ 表示"不选"），配上线性目标函数和线性约束，就得到 0-1 规划。与一般整数规划（$x \in \mathbb{Z}_{+}$）相比，0-1 规划把"取多少"压缩成"取不取"，$n$ 个变量只有 $2^n$ 种组合——虽然这个数随 $n$ 指数爆炸，但"只有有限种"这一事实恰恰是隐枚举法、分支定界法等精确算法的出发点。

1.2 数学模型

0-1 规划的标准形式（以最大化为例）：

$\max \; z = \sum_{i=1}^{n} c_i x_i$

$\text{s.t.} \quad \sum_{i=1}^{n} a_{ij} x_i \le b_j, \quad j = 1, 2, \dots, m$

$x_i \in \{0, 1\}, \quad i = 1, 2, \dots, n$

写成矩阵形式：

$\max \; z = c^\top x, \qquad \text{s.t.} \quad A x \le b, \quad x \in \{0,1\}^n$

其中：

• $x = (x_1, \dots, x_n)^\top$：0-1 决策变量，$x_i = 1$ 表示采取第 $i$ 项决策；
• $c_i$：第 $i$ 项决策带来的收益（或成本，若目标是最小化）；
• $a_{ij}$：第 $i$ 项决策消耗第 $j$ 种资源的数量；
• $b_j$：第 $j$ 种资源的上限（预算、人力、时间、容量等）。

若目标是最小化、约束是 $\ge$ 或 $=$，只需对目标取负号、约束乘 $-1$，即可化为上述标准形式。如果部分变量是连续变量（如生产数量 $x_j \ge 0$），另一部分是 0-1 变量（如是否开工 $y_j \in \{0,1\}$），则称为混合 0-1 规划（Mixed 0-1 Programming），是固定成本问题的标准形态。

1.3 五大经典原型问题

（1）0-1 背包问题（Knapsack）

$n$ 件物品，第 $i$ 件重量 $w_i$、价值 $v_i$，容量 $C$ 的背包，每件物品最多装一件，使总价值最大：

$\max \; \sum_{i=1}^{n} v_i x_i, \qquad \text{s.t.} \quad \sum_{i=1}^{n} w_i x_i \le C, \quad x_i \in \{0,1\}$

这是"唯一约束"的 0-1 规划，结构最简单但已是 NP 难问题，常用于验证算法正确性与贪心算法的失效。

（2）指派问题（Assignment）

$n$ 个人做 $n$ 件事，第 $i$ 人做第 $j$ 件事的成本为 $c_{ij}$，每人恰好做一件事、每件事恰好由一人做：

$\min \; \sum_{i=1}^{n} \sum_{j=1}^{n} c_{ij} x_{ij}, \qquad \text{s.t.} \quad \sum_{j=1}^{n} x_{ij} = 1 \;(i=1,\dots,n), \quad \sum_{i=1}^{n} x_{ij} = 1 \;(j=1,\dots,n), \quad x_{ij} \in \{0,1\}$

指派问题的约束矩阵是全单模矩阵，LP 松弛自动得到整数解，因此有匈牙利算法等 $O(n^3)$ 多项式算法——这是 0-1 规划中少见的"易解"特例。

（3）集合覆盖问题（Set Covering）

有 $n$ 个需求点、$m$ 个候选设施，设施 $j$ 建造成本 $c_j$，能覆盖的需求点集合为 $S_j$。要求每个需求点至少被一个设施覆盖，总成本最小：

$\min \; \sum_{j=1}^{m} c_j x_j, \qquad \text{s.t.} \quad \sum_{j:\, i \in S_j} x_j \ge 1 \;(i=1,\dots,n), \quad x_j \in \{0,1\}$

典型应用：消防站、急救中心、基站选址——"每个居民点至少有一个设施能在规定时间内到达"。

（4）选址问题（Facility Location）

经典的无容量固定费用选址问题（UFLP）：$y_j = 1$ 表示在 $j$ 处建仓库（固定费用 $f_j$），$x_{ij} = 1$ 表示需求点 $i$ 由仓库 $j$ 服务（服务成本 $c_{ij}$）：

$\min \; \sum_{j=1}^{m} f_j y_j + \sum_{i=1}^{n} \sum_{j=1}^{m} c_{ij} x_{ij}, \qquad \text{s.t.} \quad \sum_{j=1}^{m} x_{ij} = 1 \;(\forall i), \quad x_{ij} \le y_j \;(\forall i,j), \quad x_{ij}, y_j \in \{0,1\}$

约束 $x_{ij} \le y_j$ 是逻辑约束：只有仓库 $j$ 建了，才能把需求点分配给它——这也是竞赛应急物资选址类题目的标准骨架。

（5）固定成本问题（Fixed Charge）

生产数量 $x_j$（连续变量）有固定启动成本 $f_j$：只要 $x_j > 0$ 就要付出 $f_j$。引入 0-1 变量 $y_j$（是否开工）：

$\max \; \sum_{j=1}^{n} \left( p_j x_j - f_j y_j \right), \qquad \text{s.t.} \quad 0 \le x_j \le M_j y_j, \quad y_j \in \{0,1\}$

当 $y_j = 1$ 时 $x_j$ 可以取到 $M_j$；当 $y_j = 0$ 时强制 $x_j = 0$。$M_j$ 取 $x_j$ 的可能最大值（如产能上限）。这是"0-1 变量控制连续变量"的经典模式。

1.4 逻辑约束的建模技巧（重点）

0-1 规划的真正威力在于：现实中的逻辑关系（互斥、依赖、条件）都能翻译成线性不等式。竞赛中评分老师最看重的就是这些建模手法。

（1）互斥约束：项目 1 和项目 2 最多选一个（二选一）：

$x_1 + x_2 \le 1$

推广：$m$ 个方案中恰好选一个（多选一）：$\displaystyle\sum_{i=1}^{m} x_i = 1$；至多选 $k$ 个：$\displaystyle\sum_{i=1}^{m} x_i \le k$；至少选 $k$ 个：$\displaystyle\sum_{i=1}^{m} x_i \ge k$。

（2）依赖约束：选项目 2 必须先选项目 1（1 是 2 的前提）：

$x_2 \le x_1$

验证一下四种组合：$(x_1,x_2)=(1,1)$ 可行（两个都选）；$(1,0)$ 可行；$(0,0)$ 可行；$(0,1)$ 违反约束——即"选了 2 却没选 1"被禁止，而"选了 1 可以不选 2"。方向千万别写反：$x_1 \le x_2$ 的含义恰好相反（选 1 必须选 2）。

（3）捆绑/共存约束：两个项目要么都选、要么都不选：

$x_1 = x_2$

（4）if-then 约束与大 M 方法：形如"若 $y=1$，则必须有 $a^\top x \le b$"的条件约束，写成：

$a^\top x \le b + M(1 - y)$

其中 $M$ 是一个"足够大"的常数（大于 $a^\top x - b$ 的最大可能值）。当 $y=1$ 时约束生效为 $a^\top x \le b$；当 $y=0$ 时约束变成 $a^\top x \le b + M$，因为 $M$ 足够大，这条约束自动失效（不会切掉任何可行解）。反过来，"若 $y=0$ 则必须有 $a^\top x \le b$"写成 $a^\top x \le b + M y$。

（5）启动约束（大 M 的另一种用法）：连续变量 $x$（如产量）只有在 0-1 变量 $y$（是否开工）为 1 时才能取正值：

$x \le M y$

这是 1.3 节固定成本问题中 $x_j \le M_j y_j$ 的来源，本质上是"$x > 0 \Rightarrow y = 1$"的逻辑表达。

（6）与/或逻辑：$x_1$ 和 $x_2$ 都选了才能选 $x_3$：

$2 x_3 \le x_1 + x_2$

$x_1$、$x_2$ 中至少选一个才能选 $x_3$：$x_3 \le x_1 + x_2$。

大 M 的取值原则：$M$ 不能太小（否则 $y=0$ 时约束仍起作用，切掉了合法方案），也不能太大（过大会造成数值问题、且 LP 松弛被"撑松"，分支定界剪枝效率变差）。正确做法是取紧的上界，例如 $M = \max(a^\top x) - b$（在可行域内估算），或直接取资源总量的自然上限。

1.5 与一般整数规划的关系

• 特殊与一般：0-1 规划是整数规划的特例（变量取值从 $\mathbb{Z}_{+}$ 压缩到 $\{0,1\}$）；反过来，任何有界整数变量都可以二进制展开成 0-1 变量之和：$x = y_1 + 2y_2 + 4y_3 + \cdots$（$y_k \in \{0,1\}$），因此理论上整数规划都能编码为 0-1 规划；
• 混合 0-1 规划：部分变量连续、部分变量 0-1（如固定成本问题），求解器（HiGHS、Gurobi、CPLEX）统一按 MILP 处理；
• 组合结构更强：0-1 规划与组合数学（匹配、覆盖、装箱、图论）联系紧密，$2^n$ 枚举空间是隐枚举与分支定界的舞台；部分特殊结构（指派、网络流）约束矩阵全单模，LP 松弛自动整数，可用多项式算法求解；
• 难度：一般 0-1 规划是 NP 难问题，不存在多项式精确算法（除非 P=NP），规模大时必须借助启发式或专用结构（如背包的 DP）。

1.6 求解方法：隐枚举法与分支定界法

（1）隐枚举法（Implicit Enumeration）

理论上 $n$ 个变量有 $2^n$ 种方案，全部列出不可行；但可以用约束和目标"剪掉"大量不需要检查的分支：

• 可行性剪枝：固定了部分变量后发现剩余资源连最轻的物品都装不下，该分支全部不可行；
• 定界剪枝：计算该分支上"最好也只可能达到"的价值上界，若上界 $\le$ 已找到的最优解，该分支内的所有方案都不值得再看。

"隐"的含义：不需要真正枚举 $2^n$，而是通过剪枝跳过成片方案。

（2）分支定界法（Branch and Bound, BnB）

隐枚举法的系统化实现，三步循环：

1. 松弛（定界）：把节点的 0-1 条件放松为 $0 \le x_i \le 1$，解 LP 松弛得到上界（max 问题）——LP 是多项式可解的，上界算得快；若松弛解本身就是整数解，则得到一个整数可行解，更新下界（当前最优值）；
2. 分支：选松弛解中取分数的变量 $x_k$（$0 < x_k < 1$），强制 $x_k = 0$ 与 $x_k = 1$ 各生成一个子节点，把问题拆成两个不相交的子问题；
3. 剪枝：子节点的上界 $\le$ 当前下界，或子问题不可行时，直接丢弃该节点。

当所有节点都被处理完（展开或剪掉），下界对应的整数解就是全局最优解。现代求解器（scipy 的 HiGHS、Gurobi、CPLEX）在此基础上还叠加了割平面、预处理等技巧，统称分支-割平面法。对 0-1 背包这类结构特殊的问题，节点松弛往往有闭式公式（按价值密度排序、最后一件取分数），第六节的代码就利用了这个技巧。

1.7 优缺点

优点：

• 表达能力极强：互斥、依赖、条件等逻辑关系都能写成线性约束，几乎"什么决策都能建模"；
• 求解手段成熟：小中规模（几十个 0-1 变量）现代求解器通常秒解，且给出全局最优保证；
• 模型即论文：变量定义 + 目标 + 约束的写法清晰规范，评委易读、易验证；
• 天然可对比：可用 LP 松弛、贪心解给出上界/近似解，展示"精确解 vs 近似解"的差距，论文内容充实。

缺点：

• NP 难：规模一大（几百个 0-1 变量）求解时间指数增长，可能跑不出来；
• 建模有门槛：大 M、逻辑约束写错方向会得到"数学上没问题、业务上完全错"的模型；
• 只能处理线性目标和线性约束，非线性项（如 $x_1 x_2$、分段函数）需额外线性化；
• 无"半途而废"的优雅解：要么求得最优，要么只能拿启发式近似，中间状态的质量评估依赖求解器的间隙指标。

二、何时使用（适用场景与条件）

2.1 适用场景

1. 项目选择：预算有限，从若干备选项目中挑一批使总收益最大（投资组合、科研立项、赛事报名）；
2. 任务指派：人-岗匹配、订单-机器分配、志愿者-岗位派遣（谁做哪件事）；
3. 设施选址：仓库、基站、消防站、应急物资储备点建在哪里，覆盖哪些需求点；
4. 背包类资源分配：容量/预算/时间约束下选择物品、广告位、航线、课程（"装哪些"）；
5. 路线/节点选择：TSP（走不走边 $ij$）、路径规划中的节点是否经过（$x_{ij} \in \{0,1\}$）。

2.2 竞赛典型题目

• 投资组合选择：$M$ 只股票/项目各投不投，预算与行业分散约束（互斥：同一行业最多投 2 只；依赖：投了上游才能投下游），最大化收益或最小化风险暴露；
• 志愿者分配：$m$ 个岗位需要特定技能组合，$n$ 名志愿者各具技能，要求每岗配齐、每人最多一岗（指派模型的变体，约束 $\sum_j x_{ij} \le 1$）；
• 应急物资选址：从候选点中选 $p$ 个建储备库，使覆盖人口最大或到达时间最短（集合覆盖 / p-中位模型），再叠加"各库容量上限、预算上限"等约束。

2.3 使用前提（建模前检查清单）

1. 决策确实非此即彼：每个变量的取值天然是"选/不选"（若"选多少"，应是一般整数规划）；
2. 目标与约束是线性的：收益、成本、资源消耗与决策量成正比（非线性项需先线性化）；
3. 规模可控：0-1 变量约在几十个量级时 milp 求解可靠；几百个以上需谨慎，备好启发式方案；
4. 逻辑关系能写成线性不等式：互斥、依赖、条件约束都能用 1.4 节的技巧表达；
5. 有可量化的数据：每个选项的收益/成本/资源消耗有明确数值（论文中可用熵权、AHP 等先算好权重再建模）。

2.4 不适用 / 慎用的情形

• 决策是连续的（买多少斤、投多少钱），用线性规划即可，不必硬造 0-1 变量；
• 目标或约束非线性且难以线性化（如 $x_i \cdot x_j$ 大量出现、凸/凹非线性项），考虑非线性规划或智能算法；
• 变量成百上千：精确求解可能几小时无果，改用遗传算法、模拟退火等启发式，或用问题特有结构（DP、匈牙利算法）降维；
• 需要实时/在线决策：0-1 规划每次求解都需要时间，实时场景用贪心或离线预计算；
• 数据高度不确定且要求鲁棒方案：应升级为随机规划 / 鲁棒优化，而不是单一 0-1 规划。

2.5 与整数规划、动态规划、贪心算法的对比与选择

方法	适用情形	优点	缺点
0-1 规划 + milp	选/不选决策 + 复杂逻辑约束（互斥、依赖、大 M）	建模灵活、精确最优、逻辑约束直接写	NP 难，规模大时慢
一般整数规划	决策是"取多少个"（产量、人数）	同上	同上，且丢失 0-1 的逻辑建模便利
动态规划（DP）	背包类问题且容量 $C$ 不大（$O(nC)$ 伪多项式）	速度快且稳定、易手写、无求解器依赖	$C$ 大时状态爆炸；对复杂附加约束（互斥、依赖）不好扩展
贪心算法	需要极快近似解，或作为分支定界的初始下界	极快、易实现	无最优性保证，常见反例（本文第六节实例即贪心失败案例）

何时用 DP 更优：0-1 背包问题中，若容量 $C$ 较小（如 $C \le 10^5$）而物品数 $n$ 很大，DP 的 $O(nC)$ 时间稳定可控，而分支定界的最坏时间是指数的——此时 DP 是首选；反之 $C$ 极大（如 $10^9$）时 DP 状态表开不下，退回 0-1 规划 / 分支定界。竞赛建议：复杂逻辑约束用 0-1 规划；纯背包用 DP 或 0-1 规划二选一并互相验证；贪心永远只作对比基准，不要作为最终答案。

三、算法指标

以最大化 0-1 背包问题（本文实例）为例，各指标定义如下。

3.1 最优目标值 $z^{*}$（选中方案总价值/总成本）

$z^{*} = \max \; c^\top x, \qquad x \in \{0,1\}^n, \; Ax \le b$

含义：0-1 规划模型的最终答案——最优方案的总价值（max 问题）或总成本（min 问题）。解读：这是所有可行方案中的全局最优值，论文的核心结论数字；任何"改进方案"都不可能超过它。

3.2 LP 松弛最优值 $z_{LP}$

$z_{LP} = \max \; c^\top x, \qquad 0 \le x \le 1, \; Ax \le b$

含义：把 0-1 条件放松成 $0 \le x_i \le 1$ 后线性规划的最优值。解读：可行域变大了，所以对 max 问题 $z_{LP} \ge z^{*}$——它是不可达到（或不可超过）的上界，可用于分支定界的剪枝，也在论文中充当"理论上限"的参照系。对 0-1 背包，$z_{LP}$ 有闭式解：按价值密度 $v_i / w_i$ 从大到小装整件物品，直到装不下时把下一件物品取分数件（比例 = 剩余容量 / 该件重量）。

3.3 LP 松弛间隙（积分间隙，Integrality Gap, IG）

$\text{IG} = \frac{\lvert z_{LP} - z^{*} \rvert}{\lvert z_{LP} \rvert} \times 100\%$

含义：LP 松弛解与 0-1 最优解之间的相对差距。解读：IG 越小，说明松弛越"紧"（分支定界剪枝越有效、问题越好解）；IG 为 0 说明 LP 松弛本身就给出整数最优解（如指派问题）。若 IG 很大，模型可能松弛过松（常见原因：大 M 取值过大），应改善建模。

3.4 约束满足率（可行组合比例）

$\text{可行率} = \frac{N_{\text{feas}}}{2^n} \times 100\%, \qquad N_{\text{feas}} = \#\left\{ x \in \{0,1\}^n : Ax \le b \right\}$

含义：$2^n$ 种 0-1 组合中有多少满足全部约束。解读：反映约束松紧与可行方案密度。太小（如 $<1\%$）说明约束苛刻、可行解稀少（对启发式搜索不利）；接近 100% 说明约束几乎不起作用。小规模时可用暴力枚举统计（本文实例 $n=15$ 恰好可算），大规模时改用随机抽样估计。

3.5 资源利用率 $U$（以背包为例）

$U = \frac{\sum_{i=1}^{n} w_i x_i^{*}}{C} \times 100\%$

含义：最优方案实际使用的资源量占资源总量的比例（背包为重量利用率，选址问题可为容量利用率、预算使用率）。解读：利用率接近 100% 说明瓶颈资源被充分利用（方案"紧凑"）；明显偏低可能意味着模型遗漏了未利用资源的机会成本，或存在其他隐性瓶颈。

3.6 选中决策数 $k$

$k = \sum_{i=1}^{n} x_i^{*}$

含义：最优方案中 $x_i = 1$ 的变量个数（选了多少个项目/物品）。解读：注意"选得多 ≠ 价值高"——贪心解常常比最优解选的件数更多（塞满低价值小件），而最优解可能少选几件但价值更高。该指标用来在论文中拆解方案构成。

3.7 与贪心解、松弛解的对比（最优性差距）

$\Delta_{\text{greedy}} = z^{*} - z_{\text{greedy}}, \qquad \rho_{\text{greedy}} = \frac{z^{*} - z_{\text{greedy}}}{z_{\text{greedy}}} \times 100\%$

含义：精确解相对贪心近似解的绝对与相对提升；类似地可定义"距 LP 上界的距离" $z_{LP} - z^{*}$。解读：这两个数字是论文中最有说服力的"论证精确求解必要性"的论据：若 $\rho_{\text{greedy}}$ 显著大于 0，说明贪心不可接受、精确解物有所值；若为 0，可退而承认贪心在本例恰好最优（但仍需说明无一般性保证）。

3.8 求解时间 $T$ 与搜索工作量

含义：$T$ 为求解器/手写算法的墙钟时间（ms 或 s）；搜索工作量可用分支定界节点数 $N_{\text{BnB}}$ 度量。解读：用于评估模型规模的可行性与算法效率；论文中常报告"milp 求解时间 < 1 s，说明模型规模合理"。节点数越少说明定界越紧、剪枝越有效；节点数爆炸是"松弛过松"的典型信号。

3.9 指标汇总表

指标	中文名	公式	方向	一句话解读（本例值见第七节）
$z^{*}$	最优目标值	$\max c^\top x,\ Ax \le b,\ x \in \{0,1\}^n$	max 越大越好	最终答案：最优方案总价值 618
$z_{LP}$	LP 松弛最优值	同上，$0 \le x_i \le 1$	max 越大越好	不可超过的理论上界 627
IG	LP 松弛间隙	$\lvert z_{LP} - z^{*} \rvert / \lvert z_{LP} \rvert$	越小越好	松弛紧致程度；1.44%，很紧
可行率	约束满足率	$N_{\text{feas}} / 2^n$	—	可行方案密度；47.27%，约束适中
$U$	资源利用率	$\sum w_i x_i^{*} / C$	越高越紧凑	背包装满程度；97.14%
$k$	选中决策数	$\sum x_i^{*}$	—	最优选 9 件 vs 贪心 10 件
$\Delta_{\text{greedy}}$	贪心绝对差距	$z^{*} - z_{\text{greedy}}$	越大越有必要精确求解	差距 25，相对提升 4.22%
$z_{LP} - z^{*}$	距 LP 上界距离	—	越小说明解越"贴顶"	距上界仅 9
$N_{\text{BnB}}$	分支定界节点数	—	越小越好	23 个节点即证明最优
$T$	求解时间	墙钟时间	越短越好	本例毫秒级

四、可视化图表

0-1 规划"算出一个数"远远不够，图是向评委证明'解合理、过程正确'的关键。以下 4 张图覆盖"方案本身 + 方案成因 + 求解过程 + 与贪心的对比"，全部代码见第六节，图片自动保存到 figures/ 目录（文件名统一前缀 zolp_）。

4.1 四张图速查表

图名（输出文件）	用途	关键解读点
① 项目/物品选择结果条形图（zolp_selection_bar.png）	一眼看出哪些物品被选中、价值几何	绿色柱 = 最优方案选中的 9 件物品 {3,6,9,10,11,12,13,14,15}；灰色柱 = 未选中的 6 件；柱顶标注每件物品重量。注意物品 1、5 是灰色——贪心选了它们，最优解没选
② 价值-重量散点图（zolp_value_weight.png）	从"价值-重量"二维空间解释贪心为何失败	每件物品一个点（数字为物品编号）；蓝点 = 仅最优选（物品 3，贪心陷阱）；橙点 = 仅贪心选（物品 1、5，误装）；红色虚线 = 容量参考线 $C=70$；最优方案累计重量 68 ≤ 70
③ 分支定界搜索树（zolp_bnb_tree.png）	展示隐枚举的"分支-定界-剪枝"全过程	根节点上界 627（LP 松弛）；浅蓝 = 分支节点（节点内数字为上界），灰 = 剪枝节点（上界 ≤ 当前下界），橙黄 = 整数可行解（更新下界 591 → 618）；红色路径 = 最终最优解的搜索路径；边上标注分支决策（$x_k=1/0$）
④ 最优目标值 vs 贪心解对比柱状图（zolp_greedy_compare.png）	定量展示精确解优于贪心解	三根柱：LP 松弛上界 627（不可达到）、最优解 618、贪心解 593；双向箭头标注差距 25（相对提升 4.2%）——精确求解"物有所值"

4.2 每张图"好"与"异常"的特征

图① 选择结果条形图

• 好图特征：两色对比鲜明；选中与未选中的价值差异一眼可见；柱顶标注重量等辅助信息。本例中"价值最高的一批物品（92、91、89）全是绿色"是典型好图特征——最优解优先抓高价值物品。
• 异常特征 / 警示：若最高价值的几件物品反而没被选中，图上看会很"反常"，此时必须能解释（如重量太大装不下、被逻辑约束排除）——论文中这是评审必问点，务必在图下说明原因。

图② 价值-重量散点图

• 好图特征：能看出"右上角（价值高、重量小）的物品基本都被选中，左下角基本都没选"的大致规律；容量参考线清晰；贪心陷阱物品被明确标注。
• 异常特征：若散点图上看不出任何规律（选中与否在空间里随机分布），说明目标与价值/重量无关或数据有问题，检查模型。另外注意：容量约束作用在累计重量上，单件重量都远小于容量时，参考线只是"总量刻度"，别误读成"单件重量不得超过 70"。

图③ 分支定界搜索树

• 好图特征：三种节点类型齐备；剪枝节点占比高（本例 23 个节点中 10 个剪枝），说明定界有效；最优解路径（红色）清晰可追溯，每个分支决策都能对上"物品选没选"。
• 异常特征：搜索树呈"满二叉树"疯长（节点数指数爆炸）→ LP 松弛太松或大 M 过大，应改进建模；或者整棵树全是剪枝没有整数解 → 初始下界缺失，应先用贪心/启发式喂一个下界。

图④ 精确解 vs 贪心对比柱状图

• 好图特征：三根柱单调关系正确（LP 上界 ≥ 最优 ≥ 贪心，对 max 问题）；差距标注醒目，直接支撑"为什么要精确求解"。
• 异常特征：若贪心柱与最优柱一样高，说明本例贪心恰好最优——可以报告，但必须强调"贪心无最优性保证，本例是巧合"（第六节实例专门构造了贪心失败的情形，避免这种尴尬）。

五、符号说明

符号	含义	示例/单位
$x_i$	0-1 决策变量：$x_i=1$ 表示"选"，$0$ 表示"不选"	$x_3 = 1$：装第 3 件物品
$n$	决策变量个数	背包实例 $n = 15$
$m$	约束个数	背包实例 $m = 1$（容量约束）
$c_i$	第 $i$ 项决策的目标系数（收益/成本）	背包中 $c_i = v_i$，价值/元
$v_i$	物品 $i$ 的价值	$v_3 = 60$
$w_i$	物品 $i$ 的重量	$w_3 = 15$
$C$	背包容量 / 资源上限	$C = 70$
$A, b$	约束系数矩阵与右端项	$A = [w_1, \dots, w_n]$，$b = C$
$\{0,1\}^n$	$n$ 维 0-1 向量的集合（$2^n$ 个元素）	$n=15$ 时共 32768 种组合
$z$ / $z^{*}$	目标函数值 / 最优目标值	$z^{*} = 618$
$z_{LP}$	LP 松弛最优值（上界）	$z_{LP} = 627$
IG	LP 松弛间隙 / 积分间隙	$\text{IG} = 1.44\%$
$N_{\text{feas}}$	可行 0-1 组合个数	$N_{\text{feas}} = 15489$
$U$	资源利用率	$U = 97.14\%$
$k$	选中决策数（$\sum x_i$）	最优方案 $k = 9$
$z_{\text{greedy}}$	贪心解目标值	$z_{\text{greedy}} = 593$
$\Delta_{\text{greedy}}$	精确解相对贪心的绝对差距	$\Delta_{\text{greedy}} = 25$
$\rho_{\text{greedy}}$	精确解相对贪心的提升率	$\rho_{\text{greedy}} = 4.22\%$
$M$	大 M 常数（if-then 约束中"足够大的数"）	项目选择示例中 $M = 100$
$y_j$	辅助 0-1 变量（开工/建设等"开关"）	$y_j=1$：在 $j$ 处建仓库
$f_j$	固定成本（启动费/建设费）	万元
$N_{\text{BnB}}$	分支定界搜索节点数	本例 $N_{\text{BnB}} = 23$
$T$	求解时间	ms
BnB	分支定界法（Branch and Bound）	本文核心算法
B&C	分支-割平面法（Branch-and-Cut）	现代求解器默认组合
milp	scipy 的混合整数线性规划接口	scipy.optimize.milp，内置 HiGHS 求解器
LP 松弛	把整数条件放松为区间约束的线性规划	$0 \le x_i \le 1$
NP 难	多项式精确算法（一般认为）不存在的复杂度类	0-1 规划属 NP 难

六、可运行程序（完整代码）

环境要求：Python 3.12，依赖 numpy、scipy、matplotlib（本机 .venv 已装好）。注意：代码只使用 scipy 自带的 HiGHS 求解器（scipy.optimize.milp 与 scipy.optimize.linprog），不依赖 pulp / cvxpy 等未安装的库。以下所有代码块按顺序拼接保存为 09_zolp_demo.py，在本文档所在目录运行即可：控制台打印第三节列出的全部指标、手写分支定界全过程与 milp 对照结果，并在 figures/ 子目录生成 4 张图（前缀 zolp_）。若运行环境无图形界面（如服务器），可用 MPLBACKEND=Agg python 09_zolp_demo.py 方式运行（代码保留 plt.show()，Agg 后端下它自动跳过）。

6.1 示例问题设定

主示例：0-1 背包问题（15 件物品）。用 np.random.seed(42) 生成重量 $w_i \in \{1,\dots,20\}$、价值 $v_i \in \{1,\dots,100\}$（$i=1,\dots,15$），容量取 $C = 70$（约为总重量的一半，"适中"不拥挤）。该实例是精心挑选的贪心反例：贪心按价值密度排序装入，先把容量用物品 13、12、10、11、6、15、9、14、5 占去 53 个单位，剩下 17 个单位装不下物品 3（$w=15, v=60$），只好塞物品 1（$w=7, v=2$）凑数，总价值 593；而最优解放弃物品 1、5（价值合计 $2+33=35$），改装物品 3（价值 60），总价值 618。模型：

$\max \; \sum_{i=1}^{15} v_i x_i \qquad \text{s.t.} \quad \sum_{i=1}^{15} w_i x_i \le 70, \quad x_i \in \{0,1\}$

附加示例：带逻辑约束的项目选择问题（5 个项目）。决策变量 $y_i \in \{0,1\}$（$i=1,\dots,5$），利润 $p=(50,60,40,30,45)$、成本 $c=(20,25,15,12,18)$（万元）、人力 $h=(10,8,6,5,7)$（人），预算 60 万元。约束：① 互斥：项目 1、2 二选一，$y_1 + y_2 \le 1$；② 依赖：项目 3 必须先上项目 1，$y_3 \le y_1$；③ if-then 大 M：若选项目 2，则总人力不得超过 25 人，$h^\top y \le 25 + M(1 - y_2)$，取 $M = 100$；④ 预算：$c^\top y \le 60$。该示例演示 1.4 节三大逻辑建模技巧的实际代码写法。

6.2 完整代码（按顺序拼接即为完整脚本）

# -*- coding: utf-8 -*-
# =====================================================================
# 0-1 规划（0-1 Programming）完整演示脚本
# 内容：
#   1) 构造 15 件物品的 0-1 背包实例（np.random.seed(42) 生成，容量 C=70，
#      专门保证"贪心非最优、分支定界树不大"的典型教学情形）
#   2) 手写实现：贪心算法（价值密度排序）、LP 松弛（闭式公式）、
#      暴力枚举（2^15 = 32768 种方案全部检验，作为标准答案）、
#      分支定界法（节点松弛用价值密度序闭式定界，分支变量 = 取分数的物品）
#   3) scipy.optimize.milp 调库对照（HiGHS 求解器）+ linprog 松弛对照
#   4) 附加小示例：带逻辑约束（互斥 / 依赖 / 大 M）的项目选择问题
#   5) 打印第三节全部指标，绘制第四节要求的 4 张图（保存到 figures/，前缀 zolp_）
# 环境：Python 3.12 + numpy / scipy / matplotlib（不依赖 pulp、cvxpy）
# 运行：python 09_zolp_demo.py（无图形界面时用 MPLBACKEND=Agg python 09_zolp_demo.py）
# =====================================================================

# ========== 0. 导入库与全局设置 ==========
import itertools
import os
import time

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.patches import Patch
from scipy.optimize import Bounds, LinearConstraint, linprog, milp

# ---- matplotlib 中文显示设置（防止图内中文乱码）----
plt.rcParams["font.sans-serif"] = ["PingFang SC", "Arial Unicode MS", "SimHei"]
plt.rcParams["axes.unicode_minus"] = False

# ---- 图片输出目录（相对当前工作目录的 figures/ 子目录）----
os.makedirs("figures", exist_ok=True)

# ---- 画图配色（固定"角色-颜色"映射，全套图保持一致）----
C_OPT    = "#2E8B57"   # 深绿：最优方案选中
C_UNSEL  = "#BDBDBD"   # 灰色：未选中
C_GREEDY = "#E8930C"   # 橙色：贪心方案
C_LP     = "#5B8DEF"   # 蓝色：LP 松弛 / 仅最优选
C_BRANCH = "#AED6F1"   # 浅蓝：分支节点
C_PRUNE  = "#D5D8DC"   # 灰：剪枝节点
C_INT    = "#F5B041"   # 橙黄：整数可行解节点

# ========== 1. 构造 0-1 背包实例（15 件物品，容量 70） ==========
# 决策变量 x_i ∈ {0,1}：x_i = 1 表示把第 i 件物品装进背包
# 模型：max Σ v_i x_i   s.t. Σ w_i x_i <= 70,  x_i ∈ {0,1}
np.random.seed(42)                        # 固定随机种子，保证结果可复现
n_items = 15                              # 物品件数
weights = np.random.randint(1, 21, size=n_items)    # 重量：1~20 的随机整数
values  = np.random.randint(1, 101, size=n_items)   # 价值：1~100 的随机整数
capacity = 70                             # 背包容量（约为总重量的 49%，"适中"）
print("=" * 66)
print("0-1 背包实例（n = %d，容量 C = %d）" % (n_items, capacity))
print("重量 w =", weights.tolist())
print("价值 v =", values.tolist())
order_density = sorted(range(n_items), key=lambda i: -values[i] / weights[i])
print("物品按价值密度 v/w 降序：", [i + 1 for i in order_density])

# ========== 2. 手写实现一：贪心算法（按价值密度 v/w 从大到小装） ==========
# 贪心思想：每次挑"单位重量最值钱"的剩余物品，能装下就整件装入。
# 注意：贪心没有最优性保证，本例专门构造了它失败的情形。
def greedy_knapsack(w, v, cap):
    order = sorted(range(len(w)), key=lambda i: -v[i] / w[i])   # 价值密度降序
    rem = float(cap)
    sel = [0] * len(w)
    val = 0.0
    for i in order:
        if w[i] <= rem:            # 剩余容量还装得下：整件装入
            sel[i] = 1
            rem -= w[i]
            val += v[i]
    return val, sel, cap - rem     # 返回（总价值, 选择向量, 已用重量）

g_val, g_sel, g_used = greedy_knapsack(weights, values, capacity)
print("-" * 66)
print("[贪心解] 总价值 = %.0f，装入 %d 件，已用重量 = %d / %d"
      % (g_val, sum(g_sel), g_used, capacity))
print("[贪心解] 装入物品 =", sorted(i + 1 for i in range(n_items) if g_sel[i]))

# ========== 3. 手写实现二：LP 松弛（闭式解：最后一件"卡住"的物品取分数） ==========
# 把 x_i ∈ {0,1} 放松为 0 <= x_i <= 1 后，最优解只需对一件物品取分数：
# 按价值密度降序装整件，直到容量不够装下一件时，把该件装"剩余容量/重量"的分数。
# 这正是分支定界每个节点"定界"所用的上界公式（证明思路见 8 节延伸阅读）。
def lp_relax_closed(w, v, cap):
    order = sorted(range(len(w)), key=lambda i: -v[i] / w[i])
    rem = float(cap)
    ub = 0.0
    frac_item = None     # 取分数的那件物品编号（下标）
    frac_amount = 0.0    # 取分数的比例
    for i in order:
        if w[i] <= rem:              # 整件装入
            ub += v[i]
            rem -= w[i]
        else:                        # 第一件装不下的物品：按比例装，即得 LP 最优值
            if rem > 0:
                frac_item = i
                frac_amount = rem / w[i]
                ub += v[i] * frac_amount
            break
    return ub, frac_item, frac_amount

lp_ub, lp_frac_item, lp_frac_amount = lp_relax_closed(weights, values, capacity)
print("[LP 松弛] 上界 z_LP = %.1f，取分数的物品 = 物品 %d（x = %.2f）"
      % (lp_ub, lp_frac_item + 1, lp_frac_amount))

# ========== 4. 手写实现三：分支定界法（Branch and Bound） ==========
# 搜索策略：深度优先；分支变量 = 当前节点 LP 松弛中"取分数"的那件物品
#          （0-1 背包最经典的分支策略）；先走 x=1 分支，尽快找到好的整数解。
# 定界（剪枝）规则：
#   (1) 节点松弛上界 ub <= 当前最优整数解（下界）→ 该子树不可能更优，剪枝；
#   (2) 节点松弛解全部为 0/1 → 得到整数可行解，更新下界；
#   (3) 固定部分已超重 → 不可行，剪枝。
# 终止条件：所有节点都被展开或剪掉，下界对应的解即全局最优。
def hand_branch_and_bound(w, v, cap):
    order = sorted(range(len(w)), key=lambda i: -v[i] / w[i])
    nodes = []                  # 搜索树节点记录（供打印与画图）
    incumbent = -np.inf         # 当前最优整数解（下界）
    inc_sol = None              # 下界对应的完整解
    inc_node = None             # 找到下界的节点编号
    inc_history = []            # (节点编号, 价值) 更新轨迹

    def relax(fixed):
        """节点松弛：fixed = {物品编号: 0或1} 表示已固定的决策。
        返回 (上界, 松弛解字典, 分数物品编号)。"""
        rem = cap - sum(w[i] for i, b in fixed.items() if b == 1)
        ub = sum(v[i] for i, b in fixed.items() if b == 1)
        sol = dict(fixed)
        if rem < 0:                       # 固定部分已超重：不可行
            return -np.inf, sol, None
        for i in order:
            if i in fixed:
                continue
            if w[i] <= rem:
                sol[i] = 1                # 整件装入
                ub += v[i]
                rem -= w[i]
            else:
                if rem > 0:               # 第一件装不下的物品取分数
                    sol[i] = rem / w[i]
                    ub += v[i] * (rem / w[i])
                    return ub, sol, i
                return ub, sol, None
        return ub, sol, None

    def dfs(fixed, parent):
        nonlocal incumbent, inc_sol, inc_node
        ub, sol, frac = relax(fixed)
        nid = len(nodes)
        nodes.append({"id": nid, "parent": parent, "branch": "",
                      "bound": ub, "outcome": "branch"})
        if ub <= incumbent + 1e-9:        # 剪枝：上界不高于当前下界
            nodes[nid]["outcome"] = "pruned"
            return nid
        if frac is None:                  # 松弛解本身是 0/1 整数解 → 更新下界
            if ub > incumbent:
                incumbent = ub
                inc_sol = {i: sol.get(i, 0) for i in range(len(w))}
                inc_node = nid
                inc_history.append((nid, ub))
            nodes[nid]["outcome"] = "integer"
            return nid
        for b in (1, 0):                  # 先 x=1 分支，再 x=0 分支
            f2 = dict(fixed)
            f2[frac] = b
            child = dfs(f2, nid)
            nodes[child]["branch"] = "x%d=%d" % (frac + 1, b)
        return nid

    t0 = time.perf_counter()
    dfs({}, None)
    t_bnb = time.perf_counter() - t0
    return incumbent, inc_sol, inc_node, inc_history, nodes, t_bnb

z_bnb, x_bnb_dict, inc_node_id, inc_history, bnb_nodes, t_bnb = \
    hand_branch_and_bound(weights, values, capacity)
x_bnb = [x_bnb_dict.get(i, 0) for i in range(n_items)]   # 转为 0/1 列表
print("-" * 66)
print("[分支定界] 共生成 %d 个节点，最优值 = %.0f" % (len(bnb_nodes), z_bnb))
for (nid, vv) in inc_history:
    print("[分支定界] 节点 %d 找到整数可行解，价值 = %.0f（更新下界）" % (nid, vv))

# ========== 5. 暴力枚举（2^15 = 32768 种方案全部检验，作为"标准答案"） ==========
# n 较小（<= 25）时枚举是"绝对可靠"的对照方法；同时统计可行组合数（指标 3.4）。
def brute_force(w, v, cap):
    best = -1.0
    bx = None
    n_feas = 0
    for x in itertools.product([0, 1], repeat=len(w)):
        if sum(w[i] * x[i] for i in range(len(w))) <= cap:
            n_feas += 1
            tv = sum(v[i] * x[i] for i in range(len(w)))
            if tv > best:
                best, bx = tv, list(x)
    return best, bx, n_feas

t0 = time.perf_counter()
z_brute, x_brute, n_feas = brute_force(weights, values, capacity)
t_brute = time.perf_counter() - t0

# ========== 6. scipy.optimize.milp 调库对照（HiGHS 求解器） ==========
# milp 求最小化，故目标系数取 -v；integrality=1 表示整数变量，
# bounds=(0,1) 把整数变量限制在 [0,1]，即 0-1 变量。
c_milp = -values.astype(float)
A_milp = weights.astype(float).reshape(1, n_items)
t0 = time.perf_counter()
res_milp = milp(c=c_milp,
                constraints=LinearConstraint(A_milp, -np.inf, capacity),
                integrality=np.ones(n_items),
                bounds=Bounds(0, 1))
t_milp = time.perf_counter() - t0
z_milp = -res_milp.fun
x_milp = (res_milp.x > 0.5).astype(int)

# ---- LP 松弛的 linprog 对照（验证第 3 节闭式上界公式的正确性）----
res_lp = linprog(c=c_milp, A_ub=A_milp, b_ub=[capacity],
                 bounds=[(0, 1)] * n_items, method="highs")
z_lp_linprog = -res_lp.fun

# ========== 7. 附加小示例：带逻辑约束的项目选择问题（0-1 规划三大建模技巧） ==========
# 5 个备选项目，决策变量 y_i ∈ {0,1}（i=1..5，y_i=1 表示投资项目 i）
# 利润 p、成本 c、人力需求 h；总预算 60 万元。
# 逻辑约束：
#   ① 互斥：项目 1、2 二选一            y1 + y2 <= 1
#   ② 依赖：项目 3 必须先上项目 1        y3 <= y1
#   ③ if-then（大 M）：若选项目 2，则总人力不得超过 25 人：
#      h^T y <= 25 + M(1 - y2)，取 M = 100（足够大：h^T y 最大只有 36）
p_proj = np.array([50.0, 60.0, 40.0, 30.0, 45.0])
c_proj = np.array([20.0, 25.0, 15.0, 12.0, 18.0])
h_proj = np.array([10.0, 8.0, 6.0, 5.0, 7.0])
BUDGET = 60.0
BIG_M = 100.0
A_proj = np.array([
    [1.0, 1.0, 0.0, 0.0, 0.0],            # ① y1 + y2 <= 1
    [-1.0, 0.0, 1.0, 0.0, 0.0],           # ② y3 - y1 <= 0
    [10.0, 8.0 + BIG_M, 6.0, 5.0, 7.0],   # ③ h^T y + M·y2 <= 25 + M
    [20.0, 25.0, 15.0, 12.0, 18.0],       # ④ 预算约束
])
b_proj = np.array([1.0, 0.0, 25.0 + BIG_M, BUDGET])
res_proj = milp(c=-p_proj,
                constraints=LinearConstraint(A_proj, -np.inf, b_proj),
                integrality=np.ones(5), bounds=Bounds(0, 1))
y_proj = (res_proj.x > 0.5).astype(int)
z_proj = -res_proj.fun

# ========== 8. 指标计算与汇总打印（对应第三节全部指标） ==========
# ---- 一致性自检：手写分支定界 vs milp vs 暴力枚举必须一致 ----
assert abs(z_bnb - z_brute) < 1e-9 and abs(z_bnb - z_milp) < 1e-9, "三种方法结果不一致！"
sel_opt    = sorted(i + 1 for i in range(n_items) if x_bnb[i] == 1)
sel_milp   = sorted(i + 1 for i in range(n_items) if x_milp[i] == 1)
sel_greedy = sorted(i + 1 for i in range(n_items) if g_sel[i] == 1)
used_w_opt = int(sum(weights[i] * x_bnb[i] for i in range(n_items)))

print("=" * 66)
print("【指标 1】最优目标值 z*（选中方案总价值）")
print("  手写分支定界 : z* = %.0f，装入 %d 件：%s" % (z_bnb, int(sum(x_bnb)), sel_opt))
print("  scipy.milp   : z* = %.0f，装入物品：%s" % (z_milp, sel_milp))
print("  暴力枚举对照 : z* = %.0f（2^15 种方案逐一检验）" % z_brute)
print("  结论：三种方法最优值与方案完全一致 ✔")

print("【指标 2】LP 松弛最优值 z_LP（不可达到的上界）")
print("  闭式公式    : z_LP = %.1f（物品 %d 取分数 x = %.2f，其余物品取 0/1）"
      % (lp_ub, lp_frac_item + 1, lp_frac_amount))
print("  linprog 对照: z_LP = %.1f" % z_lp_linprog)

ig = (lp_ub - z_bnb) / lp_ub * 100
print("【指标 3】LP 松弛间隙 IG = (z_LP - z*)/z_LP = (%.1f - %.0f)/%.1f = %.2f%%"
      % (lp_ub, z_bnb, lp_ub, ig))

n_total = 2 ** n_items
rate = n_feas / n_total * 100
print("【指标 4】约束满足率 = 可行组合数/全部组合数 = %d/%d = %.2f%%"
      % (n_feas, n_total, rate))
util = used_w_opt / capacity * 100
print("【指标 5】资源利用率（最优方案）= 已用重量/容量 = %d/%d = %.2f%%"
      % (used_w_opt, capacity, util))

print("【指标 6】选中决策数 k = Σ x_i（最优方案）= %d 件；贪心装了 %d 件"
      % (int(sum(x_bnb)), int(sum(g_sel))))
print("  注意：件数多 ≠ 价值高——贪心比最优多装 1 件，价值反而低")

gap_g = z_bnb - g_val
rel_g = gap_g / g_val * 100
print("【指标 7】与贪心解的对比（最优性差距）")
print("  贪心解（按价值密度排序装入）: z_greedy = %.0f，装入物品：%s" % (g_val, sel_greedy))
print("  最优解与贪心解差距: Δ = z* - z_greedy = %.0f，相对提升 ρ = %.2f%%"
      % (gap_g, rel_g))
print("  距 LP 上界的距离: z_LP - z* = %.1f（任何方案都不可能超过 %.1f）"
      % (lp_ub - z_bnb, lp_ub))

n_branch  = sum(1 for nd in bnb_nodes if nd["outcome"] == "branch")
n_pruned  = sum(1 for nd in bnb_nodes if nd["outcome"] == "pruned")
n_integer = sum(1 for nd in bnb_nodes if nd["outcome"] == "integer")
print("【指标 8】求解时间与搜索工作量")
print("  手写分支定界: 共 %d 个节点（%d 个分支 + %d 个剪枝 + %d 个整数解），耗时 %.3f ms"
      % (len(bnb_nodes), n_branch, n_pruned, n_integer, t_bnb * 1000))
print("  scipy.milp : 耗时 %.3f ms（HiGHS 内置分支-割平面）" % (t_milp * 1000))
print("  暴力枚举   : 耗时 %.3f s（2^%d = %d 种组合）" % (t_brute, n_items, n_total))

print("=" * 66)
print("【附加示例】带逻辑约束的项目选择问题（5 个备选项目，预算 60 万元）")
print("  模型：max 50y1+60y2+40y3+30y4+45y5")
print("  约束：y1+y2<=1（互斥）；y3<=y1（依赖）；")
print("        h^T y <= 25 + 100*(1-y2)（大 M：若选项目 2 则总人力<=25）；")
print("        c^T y <= 60（预算）；y_i ∈ {0,1}")
print("  milp 最优: z = %.0f，选择项目 %s，成本 = %.0f <= %.0f"
      % (z_proj, sorted(i + 1 for i in range(5) if y_proj[i] == 1),
         c_proj @ y_proj, BUDGET))
print("  逻辑约束检验: 互斥 y1+y2 = %.0f <= 1 ✔；依赖 y3 = %.0f <= y1 = %.0f ✔"
      % (y_proj[0] + y_proj[1], y_proj[2], y_proj[0]))
print("  大 M 触发检验: y2 = %d，总人力 = %.0f <= 25 ✔（若 y2=0 则约束自动失效）"
      % (y_proj[1], h_proj @ y_proj))
res_proj_lp = linprog(c=-p_proj, A_ub=A_proj, b_ub=b_proj,
                      bounds=[(0, 1)] * 5, method="highs")
print("  LP 松弛值 = %.1f，0-1 最优值 = %.0f，间隙 = %.1f%%（逻辑约束使问题明显收紧）"
      % (-res_proj_lp.fun, z_proj, (-res_proj_lp.fun - z_proj) / (-res_proj_lp.fun) * 100))

# ========== 9. 绘制第四节要求的 4 张图（保存到 figures/，前缀 zolp_） ==========

# ---- 图 ① 项目/物品选择结果条形图（选中 vs 未选中，两色标注）----
fig1, ax1 = plt.subplots(figsize=(12, 5))
bar_colors = [C_OPT if x_bnb[i] == 1 else C_UNSEL for i in range(n_items)]
ax1.bar(range(n_items), values, color=bar_colors, edgecolor="white")
for i in range(n_items):
    ax1.text(i, values[i] + 2, "w=%d" % weights[i], ha="center", fontsize=8,
             color="#37474F")
ax1.set_xticks(range(n_items))
ax1.set_xticklabels(["物品 %d" % (i + 1) for i in range(n_items)], fontsize=9)
ax1.set_ylabel("价值 v_i")
ax1.set_xlabel("物品编号（柱顶标注重量 w_i）")
ax1.set_title("0-1 背包最优选择方案：选中 %d 件，总价值 %d，总重量 %d/%d"
              % (int(sum(x_bnb)), z_bnb, used_w_opt, capacity))
ax1.legend(handles=[Patch(color=C_OPT, label="选中（x_i = 1）"),
                    Patch(color=C_UNSEL, label="未选中（x_i = 0）")],
           loc="upper right")
fig1.tight_layout()
fig1.savefig("figures/zolp_selection_bar.png", dpi=150)

# ---- 图 ② 背包视角的价值-重量散点图（标注选中与否 + 容量参考线）----
fig2, ax2 = plt.subplots(figsize=(11, 6))
for i in range(n_items):
    in_opt = (x_bnb[i] == 1)
    in_gr = (g_sel[i] == 1)
    if in_opt and in_gr:
        col = C_OPT          # 最优与贪心都选
    elif in_opt:
        col = C_LP           # 仅最优选（贪心漏掉的关键物品）
    elif in_gr:
        col = C_GREEDY       # 仅贪心选（贪心误装的低价值物品）
    else:
        col = C_UNSEL        # 都没选
    ax2.scatter(weights[i], values[i], s=170, c=col, edgecolors="#37474F",
                linewidths=0.7, zorder=3)
    ax2.annotate("%d" % (i + 1), (weights[i], values[i]),
                 textcoords="offset points", xytext=(7, 7), fontsize=9, zorder=4)
ax2.axvline(capacity, color="#E74C3C", linestyle="--", linewidth=1.6,
            label="容量参考线 C = %d" % capacity)
ax2.text(2, 96, "最优方案累计重量 = %d ≤ %d（满足容量约束）" % (used_w_opt, capacity),
         fontsize=9, bbox=dict(boxstyle="round,pad=0.35",
                               facecolor="#FFF9E6", edgecolor="#E8930C"))
ax2.annotate("贪心陷阱：物品 3（w=15, v=60）\n密度高，但贪心先装了物品 1、5 占满容量，\n装不下它，少赚 60",
             xy=(weights[2], values[2]), xytext=(weights[2] + 12, values[2] + 2),
             fontsize=9, color="#2E8B57",
             arrowprops=dict(arrowstyle="->", color="#2E8B57", lw=1.2))
ax2.set_xlabel("重量 w_i")
ax2.set_ylabel("价值 v_i")
ax2.set_xlim(0, 76)
ax2.set_ylim(-2, 102)
ax2.set_title("价值-重量散点图：最优方案 vs 贪心方案（容量参考线 C = 70）")
ax2.legend(handles=[
    Patch(color=C_OPT, label="最优与贪心都选"),
    Patch(color=C_LP, label="仅最优选（贪心漏掉）"),
    Patch(color=C_GREEDY, label="仅贪心选（误装）"),
    Patch(color=C_UNSEL, label="都没选"),
    plt.Line2D([0], [0], color="#E74C3C", linestyle="--",
               label="容量参考线 C = 70")],
    loc="lower right", fontsize=8)
fig2.tight_layout()
fig2.savefig("figures/zolp_value_weight.png", dpi=150)

# ---- 图 ③ 分支定界搜索树 ----
# 布局：纵轴 = 深度（根在上），横轴 = 中序遍历序号
#（x=1 子树的节点排在父节点左边、x=0 子树排在右边，保证边互不交叉）
children = [[] for _ in bnb_nodes]
for nd in bnb_nodes:
    if nd["parent"] is not None:
        children[nd["parent"]].append(nd["id"])
depth_cache = {}
def node_depth(i):
    if i not in depth_cache:
        depth_cache[i] = (0 if bnb_nodes[i]["parent"] is None
                          else node_depth(bnb_nodes[i]["parent"]) + 1)
    return depth_cache[i]
xpos = {}
counter = [0]
def inorder(i):
    if len(children[i]) > 0:
        inorder(children[i][0])
    xpos[i] = counter[0]
    counter[0] += 1
    if len(children[i]) > 1:
        inorder(children[i][1])
inorder(0)
path_set = set()                     # 最终最优解的搜索路径（根 -> 最优整数解节点）
i = inc_node_id
while i is not None:
    path_set.add(i)
    i = bnb_nodes[i]["parent"]

fig3, ax3 = plt.subplots(figsize=(14, 7))
for nd in bnb_nodes:                 # 先画边（父 -> 子）
    if nd["parent"] is None:
        continue
    p = bnb_nodes[nd["parent"]]
    on_path = (nd["id"] in path_set and nd["parent"] in path_set)
    ax3.plot([xpos[p["id"]], xpos[nd["id"]]],
             [-node_depth(p["id"]), -node_depth(nd["id"])],
             color="#E74C3C" if on_path else "#9E9E9E",
             lw=2.2 if on_path else 1.0, zorder=1, solid_capstyle="round")
for nd in bnb_nodes:                 # 再画节点
    col = {"branch": C_BRANCH, "pruned": C_PRUNE, "integer": C_INT}[nd["outcome"]]
    is_inc = (nd["id"] == inc_node_id)
    x, y = xpos[nd["id"]], -node_depth(nd["id"])
    ax3.scatter(x, y, s=560 if is_inc else 420, c=col,
                edgecolors="#E74C3C" if is_inc else "#37474F",
                linewidths=1.8 if is_inc else 0.8, zorder=3)
    btxt = ("%.0f" % nd["bound"]
            if abs(nd["bound"] - round(nd["bound"])) < 1e-9
            else "%.1f" % nd["bound"])
    ax3.text(x, y, btxt, ha="center", va="center", fontsize=6.5, zorder=4)
    if nd["parent"] is not None:     # 边上标注分支决策（x_k = 1 / x_k = 0）
        px, py = xpos[nd["parent"]], -node_depth(nd["parent"])
        ax3.text((px + x) / 2, (py + y) / 2 + 0.15, nd["branch"],
                 ha="center", va="bottom", fontsize=6.5, color="#37474F", zorder=4)
    if nd["outcome"] == "pruned":    # 叶节点结果标注
        ax3.text(x, y - 0.60, "剪枝", ha="center", va="top", fontsize=6.5,
                 color="#7F8C8D", zorder=4)
    elif nd["outcome"] == "integer":
        ax3.text(x, y - 0.60, "整数解" + ("★" if is_inc else ""),
                 ha="center", va="top", fontsize=6.5, color="#B9770E", zorder=4)
ax3.text(xpos[0], -node_depth(0) + 0.42, "根节点（LP 松弛）", ha="center",
         fontsize=7, color="#2E86C1")
ax3.set_xlim(-1.2, len(bnb_nodes) + 0.2)
ax3.set_ylim(-max(depth_cache.values()) - 1.7, 0.9)
ax3.axis("off")
ax3.set_title("分支定界搜索树：共 %d 个节点（%d 分支 / %d 剪枝 / %d 整数解），红色路径为最优解"
              % (len(bnb_nodes), n_branch, n_pruned, n_integer), fontsize=12)
ax3.legend(handles=[
    Patch(color=C_BRANCH, label="分支节点（继续展开）"),
    Patch(color=C_PRUNE, label="剪枝节点（上界 ≤ 下界）"),
    Patch(color=C_INT, label="整数可行解（更新下界）"),
    plt.Line2D([0], [0], color="#E74C3C", lw=2.2, label="最优解搜索路径")],
    loc="upper left", fontsize=8, framealpha=0.9)
fig3.tight_layout()
fig3.savefig("figures/zolp_bnb_tree.png", dpi=150)

# ---- 图 ④ 最优目标值 vs 贪心解对比柱状图（展示精确解优于贪心）----
fig4, ax4 = plt.subplots(figsize=(8, 5.5))
names4 = ["LP 松弛上界", "最优解\n（分支定界）", "贪心解\n（价值密度）"]
vals4 = [lp_ub, z_bnb, g_val]
cols4 = [C_LP, C_OPT, C_GREEDY]
bars4 = ax4.bar(names4, vals4, color=cols4, width=0.5,
                edgecolor="#37474F", linewidth=0.8)
for b, v in zip(bars4, vals4):
    ax4.text(b.get_x() + b.get_width() / 2, v + 6, "%.0f" % v,
             ha="center", fontsize=12, fontweight="bold")
ax4.annotate("", xy=(2, g_val), xytext=(1, z_bnb),
             arrowprops=dict(arrowstyle="<->", color="#E74C3C", lw=1.4))
ax4.text(1.5, (z_bnb + g_val) / 2,
         "精确解比贪心\n高 %.0f（提升 %.1f%%）" % (gap_g, rel_g),
         ha="center", va="center", fontsize=10, color="#E74C3C",
         bbox=dict(boxstyle="round,pad=0.3", facecolor="white",
                   edgecolor="#E74C3C"))
ax4.set_ylabel("总价值")
ax4.set_ylim(0, 660)
ax4.set_title("最优目标值 vs 贪心解 vs LP 松弛上界")
fig4.tight_layout()
fig4.savefig("figures/zolp_greedy_compare.png", dpi=150)

# ========== 10. 显示图形 ==========
print("=" * 66)
print("4 张图已保存到 figures/ 目录：")
for f in ["zolp_selection_bar.png", "zolp_value_weight.png",
          "zolp_bnb_tree.png", "zolp_greedy_compare.png"]:
    print("  figures/" + f)
plt.show()   # 本地弹出 4 个图形窗口，逐个关闭后脚本结束；
             # 服务器等无图形界面环境用 MPLBACKEND=Agg 运行时自动跳过

6.3 运行方式说明

1. 将 6.2 节的代码按顺序拼接保存为 09_zolp_demo.py（放在本文档所在目录，保证 figures/ 相对路径正确）；
2. 本机运行：.venv/bin/python 09_zolp_demo.py；
3. 无图形界面（服务器、CI）运行：MPLBACKEND=Agg .venv/bin/python 09_zolp_demo.py（代码保留 plt.show()，Agg 后端下它自动跳过，图片仍会正常保存）；
4. 预期行为：控制台依次打印实例数据、贪心解、LP 松弛、分支定界过程、milp 与枚举对照、第三节全部 8 组指标、项目选择示例结果；figures/ 下生成 4 张 PNG。

七、结果解读与注意事项

7.1 运行输出解读（以本例合成数据为例）

运行 6.2 节代码（np.random.seed(42)，容量 $C=70$），得到如下关键结果（以下数值与真实运行输出一致）：

最优方案与指标解读：

• 最优目标值 $z^{*} = 618$：手写分支定界、scipy.milp、暴力枚举三种方法结果完全一致（三方法互验是论文可靠性的直接证据）。最优方案装入 9 件物品 {3, 6, 9, 10, 11, 12, 13, 14, 15}，总重量 68 ≤ 70；
• LP 松弛 $z_{LP} = 627$：闭式公式与 linprog 对照一致。松弛解把物品 3 拆成 $x_3 = 0.6$ 件（剩余容量 9 / 重量 15），这显然不是现实可行方案——"分数个物品"正是 0-1 条件不可忽略的直观证据；
• 积分间隙 IG = 1.44%：$z_{LP}$ 只比 $z^{*}$ 高 9，说明松弛非常"紧"，分支定界剪枝高效（这也解释了为什么 23 个节点就能证明全局最优）；
• 约束满足率 = 47.27%（15489/32768）：约一半的 0-1 组合满足容量约束，说明容量约束"适中"——既不苛刻（可行解稀缺）也不形同虚设；
• 资源利用率 = 97.14%（68/70）：最优方案几乎装满背包，容量是真正的瓶颈资源；
• 选中决策数 $k = 9$：贪心装了 10 件反而价值更低（593 < 618），印证"件数多 ≠ 价值高"；
• 贪心差距 = 25，相对提升 4.22%：贪心按价值密度装入了物品 1（$v=2$）、物品 5（$v=33$）后，剩余容量 17 装不下物品 3（$w=15, v=60$）；最优解放弃 1、5（合计 35）改装物品 3（60），净赚 25。这是价值密度贪心的经典失效模式；
• 求解时间：手写分支定界与 milp 均为毫秒级（暴力枚举约零点几秒）。分支定界共 23 个节点（11 个分支节点、10 个剪枝节点、2 个整数可行解节点），先找到价值 591 的整数解（节点 4，走 $x_3=1$ 分支），随后在节点 17 找到价值 618 的整数解并证明最优。

附加示例（项目选择）解读：milp 求得最优利润 135 万元，选择项目 {2, 4, 5}，总成本 55 ≤ 60。逻辑约束全部满足：互斥 $y_1 + y_2 = 1 \le 1$（两个互斥项目恰好选了项目 2）；依赖 $y_3 = 0 \le y_1 = 0$（项目 1 没选，项目 3 自然被禁）；大 M 约束被触发（$y_2 = 1$ 时总人力 20 ≤ 25）。LP 松弛值为 152.5，间隙约 11.5%，明显大于背包例——逻辑约束（尤其是大 M）会显著"撑松"LP 松弛，这是混合 0-1 模型求解慢于纯背包的常见原因。

7.2 四张图的解读（本例）

• 图① 选择结果条形图：绿色柱恰好覆盖价值最高的几件（92、91、89、76 全部入选）；物品 1、5 灰色——它们被贪心误装而被最优解舍弃，与图②互为印证；
• 图② 价值-重量散点图：蓝点物品 3 是"仅最优选"的唯一物品（贪心陷阱，已用箭头标注）；橙点物品 1、5 是"仅贪心选"（误装）；其余绿点（8 件）为两者共识，灰点为两者都不选。红色容量参考线 $C=70$ 提醒：容量约束作用在累计重量上（单件重量最大仅 20，任何单件都装得下，冲突发生在"组合"层面）；文本框显示最优方案累计重量 68 ≤ 70；
• 图③ 分支定界搜索树：根节点上界 627（LP 松弛）。先走 $x_3=1$ 分支（左半树），在节点 4 得到整数解 591 作为第一个下界，其子树（上界 578.2、578 等）随即被剪；回到上层走 $x_5=0$ 分支，最终沿红色路径 $x_3=1 \to x_5=0 \to x_2=0 \to x_7=0 \to x_8=0 \to x_4=0 \to x_1=0$ 在节点 17 找到 618 并证明最优（右半树所有上界 ≤ 618，全部剪掉）。整棵树只有 23 个节点，远小于 $2^{15}=32768$——这就是"隐枚举"的含义；
• 图④ 精确解 vs 贪心对比柱状图：LP 上界 627 > 最优 618 > 贪心 593，单调关系正确；双向箭头标注差距 25（提升 4.2%），直接支撑论文中"贪心不可接受、精确求解必要"的论点。

7.3 常见坑与应对

1. 大 M 取值不当：$M$ 太小会切掉合法解（模型直接错误）；$M$ 太大会造成数值问题、LP 松弛变松、求解变慢。应对：$M$ 取"紧上界"，如 $M = \max a^\top x - b$ 在可行域内的最大值，或用资源总量自然上限；论文中注明 $M$ 的取值依据。
2. 逻辑约束方向写反：$x_2 \le x_1$（选 2 必须选 1）与 $x_1 \le x_2$（选 1 必须选 2）含义相反。应对：建模后枚举该约束涉及变量的全部 4 种取值组合逐一验证；代码中用求解结果回代检验（如 6.2 节的"逻辑约束检验"打印）。
3. 忽略 0-1 条件直接松弛：拿 LP 松弛解当最终方案——本例如 $x_3=0.6$ 是"0.6 个物品"，不可执行；对松弛解四舍五入又可能违反约束（经典翻车点）。应对：0-1 问题必须用 milp（设置 integrality 与 0-1 界），LP 松弛只作上界参考。
4. 规模大时 milp 变慢：0-1 问题是 NP 难的，变量从几十增加到几百，求解时间可能从毫秒变小时。应对：优先削减 0-1 变量个数（合并决策、利用对称性）；设置 milp(options={"time_limit": ...}) 限制时间并接受带间隙的近似解；或改用问题特有算法（背包 DP、指派匈牙利算法）与启发式。
5. 数值容差：求解器可能返回 $x_i = 0.9999999$，直接当整数用会出错。应对：用 res.x > 0.5 判断 0-1 取值，并把取整后的方案回代约束与目标验证。
6. 忘设 integrality 或 bounds：只写约束却忘记 integrality=np.ones(n)，求解器会按连续变量求解；忘记 bounds=(0,1) 则整数变量可能取 2、3。应对：封装一个"建 0-1 变量"的小函数统一设置。
7. 初始下界缺失：分支定界长时间找不到整数解，剪枝失效、树疯长。应对：先用贪心/启发式解喂一个初始下界（本文手写实现虽未用，但 7.3 建议生产代码中加上：incumbent = greedy_value）。

7.4 竞赛论文写作建议（话术模板）

建模段（通用模板）：

设 0-1 变量 $x_i$：$x_i = 1$ 表示选择第 $i$ 个项目（物品/候选点），$x_i = 0$ 表示不选（$i=1,2,\dots,n$）。建立 0-1 规划模型：

$\max \; \sum_{i=1}^{n} c_i x_i \qquad \text{s.t.} \quad \sum_{i=1}^{n} a_{ij} x_i \le b_j \; (j=1,\dots,m), \quad x_i \in \{0,1\}$

其中约束 $\sum_i a_{ij} x_i \le b_j$ 依次表示预算限制、互斥条件（如 $x_1 + x_2 \le 1$）、依赖条件（如 $x_3 \le x_1$）等。

求解与结论段：

建立 0-1 规划模型，$x_i = 1$ 表示选择项目 $i$，采用分支定界法求解，最优方案共选中 5 个项目，总收益…，较贪心策略提升 12%（贪心策略无最优性保证）。LP 松弛上界为…，与最优值的间隙仅 1.4%，说明松弛紧致、求解可靠。三种方法（分支定界、milp 求解器、暴力枚举）结果一致，验证了模型的正确性。

套用本文实例时，将模板中的占位数字替换为实际输出即可："最优方案共选中 9 件物品，总收益 618，较贪心策略提升 4.22%（贪心策略收益 593）；LP 松弛上界为 627，间隙 1.44%"。注意论文中的每个数字都要能在自己的程序输出里找到出处。

对比与敏感性段：

为论证精确求解的必要性，将 0-1 规划最优解与贪心近似解对比：贪心按价值密度装填的收益为 593，低于最优值 618（差距 4.2%），原因是贪心优先装入了低价值物品 1、5 占满容量，导致高价值物品 3 无法装入——贪心算法存在系统性缺陷，精确求解是必要的。进一步，对预算 $b$ 做灵敏度分析：当预算在 $[50, 90]$ 内变动时，最优方案在 3 个方案之间切换，说明资源配置决策对预算变化敏感，管理者应审慎确定预算。

模型推广段：

该模型可推广到一般情形：当部分资源有固定启动成本时，引入辅助 0-1 变量 $y_j$ 与约束 $x_j \le M y_j$ 即得混合 0-1 规划；当决策规模增大至数百个变量时，可采用遗传算法等启发式求解，并以本文精确解作为小规模基准评估启发式的近似比。

八、延伸阅读

1. 混合 0-1 规划与固定成本问题：当"是否生产/建设"（0-1）与"生产/分配多少"（连续）同时出现时，用 $x_j \le M_j y_j$ 把两类变量耦合。经典文献：H. P. Williams, Model Building in Mathematical Programming（第五版），是 0-1 建模技巧（逻辑约束、大 M）的百科全书式参考；
2. 动态规划解 0-1 背包：状态转移 $f(i, j) = \max\{ f(i-1, j),\; f(i-1, j - w_i) + v_i \}$，时间 $O(nC)$、空间可滚动优化到 $O(C)$。当容量 $C$ 不大时 DP 比分支定界更稳；DP 与 0-1 规划互为验证是竞赛加分点；
3. 集合覆盖与选址问题：p-中位问题（选 $p$ 个设施使总距离最小）、最大覆盖问题（有限预算下覆盖尽量多需求点）在应急管理、物流、通信基站选址中应用广泛。入门：Toregas 等 1971 年经典消防站选址论文；进阶：Daskin, Network and Discrete Location；
4. TSP 的 0-1 建模：变量 $x_{ij} \in \{0,1\}$ 表示是否走边 $(i,j)$，需要子回路消除约束：Dantzig–Fulkerson–Johnson（DFJ）割 $\sum_{i \in S, j \notin S} x_{ij} \ge 2$（指数多条，分支-割平面动态添加）或 Miller–Tucker–Zemlin（MTZ）大 M 形式 $u_i - u_j + n x_{ij} \le n - 1$——是"大 M 建模 + 指数约束动态生成"的绝佳教材；
5. 启发式算法：变量上百时精确求解不现实，改用遗传算法、模拟退火、大邻域搜索等；竞赛中常用模式：小规模精确解 + 大规模启发式 + 以小规模为例评估近似质量（近似比/平均偏差）;
6. 割平面与分支-割平面：Gomory 割平面、覆盖不等式（如背包的 $x_1 + x_2 \le 1$ 一类"提升割"）可以进一步收紧 LP 松弛，是现代求解器（HiGHS、Gurobi、CPLEX）默认技术栈；scipy 的 milp 中可通过 options={"mip_rel_gap": ...} 控制求解精度与提前停止。