Возможно ли решение?

[igrnd]

Добрый день!
Вчера вечером подкинули практическую задачу экономического характера. Не могу понять, есть ли вообще у нее решение.
Итак, есть более 30 чисел $n_i$, получаемых в виде уравнений следующего вида:
$a_1x+b_1y+c_1z=n_1$
$a_2x+b_2y+c_2z=n_2$
...
$a_{30}x+b_{30}y+c_{30}z=n_{30}$
Коэффициенты $a_i, b_i, c_i$ - положительные целые числа или 0, они все известны, их менять нельзя.
Параметры x, y, z - положительные числа, их начальные значения тоже известны. На самом деле параметров около десятка, но тут хотя бы принцип показать. Если это имеет значение, то параметров заведомо меньше, чем уравнений.
Соответственно, нам известны начальные суммы $n_i$ и общая сумма $n_1+n_2+n_3+...+n_{30}=N$.
Задача: найти другие значения параметров $x, y, z$, при которых и итоговая сумма $N$, и частные суммы $n_i$ будут такие же, как и при начальных значениях параметров.
Знания математики уже изрядно выветрились за несколько десятилетий после вуза. Нутром чую, что при разных коэффициентах перед параметрами в уравнениях такое решение невозможно, но доказать не могу. Но мало самому убедиться, так надо еще просто и понятно объяснить отсутствие решения руководителю. А может, я ошибаюсь, и задачу можно решить, если не аналитически, то с помощью цифровых методов. Подскажите, где накопать решение или как грамотно объяснить, что его нет.

[пианист]

Итоговая-то автоматом получится, если все уравнения выполнятся.
А вот с уравнениями засада: в невырожденном случае из любых трех $x, y, z$ уже однозначно определяются, изменить их нельзя.
Если вырожденный, надо уточнить, как именно вырожденный.

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

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

[iifat]

Собственно, дана система линейных уравнений, причём уравнений больше, чем неизвестных. Эта система имеет решения, если ранги матрицы системы и матрицы с приставленным столбцом свободных членов имеют одинаковый ранг. Всё просто.
Методом Гаусса исключаем первое неизвестное, потом второе, потом третье. Если не появились уравнения вида $0=1$, система имеет (одно или бесконечное множество) решения.

-- 15.02.2024, 20:40 --

Евгений Машеров в сообщении #1629625 писал(а):

будут побочные решения

Что именно означает эта фраза? Побочным решением обычно называют решение преобразованной системы, не удовлетворяющее исходной. Тут же имеется бесконечное множество абсолютно равноправных решений.

[worm2]

Практический рецепт такой:
0) (патологический случай) Если все числа $a_i$, $b_i$, $c_i$ равны 0, то значит, что у нас и все $n_i$ тоже нулевые, и, стало быть, любые $x$, $y$, $z$ являются решениями.
1) Выясняем, не являются ли все тройки $(a_1, b_1, c_1)$, $(a_2, b_2, c_2)$, ..., $(a_{30}, b_{30}, c_{30})$ пропорциональными друг другу. Например: $(1, 3, 4)$, $(2, 6, 8)$, $(10, 30, 40)$ и т.п. Если все тройки пропорциональны друг другу, то все уравнения, кроме одного (в котором хотя бы одно из чисел $a_i$, $b_i$, $c_i$ не равно 0, если патологический пункт 0 исключён, то такое уравнение найдётся), можно отбросить и решать только одно это уравнение: $a_ix+b_iy+c_iz=n_i$. Любое его решение будет также решением остальных. Как найти такие любые решения? Если $a_i \ne 0$ — берём пару $(y, z)$; если $b_i \ne 0$ — берём пару $(x, z)$; если $c_i \ne 0$ — берём пару $(x, y)$. В выбранной паре значения любые, а оставшееся неизвестное вычисляем через них (если требуется найти все целые решения, то придётся немного повозиться, чтобы выбрать только целые).
2) Если есть хотя бы одна пара троек, непропорциональных друг другу, то выберем такую пару (по возможности с небольшими значениями, чтобы легче считать было). Пусть это будет пара $(a_p, b_p, c_p)$ и $(a_q, b_q, c_q)$. Вычисляем вот такие три числа: $M=b_pc_q-c_pb_q$, $N=c_pa_q-a_pc_q$, $K=a_pb_q-b_pa_q$.
Если мы правильно их вычислили, то должно быть: $Ma_p+Nb_p+Kc_p=Ma_q+Nb_q+Kc_q=0$, при этом хотя бы одно из чисел $M$, $N$, $K$ отлично от нуля (проверьте).
Теперь вычисляем $Ma_i+Nb_i+Kc_i$ для всех остальных троек. Если все такие суммы нулевые, то побочные решения есть: $(x+Mw, y+Nw, z+Kw)$, где $w$ — любое число (если требуется найти только целые решения, то подбираем $w$, чтобы $Mw$, $Nw$ и $Kw$ были целыми).
3) Если нашлась ненулевая сумма $Ma_i+Nb_i+Kc_i \ne 0$, то побочных решений нет.

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

