Методы оптимизации. Практический курс

А.В. Пантелеев
Т.А. Летова

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

ПРАКТИЧЕСКИЙ КУРС

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

Москва
Логос

2020

УДК 519.8
ББК 22.161.5
          П16

Серия основана в 2003 году

Р е ц е н з е н т ы

Кафедра управления бизнесом в строительстве 

Государственного университета управления

Б.В. Павлов, доктор технических наук, профессор, главный научный 

сотрудник Института проблем управления РАН им. В.А. Трапезникова

Пантелеев А.В.

П16      Методы оптимизации. Практический курс: учебное пособие с муль
тимедиа сопровождением / А.В. Пантелеев, Т
    .А. Летова. – М.: Логос, 

2020. – 424 с: ил. (Новая университетская библиотека).

ISBN 978-5-98704-540-4

Рассмотрены аналитические методы решения задач поиска экстремума 

функций многих переменных на основе необходимых и достаточных условий. 
Изложены численные методы нулевого, первого и второго порядков решения 
задач безусловной минимизации, а также численные методы поиска условного экстремума. Описаны алгоритмы решения задач линейного программирования, целочисленного программирования, транспортных задач. Приведено 
решение разнообразных типовых  примеров и практических задач оптимизации.

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

УДК 519.8
ББК 22.161.5 

ISBN 978-5-98704-540-4 
© Пантелеев А.В., Летова Т.А., 2020
© Логос, 2020

ОГЛАВЛЕНИЕ 

 

Раздел  I. УСЛОВИЯ  ЭКСТРЕМУМА  ФУНКЦИЙ............................................................. 6 

Глава 1. Общая постановка задачи оптимизации и основные положения ................. 6 

Глава 2. Необходимые и достаточные условия безусловного экстремума ................ 22 

Глава 3. Необходимые и достаточные условия условного экстремума...................... 39 
     3.1. Постановка задачи и основные определения................................................. 39 
 
     3.2. Условный экстремум при ограничениях типа равенств............................... 42 
 
     3.3. Условный экстремум при ограничениях типа неравенств........................... 64 
             
3.4. Условный экстремум при смешанных ограничениях................................... 86 
 
Раздел II. ЧИСЛЕННЫЕ МЕТОДЫ ПОИСКА БЕЗУСЛОВНОГО ЭКСТРЕМУМА .. 110  

Глава 4. Принципы построения численных методов поиска безусловного  
     экстремума............................................................................................................ 110 

Глава 5. Методы нулевого порядка................................................................................. 116 
 
     5.1.  Методы одномерной минимизации............................................................ 116 
 
           
5.1.1. Общая постановка задачи и стратегии поиска ................................ 116  
 
 
 
5.1.2. Метод равномерного поиска ............................................................. 119 
 
           
5.1.3. Метод деления интервала пополам .................................................. 121 
 
           
5.1.4. Метод дихотомии ............................................................................... 125 
 
           
5.1.5. Метод золотого сечения .................................................................... 126 
 
           
5.1.6. Метод Фибоначчи .............................................................................. 132 
 
           
5.1.7. Метод квадратичной интерполяции................................................. 135 
 
     5.2.  Метод конфигураций ................................................................................... 138 
 
     5.3.  Метод деформируемого многогранника.................................................... 144 
 
     5.4.  Метод Розенброка ........................................................................................ 151 
 
     5.5.  Метод сопряженных направлений.............................................................. 157 
 
     5.6.  Методы случайного поиска......................................................................... 160  
 
 
       5.6.1. Адаптивный метод случайного поиска........................................... 160 
 5.6.2. Метод случайного поиска с возвратом  
 
 
 
        
при неудачном шаге.......................................................................... 166 
 
 
 
5.6.3. Метод наилучшей пробы.................................................................. 168 

Глава 6. Методы первого порядка ................................................................................... 171 
 
     6.1.  Метод градиентного спуска с постоянным шагом.................................... 171 
 
     6.2.  Метод наискорейшего градиентного спуска ............................................. 177 
 
     6.3.  Метод покоординатного спуска.................................................................. 182 
 
     6.4.  Метод Гаусса–Зейделя................................................................................. 188 
 
     6.5.  Метод Флетчера–Ривса................................................................................ 194 
 
     6.6.  Метод Дэвидона–Флетчера–Пауэлла......................................................... 200 
 
     6.7.  Метод кубической интерполяции............................................................... 205 

