§ 2. Метод Лэнд и Дойг

2.1. Рассмотрим частично целочисленную задачу линейного программирования.

Минимизировать

при условиях

Здесь любые из отношений

Некоторые из чисел в (2.3) могут равняться В (2.4), как всегда, при этом, разумеется, не исключен и случай полностью целочисленной задачи

Многогранное множество, определяемое условиями предполагается ограниченным.

2.2. Приведем описание идеи метода Лэнд и Дойг. Рассматривается целочисленная (частично целочисленная) задача линейного программирования (2.1) — (2.4). Как и в методах отсечения, процесс начинается с решения соответствующей ей задачи линейного программирования Если полученный при этом оптимальный план не удовлетворяет условиям целочисленности (2.4), то значение целевой функции этом плане дает нижнюю границу для искомого оптимума, т. е. Пусть некоторая переменная где не получила в плане целочисленного значения. В оптимальном целочисленном плане значение должно быть либо уменьшено по крайней мере до либо увеличено по крайней мере до Если границы изменения заранее не заданы, то их можно вычислить, решив для этого две

вспомогательные задачи линейного программирования, заключающиеся в максимизации и минимизации при условиях Теперь для каждого фиксированного целочисленного значения в найденном отрезке можно искать путем решения задачи линейного программирования с ограничениями (2.2) и дополнительным ограничением

Все указанные возможности можно представить в виде некоторого дерева задач, в котором вершина отвечает исходному плану а каждая из соединенных с ней ветвью вершин отвечает оптимальному плану задачи вида: минимизировать при условиях (2.2) — (2.3) и дополнительном условии, что переменной придано конкретное значение Каждой из вершин приписывается граница равная минимальному значению для соответствующей задачи. Ясно, что для всех

Если оптимальные планы указанных задач удовлетворяют условию целочисленности, то план с минимальной границей и будет оптимальным планом исходной задачи. В противном случае возникает необходимость в дальнейшем разветвлении дерева из некоторых вершин, не удовлетворяющих условиям целочисленности; это осуществляется аналогичным образом. Разумеется, для разветвления следует каждый раз выбирать вершину с наименьшей границей. Любой путь в дереве от вершины до некоторой вершины определяет допустимую последовательность выбора целочисленных значений для переменных. Процесс продолжается до тех пор, пока дальнейшее ветвление становится невозможным. В ходе ветвления каждой вершине с минимальным еще не получившей границы, приписывается граница Каждая конечная вершина отвечает некоторому допустимому целочисленному плану; оптимальный план дает вершина с минимальным

2.3. Перейдем теперь к формальному описанию метода Лэнд и Дойг, останавливаясь на тех моментах общей схемы метода ветвей и границ, которые здесь требуют конкретизации.

1°. Задание множества Множество задается условиями

2°. Задание множеств Множество определяется условиями (2.2), (2.4) и дополнительным условием

3°. Вычисление границ (оценок). Для множества оценка где оптимальный план задачи линейного программирования (2.1) — (2.3).

Для множества оценка где оптимальный план задачи линейного программирования (2.1), (2.2),

Если множество оказывается пустым (т. е. соответствующая задача неразрешима), то ему приписывается оценка

4°. Вычисление планов. Если удовлетворяет условию целочисленности (2.4), то оптимальный план задачи

Если X удовлетворяет условию целочисленности (2.4), то X является оптимальным планом задачи (2.1), (2.2), (2.3), (2.4) и планом исходной задачи (2.1) — (2.4).

5°. Ветвление. Необходимость ветвления возникает в том случае, когда план не удовлетворяет условию целочисленности (2.4). Пусть одна из нецелочисленных компонент этого плана (где Тогда множество разбивается на два множества:

где

Замечание. Если все коэффициенты в (2.1) целые при и равны нулю при то оценку

можно заменить на более сильную оценку

Здесь символом ]а[ обозначено наименьшее целое число, не меньшее чем а.

Таким образом, в чисто вычислительном отношении этот алгоритм сводится к решению серии задач линейного программирования. Конечность алгоритма Лэнд и Дойг непосредственно следует из предположенной выше ограниченности множества (2.2) — (2.3).

2.4. Приведем небольшой численный пример, решенный в п. 2.6 гл. 5 с помощью 1-го алгоритма Гомори. Минимизировать

при условиях

0-й шаг. Оптимальный план задачи линейного программирования

Имеем План не удовлетворяет условию целочисленности (2.11). Возьмем его нецелочисленную компоненту и разобьем множество на два множества:

где

1-й шаг. Решим две задачи линейного программирования, заключающиеся в минимизации (2.8) по множествам и

В первом случае минимум достигается при Множество же оказывается пустым, так что для него имеем Производим разветвление из

где

Переобозначения:

2-й шаг. Решаем две задачи линейного программирования, заключающиеся в минимизации (2.8) по множествам Получаем

Производим разветвление из множества

где

Переобозначения:

3-й шаг. Решаем две задачи линейного программирования, заключающиеся в минимизации (2.8) по множествам Получаем

Получен целочисленный план причем

Поэтому план оптимальный.

2.5. Прослеживая за выполненными в ходе вычислений операциями, нетрудно уяснить себе геометрическую интерпретацию метода Лэнд и Дойг. Грубо говоря (здесь удобнее говорить о задаче максимизации), она заключается во вдавливании гиперплоскости, определяемой поверхностью уровня целевой функции в многогранник планов соответствующей задачи линейного программирования до встречи с ближайшей точкой этого многогранника, удовлетворяющей условиям целочисленности.

Из описания метода Лэнд и Дойг ясно, что в его осуществлении для полностью целочисленных и частично целочисленных задач никакой разницы нет. Сведения о машинной реализации этого метода пока не публиковались; известно лишь, что в 1965 г. он был запрограммирован. Из самых общих соображений ясно, что этот метод должен быть довольно эффективным для частично целочисленных задач со сравнительно небольшим количеством целочисленных переменных, а также для задач специальной структуры. Последнее соображение убедительно подтверждается успешностью применения общей идеи ветвей и границ к задаче коммивояжера (метод Литтла, Мурти, Суини и Кэрел); этот метод будет описан в следующем параграфе.