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

ФБГОУ ВО СИБИРСКАЯ ПОЖАРНО-СПАСАТЕЛЬНАЯ

АКАДЕМИЯ ГПС МЧС РОССИИ

С.В. БАБЕНЫШЕВ 

Е.Н. МАТЕРОВ 

МЕТОДЫ

ОПТИМИЗАЦИИ

УЧЕБНОЕ ПОСОБИЕ

ЖЕЛЕЗНОГОРСК

2017

ФБГОУ ВО СИБИРСКАЯ ПОЖАРНО-СПАСАТЕЛЬНАЯ

АКАДЕМИЯ ГПС МЧС РОССИИ

С.В. БАБЕНЫШЕВ, Е.Н. МАТЕРОВ 

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

УЧЕБНОЕ ПОСОБИЕ

ЖЕЛЕЗНОГОРСК

2017

УДК 517.97, 519.85
ББК 22.161.8

Б 12 

Рецензенты:

канд. физ.-мат. наук А.В. Кротов
канд. техн. наук М.И. Антипин

Бабенышев, С.В.

Б 12
Методы оптимизации: Учебное пособие для курсантов, студентов

и слушателей/ С.В. Бабенышев, Матеров Е.Н. – Железногорск: ФБГОУ 
ВО Сибирская пожарно-спасательная академия ГПС МЧС России, 2017. 
– 122 с.: ил.

Настоящее учебное пособие предназначено для обучения курсантов, студентов и слу
шателей, обучающихся в ФБГОУ ВО Сибирская пожарно-спасательная академия ГПС МЧС 
России в соответствии с федеральным государственным образовательным стандартом высшего образования. 

В пособии приведены необходимые теоретические сведения и примеры решения за
дач по дисциплине «Методы оптимизации», для обучения по очной, заочной и дистанционной формам обучения. Изложение материала ведется с упором на решение практических задач. В пособии используются примеры, иллюстрирующие применения, связанные с задачами 
МЧС России. 

УДК 517.97, 519.85
ББК 22.161.8

Учебное издание

Бабенышев Сергей Валерьевич, Матеров Евгений Николаевич

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

© ФГБОУ ВО Сибирская пожарноспасательная академия, 2017

ОГЛАВЛЕНИЕ 

Введение........................................................................................................... 5

Раздел 1. Вариационное исчисление и оптимальное управление.............. 6

Тема 1. Элементы вариационного исчисления. ....................................... 6

Тема 2. Оптимальное управление. .......................................................... 23

Тема 3. Динамическое программирование............................................. 33

Раздел 2. Безусловная оптимизация............................................................ 62

Тема 4. Выпуклые множества и функции. ............................................. 62

Тема 5. Методы безусловной оптимизации. .......................................... 72

Раздел 3. Линейное программирование...................................................... 84

Тема 6. Задачи линейного программирования....................................... 84

Тема 7. Транспортная задача. ................................................................ 104

Список сокращений. ................................................................................... 121

Литература. .................................................................................................. 122

ВВЕДЕНИЕ

«Методы оптимизации» – это математическая дисциплина, изучающая 

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

Методы, изучаемые в «Методах оптимизации», применяются в системах 

поддержки логистики и организации производства, на транспорте, при программировании и проектировании промышленных и технологических установок и бытовых приборов.

Целью данного пособия является изложение идей и методов дисциплины 

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

Структурно пособие разделено на три раздела: «Вариационное исчисле
ние и оптимальное управление», «Условная и безусловная оптимизация» и «Линейное программирование». Каждый раздел делится на логически взаимосвязанные темы, хотя существуют идеи и подходы, общие для тем из различных 
разделов. Так, например, в Теме 1 «Элементы вариационного исчисления» применяются подходы аналогичные используемым в Теме 5 «Методы безусловной 
оптимизации», а идея двойственности явно или неявно присутствует почти во 
всех разделах «Методов оптимизации». Далее, каждая тема представлена серией рассматриваемых вопросов, которые могут быть взяты за основу для формирования учебных вопросов для лекционных или практических занятий. 
Внутри каждой темы используется отдельная нумерация рисунков, формул и 
примеров.

РАЗДЕЛ 1. ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ И

ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ

Тема 1. Элементы вариационного исчисления

Вопрос 1. Экстремальные задачи и методы их решения

Предмет вариационного исчисления рассмотрим на примере двух истори
ческих задач: задачи о брахистохроне и задачи о наибольшей площади.

Задача о брахистохроне1. Даны две точки A и B, лежащие в вертикальной 

