Метод відсікаючих площин існує у двох варіантах: перший варіант призначений для розв’язку повністю цілочисельних задач (перший алгоритм Гоморі) і другий варіант – призначений для розв’язку частково цілочисельних задач (другий алгоритм Гоморі). Основна відмінність між ними полягає у способі формування відсікання.
Алгоритм знаходження розв’язку методом Гоморі для цілком цілочисельних задач нпступний:
- Лінійна задача розв’язується класичним симплекс-методом, без врахування цілочисельності змінних
. В результаті отримують деякий оптимальний опорний план, який має наступний вигляд:
- Якщо (1) містить рівняння для яких базисниі змінні
мають дробові значення, то серед них обирають таке рівняння, яке має найбільшу дробову частину. Дане рівняння перетворюють у додаткову нерівність:
де
.
Для обрання чисел та
існують наступні правила:
1) якщо дробові числа або
є додатніми числами, то
та
є цілими додатніми числами і дорівнюють цілій частині числа
або
відповідно. Приклад:
2) якщо дробові числа або
є від’ємними числами, то
та
є від’ємними цілими числами, які по абсолютній величині на одиницю більші за абсолютну величину цілої частини числа
або
. Приклад:
3) якщо або
є цілими числами, то
і
;
4) додаткова нерівність (2) повинна містити лише додатні коефіцієнти. Вона множенням на -1 спочатку приводиться до вигляду, який повинна мати нерівністьу симплекс-методі згідно із стандартною формою:
а потім за допомогою додаткової змінної перетворюється у наступне рівняння:
яке додається до оптимального опорного плану системи (1) і сумусно з ним створює псевдоплан, який містить одне від’ємне значення ;
5) даний псевдоплан розв’язується двоїстим симплекс-методом. В результаті отримують новий оптимальний опорний план з додатніми значеннями та
. Якщо в новому оптимальному опорному плані існують змінні
, значення яких містять дробову частину, то знову додають одне додаткове обмеження, і процес розрахунків повторюється до отримання цілочисельних значень базисних змінних.
Ознакою відсутності розв’язку задачі є наявність у таблиці хоча б одного рядка з цілими величинами та вільним членом
, значення якого містить дробову частину. Дана ознака вказує на відсутність розв’язку у цілих кислах.
Алгоритм знаходження розв’язку методом Гоморі для частково цілочисельних задачан алогічний цілочисельному алгоритму, тобто, так само вводяться додаткові обмеження:
де величини визначається з наступних співвідношень:
1) для нецілочисельних значень змінних :
2) для цілочисельних змінних
: