Во Вселенной остались недорешённые СЛАУ ! Помогите решить :)

[Евгений Машеров]

B@R5uk в сообщении #1673891 писал(а):

В условии задачи ТС этого нет. Хотя я вижу, что вы имеете в виду. Профессионалы в вопросе будут что-то подобное подразумевать по умолчанию. В то же время, отсылка ТС к линейному программированию не только заведёт его в дебри, откуда ему самому не выбраться (судя по первому посту), но и к решению поставленной им задачи не приблизит.

Другое дело было бы, если бы ТС рассказал, откуда эта задача возникла и как он её решение собирается применять.

Ну, из отсутствия содержательной постановки я сделал (возможно, неверный) вывод, что задача прикладная (и в которой разглашать по каким-то соображения нежелательно), что есть какие-то отягощённые шумом косвенные измерения, при этом есть дополнительные ограничения в виде целочисленности, и что шум предполагается небольшим. И, следовательно, важно найти иксы и помехи. А оценка общего числа решений - второстепенная задача (возможно, это тоже неверное предположение).
В рамках этой постановки ЦЛП работает удовлетворительно, а "решатели" легко находятся.
Если же основной смысл - найти число решений, то приблизительная оценка через объём многогранника, а точная разве что перебором (с отсечением, но всё равно долгим).

-- 10 фев 2025, 08:47 --

B@R5uk в сообщении #1673862 писал(а):

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

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

-- 10 фев 2025, 08:54 --

dgwuqtj в сообщении #1673894 писал(а):

Так с этого начинать и надо было! Количество точек внутри посчитать, может, и реально (с длинной арифметикой), а вот чтобы их всех найти, просто не хватит памяти.

(Оффтоп)

В юности обратился ко мне за помощью филолог-шизофреник. Его сверхценная идея состояла в составлении словаря всех мыслимых языков. Он полагал, что может указать алфавит, включающий все возможные буквы (что-то около 60 позиций) и правила их сочетания. Помощь требовалась в написании программы, которая словарь бы сгенерировала. Оценив размер распечатки - стопка до Луны, я погрузил его в раздумье и избавился от Научного Подвига...

А программа расчёта Всех Возможных представляется мне такой:
Восемь (тут 8 "иксов"?) вложенных циклов, по числу переменных.
Задавшись значением одного, рассчитываем $d=Ax$, где x - вектор, i-тый элемент которого выбирается в данном цикле, элементы с первого до $i-1$ уже выбраны, а последующие принимаются нулями. Если существует $d_j>b_j$ - в ужасе выходим. Иначе входим в цикл более глубокого уровня (элегантнее рекурсией, но работать будет медленнее). А на восьмом цикле, если указанная проверка пройдена, печатаем вектор x и вектор $n_j=b_j-d_j$
Время работы оценивать не берусь.

[vlad_light]

Это почти задача Learning with errors, которую решить очень сложно.