524. Метод Гоморі повністю цілочислових задач. Знаходження цілої й дробової частини числа. Алгоритм розв'язування задачі.

алгоритм, запропонований Гоморі, для розв’язування повністю цілочислової задачі лінійного програмування, ґрунтується на використанні симплексного методу і передбачає застосування досить простого способу побудови правильного відтинання. Отже, для розв’язування цілочислових задач лінійного програмування методом Гоморі застосовують такий алгоритм:

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

Якщо серед елементів умовно-оптимального плану немає дробових чисел, то цей план є розв’язком задачі цілочислового програмування

Якщо задача не має розв’язку (цільова функція необмежена, або система обмежень несумісна), то задача) також не має розв’язку.

2. Коли в умовно-оптимальному плані є дробові значення, то вибирається змінна, яка має найбільшу дробову частину. На базі цієї змінної (елементів відповідного рядка останньої симплексної таблиці, в якому вона міститься) будується додаткове обмеження Гоморі:

.

3. Додаткове обмеження після зведення його до канонічного вигляду і введення базисного елемента приєднується до останньої симплексної таблиці, яка містить умовно-оптимальний план. Отриману розширену задачу розв’язують і перевіряють її розв’язок на цілочисловість. Якщо він не цілочисловий, то процедуру повторюють, повертаючись до п. 2. Так діють доти, доки не буде знайдено цілочислового розв’язку або доведено, що задача не має допустимих розв’язків на множині цілих чисел.

У літературі доведено, що за певних умов алгоритм Гоморі є скінченним, але процес розв’язування задач великої розмірності методом Гоморі повільно збіжний.