Изложение метода Ленд-Дойга.

Решается вспомогательная ЗЛП (13.1)(13.3), которая получена из исходной ЦЗЛП (13.1)(13.4) отбрасыванием условия целочисленности переменных (13.4) (ветка 0;1). Если ее решение x(0;1) — целочисленный, то он же является и решением исходной ЦЗЛП. Иначе величина x(0;1)=L(x(0;1)) дает нижнюю оценку (границу) целевой функции ЦЗЛП на множестве D(0;1)=D, что определяется соотношениями (13.2) (13.3).

Пусть некоторая координата xj(0;1) (j=1...,n) решения x(0;1) не является целочисленной. В этом случае осуществляется разветвление множества D(0;1) на два подмножества D(1;1) и D(1;2) добавлением к ограничениям, которые задают D(0;1), ограничений xj£[xj(0;1)] но xj³[xj(0;1)]+1 соответственно, где [z] — целая часть числа z. Дальше Решаются новые вспомогательные ЗЛП с ограничениями, которые определяются подмножествами D(1;1) и D(1;2), находятся границе x(1;1) но x(1;2) и т.д.

Для последующего разветвления выбирается перспективное множество D(k;r) с наименьшей границею x(k;r). Процесс продолжается до тех пор, пока не будет получено решение, которое удовлетворяет условие целочисленности и для которого выполняется признак оптимума (см. п. 4 алгоритма). В результате ограниченности допустимого множества ЗЛП (конечности допустимого множества ЦЗЛП) метод Ленд-Дойга конечный.