Читать онлайн «Методы оптимизации»

Р. ГАБАСОВ Ф. М. КИРИЛЛОВА методы оптимизации Издание второе, переработанное и дополненное Допущено Министерством высшего и среднего специального образования БССР в качестве учебного пособия для студентов университетов по специальности 0647 «Прикладная математика» Минск Издательство БГУ им. В. И. Ленина 1981 ББК 22. 11 Г12 УДК 681. 513. 5:519. 3(075. 8) Рецензенты: кафедра вычислительной математики МГУ им. М. В. Ломоносова, Л. А. Растригин, доктор технических наук Scan AAW 20405—061 Г М317-81 30~~81 1704050000 © Издательство БГУ им. В. И. Ленина, 1981 ОГЛАВЛЕНИЕ Предисловие 5 Глава I. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ... . 9 § 1. Симплекс-метод 9 § 2. Теория двойственности 33 § 3. Двойственный симплекс-метод 46 § 4. Транспортные задачи 59 Литература 78 Глава II. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ ... . 78 § 1. Выпуклые множества и функции ... . 79 § 2. Теорема Куна — Таккера 85 § 3. Теория двойственности 93 § 4. Алгоритм решения квадратичной задачи . . 102 Литература 117 Глава III. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ . . . 117 § 1. Общая задача нелинейного программирования . 117 § 2. Задача на безусловный минимум . . . . 121 § 3. Задача на условный минимум 127 § 4. Минимизация функций при ограничениях типа неравенств 143 § 5. Негладкие задачи 150 § 6. Векторная оптимизация 167 Литература 175 Глава IV. ВЫЧИСЛИТЕЛЬНЫЕ МЕТОДЫ НЕЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 175 § 1. Методы перебора 176 § 2. Минимизация функций одной переменной . . 194 § 3. Методы безусловной минимизации ... . 203 § 4. Методы условной минимизации . . . . 217 Литература 227 Глава V. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ . . 227 § 1. Задача распределения ресурсов 228 § 2. Оптимальная по времени обработка деталей на двух станках 232 § 3. Построение кратчайшего пути на сети . . . 236 3 § 4. Задача о максимальном потоке 239 § 5. Одна задача сетевого планирования . . . 240 Литература 243 Глава VI. ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ 243 § 1. Основная задача вариационного исчисления . 244 § 2. Метод вариаций 250 § 3. Исследование второй вариации 264 Литература 271 Глава VII. ТЕОРИЯ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ . . 272 § 1. Основная задача оптимального управления . 272 § 2. Принцип максимума Понтрягнна ... . 278 § 3. Условия трансверсальности 287 § 4. Применения принципа максимума ... . 300 § 5. Оптимизация линейных систем 311 § 6. Оптимальное управление дискретными процессами 325 § 7. Оптимизация систем с распределенными параметрами 337 § 8. Линейные дифференциальные игры . . . . 341 Литература 349 ПРЕДИСЛОВИЕ Задачи оптимизации встречаются в различных сферах человеческой деятельности. Каждое разумное действие является в определенном смысле и оптимальным, ибо оно, как правило, выбирается после сравнения с другими вариантами. Интерес к задачам наилучшего выбора был высоким всегда, но особенно возрос в последние годы в связи с интенсивным развитием науки и техники. С одной стороны, людям все чаще и чаще приходится заниматься процессами, для осуществления которых требуется максимально эффективное использование имеющихся средств и ресурсов; с другой стороны, с развитием вычислительной техники резко увеличились возможности воздействия человека на изучаемые процессы.