2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки



Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

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



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Система уравнений
Сообщение13.05.2013, 21:42 
Аватара пользователя


15/08/12
54
Добрый день!

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

$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.

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

 Профиль  
                  
 
 Posted automatically
Сообщение13.05.2013, 22:25 
Заблокирован по собственному желанию
Аватара пользователя


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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение13.05.2013, 22:29 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение13.05.2013, 23:05 
Аватара пользователя


15/08/12
54
Спасибо, посмотрю Ермолаева.

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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение14.05.2013, 17:52 
Аватара пользователя


15/08/12
54
Для меня эта методичка слишком сложна для понимания на данном этапе.

Но вопрос не в этом. Пока мне не очевидно, что задача должна решаться симплекс методом, т.к. если взять, например, учебник Вентцель, Исследование операций, 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$ - это некие значения цены для переменных х в деньгах или еще в чем-то. В моей задаче такого нет. Известны химические составы минералов и всей горной породы и нужно просто рассчитать соотношение этих минералов. Безразлично их количество, лишь бы баланс сошелся.

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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение14.05.2013, 22:08 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение14.05.2013, 22:26 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение14.05.2013, 22:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение14.05.2013, 22:54 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение14.05.2013, 23:23 
Заслуженный участник
Аватара пользователя


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

Вот пример решения для небольшой системы.
$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$. Если же полученная система неравенств несовместна - то и задача не имеет решения :-(

 Профиль  
                  
 
 Re: Система уравнений
Сообщение15.05.2013, 00:11 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение15.05.2013, 00:35 
Заслуженный участник
Аватара пользователя


18/01/13
11121
Казань
Someone в сообщении #724018 писал(а):
1) Переписываем систему уравнений так, чтобы правые части были неотрицательными (те уравнения, которые этому условию не удовлетворяют, умножаем на ).

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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение15.05.2013, 00:41 


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

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

 Профиль  
                  
 
 Re: Система уравнений
Сообщение15.05.2013, 15:57 
Аватара пользователя


15/08/12
54
Если я разберусь, как решать эту систему, то напишу в 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, то постоянно вылезает то одно, то другое (получается слишком большое расхождение в балансе одного или нескольких элементов). Мне нужно найти оптимальное решение, при котором бы расхождение по всем элементам были бы минимальными.

 Профиль  
                  
 
 Re: Система уравнений
Сообщение15.05.2013, 20:34 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 21 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group