Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 2011
ПРЕДИСЛОВИЕ
Нелинейное программирование является одним из разделов математического программирования и представляет интерес не только для студентов, обучающихся по специальности «Прикладная математика и информатика» и практикующихся в области прикладной математики, но и для специалистов, работающих в данной области.
Данная книга является логическим продолжением предыдущего учебного пособия «Линейное программирование в современных задачах оптимизации» и представляет собой результат многолетнего преподавания курса «Математическое программирование» на кафедре «Математическое обеспечение систем» в НИЯУ МИФИ.
Помимо теоретических положений данное пособие содержит большое количество многоплановых примеров решения задач нелинейного программирования, связанных с вопросами поиска экстремума, что дает студентам возможность оценить многообразие областей применения принципов нелинейного программирования.
Авторы выражают искреннюю благодарность дипломникам и аспирантам кафедры «Математическое обеспечение систем»: Бушину С.В., Зубкову Д.А., Лихачевой Е.В., Вахромееву П.В, Болицевич Ю.А., осуществивших программную реализацию прикладных задач, приведенных в главе 2.
6
ОСНОВНЫЕ ОБОЗНАЧЕНИЯ И ПОНЯТИЯ
Здесь приведен ряд общепринятых обозначений и понятий, используемых при рассмотрении материала последующих глав.
1. Пусть x и y – n -мерные векторы
x |
|
y |
|
|
||
|
1 |
|
|
1 |
|
, |
x = |
|
|
, y = |
|
|
|
|
|
|
|
|
|
|
xn |
|
yn |
|
|
||
|
|
x т |
= (x , …, x |
n |
) |
– транспонированный вектор, |
||||||||||||
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
|
тогда < x, y >= x т y = ∑xi yi – скалярное произведение векторов x |
||||||||||||||||||
и y . |
|
|
|
|
|
|
|
i=1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
… a |
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
11 |
|
|
1n |
|
|
|
|
|
|
|
|
|
|
|
||
2. |
A = |
… … … |
– матрица размерности m ×n . |
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
am1 |
… amn |
|
|
|
|
|
|
|
|
|
|
||||||
3. |
f (x) = f (x1 , …, x1n ) |
– функция n переменных. |
||||||||||||||||
Функция f (x) |
имеет 1-ю и 2-ю непрерывные производные на |
|||||||||||||||||
множестве D в n-мерном пространстве Rn . |
|
|
|
|
|
|
||||||||||||
Пусть некоторая точка |
x 0 D . Тогда |
f (x) может быть пред- |
||||||||||||||||
ставлена в виде ряда Тейлора относительно этой точки: |
||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
n |
∂f |
|
(xi − xi0 ) + |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
f (x1 , …, xn ) = f (x10 , …, xn 0 ) + ∑ |
∂x |
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
i=1 |
|
x0 |
|||||
|
|
1 |
n |
n |
∂ |
2 |
f |
|
|
|
|
|||||||
|
|
|
|
(xi − xi0 )(x j − x0j ) + 0( |
|
x − x 0 |
|
2 ) . |
||||||||||
|
+ |
∑ ∑ |
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|||||||||||
|
|
2 i=1 j=1 ∂xi ∂x j |
x |
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
0 |
|
∂f |
|
∂f |
|
∂f |
т |
|
|||
4. f (x |
|
, |
, …, |
|
– градиент функции в точке |
|||||||
|
∂x |
∂x |
|
∂x |
|
|||||||
|
) = |
2 |
|
|
||||||||
|
|
|
1 |
|
|
|
|
n |
x |
|||
|
|
|
|
|
|
|
|
|
|
|
0 |
|
x 0 D . |
|
|
|
|
|
|
|
|
|
|
|
|
Градиент – это вектор, который направлен в сторону наискорейшего роста функции и ортогонален в точке х0 к поверхности
(или линии) уровня |
f (x) = const (рис. O.1). |
x2 |
линии |
|
уровня |
max
f(x)
x1
Рис. O.1. Линии уровня f (x) = const для функции двух переменных
|
|
∂2 |
f |
|
… |
∂2 |
f |
|
|
|
|
∂x ∂x |
|
∂x ∂x |
|
|
|||
|
|
|
|
|
|
||||
|
1 |
1 |
|
|
1 |
n |
|
|
|
5. H (x 0 ) = |
… |
|
… |
… |
|
– вещественная симметричная |
|||
|
|
∂2 |
f |
|
… |
∂2 |
f |
|
|
|
∂x ∂x |
|
∂x ∂x |
|
|
||||
|
|
|
|
|
|||||
|
|
n |
1 |
|
|
n |
n |
|
|
матрица (матрица Гессе).
Важность градиента и матрицы Гессе определяется их использованием во многих алгоритмах поиска экстремума функций.
Можно записать
f (x) = f (x 0 )+ < f (x 0 ), (x − x 0 ) > + |
1 |
< (x − x 0 ), |
|
2 |
|||
|
|
H (x0 )(x − x0 ) > +0(
x − x0 
2 ) .
8
6. Пусть
|
a |
|
x |
|
+ a |
|
x |
2 |
|
|
11 1 |
|
|
12 |
|
||||
a21x1 + a22 x2 |
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
x |
|
+ a |
i2 |
x |
2 |
|
|
|
i1 1 |
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
+ a |
|
|
x |
|
|
a |
m1 |
m2 |
2 |
||||||
|
1 |
|
|
|
|||||
+…+ a1 j x j +…+ a1n xn = b1;
+…+ a2 j x j +…+ a2n xn = b2 ;
…
+…+ aij x j +…+ ain xn = bi ;
…
+…+ anj x j +…+ amn xn = bm .
– система линейных уравнений в скалярном виде, тогда Ax = b – система уравнений в матричной форме, где A – матрица коэффи-
циентов aij (i =1, …, m; j =1, …, n), b – m -мерный вектор. Система линейных уравнений называется совместной, если она
имеет хотя бы одно решение.
Пусть r – ранг матрицы и представляет собой наибольший порядок отличного от нуля определителя матрицы A (число линейно независимых столбцов матрицы A ).
r ( A) = r ( Ab ) – необходимое и достаточное условие совместности системы линейных уравнений, т.е. ранг матрицы A должен быть равен рангу распределенной матрицы системы.
Ранг не превосходит числа неизвестных n , r ≤ n . Тогда:
если r = n , то решение системы единственно;
если r < n , то система имеет бесчисленное множество решений.
7. a0 + a1 x1 +…+ an xn ≥ 0 – линейное неравенство. Совокупность точек пространства, координаты которых удовле-
творяют этому неравенству, представляют собой полупространство; совокупность нескольких линейных неравенств определяет область решения, представляющую собой выпуклый многогранник.
8. Общая задача математического программирования формулируется так:
найти максимум (минимум) функции f (x) при ограничениях
gi (x1 , …, x j , …, xn ) ≤ bi , i = |
1, m |
; |
(O.1) |
||
x j ≥ 0 , j = |
|
. |
(O.2) |
||
1, n |
|||||
9 |
|
|
|
|
|
При этом:
функция f (x) называется целевой функцией;
система неравенств (O.1) и условия неотрицательности переменных (O.2) называются системой ограничений задачи;
всякое решение задачи с учетом системы ограничений, т.е. совокупность значений переменных x1 , …, xn , удовлетворяющих ус-
ловиям (O.1) и (О.2), называется допустимым решением; совокупность точек n -мерного пространства, удовлетворяющих
системе ограничений, образует так называемую допустимую область;
допустимое решение, максимизирующее (минимизирующее) целевую функцию, называется оптимальным.
Итак, задача математического программирования заключается в нахождении оптимального решения, обеспечивающего максимальное (минимальное) значение целевой функции с учетом системы ограничений на переменные.
Замечания. Постановка задачи математического программирования является достаточно общей. Если какая-то практическая задача, на первый взгляд, кажется иной, то, как правило, с помощью простых математических преобразований её можно свести к задаче рассматриваемого вида.
1. Если требуется найти минимум функции f (x) , то это эквивалентно
поиску максимума функции − f (x ) , т.е. min f (x) = −max [− f (x)] . |
|
x |
x |
2. Если заданны неравенства вида
g(x) ≥ b ,
то простой переменой знака можно прийти к виду (О.1), а именно
−g(x) ≤ −b .
3.Если на переменные x j не наложено условие неотрицательности, а заданно ограничение
xj ≥ xj _ min ,
то, вводя замену переменных
,
получаем для новой переменной условие (О.1), т.е. x′j ≥ 0 .
10