22. Описати алгоритм методу Гоморі розвязку задач цілочислового математичного програмування.

Алгоритм, запропонований Гоморі, ґрунтується на використанні симплексного методу і передбачає застосування досить простого способу побудови правильного відтинання.

Суть його полягає:

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

за умов: ; ; — цілі числа .

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

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

де символ {} позначає дробову частину числа.

Для визначення дробової частини будь-якого числа від цього числа віднімають цілу його частину — найбільше ціле число, що не перевищує даного. Цілу частину числа позначають символом []. Наприклад,

[1,3] = 1; [1,3] = 2; {1,3} = 1,3  1 = 0,3; {1,3} = 1,3  (2) =2  1,3 = 0,7.

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

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