Сравнительный анализ методов оптимизации (стр. 5 из 7)
Если f (Е) <f (xn), то перейти к построению нового симплекса, иначе - перейти к шагу 5.
Шаг 5. Перейти к новому правильному симплексу с вдвое меньшим ребром (редуцирование), считая базовой вершиной х0. Остальные n вершин симплекса найти по формуле хi = (хi + х0) /2, i=1,. ., n. Перейти к шагу 1.
Геометрическая иллюстрация работы алгоритма в пространстве показана на рисунке 14, где точки х0, х1, х2 - вершины начального симплекса, а пунктиром указаны процедуры отражения.
Рисунок 14 - Поиск точки минимума функции
с помощью правильных симплексов в пространстве 
Замечания:
1. Следует иметь в виду, что если функция f (х) многомодальна, то описанным методом может быть найдена точка локального, а не глобального минимума f (х).
2. Если ограниченность снизу целевой функции не очевидна, то в алгоритм метода следует включить дополнительную процедуру останова.
2.2.5 Поиск точки минимума по деформируемому симплексу
Алгоритм, описанный в разд.2.2.4, можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. А именно, положение новой вершины вместо вершины хn, соответствующей наибольшему значению функции, находится сравнением и выбором наименьшего среди значений целевой функции в точках;
(7)Геометрическая иллюстрация этих процедур для пространства E2 приведена на рисунках 15 и 16.
Рисунок 15 - Пробные точки z1,z2,z3,z4 для перехода к новому симплексу
Рисунок 16 - Новые симлексы, полученные в результате процедур сжатия (а, б); отражения (в); растяжения (г).
Так как величина aÎ (0;
1), то выбор точек z1 и z2 соответствует сжатию симплекса; b» 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к растяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве En для n£ 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х0ÎEn, по формулам
, (8)где ei- i-й базисный вектор; a- параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек zi в формулах (9): a = 1/2, b = 1 и g =2.
Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.
Шаг 0. Выбрать параметр точности e, параметры a, b и g, базовую точку х0, параметр a и построить начальный симплекс. Вычислить f (х0).
Шаг 1. Вычислить значения функции в вершинах симплекса х1,..., xn.
Шаг 2. Упорядочить вершины х0,..., xn так, чтобы f (х0) £ … £f (хn).
Шаг 3. Проверить достижение заданной точности. Если оно выполняется, то вычисления завершить, полагая х * » х0, f* »f (х0). Иначе - перейти к шагу 4.
Шаг 4. Найти
и пробные точки zk, k=1, …, 4 пo формулам (9). Найти f (z*) = minf (zk). Если f (z*) < f (zn). то положить xn=z* и перейти к шагу 2. Иначе - перейти к шагу 5.Шаг 5. Уменьшить симплекс, полагая хi = (хi + х0) /2, i = 1,. ., n и перейти к шагу 1.
Замечание. Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. Например, после N шагов алгоритма из точки х0 снова строят симплекс, полагая а = ||x0-xn||.
С теоретической точки зрения описанные методы минимизации слабо исследованы, однако практика показывает их работоспособность.
2.2.6 Практическая реализация симплексных методов
Пусть заданы следующие условия:
Для первой вершины:
Для второй вершины:
Для третьей вершины:
Наибольшее значение функция принимает в точке2, ее и будем отражать. Для этого найдем точку С, лежащую между 1-й и 3-й точками:
Рассмотрим метод симплекса.
Находим координаты отраженной вершины Е и значение в ней функции:
Т. к.
, то строим новый симплекс на вершинах Е,1 и 3 и повторяем эту операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса.Результат рабочей программы представлен на рисунке 17. Листинг приведен в приложении В.
Рисунок 17 - Практическая реализация симплекс-метода
Перейдем к методу деформируемого симплекса.
Введем коэффициенты уменьшения и увеличения:
.Найдем значения функции 4-х точек в окрестности начальной:
Минимальное значение функция принимает в точке1, поэтому строим новый симплекс на вершинах Е,1 и 3 и повторяем выше указанную операцию до тех пор, пока среднеквадратичное отклонение не примет указанной величины, в противном случае приступаем к редуцированию - уменьшению размеров симплекса. Результат рабочей программы представлен на рисунке 18. Листинг приведен в приложении В.
Рисунок 18 - Практическая реализация метода деформируемого симплекса
3. Условная оптимизация
До сих пор рассматривались методы безусловной оптимизации, т.е. на параметры оптимизации не накладывались никакие ограничения, поэтому допустимая область определения определялась только лишь условием существования целевой функции.
Но в реальных задачах обязательно присутствуют ограничения типа равенств или неравенств и ограничения по пределам изменения:
Наличие ограничений приводит к изменению точки минимума, тогда как в задаче без ограничений данная точка может оказаться вне допустимой области.
Рассмотрим 2 метода решения задачи условной оптимизации:
Если наложены ограничения типа равенства, то из этого ограничения выразим одну переменную через другую (двумерный случай). Подставив полученную зависимость в целевую функцию, получим преобразованную целевую функцию без ограничений.
Целевая функция преобразуется так, чтобы эта преобразованная функция в допустимой области была бы близка к исходной, а в недопустимых областях имела бы значения, существенно большие, чем допустимые. Такие функции носят название штрафных, так как к исходной функции добавляются штрафы при приближении к недопустимым областям.
Например:
где R- параметр штрафа (некое число).
Существуют многочисленные штрафные функции для неравенств, а для равенств на практике применяется один вид, т.е. если имеем задачу
, тогда формируем штрафную функцию 
В данном курсовом проекте необходимо было максимизировать объемное тело, представленное на рисунке 19.
Рисунок 19 - Объем, который необходимо максимизировать
Указанное тело состоит из цилиндра и стоящего на нем сегмента сферы. Определим изменяемые параметры для данного случая (рисунок 20): r- радиус цилиндра (равен радиусу сферы), h- высота сегмента сферы и h2 - высота цилиндра.
Рисунок 20 - Изменяемые параметры
Для цилиндра:
.Для сегмента:
Тогда для всей фигуры:
Пусть площадь всего объема равна 200:
