📚 课程目录第4章不可行性检测方法

4. 不可行性检测方法

在约束冲突诊断的整个链条中，第一步不是修复，而是确认模型确实不可行。很多初学者把"求解器返回无解"直接等同于"约束写错了"，但实际原因可能是数值病态、变量界设置过紧、求解器迭代上限被触发，甚至只是模型规模超出免费版限制。因此，本节要解决的核心问题是：如何从算法层面的冲突信号和求解器层面的状态码两个维度，快速、可靠地判定一个线性规划模型是否真的不可行。

一、单纯形法中的不可行判定：人工变量与检验数

标准形线性规划要求所有约束为等式且右端项非负。当原模型含有"≥"或"="约束时，单纯形法需要引入人工变量构造初始基可行解。判定不可行的经典依据是：在最优表中，若某个人工变量仍以正基变量身份留在基中，且其取值大于零，则原问题不可行。直观理解是，人工变量是为了"凑出"初始可行基而虚构的变量，如果最终它无法被驱赶到零，说明原约束系统本身不存在可行点。

以一个教学示例说明。设模型为：

max  z = 3x1 + 2x2
s.t. x1 + x2 ≤ 4
     x1 + x2 ≥ 6
     x1, x2 ≥ 0

两条约束分别要求 x1+x2 不超过 4 又不小于 6，显然矛盾。引入松弛变量 s1 与剩余变量 s2、人工变量 a1 后，第一阶段目标为 min w = a1。迭代结束时 a1 = 2 > 0，第一阶段最优值 w* = 2 ≠ 0，直接判定原问题不可行。这里的关键判据是第一阶段最优目标值是否为零，而不是"是否找到解"。

二、两阶段法与大M法的冲突信号差异

两阶段法把可行性检测独立成第一阶段，信号非常干净：第一阶段最优值 w* > 0 即不可行，w* = 0 则进入第二阶段优化原目标。它的优点是判定逻辑清晰、数值上更稳健，缺点是求解器内部需要跑两遍单纯形。

大M法则把人工变量以惩罚系数 M 并入原目标，构造 min z = cᵀx + M·Σaᵢ。它的冲突信号表现为：最优解中仍存在非零人工变量，且目标值中出现与 M 同量级的项。大M法的问题在于 M 的取值高度依赖人工经验——M 太小可能压不住人工变量导致误判可行，M 太大则引起系数矩阵数量级悬殊、数值不稳定。因此工程实践中，商业求解器普遍采用两阶段法或更稳健的界变换技术，大M法更多出现在教材推导和手工计算中。

判断口诀：两阶段法看"第一阶段目标值是否为零"；大M法看"最优解中人工变量是否归零"。两者本质相同，都是检验人工变量能否被完全驱逐出可行基。

三、求解器状态码：工程中最快的判定入口

实际建模时，我们很少手工跑单纯形表，而是直接读取求解器返回的状态码。不同求解器的枚举名称不同，但语义高度一致，可归纳为下表：

状态语义	Gurobi	CPLEX	HiGHS / 常见开源	含义与处置
最优	OPTIMAL	Optimal	kOptimal	正常，无需诊断
不可行	INFEASIBLE	Infeasible	kInfeasible	约束系统无可行点，进入冲突诊断
无界	UNBOUNDED	Unbounded	kUnbounded	目标可无限改进，检查遗漏约束
不可行或无界	INF_OR_UNBD	InfOrUnbd	—	需关闭 presolve 后重解以区分
达到时限/迭代上限	TIME_LIMIT / ITERATION_LIMIT	AbortTimeLim	kTimeLimit	非结论性，不可当作不可行
数值问题	NUMERIC	Numerical	—	系数尺度或容差问题，先做缩放

状态码使用中有三个高频陷阱。第一，INF_OR_UNBD 不是不可行，它只是预求解阶段无法区分两种情形，必须设置 Presolve=0 后重新求解才能定性。第二，时限中止不等于不可行，把 TIME_LIMIT 误读为 INFEASIBLE 会导致对本来可行的模型做无谓的约束删改。第三，NUMERIC 状态要先排查数值病态，例如把系数从 1e-6 到 1e6 混在同一约束中，此时求解器可能因容差误报不可行。

四、实操：用状态码快速筛查不可行模型

下面以 Python 调用 Gurobi 为例，展示一个可直接复用的判定片段。核心思路是：先读状态码，遇到 INF_OR_UNBD 时关闭预求解重解，遇到 INFEASIBLE 再进入冲突诊断。

import gurobipy as gp
from gurobipy import GRB

m = gp.Model("check")
x = m.addVar(name="x"); y = m.addVar(name="y")
m.addConstr(x + y <= 4)
m.addConstr(x + y >= 6)
m.setObjective(3*x + 2*y, GRB.MAXIMIZE)
m.optimize()

if m.Status == GRB.INFEASIBLE:
    print("确认不可行，进入冲突诊断")
elif m.Status == GRB.INF_OR_UNBD:
    m.setParam("Presolve", 0)
    m.optimize()
    print("重解后状态:", m.Status)
elif m.Status == GRB.TIME_LIMIT:
    print("未得结论，不可判为不可行")
else:
    print("状态码:", m.Status)

该示例中，模型因 x+y≤4 与 x+y≥6 矛盾，预期返回 INFEASIBLE。若实际返回 INF_OR_UNBD，说明预求解未能定性，关闭 Presolve 后重解通常可得到明确结论。这一步看似简单，却是很多工程事故的源头——把"未定性"当成"不可行"，后续所有冲突诊断都建立在错误前提上。

五、判定之后：为冲突诊断准备输入

确认不可行只是起点。为了让后续的冲突诊断（如 IIS、删除过滤、弹性松弛）有据可依，建议在判定阶段同步记录三项信息：模型规模（变量数、约束数）、状态码原文、以及是否触发过 Presolve 关闭重解。这三项构成诊断日志的最小字段集，能帮助你在多人协作或跨版本复现时快速定位问题。尤其当同一模型在不同求解器版本下状态码不一致时，这份日志往往是唯一可靠的对照依据。

切勿在状态码为 TIME_LIMIT、NUMERIC 或 INF_OR_UNBD 时直接删除约束。先定性、再诊断、后修复，顺序不可颠倒。

小结本节要点：算法层面，两阶段法看第一阶段目标值是否为零，大M法看人工变量是否归零，二者本质一致；工程层面，状态码是最快的判定入口，但必须区分"确认不可行"与"未得结论"两类状态。只有把这两层信号对齐，才能为后续的冲突定位提供可信的起点。