Система уравнений

[alenov]

Добрый день!

Помогите, пожалуйста, разобраться каким методом лучше всего (и проще) решать следующую систему уравнений:

$A_1 \cdot x_1+A_2 \cdot x_2+...+A_k \cdot x_k=A$
$B_1 \cdot x_1+B_2 \cdot x_2+...+B_k \cdot x_k=B$
$C_1 \cdot x_1+C_2 \cdot x_2+...+C_k \cdot x_k=C$
$x_1,x_2,...,x_k\geqslant0$
$k \ne n(A,B,C)$

Могут быть также дополнительные условия, например: $(x_1+x_2)/x_3=D$.
Изначально я предполагал решать симплекс методом, но вроде бы он не подходит, т.к. ничего минимизировать не надо.

Если это имеет значение, то смысл этой задачи в том, чтобы из известных составов минералов ($A_1, B_1, C_1$ - состав минерала 1 и т.д.) и горной породы ($A, B, C$) рассчитать соотношения минералов в горной породе ($x_1, x_2, ..., x_k$). Соотношения между некоторыми минералами заранее известны. k и n обычно меньше 20.

Большое спасибо!

[AKM]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»
Причина переноса: не указана.
Написали бы для чайников вроде меня, что есть $n(A,B,C)$.

[maxal]

См. post119437.html#p119437 (например, методичку Ермолаева)

[alenov]

Спасибо, посмотрю Ермолаева.

Это просто количество элементов в системе.

[alenov]

Для меня эта методичка слишком сложна для понимания на данном этапе.

Но вопрос не в этом. Пока мне не очевидно, что задача должна решаться симплекс методом, т.к. если взять, например, учебник Вентцель, Исследование операций, 1972 https://docs.google.com/file/d/0B08REaASOrMBbXRqdWlpcVl1ZzQ/edit?usp=sharing, там приводится много примеров схожих с моей задач. Но во всех этих задачах есть некая линейная функция (стр. 29 $L = c_1 \cdot x_1 + c_2 \cdot x_2 + c_3 \cdot x_3 + c_4 \cdot x_4$), которая должна быть минимизирована или максимизирована. $c_1$, $c_2$, $c_3$, $c_4$ - это некие значения цены для переменных х в деньгах или еще в чем-то. В моей задаче такого нет. Известны химические составы минералов и всей горной породы и нужно просто рассчитать соотношение этих минералов. Безразлично их количество, лишь бы баланс сошелся.

Мне нужно это условие как-то искусственно сконструировать? Или может применить какой-то другой метод?

[provincialka]

Кстати, "дополнительное условие" типа $\frac{x_1+x_2}{x_3}=D$ также сводится к линейному соотношению $x_1+x_2-Dx_3=0$.

А насколько число переменных больше, чем число уравнений?

[alenov]

Конкретно сейчас у меня 13 переменных и 11 (вместе с показанным вами 12) уравнений, но нужно научиться решать эту задачу в общем виде.

[provincialka]

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

[alenov]

Методом Гаусса я пытался решать в Excel. Получаются отрицательные значения. Как с этим справиться не понятно.
Программная реализация пока не нужна, метод бы какой-нибудь работающий найти. Вроде-то задача тривиальная...

[provincialka]

Ну, может задача и неразрешима... Что значит "отрицательные значения"? Там ведь есть свободные переменные. Значит, надо все выразить через них и наложить ограничения на знак полученных выражений.
Но если ответа не получилось - значит, его и нет. Ведь могут же условия быть противоречивыми...

Вот пример решения для небольшой системы.
$2x+3y+4z=3$
$x+y=5z$
Решением будет, например, $x=19z-3, y=3-14z$. Условия $x\ge0,y\ge0,z\ge0$ сводятся к ${3\over19}\le z\le{3\over14}$. Вот из этого промежутка берем $z$ и находим $x,y$. Если же полученная система неравенств несовместна - то и задача не имеет решения

[Someone]

Задачу можно решать симплекс-методом, но получатся не все неотрицательные решения, а, скорее всего, только одно.
1) Переписываем систему уравнений так, чтобы правые части были неотрицательными (те уравнения, которые этому условию не удовлетворяют, умножаем на $-1$).
2) В качестве целевой функции берём сумму левых частей всех уравнений минус сумма правых.
3) Максимизируем эту функцию симплекс-методом.

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

[provincialka]

Someone в сообщении #724018 писал(а):

1) Переписываем систему уравнений так, чтобы правые части были неотрицательными (те уравнения, которые этому условию не удовлетворяют, умножаем на ).

они и так неотрицательны, как и коэффициенты (так как это количество того или иного минерала/составляющей)

[mserg]

Противоречивость, возможно, - результат ошибок измерения. Классика жанра - добавить к соответствующим уравнениям разности $p_i-q_i$. И минимизировать суммы $p_i,q_i$. Конечно, возможны и другие варианты.

P.S. В Excel есть численные методы, в том числе линейное программирование (где-то в меню "Поиск решения"). Даже частично-целочисленное.

[alenov]

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

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

$a_1_1 x_1 + a_1_2 x_2 + ... + a_1_k x_k - b_1 = 0$
$a_2_1 x_1 + a_2_2 x_2 + ... + a_2_k x_k - b_2 = 0$
...
$a_n_1 x_1 + a_n_2 x_2 + ... + a_n_k x_k - b_n = 0$

$x_1...x_k \geqslant 0$ (содержание минерала k в породе)
$a_1_1...a_n_k \geqslant 0$ (содержание элемента n в минерале k)
$b_1...b_n > 0$ (содержание элемента n в породе)
$n < k < 20$

Мне понравилась идея №2 Someone. Запишу, как я ее понял:

$ L = (a_1_1 x_1 + a_1_2 x_2 + ... + a_1_k x_k - b_1) + (a_2_1 x_1 + a_2_2 x_2 + ... + a_2_k x_k - b_2) + ... + (a_n_1 x_1 + a_n_2 x_2 + ... + a_n_k x_k - b_n) \to max $

Можно ли так сделать?

Mserg, составы минералов и породы определяются разными методами и там и там есть довольно высокие погрешности, + составы минералов очень изменчивы и смешиваются один с другим. Было сделано порядка 20 определений для каждого минерала для статистики и рассчитаны медианные составы. Я, к сожалению, не понял, что вы принимаете за $p_i$ и $q_i$.

Provincialka, "отрицательные значения" - это те, которые меньше нуля. Не может быть содержание минерала в породе отрицательным. Я пробовал посчитать вашим методом, но получается по сути метод подбора, когда 3-4 уравнения он работает, но когда 10, то постоянно вылезает то одно, то другое (получается слишком большое расхождение в балансе одного или нескольких элементов). Мне нужно найти оптимальное решение, при котором бы расхождение по всем элементам были бы минимальными.

[provincialka]

Я поэтому и спрашивала, какова разность $n-k$. Если св.ободных переменных 1-2, то можно выписать неравенства и решить их "вручную". Если же их много - нужны методы поиска допустимых решений (не обязательно оптимальных).