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

1.

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

2.

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

3.

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

4.

Актуальность практики
Затраты времени на метод Хука и Джависа
Затраты времени на метод симплекса
30
35
30
25
25
20
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. функция для оптимизации
1. оптимальное значение
2. начальная точка
2. значение функции в оптимальной точке
3. область определения
3. число итераций
4. шаг поиска
5. критерии остановки
11

12.

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

13.

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

14.

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

15.

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

16.

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