求解 2 个整数方程组

Question

我有一组两个方程，三个未知数有一些条件。 x、y 和 z 都必须大于零。我该如何解决这个问题？只有一种解决方案，我已经知道了，但我想知道如何正确地找到它。

这些是方程式：

100 = x + y + z
100 = 10x +2.5y + 0.5z

需要找到 x、y 和 z。它们是正整数。

这是我的代码，但它不起作用：

from sympy import symbols, Eq, solve
x, y, z = symbols('x y z')
eq1 = Eq(x + y + z, 100)
eq2 = Eq(x*10 + y*2.5 + z*0.5, 100)
#eq3 = x, y, z must all be larger than zero and integers
solution = solve((eq1,eq2), (x,y,z))
solution

Answer 1

您没有明确说明，但根据您的评论，x、y 和 z 应该是整数。这让事情变得有点复杂。这是一个混合整数规划 (MIP) 问题的示例。您可以在 python 中查看以下解决此问题的软件包： mip

求解 MIP 的缺点是它们是 NP 难的。但是对于这个小例子，这应该无关紧要。

Answer 2

在 sympy 中，如果你想找到方程的整数解，那么你应该使用 diophantine。它不处理方程组，但您可以将一个方程的解放入另一个方程并再次调用丢番图：

In [69]: eq1 = x + y + z - 100

In [70]: eq2 = 10*x + 5*y/2 + z/2 - 100

In [71]: sol = diophantine(eq1, t, syms=[x, y, z])

In [72]: sol
Out[72]: {(t₀, t₀ + t₁, -2⋅t₀ - t₁ + 100)}

In [73]: [xt, yt, zt], = sol

In [74]: eq3 = eq2.subs({x:xt, y:yt, z:zt})

In [75]: eq3
Out[75]: 
23⋅t₀            
───── + 2⋅t₁ - 50
  2              

In [76]: t1, t2 = eq3.free_symbols

In [77]: [t1s, t2s], = diophantine(eq3, z, syms=[t1, t2])

In [78]: rep = {t1:t1s, t2:t2s}

In [79]: (xt.subs(rep), yt.subs(rep), zt.subs(rep))
Out[79]: (4⋅z₀ - 100, 500 - 19⋅z₀, 15⋅z₀ - 300)

这里的解决方案是根据整数参数z0。这给出了两个方程的解集，但您还要求 x、y、z 为正，这限制了 z0 的可能值：

In [80]: ineqs = [s.subs(rep) > 0 for s in [xt, yt, zt]]

In [81]: ineqs
Out[81]: [4⋅z₀ - 100 > 0, 500 - 19⋅z₀ > 0, 15⋅z₀ - 300 > 0]

In [82]: solve(ineqs)
Out[82]: 
               500
25 < z₀ ∧ z₀ < ───
                19

In [83]: 500/19
Out[83]: 26.31578947368421

我们看到 z 需要 26，这为 x、y 和 z 提供了唯一的解决方案：

In [84]: z, = ineqs[0].free_symbols

In [85]: (xt.subs(rep).subs(z, 26), yt.subs(rep).subs(z, 26), zt.subs(rep).subs(z, 26))
Out[85]: (4, 6, 90)

Answer 3

此类问题可以通过Z3py, a SAT/SMT解算器解决：

from z3 import Ints, solve

x, y, z = Ints('x y z')
sol = solve(x + y + z == 100, x * 100 + y * 25 + z * 5 == 1000, x > 0, y > 0, z > 0)
print(sol)

输出：[z = 90, y = 6, x = 4].

请注意，一般情况下，Z3 只会寻找一种解决方案。要查找后续解，需要添加一个子句禁止已经找到的解。（在这种情况下似乎只有一种解决方案。）

求解 2 个整数方程组

Solve system of 2 integer equations

python

sympy