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

 
 
 
 
 
В. М. Поляков, З. С. Агаларов 
 
 
 
МЕТОДЫ ОПТИМИЗАЦИИ 
 
Учебное пособие 
 
2-е издание 
 
Рекомендовано  
Учебно-методическим советом по высшему образованию  
в качестве учебного пособия для студентов бакалавриата  
и магистратуры, обучающихся по направлению подготовки  
«Прикладная математика» 
 
 
 
Москва 
Издательско-торговая корпорация «Дашков и Кƒ» 
2022 
 

УДК 519.85 
ББК 22.18 
П54 
 
Авторы: 
В. М. Поляков - доктор технических наук, профессор, профессор кафедры математики, ФГБОУ ВО «Российский государственный геологоразведочный университет им. Серго Орджоникидзе»; 
З. С. Агаларов – кандидат экономических наук, доцент кафедры математики, ФГБОУ ВО «Российский государственный геологоразведочный университет им. Серго Орджоникидзе». 
 
Рецензент: 
Н. В. Еремеев - кандидат технических наук, доцент, доцент кафедры технологии и системы автоматизированного производства металлургических 
процессов, ФГБОУ ВО «Московский авиационный институт (национальный 
исследовательский университет)». 
 
 
 
Поляков, Владимир Михайлович. 
П54   
Методы оптимизации : учебное пособие / В. М. Поляков, 
З. С. Агаларов. ² 2-е изд. ² Москва : Издательско-торговая 
корпорация «Дашков и Кƒ», 2022. ² 86 с. 
 
ISBN 978-5-394-05003-9. 
 
В учебном пособии рассматриваются различные методы оптимизации. Основное внимание уделено практической стороне решения задач оптимизации.  
Для студентов бакалавриата и магистратуры, обучающихся по 
направлению подготовки «Прикладная математика», а также студентов других направлений подготовки и специальностей, изучающих методы оптимизации. 
 
 
 
 
ISBN 978-5-394-05003-9 
‹ Поляков В. М., Агаларов З. С., 2021 
‹ ООО «ИТК «Дашков и Ко», 2021 
2 
 

 
СОДЕРЖАНИЕ 
ВВЕДЕНИЕ ........................................................................................... 
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. ЗАДАЧА ПОИСКА ЭКСТРЕМУМОВ ФУНКЦИИ, 
ЗАДАННОЙ НА Rn  
............................................................................ 
55
5.1. Аналитическое решение задачи оптимизации  
функции w(x), заданной на Rn  ....................................................... 
55
5.2. Численное решение задачи оптимизации  
функции w(x), заданной на Rn  
........................................................ 
57
5.2.1. Метод градиентного (наискорейшего) спуска 
........... 
58
5.2.2. Метод покоординатного спуска ................................. 
69
6. ЧИСЛЕННОЕ РЕШЕНИЕ ЗАДАЧИ ОПТИМИЗАЦИИ 
ФУНКЦИИ fx, ЗАДАННОЙ НА ОГРАНИЧЕННОМ 
МНОЖЕСТВЕ 8 ك Rn  ....................................................................... 
75
6.1. Метод штрафных функций 
...................................................... 
75
6.2. Алгоритмы методов штрафных и барьерных  
функций ........................................................................................... 
81
ЗАКЛЮЧЕНИЕ 
.................................................................................. 
84
ЛИТЕРАТУРА 
.................................................................................... 
85
 
4 

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

мистом не лежат кучи денег или ценных бумаг, нет станков и механизмов, которые могут использоваться в производстве. Все - в таблицах на бумажном носителе или, возможно, в табличках Excel на 
экране компьютера. Суть одна ² экономист создал математическую 
модель инвестиций и работает с ней, чтобы дать прогноз эффективности анализируемых решений и выбрать из них лучшее. Другими 
словами, этот экономист занимается оптимизацией инвестиций.  
Предположим, что в таблице, которую подготовил экономист, 
представлены только три варианта инвестиций. Во многих случаях 
рассматриваемая задача оптимизации предусматривает анализ значительно большего числа вариантов решений. В этих ситуациях математическая модель, описывающая процесс оценки эффективности 
рассматриваемых вариантов, усложняется. Очень часто в таких случаях применяют модели математического программирования. Решая 
задачу математического программирования, находят вариант (варианты) оптимального распределения ограниченных ресурсов, позволяющий достичь поставленную цель. Подробно о постановке цели 
(целей) операций, задачах и теории математического программирования рассказывается, в частности, в работах [1, 2, 3, 6]. В данном 
пособии рассматриваются численные методы решения задач математического программирования: 
‹  
௫
ሺˋˎˋ ƒšሻݓሺݔሻǡ    ݔא ܺ Ǥ                              ሺͲǤͳሻ 
В этой задаче ݓሺݔሻ ² показатель эффективности, характеризующий степень достижения цели в зависимости от проводимых мероприятий, характеризуемых вектором ݔ. Множество ܺ в задачах оптимизации, как правило, задают с помощью системы равенств и 
неравенств типа 
݃ሺݔሻ൒Ͳ,   ݄ሺݔሻൌͲ. 
Предполагается, что читатель знаком с постановкой задач математического программирования и имеет представление о теории 
математического программирования. Теория математического про- 
6 

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

чений ݓሺݔ௞ሻ в этих точках). А также изучение сходимости значений 
ݓሺݔ௞ሻ к значению целевой функции в точке оптимума ݓሺݔכሻ.  
В настоящее время легко найти множество как коммерческих, 
так и общедоступных программ, написанных на различных языках 
программирования, реализующих методы оптимизации. Используя 
эти программы, их пользователю остается только ввести в числе исходных данных целевую функцию, ограничения и заданную точность вычисления оптимума. Далее результат получается автоматически, но не всегда верный. Это как с вождением автомобиля ² 
чтобы тронуться с места, достаточно знать органы управления автомобилем. Но если вы не знаете его возможностей в различных условиях эксплуатации, не знакомы с его устройством, особенностями 
взаимодействия различных агрегатов, то далеко не уедете. Поэтому 
мы посчитали верным решением ознакомить читателей с работой часто используемых в прикладных программах оптимизации алгоритмов и довести их до программной реализации. Вопросы сходимости 
мы упоминаем только в связи с особенностями исходных задач и 
применяемых методов оптимизации.  
Приступая к изучению теории оптимизации, мы бы советовали 
читателям освежить знания по этому вопросу, познакомившись с материалом, представленным, например, в источнике [7]. Кроме этой 
работы, существуют сотни других пионерских и обзорных работ на 
эту тему. Масса полезных сведений на этот счет имеется в интернете.  
В данном пособии мы не рассматриваем линейное программирование как самостоятельный метод оптимизации, поскольку эта задача традиционно изучается в курсе «Исследование операций». Курс 
«Методы оптимизации» читается по направлению подготовки «Прикладная математика» в 8-м семестре. Настоящее пособие подготовлено на основе материалов занятий по данному предмету, а также по 
дисциплине «Интеллектуальные системы», проводимых авторами 
пособия. Сделан акцент на практическую сторону реализации методов поиска экстремумов. 
8 

1. НЕКОТОРЫЕ ПРОБЛЕМЫ, ВОЗНИКАЮЩИЕ  
ПРИ ИСПОЛЬЗОВАНИИ ЧИСЛЕННЫХ МЕТОДОВ 
ОПТИМИЗАЦИИ 
Решением задачи (0.1) являются точка ݔכ и значение целевой 
функции (показателя эффективности) в этой точке ²  ݓሺݔכሻ. Они 
должны быть найдены с удовлетворяющей исследователя точностью. 
Известно о ряде проблем, с которыми часто сталкиваются специалисты, занимающиеся поиском оптимальных решений с помощью математического моделирования различных процессов. Математическая 
модель, описывающая ход оптимизации, должна адекватно описывать 
изучаемую задачу. А именно: показатель эффективности, являющийся, по сути, математическим эквивалентом степени достижения 
цели операции, должен быть чувствителен к изменению оптимизируемых переменных. Если это не так, то либо степень достижения цели 
операции слабо зависит от тех мероприятий, которые проводятся и моделируются, либо математическая модель разработана неверно.  
В первом случае к математическому моделированию приступили слишком рано, не изучив в достаточной степени рассматриваемый процесс. Во втором случае требуется более тщательный подбор математической зависимости между показателем эффективнос- 
ти операции и управляемыми переменными, характеризующими 
проводимые для достижения цели операции. Показатель эффективности может стремиться при некоторых значениях оптимизируемых 
показателей к бесконечности. Другими словами, математическая зависимость показателя эффективности от оптимизируемых переменных адекватно реагирует на их изменения, но при некоторых значениях управляемых переменных теряет смысл.  
Например, рассмотрим функцию эффективности (1.1). При 
ܽଶݔଵൌെܽଷݔଶ значение функции 
                                    ሺͳǤͳሻ 
ݓሺݔሻൌ
ܽଵݔଵ
ܽଶݔଵ൅ܽଷݔଶ
стремится к бесконечности. 
9