14.Сущность Симплекс-метода:

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

1. В области допустимых решений выбирается начальная точка Ос с координатами (x₁, x₂) – центр симплекса. Выбор точки Ос – произволен, однако от ее расположения зависит скорость решения. Вокруг точки Ос размещаются три точки – вершины симплекса y¹, y², y³, имеющие координаты (x₁, x₂), (x₁, x₂), (x₁, x₂) соответственно. Точки размещаются в вершинах равностороннего треугольника (рис.3.).

Рис.3. Схема для определения координат вершин исходного симплекса.

Выбор размера треугольника (симплекса) имеет важное значение. Чем больший размер имеет симплекс, тем быстрее будет получено решение, но тем ниже будет его точность! Размер симплекса определяется радиусом описанной окружности треугольника R. Рекомендуемое значение – 5..10% от наименьшего интервала варьирования переменной в задаче:

R=0,05..0,1(min{b_j- a_j}) (1)

После выбора точки-центра исходного симплекса и определения радиуса описанной окружности R. Рассчитываются координаты вершин y¹, y², y³ (рис.4.) – табл.1.

Рис.3. Схема «кантования» симплекса.

2. В 3-х выбранных точках определяется значение целевой функции. Если задача оптимизации имеет решение, то среди трех точек-вершин симплекса обязательно найдется точка с наихудшим значением целевой функции. После выявления такой точки производится «кантование» симплекса – его поворот относительно противолежащего ребра. По-другому, новое положение вершины определяется путем зеркального отражения относительно центра тяжести двух других точек. Допустим, в нашем случае наихудшей является вершина y¹ исходного симплекса. После кантования она должна прейти в положение y⁴ (рис.3.). Координаты нового положения вершины 1 можно рассчитать по формулам:

(2)

В данные формулы координаты наихудшей вершины входят со знаком (-), а координаты остальных вершин со знаком (+). Это правило определения координат отраженной вершины симплекса сохраняется и на других шагах расчета.

3. В новой вершине рассчитывается (или определяется экспериментом)значение целевой функции и снова производится сравнение трех значений ЦФ, выявляется вершина с наихудшим значением ЦФ и производится «кантование» симплекса способом, описанным выше (рис.4.). Допустим в новом положении симплекса худшей оказывается вершина y² после кантования она должна перейти в положение y⁵ . По ходу расчета заполняется таблица 2. Видно, что на каждом шаге расчета производится только одно вычисление ЦФ. Поэтому симплекс метод является более быстрым по-сравнению с методом покоординатного спуска (подъема). Траектория движения к оптимуму при использовании симплекс-метода близка к траектории при использовании быстрого градиентного метода.

Рис.4. Схема «движения» симплекса.

Таблица 2.

Если ЦФ имеет в ОДР оптимум то симплекс будет направленно «двигаться» по направлению к нему. Помешать этому могут особые случаи движения, вызванные зацикливанием алгоритма.

1. «Качание» симплекса. Допустим на третьем шаге расчета худшей оказывается вершина y⁴ после кантования симплекса она переходит в положение y⁶ . Но вычислив значение целевой функции в точке y⁶ , мы получаем худшее значение из всех вершин симплекса. Получается, что симплекс должен вернуться в предыдущее положение, т.е. вершина y⁶ должна вернуться в положение y⁴ . Но в этой точке значение ЦФ уже было вычислено на предыдущем шаге и оно оказалось худшим из всех. Т.е. симплекс начинает «качаться» относительно ребра y³ – y⁵ . Если расчет симплекс-методом производится на ЭВМ, то в данном случае происходит зацикливание программы. Такое поведение симплекса связано с наличием на поверхности, изображающей ЦФ «гребня» или «оврага» рис.5., при этом точки y³ и y⁵ находятся на вершине «гребня» или на дне «оврага». В данном случае необходимо отразить наихудшую вершину симплекса из находящихся на «гребне» (дне «оврага»). По-другому: отражению подлежит средняя по значению ЦФ вершина. Допустим расчет дает y⁵ < y³ < y⁴ (в случае «оврага») или y⁴ < y³ < y⁵ (в случае «гребня»), тогда новое положение вершины симплекса определяется путем отражения вершины y³ .

