Метод Гоморі

Перший алгоритм Р. Гоморі полягає в наступному:

Нехай задана повністю цілочисельна лінійна задача:

(5.2)

(5.3)

Нехай в результаті лінійних операцій над рівняннями системи (5.3) отримано нове лінійне рівняння

(5.4)

Цілою частиною числа називається найбільше ціле число , яке не перевищує . Наприклад ; .

Замінивши в рівнянні (5.4) всі коефіцієнти їх цілими частинами, отримаємо:

(5.5)

Якщо всі є цілочисельними, то ліва частина рівняння (5.5) теж цілочисельна. Рівняння (5.5) можна посилити таким чином:

(5.6)

Це обмеження-нерівність (4.6) можна перетворити в обмеження-рівняння шляхом введення додаткової цілочисельної і ненегативної змінної : (5.7)

Віднімемо (5.4) з (5.7). Враховуючи, що , отримаємо:

(5.8)

У першому методі Гоморі всі обмеження формуються відповідно до рівнянь (5.8) – це і є відсікання нецілочисельних точок.

Фактично (5.8) – рівняння відсікаючої гіперплощини. Після вирішення задачі лінійного програмування одержуємо деяке базисне рішення, в якому деякі змінні можуть бути цілочисельними, а інші – нецілочисельними. Для нецілочисельних базисних змінних будуємо відсікання за першим алгоритмом Гоморі, послідовно для кожної з них. Якщо нецілочисельних змінних декілька, то краще вибрати ту, в якої більше дробова частина. Якщо рівняння вибраної базисної змінної має вигляд

, (5.9)

то рівняння додаткового обмеження-відсікання виглядає таким чином:

. (5.10)

Побудова відсікання - «велика ітерація». Далі для звуженої області проводять «малі ітерації».

Вирішення задач цілочислового лінійного програмування можуть бути відсутні, якщо:

1) цільова функція є необмеженою знизу, тобто як початкова нецілочисельна, так і цілочисельна задачі лінійного програмування не мають рішення;

2) початкова задача лінійного програмування має рішення, а цілочисельна не має. У симплекс-таблиці це видно таким чином: у стовпці вільних членів у деякому рядку стоїть неціле число, а вся решта коефіцієнтів цього рядка ­– цілі числа.

Збіжність даного алгоритму достатньо повільна. Для задачі з 10-ма змінними необхідно провести порядку 1000 ітерацій.

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

Округлення нецілочисельного рішення до найближчого цілого може дати точку, що не належить області.

Другий алгоритм Р. Гоморі:

Застосовується для вирішення як повністю, так і не повністю цілочисельних задач. Багато індексів при змінних розбивають на дві неперекресні підмножини і так, що:

при , ( - цілочисельні);

при , ( - нецілочисельні).

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

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

, (5.11)

де - вільна змінна.

Тоді за другим алгоритмом Гоморі відсікання будуємо таким чином:

, (5.12)

де (5.13)