Оптимизация нелинейных моделей

Как известно для оптимизации линейной модели чаще всего пользуются симплексом-методом. Подскажите, пожалуйста, какой методикой чаще всего пользуются для оптимизация нелинейной модели? И где вообще можно в интернете на доступном языке почитать про оптимизацию нелинейных моделей?
Заранее спасибо!

Да есть впринципе куча методов которые ищут минимум у нелинейной функции при наличии ограничений (нелинейных). Лично я использовал метод Фиакко и Мак-Кормика для этих целей. Если не забуду, то завтра выложу электронный конспект

Цитата Swindler @ 26.09.06, 09:51

Да есть впринципе куча методов которые ищут минимум у нелинейной функции при наличии ограничений (нелинейных). Лично я использовал метод Фиакко и Мак-Кормика для этих целей. Если не забуду, то завтра выложу электронный конспект

Для линейной модели мы привыкли, что целевая функция и ограничения выглядят так:
{ОГРАНИЧЕНИЯ}
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ЦФ

DelphiLexx, я что-то не особо вник в твою функцию, но смогу тебя заверить, что есть методы, которые минимизируют нелинейные функции при нелинейных (в том числе) ограничениях. В чем твоя проблемма, я не понял. Ты выбираешь себе метод?

Цитата Swindler @ 26.09.06, 10:56

DelphiLexx, я что-то не особо вник в твою функцию?

Выдели те франменты, которые ты не понял - я их объясню

DelphiLexx, напиши на примере одну из составляющих частей, а то я не вижу пока что нелинейности.

Цитата Swindler @ 26.09.06, 11:23

DelphiLexx, напиши на примере одну из составляющих частей, а то я не вижу пока что нелинейности.

Дело в том, что модель о которой я говорил, может быть, и вовсе не нелинейная (сам уже запутался). Суть задачи следующая у нас есть показатели Xср1, Xср2 которые в линейной модели использовались бы в качестве коэффициентов при X1, X2, ..., Xn при составлении условий, но в связи с тем что эти показатели у меня варьируют с коэффициентов вариации Gw, следовательно, использовать линейную модель нельзя (может получиться, что решения не будет найдено, но тем не менее можно получить X1, X2, ... Xn близкие (с определенной долей вероятности) к заданным характеристикам). Вот и встает задача - какая это модель? И как её решать?

Сообщение отредактировано: DelphiLexx - 26.09.06, 12:30

DelphiLexx, напиши пример с 3-мя переменными, а то по твоим рассуждениям ничего не понятно.

Цитата Swindler @ 26.09.06, 12:33

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 с определенной степенью вероятности для указанных условий. Вот я и спрашиваю как решаются подобного рода задачи?

Сообщение отредактировано: DelphiLexx - 26.09.06, 13:15

Цитата DelphiLexx @ 26.09.06, 13:13

Вот я и спрашиваю как решаются подобного рода задачи?

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

Можно воспользоваться методами многомерной оптимизации, ищущими локальный минимум, и надеяться, что найденный локальный минимум окажется лучшим решением. При этом решение задачи с ограничениями возможно либо путем использования метода штрафных или барьерных функций (т.е. модификации целевой функции с учетом нелинейных ограничений; исходные коды некоторых алгоритмов оптимизации можно найти на alglib.sources.ru), либо с использованием специализированных алгоритмов, решающих задачу оптимизации при нелинейных ограничениях на переменные (тут надо смотреть в сторону Matlab, там немало таких алгоритмов). Если вам не надо программировать, а нужно просто найти решение, то почти однозначно - Matlab и optimization toolbox.

DelphiLexx, попробуй определить свои параметры как векторы и матрицы, а затем описать зависимости между ними и что надо найти.

Судя по данным тобою условиям, требуется лишь рассмотреть отдельно два случая неравенств: когда >= и <=.

Цитата shadeofgray @ 26.09.06, 13:39

Можно воспользоваться методами многомерной оптимизации, ищущими локальный минимум, и надеяться, что найденный локальный минимум окажется лучшим решением

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

DelphiLexx, это реально симплекс метод (судя по твоим условиям 2-4). Раздели их на 6 штук и будет тебе счастье. Да, нелинейности тут нет

Цитата Swindler @ 27.09.06, 06:33

DelphiLexx, это реально симплекс метод (судя по твоим условиям 2-4). Раздели их на 6 штук и будет тебе счастье. Да, нелинейности тут нет

Очень большая к тебе просьба прочитай вот это:
Есть проблема - дело в том, что коэффициенты при X1, X2, X3 в условии 2-4 варьируют(изменяются т.е., например, условие для белка значение коэффициента = 20.2 при X1 на самом деле варьирует в диапозоне от 18.1 до 22 ) и нам изветстна степень их варьирования (коэффициент вариации). В связи с этим получается, что нельзя брать табличные значения напрямую, а следовательно использовать линейную модель и симплекс-метод. Поэтому задача сводится к нахождению X1, X2, X3 с определенной степенью вероятности для указанных условий. Вот я и спрашиваю как решаются подобного рода задачи?

Генетические алгоритмы позволяют решать такого рода задачи.