2.2. Метод відсікання Гоморі

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

усі ³ 0 та цілі. (19)

Оскільки ми говоримо про повністю цілочислову задачу, то перед її зведенням до канонічної форми ми повинні перетворити задачу таким чином, щоб усі її коефіцієнти a_ij, b_i, c_j були цілими.

Нехай множина допустимих розв’язків задачі є непорожньою і зліченою. Розглянемо, як побудувати додаткові лінійні обмеження, які задовольняє кожний розв’язок, допустимий за умовами (18) - (19).

Розглянемо довільне лінійне обмеження, яке можна отримати за допомогою елементарних перетворень над лінійними обмеженнями (18). Тоді, якщо деякий розв’язок задовольняє (18) - (19), то він повинен також задовольнити і це рівняння. Нехай вираз

(20)

визначає саме таке обмеження.

Позначимо символом [a] цілу частину дійсного числа a - найбільше ціле, що менше або дорівює a. За визначенням [a]£a. Наприклад:

[ 12/5 ] = 2; [-12/5 ]= –3;

[ 2/15 ] = 0; [-2/15 ]= –1;

[ 5,6 ] = 5; [ –5,6 ]= –6.

Оскільки величини невід’ємні ((19)), і вони задовольняють обмеження (20), то вони також задовольнять і більш слабке обмеження, ніж (20):

(21)

Далі, оскільки сума в лівій частині (21) повинна бути цілочисельною, (21) можна посилити таким чином:

(22)

Рівняння (22) зветься рівнянням в цілих частинах. Його можна перетворити на рівність, додавши вільну змінну:

(23)

З рівняння (23) випливає, що на s також накладено умову невід’ємності та цілочисельності. Таким чином, якщо до умов (18), (19) додати лінійне обмеження (23), задача все одно залишиться повністю цілочисловою і її множина допустимих розв’язків не зміниться.

Визначимо та - дробові частини чисел і - тотожностями:

За визначенням дробові частини є не від’ємним. Наприклад:

• дробова частина числа 12/5 дорівнює 2/5;

• дробова частина числа –12/5 складає 3/5;

• дробова частина числа 1/3 дорівнює 1/3;

• дробова частина числа –1/3 дорівнює 2/3;

• дробова частина числа 3 дорівнює 0;

• дробова частина числа -3 дорівнює 0.

Віднімаючи почленно з рівняння (23) рівняння (20), отримаємо обмеження, що складається лише з дробових частин:

(24)

Це перетворення є елементарним, а це означає, що множина допустимих розв’язків системи (18), (19), (23) збігається з множиною допустимих розв’язків системи (18), (19), (24).

Рівняння (24) називається рівнянням відсікання, а рівняння (20), за яким побудували рівняння відсікання, зветься породжуючим рівнянням. Задача (17) – (19), (24) з додатковим обмеженням-відсіканням називається розширеною.

2.3. Схема алгоритму Гоморі

Крок 1. Знайти оптимальний розв’язок послабленої задачі.

Крок 2. Припинити обчислення, якщо поточний розв’язок ЗЛП є цілочисловим. В іншому випадку вибрати дробову базисну змінну . Скласти рівняння відсікання за рівнянням, що містить цю базисну змінну в поточному оптимальному розв’язку ЗЛП. Тобто, якщо i -й рядок симплекс-таблиці має вигляд:

^{(породжуюче рівняння)}

(підсумовування ведеться за небазисними змінними j; b_i - дробове значення змінної ), то додаткове обмеження має вигляд:

^{(рівняння-відсікання),}

де - дробова частина ; - дробова частина .

Крок 3. Додати до вхідної задачі це рівняння-відсікання; знайти за допомогою двоїстого симплекс-методу³ оптимальний розв’язок розширеної задачі та повернутися на крок 2.

Алгоритм Гоморі має наступні особливості:

1. Загальна кількість обмежень розширеної задачі не може перевищувати кількість n змінних вхідної задачі у канонічній формі. Якщо розширена задача містить більш ніж n обмежень, то одна або декілька вільних змінних s, зазначених відсіканням Гоморі, повинні стати базисними. У цьому разі відповідні рівності стають надлишковими і можуть бути виключені з таблиці (приклад 5).

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

2. Якщо у стовпці β вільних членів (стовпці "Розв’язок") є від’ємний коефіцієнт, і при цьому всі коефіцієнти відповідного рядка є невід’ємними, то ЗЦЛП буде нерозв’язною (не має допустимих розв’язків) (приклад 6).