2015-08-21
6728
Описание алгоритма:
Суть метода заключается в исследовании целевой функции в вершинах некого "образца", построенного в пространстве вокруг "базовой" точки. Вершина, давшая наибольшее значение целевой функции отображается относительно двух других вершин и таким образом становится новой базовой точкой, вокруг которой строится новый образец и снова выполняется поиск. В случае двух переменных симплексом является равносторонний треугольник, в трёхмерном пространстве - тетраэдр.
Работа алгоритма начинается с построения регулярного симплекса в пространстве независимых переменных и оценивания значений целевой функции в каждой точке. Затем определяется вершина с максимальным значением целевой функции и проектируется через центр тяжести оставшихся вершин в новую точку.
Процедура продолжается до тех пор, пока не будет накрыта точка минимума.
Некоторые правила:
1. Если вершина с максимальным значением целевой функции построена на предыдущем шаге, то отбрасывается вершина со следующим по величине значением целевой функции.
2. Если вокруг одной из вершин начинается циклическое движение, то необходимо уменьшить размеры симплекса.
Поиск заканчивается тогда, когда размеры симплекса или разность значений целевой функции становятся достаточно малыми.
При заданной начальной точке 
и масштабном множителе 
, координаты остальных 
вершин симплекса в 
- мерном пространстве вычисляются по формуле:
Приращения 
и 
определяется по формулам:
Величина 
выбирается исследователем, исходя из характеристики решаемой задачи. При 
ребро симплекса имеет единичную длину.
Вычисление центра тяжести:
Если 
- точка, подлежащая отражению, то координаты центра тяжести определяются по формуле:
Координаты новой вершины удовлетворяют уравнению:
Для того чтобы симплекс обладал свойством регулярности, отображение должно быть симметричным, т.е. 
Если некоторая вершина симплекса не исключается на протяжении нескольких итераций, то необходимо уменьшить размер симплекса и построить новый симплекс, выбрав в качестве базовой точку с минимальным значением целевой функции.
Алгоритм метода:
Шаг 1. Задать: 1. Начальную точку х(0) ;
2. Масштабный множитель α;
3. Приращения δ1 и δ2 ;
4.Условие окончания поиска. Перейти к шагу 2.
Шаг 2. Вычислить координаты вершин х(1) и х(2) симплекса. Перейти к
шагу 3.
Шаг 3. Определить значения целевой функции в вершинах симплекса. Перейти к шагу 4.
Шаг 4. Вершина, которой соответствует наибольшее значение целевой функции, построена на предыдущей итерации?
Да: отображается вершина, которой соответствует следующее по величине значение целевой функции
Нет: отображается точка с наибольшим значением целевой функции относительно двух других вершин симплекса. Перейти к шагу 5.
Шаг 5. Проверка на условие окончания.
Да: закончить поиск; результат- точка с наименьшим значением целевой функции;
Нет: перейти к шагу 3.
Ход решения:
Исходные данные:
Для построения исходного симплекса необходимо задать начальную точку и масштабный множитель. Пусть 
.
Тогда:
Вычисляем координаты двух других вершин симплекса
Значения целевой функции в этих точках соответственно равны:
Так как в точке 
целевая функция принимает максимальное значение, то необходимо отразить точку 
относительно центра тяжести остальных вершин симплекса.
В полученной точке 
, т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и .
В полученной точке 
, т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
, т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек и 
.
В полученной точке 
, т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек и 
.
В полученной точке 
, т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
, т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
, т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и .
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и 
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек и 
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек и 
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку 
относительно центра тяжести точек 
и
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку относительно центра тяжести точек и 
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке соответствует максимальное значение целевой функции. Наблюдается циклическое движение вокруг точки . Для получения более точного результата уменьшаем размер симплекса.
Уменьшаем размер симплекса.
В качестве новой базисной точки, примем точку 
. Вычислим координаты остальных двух вершин базиса:
Так как в точке 
целевая функция принимает максимальное значение, то необходимо отразить точку 
относительно центра тяжести остальных вершин симплекса.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Следует отразить точку 
относительно центра тяжести точек 
и .
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку 
относительно центра тяжести точек 
и 
.
В полученной точке 
. Новый симплекс образован вершинами 
, причём точке 
соответствует максимальное значение целевой функции. Наблюдается циклическое движение вокруг точки 
. Завершаем поиск.
Искомая точка:
Для получения более точного результата необходимо уменьшить размер симплекса.
Решение поставленной задачи симплекс методом представлено на рисунке 1.
|
| Рисунок 1 – решение задачи симплекс-методом |