iifat в сообщении #1629635 писал(а):

Что именно означает эта фраза? Побочным решением обычно называют решение преобразованной системы, не удовлетворяющее исходной. Тут же имеется бесконечное множество абсолютно равноправных решений.

При неполном ранге у СЛАУ бесконечно много решений, но по условию данной задачи интересуют только целочисленные неотрицательные, что я и назвал побочными. Их конечное число, возможно, ноль. Как отыскать, если установлена неполнота ранга? Возможно, через ЦЛП, с целевой функцией максимум суммы абсолютных величин отклонений от декларированных значений неизвестных.

[igrnd]

Ох, последний раз я решал матрицы лет 30 назад Вспомнить бы хоть что-нибудь. Собственно, мне даже не решение нужно найти (одно решение уже есть, изначально заданное), а доказать, что другого не существует. Желательно самыми простыми словами.
Задача чисто практическая, это я уже пытаюсь найти теоретическое обоснование наличия/отсутствия второго решения.
Каждое уравнение — это расчет суммы контракта в месяц, контракт может быть на три года или около того. Коэффициенты $a_i, b_i,$ ... — это количество конкретных работ в месяц, они заданы заказчиком и не могут меняться. Параметры $x, y, z$ — это стоимость каждого вида работ. Она задается исполнителем, но не согласовывается с заказчиком. С заказчиком согласованы только суммы по месяцам $n_i$ и итоговая сумма контракта. Теперь начальник хочет пересмотреть стоимость работ. Но при этом он не может менять уже утвержденные суммы контракта в месяц. Начальник убежден, что решение найти можно, и требует от сотрудников его найти. Пока не от меня конкретно, но собираются меня тоже подключить, как программиста. Соответственно, надо либо решить задачу, либо доказать начальнику, что решения нет. Желательно простыми словами, на пальцах, потому что дольше двух минут он объяснения слушать не способен :)
Параметры $x, y, z$ - это для примера их три, на практике может быть с десяток или даже больше. Например, есть контракт на 38 месяцев, в котором 31 вид работ (букв не хватит, нужны индексы). В этом контракте количество работ в месяц (коэффициенты $a_i, b_i$ и т.п. в примере) для 16 видов работ одинаковое каждый месяц и не нулевое, еще для 5 — уникальное каждый месяц и тоже не нулевое (уже нельзя сократить количество уравнений), по остальным 10 видам количество не одинаковое, но может повторяться или принимать нулевое значение. Конечно, там кое-что бывает можно упростить, например, могут быть созависимые параметры, но это уже частный случай.

[пианист]

igrnd в сообщении #1629763 писал(а):

Собственно, мне даже не решение нужно найти (одно решение уже есть, изначально заданное), а доказать, что другого не существует. Желательно самыми простыми словами.

А если так: берем какое-нибудь из уравнений, выражаем $x$ через $y$ и $z$. Подставляем в какое-то другое, получаем уравнение на $y$ и $z$; из него выражаем $y$ через $z$. Теперь берем какое-то третье уравнение, в нем заменяем сначала $x$, потом $y$, получаем уравнение на $z$, решаем его. Потом все обратно, находим $y$ и $x$. Значит, других решений нет.
Не убедит?

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

В общем, так. Если ранг матрицы коэффициентов равен числу работ, то решение единственное. Искать можно разными способами, например, ортогонализацией Грама-Шмидта. Если ранг неполон, то решение неоднозначное, их бесконечно много, но возможно, среди них нет положительного целочисленного. Тут можно поискать через ЦЛП, но, скорее всего, будет случай полного ранга.

[igrnd]

Поднапрягся и посчитал ранг матрицы для реального контракта. И расстроился, так как ранг заметно меньше количества параметров.
Пробовал упростить систему: объединить работы с одинаковыми коэффициентами в один вид. То есть, если количество работ одинаковое и постоянное $a_i=b_i=\operatorname{const}=A$, то заменял $a_ix+b_iy$ на $Ap$, где $p=x+y$ — новый параметр. Размерность матрицы уменьшается, но ранг все равно остается меньше количества параметров. Получается, что другие решения все-таки есть. Вот как теперь найти второе решение и проверить, чтобы все параметры в альтернативном решении были положительными? Какие методы ЦЛП стоит посмотреть?
Для конкретного практического случая на данный момент решение уже не требуется, но в будущем к этому вопросу вполне могут вернуться с другими контрактами. Да и просто интересно.