Рассмотрим математическую модель ЗЛЦП с неделимостями. Для функции (1) (найти max) при условии

Пусть условия (2) и (3) определяют некоторый многогранник, или множество решений D⁽¹⁾ , а условия (2), (3), (4) определяют решение D_y – совокупность целочисленных решений ЗЛЦП.

a_ij, b_i — целые

Решаем исходную ЗЛП, которая определяется условиями (1), (2), (3). на D⁽¹⁾ симплекс методом. Пусть — оптимальное решение и . Если решение целочисленное, то это и есть оптимальный план исходной задачи.

Пусть план не является целочисленным. Тогда в качестве оценки множества j( D⁽¹⁾) берем значение .

Пусть в плане его координата не целочисленна. Тогда естественно предположить, что в оптимальном челочисленном плане эту координату надо либо уменьшить по крайней мере до целой части числа , либо увеличить по крайней мере до значения +1.

// Целая часть числа а – это наибольшее целое, которое не превосходит это число.

Это соображение положено в основу разбиения множества D⁽¹⁾:

Пусть обе задачи разрешимы и оптимальным решением 1 ЗЛП является , а второй — , тогда оценка 1- го подмножества

Если какая – то задача неразрешима, то оценкой соответствующего подмножества является ? и оно исключается из рассмотрения.

Из двух полученных оценок выбираем наибольшую. Если соответствующий ей план является целочисленным, то задача решена, это и есть оптимальное решение исходной задачи (1) – (4).

Если наибольшей оценке соответствует нецелочисленный план, то соответствующее подмножество будем разбивать на 2 подмножества аналогично тому, как разбивали множество D⁽¹⁾. Процесс вычислений заканчивается когда среди всех неподвергающихся делению подмножеств найдется подмножество с наибольшей оценкой, которой будет соответствовать целочисленное решение. Это и будет оптимальное решение исходной ЗЛЦП.