Ф.П. Васильев - Численные методы решения экстремальных задач

Ф. П. ВАСВЛЪКВ ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ ЭКСТРЕМАЛЬНЫХ ЗАДАЧ Издание второе, переработанное и дополненное Допущено Госудорственнъмс «омитстом СССР по народнолсу абраоованию в качестве учебного пособия для студентов еуоов, обучающихся па спвуиальности пПрикладная математика» 0 МОСКВА «НАУКА» ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТРМАТИЧЕСКОИ ЛИТЕРАТУР тз88 ББК 2219 В19 агДК 519.6 (075. 8) Васильев Ф. П. Численные методы решеиив экстремальных задач: Учеб. пособие для вузов.— 2-е изд., перераб.

и доп.— Мл Наука. Гл. ред. фпз.-мат. лнт., 1988.— 552 с.— 1ЯВг1 5-02-013795-0. Содержит основные численные методы решения экстремальных задач. Приводятся теоретическое обоснование и краткие характеристики атих методов. Рассматриваются задачи минимизации фуннций конечного числа переменных и задачи оптимального управления процессами, описываемыми системами обыкновенных дифференциальных уравнений. Сохранена структура первого издания, но содержание некоторых глав существенно переработано и дополнено.

1-е издание — в 1980 г. Для студентов вузов по специальности «Принладная математива», а также для специалистов, связанных с решением задач овтнмизации. Табл. 11. Ил. 42. Библпогр. 343 назв. Рецеваент член-корреспондент АН СССР Л. Д. Кудря«чае 1702070000 — 191 053(02)-88 тельство «Натка«. иая редакция ка-математичеакон ратуры, 1ззо; меиеиияыи, 1ЭЗЗ 1ЯВ57 5-02-013796-0 ОГЛАВЛЕНИЕ Предисловие ко в*орому изданию Предисловие Гл аз а 1. Методы минимизации функций одной переменной $ 1.

Постановка задачи 2. Классический метод $ 3. Метод деления отрезка пополам 1 4. Метод золотого сечения. Симметричные методы $ 5. Об оптпмальных методах 6. Метод ломаных 4 7. Методы покрытий $8. Выпуклые функции одной переменной 9. Метод касательных 4 10. Метод поиска глобального минимума $ М. Метод парабол 1 12. Другой метод поиска глобального минимума $13.

О методе стохастической аппроксимации Глав а 2. Предварительные сведения о вадачах иа экстремум $1. Постановка задачи минимизации. Теорема Вейерштрасса 1 2. Классический метод . 1 3. Вспомогательные предложения Г л а в а 3. Элементы линейного программирования $ 1. Постановка задачи $ 2. Геометрическая интерпретация. Угловые точки 1 3.

Симплекс-метод $4. Антициклин $5. Выбор начальной угловой точки 1 6. Об условии разрешимости канонической задачи Глава 4. Элементы выпуклого анализа $1. Выпуклые множества 1 2. Выпуклые функции 1 3. Сильно выцуклые функции 1 4. Проекция точки на множество 5. Отделимость выпуклых множеств 1 6. Субграднент. Субдифферевцнал $7. Равномерно выпуклые функции 8. Правило множителей Лагранжа 1 9. Теорема Куна — Танкера. Двойственная задача Гл а в а 5. Методы минимизации функций многих переменных 1 1. Градиентный метод 2. Метод проекции градиента 3. Метод проекции субградпепга 5 6 9 9 15 17 19 22 28 33 38 46 53 59 62 66 68 68 78 91 101 101 106 113 126 136 148 148 162 181 188 193 206 218 223 234 260 260 277 285 ОГЛАВЛЕНИЕ Г л з в а 6. Принцип максимума Понтрягина.......

421 $1. Постановка задачи оптимального управления.... 421 2. Формулировка принципа максимума. Примеры.... 435 3. Доказательство принципа максимума...., . 461 4 4. О методах решения краевой задачи принципа максимума 480 5. Связь между принципом максимума н классическим варпационным исчислением........... 485 490 490 505 513 522 531 531 532 Список лнтературы Основная литература . Дополнительная лнтература Предметяый указатель 546 4. Метод условного градиента 5. Метод возможных направлений 6. Метод лннеаризацпп 7. Квадратичное программирование 8.

