Задача 2.
Постановка задачи. Cоставить алгоритм нахождения с требуемой точностью экстремума функции f(X) двух переменной симплекс-методом с изменяемой длиной ребра. Начальное расположение симплекса – одна из вершин в начале координат.
Алгоритм метода.
1. Начальный этап. Расчет координат симплекса в соответствии с таблицей
№ вершины | x1 | x2 |
1 | 0 | 0 |
2 | P | Q |
3 | Q | P |
где , .
Задать k = 0.
2. Определение вершин с максимальным и минимальным значением функции. Определяют те вектора X многогранника, которые дают максимальное и минимальное значение f(X), а именно
f(Xh(k)) = maxf(X1(k)), ..., f(Xn+1(k))};
f(Xl(k)) = minf(X1(k)), ..., f(Xn+1(k))}.
3. Расчет координат центра тяжести. Координаты центра тяжести рассчитываются по формуле
, j =1, …, n,
где индекс j обозначает координатное направление.
Если на k-1 этапе произошла редукция, то перейти к шагу 5, иначе к шагу 4.
4. Определение зацикливания. Зацикливание происходит в случае, если номера вершин с максимальным значением f(X) совпадают на k-ом и (k-1)-ом шагах, т.е.
h(k) = h(k-1).
Если зацикливание не обнаружено, то переход к этапу 5, в противном случае происходит проверка условия окончания поиска
В случае выполнения условия переход к этапу 7, иначе к этапу 6.
5. Отражение. Представляет проектирование Xh(k) через центр тяжести в соответствии с соотношением
.
Установить k = k + 1 и перейти к этапу 2.
6. Редукция. Расчет координат вершин симплекса осуществляется в соответствии с формулой
Xi(k+1) = Xl(k) + 0,5(Xi(k) - Xl(k)), i = 1, …, n + 1.
Установить k = k + 1 и перейти к шагу 2.
7. Выдача полученных результатов. В качестве решения задачи взять вершину с минимальным значением f(X).
Реализация метода. На рис. 2.3 приведено содержание ячеек рабочего листа, используемых для осуществления первых двух итераций при нахождении данным методом минимума функции f(X) = (x1 - 2)2 + (x2 - 3)2 при начальной длине ребра, равной 1, и точности поиска 0,01
Результаты решения задачи для условий, описанных выше, приведены на рис. 2.4.