Методы Хука-Дживса (стр. 2 из 2)
В приведенной программе минимальная длина шага равна
, но она может быть изменена . Для контроля за выполнением процедуры в программу введена печать промежуточных результатов. Для увеличения скорости счета могут быть удалены строки вывода подсказок и пояснений.Процедура calculate вычисляет значение минимизируемой функции ,в нашем случае : f (x1,x2) = 3x12+4x1x2+5x22 ,
при ограничениях x1 
x2 x1+x2 
.
Минимум, равный 44, достигается в точке (3;1) при ограничении x1+x2=4.
Для начальной точки (4;3) и при длине шага , равной единице , программой успешно решена задача минимизации .
Ниже приведена распечатка результата работы программы :
Модифицированный метод Хука-Дживса
(при наличииограничений)
Введите число переменных
2
Введите начальную точку х1,х2,…,хN
4
3
Введите длину шага
1
Начальное значение функции 141.000
4.000
3.000
Пробный шаг 108.000
3.000
3.000
Пробный шаг 71.000
3.000
2.000
Поиск по образцу 1.70000000000001566Е+0038
2.000
1.000
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Поиск по образцу 1.70000000000001566Е+0038
3.000
0.000
Пробный шаг 48.000
4.000
0.000
Пробный шаг 48.000
4.000
0.000
Замена базисной точки 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Уменьшить длину шага
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Уменьшить длину шага
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Уменьшить длину шага
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Уменьшить длину шага
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Уменьшить длину шага
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Уменьшить длину шага
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Уменьшить длину шага
Пробный шаг 44.000
3.000
1.000
Пробный шаг 44.000
3.000
1.000
Уменьшить длину шага
Минимум найден
х(1) = 3.000
х(2) = 1.000
Минимум функции равен 44.000
Количество вычислений равно 74
Для начальной точки (3;4) и длины шага , равной единице , программой также успешно решена задача минимизации .
Для начальной точки (5;6) и длины шага , равной единице , задача не решена , т.к. программа остановилась в точке (1;3) , т.е. на активном ограничении , и выдала неверный результат .
Распечатка результата работы программы приведена ниже :
Модифицированный метод Хука-Дживса
(при наличииограничений)
Введите число переменных
2
Введите начальную точку х1,х2,…,хN
5
6
Введите длину шага
1
Начальное значение функции 375.000
5.000
6.000
Пробный шаг 324.000
4.000
6.000
Пробный шаг 253.000
4.000
5.000
Поиск по образцу 155.000
3.000
4.000
Пробный шаг 124.000
2.000
4.000
Пробный шаг 81.000
2.000
3.000
Поиск по образцу 1.70000000000001566Е+0038
0.000
1.000
Пробный шаг 1.70000000000001566Е+0038
0.000
1.000
Пробный шаг 1.70000000000001566Е+0038
0.000
1.000
Замена базисной точки 81.000
2.000
3.000
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Поиск по образцу 1.70000000000001566Е+0038
0.000
3.000
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Замена базисной точки 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Уменьшить длину шага
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Уменьшить длину шага
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Уменьшить длину шага
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Уменьшить длину шага
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Уменьшить длину шага
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Уменьшить длину шага
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Уменьшить длину шага
Пробный шаг 60.000
1.000
3.000
Пробный шаг 60.000
1.000
3.000
Уменьшить длину шага
Минимум найден
х(1) = 1.000
х(2) = 3.000
Минимум функции равен 60.000
Количество вычислений равно 89
Аналогичные неутешительные результаты были получены для начальной точки (5;6) и длины шага , равной 0.5 .Неверное решение было найдено в точке (1.5;2.5) . Для начальной точки (4;3) и длины шага , равной 0.5 ,программа работала нормально , но было получено неверное решение в точке (2.5;1.5) .
Проблема понятна . С помощью данного метода невозможно двигаться вдоль границы области ограничений и сходимость достигается в первой же точке границы , где и находится решение . Общая задача оптимизации при наличии ограничений очень сложна и для получения практического метода решения требуются более изощренные процедуры , чем приведенная выше .
Литература:
1. Б.Банди “Методы оптимизации”
2. Р.Хук , Т.А.Дживс “ Прямой поиск решения для числовых и статических проблем ”, 212-219 с., 1961 .