Глава 7. Методы второго порядка ................................................................................... 209 
 
     7.1.  Метод Ньютона............................................................................................. 209 
 
     7.2.  Метод Ньютона–Рафсона ............................................................................ 214 
             
7.3.  Метод Марквардта ....................................................................................... 218 

 
3

 
Раздел III. ЧИСЛЕННЫЕ  МЕТОДЫ  ПОИСКА  УСЛОВНОГО  ЭКСТРЕМУМА.... 225 

Глава 8. Принципы построения численных методов поиска условного  
     
экстремума............................................................................................................ 225 

Глава 9. Методы последовательной безусловной минимизации............................... 232 
 
    
9.1. Метод штрафов............................................................................................. 232 
 
    
9.2. Метод барьерных функций ......................................................................... 241 
 
    
9.3. Комбинированный метод штрафных функций ......................................... 247 
            
9.4.  Метод множителей....................................................................................... 252 
 
    
9.5.  Метод точных штрафных функций............................................................ 259 

Глава 10. Методы возможных направлений .................................................................. 267 
 
    
10.1. Метод проекции градиента.......................................................................... 267 
 
 
10.1.1.  Метод проекции градиента в задачах с ограничениями 
             
         
типа равенств………………………………………………………267
                      
10.1.2.  Метод проекции градиента в задачах с ограничениями 
 
                              типа неравенств……………………………………………………272 
 
    
10.2.  Метод Зойтендейка ..................................................................................... 277 
 
Раздел IV. ЗАДАЧИ  ЛИНЕЙНОГО  ПРОГРАММИРОВАНИЯ................................. 283 

Глава 11. Методы решения задач линейного программирования............................. 283 
11.1. Симплекс-метод Данцига............................................................................ 283  
11.1.1. Решение канонической задачи....................................................... 283 
11.1.2. Решение основной задачи............................................................... 290 
11.2. Модифицированный симплекс-метод ....................................................... 327 
11.3. Прямая и двойственная задачи линейного программирования .............. 348 

  Глава 12. Методы решения задач линейного целочисленного  
              
программирования.............................................................................................. 368  
 
    
12.1.  Метод ветвей и границ................................................................................ 368 
 
    
12.2.  Метод Гомори.............................................................................................. 387 

Глава 13. Методы решения транспортных задач.......................................................... 402  
 
    
13.1.  Постановка задачи и стратегия решения .................................................. 402 
13.2. Методы нахождения начального плана перевозок................................... 404 
13.2.1. Метод северо-западного угла......................................................... 404 
13.2.2. Метод минимального элемента...................................................... 406 
 
       13.3. Метод потенциалов ...................................................................................... 407 
 
Предметный указатель......................................................................................................... 420 

Cписок литературы............................................................................................................... 422 

 

 
4 

ПРЕДИСЛОВИЕ 
 
 
 
 
Книга предназначена для студентов технических вузов и представляет собой учебное пособие по курсу «Методы оптимизации». Предполагается, что читатель владеет основными понятиями математического анализа и линейной алгебры. Книга состоит из четырех разделов, которые охватывают основной материал курсов лекций, читаемых авторами на различных факультетах Московского авиационного института.  
Первый раздел содержит аналитические методы поиска экстремума функций многих переменных. Их практическое применение при решении прикладных задач весьма 
ограничено. Условия экстремума функций служат методологической основой численных 
процедур поиска условного и безусловного экстремумов и предназначены для исследования точек, получаемых в процессе приближенного решения задач оптимизации. 
Второй раздел посвящен изложению численных методов поиска безусловного экстремума, используемых в качестве основного инструмента решения более сложных и 
часто встречающихся на практике задач условной оптимизации, рассмотренных в третьем разделе.  
Четвертый раздел включает методы решения задач линейного и целочисленного 
программирования, являющихся частным случаем задач поиска условного экстремума, 
для которых разработаны специальные алгоритмы решения, а также методы решения 
транспортных задач. 
Изложение построено по единой схеме, включающей постановку задачи, стратегию поиска, алгоритм и процедуру решения, сходимость метода, демонстрационные 
примеры, прикладные задачи. 
В конце каждой главы предлагаются задачи для самостоятельного решения с ответами. Кроме того, имеются задачи для расчетно-графических работ, в том числе зависящие от параметров  m  – порядкового номера учебной группы в лекционном потоке и n  – 
номера студента по списку группы. Это может позволить студентам выработать навыки 
решения типовых задач оптимизации.  
Книга может быть использована для самостоятельного изучения курса, так как содержит весь необходимый теоретический материал и большое количество детально разобранных примеров. 
К книге прилагается CD диск с компьютерной версией учебного пособия, снабженной гипертекстовой информационно-поисковой системой, лабораторными практикумами по решению задач поиска безусловного экстремума, задач линейного программирования, транспортных задач. Авторы выражают сердечную благодарность своей коллеге 
С.Ю. Луневой, а также студентам и выпускникам факультета прикладной математики и 
физики Т. Слепневой, А. Пикалеву, С. Духовенскому, С. Троепольскому,  Г. Турунову,  
Г. Сологубу, З. Хакимову, К. Пономаревой за помощь при создании компьютерного 
учебно-методического комплекса по курсу «Методы оптимизации». 

Раздел I.  УСЛОВИЯ  ЭКСТРЕМУМА  ФУНКЦИЙ 

Глава 1. ОБЩАЯ  ПОСТАНОВКА  ЗАДАЧИ  ОПТИМИЗАЦИИ                  
И  ОСНОВНЫЕ  ПОЛОЖЕНИЯ 

 
Постановка задачи поиска минимума функций содержит: 
• целевую функцию 
( )
f x , где 
1
(
,...,
)T
n
x
x
x
=
, определенную на n-мерном евклидо
вом пространстве Rn . Ее значения характеризуют степень достижения цели, во 
имя которой поставлена или решается задача; 
• множество допустимых решений X
Rn
⊆
, среди элементов которого осуществляется поиск. 
 
Требуется найти такой вектор 
 из множества допустимых решений, которому 
соответствует минимальное значение целевой функции на этом множестве: 
x∗

 
 
(
)
( )
min
x X

f x
f
∗
∈
=
x .                                      
(1.1) 

 
З а м е ч а н и я  1.1.  
 
1. Задача поиска максимума функции 
( )
f x  сводится к задаче поиска минимума путем замены знака перед функцией на противоположный (рис. 1.1): 

[
]
(
)
( )
( )
max
min
x
X
x
X

f x
f x
f
∗
∈
∈
=
= −
−
x . 

 

 

f

(
)
f x∗
( )
f x  

x ∗

x 

( )
f x
−
 

(
)
f x∗
−

Рис. 1.1 

2. Задача поиска минимума и максимума целевой функции 
( )
f x  называется зада
чей поиска экстремума:  
(
)
( )
extr
x X

f x
f
∈
=
x
∗
. 

3. Если множество допустимых решений X задается ограничениями (условиями), 
накладываемыми на вектор x , то решается задача поиска условного экстремума. Если 
, т.е. ограничения (условия) на вектор x отсутствуют, решается задача поиска  
безусловного экстремума. 
X
Rn
=

 
6 

4. Решением задачи поиска экстремума является пара (
,
(
))
x
f x
∗
∗
, включающая 

точку 
 и значение целевой функции в ней. 
x∗

5. Множество точек минимума (максимума) целевой функции 
( )
f x  на множестве 

X  обозначим 
. Оно может содержать конечное числo точек (в том числе одну), бесконечное число точек или быть пустым. 
X ∗

 
Определение 1.1. Точка x
X
∗ ∈
 называется точкой глобального (абсолютного) минимума функции 
( )
f x  на множестве X , если функция достигает в этой точке своего наименьшего значения, т.е.  
(
)
( )
f x
f
∗ ≤
x     ∀
∈
x
X . 

 
Определение 1.2. Точка x
X
∗ ∈
 называется точкой локального (относительного) 
минимума функции 
( )
f x  на множестве допустимых решений X , если существует ε > 0 , 

такое, что если 
 и 
x
X
∈
ε
<
−
∗
x
x
, то 
(
)
( )
f x
f
∗ ≤
x . Здесь 
2
2
2
2
1
...
n
x
x
x
x
+
+
+
=
 – 

евклидова норма вектора x . 

 
З а м е ч а н и я  1.2. 
 
1. В определении 1.1 точка 
 сравнивается по величине функции со всеми точками из множества допустимых решений 
, а в определении 1.2  – только  с принадлежащими ее ε -окрестности (рис. 1.2). 

x∗

X

 

 
Рис. 1.2 
 

2. Если в определениях 1.1 и 1.2 знак неравенства ≤ заменить на 
, то получим 
определения глобального (абсолютного) и локального (относительного) максимумов. 
≥

