Сравнительный анализ методов оптимизации (стр. 4 из 5)
Шаг 3.Сделать пробный шаг y=
+Dje j . Если f ( ) £f(y), то перейти к шагу 5, иначе – к шагу 4.Шаг 4.Положить
= у.Шаг 5.Положить j= j+ 1. Если j£n, то перейти к шагу 2. В противном случае исследующий поиск окончен – получена точка
для которой f ( ) <f(y), если ¹ х.3.5 Пример решения методами правильного симплекса, деформируемого симплекса, покоординатного спуска, Хука – Дживса
Дана функция
, с=7; d=7.Найти минимум функции с точностью ε=0,001
Метод правильного симплекса
Выбираем длину стороны треугольника l=10ε=0,0001
Вершины треугольника находим следующим образом:
A(
);B(
);D(
).A(1,065; 0,918);
B(1,07,0,927);
D(1,075,0,918).
Шаг 0
F(A)=10,903; F(B)=11,081; F(D)=11,051.
F1<F2<F3:
F1=F(A); F2=F(D); F3=F(B).
Отражаем вершину 3 относительно центра тяжести.
F(E)=10,873.
Значение функции в найденной точке меньше, значения функции в точке 1, поэтому принимаем новый симплекс (1,2,E).
Шаг 1
F(1)=10,903; F(2)=11,081; F(E)=10,873.
F1<F2<F3:
F1=F(E); F2=F(1); F3=F(2).
Отражаем вершину 3 относительно центра тяжести.
F(E)=10,726.
Значение функции в найденной точке меньше, значения функции в точке 1, поэтому принимаем новый симплекс (1,2,E).
, 
.В результате получаем x1=0,125, x2=0,208, f(x1, x2)=-0,41.
Метод деформируемого симплекса
Выбираем длину стороны треугольника l=5ε=0,005
Вершины треугольника находим следующим образом:
A(
);B(
);D(
).A(1,065; 0,918);
B(1,07,0,927);
D(1,075,0,918).
Принимаем коэффициенты выбора пробных точек k1=0,5, k2=1, k3=2.
Шаг 0
F(A)=10,903; F(B)=11,081; F(D)=11,051.
F1<F2<F3:
F1=F(A); F2=F(D); F3=F(B).
Находим центр тяжести вершины 3 относительно вершин 1 и 2:
Выбираем пробные точки:
F(z1)=10,966.
F(z2)=11,018.
F(z3)=11,044.
F(z3)=11,097.
Значение функции в z1 точке меньше, значения функции в точке 3, поэтому принимаем новый симплекс (1,2,z1).
Шаг 1
F(1)= 10,903; F(2)= 11,051; F(z1)=10,966.
F1<F2<F3:
F1=F(1); F2=F(z1); F3=F(2).
Выбираем пробные точки:
F(z1)=10,955.
F(z2)=10,998.
F(z3)=11,019.
F(z3)=11,062.
Значение функции в точке z1 меньше, значения функции в точке 3, поэтому принимаем новый симплекс (1,2,z1).
, 
.В результате получаем x1=-0,012, x2=0,419, f(x1, x2)=-0,014.
Метод покоординатного спуска
(1,065; 0,918).
α=5ε=0,005.
Шаг 1
Координату
закрепляем, 
Т.к.
,Следовательно
Получим x1=0,012,
Шаг 2
Принимаем
и закрепляем, 
Т.к.
, 
Получим x2=0,199,
Продолжаем поиск до тех пор, пока не будет выполнено условие
В результате получаем x1=0,117, x2=0,189, f(x1, x2)=-0,411.
Метод Хука-Дживса
x0: (1,065; 0,918).
Δ1=5*ε=5*0,001, Δ2=5*ε=5*0,001.
λ=2.
Шаг 1
Принимаем k1=-1, k2=-1 – коэффициенты, определяющие направление поиска.
В данном направлении функция убывает.
Шаг 2
Принимаем k1=-1, k2=-1.
В данном направлении функция убывает.
Продолжаем поиск до тех пор, пока не будет выполнено условие
В результате получаем x1=0,115, x2=0,198, f(x1, x2)=-0,411.
4. Основы линейного программирования
Если в задаче оптимизации целевая функция и все ограничения заданы в виде линейных функций, то этот класс задач носит название задач линейного программирования.
Примечание: если переменных две, то задача может быть решена и геометрически.
Точка оптимального решения является крайней точкой пересечения выпуклых множеств,
4.1 Симплекс-метод решения задачи ЛП
Допустим, что есть базисное решение. Не трудно заметить, что в качестве базисного решения можно принять:
, 
Суть симплекс-метода заключается в переходе решения к другим базисным допустимым решениям, при которых значение целевой функции не убывает.