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

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

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

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

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

Рекомендовано методическим советом УрФУ 
для студентов вуза, обучающихся по направлениям подготовки 
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
®Ґ
= +Ґ,