Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.145.54.7] |
|
Сообщ.
#1
,
|
|
|
Как известно для оптимизации линейной модели чаще всего пользуются симплексом-методом. Подскажите, пожалуйста, какой методикой чаще всего пользуются для оптимизация нелинейной модели? И где вообще можно в интернете на доступном языке почитать про оптимизацию нелинейных моделей?
Заранее спасибо! |
Сообщ.
#2
,
|
|
|
Да есть впринципе куча методов которые ищут минимум у нелинейной функции при наличии ограничений (нелинейных). Лично я использовал метод Фиакко и Мак-Кормика для этих целей. Если не забуду, то завтра выложу электронный конспект
|
Сообщ.
#3
,
|
|
|
Цитата Swindler @ Да есть впринципе куча методов которые ищут минимум у нелинейной функции при наличии ограничений (нелинейных). Лично я использовал метод Фиакко и Мак-Кормика для этих целей. Если не забуду, то завтра выложу электронный конспект Для линейной модели мы привыкли, что целевая функция и ограничения выглядят так: {ОГРАНИЧЕНИЯ} x1 + x2 + x3 <= 1 x1 + 3x2 + 45x3 >= 12 2x1 + 78x3 <=1300 {ЦЕЛЕВАЯ ФУНКЦИЯ} F = 2x1 + 3x2 + 6x3 -> mim Хотел бы уточнить вид ограничений и целевой функции моей нелинейной модели выглядит так: {ОГРАНИЧЕНИЯ} 30 >= X1 <= 40 50 >= X2 <= 60 10 >= X3 <= 20 Wг1(Xср11, Gwг1)X1 + Wсв1(Xср12, Gwсв1)X2 + Wб1(Xср13, Gwб1)X3 <= Wпок1(Gwпок1) Wг2(Xср21, Gwг2)X1 + Wсв2(Xср22, Gwсв2)X2 + Wб2(Xср23, Gwб2)X3 > Wпок2(Gwпок2) ... Wгn(XсрN1, Gwг2)X1 + Wсвn(XсрN2, Gwсвn)X2 + Wб2(XсрN3, GwбN)X3 > WпокN(GwпокN), где, например, запись Wг1(Xср11, Gwг1) означает, что в качестве коэффициента берется не среднее арифметическре Xср1 - а среднее арифматическое с коэффициентом вариции. X1 + X2 + X3 = 1 {ЦЕЛЕВАЯ ФУНКЦИЯ} F = ЦФ(X1,X2,X3) + deltaЦФ |
Сообщ.
#4
,
|
|
|
DelphiLexx, я что-то не особо вник в твою функцию, но смогу тебя заверить, что есть методы, которые минимизируют нелинейные функции при нелинейных (в том числе) ограничениях. В чем твоя проблемма, я не понял. Ты выбираешь себе метод?
|
Сообщ.
#5
,
|
|
|
Цитата Swindler @ DelphiLexx, я что-то не особо вник в твою функцию? Выдели те франменты, которые ты не понял - я их объясню |
Сообщ.
#6
,
|
|
|
DelphiLexx, напиши на примере одну из составляющих частей, а то я не вижу пока что нелинейности.
|
Сообщ.
#7
,
|
|
|
Цитата Swindler @ DelphiLexx, напиши на примере одну из составляющих частей, а то я не вижу пока что нелинейности. Дело в том, что модель о которой я говорил, может быть, и вовсе не нелинейная (сам уже запутался). Суть задачи следующая у нас есть показатели Xср1, Xср2 которые в линейной модели использовались бы в качестве коэффициентов при X1, X2, ..., Xn при составлении условий, но в связи с тем что эти показатели у меня варьируют с коэффициентов вариации Gw, следовательно, использовать линейную модель нельзя (может получиться, что решения не будет найдено, но тем не менее можно получить X1, X2, ... Xn близкие (с определенной долей вероятности) к заданным характеристикам). Вот и встает задача - какая это модель? И как её решать? |
Сообщ.
#8
,
|
|
|
DelphiLexx, напиши пример с 3-мя переменными, а то по твоим рассуждениям ничего не понятно.
|
Сообщ.
#9
,
|
|
|
Цитата Swindler @ DelphiLexx, напиши пример с 3-мя переменными, а то по твоим рассуждениям ничего не понятно. Хорошо. Я уйду от общности и перейду к частному случаю: Для простоты примера, мне нужно составить мясной фарш (не обращай внимание на предметную область) из 3-х компонентов X1, X2, X3 (говядина, свинина, крахмал). Причем он должен меня удовлетворять по белку, жиру и влаге. X1, X2, X3 - по-русски говоря это проценты ввода говядины, свинины, крахмал. Естественно X1 + X2 + X3 = 1 (т.е. 100%). Вот у нас и получилась 1-ое условие. Также нам нужно, чтобы итоговый фарш содержал белка 15.2 +- 0.4, жира 14.5 +- 1 и влагу = 68 +- 1.2, поэтому получаем условия 2-4: 15.2 - 0.4 >= 20.2X1 + 17X2 + 12.7X3 <= 15.2 + 0.4 для белка 14.5 - 1 >= 7X1 + 16X2 + 11.5X3 <= 14.5 + 1 для жира 68.8 - 1.2 >= 77.7X1 + 66X2 + 74*X3 <= 68.2 + 1.2 для влаги Здесь коэффициенты при X1, X2, X3 табличное значение белка, жира и влаги для говядины, свинины, крахмала. Целевая функция у нас будет минимизация по цене. F = 17.8X1 + 17.4X2 + 0.74X3 -> min (здесь коэффициенты при X1, X2, X3 стоимость единицы соответствующего ингридиента - говядина, свинина, крахмал) [B]Все, конечно, хорошо закидывай в симплекс метод и получай X1, X2, X3. Но есть проблема - дело в том, что коэффициенты при X1, X2, X3 в условии 2-4 варьируют(изменяются) и нам изветстна степень их варьирования (коэффициент вариации). В связи с этим получается, что нельзя брать табличные значения напрямую, а следовательно использовать линейную модель и симплекс-метод. Поэтому задача сводится к нахождению X1, X2, X3 с определенной степенью вероятности для указанных условий. Вот я и спрашиваю как решаются подобного рода задачи? |
Сообщ.
#10
,
|
|
|
Цитата DelphiLexx @ Вот я и спрашиваю как решаются подобного рода задачи? Если я правильно понимаю вопрос, аналога симплекс-метода для подобных задач не существует. Т.е. не существует алгоритма, который за конечное число шагов найдет оптимальное решение. Можно воспользоваться методами многомерной оптимизации, ищущими локальный минимум, и надеяться, что найденный локальный минимум окажется лучшим решением. При этом решение задачи с ограничениями возможно либо путем использования метода штрафных или барьерных функций (т.е. модификации целевой функции с учетом нелинейных ограничений; исходные коды некоторых алгоритмов оптимизации можно найти на alglib.sources.ru), либо с использованием специализированных алгоритмов, решающих задачу оптимизации при нелинейных ограничениях на переменные (тут надо смотреть в сторону Matlab, там немало таких алгоритмов). Если вам не надо программировать, а нужно просто найти решение, то почти однозначно - Matlab и optimization toolbox. |
Сообщ.
#11
,
|
|
|
DelphiLexx, попробуй определить свои параметры как векторы и матрицы, а затем описать зависимости между ними и что надо найти.
Судя по данным тобою условиям, требуется лишь рассмотреть отдельно два случая неравенств: когда >= и <=. |
Сообщ.
#12
,
|
|
|
Цитата shadeofgray @ Можно воспользоваться методами многомерной оптимизации, ищущими локальный минимум, и надеяться, что найденный локальный минимум окажется лучшим решением Дай, пожалуйста, ссылку на метод решения задачи условия которых аналогичны моим. |
Сообщ.
#13
,
|
|
|
DelphiLexx, это реально симплекс метод (судя по твоим условиям 2-4). Раздели их на 6 штук и будет тебе счастье. Да, нелинейности тут нет
|
Сообщ.
#14
,
|
|
|
Цитата Swindler @ DelphiLexx, это реально симплекс метод (судя по твоим условиям 2-4). Раздели их на 6 штук и будет тебе счастье. Да, нелинейности тут нет Очень большая к тебе просьба прочитай вот это: Есть проблема - дело в том, что коэффициенты при X1, X2, X3 в условии 2-4 варьируют(изменяются т.е., например, условие для белка значение коэффициента = 20.2 при X1 на самом деле варьирует в диапозоне от 18.1 до 22 ) и нам изветстна степень их варьирования (коэффициент вариации). В связи с этим получается, что нельзя брать табличные значения напрямую, а следовательно использовать линейную модель и симплекс-метод. Поэтому задача сводится к нахождению X1, X2, X3 с определенной степенью вероятности для указанных условий. Вот я и спрашиваю как решаются подобного рода задачи? |
Сообщ.
#15
,
|
|
|
Генетические алгоритмы позволяют решать такого рода задачи.
|