Файл: прикладная математика учебное пособие московский автомобильнодорожный.docx

квадратичная форма, называется задачей квадратичного программи- рования. Для сформулированной задачи квадратичного программиро- вания функция Лагранжа запишется в виде

n n n n

L _d_jx_jj1

^^^ckj^xk^xjk1 j1

 y_i(b_i

_a_ijx_j).

j1

Если функция Lимеет седловую точку

( X,Y)  (x⁰, x⁰,..., x⁰, y⁰,

0 0 1 2 n 1

y⁰,..., y⁰ ), то в этой точке выполняются соотношения (1.15). Вводя те-

2 m

перь дополнительные переменные

v_j( j

 1,...,n), w_i

(i 1,...,m),

обра-

щающие неравенства из (1.15) в равенства, перепишем выражения (1.15), записанные для задачи квадратичного программирования, сле- дующим образом:

L₀

x_j

L₀

y_i

 0 ( j 1,...,n);
 0 (i=1,...,m);

(1.19)
(1.20)

1 2 3 4 5 6 7 8 9 ... 42

xv

j j
⁰  0 ( j

yw

i i
⁰  0 (i

 1,...,n);

 1,...,m);

(1.21)

(1.22)

x⁰  0, v 0, y⁰  0, w 0, (j 1,...,n; i=1,...,m). (1.23)

j j i i

Таким образом, чтобы найти решение задачи квадратичного про- граммирования (1.16…1.18), нужно определить неотрицательное ре- шение систем линейных уравнений (1.19 и 1.20), удовлетворяющих условиям (1.21 и 1.22). Это решение можно найти с помощью метода искусственного базиса, примененного для нахождения максимального

^{значения}^{функции}F

 _My_ii

при условиях (1.19, 1.20, 1.23) с учетом

(1.21 и 1.22). Здесь y_i

искусственные переменные, введенные в

уравнения (1.19 и 1.20). Используя метод искусственного базиса и до- полнительно учитывая условия (1.21 и 1.22), после конечного количе- ства шагов либо установим неразрешимость, либо получим опти- мальный план исходной задачи.

Итак, процесс нахождения решения задачи квадратичного про- граммирования (1.16…1.18) включает в себя следующие этапы:

составляют функцию Лагранжа;
записывают в виде выражений (1.19…1.23) необходимые и доста- точные условия существования седловой точки для функции Ла- гранжа либо находят ее координаты;
используя метод искусственного базиса, либо устанавливают от- сутствие седловой точки для функции Лагранжа, либо находят ее координаты;
записывают оптимальное решение исходной задачи и находят значение целевой функции.

Градиентные методы решения задач нелинейного программирования

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

дов состоит в том, что начиная с некоторой точки

_X(k)

осуществляет-

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

К первой группе относятся методы, при использовании которых исследуемые точки могут не выходят за пределы области допустимых решений задачи. Наиболее распространенным из таких методов яв- ляется метод Франка-Вулфа.

Ко второй группе относятся методы, при использовании которых исследуемые точки могут как принадлежать, так и не принадлежать области допустимых решений. Однако в результате реализации ите- рационного процесса находится точка области допустимых решений, определяющая приемлемое решение. Из таких методов чаще всего используется метод штрафных функций или метод Эрроу-Гурвица.

При нахождении решения задач градиентными методами, в том числе и названными, итерационный процесс осуществляется до того

момента, пока градиент функции

f(x₁, x₂,..., x_n)

в очередной точке

_X(k1)

не станет равным нулю или же пока

f( X⁽^k^¹⁾ )  f( X⁽^k⁾ )

 ,

где  –

достаточно малое положительное число, характеризующее точность полученного решения.

Метод Франка-Вулфа

Пусть требуется найти максимальное значение вогнутой функции

при условиях

f(x₁, x₂,..., x_n)
n

(1.24)

^^aij^xjj1

 b_i

(i 1,...,m),

(1.25)

x_j 0 ( j

 1,...,n).

(1.26)

Особенностью этой задачи является то, что ее система ограниче- ний содержит только линейные неравенства. Эта особенность являет- ся основой для замены в окрестности исследуемой точки нелинейной целевой функции линейной, благодаря чему решение исходной зада- чи сводится к последовательному решению задач линейного про- граммирования.