Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Методы оптимизации

Покупка
Основная коллекция
Артикул: 175150.09.01
К покупке доступен более свежий выпуск Перейти
Освещается одно из важнейших направлений математики — теория оптимизации. Рассмотрены теоретические, вычислительные и прикладные аспекты методов конечномерной оптимизации. Описаны алгоритмы численного решения задач безусловной минимизации функций одного и нескольких переменных, изложены методы условной оптимизации. Приведены примеры решения конкретных задач, дана наглядная интерпретация полученных результатов. Предназначено для студентов, аспирантов и преподавателей технических, экономических и других вузов.
Тематика:
ББК:
УДК:
ОКСО:
ГРНТИ:
Аттетков, А. В. Методы оптимизации : учебное пособие / А.В. Аттетков, В.С. Зарубин, А.Н. Канатников. — Москва : РИОР : ИНФРА-М, 2021. — 270 с. — (Высшее образование: Бакалавриат). — DOI: https://doi.org/10.12737/11456. - ISBN 978-5-369-01037-2. - Текст : электронный. - URL: https://znanium.com/catalog/product/1497867 (дата обращения: 29.03.2024). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.

ВЫСШЕЕ ОБРАЗОВАНИЕ - БАКАЛАВРИАТ серия основана в 1 996 г.



> 00 >
X о 00

. АТТЕТКОВ
. ЗАРУБИН
. КАНАТНИКОВ





МЕТОДЫ ОПТИМИЗАЦИИ

УЧЕБНОЕ ПОСОБИЕ





                      Рекомендовано Министерством образования РФ в качестве учебного пособия для студентов высших учебных заведений

znanium.com

Москва РИОР ИНФРА-М
УДК 519.863(075.8)
ББК 22.18я73
      А92




   ФЗ    Издание не подлежит маркировке   
№ 436-ФЗ в соответствии с п. 1 ч. 4 ст. 11

Рецензенты:
      А.В. Манжиров — д-р физ.-мат. наук, профессор;
      В.Ф. Формалев — заслуженный деятель науки РФ, д-р физ.-мат. наук, профессор





       Аттетков А.В.
А92       Методы оптимизации : учебное пособие / А.В. Аттетков, В.С. Зарубин,
       А.Н. Канатников. — Москва : РИОР : ИНФРА-М, 2021. — 270 с. — (Высшее образование: Бакалавриат). — DOI: https://doi.org/10.12737/11456

          ISBN 978-5-369-01037-2 (РИОР)
          ISBN 978-5-16-004876-5 (ИНФРА-М, print)
          ISBN 978-5-16-103309-8 (ИНФРА-М, online)
          Освещается одно из важнейших направлений математики — теория оптимизации. Рассмотрены теоретические, вычислительные и прикладные аспекты методов конечномерной оптимизации. Описаны алгоритмы численного решения задач безусловной минимизации функций одного и нескольких переменных, изложены методы условной оптимизации. Приведены примеры решения конкретных задач, дана наглядная интерпретация полученных результатов.
          Предназначено для студентов, аспирантов и преподавателей технических, экономических и других вузов и факультетов.


УДК 519.863(075.8)
                                                ББК 22.18я73












ISBN 978-5-369-01037-2 (РИОР)
ISBN 978-5-16-004876-5 (ИНФРА-М, print) © Аттетков А.В., Зарубин В.С.,
ISBN 978-5-16-103309-8 (ИНФРА-М, online) Канатников А.Н.
        ОГЛАВЛЕНИЕ





Предисловие.............................................. 5
Список принятых обозначений.............................. 7
Введение................................................. 9
Глава 1
Задачи оптимизации...................................... 11
      1.1. Основные понятия............................. 11
      1.2. Примеры задач оптимизации.................... 12
      1.3. Классы задач оптимизации..................... 19
          Вопросы для самопроверки...................... 23
Глава 2
Методы одномерной минимизации .......................... 25
      2.1. Предварительные замечания ................... 25
      2.2. Методы прямого поиска........................ 27
      2.3. Сравнение методов прямого поиска ............ 34
      2.4. Методы полиномиальной аппроксимации.......... 37
          Вопросы для самопроверки...................... 43
Глава 3
Многомерная безусловная минимизация..................... 44
      3.1. Методы спуска................................ 47
      3.2. Метод градиентного спуска.................... 50
      3.3. Минимизация квадратичной функции............. 59
      3.4. Метод сопряженных направлений ............... 68
      3.5. Метод Ньютона и его модификации ............. 80
      3.6. Квазиньютоновские методы..................... 89
      3.7. Методы прямого поиска........................ 98
      3.8. Методы случайного поиска.................... 119
          Вопросы для самопроверки..................... 126
Оглавление

Глава 4
Аналитические методы нелинейного программирования . . .    128
      4.1. Минимизация целевой функции на заданном множестве......................................... 128
      4.2. Минимизация при ограничениях типа равенства ... 133
      4.3. Общая задача нелинейного программирования ....  136
      4.4. Седловая точка функции Лагранжа.................. 143
      4.5. Двойственная функция............................. 145
          Вопросы для самопроверки.......................... 149
Глава 5 Численные методы нелинейного программирования............... 151
      5.1. Метод условного градиента........................ 151
      5.2. Использование приведенного градиента............. 158
      5.3. Проектирование точки на множество................ 168
      5.4. Метод проекции точки на множество................ 172
      5.5. Метод проекции антиградиента..................... 178
      5.6. Метод возможных направлений...................... 199
      5.7. Методы последовательной безусловной минимизации....................................... 212
          Вопросы для самопроверки.......................... 221
Глава 6 Методы линейного программирования........................... 222
      6.1. Виды задач линейного программирования............ 223
      6.2. Графический метод решения задач линейного программирования.................................. 227
      6.3. Основы теории линейного программирования....      230
      6.4. Симплекс-метод................................... 233
      6.5. Построение начального допустимого базисного решения........................................... 244
      6.6. Двойственная задача линейного программирования. . 250
          Вопросы для самопроверки.......................... 258
Список рекомендуемой литературы............................. 260
Предметный указатель........................................ 266
        ПРЕДИСЛОВИЕ





    Предлагаемое пособие посвящено конечномерным задачам оптимизации. В излагаемом материале основное внимание уделено прикладным и вычислительным аспектам, в первую очередь анализу численных методов оптимизации и построению алгоритмов их реализации. В книге опущены доказательства многих теоретических положений, в частности теорем о сходимости методов. По этим вопросам есть обширная литература, и «математические тонкости», связанные с оценками сходимости методов, можно изучить самостоятельно. В практической деятельности более важно понимание сути методов и алгоритмов их реализации, знание условий их применения. Большое количество примеров и разобранных задач, поясняемых графическими иллюстрациями и интерпретацией полученных результатов, позволяет использовать данное издание не только как учебное пособие, но и как методическое, предназначенное для проведения семинарских занятий и организации лабораторных работ.
    В основу книги лег методический опыт авторов, которые в течение ряда лет в стенах МГТУ имени Н.Э. Баумана читают лекции по методам оптимизации, ведут семинарские и лабораторные занятия. Этот опыт нашел свое отражение в учебнике авторов, изданном ранее . В предлагаемом издании методические наработки авторов получили дальнейшее развитие. Некоторые разделы переработаны. Так, пересмотрена глава по одномерной оптимизации, три главы по методам многомерной оптимизации сокращены и собраны в одну. Глава по оптимизации выпуклых функций не включена в пособие, поскольку этот материал имеет в основном теоретическое значение. Авторы ограничились изложением минимальных сведений по выпуклым функциям в первой главе. В то же время в книгу включен новый материал: методы случайного поиска в третьей главе, новая глава по методам линейного программирования.

  * Аттетков А.В. Методы оптимизации: учебник для вузов / А.В. Аттетков, С.В. Галкин, В.С. Зарубин; под ред. В.С. Зарубина, А.П. Крищенко. -М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. -440 с.
Предисловие

    Содержание пособия относится к специальным разделам высшей математики, для работы с ним требуется хорошее знание базового курса. В частности, предполагается, что читатель умеет оперировать основными понятиями линейной алгебры, аналитической геометрии, теории матриц и математического анализа.
    Мы признательны нашим рецензентам доктору физико-математических наук, профессору А.В. Манжирову и доктору физико-математических наук, профессору В.Ф. Формалеву за ряд замечаний, учтенных нами при подготовке пособия.
        СПИСОК ПРИНЯТЫХ ОБОЗНАЧЕНИЙ




◄ и ►   — начало и окончание доказательства

#       — окончание примера, замечания

{«I, а₂,..., ап} — конечное множество, состоящее из элементов а^, аг,..., «п
{х: P(х)} — множество, состоящее из тех и только тех элементов х, которые обладают характеристическим свойством P(х)
k = 1, N — число к принимает последовательно все значения из множества натуральных чисел от 1 до N включительно
N — множество натуральных чисел
Z       — множество целых чисел
R       — множество действительных чисел
R ।     — множество всех положительных действительных чисел
R*      — множество всех неотрицательных действительных чисел
Rⁿ      — n-я декартова степень множества R действительных чи-
           сел (также n-мерное евклидово арифметическое пространство)
R+      — положительный ортант, т.е. n-я декартова степень множе-
           ства R । положительных действительных чисел
Rn      — неотрицательный ортант, т.е. n-я декартова степень мно-
           жества R* неотрицательных действительных чисел
AB и | AB\ — отрезок, соединяющий точки A и B, и его длина x = (xi ... хп)т — n-мерный арифметический вектор, т.е. элемент n-мерного евклидова арифметического пространства Rⁿ
|x|     — длина (модуль, евклидова норма) вектора x
п
52 ak — сумма n слагаемых а₁, а₂,..., ап k=1
п
П am — произведение n сомножителей аь а2,..., ап m=1
D(f) и R(f) — область определения и область значений функции f⁽х⁾
Список принятых обозначений

sgn х   — функция знака числа действительного числа х, те. sgn х =
           = 1 при х > 0, sgn х = 0 при х = 0 и sgn х = —1 при х < О exp(x) — экспоненциальная функция ex diam X — диаметр ограниченного множества X дХ — граница множества X
sup f (х) и inf f (х) — точная верхняя грань и точная нижняя грань xex       x'\x        ,
           функции f (х) на множестве X
max f (х) и min f (х) — максимальное и минимальное значения xex       xex
           функции f (х) на множестве X
f (х + 0) = lim f (х) и f (х — 0) = lim f (х) — правосторонний x^a+0                           x^a+0
           и левосторонний пределы функции f (х) одного действительного переменного в точке a
grad f (х) — градиент скалярной функции f (х) многих переменных (a, b)  — скалярное произведение векторов а и b
Ат      — матрица, транспонированная к матрице A
Rg А — ранг матрицы А
det А — определитель матрицы А
с( А)   — число обусловленности матрицы А
|| А || — евклидова норма матрицы А
I — единичная матрица
f (x) ^ min, x G Q, — задача минимизации функции f (x) на множестве Q
f (x) ^ inf, x G Q, — задача нахождения точной нижней грани функции f (x) на множестве Q
а ^ b, b ^ а — каждая координата вектора a G Rn не меньше соответствующей координаты вектора b G Rn
wk      — антиградиент целевой функции в текущей точке xk⁻¹
           итерационной последовательности {xk}
uk и ek — направление спуска и шаг спуска на k-й итерации метода спуска
H(x)    — матрица Гессе скалярной функции многих переменных
        ВВЕДЕНИЕ





   Бурное развитие информационных технологий сместило многие акценты в развитии науки. В математике повысилась роль численных методов решения прикладных задач. Эти методы в сочетании с мощью современной вычислительной техники позволяют решать такие задачи, которые еще 50 лет назад не поддавались исследователям. Широкий класс задач, связанных с применением численных методов, — класс оптимизационных задач.
   На практике часто возникает ситуация, когда из нескольких возможных вариантов поведения необходимо выбрать один вариант, в том или ином смысле наилучший. Такой выбор (принятие наилучшего решения) может быть осуществлен по-разному. Один из подходов заключается в количественной оценке каждого возможного варианта поведения (решения) и выборе среди них того, у которого оценка наилучшая (максимальная или минимальная). Так мы приходим к задаче оптимизации, которую можно сформулировать следующим образом. Есть некоторое множество возможных решений, называемых альтернативами. Каждой альтернативе можно дать некоторую количественную оценку на основе некоторого критерия оптимальности. Решение задачи оптимизации состоит в определении той альтернативы, для которой критерий оптимальности дает наибольшую (или наименьшую) количественную оценку.
   Задачи оптимизации как задачи выбора наилучшей альтернативы на основе критерия оптимальности возникают в самых различных ситуациях. В этом ряду особенно важна задача проектирования технических устройств и технологических процессов, в которой какие-либо параметры устройства или процесса могут в определенной степени варьироваться, причем за счет изменения этих параметров можно повысить эксплуатационные характеристики устройства или экономичность проведения технологического процесса. Упомянем задачу распределения материальных и финансовых ресурсов, встречающуюся во многих областях экономики и управления. В ряде случаев закон развития процесса или явления можно формулировать как достижение минимума некоторого показателя (например, принцип минимума по
Введение

тенциальной энергии в теоретической механике или принцип Ферма в оптике, согласно которому луч света следует по пути с наименьшим временем движения).
   Разнообразны задачи оптимизации и по своему внутреннему содержанию. Множество альтернатив может описываться одним числовым параметром (одномерная оптимизация) или несколькими параметрами (многомерная оптимизация). Есть класс задач оптимизации, в которых каждая альтернатива характеризуется бесконечным числом параметров (например, задача распределения заряда в твердом теле или задача распределения температуры в некоторой области пространства), хотя в этом случае корректнее говорить не о бесконечном числе параметров, а о функции. Выделяя этот класс задач, говорят о бесконечномерной оптимизации, противопоставляя ей конечномерную оптимизацию.
   В задаче оптимизации может быть несколько критериев оптимальности. Так, в экономике развитие связано с получением наибольшей прибыли, но при принятии решений могут учитываться и другие факторы, например, отражающие экологическую чистоту производства, экономические риски, возникающие из-за противодействия конкурентов, и т.п. В этом случае возникает задача многокритериальной оптимизации.
   В этом учебном курсе мы остановимся на задачах конечномерной оптимизации с одним критерием оптимальности.
                Глава 1





            ЗАДАЧИ ОПТИМИЗАЦИИ




    1.1. Основные понятия

    Если каждая альтернатива в задаче оптимизации характеризуется совокупностью из n числовых параметров, то естественно альтернативы ассоциировать с элементами n-мерного арифметического пространства Rn. В этом случае множество всех альтернатив будет представлять собой некоторое подмножество Q С Rn, а критерий оптимальности, который каждой альтернативе ставит в соответствие некоторую числовую оценку, — функцию многих переменных f (xj,x2,..., xn), определенную на множестве Q.
    Таким образом, с математической точки зрения задача конечномерной оптимизации заключается в определении наибольшего или наименьшего значения функции многих переменных f (xj,Х2,...,xn) на заданном множестве Q и точки x* G Q, в которой это значение достигается. Так сформулированную задачу называют задачей математического программирования, а функцию f (x) = f (xj ,x2,...,xn) — целевой функцией. Переменные xj, x2, ..., xn — это параметры оптимизации, каждая точка x = (xj, x2, ..., xn) G Q — допустимое решение, а множество Q С Rn — множество допустимых решений, или допустимое множество. Точку x* G Q, в которой целевая функция принимает наименьшее значение, называют оптимальным решением. Задачу математического программирования будем записывать следующим образом:
