Приклад 2.

варіанти:

1. Перший алгоритм Гоморі для рішення повністю цілочисельних задач.

2. Другий алгоритм Гоморі для рішення частково цілочисельних задач.

Ідея розрахунків методом відтинаючих площин для розв’язання повністю цілочисельних задач (1-й метод Гоморі) полягає у такому підході:

1) лінійна задача (1)

(1)

Опорний план, який має канонічний вигляд:

(2)

2) якщо серед рівнянь-обмежень (2) є дробові значення базисних змінних x_i = b_i, то обирають серед них таке значення, яке має найбільшу дробову частину. Це рівняння

Перетворюють у додаткову нерівність:

(3)

Правила обрання чисел [a_ij] та [b_i]:

1. Якщо дробові числа a_ij або b_i є додатними числами, то [a_ij] та [b_i] є цілими додатними числами і дорівнюють цілій частині числа a_ij або b_i. Наприклад:

2. Якщо дрібне число a_ij або b_i є від’ємним числом, то [a_ij] та [b_i] є від’ємним цілим числом, яке за абсолютним значенням на “1” більше за абсолютне значення цілої частини числа a_ij або b_i. Наприклад:

Якщо a_ij або b_i є цілими числами, то α_ij =0, β_i =0.

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

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

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

Часткові цілочислові задачі (в них вимоги щодо цілочисельності ставляться лише до окремих змінних) розв’язуються так само, як попередні, за рахунок введення додаткового обмеження

,

де - визначається з відношень:

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

;

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

.