6.3. Методи знаходження рішення задачі квадратичного програмування

Алгоритм розв’язання задачі квадратичного програмування:

1. Складаємо функцію Лагранжа.

2. Записуємо необхідні і достатні умови існування сідлової точки функції Лагранжа .

3. Використовуючи метод штучного базису, або встановлюємо, що сідлова точка функції Лагранжа відсутня, або знаходимо її координати.

4. Записуємо оптимальний розв’язок задачі квадратичного програмування і знаходимо значення цільової функції.

Приклад. Знайти максимальне значення функції

(6.3.1)

при обмеженнях

(6.3.2)

(6.3.3)

Розв’язання. Функція є угнутою оскільки являє собою суму лінійної функції f₁ = x₁ +8 x₂ (яку також можна розглядати як угнуту) і квадратичної форми f₂ = -x₁² – x₂², яка є недодатне визначеною і йому також є угнутою функцією. Система обмежень задачі містить лише лінійні рівняння. Отже, можна застосувати теорему Куна-Таккера. З цією метою запишемо функцію Лагранжа:

(6.3.4)

Запишемо необхідні і достатні умови існування сідлової точки побудованої функції Лагранжа:

(6.3.5)

(6.3.6)

(6.3.7)

Запишемо систему (6.3.5) таким чином:

(6.3.8)

Зведемо ці нерівності до строгих рівностей. З цією метою введемо додаткові невід’ємні змінні

(6.3.9) (6.3.10)

Враховуючи рівності (6.3.9) можна записати:

(6.3.11)

Для знаходження базисного розв’язку системи лінійних рівнянь (6.3.9) застосовуємо метод штучного базису. Для цього в перше і друге рівняння системи (6.3.9) вводимо додаткові невід’ємні змінні z₁ , z₂ і розв’яжемо задачу лінійного програмування:

(6.3.12)

при обмеженнях

(6.3.13)

(6.3.14)

Розв’язавши задачу (6.3.12) - (6.3.13) знаходимо допустимий розв’язок системи лінійних рівнянь (6.3.13) (табл.1).

Як видно з таблиці 1 розв’язком задачі є

Оскільки то (x⁰ , λ⁰ ) = (1/2, 4, 0, 0) є сідловою точкою функції Лагранжа задачі (6.3.1)-(6.3.3). Отже, x^* = (1/2; 4) оптимальний план задачі і f_max = 16,75.

Таблиця1.

і	Б	Сб	А0	0	0	0	0	0	0	0	0	-М	-М
				Ах1	Ах2	Аλ1	Аλ2	Аν1	Аν2	Аω1	Аω2	Аz1	Az2
1	Az1	-M	1	2	0	1	0	-1	0	0	0	1	0
2	Az2	-M	8	0	2	1	1	0	-1	0	0	0	1
3	Aw1	0	7	1	1	0	0	0	0	1	0	0	0
4	Aw2	0	5	0	1	0	0	0	0	0	1	0	0
m+1			0	0	0	0	0	0	0	0	0	0	0
m+2			-9	-2	-2	-2	-1	1	1	0	0	0	0
1	Ax1	0	1/2	1	0	1/2	0	-1/2	0	0	0	1/2	0
2	Az2	-M	8	0	2	1	1	0	-1	0	0	0	1
3	Aw1	0	13/2	0	1	-1/2	0	1/2	0	1	0	-1/2	0
4	Aw2	0	5	0	1	0	0	0	0	0	1	0	0
m+1			0	0	0	0	0	0	0	0	0	0	0
m+2			-8	0	-2	-1	-1	0	1	0	0	1	0
1	Ax1	0	1/2	1	0	1/2	0	-1/2	0	0	0
2	Ax2	0	4	0	1	1/2	1/2	0	-1/2	0	0
3	Aw1	0	5/2	0	0	1/2	-1/2	1/2	1/2	1	0
4	Aw2	0	1	0	0	-1/2	-1/2	0	1/2	0	1
m+1			0	0	0	0	0	0	0	0	0