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

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

2.1. Одномерный случай

Имеем задачу

f(х)-> extr x€Х,

где X € Е₁ — совокупность отрезков, интервалов, полуинтервалов.

Теорема Ферма. Пусть функция f(x) дифференцируема в некотором промежутке X и во внутренней точке х* этого промежутка принимает наибольшее (наименьшее) значение. Тогда f'{x*) = 0.

Искать: граничные точки, точки разрыва функции и точки разрыва производной.

Правило нахождения глобального экстремума. Для нахождения глобального экс­тремума функции f(x) на множестве X С Е₁ нужно найти следующие множества то­чек:

1. множество стационарных точек Х₁ = {х€ X \ f'(x) = 0};

2. множество точек разрыва функции Х₂ = {х € X \ f(x) — разрывна };

3. множество точек разрыва производной Х₃ = {х € X \ f'(x) — разрывна};

1. множество граничных точек (в том числе и точки ±оо_; если они принадлежат допустимому множеству) Х₄ = FrX = X \ IntX.

После этого необходимо вычислить значения функции в этих точках и выбрать среди них наибольшее и наименьшее значения. Если соответствующие точки принадлежат множеству X, то минимум или максимум достигается на множестве X. В противном случае имеем точную нижнюю или верхнюю границы.

3. Задачи с ограничениями-равенствами. Метод неопределённых множите­лей Лагранжа

Теперь перейдём к анализу задач условной оптимизации в Е_п и рассмотрим случай ограничений-равенств, т. е. решается задача:

f(x)->min{x€X} (f(x)->max{x€X}) (1)

где

X = {х € Е_п | φ_j(x) = 0, j = 1, т}.(2)

Будем предполагать, что т < п.

В дальнейшем нам потребуется следующая

Теорема о неявных функциях. Предположим, что:

1) дана система из т уравнений с п неизвестными (т < п)

Fj(xi,...,x_n) = 0 (j = l,m); (3)

2) все функции Fj(x) определены, непрерывны и имеют непрерывные частные производ­ные по всем аргументам в некоторой окрестности Uε (x°) точки х°, в которой Fj(x°) = 0(j=1,m, ε>0)

3) якобиан

Тогда:

а) в некоторой окрестности точки х°, содержащейся в Uε (x°), система уравнений (3) определяет, x₁,..., х_т как однозначные функции от х_т+1,..., х_п:

xi=f(х_т+1,..., х_п) (i=1,m)

б) при x_i = x°_i (i= т + 1, п) эти функции принимают значения x°_i (i = 1, т):fi(x°_m+1,… x°_n)= x°_I (i=1,m)

в) все функции fi{x_m+1,... ,х_п) (г = 1,m) непрерывны и имеют непрерывные частные производные по всем аргументам.

Следует обратить внимание на локальный характер теоремы существования неявных функций: речь идёт всё время о некоторой окрестности рассматриваемой точки. Но и в таком виде эта теорема полезна.

Рассмотрим теперь задачу (1) о нахождении экстремума функции f(x) на множестве X, определяемом условием (2). Предполагается, что функции f{x), <φ_j(x) (j = l,m) непрерыв­ны и непрерывно дифференцируемы в окрестности Uε(x*) некоторой экстремальной точки х*. Пусть в этой точке ранг матрицы частных производных

р авен т. Для определённости будем считать, что определитель

Тогда, в силу теоремы о неявных функциях, в некоторой окрестности точки х* система уравнений

φ _j(x) = 0(i = l,m) (3')

равносильна системе

xi = fi(x_m+1,...,x_n) (i = l,m), (5)

где fi — неявные функции, определяемые системой (3')- Таким образом, вопрос об условном экстремуме сводится к вопросу о безусловном экстремуме для сложной функции

F(x_m+1,...,x_n)≡f(f1(x_m+1,...,x_n),…, fm(x_m+1,...,x_n), x_m+1,...,x_n)) (6)

в точке х*. Эти соображения приводят к методу нахождения точек, доставляющих экс­тремум функции при ограничениях-равенствах. Если каким-то образом удаётся разрешить систему уравнений (3') относительно переменных хi (i = 1,m) и найти явные выражения для функций (5), то дело сводится к нахождению безусловного экстремума для функции (6). Этот метод называется методом исключения зависимых переменных. Можно указать дру­гой путь для нахождения экстремальных точек, не предполагая, что мы имеем явные выра­жения для функций (5), хотя существование этих функций использоваться будет. Лагранж предложил метод, в котором все переменные сохраняют одинаковую роль.

Метод неопределённых множителей Лагранжа. Введём в рассмотрение новые переменные y_j (j = 1, т) и функцию F(x,y) = f(x) +Sum{j=1,m}(y_i φ_j(x))

Переменные y_j называются неопределёнными множителями Лагранжа, а функция F(x, у) — функцией Лагранжа.

Пусть в точке х*, удовлетворяющей системе (3'), выполнены условия теоремы о неяв­ных функциях. Тогда, для того чтобы точка х* была точкой экстремума задачи (1)-(2), необходимо существование таких чисел у* (j = 1, т), что выполняются равенства

dF(x*,y*)/дx_i=0 (i=1,n)(7)

dF(x*,y*)/дy_j=0 (j=1,m)(8)

Условия (8), очевидно, эквивалентны условиям (3')- При решении задачи (1)-(2) дан­ным методом существенную роль играет предположение о ранге матрицы (4). Чтобы быть уверенным в том, что не пропущена ни одна подозрительная точка, следует предварительно установить, что это предположение выполняется во всех точках множества X.