- •1 Постановка задачи 3
- •2 Теоретические сведения
- •2.1 Симплекс-метод
- •2.2 Метод покоординатного спуска нулевого порядка
- •2.3 Метод градиентного спуска с постоянным шагом
- •2.4 Метод наискорейшего градиентного спуска
- •3 Аналитическое решение уравнений
- •4 Исследование работы реализованных методов
- •4.1 Симплекс-метод
- •Метод покоординатного спуска нулевого порядка
- •4.3 Метод градиентного спуска с постоянным шагом
- •4.4. Метод наискорейшего градиентного спуска
- •5 Выводы
- •Список использованной литературы
2.3 Метод градиентного спуска с постоянным шагом
Стратегия решения задачи состоит в построении последовательности точек , k=0, 1, 2, ... nтаких, что ,k=0,1,2,...n. Точки последовательности вычисляются по правилу:k=0,1,2,... В качестве начала итераций выбирается произвольная точка. Величина шага задается пользователем и остается постоянной до тех пор, пока функция убывает в точках последовательности, т.е. до тех пор, пока выполняется соотношение. Если это условие не выполняется, то производится коррекция длины шага, и опять проверяется выполнение неравенства. Процесс завершается в точке, для которой выполняется условие окончания -.
2.4 Метод наискорейшего градиентного спуска
Градиентный спуск — метод нахождения локального минимума функции с помощью движения вдоль градиента. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Стратегия решения задачи состоит в построении такой последовательности точек, что значение функции в каждой последующей точке меньше чем в предыдущей. Точки последовательности вычисляются по правилу где величина шагаtkопределяется для каждого значенияkиз условия
.
3 Аналитическое решение уравнений
Решим заданные уравнения аналитическим способом.
Найдем первые частные производные:
;
Прировняем полученные производные к нулю и найдем корни системы уравнений:
Искомое решение уравнения: ;
Значение функции в найденной точке:
Найдем первые частные производные:
;
Прировняем полученные производные к нулю и найдем корни уравнения:
0
Искомое решение уравнения: ;
Значение функции в найденной точке:
4 Исследование работы реализованных методов
4.1 Симплекс-метод
Рассмотрим работу программы при различных входных данных.
В качестве рассматриваемой функции выберем
,
имеющую решение в точке .
Зададим исходные данные:
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,5 |
3 |
0,001 |
200 |
Окно программы при решении симплекс-методом с заданными параметрами – рисунок 3.
Рисунок 2
Вариации с коэффициентом отражения
Увеличим коэффициент :
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
2 |
0,5 |
3 |
0,001 |
200 |
Решение при новых параметрах – рисунок 4.
Рисунок 4
Уменьшим коэффициент :
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
0,5 |
0,5 |
3 |
0,001 |
200 |
Решение при новых параметрах – рисунок 5.
Рисунок 5
Вариации с коэффициентом сжатия
Восстановим исходные параметры – рисунок 3.
Зададим коэффициент сжатия и повторим расчет.
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,8 |
3 |
0,001 |
200 |
Решение при новых параметрах – рисунок 6.
Рисунок 6
Уменьшим коэффициент сжатия :
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,2 |
3 |
0,001 |
200 |
Решение при новых параметрах – рисунок 7.
Рисунок 7
Вариации с коэффициентом растяжения
Восстановим исходные параметры – рисунок 3.
Зададим коэффициент растяжения и повторим расчет.
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,5 |
3,5 |
0,001 |
200 |
Решение при новых параметрах – рисунок 8.
Рисунок 8
Уменьшим коэффициент растяжения :
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,5 |
2,5 |
0,001 |
200 |
Решение при новых параметрах – рисунок 9.
Рисунок 9
Можно сделать вывод, что применяя симплекс-метод для данной функции для получения наиболее точного решения, необходимо:
Задать коэффициент отражения в диапазоне [1; 2];
Задать коэффициент сжатия в диапазоне [0,5; 0,9];
Задать коэффициент растяжения в диапазоне [1; 1,9];
Также для уменьшения количества итераций необходимо:
Задать коэффициент отражения в диапазоне [0,8; 1];
Задать коэффициент сжатия в диапазоне [0,5; 0,8];
Задать коэффициент растяжения в диапазоне [1,8; 2;9]
.
В качестве рассматриваемой функции выберем
,
имеющую решение в точке .
Зададим исходные данные:
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,5 |
3 |
0,001 |
200 |
Окно программы при решении симплекс-методом с заданными параметрами – рисунок 10.
Рисунок 10
Вариации с коэффициентом отражения
Увеличим коэффициент :
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
2 |
0,5 |
3 |
0,001 |
200 |
Решение при новых параметрах – рисунок 11.
Рисунок 11
Уменьшим коэффициент :
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
0,5 |
0,5 |
3 |
0,001 |
200 |
Решение при новых параметрах – рисунок 12.
Рисунок 12
Вариации с коэффициентом сжатия
Восстановим исходные параметры – рисунок 10.
Зададим коэффициент сжатия и повторим расчет.
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,8 |
3 |
0,001 |
200 |
Решение при новых параметрах – рисунок 13.
Рисунок 13
Уменьшим коэффициент сжатия :
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,2 |
3 |
0,001 |
200 |
Решение при новых параметрах – рисунок 14.
Рисунок 14
Вариации с коэффициентом растяжения
Восстановим исходные параметры – рисунок 10.
Зададим коэффициент растяжения и повторим расчет.
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,5 |
3,5 |
0,001 |
200 |
Решение при новых параметрах – рисунок 15.
Рисунок 15
Уменьшим коэффициент растяжения :
A |
B |
C |
|
|
|
|
N |
(9; 9) |
(6; 8) |
(9; 6) |
1 |
0,5 |
2,5 |
0,001 |
200 |
Решение при новых параметрах – рисунок 16.
Рисунок 16
Можно сделать вывод, что применяя симплекс-метод для данной функции для получения наиболее точного решения, необходимо:
Задать коэффициент отражения в диапазоне [0,5; 1];
Задать коэффициент сжатия в диапазоне [0,5; 0,9];
Задать коэффициент растяжения в диапазоне [2,5; 3].
Также для уменьшения количества итераций необходимо:
Задать коэффициент отражения в диапазоне [0,8; 1];
Задать коэффициент сжатия в диапазоне [0,1; 0,7];
Задать коэффициент растяжения в диапазоне [2; 3,4].
Если необходимо добиться максимальной точности от данного метода, то требуется в дополнение к условиям получения наиболее точного решения, которые описаны выше, добавить ещё одно – задать максимально маленьким число для остановки алгоритма.
При для функцииполучим результат (рисунок 17)
Рисунок 17
При для функцииполучим результат (рисунок 18).
Рисунок 18