Решите систему из 2 целочисленных уравнений
У меня есть набор из двух уравнений с тремя неизвестными, который имеет некоторые условия. x, y и z должны быть больше нуля. Как я могу это решить? Есть только одно решение, и я его уже знаю, но хочу знать, как правильно к нему добраться.
Это уравнения:
100 = x + y + z100 = 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
Ответы 3
Вы не указали это явно, но, согласно вашему комментарию, x, y и z должны быть целыми числами. Это немного усложняет дело. Теперь это пример задачи смешанного целочисленного программирования (MIP). Вы можете взглянуть на следующий пакет для решения этой проблемы в python: мип
Недостатком решения MIP является то, что они трудны для NP. Но для этого небольшого примера это не должно иметь значения.
В 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)
Безумно сложно, но я попробовал ваше решение, и оно работает. Спасибо!
Это просто сложно, потому что diophantine не обрабатывает несколько уравнений в качестве входных данных. В идеале большая часть вышеперечисленного должна быть обработана внутри diophantine, но это еще не добавлено.
Задачи такого типа можно решить с помощью Z3py , решателя 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 ищет только одно решение. Для поиска последующих решений необходимо добавить пункт, запрещающий уже найденные решения. (В этом случае, похоже, есть только одно решение.)
Очень круто! Не знал z3, но это так красиво и просто. Спасибо!
Вы можете добавить ограничения (sympy называет их предположениями) при создании символа, например
x = Symbol("x", positive=True)— вы пробовали это? Не уверен насчет целочисленного ограничения.