Алгоритмы прямого поиска экстремума функции (Метод Хука и Дживса, метод симплекса)

1.

Федеральное агентство по рыболовству
Федеральное государственное бюджетное образовательное
учреждение высшего образования
«Астраханский государственный технический университет»
Система менеджмента качества в области образования, воспитания, науки и инноваций
сертифицирована
ООО «ДКС РУС» по международному стандарту ISO 9001:2015
КУРСОВОЙ ПРОЕКТ
по дисциплине:
“Основы алгоритмизации и программирование”
на тему:
«Алгоритмы прямого поиска экстремума функции
(Метод Хука и Дживса, метод симплекса)»
Выполнил: обучающийся группы ДИПРб-11/2
Федоров Сергей Алексеевич
Руководитель: асс. Кравченкова Елена Павловна
Астрахань 2025

2.

Анализ предметной области
Электроника
Алгоритмы
прямого поиска
экстремума
функции
Компьютерные
науки
Медицинские
исследования
Проектирование
Информационные
технологии
2

3.

Смежная дисциплина
Основы
алгоритмизации и
программирование
Математический
анализ
Алгоритмы
прямого поиска
экстремума
функции
3

4.

Актуальность курсового проекта
Затраты времени на метод Хука-Дживса
Затраты времени на метод симплекса
30
35
25
20
25
Минуты
Минуты
30
20
15
15
10
10
5
5
0
0
Формулировка... Приведение к...
Построение
начальной...
Итерация
симплекс...
Проверка...
Итерпретация...
Определение
задачи
Оценка
начальной точки
Поиск по
направлениям
Итерация поиска
Завершение
Самостоятельно
Самостоятельно
4

5.

ЦЕЛЬ КУРСОВОГО ПРОЕКТА
Углубленное изучение материалов по дисциплинам «Основы
алгоритмизации и программирование», «Математический анализ»
по теме «Алгоритмы прямого поиска экстремума функции (Метод
Хука-Дживса, метод симплекса)».
5

6.

ЗАДАЧИ КУРСОВОГО ПРОЕКТА
Для реализации поставленной цели, необходимо решить следующие задачи:
1. Анализ предметной области по теме: «Алгоритмы прямого поиска экстремума функции (Метод
Хука и Дживса, метод симплекса)».
2. Изучение теоретического материала по дисциплинам «Основы алгоритмизации и
программирование», «Математический анализ» по теме: «Алгоритмы прямого поиска экстремума
функции (Метод Хука и Дживса, метод симплекса)».
3. Разработка рабочего проекта, позволяющее пользователю применять эти методы
6

7.

ТЕОРЕТИЧЕСКИЙ МАТЕРИАЛ
Алгоритмы прямого поиска функции — это класс методов
оптимизации, которые используются для нахождения экстремумов
(максимумов или минимумов) заданной функции. Эти алгоритмы не
требуют вычисления производных и могут применяться к функциям,
которые могут быть недифференцируемыми, имеют разрывные точки
или являются сложными для анализа. Они особенно полезны в
ситуациях, когда функция задана экспериментально или в виде
черного ящика, когда доступ к её аналитической форме ограничен.
7

8.

Метод Хука-Дживса
Метод Хука-Дживса — это метод
прямого поиска для оптимизации
функций, сочетающий исследующий
поиск (локальное исследование
окрестности) и поиск по образцу
(ускоренное движение в направлении
улучшения).
8

9.

Метод симплекса
Метод симплекса — это
метод прямого поиска для
оптимизации функций,
сочетающий деформацию
симплекса (пошаговое
изменение многомерной
фигуры) и адаптацию шага
(растяжение, сжатие или
отражение для улучшения
результата).
9

10.

Диаграмма вариантов использования
10

11.

Интерфейс программы
Рисунок 1 - интерфейс программы с выбранным
методом решения Хука-Дживса
Рисунок 2 - интерфейс программы с выбранным
методом решения методом симплекса
11

12.

ВХОДНЫЕ И ВЫХОДНЫЕ ДАННЫЕ
Входные данные:
Выходные данные:
1. начальная точка
1. оптимальное значение
2. область определения
2. значение функции в оптимальной точке
3. шаг поиска
3. число итераций
12

13.

Средства разработки
Язык разработки: С++ (17)
Среда разработки: Visual Studio (17.12.3)
Документации: MS Word 2021
Презентация: Power Point 2021
13

14.

Сведения о проекте
Среда разработки: Visual Studio(17.12.3)
ЯП: C++(17)
Количество строк код: 153
14

15.

Системные требования
1. Процессор: Intel/Amd-совместимый процессор с тактовой
частотой не менее 1,6 ГГц;
2. Оперативная память: не менее 8 ГБ ОЗУ;
3. Жесткий диск: не менее 20 ГБ свободного места на жестком
диске;
4. Операционная система: Windows 7/8/10 (x64)
15

16.

Заключение
Затраты времени на метод Хука-Дживса
Затраты времени на метод симплекса
30
35
30
25
25
20
20
15
15
10
5
10
0
Формулировка...
5
Приведение к...
Построение
начальной...
Итерация
симплекс...
Проверка...
Итерпретация...
0
Определение задачи Оценка начальной
точки
Поиск по
направлениям
Самостоятельно
Итерация поиска
С помощью программы
Завершение
Самостоятельно
С помощью программы
16

17.

Спасибо за внимание!
17