10. Опишіть алгоритм методу Гоморі.

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

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

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

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

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

.

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