Page 173 - 6197
P. 173
Знаходження такого розв’язку можна здійснити як
реалізацію першого етапу задачі лінійного програмування
шляхом уведення штучних невід’ємних змінних. При цьому
додатковими обмеженнями буде необхідність виконання умов
u x 0 і v w . Виконання цих умов означає: якщо змінна
0
k k i i
x приймає додатне значення, то величина u набуде
k k
нульового значення. Це означає, що змінні x і u не можуть
k k
бути одночасно введеними у базис. Аналогічно змінні v і w
i i
не можуть одночасно приймати додатні значення (бути
одночасно базисними змінними). Остання умова носить назву
обмеженого доступу до базису.
Процес знаходження розв’язку задачі квадратичного
програмування закінчується тоді, коли штучні змінні
набувають нульових значень і це означає, що початкова
задача має непусту множину допустимих розв’язків.
Приклад 3.5. Знайти мінімум функції
2
2
R x 4x 6x 2x 2x x 2x (3.52)
2
1
1 2
2
1
за умови, що
x 2x 2 0 , (3.53)
1 2
x 0 , x . (3.54)
0
1 2
Дослідимо функцію R x на глобальний мінімум.
2 1
Визначимо матрицю D і її кутові мінори. Маємо D і
1 2
відповідно 2 0 , 3 0 . Отже, функція x має
R
1 2
глобальний мінімум, значення якого визначимо із умов
R x R x
0 і 0 . Враховуючи значення R x ,
x x
1 2
знаходимо
2x x 2 ,
1 2
173