Материал: Бородакий Нелинейное программирование в современных задачах оптимизации 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

 

 

 

 

 
x′j = xj − xj _ min

При этом:

функция 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

Источник: https://studfile.net/preview/16708738/

Смотрите также:

2014 biblioonline ru
Отформатировать текстовый фрагмент в MS Word. Текстовый фрагмент, который подлежит форматированию, приведен в документе Задание 1, прикрепленном ниже.
_ ОПОРНИЙ КОНСПЕКТ БД
_05_В. Гюго
_1966(~1
_Антонян Ю.М., Сексуальные преступления. Чикатило и другие
_РГР № 1 (2)
- Габариты и масса 27