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


В. М. Поляков, 3. С. Агаларов






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





Учебное пособие



            2-е издание



Рекомендовано Учебно-методическим советом по высшему образованию в качестве учебного пособия для студентов бакалавриата и магистратуры, обучающихся по направлению подготовки «Прикладная математика»






Москва Издательско-торговая корпорация «Дашков и К°» 2022

УДК 519.85
ББК 22.18
     П54


Авторы:
      В. М. Поляков - доктор технических наук, профессор, профессор кафедры математики, ФГБОУ ВО «Российский государственный геологоразве-дочныйуниверситет им. Серго Орджоникидзе»;
      3. С. Агаларов - кандидат экономических наук, доцент кафедры математики, ФГБОУ ВО «Российский государственный геологоразведочный университет им. Серго Орджоникидзе».

Рецензент:
      Н.      В. Еремеев - кандидат технических наук, доцент, доцент кафедры технологии и системы автоматизированного производства металлургических процессов, ФГБОУ ВО «Московский авиационный институт (национальный исследовательский университет)».




        Поляков, Владимир Михайлович.

П54 Методы оптимизации : учебное пособие / В. М. Поляков, 3. С. Агаларов. — 2-е изд. — Москва : Издательско-торговая корпорация «Дашков и К°», 2022. — 86 с.

         ISBN 978-5-394-05003-9.

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







ISBN 978-5-394-05003-9

          © Поляков В. М., Агаларов 3. С., 2021 © ООО «ИТК «Дашков и Ко», 2021

            СОДЕРЖАНИЕ



ВВЕДЕНИЕ..........................................5
1.    НЕКОТОРЫЕ ПРОБЛЕМЫ, ВОЗНИКАЮЩИЕ ПРИ ИСПОЛЬЗОВАНИИ ЧИСЛЕННЫХ МЕТОДОВ ОПТИМИЗАЦИИ.......................................9
2.    МЕТОДЫ ОПТИМИЗАЦИИ, ОСНОВАННЫЕ
НА ПЕРЕБОРЕ ВАРИАНТОВ РЕШЕНИЙ....................11
  2.1. Метод полного перебора вариантов..........11
      2.1.1. Алгоритм и код программы, реализующие метод перебора вариантов на сетке..........14
  2.2. Методы случайного поиска оптимального решения.28
      2.2.1. Метод случайного поиска оптимума....28
      2.2.2. Алгоритм и код программы поиска оптимума методом Монте-Карло...............30
      2.2.3. Метод случайного поиска с обучением.33
      2.2.4. Алгоритм и код программы поиска оптимума методом случайного поиска с обучением......36
3.    МЕТОДЫ РЕШЕНИЯ ЗАДАЧ МАТЕМАТИЧЕСКОГО ПРОГРАММИРОВАНИЯ, ОСНОВАННЫЕ НА ЛИНЕАРИЗАЦИИ ЦЕЛЕВОЙ ФУНКЦИИ
И ОГРАНИЧЕНИЙ....................................41
  3.1. Суть методов поискаэкстремумов, основанных
  на линеаризации задач математического программирования....41
      3.1.1. Аппроксимирующее линейное программирование...............................42
      3.1.2. Алгоритм и код программы поиска оптимума методом Гриффица— Стюарта......................45

3

4.   ЗАДАЧА ОДНОМЕРНОЙ ОПТИМИЗАЦИИ.............48
  4.1. Аналитическое решение задачи одномерной оптимизации..........................................48
  4.2. Численное решение задачи одномерной оптимизации..........................................49
      4.2.1. Алгоритм поиска оптимума методом деления пополам..........................................51
      4.2.2. Алгоритм нахождения оптимума методом золотого сечения.................................53
5.   ЗАДАЧА ПОИСКА ЭКСТРЕМУМОВ ФУНКЦИИ, ЗАДАННОЙ НА Rⁿ.........................................55
  5.1. Аналитическое решение задачи оптимизации функции w(x),заданнойна Rⁿ ..........................55
  5.2. Численное решение задачи оптимизации функции w(x), заданной на Rⁿ.........................57
      5.2.1. Метод градиентного (наискорейшего) спуска.58
      5.2.2. Метод покоординатного спуска..............69