плоскости. Какова траектория материальной точки, движущейся только под 
действием силы тяжести, которая начинает двигаться из начальной точки A и 
достигает конечной точки B за кратчайшее время?

Задача о брахистохроне была предложена научному сообществу Иоган
ном Кеплером в 1696 году. Свои решения прислали или опубликовали: Исаак 
Ньютон, Готлиб Лейбниц, Гийом Лопиталь, Якоб Бернулли, Эренфрид Чирнхаус.

Дадим вариационную формулировку этой задачи (см. рис. 1).

Пусть A = O(0,0) – начальная точка совпадает с началом координат, ко
нечная – B = B(a, b). Пусть y = y(x) – какая-то траектория движения материальной точки. Выразим скорость движения ν(x) материальной точки с массой m
двумя способами и приравняем выражения между собой.

Рис. 1. Иллюстрация к задаче о брахистохроне.

1) Из закона сохранения энергии

2

2

mv
mgh
mgy



1 Брахистохрона (от греч. βραχιστοζ (брахистос) – кратчайший, χρονοζ (хронос) – время) – кривая наискорейшего спуска.

получаем 
2
v
gy

.

2) С другой стороны:

2
1
,
y dx
dl
v
dt
dt






где dl – элемент дуги кривой, который можно расписать, при явном задании 
функции, как 
2
1
dl
y dx



.

Приравнивая выражения для v, получаем:

2
1
2
y dx
gy
dt





или, разделяя переменные, 

2
1
.

2

y
dt
dx

gy





Таким образом, общее время T прохождения точкой, движущейся по тра
ектории (x, y(x)) при изменении параметра от 0 до a, равно

2
2

0
0

1
1
)
1
(

2
2

a
a
y
y
dx
dx
y
gy
g

T y








.

Задача состоит в нахождении функции ˆ
ˆ( )
y
y x

, дающей минимальное 

значение T(y).

В современной формулировке это записывается следующим образом:

2

0

1
1
inf,

2

a
y
dx
y
g






(0)
0
y

,     ( )
y a
b

,

или, в альтернативной записи,

ˆ
argmin ( )
y
T y

, где 

2

0

1
1
( )

2

a

T
y
dx
y
y
g





,

(0)
0
y

,     ( )
y a
b

.

Замечание. В формулировке задачи о брахистохроне используется сокра
щение inf (от лат. infimum – низший). Если в вариационной задаче требуется 
искать кривую, на которой достигается максимум, то вместо inf пишут sup (сокращение от лат. supremum – высший). В альтернативной постановке, argmin –
это сокращение от «аргумент минимума»

Решением задачи о брахистохроне является дуга вертикальной циклоиды

с точкой возврата в точке А. Вспомним, что циклоида (рис. 2) – это плоская 
кривая, заданная траекторией движения точки, закрепленной на ободе движущегося колеса. Аналитически циклоиду можно задать с помощью пары параметрических уравнений:

( )
sin ),

( )
(
(
1
cos ).

x t
r t
t

y t
r
t









Рис. 2. Циклоида.

Брахистохроны применяют при проектировании трамплинов, аттракцио
нов, технологических спусков и так далее.

Задача о наибольшей площади. Среди всех плоских кривых, имеющих 

данную длину l и оканчивающихся в точках A(a,0) и B(b,0) найти кривую y(x), 
ограничивающую вместе с отрезком [a, b] наибольшую площадь (рис. 3).

В современной формулировке:

( )
inf,

b

a y x dx 


2
( )
0,
( )
0,    
1
.
( )

b

a
y a
y b
y
x dx
l







или, в альтернативной записи,

ˆ
argmax ( )
y
F y

, где 
( )
( )

b

a
F y
y x dx

,

2
( )
0,
( )
0,    
1
.
( )

b

a
y a
y b
y
x dx
l







Задачу о наибольшей площади еще называют изопериметрической за
дачей (задачей постоянного периметра) или задачей Дидоны, по мотивам известного исторического мифа об основании Карфагена его первой царицей –
Дидоной.

Рис. 3. Дуги окружности – решения задачи о наибольшей площади.

С методами вариационного исчисления познакомимся на примере реше
ния простейшей задачи вариационного исчисления (ПЗВИ).

Простейшая задача классического вариационного исчисления.

Постановка задачи:

( )
( , ( ),
( ))
extr,

b

a
J y
f x y x y x dx




(1)

( )
,
( )
,
y a
A
y b
B


(2)

где ( , , )
f x y y – функция от трех переменных, называемая интегрантом;

extr2 – обозначает inf или sup;
отрезок a
b
x


предполагается фиксированным и конечным;

выражение ( )
( , ( ),
( ))

b

a
J y
f x y x y x dx


называется функционалом.

Любой функционал, по существу, является функцией от функций, так как 

для любой подходящей функции однозначно определяет число – значение функционала на этой функции.

Вспомним, что на произвольном отрезке [a, b] выделяют следующие спе
циальные множества функций, образующие линейные функциональные пространства (то есть множества функций, замкнутые относительно сложения и 
умножения на число):  

C[a, b] – непрерывные функции;

C1[a, b] – непрерывно дифференцируемые или гладкие;

KC[a, b] – кусочно-непрерывные; 

KC1[a, b] – кусочно-непрерывно дифференцируемые (см. рис. 5).

2 extr – от лат. extremum, обозначает экстремальное, то есть наибольшее или наименьшее значение. 

Для запоминания этих обозначений удобно пользоваться следующими 

мнемоническими3 правилами:

1) С – сокращение от англ. “continuous”, непрерывный; 
2) К – сокращение от «кусочно»; 
3) верхний индекс показывает порядок производной, до которого, вклю
чительно, применимо указанная комбинация свойств.

