Симплекс-метод поиска глобального экстремума

Метод предназначен для поиска глобального или локального экстремума и суть его заключается в следующем. В горизонтальной плоскости параметров методами аналитической геометрии создается модель равностороннего треугольника abc – симплекса, рис. 22.

Рис.22. К обоснованию симплекс-метода для поиска экстремума

Размер симплекса, определяемый длиной стороны, выбирается произвольно. Первоначальное его положение также не имеет принципиального значения. Главное условие – все его вершины должны проецироваться на поверхность отклика функции цели . Процесс итерации заключается в следующем.

1. Рассчитывают значения функционала во всех точках – проекциях вершин симплекса на поверхность отклика функции цели:

, , .

2. Производят количественное сравнение полученных значений

функционала.

3. Если ищется максимальное значение функции цели, то из

анализируемых значений выбирается наименьшее .

4. На плоскости строят второе положение симплекса путем

поворота предыдущего относительно той стороны треугольника,

которая расположена против вершины, имеющей проекцию с

минимальным значением функции цели.

5. Повторяют действия по п.п. 1-4 (перемещения симплекса на рис.22 показаны под номерами итерационных шагов) до тех пор, пока симплекс не начнет совершать периодические перемещения. Они могут быть двух типов: систематический поворот относительно одной из сторон (позиции 8-9, рис.22), вращение вокруг какой-либо точки (например, точки D).

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

7. Действия по п.п.1-6 повторяют до тех пор, пока размер стороны симплекса не достигнет заданной минимальной величины.

8. Определяют значение функции цели и оптимальный план по координатам той вершины симплекса в его окончательном положении, для которой значение функционала будет максимальным.

Из описанного алгоритма метода видно, что для него характерен большой объем вычислительных операций. Поэтому реализация такого метода безусловно предпочтительно выполнять с привлечением вычислительной техники. При этом построение программного алгоритма и организация вычислений не могут вызвать больших затруднений. Тем не менее симплекс-метод может быть очень эффективен для многих приложений.

Поиск по сайту: