如何在Python中用迭代方法求解线性方程组？

Question

我有一个在 Python 中表示为字符串的线性方程组，我需要为每个变量找到同时满足所有方程而不矛盾的整数值（正或负）。变量和方程的数量可能会有所不同，因此解决方案应相应调整。

这是此类方程组的一个示例：

from sympy import symbols, Eq, solve
import re

system_equations = [
'5 = X0 + Y0', 
'6 = X0 + Y1', 
'5 = X0 + Y3', 
'5 = X0 + Y4', 
'3 = X1 + Y2', 
'0 = X2 + Y2', 
'1 = X2 + Y4'
]


# Extract all variable names from the system of equations
variable_names = list(set(re.findall(r'[XY]\d+', ' '.join(system_equations))))

# Create symbols for the variables
variables = symbols(' '.join(variable_names))

请务必记住，程序必须适应变量（Xi 和 Yj）或/和方程的数量，这只是一个示例，其中我们有 8 个未知数和 7 个线性方程。

对于此示例，其中存在同时满足所有方程（无矛盾）的整数值的可能解决方案之一可能是：

# a (posible) correct output
values_of_int_decomposition_variables = [['X0', 2], ['X1', 1], ['X2', -2], ['Y0', 3], ['Y1', 4], ['Y2', 2], ['Y3', 3], ['Y4', 3]]

请注意，如果他们设法满足所有方程：

ij_number_to_decompose = Xi + Yj

5 = 2 + 3
6 = 2 + 4
5 = 2 + 3
5 = 2 + 3
3 = 1 + 2
0 = 2 + (-2)
1 = -2 + 3

对于值为 0 的方程，必须将其分解为 2 个大小相等但符号相反的值（X2 和 Y2 应该具有相反的值）

Answer 1

您可以使用 PuLP 或 SciPY 库来求解线性方程。

from sympy import symbols, Eq, solve
import re
from pulp import LpMaximize, LpProblem, LpVariable, value

system_equations = [
    '5 = X0 + Y0',
    '6 = X0 + Y1',
    '5 = X0 + Y3',
    '5 = X0 + Y4',
    '3 = X1 + Y2',
    '0 = X2 + Y2',
    '1 = X2 + Y4'
]

variable_names = list(set(re.findall(r'[XY]\d+', ' '.join(system_equations))))

variables = {var: LpVariable(var, lowBound=None, cat='Integer') for var in variable_names}

prob = LpProblem("IntegerLinearProgramming", LpMaximize)
print(variables)
for equation in system_equations:
    lhs, rhs = equation.split('=')
    lhs = lhs.strip()
    rhs = rhs.strip()
    print(rhs)
    terms = re.findall(r'([+-]?\s*\d*\s*\*?\s*[XY]\d+)', rhs)
    constraint = sum(eval(term, {}, variables) for term in terms) == int(lhs)
    prob += constraint

prob.solve()

values_of_int_decomposition_variables = [[var, int(value(variables[var]))] for var in variable_names]

print(values_of_int_decomposition_variables)