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

Министерство образования и науки Российской Федерации
Уральский федеральный университет
имени первого Президента России Б. Н. Ельцина

И. В. Гребенникова

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

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

Рекомендовано методическим советом УрФУ 
для студентов вуза, обучающихся по направлениям подготовки 
09.03.02 — Информационные системы и технологии;
 09.04.02 — Информационные системы и технологии

Екатеринбург
Издательство Уральского университета
2017

УДК 004.4-048.34(075.8)
ББК 32.973я73
          Г79

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

Научный редактор — канд. техн. наук, доц. В. А. Пухов

 
Гребенникова, И. В.
Г79    Методы оптимизации : учебное пособие / И. В. Гребенникова. — 
Екатеринбург : УрФУ, 2017. — 148 с.

ISBN 978-5-7996-2090-5

Представлены основные разделы курса «Методы оптимизации» для из-
учения в техническом вузе. Каждый раздел пособия содержит теоретиче-
скую часть, примеры решения типовых задач, систематизированную под-
борку контрольных заданий.
Предназначено для бакалавров направления 09.03.02 «Информацион-
ные системы и технологии» и магистров 09.04.02 «Информационные систе-
мы и технологии» всех форм обучения.

Библиогр.: 11 назв. Рис. 15.

УДК 004.4-048.34(075.8)
ББК 32.973я73

ISBN 978-5-7996-2090-5 
© Уральский федеральный
 
     университет, 2017

Оглавление

Предисловие ...................................................................................5
1. Постановка оптимизационной задачи ......................................6

1.1. Экстремальные задачи. Определения ................................6
        Контрольные задания ....................................................... 10
1.2. Разрешимость задачи оптимизации ................................. 11
        Контрольные задания ....................................................... 15

2. Оптимизация функции одной переменной ............................ 16

2.1. Необходимые и достаточные условия локального 
        экстремума ........................................................................ 16
        Контрольное задание ........................................................ 23
2.2. Отыскание наибольшего и наименьшего значений 
        на отрезке .......................................................................... 24
        Контрольные задания ....................................................... 27
2.3. Выпуклые функции ........................................................... 29
        Контрольные задания ....................................................... 31

3. Численные методы минимизации функции одной 
      переменной .............................................................................. 32

3.1. Унимодальные функции ................................................... 33
        Контрольные задания ....................................................... 35
3.2. Метод перебора ................................................................. 35
        Контрольные задания ....................................................... 39
3.3. Методы сокращения отрезка поиска ................................ 40
        3.3.1. Метод деления отрезка пополам (дихотомии) ....... 41
        3.3.2. Метод золотого сечения .......................................... 46
        3.3.3. Метод Фибоначчи ................................................... 51
        Контрольные задания ....................................................... 56

4. Оптимизация функции нескольких переменных ................... 59

4.1. Необходимые и достаточные условия экстремума .......... 59
        Контрольное задание ........................................................ 69

Оглавление

4.2. Условный экстремум функции нескольких переменных .......70
        Контрольное задание ........................................................ 79
4.3. Отыскание наибольшего и наименьшего значений 
        функции нескольких переменных в замкнутой области .... 79
        Контрольное задание ........................................................ 86

5. Численные методы минимизации функции нескольких 
      переменных .............................................................................. 87

5.1. Методы безусловной минимизации ................................. 87
5.2. Метод градиентного спуска .............................................. 89
        Контрольные задания ....................................................... 93
5.3. Метод наискорейшего спуска ........................................... 94
        Контрольное задание ........................................................ 97
5.4. Метод сопряженных градиентов ...................................... 97
        Контрольные задания ..................................................... 101
5.5. Метод Ньютона ............................................................... 102
        Контрольные задания ..................................................... 108

6. Линейное программирование ............................................... 110

6.1. Постановка задачи линейного программирования ....... 110
        Контрольные задания ..................................................... 116
6.2. Графический метод решения задачи линейного 
        программирования.......................................................... 120
        Контрольные задания ..................................................... 128
6.3. Симплекс-метод решения задачи линейного 
        программирования.......................................................... 131
        Контрольное задание ...................................................... 143

Библиографический список ....................................................... 146



Предисловие

К

аждая глава учебного пособия состоит из двух частей: 
теоретической и практической. В первой части содер-
жится теоретический материал справочного харак-
тера: понятия, определения, утверждения, формулы по курсу 
«Методы оптимизации», а также примеры решения типовых 
задач, графические иллюстрации. Вторая часть включает си-
стематизированную подборку заданий для самостоятельно-
го решения.
По содержанию данное пособие соответствует требованиям 
ФГОС ВО направлений подготовки 09.03.02 «Информационные 
системы и технологии» и 09.04.02 «Информационные системы 
и технологии» всех форм обучения и включает в себя в соответ-
ствии с учебной программой основные разделы:
— постановка задачи конечномерной оптимизации;
— оптимизация функции одной переменной;
— численные методы минимизации функции одной пере-
менной;
— оптимизация функции нескольких переменных;
— численные методы минимизации функции нескольких 
переменных;
— линейное программирование.
Математический аппарат, применяемый в данном пособии 
и используемый при изучении курса «Методы оптимизации» 
и решении задач, не выходит за пределы обычного (стандарт-
ного) курса высшей математики в технических вузах.



1.Постановкаоптимизационнойзадачи

1.1.Экстремальныезадачи.Определения
З

адачи отыскания наибольших и наименьших величин 
часто возникают в науке, технике и экономике. Что-
бы применять математические методы для их решения 
и анализа, необходимо уметь переходить от содержательной 
к математической постановке задачи. Для этого нужно опре-
делить:
— целевую функцию f x
R
R
n
( ):
®
;
— множество допустимых решений X
Rn
М
 (допустимое мно-
жество) для функции f x
( );
— критерий оптимизации extrО{min,max}.
Таким образом, тройка вида ( ,
,
)
f X extr  задает экстремаль-
ную или оптимизационную задачу. Формально математическая 
постановка выглядит следующим образом:

 
f x
x X
( ) ®
О
extr.

Задача оптимизации заключается в следующем: требуется 
найти x
X
0 О
 (если он существует), доставляющее экстремаль-
ное (минимальное или максимальное) значение целевой функ-
ции f x
( ) на множестве X , а именно для x0 должно выполнять-
ся одно из условий:

1.1.Экстремальныезадачи.Определения

 
либо f x
f x
(
)
( )
0 Ј
 для всех x
X
О
, 
(1.1)

 
либо f x
f x
(
)
( )
0 і
 для всех x
X
О
. 
(1.2)

Если такого элемента на множестве X  не существует, то тре-
буется построить последовательность

 
{
}
xk , k =1 2
, , …, x
X
k О
, 
(1.3)

такую, что выполняется одно из соотношений

 
lim
(
)
inf
( )
k
k
x X
f x
f x
®Ґ
О
=
, 
(1.4)

 
lim
(
)
sup ( )
k
k

x X
f x
f x

®Ґ
О
=
. 
(1.5)

Ниже приведем несколько определений различных объектов.
Определение 1.1. Точка x
X
0 О
, удовлетворяющая усло-
вию (1.1), называется точкой глобального минимума функции 
f x
( ) на множестве X , следовательно, x
X
0 О
, удовлетворяющая 
условию (1.2), — точкой глобального максимума функции f x
( ) 
на X .
Последовательность {
}
xk  (1.3), удовлетворяющая равен-
ству (1.4), — минимизирующая для функции f x
( ) на множе-
стве X , следовательно, последовательность {
}
xk , удовлетворя-
ющая (1.5), — максимизирующая для f x
( ) на множестве X .
Если X
Rn
=
, то задача оптимизации — задача безусловного 
экстремума f x
( ). Если X
Rn
№
, то имеем задачу на условный экс-
тремумf x
( ).
Определение 1.2. Функция f x
( ) называется ограниченной 
снизу на множестве X , если существует такое число m, что вы-
полняется m
f x
Ј
( ) для " О
x
X .
Для функции f x
( ), ограниченной сверху на множестве X , 
существует такое число M , что выполняется f x
M
( ) Ј
 для " О
x
X .
Определение 1.3. Число m
f x
x X
0 =
Оinf
( ) называется нижней гра-

нью функции f x
( ) на множестве X :

1.Постановкаоптимизационнойзадачи

1) если m
f x
0 Ј
( ) для " О
x
X ;
2) для " >
e
0 $
О
<
+
x
X
f x
m
e
e
e
:
(
)
0
.
Если f x
( ) не ограничена снизу на множестве X , то полагают

 
m
f x
x X
0 =
= -Ґ
Оinf
( )
.

Число M
f x
x X

0 =
О
sup ( ) называется верхней гранью функции f x
( ) 

на множестве X :
1) если f x
M
( ) Ј
0 для " О
x
X ;
2) для " >
e
0 $
О
>
-
x
X
f x
M
e
e
e
:
(
)
0
.
Если f x
( ) не ограничена сверху на множестве X , то

 
M
f x
x X

0 =
= +Ґ
О
sup ( )
.

Рассмотрим примеры целевых функций.

Пример 1.1

Рассмотрим целевую функцию f x
x
( ) = 1, X =
+Ґ
[ ,
)
1
. Показать, 

что множество точек минимума функции f x
( ) на множестве X  
пусто и m
f x
x X
0
0
=
=
Оinf
( )
, а максимум функции f x
( ) на множе-

стве X  существует и равен 1.

Р е ш е н ие
Предположим, что множество точек минимума функции f x
( ) 
на множестве X  не пусто, то есть существует хотя бы одна точ-
ка минимума x
X
0 О
 функции f x
( ). Возьмем произвольное чис-

ло x
x
>
0. Тогда x
X
О
 и f x
x
x
f x
(
)
( )
0

0

1
1
=
>
=
, то есть x0 не являет-

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

1.1.Экстремальныезадачи.Определения

Покажем, что m
f x
x X
0
0
=
=
Оinf
( )
. Очевидно, для произвольного 
x
X
О
=
+Ґ
[ ,
)
1
 справедливо равенство f x
