Метод Гоморі

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

Нехай одержано оптимальний розв’язок , який не э цілочисловим, тоді останній крок можна представити у вигляді симплексної таблиці, де - ранг системи обмежень; - коефіцієнт симплексної таблиці -го рядка -го стовпця; - вільний член -го рядка.

			...		...			...
			...		...			...
...	...	...	...	...	...	...	...	...	...	...
			...		...			...
...	...	...	...	...	...	...	...	...	...	...
			...		...			...

Нехай і хоча б одне з () – дробові числа.

Позначимо через і цілі частини чисел і .

Цілою частиною числа називається найбільше ціле число, яке не перевищує .

Позначимо через і цілі частини чисел і .

Дробовою частиною чисел і називається різниця та .

П риклад:

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

Зауваження:

1. Якщо (вільний член) – дробове число, а всі коефіцієнти - цілі числа, тоді задача лінійного програмування не має цілочислового розв’язку.

2. Обмеження цілочисельності може бути накладене не на всі змінні, а лише на їх частину. У цьому випадку задача є частково цілочисловою.