2.3.4 Метод квантования симплексов

Симплексный метод относится к группе безградиентных методов детерминированного поиска. Основная идея метода заключается в том, что по известным значениям функции в вершинах выпуклого многогранника, называемого симплексом, находится направление, в котором требуется сделать следующий шаг, чтобы получить наибольшее уменьшение (увеличение) критерия оптимальности. Примером симплекса на плоскости является треугольник, в трехмерном пространстве – четырехгранная пирамида, в n-мерном пространстве – многогранник сn + 1 вершиной. Основным свойством симплекса является то, что против любой из вершин симплекса расположена только одна грань, на которой можно построить новый симплекс, отличающийся от прежнего расположением новой вершины, остальные вершины обоих симплексов – совпадают.

Наглядную иллюстрацию симплексного метода удобнее рассматривать на примере задачи отыскания минимального значения целевой функции двух независимых переменных (рис. 2.11).

Рисунок 2.11 –Блок-схема метода наискорейшего спуска

Алгоритм поиска заключается в следующем.

1) Определяются значения целевой функции в трех точкахS10,S20,S30, соответствующих вершинам симплекса. Из найденных значений выбирается наибольшее. В рассматриваемом примере – этоS10 (рис. 2.12).

Рисунок 2.12 –Поиск оптимума симплексным методом

2) Строится новый симплекс, для этого вершинаS10 исходного симплекса заменяется вершинойS11, расположенной симметрично вершинеS10 относительно центра грани, расположенной против вершиныS10. Построение нового симплексаS20 S30 S11 осуществляется определением центраА стороныS20 S30 треугольникаS10 S20 S30, после чего проводится прямаяS10A, на продолжении которой откладывается отрезокАS11 равныйS10А.

3) Вычисляется значение целевой функции в вершинеS11, которое сравнивается с известными значениями в вершинахS20 иS30. В результате определяется вершинаS30 с наибольшем значением целевой функции, подлежащая исключению при построении следующего симплексаS11 S20 S31.

Исключение из рассмотренных вершин симплексов с наибольшим значением целевой функции приводит к сходимости процесса к минимальному значению.

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

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