x
( ) =
>
1
0. Далее пусть 

e > 0. Возьмем произвольное xe
e
>
ж
из

ц
шч
max
,
1 1 . Тогда x
X
e О
 

и f x
(
)
e
e
e
<
=
+
0
. Поэтому m0
0
= .

Для f x
x
( ) = 1 имеем M
f x
f x
f
x X
x X
0
1
1
=
=
=
=
О
О
sup ( )
max
( )
( )
.

Пример 1.2
Пусть целевая функция f x
e
x
( ) =
- , X
R
=
. Показать, что множество 
точек минимума функции f x
( ) на множестве X  пусто и 

m
f x
x X
0
0
=
=
Оinf
( )
, найти M
f x
x X

0 =
О
sup ( ).

Р е ш е н и е
Предположим, что множество точек минимума функции f x
( ) 
на множестве X  не пусто, то есть существует хотя бы одна точка 
минимума x
X
0 О
 функции f x
( ). Возьмем произвольное число 
x
x
>
0. Тогда x
X
О
 и f x
e
e
f x

x
x
(
)
( )
0

0
=
>
=
-
-
, то есть x0 не является 
точкой минимума f x
( ) на множестве X . Полученное 
противоречие и доказывает, что множество точек минимума 
функции f x
( ) на множестве X  пусто.
Покажем, что m
f x
x X
0
0
=
=
Оinf
( )
. Очевидно, для произвольного 
x
X
О
 справедливо равенство f x
e

x
( ) =
>
-
0. Далее пусть e > 0. 

Возьмем произвольное xe
e
> ln 1 . Тогда x
X
e О
 и f x
(
)
e
e
e
<
=
+
0
. 

Поэтому m0
0
= .
Для f x
e
x
( ) =
-  имеем M
f x
x X

0
1
=
=
О
sup ( )
, кроме того, 

sup ( )
max
( )
( )
x X
x X
f x
f x
f
О
О
=
=
=
0
1.

1.Постановкаоптимизационнойзадачи

Пример 1.3
Пусть функция f x
x
( )
ln
=
, X = ( , ]
0 1 . Найти m
f x
x X
0 =
Оinf
( ).

Р е ш е н и е
Функция f x
( ) не ограничена снизу на множестве X , поэтому 
по определению нижней грани полагаем m
f x
x X
0 =
= -Ґ
Оinf
( )
.

С учетом равенства min
x X
x X
f x
f x
О
О
= -
-
( )
max(
( )) задача максимизации 
может быть сведена к задаче минимизации.

Контрольные задания

1. Найти множество точек минимума функции f x
( ) на множестве 
X :
а) f x
x
( )
sin
=
2 p , X
R
=
;
б) f x
x
x
( ) =
-
2 , X = -
[
, ]
1 2 ;

в) f x
( )
cos
=
p
2, X =[ , ]
0 1 ;

г) f x
x
x

x
( )

,
,

,
,

=

>

Ј

м
нп

оп

1

1
1  X
R
=
.

2. Показать, что множество точек минимума функции f x
( ) 
на множестве X  пусто и найти m
f x
x X
0 =
Оinf
( ):

а) f x
x
( ) =
+
1
1
2 , X
R
=
;

б) f x
x
x
x
( ) =
-
+
+
2
9
12
5
3
2
, X = -Ґ
(
, )
5 ;

в) f x
x
x
( )
sin
=
, X
R
=
;

г) f x
x
( )
arctg
=
, X = -Ґ -
(
,
]
1 ;

д) f x
x
( )
tg
=
, X = -
[
, ]
2 2 ;

1.2.Разрешимостьзадачиоптимизации

е) f x
x
( )
ln
=
1 , X = ( , )
0 1 ;

ж) f x
x
( )
ln
=
1 , X =
+Ґ
( ,
)
1
.

3. Показать, что если min
( )
x X f x
О
 существует, то 

inf
( )
min
( )
x X
x X
f x
f x
О
О
=
.

1.2.Разрешимостьзадачиоптимизации

Из условий, гарантирующих существование точек глобального 
минимума или максимума функции f x
( ) на множестве X , 
вытекают следующие теоремы.

Теорема 1.1 (Вейерштрасса). Если множество X
Rn
М
 не пусто 
и компактно (ограничено и замкнуто), а функция f x
( ) 
непрерывна на нем, то множество точек глобального минимума (
и множество точек глобального максимума) функции f x
( ) 
на нем не пусто и компактно.
В условиях теоремы Вейерштрасса любая минимизирующая 
последовательность {
}
xk  сходится к множеству точек глобального 
минимума.

Теорема 1.2. Пусть множество X
Rn
М
 непусто и замкнуто, 
а функция f x
( ) непрерывна на нем. Пусть выполняется хотя бы 
одно из следующих условий:
1) существует такая точка X
X
* М
, что множество вида

 
X
x
X
f x
f x
*
*
:
( )
(
)
=
О
Ј
{
}

 
ограничено;
2) для любой последовательности {
}
xk , k =1 2
, ,..., x
X
k О
, такой 
что
 
lim
k
k
x
®Ґ
= +Ґ,