Методы оптимизации, Габасов Р., 2011

Методы оптимизации, Габасов Р., 2011.
  Данное пособие является третьим изданием (первые два вышли в 1975 и 1981 гг.) аналогичного пособия. По сравнению с предыдущими здесь переработаны все темы. В частности, глава «Линейное программирование» полностью ориентирована на симплекс-метод для задач с двухсторонними прямыми ограничениями. В главе, посвященной выпуклому программированию, помимо задач оптимизация приводятся основы выпуклого анализа, в том числе негладкого. Расширена тематика задач оптимального управления, в которой рассматриваются задачи в различных классах управляющих воздействий, в том числе синтез оптимальных систем. Все утверждения снабжены подробными доказательствами, а каждая тема - набором модельных примеров, иллюстрирующих доказанные результаты.
Рассчитано на студентов математического и экономического профиля. Рекомендуется также преподавателям, аспирантам, специалистам, работающим в области приложений математики.

СПЕЦИАЛЬНЫЕ ЗАДАЧИ.
Общие задачи ЛП. исследованные в предыдущих параграфах, не обладают специальными структурами матриц условий, и элементами этих матриц могут быть любые числа. В приложениях часто встречаются специальные задачи ЛП, у которых матрицы условий обладают хотя бы одним из следующих свойств: 1) сильно разрежены (имеют небольшое количество ненулевых элементов); 2) имеют специальную структуру (блочную, ленточную и т. п.); 3) их элементы сгенерированы по специальным правилам. Каждую из таких задач можно свести к общей задаче ЛП, решать общими прямым и двойственным симплекс-методами. Однако значительно более эффективным оказывается другой подход, в котором общие методы адаптируются к специальным задачам, в результате чего получаем очень эффективные специальные методы, учитывающие специфику задач.
Выделение специальных задач и разработка для них специальных методов - одно из основных направлений развития современной теории экстремальных задач.
В данном пособии рассмотрим только один класс специальных задач, называемых транспортными, и, адаптируя для них симплекс-метод, построим эффективный метод потенциалов их решения.
ОГЛАВЛЕНИЕ
ПРЕДИСЛОВИЕ
ВВЕДЕНИЕ
Литература
ГЛАВА 1. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
§1. Симплекс-метод
1.1. Производственная задача
1.2. Графический метод решения задач ЛП
1.3. Каноническая задача ЛП
1.4. Базисный план
1.5. Потенциалы и оценки
1.6. Критерий оптимальности
1.7. Итерация симплекс-метода
1.8. Алгоритм
1.9. Первая фаза
1.10. Конечность симплекс-метода
1.11. Три свойства канонической задачи
1.12. Задача произвольной формы
§2. Двойственный симплекс-метод
2.1. Двойственная каноническая задача
2.2. Базисные двойственный план и псевдоплан
2.3. Теория двойственности
2.4. Критерий оптимальности базисного двойственного плана
2.5. Итерация
2.6. Алгоритмы двойственного симплекс-метода
2.7. Вырожденный базисный двойственный план
2.8. Первая фаза
2.9. Задача ЛП в произвольной форме
2.10. Конечность двойственного симплекс-метода
§3. Анализ решения
3.1. Единственность оптимального прямого плана
3.2. Единственность оптимального двойственного плана
3.3. Анализ чувствительности решения задачи
3.4. Коррекция оптимальных планов при возмущении задач ЛП
3.5. Изменение размеров задачи
3.6. Нестационарные задачи
§4. Специальные задачи
4.1. Сетевая транспортная задача
4.2. Матричные транспортные задачи
§5. Некоторые приложения ЛП
5.1. Задачи на минимакс
5.2. Кусочно-линейная экстремальная задача
5.3. Приложение к исследованию линейных соотношений
5.4. Линейное программирование и матричные игры. Теорема о минимаксе
5.5. Задача о максимальном потоке
Литература
ГЛАВА 2. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ
§6. Выпуклые множества и функции
6.1. Выпуклые множества
6.2. Отделимость выпуклых множеств
6.3. Выпуклые функции
6.4. Дифференцируемость выпуклых функций
6.5. Экстремумы выпуклых функций
§7. Основная задача выпуклого программировании. Теорема Куна - Таккера
7.1 Постановка задачи
7.2. Теорема Куна - Таккера
7.3. Задача ВП с линейными ограничениями
§8. Теория двойственности в выпуклом программировании
8.1. Двойственная задача
8.2. Соотношения двойственности
8.3. Задача квадратичного программирования
8.4. Задача геометрического программирования
§9. Общая задача квадратичного программирования
9.1. Каноническая задача КП
9.2. Графо-аналитический метод
9.3. Алгоритм решения простой задачи квадратичного программирования
9.4. Алгоритм решения общей задачи квадратичного программирования
§10. Специальные методы численного решения задач выпуклого программирования
10.1. Непрямые методы
10.2. Прямые методы
Литература
ГЛАВА 3. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
§11. Конечномерные экстремальные задачи
§12. Задача безусловной оптимизации
12.1. Необходимое условие минимума первого порядка
12.2. Условия оптимальности второго порядка
§13. Задачи с простыми ограничениями
§14. Задача со смешанными ограничениями
14.1. Обобщенное правило множителей Лагранжа
14.2. Классическое правило множителей Лагранжа
14.3. Условно стационарные и нормальные планы
14.4. Условия минимума второго порядка
14.5. Линейные ограничения
14.6. Общая схема исследования задачи НЛП
§15. Негладкие задачи
15.1. Минимизация функций, дифференцируемых по направлениям
15.2. Производная и субдифференциал Кларка
§16. Векторная оптимизация
16.1. Принципы выбора
16.2. Скаляризация критерия
16.3. Введение иерархии целевых функций
Литература
ГЛАВА 4. ЧИСЛЕННЫЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
§17. Минимизация функций одной переменной
17.1. Поиск точек безусловного минимума. Метод Пауэлла
17.2. Методы поиска точек минимума унимодальных функций
17.3. Метод ломаных
§18. Безусловная минимизация функций
18.1. Методы градиентного типа
18.2. Метод Ньютона
§19. Условная минимизация функций
19.1. Метод проекции градиента
19.2. Метод условного градиента
19.3. Метод модифицированных функций Лагранжа
19.4. Метод штрафных функций
Литература
ГЛАВА 5. ДИСКРЕТНОЕ ПРОГРАММИРОВАНИЕ §20. Методы ветвей и границ
20.1. Постановка задачи дискретного программирования
20.2. Общая схема методов ветвей и границ
§21. Задача о рюкзаке
§22. Целочисленное линейное программирование
22.1. Метод ветвей и границ
22.2. Метод отсечения Гомори
§23. Метод вариаций. Задача минимизации штрафов
Литература
ГЛАВА 6. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ
§24. Оптимизация многошаговых процессов
24.1. Постановка задачи
24.2. Инвариантное погружение. Функция Веллмана
24.3. Принцип оптимальности. Уравнение Веллмана
24.4. Анализ результатов
24.5. Стандартная процедура
24.6. Задача о замене оборудования
§25. Задача распределения ресурсов
§26. Построение кратчайшего пути на сети
§27. Задача сетевого планирования
Литература
ГЛАВА 7. ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ
§28. Основная задача вариационного исчисления
28.1. Задача о брахистохроне
28.2. Основная задача
28.3. Другие задачи вариационного исчисления
§29. Метод вариаций
29.1. Вариация допустимой кривой
29.2. Вариации функционала
29.3. Необходимые условия слабого минимума в терминах вариаций функционала
29.4. Уравнение Эйлера
29.5. Теорема Гильберта
29.6. Кусочно-гладкие допустимые кривые
§30. Исследование второй вариации
30.1. Присоединенная задача о минимуме
30.2. Условие Лежандра - Клебша
30.3. Условие Якоби
Литература
ГЛАВА 8. ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
§31. Задача предельного быстродействия
31.1. Оптимальное по быстродействию управление механическим объектом
31.2. Сравнение задачи быстродействия с задачей о брахистохроне
31.3. Математическая модель задачи предельного быстродействия
§32. Принцип максимума
32.1. Постановка задачи
32.2. Существование оптимальных программ
32.3. Формула приращения критерия качества
32.4. Необходимое условие оптимальности программ (принцип максимума Понтрягина)
32.5. Достаточное условие оптимальности
32.6. Задачи оптимального управления с терминальными ограничениями
32.7. Принцип максимума для задач быстродействия
32.8. Краевая задача принципа максимума Понтрягина
32.9. Примеры
§33. Специальные задачи оптимального управления
33.1. Оптимизация непрерывных динамических систем в классе дискретных управляющих воздействий
33.2. Оптимизация дискретных систем
33.3. Оптимизация квазинепрерывных систем
33.4. Оптимизация непрерывных динамических систем в классе дискретно-импульсных управляющих воздействий
§34. Динамическое программирование в теории оптимального управления
34.1. Задача оптимального управления в классе кусочно-непрерывных управляющих воздействий
34.2. Связь динамического программирования с принципом максимума
34.3. Применение динамического программирования к специальным задачам оптимального управления
§35. Проблема синтеза оптимальных систем управления
35.1. Синтез оптимальных систем управления с помощью принципа максимума
35.2. Применение динамического программирования к синтезу оптимальных систем управления
35.3. Оптимальные системы управления
35.4. Оптимальное управление в реальном времени
Литература
Предметный указатель.