Решение системы (более двух) линейных неравенств

Question

Если я использую

diophantine(2*x+3*y-5*z-77)

Я получаю этот результат.

{(t_0, -9*t_0 - 5*t_1 + 154, -5*t_0 - 3*t_1 + 77)}

Хорошо пока. Однако иногда можно ограничить x, y и z, чтобы они были (скажем) неотрицательными. Когда я использую такой подход<

reduce_inequalities([0<=t_0, 0<=-9*t_0 - 5*t_1 + 154, 0<=-5*t_0 - 3*t_1 + 77],[t_0, t_1])

Я получил:

NotImplementedError: 
inequality has more than one symbol of interest

Имеются ли у sympy, sage, prolog, haskell или какого-либо другого свободно доступного продукта средства для решения систем линейных неравенств, возникающих таким образом.

Спасибо!

Answer 1

Чтобы рассуждать о целых числах в Prolog, вы можете использовать ограничения CLP(FD) вашей системы Prolog.

Точные детали немного отличаются в разных системах Prolog. Пожалуйста, смотрите руководство к вашей системе для получения дополнительной информации, а также clpfd для связанных вопросов.

В вашем случае мы можем начать с простого размещения ограничения:

? - 2 * X + 3* Y - 5 * Z # = 77.2 * Х + 3* y #=5*Z+, 77.

В этом случае, как и для всех чистых программ Prolog, ответ системы декларативно эквивалентен исходному запросу. Здесь это не очень помогает: система лишь слегка переписала исходное ограничение.

Вы можете ограничить это далее, например, с помощью:

? - 2 * X + 3* Y - 5 * Z # = 77, [X, Y,Z] ins 0..суп. X в 0...,
2*X+3*Y#=5*Z+77,
Y в 0...,Z в 0...

В соответствии с запросом эта дополнительная цель ограничивает переменные неотрицательными целыми числами. Ответ системы по-прежнему не очень помогает.

Ты можешь использовать label/1 искать конкретные решения. Однако эта так называемая маркировка требует, чтобы все домены были конечными, и поэтому мы в настоящее время получаем:

? - 2 * X + 3* Y - 5 * Z # = 77,
   Vs = [X, Y,Z],
   Vs ins 0..sup,
   ярлык (против).ОШИБКА: Аргументы недостаточно проработаны

Хорошая новость (в некотором смысле) в том, что у нас нет времени, чтобы попробовать все возможности в любом случае. Таким образом, мы могли бы также ограничиться некоторой конечной частью пространства поиска. Например:

? - 2 * X + 3* Y - 5 * Z # = 77,
   Vs = [X, Y,Z],
   По сравнению с 0,10 000 000 000 000 000 000,
   этикетки (Vs).

С помощью этого запроса вы получаете конкретные целые числа в качестве решений:

Х = 0,
Y = 29,
Z = 2,
Vs = [0, 29, 2];
Х = 0,
Y = 34,
Z = 5,
Vs = [0, 34, 5];
Х = 0,
Y = 39,
Z = 8,
Vs = [0, 39, 8];
Х = 0,
Y = 44,
Z = 11,
Vs = [0, 44, 11];
и т.п.

Поскольку вы рассуждаете о линейных ограничениях, CLP(Q) также стоит попробовать.