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