Квадратичный симплекс-метод

Рассмотрим задачу квадратичного программирования, которая состоит в нахождении минимального значения функции Z= Z(x₁ , х₂, …,х_n)

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

Она является частным случаем задачи выпуклого программирования, поэтому для ее решения можно использовать необходимые и достаточные условия Куна-Таккера для установления наличия решения. Функция Лагранжа для задачи квадратичного программирования записывается так:

, где - множители Лагранжа,

Теорема Куна-Таккера в аналитической форме может быть представлена следующими выражениями:

Соотношения (3) и (6) определяют условия дополняющей нежесткости.

Для решения данной системы можно использовать следующий прием. Неравенства (1) и (4) преобразуют в равенства, вводя соответственно две группы дополнительных переменных _j, j=1÷ n и _i , i= 1÷ m. При этом _j ≥ 0 и _i ≥ 0. В результате от системы 1-6 переходим к системе 7-12.

Таким образом, система (7) и (10) содержит (m+n) линейных уравнений с условием неотрицательности переменных (8) и (11) и условием дополняющей нежесткости (9) и (12).

Для решения такой вспомогательной задачи (7 + 10) можно использовать симплексный метод. Для нахождения исходного опорного (допустимого базисного) решения применим метод искусственного базиса (М-метод), введя искусственные переменные у_k ≥0, k =1÷ (m+n), k ≤ (m+n).

Целевая функция М - вспомогательной задачи имеет вид:

Если в результате решения М-вспомогательной задачи min F(y) = 0 и все искусственные переменные у_k принимают нулевые значения, кроме того, выполняются условия дополняющей нежесткости, то опорное решение вспомогательной задачи определяет оптимальное решение задачи квадратичного программирования.

Если условие нежесткости не выполняется, то надо перейти к новому опорному решению, включив в базис переменную с нулевой оценкой.

Если min F(y) > 0, то задача квадратичного программирования не имеет решения. Если хотя бы одна из искусственных переменных не равна нулю, то система основной задачи не имеет решения.

Пример 25

min Z = (x₁ – 5)² + (x₂ -10)²

Решение.

Преобразуем целевую функцию и ограничения.

Min Z =

х₁+ х₂ – 11 ≤ 0

4х₁ – х₂ – 4 ≤ 0

Составляем функцию Лагранжа.

.

Находим частные производные и составляем условия Куна-Таккера (1-6).

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

Вводим искусственные переменные в первое и второе уравнения, т.к. в них нет базисных переменных.

Все переменные неотрицательные. Условия дополняющей нежесткости: х₁₁=0; х₂₂=0; ₁₁=0; ₂₂=0.

Умножим целевую функцию на (-1) и запишем исходное опорное решение в первую симплексную таблицу.

maxZ = -My₁ - My₂

Таблица 9

Симплексная таблица 1

№1	Сj	0	0	0	0	0	0	0	0	0	-M	-M
Ci	П БП	ai0	x1	x2	1	2	1	2	1	2	y1	y2	СО
-M	y1	10	2	0	1	4	-1	0	0	0	1	0	10:4=2,5*
-M	y2	20	0	2	1	-1	0	-1	0	0	0	1	-
0	1	11	1	1	0	0	0	0	1	0	0	0	-
0	2	4	4	-1	0	0	0	0	0	1	0	0	-
	j	-30M	-2M	-2M	-2M	-3M	M	M	0	0	0	0
						*

Таблица 10

Симплексная таблица 2

№2	Сj	0	0	0	0	0	0	0	0	0	-M	-M
Ci	П БП	ai0	x1	x2	1	2	1	2	1	2	y1	y2	СО
0	2	5/2	1/2	0	1/4	1	-1/4	0	0	0	1/4	0	-
-M	y2	22,5	1/2	2	5/4	0	-1/4	-1	0	0	1/4	1	22,5:2==11,25
0	1	11	1	1	0	0	0	0	1	0	0	0	11 *
0	2	4	4	-1	0	0	0	0	0	1	0	0	-
	j	-22,5M	-1/2M	-2M	-5/4M	0	1/4M	M	0	0	3/4M	0
				*

Таблица 11

Симплексная таблица 3

№3	Сj	0	0	0	0	0	0	0	0	0	-M	-M
Ci	П БП	ai0	x1	x2	1	2	1	2	1	2	y1	y2	СО
0	2	5/2	1/2	0	1/4	1	-1/4	0	0	0	1/4	0	5/2:1/4=10
-M	y2	1/2	-3/2	0	5/4	0	-1/4	-1	-2	0	1/4	1	1/2:5/4=2/5 *
0	x2	11	1	1	0	0	0	0	1	0	0	0	-
0	2	15	5	0	0	0	0	0	1	1	0	0	-
	j	-1/2M	3/2M	0	-5/4M	0	1/4M	M	2M	0	3/4M	0
					*

Таблица 12

Симплексная таблица 4

№4	Сj	0	0	0	0	0	0	0	0	0	-M	-M
Ci	П БП	ai0	x1	x2	1	2	1	2	1	2	y1	y2	СО
0	2	2,4	4/5	0	0	1	-1/5	1/5	2/5	0	1/5	-1/5	2,4:4/5=3*
0	1	2/5	-6/5	0	1	0	-1/5	-4/5	-8/5	0	1/5	4/5	-
0	x2	11	1	1	0	0	0	0	1	0	0	0	11:1=11
0	2	15	5	0	0	0	0	0	1	1	0	0	15:5=3
	j	0	0	0	0	0	0	0	0	0	M	M
			*

В четвертой симплексной таблице получено оптимальное решение вспомогательной задачи: minZ = 0, искусственные переменные у не входят в базис и все оценки _j неотрицательные. Однако не выполняется условие дополняющей нежесткости ₂₂=0, а именно ₂ и ₂ имеют ненулевые значения. Поэтому введем в базис переменную х₁, т.к. х₁ является свободной переменной и имеет нулевую оценку (альтернативное решение).

Таблица 13

Симплексная таблица 5

№5	Сj	0	0	0	0	0	0	0	0	0	-M	-M
Ci	П БП	ai0	x1	x2	1	2	1	2	1	2	y1	y2
0	x1	3	1	0	0	5/4	-1/4	1/4	1/2	0	1/4	-1/4
0	1	4	0	0	1	3/2	-4/5	-1/2	-1	0	1/2	1/2
0	x2	8	0	1	0	-5/4	1/4	-1/4	1/2	0	-1/4	1/4
0	2	0	0	0	0	-25/4	5/4	-5/4	-3/2	1	-5/4	5/4
	j	0	0	0	0	0	0	0	0	0	M	M

В пятой симплексной таблице выполняются все необходимые условия.

- является седловой точкой функции Лагранжа. Следовательно, - оптимальное решение исходной задачи. Min Z = 8.

Замечание. Решение задачи квадратичного программирования можно выполнить методом Ньютона на персональном компьюторе, использовуя приложение MS Excel «Поиск решения».