Метод Гоморі (метод відсікаючих площин)

Метод відсікаючих площин існує у двох варіантах: перший варіант призначений для розв’язку повністю цілочисельних задач (перший алгоритм Гоморі) і другий варіант –  призначений для розв’язку частково цілочисельних задач (другий алгоритм Гоморі). Основна відмінність між ними полягає у способі формування відсікання.

Алгоритм знаходження розв’язку методом Гоморі для цілком цілочисельних задач нпступний:

1. Лінійна задача розв’язується класичним симплекс-методом, без врахування цілочисельності змінних . В результаті отримують деякий оптимальний опорний план, який має наступний вигляд:

   

2. Якщо (1) містить рівняння для яких базисниі змінні  мають дробові значення, то серед них обирають таке рівняння, яке має найбільшу дробову частину. Дане рівняння перетворюють у додаткову нерівність:

   

   де .

Для обрання чисел та існують наступні правила:

1) якщо дробові числа або є додатніми числами, то  та є цілими додатніми числами і дорівнюють цілій частині числа   або  відповідно. Приклад:

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

3) якщо   або є цілими числами, то і ;

4) додаткова нерівність (2) повинна містити лише додатні коефіцієнти. Вона множенням на -1 спочатку приводиться до вигляду, який повинна мати нерівністьу симплекс-методі згідно із стандартною формою:

а потім за допомогою додаткової змінної перетворюється у наступне рівняння:

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

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

Ознакою відсутності розв’язку задачі є наявність у таблиці хоча б одного рядка з цілими величинами  та вільним членом , значення якого містить дробову частину. Дана ознака вказує на відсутність розв’язку у цілих кислах.

Алгоритм знаходження розв’язку методом Гоморі для частково цілочисельних задачан алогічний цілочисельному алгоритму, тобто, так само вводяться додаткові обмеження:

де величини  визначається з наступних співвідношень:

1) для нецілочисельних значень змінних :

2) для цілочисельних змінних :