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

МИНИСТЕРСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ДЕЛАМ ГРАЖДАНСКОЙ

ОБОРОНЫ, ЧРЕЗВЫЧАЙНЫМ СИТУАЦИЯМ И ЛИКВИДАЦИИ ПОСЛЕДСТВИЙ

СТИХИЙНЫХ БЕДСТВИЙ

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

ГПС МЧС РОССИИ

С.В. Бабенышев, Е.Н. Матеров

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

Допущено Министерством Российской Федерации по делам гражданской обороны, 
чрезвычайным ситуациям и ликвидации последствий стихийных бедствий в качестве учебного пособия для курсантов, студентов и слушателей образовательных 

организаций МЧС России

Железногорск

2019

УДК 517.97, 519.85
ББК 22.161.8

Б 12 

Авторы:

Бабенышев Сергей Валерьевич,

кандидат физико-математических наук

Матеров Евгений Николаевич,

кандидат физико-математических наук

Рецензенты:

Сатин А.П., кандидат технических наук, доцент

(ФГБОУ Академия ГПС МЧС России)

Ефимов С.В., кандидат технических наук
(Воронежский институт ГПС МЧС России)

Бабенышев С.В. Методы оптимизации. [Текст]: учебное пособие / 

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

В пособии приведены необходимые теоретические сведения и 

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

УДК 517.97, 
519.85
ББК 22.161.8

© ФГБОУ ВО Сибирская пожарно-спасательная академия ГПС МЧС России, 2019
© Бабенышев С.В., Матеров Е.Н., 2019

ОГЛАВЛЕНИЕ 

ВВЕДЕНИЕ ........................................................................................................................5 

РАЗДЕЛ 1. ВАРИАЦИОННОЕ ИСЧИСЛЕНИЕ И ОПТИМАЛЬНОЕ УПРАВЛЕНИЕ
..............................................................................................................................................6 

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

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

Вопрос 2. Понятие вариации..........................................................................14 

Вопрос 3. Условия существования экстремума функционала....................16 

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

Вопрос 1. Постановка задачи оптимального управления ...........................25 

Вопрос 2. Принцип оптимальности и принцип максимума Понтрягина...31 

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

Вопрос 1. Задачи динамического программирования .................................38 

Вопрос 2. Принцип поэтапного построения оптимального уравнения .....40 

Вопрос 3. Уравнение Беллмана......................................................................41 

Вопрос 4. Динамическое программирование и  принцип максимума 

Понтрягина .................................................................................62 

Вопрос 5. Дискретизация задачи оптимального управления......................65 

РАЗДЕЛ 2. УСЛОВНАЯ И БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ................................69 

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

Вопрос 1. Выпуклые множества и функции.................................................69 

Вопрос 2. Задача выпуклого программирования .........................................74 

Вопрос 3. Функция Лагранжа для задачи выпуклого программирования 75 

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

Вопрос 1. Постановка задачи безусловной оптимизации ...........................80 

Вопрос 2. Методы локальной безусловной оптимизации...........................83 

РАЗДЕЛ 3. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ ....................................................93 

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

Вопрос 1. Задачи с линейными целевыми функциям и ограничениями ...93 

Вопрос 2. Постановка задачи линейного программирования.....................94 

Вопрос 3. Различные постановки задачи линейного программирования..96 

Вопрос 4. Симплекс-метод...........................................................................104 

Вопрос 5. Двойственная задача линейного программирования...............109 

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

Вопрос 1. Постановка транспортной задачи ..............................................114 

Вопрос 2. Методы построения первоначального опорного плана ...........117 

Вопрос 3. Метод потенциалов .....................................................................119 

Заключение.....................................................................................................................132 

Список используемых сокращений..............................................................................133 

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

ВВЕДЕНИЕ

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

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

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

Структурно пособие разделено на три раздела: «Вариационное ис
числение и оптимальное управление», «Условная и безусловная оптимизация» и «Линейное программирование». Каждый раздел делится на логически взаимосвязанные темы, хотя существуют идеи и подходы, общие для тем из различных разделов. Так, например, в Теме 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 Брахистохрона (от греч. βραχιστοζ (брахистос) – кратчайший, χρονοζ (хронос) – время) – кривая 
наискорейшего спуска.

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

2

2

mv
mgh
mgy



получаем ( )
2
( )
v x
g y x


.

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

2
1
,
y dx
dl
v
dt
dt






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

Приравнивая выражения для 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








.

Задача состоит в нахождении функции ŷ = ŷ(x), дающей минималь
ное значение для выражения T(y), называемого, в общем случае, функционалом2.

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

2

0

1
1
inf,

2

a
y
dx
y
g






y(0) = 0, y(a) = b,

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

ŷ = argmin T(y), где

2

0

1
1
( )

2

a

T
y
dx
y
y
g





,

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

2 Функционал, неформально можно понимать, как функцию от функций, то есть некий способ по заданной функции получить, связанное с ней, некоторое числовое значение.

Замечание. В формулировке задачи о брахистохроне используется 

сокращение 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 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 – функция от трех переменных, называемая интегрантом;

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

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

b

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

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

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

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

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

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

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

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

включительно, применима указанная комбинация свойств.

Эти же соглашения обобщаются и на обозначения других классов 

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

Рис. 5. Кусочно-непрерывно дифференцируемая (кусочно гладкая) функция – это 
функция, которая сама является непрерывной и имеет производную, которая кусочно-непрерывна. На рисунке «зеленая» (1) функция – кусочно-непрерывна, а
«красная» (2) и «синяя» (3) – кусочно гладкие («изломы» на их графиках свидетельствуют о скачках их производных).

4 Мнемоническое правило, здесь – правило, необязательно учитывающее реальное происхождение 
термина или сокращения, но удобное для запоминания.

(1)

(2)

(3)

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

y(x0) = y0,    y(x1) = y1.

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

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

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

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

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

Замечание. Функция y(x), определенная на отрезке [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


 .

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

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

Определение. Допустимая функция ŷ доставляет функционалу 

J(y) слабый локальный минимум (записывается ŷ ∈ wlocmin – от англ. 
weak local minimum), если существует δ > 0 такое, что

J(y) ≥ J(ŷ)

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

Аналогично определяется понятие слабого локального макси
мума (пишется ŷ ∈ wlocmax – от англ. weak local maximum).

Определение. Допустимая функция ŷ доставляет слабый глобаль
ный минимум (ŷ ∈ wabsmin – от англ. weak absolute minimum), если

J(y) ≥ J(ŷ)

для любой допустимой функции y.

Аналогично определяют слабый глобальный максимум (обозна
чается ŷ ∈ wabsmax – от англ. weak absolute maximum).

Если в качестве допустимого множества брать множество ку
сочно-непрерывно дифференцируемых функций KC1[a, b], с нормой 
|| ||C
y
, то говорят, что задача (1)-(2) даётся в сильной постановке. Соот
ветственно, тогда говорят о сильном локальных минимуме (ŷ ∈ slocmin) 
и максимуме (ŷ ∈ slocmax – от англ. strong local maximum) и сильном 
глобальном минимуме (ŷ ∈ sabsmin) и максимуме (ŷ ∈ sabsmax).

Сведем особенности введенных определений в одну таблицу: