scipy.linprog可行性Bug：存在可行点却返回不可行状态？

你遇到的情况是scipy.optimize.linprog误判线性规划问题为不可行，但实际存在可行点。这主要和求解器的数值特性、初始搜索策略有关，具体原因和解决办法如下：

原因解析 #

scipy 1.11.0中linprog默认使用HiGHS求解器，该求解器在处理可行域远离原点、或约束条件数值差异较大的问题时，可能因初始搜索范围有限、数值精度限制，无法触及可行域，进而误判问题不可行。你提供的可行点x0数值量级达数百，远超出求解器默认的初始搜索区间，导致求解器在初始迭代中找不到可行区域。

解决办法 #

1. 显式提供初始可行点引导求解器 #

直接将已知的可行点传入x0参数，让求解器从该点出发确认可行域存在：

import numpy as np
from scipy.optimize import linprog

A_ub = np.array(
      [[-0.15729144,  0.29943807,  0.29311432],
       [-1.32475528, -2.1125364 , -1.55138585],
       [ 1.00861965,  0.53283629, -0.14939833],
       [ 1.07581479,  0.164022  , -1.19889684]])

b_ub = -np.ones(4)
x0 = np.array([229.1748166, -507.05266751, 512.14005547])

result = linprog(np.zeros(3),
                 A_ub=A_ub,
                 b_ub=b_ub,
                 x0=x0)

print(result)

运行后求解器会返回正确的可行状态与可行点。

2. 缩放约束条件缩小数值量级 #

对约束矩阵A_ub和b_ub进行等比例缩放，让可行点的数值量级更接近原点，降低求解器的数值计算压力：

# 缩放系数选择100，保持约束等价性
scaled_A_ub = A_ub / 100
scaled_b_ub = b_ub / 100

result = linprog(np.zeros(3),
                 A_ub=scaled_A_ub,
                 b_ub=scaled_b_ub)

# 还原得到原问题的可行点
original_x = result.x * 100
print("还原后的可行点：", original_x)
print("约束验证结果：", (A_ub @ original_x <= b_ub).all())

关于linprog的返回逻辑 #

当问题确实存在可行点时，linprog应当返回可行状态（success=True、status=0）及对应可行点。此次误判是求解器在特定数值场景下的局限性，而非linprog的设计逻辑问题。

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