f (x) ^ min, x G Q.
    С математической точки зрения нет различий между поиском наибольшего значения функции и поиском наименьшего значения функции. Чтобы преобразовать одну задачу в другую, достаточно сменить знак целевой функции. Учитывая это, в дальнейшем ограничимся рассмотрением только одной из этих двух задач, а именно задачей минимизации функции, состоящей в поиске наименьшего значения целевой функции на допустимом множестве и точки, в которой это значение достигается.
Глава 1. Задачи оптимизации

   Из курса математического анализа известно, что функция на заданном множестве может не достигать наименьшего значения. Причина в том, что она либо не ограничена снизу, либо ограничена снизу, но тем не менее не достигает точной нижней грани множества своих значений. И в том, и в другом случае задача минимизации не имеет решения, что говорит о некорректной ее постановке и о необходимости вносить изменения в математическую модель изучаемого объекта или явления. В некоторых случаях может решаться задача поиска точной нижней грани mf функции f (x) на допустимом множестве Q и построения такой последовательности точек {xk} С Q, для которой f (xk) ^ mf при к ^ ж. Подобную задачу записывают в виде
f (x) ^ inf, x G Q.
   Задачу поиска точной нижней грани можно рассматривать как обобщение задачи минимизации. Методы решения такой задачи в целом те же, что и методы решения задачи минимизации. Поэтому мы на ней останавливаться не будем, считая, что исследуемая целевая функция на допустимом множестве достигает наименьшего значения.

    1.2. Примеры задач оптимизации

   Рассмотрим некоторые задачи оптимизации, возникающие в геометрии, алгебре и других разделах математики. Многие из подобных задач можно решить геометрическим или алгебраическим путем, а также с помощью методов исследования функции на экстремум, изучаемых в курсе математического анализа. Рассматриваемые задачи тесно связаны с историей развития методов оптимизации и позволяют наглядно продемонстрировать многообразие объектов оптимизации — тех устройств, процессов или явлений, при исследовании которых возникают задачи оптимизации. Кроме того, они наглядно показывают, как возникает проблема поиска оптимального решения и как такая проблема превращается в конкретную математическую задачу. Наконец, подходы к решению простейших задач оптимизации являются источниками важнейших идей, лежащих в основе современных методов решения задач оптимизации.
   Пример 1.1. Рассмотрим задачу определения сторон прямоугольника, вписанного в окружность радиуса R и имеющего наибольшую площадь S (рис. 1.1).
К покупке доступен более свежий выпуск Перейти