48.Метод Гоморі.

алгоритм, запропонований Гоморі, для розв’язування повністю цілочислової задачі лінійного програмування, що ґрунтується на використанні симплексного методу і передбачає застосування досить простого способу побудови правильного відтинання. Нехай маємо задачу цілочислового програмування: за умов:,(8.6),(8.7)– цілі числа. (8.8) Допустимо,щопараметри– цілі числа. доведено, що за певних умов алгоритм Гоморі є скінченним, але процес розв’язування задач великої розмірності методом Гоморі повільно збіжний. Слід також мати на увазі, що і кількість ітерацій суттєво залежить від сформованого правильного відтинання. снують ефективніші відтинання, які використовуються у другому та третьому алгорит­мах Гоморі, однак наявний практичний досвід ще не дає змоги виділити з них найкращий. Загалом, алгоритм Гоморі в обчислювальному аспекті є мало вивченим. Якщо в лінійному програмуванні спостерігається відносно жорстка залежність між кількістю обмежень задачі та кількістю ітерацій, що необхідна для її розв’язування, то для цілочислових задач такої залежності не існує. Кількість змінних також мало впливає на трудомісткість обчислень.