Алгоритм симплекс метода
Начальный этап. Пусть e> 0 - скаляр, используемый в критерии остановки, l – длина ребра симплекса, α – коэффициент уменьшения размеров симплекса. Выбрать начальную точку X1, рассчитать вершины исходного симплекса X1, X2, …, Хn+1, определить значение функции в этих вершинах f(X1),…, f(Xn+1) и перейти к основному этапу. Основной этап. Шаг 1. Определить из n+1 вершин вершину с максимальным значением функции и соответствующий ей номер j. Рассчитать новую вершину Хn+2= . Если f(Xn+2)≤ f(Xj), то Xj=Xn+2 и перейти к шагу 1. В противном случае перейти к шагу 2. Шаг 2. Если длина ребра £ e, то остановиться; в противном случае провести редукцию симплекса. Выбрать из n+1 вершин вершину с минимальным значением функции и соответствующий ей номер m. Рассчитать вершины нового симплекса Xi= ((1- α )Xm + Xi)/α для i ≠m, вычислить значения функции f(X1),…, f(Xn+1) и перейти к шагу 1. Пример расчета экстремума функции симплекс-методом. Постановка задачи. Минимизировать f(X) = (x1 - 2)4 + (х1 - 2х2)2 с точностью e=0,01. Выбираем начальное приближение X(1) = [2.5, 2.5]Т, длину ребра симплекса l=0.5 и коэффициент сжатия симплекса a = 2. Результаты расчета для данных условий представлены в таблице 2.4, графическая интерпретация метода – на рисунке 2.4. Таблица 2.4 Результаты расчета минимума функции f(X) = (x1 - 2)4 + (х1 - 2х2)2 симплекс методом.
Из таблицы видно, что на пятой итерации происходит зацикливание симплекса, так как отраженная вершина № 2 вновь становится «наихудшей». После редукции симплекса реализовано семь итераций, после чего вновь появляется эффект зацикливания. В результате чего вновь производится редукция. Полученный симплекс не находится в области экстремума функции. Поэтому проведенная редукция не дает желаемого результата, что говорит о плохой сходимости метода на функциях "овражного" типа.
Рис.2.4. Графическая иллюстрация поиска минимума функции симплекс-методом. Метод Нелдера и Мида. Отмеченные выше недостатки регулярного симплекса, а также отсутствие ускорения поиска и трудности при проведении поиска на искривленных “оврагах” и “хребтах” явились причиной разработки Нелдером и Мидом метода, в котором симплекс меняет свою форму, т. е. представляет деформируемый многогранник. Изменение формы многогранника происходит за счет операций растяжения, сжатия и редукции. 1. Построение начального многогранника. Выбирается произвольной формы многогранник с координатами вершин Xi(k) = [xi1(k), …, xij(k), …, xin(k)]Т, i = 1,…, n+1. Индекс (k) будет обозначать k-й этап поиска. Значение целевой функции в Xi(k) равно f(Xi(k)). 2. Расчет координат центра тяжести. Определяют те векторы х многогранника, которые дают максимальное и минимальное значение f(X), а именно f(Xh(k)) = max{f(X1(k)), …, f(Xn+1(k)); f(Xl(k)) = min{ f(X1(k)), …, f(Xn+1(k)). Тогда координаты центра тяжести рассчитываются по формуле , j = 1, …, n, где индекс j обозначает координатное направление. 3. Отражение. Представляет проектирование Xh(k) через центр тяжести в соответствии с соотношением , где a > 0 - коэффициент отражения; Xh(k) - вершина, в которой функция f(X) имеет наибольшее значение. В обычном симплексе a = 1. 4. Растяжение. Происходит в случае, если . Вектор ( ) увеличивается в соответствии с соотношением , где g > 1 - коэффициент растяжения. Если , то заменяется на и процедура продолжается с этапа 2 при k = k + 1. Иначе заменяется на и также осуществляется переход к этапу 2 при k = k + 1. 5. Сжатие. Если для всех i ¹ h, то вектор ( ) уменьшается в соответствии с формулой , где 0 < b < 1 - коэффициентом сжатия. Затем заменить на и происходит возврат к операции 2 при k = k + 1. 6. Редукция. Происходит при условии, если . Все векторы ( ) уменьшаются в 2 раза с отсчетом от в соответствии с формулой , i=1, …, n+1. Затем возвращаемся к операции 2 для продолжения поиска на (k+1)-м шаге. Для окончания поиска Нилдер и Мид используют критерий вида £ e , где e- заданная точность поиска; - значение функции в центре тяжести.
Популярное: Личность ребенка как объект и субъект в образовательной технологии: В настоящее время в России идет становление новой системы образования, ориентированного на вхождение... Почему люди поддаются рекламе?: Только не надо искать ответы в качестве или количестве рекламы... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (764)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |