Метод Ленд и Дойг


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

Метод Ленд и Дойг

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

aij, bi — целые

clip_image006

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

Пусть план clip_image010[2] не является целочисленным. Тогда в качестве оценки множества j( D(1)) берем значение clip_image014.

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

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

Это соображение положено в основу разбиения множества D(1):

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

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

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

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