§ 5. Алгоритм Данцига

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

Гофман [91] (их рассуждения будут воспроизведены ниже), конечность алгоритма Данцига гарантируется лишь для очень узкого класса задач. На примере алгоритма Данцига видно, насколько тонким является вопрос о построении правильных отсечений и сколь осторожно следует подходить к различным упрощенным алгоритмам.

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

Максимизировать

при условиях

Ранг матрицы считаем равным

5.2. Теорема 5.1. Пусть является оптимальным опорным планом задачи и не удовлетворяет условию целочисленности, множество индексов, нумерующих небазисные переменные, соответствующие

Тогда неравенство

является правильным отсечением.

Доказательство теоремы 5.1. Сначала проверим условие отсечения. Действительно,

так что условие отсечения выполнено.

Переходим к проверке условия правильности. Так как план однозначно определяется своими небазисными

переменными, то для любого плана X задачи не совпадающего с планом

причем для любого плана X задачи из целочисленности переменных следует, что

5.3. Правильное отсечение, отсекающее нецелочисленный оптимум задачи можно записать следующим образом:

Заметим, что каждая из вновь вводимых переменных однозначно определяется заданием переменных так что

5.4. Обозначим через упорядоченные в порядке возрастания компоненты плана X задачи (5.1) — (5.3), так что

Положим

5.5. Лемма 5.1. Если для некоторого плана X задачи

то

Доказательство проведем по индукции. Сначала докажем, что

По определению

Так как ранг матрицы равен то

где - число элементов множества Из определения чисел получаем

Из (5.10), (5.11), (5.12) и (5.8) имеем

Лемма доказана при

Теперь допустим, что лемма верна при и докажем ее при

Лемма доказана.

Пользуясь леммой, докажем две теоремы. 5.8. Теорема 5.2. Яялы каждый оптимальный план задачи содержит не менее положительных компонент, то алгоритм Данцига не будет конечным.

Доказательство. Допустим, что на 5-й итерации алгоритма Данцига получится искомый оптимальный план Рассмотрим числа

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

По определению чисел отсюда следует, что

а так как должно быть целым, то

Но по определению чисел

Из (5.14) получаем

и по лемме 5.1

Из (5.14), (5.15) и (5.17) следует, что среди чисел (5.13) по крайней мере положительных, а следовательно, не больше чем нулей. Но выше было отмечено, что среди чисел (5.13) должно быть нулей. Получилось противоречие. Теорема 5.2 доказана.

5.7. Следствие 5.1 (из теоремы 5.2). Для того чтобы алгоритм Данцига был конечным, необходимо, чтобы искомый оптимальный план лежал на ребре многогранного множества (предполагается, что задача невырожденная).

Хотя это условие и является весьма жестким, ему удовлетворяют, например, все (невырожденные) задачи следующего вида:

Максимизировать

при условиях

А это важный класс задач (см. гл. 2 и 3).

5.8. Однако приведенное в следствии 5.1 необходимое условие конечности алгоритма Данцига не является статочным. Действительно, имеет место следующая

Теорема 5.3. Если для некоторого оптимального плана X задачи (5.1) — (5.4) и некоторого плана задачи имеют место неравенства

и

то алгоритм Данцига не будет конечным.

Доказательство. Допустим, что алгоритм Данцига конечен. Тогда из (5.23) следует, что точка была отсечена на некоторой (скажем, итерации, так что

Но из (5 24) и леммы 5.1 получим

Сравнивая (5.25) и (5.26), получаем противоречие. Теорема 5.3 доказана. Итак, упрощенный алгоритм Данцига будет конечным лишь в весьма редких случаях.

5.9. Приведем простой численный пример, когда искомый целочисленный оптимум является внутренней точкой многогранника планов и алгоритм Данцига не является конечным.

Максимизировать

при условиях

Оптимальный план является внутренней точкой многогранника планов.