- •1. ОСНОВНЫЕ ПОНЯТИЯ
- •2.1. Формализация геометрической задачи
- •2.2. Аппроксимация экспериментальных данных
- •2.3. Выбор места расположения управляющей вычислительной машины на производстве
- •2.4. Выбор места расположения УВМ в производственном здании
- •2.5. Определение оптимальных настроек АСР
- •2.6. Распределение нагрузки между параллельными агрегатами
- •2.7. Оптимизация температурного режима реактора периодического действия
- •3. ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ И АНАЛИЗА
- •3.1. Общие сведения о множествах
- •Рис.2. Графическое представление операций над множествами
- •3.2. Евклидово пространство
- •3.3. Функция нескольких переменных и ее свойства
- •4. ПОСТАНОВКА ЗАДАЧИ ОПТИМИЗАЦИИ В ЕВКЛИДОВОМ ПРОСТРАНСТВЕ. УСЛОВИЯ ОПТИМАЛЬНОСТИ
- •4.1. Целевая функция. Локальный и глобальный оптимумы
- •4.2. Разрешимость задачи оптимизации
- •4.3. Задачи оптимизации без ограничений
- •4.4. Задачи оптимизации с ограничениями типа равенств. Метод неопределенных множителей Лагранжа
- •4.5. Задачи с ограничениями типа неравенств
- •5. ВЫПУКЛЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ
- •5.1. Постановка задачи
- •5.2. Условия оптимальности в выпуклых задачах
- •6. МЕТОДЫ РЕШЕНИЯ ОПТИМАЛЬНОЙ ЗАДАЧИ ДЛЯ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ
- •6.1. Необходимые и достаточные условия экстремума функции одной переменной
- •6.2. Алгоритм аналитического метода
- •7. ИТЕРАЦИОННЫЕ МЕТОДЫ ОПТИМИЗАЦИИ
- •7.1. Алгоритм итерационного метода
- •7.2. Метод сканирования
- •7.3. Определение унимодальной функции
- •7.4. Метод дихотомии
- •7.5. Метод золотого сечения
- •7.6. Одномерный градиент
- •7.7. Методы полиномиальной аппроксимации
- •7.8. Метод Пауэлла
- •7.9. Метод ДСК
- •7.10. Метод квадратичной интерполяции
- •7.11. Метод кубической аппроксимации
- •7.12. Метод Фибоначчи
- •7.14. Методы поиска безусловного экстремума невыпуклых функций
- •7.15. Метод тяжелого шарика
- •8. ЗАДАНИЯ
- •8.1. Исследование функции на выпуклость (вогнутость)
- •8.2. Варианты задач безусловной оптимизации
- •8.3. Варианты задач условной оптимизации
- •9. КОНТРОЛЬНЫЕ ВОПРОСЫ
- •10. ЛИТЕРАТУРА
4.4. Задачи оптимизации с ограничениями типа равенств. Метод неопределенных множителей Лагранжа
Рассмотрим теперь задачу на условный экстремум. Как показано в п.4.З, решение задачи об отыскании экстремумов функции n переменных
f (x), x = (x1, x2 ,...,m) Rn
может быть сведено с помощью необходимых условий к решению системы уравнений (4.5), в результате чего определяются стационарные точки функции f (x). Оказывается, что аналогичное сведение возможно и для задачи отыскания экстремумов функции f (x) при наличии ограничений типа равенств (уравнений связи):
gi (x) = 0, i =1,2,..., m. |
(4.6) |
Уточним, что именно мы будем понимать под решением задачи на условный экстремум.
Обозначим
D = {x Rn gi (x) = 0, i =1,2,...,m}
и предположим, что функции gi(x), i = 1,2,…,m имеют непрерывные частные производные по всем аргументам до второго порядка включительно в некоторой области G, содержащей множество D.
Говорят, что точка х0 доставляет условный локальный минимум (строгий условный локальный минимум) функции f (x), если ε > 0 такое, что для любого x D∩U(x0,ε) выполняется f(x) > f(x0). Для строгого локального минимума − f (x) ≥ f (x0 ) .
Пусть х0 – некоторая точка множества D, и ранг матрицы Якоби, рассматриваемой в точке х0 для функций gi(x), i = 1,2,…,m, равен m. Не нарушая общности, будем считать, что отличен от нуля определитель (якобиан), составленный из частных производных по первым m аргументам, т.е.
38
|
∂g1 |
... |
∂g1 |
|
|
|
||||
|
|
|
|
|||||||
|
|
|
|
|
|
|
||||
|
∂x |
∂x |
m |
|
|
|||||
1 |
|
|
|
|
≠ 0 . |
(4.7) |
||||
................. |
|
|||||||||
∂gm |
... |
|
∂gm |
|
|
|||||
|
|
|
|
|||||||
∂x |
|
∂x |
m |
|
|
|||||
1 |
|
|
|
|
|
|
|
Тогда по теореме о неявных функциях в некоторой окрестности точки х0 система уравнений (4.6) разрешима относительно переменных х1,х2,...,xm, т.е. представима в виде
xi =ϕi (xm+1, xm+2 ,..., xn ), i =1,2,..., m, |
(4.8) |
где ϕi (xm+1, xm+2 ,..., xn ), i =1,2,..., m, – непрерывно дифференцируемые в рассматриваемой окрестности функции.
Переменные хm+1,хm+2,...,xn естественно назвать "независимыми", в отличие oт "зависимых" – х1,х2,...,xm.
Подставляя выражения (4.8) в f (х), получим задачу отыскания безусловного экстремума функции n–m переменных
f(ϕ1(xm+1,..., xn ),...,ϕm (xm+1,..., xn ), xm+1,..., xn ) =
=h(xm+1,..., xn ),
Осуществить представление (4.8) удается не всегда. Рассмотрим метод, который не предполагает наличие явных выражений типа (4.8). Он известен как метод неопределенных множителей Лагранжа.
Как было отмечено в замечании к теореме 4.1, в точке х0, доставляющей безусловный экстремум функции f, ее полный дифференциал равен нулю, т.е.
n |
∂f (x |
0 |
) |
|
df (x0 ) = ∑ |
|
dxj = 0. |
||
∂x j |
|
|
||
j =1 |
|
|
|
Выделив переменные х1,х2,...,xm, можно этому равенству придать
вид
m |
∂f (x |
0 |
) |
|
n |
∂f (x |
0 |
) |
|
|
∑ |
|
dxj + |
∑ |
|
∂xk = 0. |
(4.9) |
||||
∂xj |
|
|
∂xk |
|
|
|||||
j =1 |
|
|
|
k =m+1 |
|
|
|
|
По условию функции gi(x) имеют непрерывные частные производ-
39
ные, поэтому, продифференцировав обе части равенства (4.6), получим
|
dgi (x0 ) = 0, |
i =1,2,...,m, |
|
||||||||
или |
|
|
|
|
|
|
|
|
|
|
|
m |
∂gi (x |
0 |
) |
|
n |
|
∂gi (x |
0 |
) |
|
|
∑ |
|
dxj + |
∑ |
|
|
dxk = 0. |
(4.10) |
||||
∂x j |
|
|
|
|
|
||||||
j =1 |
|
|
|
k =m+1 ∂xk |
|
|
|
|
i = 1,2,...,m.
Сложив почленно с равенством (4.9) равенства (4.10), умноженные на произвольные множители λi, i = 1,2,…,m получим
m |
∂f (x0 ) |
m |
∂g |
(x0 ) |
n |
∂f (x0 ) m |
∂g |
(x0 ) |
|
||||||||||||||
|
|
|
+ ∑λi |
i |
|
|
|
|
|
|
+ ∑ |
|
|
|
|
+ ∑λi |
i |
|
|
|
(4.11) |
||
∑ |
∂x |
j |
∂x |
j |
|
dxj |
|
|
∂x |
|
∂x |
k |
dxk = 0. |
||||||||||
j =1 |
|
i=1 |
|
|
|
|
|
k =m+1 |
k |
|
i=1 |
|
|
|
|
||||||||
|
Распорядимся множителями |
λi , i =1,2,..., m, таким образом, что- |
|||||||||||||||||||||
бы обратились в нуль коэффициенты при |
dx1, dx2,..., dxm, |
|
|
||||||||||||||||||||
|
|
|
|
∂f (x |
0 |
) |
|
|
m |
∂gi (x |
0 |
) |
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
+ ∑λi |
|
|
= 0, |
j =1,2,...,m. |
|
|
(4.12) |
||||||||||
|
|
|
|
|
∂x j |
|
|
|
|
∂x j |
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
Это возможно сделать, так как уравнения (4.12) образуют систему линейных алгебраических уравнений относительно λi, i = 1,2,…,m, которая имеет единственное решение в силу того, что ее определитель (4.7) по условию отличен от нуля.
Пусть λi0, i = 1,2,…,m – требуемые значения множителей λi. Тогда равенство (4.11) примет вид
n |
|
∂f (x0 ) |
m |
∂g |
(x0 ) |
|
|
|
|
0 |
i |
|
|
∑ |
|
∂xk |
+ ∑λi |
∂xk |
dxk = 0, |
|
k =m+1 |
|
i=1 |
|
из которого следует, что коэффициенты при dxk, k = m + 1,…,n быть нулями, т.е.
∂f (x0 ) |
m |
∂g (x0 ) |
|
|
|
+ ∑λ0i |
i |
|
= 0, k = m +1, ..., n. |
∂x |
∂x |
|
||
k |
i=1 |
|
k |
|
должны
(4.13)
40
Таким образом, если x0 = (x10 , x20 ,..., xn0 ) – точка экстремума функции f (x) при ограничениях (4.6), то координаты этой точки x10 , x20 ,..., xn0 вме-
сте с λ10 , λ02 ,..., λ0m являются решением системы n+m уравнений относительно неизвестных x1, x2 ,..., xn , λ1 , λ2 ,..., λm :
g |
(x) = 0, |
|
|
|
|
|
|
|
i =1,2,...,m |
|||||
|
|
i |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∂f (x) |
|
m |
∂g |
(x) |
|
|
|||||||
|
|
|
|
|
|
+∑λ0i |
|
i |
|
|
|
= 0, |
j =1,2,...,m |
|
|
|
∂x j |
|
∂x j |
||||||||||
|
|
|
|
i=1 |
|
|
|
|||||||
|
|
∂f (x) |
|
m |
|
∂g |
(x) |
|
|
|||||
|
|
|
|
|
|
+ |
∑λ0i |
|
i |
|
|
|
= 0, |
k = m +1,...,n |
|
|
∂x |
|
|
|
∂x |
|
|
||||||
|
|
|
k |
|
i=1 |
|
k |
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
Этот результат представляет собой основное содержание метода множителей Лагранжа. Он позволяет свести задачу условной оптимизации к безусловной оптимизации, решение которой находится из необходимых условий существования экстремума функции. Метод состоит из следующих этапов:
1)составляется функция n+m переменных, которая называется функцией Лагранжа:
m |
|
L(x,λ) = f (x) + ∑λi gi (x); |
(4.14) |
i=1
2)находятся и приравниваются нулю частные производные по xj и λi функции (4.14):
|
|
∂L |
|
∂f (x) |
m |
∂gi (x) |
|
|
||
|
|
= |
+ ∑λi |
= 0, j =1,2,..., n, |
|
|||||
|
∂xj |
∂x j |
|
|
||||||
|
|
|
i=1 |
∂xj |
|
|||||
|
∂L |
|
|
|
|
|
|
(4.15) |
||
|
= gi (x) = 0, |
|
i =1,2,...,m; |
|||||||
|
|
|
||||||||
|
∂λ |
j |
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
3) решается система (4.15) n+m уравнений относительно n+m не-
известных x1, x2 ,..., xn , λ1 , λ2 ,..., λm .
41
Система уравнений (4.15) представляет собой необходимые условия экстремума в задаче с ограничениями типа равенств.
Как и в случае задач на безусловный экстремум условия (4.15) по-
зволяют выделить точки x1k , x2k ,..., xnk из множества D, в которых функция может достигать экстремума. Их принято называть условностационарными точками функции f.
Для выяснения характера условно-стационарной точки следует обратиться к достаточным условиям существования условного экстремума, они аналогичны достаточным условиям безусловного экстремума, приведенным в теореме 4.3.
Пример 4:
Спроектировать закрытую емкость заданного объема V в форме прямоугольного параллелепипеда (рис. 6):
1)из условия минимального расхода материала;
2)из условия минимальной суммарной длины сварного шва;
h
b
a
Рис.6. Прямоугольный параллелепипед объема V
1) Расход материала определяется площадью боковой поверхности параллепипеда S. Емкость будем изготавливать из железного листа, развертка емкости представлена на рисунке 7:
S = 2a b + 2a h + 2b h .
Объем бака:
V = a b h .
Математическая модель задачи условной оптимизации:
42
S = 2a b + 2a h + 2b h → min
при условии
a b h −V = 0 − уравнение связи
a,b, h > 0
Составим функцию Лагранжа
L = 2a b +2a h +2b h +λ(a b h −V ) → mina,b,h > 0
(4.16)
(4.17)
Ошибка! |
b |
|
|
a |
b |
a |
b |
|
|
|
h |
Рис.7. Прямоугольный параллелепипед в развертке
Решение:
Задача (4.17) относится к задаче безусловной оптимизации и может быть решена из необходимых условий существования экстремума функции:
∂∂La = 2b + 2h + λbh = 0
∂∂Lb = 2a + 2h + λah = 0
∂L = 2a + 2b + λab = 0∂h
∂L
∂λ = a b h −V = 0
Выразим из первого уравнения системы:
43
λ = − |
2b + 2h |
(4.18) |
|
bh |
|||
|
|
Подставим λ во второе уравнение системы
2a + 2h − (2b + 2h) a h = 0 b h
Помножим на b, получим
2a b + 2h b − 2a b − 2a h = 0
2h b = 2a h b = a
Подставим (4.18) в третье уравнение системы, и получим:
2a + 2b − (2b + 2h) a b = 0 b h
Умножим левую и правую части на h.
2a h + 2b h − 2b a − 2a h = 0 2b h = 2b a
Получаем a = h.
Следовательно, чтобы минимизировать площадь боковой поверхности, емкость следует изготовлять в виде куба (a = b = h).
Найдем размер стороны куба из четвертого уравнения системы:
a3 =V , |
a = 3 V |
||||
λ = |
− 4a |
= − |
4 |
|
|
a2 |
a |
||||
|
|
Теперь решим задачу методом исключения неизвестных. Выразим h из уравнения связи и подставим в целевую функцию:
|
|
h |
= |
V |
|
|
|
|
|
||
|
|
ab |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|||
|
V |
+ 2b |
V |
|
= 2ab + 2 |
V |
|
V |
|
||
S = 2ab + 2a |
|
|
|
b |
+ 2 |
a |
→ min |
||||
ab |
ab |
||||||||||
|
|
|
|
|
|
||||||
a,b > 0 |
|
|
|
|
|
|
|
|
|
|
Получили задачу безусловной оптимизации. Из необходимых условий существования экстремума имеем:
44
∂S |
= 2b + |
2V |
|
= 0 b = |
V |
|||
|
|
|
|
|
|
|
||
∂a |
a |
2 |
a |
2 |
||||
|
|
|
|
|
|
|||
|
∂S |
|
2V |
|
|
|
|
|
|
= 2a + |
|
= 0 |
|
|
|||
|
|
2 |
|
|
|
|||
|
∂b |
|
b |
|
|
|
|
|
|
|
|
|
|
|
|
Подставим b во 2-е уравнение системы:
2a − 2VVa2 4 = 2a − 2Va4 = 0
2a(1 − a3 ) = 0
V
I. a = 0 b = 0 h = 0
Эта стационарная точка не удовлетворяет уравнению связи.
II. |
a3 |
=1 a = 3 V ; |
|
||||||
V |
|
|
|||||||
|
b = |
|
|
|
V |
|
= 3 V ; |
|
|
|
3 |
|
|
||||||
|
|
|
V 2 |
|
|||||
|
h = |
V |
= 3 V |
a, т=тb. = h |
|||||
|
|
||||||||
|
|
|
3 |
V 2 |
|
Из достаточных условий определим характер экстремума:
|
|
|
|
∂2 S |
|
∂2 S |
|
4V |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∂ 2 |
|
|
|
|
3 |
|||||
Г |
= |
|
|
∂a∂b |
= a |
||||||||
|
|
a |
|
∂2 S |
|
|
|||||||
|
|
|
∂2 S |
|
|
2 |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
∂b∂a |
|
∂b2 |
|||||||||
|
|
|
|
|
|
|
|
После подстановки стационарных точек:
4 |
2 |
||
|
|
|
|
Г = |
2 |
4 |
|
|
|
2
4V b3
M1 = 4 > 0
M2 = 16 − 4 = 12 >0
Следственно, по критерию Сильвестра стационарная точка доставляет минимальное значение целевой функции S.
2) На рисунке 7 сварной шов выделен темной линией. Обозначим суммарную длину сварного шва R. Математическая модель задачи условной оптимизации:
45
R = 2a + 4b + h → mina b h −V = 0
a,b,h > 0
Составим функцию Лагранжа, получим задачу безусловной оптимизации:
L = 2a + 4b + h + λ(a b h −V ) → mina,b, h > 0
Решение:
Запишем необходимые условия (4.15):
∂∂La = 2 + λbh = 0
∂∂Lb = 4 + λah = 0∂L
∂h =1 + λab = 0∂L
∂λ = a b h −V = 0
Выразим из третьего уравнения системы:
λ = − ab1
Подставим λ в первое уравнение системы:
2 − bhab = 0
или, после умножения на a:
2a = h |
a = |
h |
|
||
|
2 |
Подставим λ во второе уравнение системы:
4 − ahab = 0
После умножения на b, получим:
46