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