Эти же соглашения обобщаются и на обозначения других классов функ
ций, так, например, C2[a, b] обозначает класс дважды непрерывно дифференцируемых функций, то есть функций, имеющих непрерывные производные до 
второго порядка включительно.

Рис. 5. Кусочно-непрерывно дифференцируемая (кусочно гладкая) функция – это функция, 

которая сама является непрерывной и имеет производную, которая кусочно-непрерывна.
На рисунке «зеленая» функция – кусочно-непрерывна, а «красная» и «синяя» – кусочно 

гладкие («изломы» на их графиках свидетельствуют о скачках их производных).

В ПЗВИ, экстремум функционала J ищется среди непрерывно дифферен
цируемых функций y ∈ C1[a, b], удовлетворяющих краевым условиям

0
0
( )
y x
y

, 
1
1
( )
y x
y

.

В общем случае, функции, удовлетворяющие ограничениям заданной ва
риационной задачи, называются допустимыми.

В пространствах C[a, b] и C1[a, b] будем рассматривать нормы4 || ||C
y
и 

1
||
||C
y
, соответственно:

|| || : max
| ( )|
C
a x b
y
y x
 


3 Мнемоническое правило, здесь – правило, необязательно учитывающее реальное происхождение термина 
или сокращения, но удобное для запоминания.
4 Норма функции, по сути, это функционал со специальными свойствами, такими как линейность и неравенство треугольника. Интегральные функционалы, такие как в постановке задачи ПЗВИ, уже являются линейными в силу свойства линейности интеграла.

1
||
|| : max{||
|| ,||
|| }
C
C
C
y
y
y

.

Замечание. Функция y, определенная на отрезке [a, b], может рассматри
ваться как бесконечномерный вектор, с таким же количеством отдельных компонент, сколько существует точек на отрезке [a, b], причем каждая компонента 
индексируется какой-то точкой x отрезка. Для функций традиционно использовать запись x-ой компоненты, как y(x), а не yx, как для векторов:

(
, ( ),
)
x b
a
y
y x
 
 

.

Сложение и умножение функций на число выполняются покомпонентно, так 
же, как и соответствующие операции для векторов. Норма бесконечномерного 
вектора-функции играет роль модуля конечномерного вектора.

Пример. Для функции 

1
sin3
[0,2 ]
y
x
C



имеет место (см. рис. 4):

0
2
||
||
max |sin3 | 1
C
x
y
x


 

 ;

0
2
0
2
0
2
||
||
max |3cos3 |
max 3 | cos3 | 3 max | cos3 | 3 1
3
C
x
x
x
y
x
x
x




 
 
 




 
   ;

1
||
||
max{||
|| ,||
|| }
max{1,3}
3
C
C
C
y
y
y


 .

Рис. 4. Графики функции 
sin3
y
x

и 
3cos3
y
x
 
.

Определение. Допустимая функция ˆy доставляет функционалу J(y) сла
бый локальный минимум (записывается ˆy
wlocmin

– от англ. weak local min
imum), если существует 
0
 
такое, что

ˆ
( )
( )
J y
J y


для любой допустимой функции y такой, что 
1
ˆ
||
||C
y
y



.