Загальна постановка задачі. Деякі задачі лінійного програмування вимагають цілочислового розв’язку

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

з обмеженнями

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