如何在 Python 中获得欠定线性方程组的所有可能解？

Question

我有兴趣获得 Python 中的欠定线性问题的所有可能解决方案。更具体地说，假设我们只有一个方程、几个变量，并且我们想用正整数来求解它。这可以使用 SymPy 在 Python 中表达。让我介绍一个例子：

import numpy as np
import sympy as sp

coeff = [2, 2, 4, 6, 6, 4, 4, 4, 4, 8, 8, 4, 4, 4, 4, 8, 8, 6, 6, 6, 6, 12, 12, 12, 12]

symbol_names = [f'x{i}' for i in range(len(coeff))]
xvec = sp.symbols(symbol_names, integer=True, positive=True)

使用这种表示法，线性问题可以轻松地表示为点积。例如，如果我们希望方程等于 2，则方程将为

np.dot(dim_ebrs, xvec)-2]

。

使用 SymPy 库我尝试求解方程，得到以下结果

sp.solve([np.dot(dim_ebrs, xvec)-2], xvec, dict=True)

[{x0: -x1 - 4*x10 - 2*x11 - 2*x12 - 2*x13 - 2*x14 - 4*x15 - 4*x16 - 3*x17 - 3*x18 - 3*x19 - 2*x2 - 3*x20 - 6*x21 - 6*x22 - 6*x23 - 6*x24 - 3*x3 - 3*x4 - 2*x5 - 2*x6 - 2*x7 - 2*x8 - 4*x9 + 1}]

它只是解决了一个变量的问题，而不是为每个变量提供实际值。我期望得到与 Mathematica 中获得的更相似的东西：

Solve[{xvec . dim == 2, xvec >= 0}, xvec, Integers]

{{x1 -> 0, x2 -> 1, x3 -> 0, x4 -> 0, x5 -> 0, x6 -> 0, x7 -> 0, 
  x8 -> 0, x9 -> 0, x10 -> 0, x11 -> 0, x12 -> 0, x13 -> 0, x14 -> 0, 
  x15 -> 0, x16 -> 0, x17 -> 0, x18 -> 0, x19 -> 0, x20 -> 0, 
  x21 -> 0, x22 -> 0, x23 -> 0, x24 -> 0, x25 -> 0}, {x1 -> 1, 
  x2 -> 0, x3 -> 0, x4 -> 0, x5 -> 0, x6 -> 0, x7 -> 0, x8 -> 0, 
  x9 -> 0, x10 -> 0, x11 -> 0, x12 -> 0, x13 -> 0, x14 -> 0, x15 -> 0,
   x16 -> 0, x17 -> 0, x18 -> 0, x19 -> 0, x20 -> 0, x21 -> 0, 
  x22 -> 0, x23 -> 0, x24 -> 0, x25 -> 0}}

Python中可以得到满足方程的所有可能值吗？

提前致谢

Answer 1

我设法执行了一些代码来完成我所公开的案例的工作。我对任何类型的系统进行了一些概括：

xvec . v == 2*t

，其中

xvec

是我们寻求的解决方案。我把它贴在这里：

def sols(v, t):      
    
    x_max = 2*t // np.array(v)
    l = [range(i+1) for i in x_max]
    A_vec = np.array([list(elem) for elem in it.product(*l)])
    x_vec = A_vec[(A_vec @ dim ==2*t), :]
    return np.array(x_vec)

然而，一旦

t

增长，算法就会花费大量时间。有没有可能的优化方法？

谢谢