6.   ЧИСЛЕННОЕ РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ ФУНКЦИИ/*, ЗАДАННОЙ НА ОГРАНИЧЕННОМ
МНОЖЕСТВЕ X QRⁿ ...............................75
  6.1. Метод штрафных функций..................75
  6.2. Алгоритмы методов штрафных и барьерных функций......................................81
ЗАКЛЮЧЕНИЕ.....................................84
ЛИТЕРАТУРА.....................................85

4

            ВВЕДЕНИЕ



     Термин «оптимизация» широко используется в различных прикладных дисциплинах. Несмотря на некоторые отличия в толковании этого термина, возникающие в силу специфики решаемых задач, смысл его один: оптимизация — это процесс поиска лучшего решения. В данной работе мы понимаем под термином «оптимизация» процесс нахождения экстремумов функции, заданной на ограниченной или на неограниченной области линейного пространства.
     Люди в своей повседневной деятельности, как правило, решают две задачи. Первая задача — дать прогноз хода какого-либо явления или процесса. Вторая задача — обосновать лучшее в каком-то смысле решение. И первая, и вторая задача традиционно решались человеком интуитивно или путем логического анализа. Современная теория, построенная на стыке многих дисциплин, таких как биология, психология человека, экономика, социология [4], хорошо объясняет особенности такого далеко не всегда безошибочного метода принятия решения. Этот путь проверен опытом, накопленным в течение сотен тысяч лет существования человека разумного. И тем не менее часто приводит к ошибкам. Дело в том, что в силу усложнения хозяйственной деятельности людей, интуиции и логического мышления становилось недостаточно для обоснования все более и более сложных решений. Поэтому появился такой инструмент, как математика, позволяющий расчетным путем оценивать эффективность тех или иных решений и выбирать лучшие из них или давать количественные оценки прогнозов протекания разнообразных явлений и процессов. Следовательно, применение расчетных методов к решению любых задач — и есть суть математического моделирования.
     Когда экономист в таблице приводит расчеты оценки ожидаемой прибыли при тех или иных вариантах инвестиций в производство, он занимается не чем иным, как математическим моделированием инвестиционной деятельности. В данном случае рядом с эконо

5

мистом не лежат кучи денег или ценных бумаг, нет станков и механизмов, которые могут использоваться в производстве. Все - в таблицах на бумажном носителе или, возможно, в табличках Excel на экране компьютера. Суть одна — экономист создал математическую модель инвестиций и работает с ней, чтобы дать прогноз эффективности анализируемых решений и выбрать из них лучшее. Другими словами, этот экономист занимается оптимизацией инвестиций.
     Предположим, что в таблице, которую подготовил экономист, представлены только три варианта инвестиций. Во многих случаях рассматриваемая задача оптимизации предусматривает анализ значительно большего числа вариантов решений. В этих ситуациях математическая модель, описывающая процесс оценки эффективности рассматриваемых вариантов, усложняется. Очень часто в таких случаях применяют модели математического программирования. Решая задачу математического программирования, находят вариант (варианты) оптимального распределения ограниченных ресурсов, позволяющий достичь поставленную цель. Подробно о постановке цели (целей) операций, задачах и теории математического программирования рассказывается, в частности, в работах [1, 2, 3, 6]. В данном пособии рассматриваются численные методы решения задач математического программирования:
min (или max) w(x), хЕХ.                 (0-1)
                 X
     В этой задаче w(x) — показатель эффективности, характеризующий степень достижения цели в зависимости от проводимых мероприятий, характеризуемых вектором х. Множество Х в задачах оптимизации, как правило, задают с помощью системы равенств и неравенств типа
д(х) > 0, h(x) = 0.
     Предполагается, что читатель знаком с постановкой задач математического программирования и имеет представление о теории математического программирования. Теория математического про

6

граммирования начинается с трудов Ж. Л. Лагранжа и ряда его современников. Задачи оптимизации ставились и решались тогда по понятным причинам в аналитическом виде. В 1951 г. А. У. Таккер и Г. У. Кун в теореме, известной теперь как теорема Куна — Таккера, обобщили метод поиска экстремумов функции, заданной на ограниченном пространстве, предложенный Лагранжем, на случай общей задачи нелинейного программирования с ограничениями как в виде равенств (как было у Лагранжа), так и в виде неравенств. Но одно дело — получить условия существования оптимума функции, заданной на ограниченном множестве, другое — найти решение задачи оптимизации. Аналитически в общем случае задачи математического программирования не решались. Исключение составило линейное программирование, теория и практика которого были разработаны отечественным ученым Л. В. Канторовичем и американцем Д. Б. Данцигом. Алгоритм линейного программирования приводил к оптимуму при конечном количестве шагов; кроме того, при решении задач небольшой размерности он не требовал проведения большого количества вычислений.
     Бурное развитие теория оптимизации претерпела в связи с появлением мощных вычислительных средств. Появилась реальная возможность численными методами решать задачи оптимизации. Это послужило очередным стимулом к разработке теории оптимизации. Но теперь основное внимание уделялось обоснованию численных методов поискаэкстремумов. В связи с этим отметим математиков М. Аоки, У. И. Зангвилла, А. Фиакко, Г. Мак-Кормика, Э. Полака, Р. Гриффитса, Р. Стюарта, Б. Н. Пшеничного, Ю. М. Данилина, Л. М. Абрамова, В. Ф. Капустина, В. Г. Карманова и многих других ученых, занимавшихся разработкой численных методов решения задач математического программирования. Теория этих методов разработана практически исчерпывающе. Ее основой является изучение сходимости точек хк множества А к точке оптимума %* при увеличении количества итераций к (шагов вычисления точек хк и зна

7

чений w(xk) в этих точках). А также изучение сходимости значений w(xk) к значению целевой функции в точке оптимума w(x*).
     В настоящее время легко найти множество как коммерческих, так и общедоступных программ, написанных на различных языках программирования, реализующих методы оптимизации. Используя эти программы, их пользователю остается только ввести в числе исходных данных целевую функцию, ограничения и заданную точность вычисления оптимума. Далее результат получается автоматически, но не всегда верный. Это как с вождением автомобиля — чтобы тронуться с места, достаточно знать органы управления автомобилем. Но если вы не знаете его возможностей в различных условиях эксплуатации, не знакомы с его устройством, особенностями взаимодействия различных агрегатов, то далеко не уедете. Поэтому мы посчитали верным решением ознакомить читателей с работой часто используемых в прикладных программах оптимизации алгоритмов и довести их до программной реализации. Вопросы сходимости мы упоминаем только в связи с особенностями исходных задач и применяемых методов оптимизации.
     Приступая к изучению теории оптимизации, мы бы советовали читателям освежить знания по этому вопросу, познакомившись с материалом, представленным, например, в источнике [7]. Кроме этой работы, существуют сотни других пионерских и обзорных работ на эту тему. Масса полезных сведений на этот счет имеется в интернете.
     В данном пособии мы не рассматриваем линейное программирование как самостоятельный метод оптимизации, поскольку эта задача традиционно изучается в курсе «Исследование операций». Курс «Методы оптимизации» читается по направлению подготовки «Прикладная математика» в 8-м семестре. Настоящее пособие подготовлено на основе материалов занятий по данному предмету, а также по дисциплине «Интеллектуальные системы», проводимых авторами пособия. Сделан акцент на практическую сторону реализации методов поиска экстремумов.

8

            1. НЕКОТОРЫЕ ПРОБЛЕМЫ, ВОЗНИКАЮЩИЕ ПРИ ИСПОЛЬЗОВАНИИ ЧИСЛЕННЫХ МЕТОДОВ ОПТИМИЗАЦИИ



     Решением задачи (0.1) являются точках* и значение целевой функции (показателя эффективности) в этой точке — w(x*). Они должны быть найдены с удовлетворяющей исследователя точностью. Известно о ряде проблем, с которыми часто сталкиваются специалисты, занимающиеся поиском оптимальных решений с помощью математического моделирования различных процессов. Математическая модель, описывающая ход оптимизации, должна адекватно описывать изучаемую задачу. А именно: показатель эффективности, являющийся, по сути, математическим эквивалентом степени достижения цели операции, должен быть чувствителен к изменению оптимизируемых переменных. Если это не так, то либо степень достижения цели операции слабо зависит от тех мероприятий, которые проводятся и моделируются, либо математическая модель разработана неверно.
     В первом случае к математическому моделированию приступили слишком рано, не изучив в достаточной степени рассматриваемый процесс. Во втором случае требуется более тщательный подбор математической зависимости между показателем эффективности операции и управляемыми переменными, характеризующими проводимые для достижения цели операции. Показатель эффективности может стремиться при некоторых значениях оптимизируемых показателей к бесконечности. Другими словами, математическая зависимость показателя эффективности от оптимизируемых переменных адекватно реагирует на их изменения, но при некоторых значениях управляемых переменных теряет смысл.
     Например, рассмотрим функцию эффективности (1.1). При а₂хг = —а₃х₂ значение функции

агхг
w(x) =-------------
а2хг + а₃Х2
стремится к бесконечности.


9

(1.1)

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

10

            2. МЕТОДЫ ОПТИМИЗАЦИИ, ОСНОВАННЫЕ НА ПЕРЕБОРЕ ВАРИАНТОВ РЕШЕНИЙ


        2.1. Метод полного перебора вариантов

    Наиболее простым в реализации и в то же время гарантирующим получение решения, позволяющего решать и многоэкстремальные задачи оптимизации, является метод полного перебора вариантов на сетке. Наиболее просто этот метод реализуется, если множество допустимых решений X ограничивается плоскостями, перпендикулярными осям координат, т. е. представляет собой гиперкуб Хд. В случае если множество X имеет более сложную форму, множество допустимых решений X включается в гиперкуб X с Хд той же размерности, что и решаемая задача. Таким образом, множество допустимых решений X становится подмножеством Хд. В свою очередь, гиперкуб Xg разбивается на кубики, сечением параллельных плоскостей, перпендикулярных к ребрам куба Xg = U™₌₁Xgᵢ. Как правило (но не всегда), используют сетки разбиения с одинаковым шагом по всем координатам. Иллюстрация этой процедуры для случая двух переменных дана на рис. 1.
    Далее последовательно вычисляют значения показателя эффективности w(xk) в точках, являющихся центрами кубиков. Иногда в целях экономии числа вычислений центры кубиков не определяют и значения показателя эффективности вычисляют для какой-то всегда одной и той же из вершин каждого кубика. В зависимости от модификации метода оптимизации на сетке: 1) запоминают все значения показателя эффективности и координаты точек, в которых он был рассчитан, и далее сравнивают значения показателей эффективности между собой, выделяя все локальные максимумы и выбирая среди них глобальный; или 2) последовательно сравнивают между собой значения целевой функции, вычисленные на текущем и предыдущем шагах, и запоминают только следующее, меньшее (большее) зна-


11

Рис. 1. Включение множествах в Хд:
X — множество допустимых решений;
Хд — гиперкуб, включающий множество допустимых решений X

q₂(x) гО

чение показателя эффективности и координаты точки, в которой он вычисляется. В результате определяется оптимум.
     Первый подход используют тогда, когда есть уверенность или хотя бы допускается предположение, что решаемая задача является многоэкстремальной. В этом случае часто требуется найти все локальные оптимумы и выбрать из них глобальный. Поэтому весьма полезно до применения вычислительных процедур изучить задачу оптимизации на предмет принадлежности ее к классу задач выпуклого программирования. Если окажется, что рассматриваемая задача относится к этому классу задач, то алгоритм поиска оптимума упрощается, поскольку найденный локальный оптимум единственный и он же является глобальным.
     Есть на первый взгляд сложная проблема — «вписать» множество допустимых решений X в гиперкуб. Если размеры гиперкуба будут слишком большими, то тогда придется проводить много лишних проверок: действительно ли очередная точка хк, рассматривае

12