59

Министерство образования Российской Федерации

КАЗАНСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. А.Н.ТУПОЛЕВА

О.К. Мурга

ЧИСЛЕННЫЕ МЕТОДЫ

ОПТИМИЗАЦИИ

Учебное пособие

Казань 2004

УДК 519.6

Мурга О.К. Численные методы оптимизации: Учебное пособие. Казань: Изд-во Казан. гос. техн. ун-та, 2004, 59 с.

ISBN

Пособие содержит подробное описание основных численных методов оптимизации, алгоритмов их реализации, необходимые методические указания для выполнения лабораторных работ. Предназначено для студентов, обучающихся по направлению “Информатика и вычислительная техника”, учебные планы которых предусматривают изучение дисциплины “Методы оптимизации”.

Табл. 3 Ил. 4 Библиогр.: 4 назв.

Рецензенты: кафедра математического анализа ( Казанский государствен-

ный педагогический университет);

канд. техн. наук А.Н. Козин (Академия управления

"ТИСБИ").

Рекомендовано к изданию Учебно-методическим центром

КГТУ им.А.Н. Туполева

ISBN С Изд-во Казан. гос.техн. ун-та, 2004.

С Мурга О.К., 2004.

Оглавление

ВВЕДЕНИЕ 5

1. Методы одномерной оптимизации 6

1.1. МЕТОДЫ ПЕРЕБОРА 7

1.1.1. Метод равномерного поиска 7

1.1.2. Метод поразрядного поиска 7

1.2. МЕТОДЫ ИСКЛЮЧЕНИЯ ОТРЕЗКОВ 8

1.2.1. Метод дихотомии 8

1.2.2. Метод золотого сечения 9

1.3. СРАВНИТЕЛЬНЫЙ АНАЛИЗ МЕТОДОВ ОДНОМЕРНОГО ПОИСКА 11

1.4. ПОРЯДОК ВЫПОЛНЕНИЯ ЛАБОРАТОРНОЙ РАБОТЫ 11

1.5. ЗАДАНИЯ ДЛЯ ЛАБОРАТОРНОЙ РАБОТЫ. 12

2. Методы безусловной оптимизации 13

2.1. ПРЯМЫЕ МЕТОДЫ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ 13

2.1.1. Поиск по правильному симплексу 14

2.1.2. Поиск по деформируемому многограннику 15

2.1.3. Типовой пример. 19

2.1.4. Порядок выполнения лабораторной работы 20

2.1.5. Задания для лабораторной работы 21

2.2 МЕТОДЫ ПОКООРДИНАТНОГО СПУСКА 21

2.2.1 Метод циклического покоординатного спуска 22

2.2.2. Метод Зейделя. 23

2.2.3. Метод Хука-Дживса 24

2.2.4. Метод Пауэлла. 25

2.2.5. Типовые примеры 25

2.2.6. Порядок выполнения лабораторной работы 28

2.2.7. Задания для лабораторной работы 29

2.3. ГРАДИЕНТНЫЕ МЕТОДЫ 29

2.3.1. Метод градиентного спуска 30

2.3.2. Метод наискорейшего спуска 31

2.3.4. Порядок выполнения лабораторной работы 33

2.3.5. Задания для лабораторной работы 34

3. Методы оптимизации при наличии ограничений 35

3.1. МЕТОДЫ ПОСЛЕДОВАТЕЛЬНОЙ БЕЗУСЛОВНОЙ ОПТИМИЗАЦИИ 36

3.1.1. Метод штрафных функций 36

3.1.2. Метод барьерных функций 37

3.1.3. Комбинированный метод штрафных функций 38

3.1.4. Типовой пример 38

3.1.5. Задание для лабораторной работы 39

3.2. МЕТОД ВОЗМОЖНЫХ НАПРАВЛЕНИЙ 40

3.2.1. Постановка задачи выпуклого программирования 40

3.2.2. Описание метода возможных направлений 40

3.2.3. Построение начального приближения 41

3.2.4. Выбор наилучшего подходящего направления 43

3.2.5. Определение длины шага 46

3.2.6. Типовой пример 47

3.2.7. Задания для лабораторной работы 48

3.3. МЕТОД СЛУЧАЙНОГО ПОИСКА 48

3.3.1. Поиск с возвратом при неудачном шаге 49

3.3.2. Алгоритм наилучшей пробы 50

3.3.3. Алгоритм статистичекого градиента 50

3.3.4. Порядок выполнения работы 51

3.3.5. Задания для лабораторной работы 52