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

К задачам квадратичного  программирования относят специальный класс задач, для которых целевая функция  - квадратичная и вогнутая (или выпуклая), а все ограничения линейны.

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

В матричном виде эта задача записывается так:

максимизировать

           (1)

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

                                      (2)

где   – симметричная, отрицательно определенная матрица,

Заметим, что если  – отрицательно определенная матрица, то квадратичная форма   вогнута (выпукла вверх). Следовательно, задача (1), (2) является задачей вогнутого программирования.

Приведем примеры квадратичных функций:            

Будем предполагать, что  - строго вогнута. Применив к задаче (1) – (2) теорему Куна-Таккера, получим необходимые и достаточные условия оптимальности в виде теоремы

Вектор   является оптимальным решением задачи квадратичного программирования тогда и только тогда, когда существуют такие  -мерные вектора   и  -мерный вектор  , что выполняются следующие условия:      

  

Заметим, что условия 1), 2) образовывают относительно переменных   систему   уравнений с   неизвестными.

Доказательство. Составим функцию Лагранжа для задачи (1):

                (3)

Заметим, что

                        (4)

                                (5)

Применив теорему Куна-Таккера к функции (3) и воспользовавшись выражениями (4), (5), получим:      

причем, если        

причем, если        

 Введем два вспомогательных вектора:    . Причем выберем  , если   и  , если  . Аналогично выберем  ,

если   и  , если  .      

 Прибавив вектор   к условию а) и вычтя   из б), получаем равенства

                                                    (6)

Сравнив компоненты векторов   и  , а также   и  , получим два условия дополняющей нежесткости:

 

Теорема доказана.

Из условий 3), 4) следует, что по меньшей мере   переменных из  и   переменных среди   обращаются в  нуль.

Как уже отмечалась, система (6) состоит из   уравнений с   неизвестными. Таким образом, если  существует оптимальное решение задачи (1), то оно должно быть одним из базисных решений (6). Поскольку для нахождения допустимого базисногорешения можно применить симплекс-метод Данцига, то этот метод (как и другие методы ЛП) пригоден для решения задач квадратичного программирования.

Перепишем (6) в виде

                                 (7)

Для нахождения начального базиса системы (7) применим метод искусственных переменных. Введем искусственные переменные   и  . Приходим к  следующей системе:

                          (8)

При этом знаки перед компонентами векторов   выбираем одинаковыми со знаками соответствующих компонентов свободных членов –   и  .

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

Если удается вывести из базиса все искусственные переменные и при этом удовлетворяются условия 3), 4) теоремы, то найденное базисное решение есть оптимальной.

 

Пример. Решить следующую задачу

максимизировать                  (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
M		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		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
M		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
M		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