Конспект лекций. — Новосибирск: Изд-во НГТУ, 2009. — 126 с.
Работа подготовлена на кафедре прикладной математики для студентов III курса ФПМИ (направление 010500 – Прикладная математика и информатика, специальности 010503 – Математическое обеспечение и администрирование информационных систем.
Курс лекций рассчитан на один семестр и предназначен для студентов ФПМИ, но может быть полезен и студентам других специальностей. Пособие должно помочь студентам овладеть прикладными методами оптимизации.
Содержание.
Введение.
Методы одномерного поиска.
Метод дихотомии.
Метод золотого сечения.
Метод Фибоначчи.
Контрольные вопросы.
Прямые методы поиска.
Алгоритм Гаусса.
Алгоритм Хука и Дживса.
Алгоритм Розенброка.
Симплексный метод Нелдера-Мида или поиск по деформируемому многограннику.
Метод Пауэлла и сопряженные направления.
Обоснование применения сопряженных направлений в алгоритмах оптимизации.
Алгоритм метода Пауэлла.
Контрольные вопросы.
Методы первого порядка.
Алгоритм наискорейшего спуска.
Метод сопряженных градиентов.
Многопараметрический поиск.
Контрольные вопросы.
Методы второго порядка (Метод Ньютона).
Контрольные вопросы.
Методы переменной метрики.
Введение.
Метод Бройдена.
Метод Дэвидона-Флетчера-Пауэлла.
Алгоритмы Пирсона.
Проективный алгоритм Ньютона-Рафсона.
Методы Гринштадта и Гольдфарба.
Алгоритм Флетчера.
Алгоритмы с аппроксимацией матрицы Гессе.
Контрольные вопросы.
Методы штрафных функций.
Контрольные вопросы.
Статистические методы поиска.
Введение.
Простой случайный поиск.
Простейшие алгоритмы направленного случайного поиска.
Алгоритм парной пробы.
Алгоритм наилучшей пробы.
Метод статистического градиента.
Алгоритм наилучшей пробы с направляющим гиперквадратом.
Алгоритмы глобального поиска.
Контрольные вопросы.
Линейное программирование.
Основные определения и теоремы.
Основная теорема линейного программирования.
Симплекс метод.
Введение в симплекс-метод.
Алгоритм симплекс метода.
Вырожденность в задачах линейного программирования.
Двойственность задач линейного программирования.
Введение.
Преобразования при решении прямой и двойственной задач.
Теоремы двойственности.
Основная теорема двойственности линейного программирования.
Вторая теорема двойственности.
Метод последовательного уточнения оценок.
Контрольные вопросы.
Методы решения транспортной задачи.
Формулировка классической транспортной задачи.
Метод северо-западного угла.
Метод минимального элемента.
Теорема, лежащая в основе метода потенциалов.
Алгоритм метода потенциалов.
О вырожденности транспортной задачи.
Контрольные вопросы.
Транспортная задача с ограничениями.
Постановка задачи.
Метод потенциалов для определения оптимального плана.
Построение опорного плана.
Контрольные вопросы.
Транспортная задача по критерию времени.
Контрольные вопросы.
Задача о максимальном потоке в транспортной сети.
Постановка задачи.
Алгоритм построения максимального потока в транспортной сети.
Контрольные вопросы.
Параметрическое линейное программирование.
Постановка.
Алгоритм.
Контрольные вопросы.
Литература.
Рекомендуемая литература.
