如何使用Scipy求解带布尔约束的线性方程组，并确定变量的确定取值（必为0或必为1）

嘿，这个问题我刚好有思路！你不需要生成所有解就能找到那些必为0或1的变量，用Scipy的linprog就能搞定，核心思路是对每个变量分别计算它在可行解中的最小和最大可能值——如果最小值和最大值都是1，那它肯定在所有解里都是1；如果都是0，那它肯定全是0。咱们一步步来：

核心逻辑 #

对于每个变量x_j：

• 要判断它是否必须为1：我们可以尝试在约束下最小化x_j，如果最小结果是1，说明所有可行解里x_j都不能小于1（也就是只能是1）。
• 要判断它是否必须为0：我们尝试在约束下最大化x_j，如果最大结果是0，说明所有可行解里x_j都不能大于0（也就是只能是0）。

因为linprog默认是求最小值，所以最大化x_j可以转化为求-x_j的最小值，结果取反即可。

代码实现（以你的示例为例） #

咱们用你给出的方程组来写代码验证：

import numpy as np
from scipy.optimize import linprog

# 定义约束条件
A_eq = np.array([
    [1, 1, 1, 0],  # x1 + x2 + x3 = 2
    [1, 0, 0, 1],  # x1 + x4 = 1
    [1, 1, 0, 0]   # x1 + x2 = 1
])
b_eq = np.array([2, 1, 1])
bounds = [(0, 1)] * 4  # 变量都是0或1
num_vars = len(bounds)

# 存储每个变量的最小和最大可能值
var_min = np.zeros(num_vars)
var_max = np.zeros(num_vars)

for j in range(num_vars):
    # 最小化x_j：目标函数第j位为1，其余为0
    c_min = np.zeros(num_vars)
    c_min[j] = 1
    res_min = linprog(c_min, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs-ipm')
    
    # 最大化x_j：等价于最小化 -x_j，结果取反
    c_max = np.zeros(num_vars)
    c_max[j] = -1
    res_max = linprog(c_max, A_eq=A_eq, b_eq=b_eq, bounds=bounds, method='highs-ipm')
    
    if res_min.success and res_max.success:
        var_min[j] = res_min.x[j]
        var_max[j] = -res_max.fun  # 因为res_max.fun是min(-x_j)，所以max(x_j) = -res_max.fun
    else:
        # 没有可行解的情况，这里可以根据需求处理
        print(f"变量x{j+1}不存在可行解")

# 确定必为1和必为0的变量（用np.isclose处理浮点数精度问题）
guaranteed_1 = [f"x{j+1}" for j in range(num_vars) if np.isclose(var_min[j], 1) and np.isclose(var_max[j], 1)]
guaranteed_0 = [f"x{j+1}" for j in range(num_vars) if np.isclose(var_min[j], 0) and np.isclose(var_max[j], 0)]

print("必为1的变量：", guaranteed_1)
print("必为0的变量：", guaranteed_0)

运行这段代码后，输出会是：

必为1的变量： ['x3']
必为0的变量： []

和你给出的示例结果完全一致！

处理带系数的情况 #

如果你的方程组里有小系数（比如x1 + 2*x3 + x4 = 3），这个方法同样适用——只需要把A_eq里的对应系数改成实际值就行，比如把某一行改成[1, 0, 2, 1]，约束逻辑完全不变。

为什么这个方法比枚举所有解更好？ #

枚举所有解在变量多的时候会非常慢，但这个方法只需要对每个变量跑两次线性规划，效率高很多，尤其适合你说的“变量多但可行解少”的场景。而且linprog的highs-ipm方法处理这类整数约束（虽然我们用的是连续边界，但结果会收敛到0/1，因为约束是线性且布尔的）的性能很不错。

备注：内容来源于stack exchange，提问作者Salvador Dali