Найти целочисленные решения для набора уравнений с более неизвестными, чем уравнения

Question

Я пытаюсь построить систему, для которой мне нужно найти решение для набора линейных уравнений с (большим) числом переменных, чем уравнения.

Проблема сводится к следующему:

Представьте себе набор уравнений:

A = A1*X1 + A2*X2 + ... + AnXn 
B = B1*X1 + B2*X2 + ... + BnXn 

Как я могу найти один или несколько (положительные) целые решения в этой системе?

Примечание: Я смотрел библиотеку apache-commons-math, но не мог найти никаких указаний о том, как решить/найти решение системы со свободными переменными.

Answer 1

Используйте алгоритм восстановления решетки решетки Ленстра-Ленстра-Ловаша, чтобы найти нормальную форму Эрмита вашей системы.

Это straaightforward в MATLAB http://fr.mathworks.com/help/symbolic/mupad_ref/linalg-hermiteform.html

Проверить NTL для C++ http://www.shoup.net/ntl/index.html

Answer 2

Я бы попробовал следующий подход (обратите внимание, что мне никогда не приходилось справляться с этой проблемой, поэтому возьмите этот ответ как попытку решить с вами проблему вместо реального аналитического ответа).

Вы просто найти решения так же, как если бы это регулярная система, так что вы, возможно, найти infinetly много решений:

Пример:

y = x + 3 

тогда действительных чисел пары (2,5) является возможным реальным решением для этой системы, как только у вас будет бесконечно много решений, вы просто ограничиваете подмножество решений, которые производятся целыми числами.

Конечно у вас есть ограничения, в нашем случае решение имеет только 1 свободную переменную, так что мы можем написать все решения, как, что:

(x, x+3) 

сюрприз:

Если есть иррациональное число где-то , нет целочисленных решений:

(x, x+pi) => neither 1st or 2nd number here can be whole at same time 

Таким образом, вы, вероятно, можете найти целые решения тогда и только тогда, когда ваш " бесконечно много решений "ограничены целыми или рациональными числами.

Предположим, у вас есть следующий вектор:

(3x, (2/5)y, y, x, x+y) 

Тогда целое решение может быть:

x=3 
y=10/2 

Если вы чувствуете, что ответ не удовлетворяет вас, просто скажите: Я буду удалять чтобы не набирать очки бонусов

Answer 3

Вы можете посмотреть на ограничительных решателей, как Z3. Там также есть JavaExample.

Полезный учебник, объясняющий некоторые возможности Z3, можно найти here.

EDIT: Кроме того, посмотрите на Algorithm for solving systems of linear inequalities

Answer 4

Это взято из relevent Wikipedia section.

1. Перепишите уравнения с матричной ноте AX=C.
2. Вычислить Smith normal form из A. Грубо говоря, это найти B=UAV, где B[i][j] == 0, если i != j.
3. B(inverse(V))X=UC
4. Как B[i][j] == 0 если i != j, это тривиально, чтобы найти значение (inverse(V))X и, таким образом X.

Answer 5

Выполните этот пример: предположим, что уравнения:

7 = x + 3y + 4z + 9w 
12 = 4x + 2y + 3z + 7w 

Есть 2 уравнения и 4 неизвестных. Вы можете установить 2 неизвестных, чтобы быть параметры, поэтому система будет иметь столько уравнений, сколько неизвестных:

7 - (4z + 9w) = x + 3y 
12 - (3z + 7w) = 4x + 2y 

Мы будем использовать х и у, как неизвестные. Можно решить и оставить ш и г в качестве параметров линейного решения:

x = (22 - 3w - z)/10 
y = (16 - 29w - 13z)/10 

Теперь вам нужно сделать числитель делится на 10, то знаменатель. Если есть решение, вы можете проверить все параметры от 1 до 10.

В общем, вы делаете это:

• Выберите параметры так, что есть так много неизвестных как уравнения. Попробуйте оставить неизвестные, которые генерируют наименьшее абсолютное значение для детерминанта (в примере это было 10, но выбор y и z был бы лучше, так как это было бы | det | = 3)
• Решите линейную систему и сгенерируйте ответ в зависимости от параметров
• Проверьте значения параметров от 1 до абсолютного значения det (если есть решение, вы найдете его в этой точке), пока не будет целочисленное решение для всех неизвестных (именно поэтому вы выбираете наименьшее детерминантное значение перед) и проверяете, является ли оно положительным (это не было проиллюстрировано в примере).

Извините, если это грубая сила на последнем шаге, но, по крайней мере, существует возможность минимизировать диапазон теста. Может быть, может быть лучший способ решить окончательную систему диофантовых уравнений, но я не знаю никакого метода.

