如何从Python的linprog不可行线性规划输出中获取不可行性证明

核心原理 #

你需要的非负向量v是Farkas引理定义的原问题不可行性证书：当原问题Ax <= b, x >= 0无可行解时，必然存在满足v^T*A >= 0、v^T*b < 0的非负向量v。

最简单实现方案 #

优先用SciPy内置的HiGHS求解器直接提取对偶乘子，不需要额外构造问题：

1. 调用linprog时指定求解器参数method='highs'，替换默认的旧版单纯形实现
2. 当求解返回status=2（不可行）时，直接读取返回结果的ineqlin.marginals属性，得到的就是你需要的非负向量v

注：HiGHS是SciPy 1.7.0及以上版本内置的线性规划求解器，对不可行、无界等边界场景的对偶信息输出支持更完善。

旧版SciPy兼容方案 #

如果你的SciPy版本低于1.7.0，手动构造如下线性规划求解即可：

• 优化目标：min (v^T @ b)
• 约束条件：
  • A.T @ v >= 0
  • v >= 0
  • sum(v) = 1（添加该约束避免无界的零解）
    用linprog求解上述问题，得到的最优解v就是所需的不可行性证明。

验证注意事项 #

你的求解输出里Phase1伪目标值为4.5，远大于默认公差，验证v的约束时可以适当放宽数值公差，不要硬卡严格等于0的判定条件。

内容的提问来源于stack exchange，提问作者dbradac