Метод сопряженных направлений 9. Метод Ньютона 4 10. Метод Стеффенсена 4 11. Метод нокоординатного спуска 4 12. Метод поиска глобального минимума 4 13. Метод модифицированных функций Лаграпнса 4 14, Метод штрафных функций 15. Метод барьерных функций Зз 16. Метод нагруженных функций 1 17. О методе случайного поиска $18. Общие аамечання Г л а в а 7. Динамическое программирование 1. Схема Беллмана.

Проблема синтеза для дискретных систем 4 2. Схема Моисеева 4 3. Проблема синтеза для систем с непрерывнып временем 4 4. Достаточные условкя оптимальности 291 299 309 314 Зо 329 338 Зйг 347 356 363 З84 396 410 415 ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ Во втором издании книга существенно переработана.

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

Исправлены замеченные ошибки, неточности. Автор глубоко признателен С. М. Алпакбарову, А. С. Антппину, А. В. Арутюнову, С. С. Ахиезу, Е. Г. Белоусову, А. И. Бонпкову, В. А. Березневу, Н. С. Васильеву, О. В. Васильеву, Г. С. Ганшпну, Ю. Ы. Данилину, Д. В. Денисову, Я. И.

Заботпву, С. К. Завриеву, В. С. Ижуткину, А. С. Ильинскому, А. Д. Искендерову, А. 3. Ишмухаметову, А. Г. Коваленко, А. И. Кораолеву, Е. В. Лямину, М. Д. Марданову, Ю. Е. Нестерову, В. Н. Нефедову, В. И. Плотникову, М. М. Потапову, Т. Л. Рудневой, А. Г. Сухареву, А. Г.

Тетереву, А. В. Тимохогу, А. А. Третьякову, В. Р. Фазылову, Р. Ф. Хабибуллину, Ю. Н. Меренных, Н. Т. Чиричу, которые своимп советами, предложенпями, замечаниями способствовали улучшению второго издания книги. ПРЕДИСЛОВИЕ Первые задачи геометрического содержания, связанные с отысканием наименьших и наибольших величин, появились еще в древние времена. Развитие промышленности в ХЧП— ХЧП1 веках привело к необходимости исследования более сложных задач на экстремум и к появлению вариационного исчисления.

Однако лишь в ХХ веке при огромном размахе производства и осознании ограниченности ресурсов Земли во весь рост встала задача оптимального использования энергии, материалов, рабочего времени, большую актуальность приобрели вопросы наилучшего в том или ином смысле управления различными процессами физики, техники, экономики и др. Сюда относятся, например, задача организации производства с целью получения максимальной прибыли при заданных затратах ресурсов, задача управления системой гидростанций и водохранилищ с целью получения максимального количества электроэнергии, задача о космическом перелете из одной точки пространства в другую наибыстрейшим образом или с наименьшей затратой анергпи, задача о быстрейшем нагреве или остывании металла до заданного температурного режима, задача о наилучшем гашении вибраций и многие другие задачи.

Потребности развития самой вычислительной математики также привели к необходимости исследования таких задач на максимум и минимум, как, например, задачи наилучшего приблин~ения функций, оптимального выбора параметров итерационного процесса или узлов интерполирования, минимизации не- вязки уравнений и т. д. На математическом языке такие задачи могут быть сформулированы как задачи отыскания экстремума (максимума или минимума) некоторой функции или функционала у(и), выражающего собой качество (цену) управления и из заданного множества У некоторого пространства. Требованле принадлежности управления и некоторому множеству У выражает собой ограняченвя, сбычяо вытекающие нз законов сохранения, ограниченности наличных ресурсов, возможностек технической реализации управления, нежелательности какнх-лнбо запрещенных (аварийных) состояний н т.

п. Задачи отыскания экстремума функция у(и) на множестве у принято называть экстремальными зада- пгедисловик чами. Заметим, что аадача максимизации функционала У(и) на множестве У эквивалентна задаче минимизации функционала — У(и) на том же множестве У, поэтому можно ограничиться рассмотрением задач хшнимпзации. В настоящее время теория экстремальных задач обогатилась фундаментальными результатами, появилпсь ее новые разделы, такие как линейное, выпуклое, стохастпческое программирование, оптимальное управление и др. Потребности практики способствовали бурному развитию методов приближенного решения экстремальных задач.