Пусть требуется найти безусловный минимум функции n переменных . Предполагается, что серьёзных ограничений на область определения функции нет, то есть функция определена во всех встречающихся точках.
Параметрами метода являются:
коэффициент отражения α > 0, обычно выбирается равным 1.
коэффициент сжатия β > 0, обычно выбирается равным 0,5.
коэффициент растяжения γ > 0, обычно выбирается равным 2.
«Подготовка» . Вначале выбирается n + 1 точка, образующие симплекс n-мерного пространства. В этих точках вычисляются значения функции: .
«Сортировка» . Из вершин симплекса выбираем три точки: xh с наибольшим (из выбранных) значением функции fh, xg со следующим по величине значением fg и xl с наименьшим значением функции fl. Целью дальнейших манипуляций будет уменьшение по крайней мере fh.
Найдём центр тяжести всех точек, за исключением xh: . Вычислять fc = f(xc) не обязательно.
«Отражение» . Отразим точку xh относительно xc с коэффициентом α (при α = 1 это будет центральная симметрия, в общем случае — гомотетия) , получим точку xr и вычислим в ней функцию: fr = f(xr). Координаты новой точки вычисляются по формуле:
xr = (1 + α)xc − αxh.
Далее смотрим, насколько нам удалось уменьшить функцию, ищем место fr в ряду fh,fg,fl.
Если fr < fl, то направление выбрано удачное и можно попробовать увеличить шаг. Производим «растяжение» . Новая точка xe = (1 − γ)xc + γxr и значение функции fe = f(xe).
Если fe < fl, то можно расширить симплекс до этой точки: присваиваем точке xh значение xe и заканчиваем итерацию (на шаг 9).
Если fe > fl, то переместились слишком далеко: присваиваем точке xh значение xr и заканчиваем итерацию (на шаг 9).
Если fl < fr < fg, то выбор точки неплохой (новая лучше двух прежних) . Присваиваем точке xh значение xr и переходим на шаг 9.
Если fh > fr > fg, то меняем местами значения xr и xh. Также нужно поменять местами значения fr и fh. После этого идём на шаг 6.
Если fr > fh, то просто идём на следующий шаг 6.
В результате (возможно, после переобозначения) fr > fh > fg > fl.
«Сжатие» . Строим точку xs = βxh + (1 − β)xc и вычисляем в ней значение fs = f(xs).
Если fs < fh, то присваиваем точке xh значение xs и идём на шаг 9.
Если fs > fh, то первоначальные точки оказались самыми удачными. Делаем «глобальное сжатие» симплекса — гомотетию к точке с наименьшим значением xl:
, .
Последний шаг — проверка сходимости. Может выполняться по-разному, например, оценкой дисперсии набора точек. Суть проверки заключается в том, чтобы проверить взаимную близость полученных вершин симплекса, что предполагает и близость их к искомому минимуму. Если требуемая точность ещё не достигнута, можно продолжить итерации с шага 2.
[править] Источник
ВУЗы и колледжи
Математики, вопрос к вам. Подскажите алгоритм решения симплексного метода
простейший симплексный алгоритм ))) это 5-й класс задача))))
Похожие вопросы
- Задача по генетике. Подскажите, пожалуйста, решение или хотя бы принци или алгоритм решения подобных задач на потомство.
- В чем заключается метод комплексных амплитуд? Каков алгоритм анализа цепей методом комплексных амплитуд?
- Помогите составить алгоритм решения задач по химии на изомеры
- Решение системы методом Гаусса
- Напишите плззз алгоритм решений неравенств с модулем!
- Помогите, пожалуйста, с решением КЗЛП методом искусственного базиса
- Решение неравенств методом интервалов
- Подскажите пожалуйста решение и что за тема (раздел) по которой можно научится решать
- Математики, вопрос к вам! Для поступающих в МГУ в 1975 году была предложена задача
- Подскажите литературу, где описываются методы анализа качества прогнозов?