Система линейных уравнений с целочисленными ограничениями

[0101]

Задана система линейных уравнений такого вида

$\left\{ \begin{array}{rcl} \left\lfloor\frac{x_{0}}{a_{00}}\right\rfloor+\left\lfloor\frac{x_{1}}{a_{01}}\right\rfloor+\left\lfloor\frac{x_{2}}{a_{02}}\right\rfloor=b_{0} \\ \\ \left\lfloor\frac{x_{0}}{a_{10}}\right\rfloor+\left\lfloor\frac{x_{1}}{a_{11}}\right\rfloor+\left\lfloor\frac{x_{2}}{a_{12}}\right\rfloor=b_{1} \\ \\ {a_{20}}*x_{0}+{a_{21}}*x_{1}+{a_{22}}*x_{2}=b_{2} \\ \end{array} \right.$

где $a_{ij}$, $b_{i}$ - целые числа, $\left\lfloor\frac{x_{j}}{a_{ij}}\right\rfloor$ - целая часть от деления $\frac{x_{j}}{a_{ij}}$
Количество неизвестных совпадает с количеством уравнений.
Как искать неизвестные $x_{j}$?
Решения можно подобрать. Но есть ли жадный алгоритм?

[Sonic86]

А как Вы пытались и что получилось?
От балды можно посоветовать:
1. Воспользоваться неравенством $t-1\leqslant [t]\leqslant t$, получить какую-то область и перебрать ее.
2. Или, например, если $a_{0j}, a_{1j}$ невелики, выполнить подстановки $x_j=a_{0j}a_{1j}y_j+r_j, 0\leqslant r_j < a_{0j}a_{1j}$. Или даже заменить $a_{0j}\cdot a_{1j}$ на $\text{НОК}(a_{0j}\cdot a_{1j})$, затем перебрать все варианты $r_j$ - получится множество систем обычных линейных уравнений.
3. Можно решить третье уравнение в общем виде, подставить решение в первые 2 уравнения и попробовать упростить.
Надо поперебирать методы, м.б. покомбинировать их. Можно выбрать наугад задачу такого типа побольше и попытаться ее решить руками.
Насчет жадного алгоритма не очень понятно - решений здесь скорее всего мало, хотя бы одно найти. А целевой функции здесь нет.

[Xaositect]

Как вариант, привести к смешанному целочисленному линейному программированию. Для этого ввести новые целочисленные переменные $q_{ij} = \lfloor \frac{x_i}{a_ji} \rfloor$ и записать соответствующие неравенства.

[Markiyan Hirnyk]

Mathematica решает такие системы.

[0101]

Спасибо! С переходом к смешанному целочисленному линейному программированию понятно.

Цитата:

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

Когда число неизвестных совпадало с количеством уравнений, напрашивалась ошибочная мысль о ненужности целевой функции. Если ввести новые целочисленные переменные $q_{ij} = \lfloor \frac{x_i}{a_ji} \rfloor$, неизвестных станет больше и целевая функция станет необходима.

Цитата:

Mathematica решает такие системы.

LinearProgramming — real and integer linear programming in matrix form?
Какие именно пакеты рекомендуете?

[kotenok gav]

0101 в сообщении #1339430 писал(а):

переменные

Они будут выражаться друг через друга. Переменных не станет больше.

[Markiyan Hirnyk]

0101

Цитата:

LinearProgramming — real and integer linear programming in matrix form?
Какие именно пакеты рекомендуете?

Нет. Вот пример

sol = Reduce[{4*x1 + 7*x2 + 6*x3 == 186, 
   Floor[(1/2)*x1] + Floor[(1/5)*x2] + Floor[(1/3)*x3] == 18, 
   Floor[(1/5)*x1] + Floor[(1/2)*x2] + Floor[(1/4)*x3] == 21}, {x1, 
   x2, x3}, Reals]

((155/2<x1<78&&1/7 (744-4 x1)<x2<62)||(72<=x1<=73&&1/7 (714-4 x1)<x2<62)||(73<x1<=147/2&&1/7 (714-4 x1)<x2<=1/7 (726-4 x1))||(147/2<x1<74&&60<=x2<=1/7 (726-4 x1))||(74<=x1<75&&1/7 (726-4 x1)<x2<62)||(153/2<x1<78&&1/7 (726-4 x1)<x2<60)||(x1==72&&58<=x2<60)||(72<x1<74&&58<=x2<=1/7 (708-4 x1))||(75<=x1<76&&1/7 (714-4 x1)<x2<60)||(x1==74&&442/7<x2<64)||(74<x1<75&&1/7 (738-4 x1)<x2<=1/7 (744-4 x1))||(74<=x1<75&&1/7 (708-4 x1)<x2<=1/7 (714-4 x1))||(151/2<x1<76&&1/7 (708-4 x1)<x2<58)||(157/2<x1<80&&1/7 (762-4 x1)<x2<64)||(68<=x1<137/2&&56<=x2<=1/7 (666-4 x1))||(x1==137/2&&x2==56)||(x1==70&&56<x2<58)||(70<x1<=71&&56<=x2<58)||(71<x1<72&&56<=x2<=1/7 (690-4 x1))||(70<=x1<=281/4&&54<=x2<55)||(281/4<x1<72&&54<=x2<=1/7 (666-4 x1)))&&x3==1/6 (186-4 x1-7 x2)

\begin{multline*} \left(\left(\frac{155}{2}<x_1<78\land \frac{1}{7} (744-4 x_1)<x_2<62\right)\lor \left(72\leq x_1\leq 73\land \frac{1}{7} (714-4 x_1)<x_2<62\right)\\ \lor \left(73<x_1\leq \frac{147}{2}\land \frac{1}{7} (714-4 x_1)<x_2\leq \frac{1}{7} (726-4 x_1)\right)\lor \left(\frac{147}{2}<x_1<74\land 60\leq x_2\leq \frac{1}{7} (726-4 x_1)\right)\\ \lor \left(74\leq x_1<75\land \frac{1}{7} (726-4 x_1)<x_2<62\right)\lor \left(\frac{153}{2}<x_1<78\land \frac{1}{7} (726-4 x_1)<x_2<60\right)\\ \lor (x_1=72\land 58\leq x_2<60)\\ \lor \left(72<x_1<74\land 58\leq x_2\leq \frac{1}{7} (708-4 x_1)\right)\lor \left(75\leq x_1<76\land \frac{1}{7} (714-4 x_1)<x_2<60\right)\\ \lor \left(x_1=74\land \frac{442}{7}<x_2<64\right) \lor \left(74<x_1<75\land \frac{1}{7} (738-4 x_1)<x_2\leq \frac{1}{7} (744-4 x_1)\right)\\ \lor \left(74\leq x_1<75\land \frac{1}{7} (708-4 x_1)<x_2\leq \frac{1}{7} (714-4 x_1)\right) \lor \left(\frac{151}{2}<x_1<76\land \frac{1}{7} (708-4 x_1)<x_2<58\right)\\ \lor \left(\frac{157}{2}<x_1<80\land \frac{1}{7} (762-4 x_1)<x_2<64\right)\\ \lor \left(68\leq x_1<\frac{137}{2}\land 56\leq x_2\leq \frac{1}{7} (666-4 x_1)\right)\lor \left(x_1=\frac{137}{2}\land x_2=56\right)\lor (x_1=70\land 56<x_2<58)\\ \lor (70<x_1\leq 71\land 56\leq x_2<58)\\ \lor \left(71<x_1<72\land 56\leq x_2\leq \frac{1}{7} (690-4 x_1)\right)\lor \left(70\leq x_1\leq \frac{281}{4}\land 54\leq x_2<55\right)\\ \lor \left(\frac{281}{4}<x_1<72\land 54\leq x_2\leq \frac{1}{7} (666-4 x_1)\right)\right)\land x_3=\frac{1}{6} (-4 x_1-7 x_2+186)\end{multline*}

[0101]

Markiyan Hirnyk Спасибо!
Теперь буду искать алгоритмы, которые использует для решения этой задачи Mathematica.

[Lia]

Оффтоп отделен сюда: «Оформительский оффтоп»