Page 19 - 6416

Результат розв’язування задачі
>> x
x =
3.0000
4.0000
>> fval
fval =
15.0000
Неважко переконатись, що результати обчислень отримані при розв’язуванні задачі
лінійного програмування графічним, двоетапним методами та за допомогою ЕОМ повністю
співпадають.

6.4 Приклад розв’язання задачі квадратичного програмування
Задача 3
Розв’яжемо таку задачу квадратичного програмування:
2
2
min : R   x   14x  54x  4x  2x x  6x ,
1
2
2
1
1 2
9
x  2x  ,
1 2
0
x , x  .
1 2

Дослідимо функцію   x на глобальний мінімум. Визначимо матрицю D і її кутові
R
 4  1
мінори. Маємо D    і відповідно   4 0 ,   23 0 . Отже, функція   x має
R
2
1
  1 6 
 R   x  R   x
глобальний мінімум, значення якого визначимо із умов  0 і  0 . Враховуючи
x  1 x  2
значення   x , знаходимо
R
8x  2x  14,
1 2
 2x  12x  54 .
1 2
Отримали систему лінійних рівнянь з двома невідомими, розв’язок якої визначає точку
*
глобального мінімуму x  3 5;  .
g
*
Неважко переконатись, що точка x не належить області X допустимих розв’язків
g
задачі.
*
Дійсно   3 8 11 9g x *     , тобто x  X .
g g
Для знаходження розв’язку задачі розглянемо систему співвідношень, які випливають із
умов теореми Куна-Таккера. Спочатку обмеження задачі перетворимо до такого тотожного
вигляду: x  2x  9 0 .
1 2
Запишемо узагальнену функцію Лагранжа
2
2
L  x, ,u    14x  54x  4x  2x x  6x    x  2x   9  u x  u x
1 1
1
2
2
1 2
1
2 2
1
2
і запишемо умови теореми Куна-Таккера для задачі, що розв’язується
0
  x  2x   9  ,
1
2
 x  2x  9 0 ,
1 2
u x  0, u x  ,
0
1 1 2 2
 L  x, ,u  0 ,
0
x , x  ,   ,
0
1 2
0
u  0 , u  .
1 2
Знайдемо компоненти градієнта функції  x, ,u  . Маємо
L
16