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
   168   169   170   171   172   173   174   175   176   177   178