EDIT1

Существует способ избежать перебирая последнюю часть.Опять же, в этом примере, вы должны сделать:

22 = 3w + z (congruent, mod 10) 
16 = 29w + 13z (congruent, mod 10) 

Применение модуля:

2 = 3w + z (congruent, mod 10) 
6 = 9w + 3z (congruent, mod 10) 

Вы можете сделать систему сравнений треугольной (Gaussian элиминации), умножая конгруэнтность на инверсий в модуле 10 и подведение итогов к другим. Инверсия 9 по модулю 10 равена -1, поэтому мы умножаем последнюю конгруэнтность:

2 = 3w + z (congruent, mod 10) 
-6 = -9w + -3z (congruent, mod 10) 

эквивалентна:

2 = 3w + z (congruent, mod 10) 
4 = w + 7z (congruent, mod 10) 

Затем умножить на -3 и добавить к первому:

2 - 3*4 = 3w + z -3w - 21z (congruent, mod 10) 
4 = w + 7z (congruent, mod 10) 

Эквивалент:

-10 = -20z (congruent, mod 10) 
4 = w + 7z (congruent, mod 10) 

The n, вы решаете сверху вниз (этот пример кажется истинным для любого значения z). Там может быть определенная степень свободы, если у вас больше параметров, чем сравнений, но они эквивалентны, и вы можете установить избыточные параметры при любом значении, предпочтительно наименьшее, которое равно 1.

Сообщите мне, если есть что-то непонятное все же!

Answer 6

Если я правильно понимаю проблему, у вас есть несколько пакетов, каждый из которых имеет разные почтовые расходы. Вы хотите оплатить эти почтовые расходы из пула марок, которые у вас есть. Можно решить проблему с целым программированием. Решение ниже решает для всех пакетов сразу. У вас будет число переменных, равное numPackages * numStampDenominations (вероятно, неудобно для большого количества пакетов).

Ограничение равенства выглядит как Aeq x = beq. Матрица Aeq для двух пакетов с 4 штемпеля наименований (numVars numPackages) выглядит следующим образом:

.21 .68 .47 .01 .00 .00 .00 .00   .89 
            * x = 
.00 .00 .00 .00 .21 .68 .47 .01   .50 

первая строка коэффициенты ограничения (значения штампа) для пакета 1. ненулевые коэффициенты являются значения штампа. Нулевая переменная, связанная с другими пакетами, не заботится.

Второй набор ограничений (неравенство) касается пула марок, которые у меня имеются. Ограничение неравенства выглядит как A * x = b. Матрица А в течение 4 штампа наименований и 8 переменных (numPackages * numStampDenominations) выглядит следующим образом:

1 0 0 0 1 0 0 0   10 

0 1 0 0 0 1 0 0   10 
       * x <= 
0 0 1 0 0 0 1 0   10 

0 0 0 1 0 0 0 1   20 

функция затрат е '* х, который является только общее число штампов. Его коэффициенты являются просто единицами в виде вектора столбца.

Ниже приведен скрипт, запущенный в Matlab, который решает проблему описанным образом. Вероятно, он будет сформулирован примерно так же в октавах, предлагающих GNU, похожих на Matlab. Matlab или октава не могут быть правильным решением для вас, но они, по крайней мере, говорят вам, что работает, и дают вам песочницу для разработки решения.

% The value of each stamp available as a 4x1 matrix 
sv = [.21; .68; .47; .01]; 
% The number of each stamp available as a 4x1 matrix 
sq = [10;10;10;40]; 
% Number of demominations 
m = size(sv, 1); 
% The postage required for each package as a 4x1 matrix 
% -- probably read from a file 
postage = [.89;.50;1.01;.47;.47]; 
% Number of packages -- just a count of the postage rows 
packageCount = size(postage, 1); 
% Number of variables is m*packageCount 
numVar = m*packageCount; 
% lower bound -- zero stamps of a given denomination 
lb = zeros(numVar,1); 
% upper bound -- use constraints for upper bound 
ub = []; 
% The cost function -- minimize the number of stamps used 
% min(f'*x) 
f = ones(numVar,1); 
% integer constraints 
intcon = 1:numVar; 
% Construct postage constraint matrix 
Aeq = zeros(numVar, packageCount); 

for i = 1:packageCount 
    first = i*m - 3; 
    last = first + 3; 
    Aeq(first:last,i) = sv(:); 
end 

% Construct stamp count constraint matrix 
A = zeros(numVar, m); 

for r = 1:m 
    for j = 1:m 
     c = (j-1)*m + 1; 
     A(c,r) = 1; 
    end 
end 

x = intlinprog(f, intcon, A', b, Aeq', beq, lb, ub)