3. Глобальный экстремум всегда является одновременно локальным, но не наоборот. 

 
Определение 1.3. Поверхностью уровня функции 
( )
f x  называется множество точек, в которых функция принимает постоянное значение, т.е. 
.  Если 
( )
f x = const
n = 2, 

поверхность уровня изображается линией уровня на плоскости 
. 
R2

 

X

 

 

x2

ε 

x ∗

x1

 
7

 
Пример 1.1. Построить линии уровня функций: 

    
а) 
2
1
( )
2
2
f x
x
x
=
+
;     б) 

2
2
1
2
( )
4

x
f x
x
=
+
;    

  
в) 
2
2
2
( )
1
f x
x
x
=
−
;     г) (
)
f x
x
x
1
2
2
2
,
=
. 
Уравнения линий уровня имеют следующий вид [10]: 

а) 
2
2
1
2
( )
2
f x
x
x
r
=
+
=
=
const
 –  уравнение окружностей с центром в точке (
 и 
радиусом, равным r (рис. 1.3, а); 
)
0 0
,
T

 
б) 

2
2
1
2
( )
const
4

x
f x
x
=
+
=
 – уравнение эллипса. Если 
, то 
const
1
=
a = 2  и b = 1 –  

большая и малая полуоси (рис. 1.3, б); 
 
в) 
 – уравнение гиперболы (рис. 1.3, в); 
2
2
2
1
( )
const
f x
x
x
=
−
=

 
г) 
 – уравнение двух параллельных оси 
 прямых (рис. 
1.3, г). (
)
f x
x
x
1
2
2
2
,
=
= const
Ox1

 
 
x2
 

 

f

 
 
а) 
 
 

 
 
 
б) 
 
Рис. 1.3 

x2

( )
const
4
f x =
=
2
2
2
1
2
( )
f x
x
x
=
+
 

x1
1 
2 

( )
0
f x =
( )
const
1
f x =
=
 
x1

x2

f

( )
4
f x =
 
2
2
1
2
2
( )
4

x
f x
x
=
+
 

1
x1

x1

x2

2 
− 4

( )
1
f x =  
( )
0
f x =

4 

 
8 

 
 
 
 
( )
0
f x =
( )
1
f x =  
x2
f

2
2
2
1
( )
f x
x
x
=
−
 
1
( )
1
f x = −
f x
( ) = −1

x1
1 
– 1
x2

-1 
x1
( )
1
f x =  
( )
0
f x =
 
 
 
 
в) 

 

f
x2

1
( )
1
f x =
(
)
f x
x
x
1
2
2
2
,
=
( )
0
f x =

x1

( )
1
f x =
-1 

x1
x2

г) 
 
Рис. 1.3 (Окончание) 
 
 
 
Пример 1.2. На рис. 1.4 изображены линии уровня функции 
( )
f x . Цифры указывают ее значение на соответствующей линии. Точкам 
 и 
 соответствуют значения 
функции 
A
B

f A
( ) = 10 и f B
( ) = 5 . Требуется классифицировать точки экстремума. 

Функция рассматривается на множестве R2 , т.е. решается задача поиска безус
ловного экстремума. В точке А с координатами 
достигается локальный минимум; в 

точке В с координатами 
достигаются локальный и глобальный минимум одновременно; в точке C нет ни минимума, ни максимума, так как по одним направлениям функция убывает, а по другим – возрастает. Заметим, что изображенная структура линий 
уровня типична для так называемых многоэкстремальных задач.
(
)
1 3
,
T

(
)
3 1
,
T

 

 
9

x2

 
Рис. 1.4 
 
 
 
Пример 1.3. На рис. 1.5 изображен график функции 
( )
f x , определенной на множестве X
R
=
. Требуется классифицировать точки экстремума. 
Решается задача поиска безусловного экстремума. На рис. 1.5 выделим        
-окрестности точек 
ε
A B
F
,
,
,
…
 и проверим выполнение определений 1.1 и 1.2  с учетом 
пп. 1, 2 замечаний 1.1, 1.2. В результате получаем: A – точка локального минимума; B, E 
–  точки локального максимума; бесконечное множество точек из отрезка CD  –  точки 
локального минимума; F  –  точка локального и одновременно глобального минимума; 
глобальный максимум  отсутствует. 
 
Рис. 1.5 

20 

3
A

30

25

C
2

20

22 
1
B
10

x1
3
1
2

f

x 
B
A
D
C
E
F

 
10