5.5. КВАДРАТИЧНОЕ ПРОГРАММИРОВАНИЕ
К задачам квадратичного программирования относят специальный класс задач НП, для которых целевая функция 
- квадратичная и вогнутая (или выпуклая), а все ограничения линейны.
Применив к этой задаче теорему Куна-Таккера, получим условия для оптимального решения в виде системы линейных уравнений, решить которые можно симплекс-методом.
В матричном виде эта задача записывается так:
максимизировать
(5.5.1)
при ограничениях
(5.5.2)
где 
- симметричная, отрицательно определенная матрица,
Заметим, что если 
- отрицательно определенная матрица, то квадратичная форма 
вогнута (выпукла вверх). Следовательно, задача (5.5.1), (5.5.2) является задачей вогнутого программирования.
Приведем примеры квадратичных функций:
Будем предполагать, что - строго вогнута. Применив к задаче (5.5.1) - (5.5.2) теорему Куна-Таккера, получим необходимые и достаточные условия оптимальности в виде теоремы [18; 23].
Теорема 5.14. Вектор 
является оптимальным решением задачи квадратичного программирования тогда и только тогда, когда существуют такие 
-мерные вектора 
и 
-мерный вектор 
, что выполняются следующие условия:
Заметим, что условия 1), 2) образовывают относительно переменных 
систему 
уравнений с 
неизвестными.
Доказательство. Составим функцию Лагранжа для задачи (5.5.1):
(5.5.3)
Заметим, что
(5.5.4)
(5.5.5)
Применив теорему Куна-Таккера к функции (5.5.3) и воспользовавшись выражениями (5.5.4), (5.5.5), получим:
причем, если 
причем, если 
Введем два вспомогательных вектора: 
. Причем выберем 
, если 
и 
, если 
. Аналогично выберем 
,
если 
и 
, если 
.
Прибавив вектор 
к условию а) и вычтя 
из б), получаем равенства
(5.5.6)
Сравнив компоненты векторов 
и , а также 
и , получим два условия дополняющей нежесткости:
Теорема доказана.
Из условий 3), 4) следует, что по меньшей мере 
переменных из 
и 
переменных среди 
обращаются в нуль.
Как уже отмечалась, система (5.5.6) состоит из 
уравнений с 
неизвестными. Таким образом, если существует оптимальное решение задачи (5.5.1), то оно должно быть одним из базисных решений (5.5.6). Поскольку для нахождения допустимого базисного решения можно применить симплекс-метод Данцига, то этот метод (как и другие методы ЛП) пригоден для решения задач квадратичного программирования.
Перепишем (5.5.6) в виде
(5.5.7)
Для нахождения начального базиса системы (5.5.7) применим метод искусственных переменных. Введем искусственные переменные 
и 
. Приходим к следующей системе:
(5.5.8)
При этом знаки перед компонентами векторов 
выбираем одинаковыми со знаками соответствующих компонентов свободных членов - 
и 
.
Составив псевдоцелевую функцию 
выводим из базиса искусственные переменные 
и вводим 
. При этом следует учитывать условия дополняющей нежесткости 
Если удается вывести из базиса все искусственные переменные и при этом удовлетворяются условия 3), 4) теоремы 5.14, то найденное базисное решение есть оптимальной.
Пример 5.6. Решить следующую задачу
максимизировать 
(1)
при ограничениях
(2)
Поскольку 
это 
вогнута, и эта задача является задачей квадратичного программирования.
Составляем функцию Лагранжа
Применив теорему Куна-Таккера, получим следующие условия для оптимального решения:
(3)
и условия дополняющей нежесткости
(4)
Введя в систему (3) свободные переменные 
получим следующую систему:
(5)
и условия дополняющей нежесткости
(6)
Второе ограничение в условиях (2) выполняется как строгое равенство, поэтому нет ограничения на знак переменной 
. Тем не менее поскольку симплекс-метод позволяет находить лишь неотрицательные базисные решения, то сделаем замену переменных: 
. Запишем систему (5) в эквивалентном виде
(7)
Необходимо найти ДБР системы (7), удовлетворяющее всем условиям (6). Для этого применим метод искусственных переменных. Введем искусственные переменные 
в первое, второе и четвертое ограничения. В результате получим следующую задачу ЛП:
минимизировать 
(8)
при ограничениях
(9)
Решаем задачу (8), (9) симплекс-методом при дополнительном ограничении (6) на выбор базиса.
Результаты последовательных итераций приведен в табл. 5.1-5.5. После четвертой итерации получаем оптимальное решение, удовлетворяющее условиям дополняющей нежесткости:
Таблица 5.1
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
M |
M |
M |
|
|
Bx |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
20 |
2 |
5 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
|
M |
|
8 |
2 |
-1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
|
M |
|
32 |
8 |
0 |
2 |
2 |
-2 |
-1 |
0 |
0 |
0 |
1 |
0 |
|
|
|
120 |
0 |
30 |
5 |
-1 |
1 |
0 |
-1 |
0 |
0 |
0 |
1 |
|
D |
160M |
10M |
29M |
7M |
M |
-M |
-M |
-M |
0 |
0 |
0 |
0 |
Таблица 5.2
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
M |
M |
|
|
Bx |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
2 |
0 |
-5/6 |
1/6 |
-1/6 |
0 |
1/6 |
1 |
0 |
0 |
|
M |
|
12 |
2 |
0 |
1/6 |
-1/30 |
1/30 |
0 |
-1/30 |
0 |
1 |
0 |
|
M |
|
32 |
8 |
0 |
2 |
2 |
-2 |
-1 |
0 |
0 |
0 |
1 |
|
0 |
|
4 |
0 |
1 |
1/16 |
-1/30 |
1/30 |
0 |
-1/30 |
0 |
0 |
0 |
|
D |
44M |
10M |
0 |
|
|
|
-M |
- |
0 |
0 |
0 |
Таблица 5.3
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
M |
M |
|
|
Bx |
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
0 |
1 |
0 |
-5/12 |
1/2 |
-1/2 |
0 |
1/12 |
1/2 |
0 |
0 |
|
M |
|
12 |
0 |
0 |
1 |
-1/5 |
1/5 |
0 |
-1/5 |
-1 |
1 |
0 |
|
|
|
32 |
0 |
0 |
16/3 |
4/3 |
-4/3 |
-1 |
-2/3 |
-4 |
0 |
1 |
|
0 |
|
4 |
0 |
1 |
1/6 |
-1/30 |
1/30 |
0 |
-1/30 |
0 |
0 |
0 |
|
D |
44M |
0 |
0 |
19M/3 |
17M/5 |
-17M/5 |
-M |
-13M/15 |
-5M |
0 |
0 |
Таблица 5.4
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
M |
|
|
Bx |
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
5/2 |
1 |
0 |
0 |
3/16 |
-3/16 |
-5/64 |
1/32 |
3/16 |
0 |
|
|
|
6 |
0 |
0 |
0 |
-9/20 |
9/20 |
3/16 |
-3/40 |
-1/4 |
1 |
|
0 |
|
6 |
0 |
0 |
1 |
1/4 |
-1/4 |
-3/16 |
-1/8 |
-3/4 |
0 |
|
0 |
|
3 |
0 |
1 |
0 |
-3/40 |
3/40 |
1/32 |
-1/80 |
1/9 |
0 |
|
D |
6M |
0 |
0 |
0 |
-9M/20 |
9M/20 |
3M/16 |
-3M/40 |
M/4 |
0 |
Таблица 5.5
|
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
|
Bx |
|
|
|
|
|
|
|
|
|
|
|
0 |
|
5 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1/12 |
|
0 |
|
40/3 |
0 |
0 |
0 |
-1 |
1 |
5/12 |
1/6 |
-5/9 |
|
0 |
|
28/3 |
0 |
0 |
1 |
0 |
0 |
1/12 |
-1/6 |
-8/9 |
|
0 |
|
2 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
|
D |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
