Page 179 - 5637

3.4. Якщо 0 < < ∞, то обчислюємо за формулою = + .
п
п
п п
Заміняємо на + 1 і переходимо до п.2.
4. Якщо < , то замінюємо на + 1 і переходимо до п.3. Якщо = ,

то хп оголошується наближеним рішенням задачі (8.1) – (8.3).

В даному алгоритмі (як і в алгоритмі методу вектора спаду) при переході до

процедури перебору елементів околиці Хеммінга ( , ) збільшеним на одиницю

радіусом досить розглядати точки, що належать поверхні Хеммінга ( , ) =

= ( , )/ ( , − 1). Достатні умови збіжності алгоритму методу направляючих

околиць при вирішенні задачі опуклого цілочисельного програмування сформульовані
в [69]. Там же розглянуті приклади його застосування для вирішення завдань

лінійного цілочисельного програмування, частково цілочисельного програмування, а

також для пошуку локальних рішень параметричних задач лінійного цілочисельного

програмування (тобто завдань, цільова функція і (або) коефіцієнти системи обмежень

яких залежать від деякого параметра). Як критерій закінчення пошуку (або якості

рішення) по алгоритму методу направляючих околиць аналогічно алгоритму методу

вектора спаду може слугувати оцінка величини min ( ), отримана з допомогою
∈
алгоритму статистичної оцінки екстремальних значень функції (див. §8.6).

При описі алгоритму методу направляючих околиць залишилася невирішеною

завдання отримання хоча б одного допустимого рішення, тобто елемента безлічі . У

загальному випадку для знаходження допустимих рішень можна скористатися

алгоритмами безумовної мінімізації, призначеними для виконання завдання пошуку

такого , що

= min ( ),
∈

де ( ) = ∑ ( ) ( ) ; ( ) – оператор Хевісайда; = 0 при ( ) ≤ 0 і = 1

при ( ) > 0; ( = 1, … , ) – функції, формують систему обмежень (8.3).

Функціонал ( ) характеризує ступінь порушення даної точкою у системи обмежень.

Легко бачити, що ( ) ≥ 0 для всіх ∈ і ( ) = 0 при ∈ . У даній постановці
завдання пошуку допустимого рішення трансформується в задачу цілочисельного
програмування без обмежень, для вирішення якої можна застосувати методи

напрямних околиць і вектора спаду.