Плоскость пространство

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

Сущность симплексного метода иллюстрируем на рисунке

Начальная серия опытов соответствует вершинам исходного симплекса (точка 1,2, 3). Условия этих первых опытов берутся из области значений факторов, соответствующих наиболее благоприятным из известных режимов оптимизируемого процесса. Сравнивая между собой результаты опытов в точках 1, 2, 3, находят среди них самый «плохой», с точки зрения выбранного критерия оптимальности. Пусть, например, самым неудачным оказался опыт в точке 1. Этот опыт исключают из рассмотрения, а вместо него в состав симплекса вводят опыт в точке 4,которая симметрична точке 1 относительно противоположной стороны треугольника, соединяющей точки 2 и 3.

Далее сравнивают между собой результаты опытов в вершинах нового симплекса, отбрасывают самый «неудачный» из них и переносят соответствующую вершину симплекса в точку 5. Затем рассмотренная процедура повторяется в течение всего процесса оптимизации, если достигнут экстремум критерия оптимальности, то дальнейшее движение симплекса прекращается. Это значит, что новый шаг возвращает исследователя в предыдущую точку факторного пространства. Критерием окончания поиска могут служить размеры симплекса. Поиск можно прекратить, например, если все ребра симплекса станут меньше заданной достаточно малой величины.

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

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

В симплексном методе используют три основные процедуры: отображения вершины, деформации симплекса и уменьшения размеров симплекса. Ниже дана характеристика каждой из них.

а) Отображение вершины. Обозначим вершины симплекса, построенного на i-й итерации, следующим образом:

Здесь п — размерность вектора х. Пусть требуется отобразить вершину j относительно противоположной грани, т. е. найти координаты точки x ^j(i+1). Воспользуемся тем, что середина отрез­ка, соединяющего точки х ^jiи x ^j(i+1), одновременно является

Рис. 1. Основные операции симплексного алгоритма:

а — отображение «наихудшей» вершины; б — растяжение симплекса; в — сжатие симп­лекса; г — уменьшение размеров симплекса.

и центром тяжести противоположной грани. Это приводит к век­торному равенству

(1)

из которого для координаты k отображенной вершины получим:

(2)

б) Деформация симплекса. Если отображение j-й вершины симплекса оказалось «удачным», т. е. значение f в отображенной вершине больше, чем в вершинах, оставшихся неподвижными, то симплекс растягивают (рис. 1,6). При этом

Остальные вершины неподвижны, т. е.

Если операция отображения оказалась «неудачной», т. е. значение f в отображенной вершине х ^ji меньше, чем в оставших­ся неподвижными, то симплекс сжимают (рис. 1, в). При этом

в) Уменьшение размеров симплекса. Эта операция сводится к уменьшению всех ребер симплекса, причем самая «лучшая» его вершина неподвижна, а остальные стягиваются к ней (рис. 1,г).

Последовательность действий в симплексном алгоритме тако­ва. Сравнивают значения функции f в вершинах очередного симплекса. Для этого лишь в начальном цикле требуется п+1 вычисление f. В последующих циклах нужно только одно вычис­ление, так как вершины, кроме одной, неподвижны, и значение функции f в них известно из предыдущих вычислений. Если наи­меньшее значение f в цикле i оказалось в вершине, которая в предыдущем цикле была неподвижна, проводят операцию ото­бражения этой вершины. Если наименьшее значение f оказалось в вершине, которая в цикле i —1 переместилась, то в цикле i проводят операцию сжатия симплекса. Если же в вершине, ото­браженной в предыдущем цикле, Значение функции оказалось наибольшим, проводят операцию растяжения. Если при этом значение f увеличилось, то растяжение повторяют. Наконец, если максимум функции в вершинах симплекса, построенного в цик­ле i+l, оказался меньше, чем в предыдущем цикле, уменьшают размеры симплекса. Так, при стягивании к лучшей вершине х*¹ с уменьшением размера ребер в два раза координаты остальных вершин пересчитывают по формуле

Для лучшей вершины x ^j(i+1) = х ^ji

Алгоритм останавливается, когда длина наибольшего ребра симплекса окажется меньше некоторого заранее заданного чис­ла E. Действительно, найденные значения составляющих опти­мального решения можно реализовать с некоторой точностью. Эту точность можно принять за единицу масштаба измерения соответствующего параметра и считать е равным единице. В ка­честве решения принимают координаты лучшей вершины послед­него симплекса (рис. 2).

Рис. 2. Траектория поиска максимума с использованием симплексного алгоритма.