Рис.5. «Качание» симплекса.

2. «Вращение» симплекса вокруг вершины. Допустим, что вершина y³ перешла в положение y⁷ . Вычислив значение ЦФ в данной точке получаем:

y⁵ < y⁷ < y⁴ (ищем минимум)

или:

y⁵ > y⁷ >y⁴ (ищем максимум)

Т.е. отражать нужно вершину y⁴ . После отражения она прейдет в положение y⁸ и мы будем иметь:

y⁵ < y⁸ < y⁷ (или y⁵ > y⁸ >y⁷ )

т.е. вершина y⁷ должна прейти в новое положение y⁹. Если далее окажется, что:

y⁵ < y⁹ < y⁸ (или y⁵ > y⁹ >y⁸ )

то, вершина y⁸ подлежит отражению и должна перейти в точку y⁶ . Значение ЦФ в т. y⁶ было вычислено ранее и оно оказалось хуже, чем в т. y⁵. Если данное значение хуже, чем в т. y⁹ , то симплекс перейдет в положение y³ y⁵ y⁶ , которое уже рассматривалось ранее, и далее начнет вращаться вокруг точки y⁵ . Т. y⁵ оказывается окруженной точками с худшим значением ЦФ!!!!! Т.е. в данной точке находится локальный оптимум. Таким образом, вращение симплекса является признаком оптимума и, соответственно, признаком окончания расчета.

15.Особенности реализации симплекс-метода в САПР:

Благодаря своей простоте и надежности симплекс-метод получил широкое распространение в модулях оптимизации современных пакетов компьютерного моделирования. Существует множество модификаций метода. Остановимся на их общих особенностях. В основном они связаны с повышением точности и быстродействия алгоритма.

1. Выбор начального симплекса. Как правило точки –вершины начального симплекса размещаются внутри ОДР случайным образом. Производится проверка соблюдения ОГР. Если ОГР нарушаются, то координаты точки пересчитываются.

2. В ходе расчета симплекс может менять свою форму и размеры. Изменение формы и размеров может происходить по двум причинам. Во-первых при отражении симплекса используется некоторый коэффициент отражения k, обычно равный 1.3. k равен отношению расстояний ОА’/OA (рис.6.).

Рис.6. Коэффициент отражения симплекса.

Если новая вершина симплекса нарушает ГРУ и ОГР, или наблюдаются особые случаи движения симплекса, то коэффициент отражения уменьшается в два раза (рис.7.). Коэффициент отражения может быть уменьшен в областях большого изменения ЦФ и увеличен в «пологих» областях. Другой причиной изменения формы и размеров симплекса является его взаимодействие с границами ОДР (рис.7.).

Рис.7. Изменение формы и размеров симплекса в ходе расчета.

При выходе вершины симплекса за границу ОДР в некоторых вариантах реализации симплекс-метода она принудительно возвращается на границу и форма симплекса искажается. При длительном взаимодействии с границей симплекс может потерять размерность (рис.8.).

Рис.8. Взаимодействие симплекса с границами.

3. Использование различных критериев окончания расчета. Если в приведенном выше варианте реализации симплекс-метода критерием окончания расчета фактически являлось зацикливание алгоритма (время расчета), то в системах САПР используются более надежные расчетные критерии.

Критерий малого изменения ЦФ (для пологих поверхностей):

, (3)

где - среднее значение ЦФ в вершинах симплекса.

p – число вершин симплекса

- наперед заданное малое число.

Для горизонтальной плоскости =0.

Критерий малого изменения параметров (для крутых поверхностей):

; (4)

где - среднее значение параметров в вершинах симплекса;

- наперед заданное малое число;

n – число переменных в задаче;

i – порядковый номер переменной.

Для вертикальной плоскости =0.