Задача квадратичного программирования (КП) может быть записана в матричной форме следующим образом: \/(х) = х' Dx + (с, х) -^ max, Ax-^b, (1) х>0, где Л' - /7-мерный вектор-столбец; Л-' - /2-мерная вектор-строка; с' - /7-мерная вектор-строка; b - /77-мерный вектор-столбец; А - матрица размера т х п\ D - симметрическая квадратная матрица порядка п\ x'Dx = (x'D, X) = (л-, Dx). Решить задачу КП - это значит найти точку х* G £2, для кото рой достигается максимум функции /(х*) = т а х / ( х ) , (2) где О. - множество допустимых планов задачи, определяемое системой ог раничений Ах = Ь, х>0 . Если Z) = О, то задача сводится к задаче линейного программи рования (см.). Если целевая функция задачи КП ограничена сверху, то задача обязательно имеет оптимальное решение, т.е. точку глобального максимума. Для нахождения глобального максимума общей задачи (1) не существует эффективных вычислительных методов. В настоящее время развиты методы выпуклого КП - раздела выпуклого программирования (см.), который занимается задачами поиска глобального максимума выпуклой квадратичной функ ции на многогранном множестве. В этом классе задач доказано, что если матрица D является отрицательно определенной, то це левая функция (1) будет ограничена сверху, и задача (1) будет иметь оптимальное решение, притом единственное (при условии, что допустимое множество непусто). 309 Важное место в выпуклом КП занимает двойственная задача. В соответствии с общим принципом двойственности для за дачи (1) двойственная задача имеет вид: L(X) = - У/)л'+ (Х, Z?)-> min (3) при условиях 2Dx -^ А' Х>с, х> О, (4) где Л' - матрица, транспонированная по отношению к А\ с - «-мерный вектор-столбец; X - w-мерный вектор-столбец. В линейном случае (при D = 0) определение двойственной зада чи (3) - (4) совпадает с принятым в линейном программировании. Как и в случае линейного программирования, в КП имеет место теорема двойственности: Если одна из задач двойственной пары разрешима, то и дру гая задача также разрешима, причем экстремальные значения обеих задач равны. Условие Куна-Такера для выпуклой задачи (1) - (2) имеет вид: Ах = Ь, 2Dx-^A'X + v = -c\ (5) x.v. = Oj= 1, ... ,п. Таким образом, для того чтобы вектор х^ был решением за дачи (1) - (2), необходимо и достаточно существование вектора v^ > О и вектора А,^, таких, чтобы система векторов х^, v^, Х^ удов летворяла условию (5). Любой (2п + т)-мерный вектор (х, v. А,}, который является решением системы (5) при условии х > О, v > О, будет крайней точкой многогранного множества, т.е. базисным решением системы: Ах - Ь, 2Dx-A'X + v = c. ^ ^ С учетом условия (6) решение задачи КП сводится к нахожде нию базисных решений многогранных множеств, что может быть успешно осуществлено симлекс-методом линейного программи рования за конечное число шагов. 310 Кроме общих методов выпуклого программирования специ ально для задачи выпуклого КП разработано много численных методов, включая конечные [4]. Наиболее употребительными ко нечными методами являются: симплексный метод Билла, метод сопряженных градиентов, симплексный метод Вулфа. Эффектив ность того или иного метода существенно зависит от специфики решаемой задачи.
Ви переглядаєте статтю (реферат): «КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ» з дисципліни «Теорія систем і системний аналіз в управлінні організаціями»
