Page 167 - 5637

повторюється, але додаються нові обмеження, названі за ефектом їхньої дії

відсіканнями. В даний час найбільш відомі метод Гоморі, призначений для вирішення

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

Бендерс та ін. [67, 72].

Комбінаторні методи призначені для вирішення задач цілочисельного

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

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

популярні комбінаторні методи і алгоритми: методи гілок і кордонів, адитивний

алгоритм Балаша, метод послідовного аналізу варіантів, метод послідовних

розрахунків [72, 76].

У сучасній інженерній практиці, особливо в практиці автоматизованого вибору

найкращих рішень, зріс інтерес до наближених методів дискретної оптимізації.

Наближені методи дозволяють отримати прийнятні для практики результати в

широкому діапазоні вирішуваних завдань, у той час як точні методи орієнтовані на

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

локальної оптимізації, випадкового пошуку, методи, які є модифікацією точних, а

також різні їх комбінації. (Наближеним методом присвячено багато праць, серед них

відзначимо [72], а також серію робіт школи В.С. Михалевича і І.В. Сергієнко [69, 73].)

8.2. Оптимізація дискретних параметрів методом Гоморі

У багатьох практичних додатках представляє великий інтерес завдання лінійного

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

форма

+ +. . . + ≤ , = 1, … , ; ≥ 0, = 1, … , ; (8.4)

= + +. . . + . (8.5)

Потрібно знайти цілочисельне рішення системи нерівностей (8.4), яке мінімізує
цільову функцію , причому всі коефіцієнти , і цілі ( = 1, … , ; = 1, … , ;

= 0, … , ).
Один з методів розв'язання задачі цілочислового програмування запропонований

Р.Е. Гоморі [67, 72]. Ідея методу полягає у використанні методів безперервного

лінійного програмування, зокрема симплекс-метода. Якщо знайдене за допомогою