2014 dxdy logo

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

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




 
 Алгоритм поиска оптимальной пропорции составляющих
Сообщение09.09.2014, 18:09 
Здравствуйте, возникла прикладная задача, для которой необходимо написать программу-калькулятор. К сожалению никак не соображу по какому алгоритму считаются подобные задачки, хотя чувствую что есть какое-то специальное решение для такого типа задач. Был бы очень признателен за помощь и подсказки. Мне важно понять смысл алгоритма, тогда смогу интерпретировать его в код.

Задача звучит так:
Нам нужно получить раствор 3х элементов в заданной пропорции (например 30 : 70 : 50), но чистых элементов у нас нет, есть только их соединения в различной форме, это то что мы имеем.
Скажем, у нас есть 5 соединений которые мы можем использовать. Они содержат нужные нам элементы в следующих пропорциях:

10 : 20 : 10

30 : 50 : 40

50 : 70 : 70

50 : 10 : 30

40 : 40: 40

Таким образом, наша задача определить, в каких пропорциях нужно смешать имеющиеся у нас соединения, чтобы в результате получить состав элементов максимально близкий к эталону (30 : 70 : 50).

Я к сожалению не математик, и давно уже не студент, задача практическая, чтобы посчитать хим.реактивы. Формулы мне не помогут, т.к. меня не интересует математическое решение, его все равно не превратить в массивы и циклы, без понимания логики.
Пробовал приспособить под это дело Pid регулятор, но что-то ничего вразумительного не вышло.
Поэтому мне нужна наводящая подсказка: в какую сторону копать, может быть ссылка на описание подобного рода задач или хотя бы простой ответ: "Нет такого алгоритма, только перебором вариантов" или же "да есть, почитай про ..."

Спасибо.

 
 
 
 Posted automatically
Сообщение09.09.2014, 18:36 
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
Тема перемещена в Карантин по следующим причинам:

Изложите Ваши соображения и затруднения, пожалуйста.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

 
 
 
 Posted automatically
Сообщение09.09.2014, 19:18 
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

 
 
 
 Re: Алгоритм поиска оптимальной пропорции составляющих
Сообщение09.09.2014, 19:55 
Я бы порекомендовал в такой ситуации так называемые нормальные псевдорешения.
Здесь у Вас так и напрашивается система линейных уравнений, но она, увы, недоопределена: количество неизвестных (5, по количеству реактивов) больше, чем количество уравнений (3, по количеству параметров в соотношении).

 
 
 
 Re: Алгоритм поиска оптимальной пропорции составляющих
Сообщение10.09.2014, 06:41 
Аватара пользователя
blondinko в сообщении #905987 писал(а):
напрашивается система линейных уравнений, но она, увы, недоопределена
Разве это плохо? Насколько я понимаю, требуется хоть какое-то решение.

-- 10.09.2014, 07:36 --

Правильно ли я понял, что:

1) нужные пропорции могут быть любыми,
2) количество доступных соединений и пропорции веществ в них могут быть любыми

?

 
 
 
 Re: Алгоритм поиска оптимальной пропорции составляющих
Сообщение10.09.2014, 08:21 
Аватара пользователя
1. У нас соединений больше, чем потребных элементов.
Это задача линейного программирования (если ещё добавить целевую функцию)
Если расход i-того соединения обозначить$x_i$, а содержание j-того элемента в i-том соединении $a_{i,j}$, потребное количество j-того элемента $c_j$
то у нас будет система уравнений вида
$\Sigma_i a_{i,j}x_i=c_j$
К ней можно добавить "цены" соединений $ b_i$ и целевую функцию, которую будем минимизировать
$\Sigma b_ix_i$ (или максимизировать, если эти коэффициенты - "полезности")
Программы для ЛП доступны, но навскидку не назову
2. У нас элементов больше, чем соединений.
Тогда на точное соотношение выйти, вообще говоря, нельзя, надо искать приближение.
Если устраивает квадратичная мера приближения - можно воспользоваться программами регрессионного анализа, матрица Х будет состоять из концентраций элементов, Y - потребность в элементах, вектор коэффициентов модели даст дозу соединений.

 
 
 
 Re: Алгоритм поиска оптимальной пропорции составляющих
Сообщение10.09.2014, 12:08 
Спасибо большое за ваши соображения, буду пробовать. по условиям уточню:
Количество искомых элементов может варьироваться, но ограничено существующими (таблица менделеева), но чаще всего это будет количество 30-50шт.
Количество же соединений, ничем не ограничено, и теоритически их может быть много больше чем искомых элементов, но на практике, обычно располагают набором из максимум некольких десятков соединений, а чаще нескольких штук (5-6).
Т.е. в идеале иметь универсальное решение для обоих случаев, но чаще всего, соединений меньше, чем искомых элементов.
Одни соединения могут быть моноэлементными (содержать только один искомый элемент), а другие содержать в составе десятки элементов.

 
 
 
 Re: Алгоритм поиска оптимальной пропорции составляющих
Сообщение10.09.2014, 14:49 
Аватара пользователя
В общем, погуглите "Задача о диете".

 
 
 
 Re: Алгоритм поиска оптимальной пропорции составляющих
Сообщение10.09.2014, 15:11 
Аватара пользователя
На всякий случай отмечу, что с задачами ЛП отлично справляется Wolfram Mathematica. prgmem, почитайте эту страницу справки.

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group