Задача квадратичного программирования

(43)

при ограничениях

(44)

(45)

где D=|| a_ij || - симметрическая n x n матрица, r=(r₁,…,r_n) - постоянный вектор, A=|| a_ij || - m x n матрица, b=(b₁,…,b_m) - постоянный вектор, можно свести к задаче ЛП. Здесь матрица D предполагается положительно определенной (отсюда следует выпуклость квадратичной формы F(x), а ограничения (44)-(45) являются линейными). Такой переход можно осуществить следующим образом. Сначала строим каноническую форму задачи (43)-(45), введя в ограничения (44) слабые переменные x_n+1,…,x_n+m. Тогда ограничения задачи запишутся (в координатной форме):

(46)

(47)

(48)

Теперь для задачи (43), (46)-(48) введем (классическую) функцию Лагранжа и запишем необходимые условия оптимальности (см. теорему 4)

- условие стационарности:

(49)

- условие допустимости;

(50)

, (51)

- условие дополняющей нежесткости:

(52)

- условие неотрицательности:

(53)

Систему (49)-(53) можно решать двухфазным симплекс-методом (методом искусственного базиса), рассматривая (49) как целевую функцию, а (50)-(53) – как ограничения, с учетом того, что множители Лагранжа l₁,…, l_n,m₁,…, m_n не должны все одновременно равняться нулю.

Замечание. При использовании двухфазного симплекс метода следует учитывать «нелинейность» ограничений (52), т.е. не включать в базисные одновременно переменные l_j и x_j с одним и тем же индексом и переменные m_j и x_n+i с одним и тем же индексом.

4) Элементарным (по своей идее) является метод сведения задачи с ограничениями-равенствами:

(54)

при ограничениях

(55)

к задаче безусловной оптимизации (метод исключения). Из уравнений (55) исключается k переменных, например,

Подставляя найденные представления переменных x₁,…,x_k в целевую функцию (54), приходим к следующей задаче безусловной оптимизации относительно n-k переменных:

Этот метод наиболее приемлем в том случае, когда ограничения (55) линейны:

Ax=b

Дата добавления: 2015-09-04