Методы отсечения (стр. 5 из 6)
– целые, 
(42)Ранг матрицы
считаем равным m.Теорема. Пусть x(£r, C)=xr является оптимальным опорным планом задачи (£r, C) и xr не удовлетворяет условию целочисленности, Nr – множество индексов, нумерующих небазисные переменные, соответствующие xr.
Тогда неравенство
(43)является правильным отсечением.
Правильное отсечение, отсекающее нецелочисленный оптимум x(£r, C) задачи (£r, C), можно записать следующим образом:
– целое.
Заметим, что каждая из вновь вводимых переменных 
однозначно определяется заданием переменных 
, так что 
.
Обозначим через 
упорядоченные в порядке возрастания компоненты плана x задачи (39) – (41), так что
(44)
Положим
(45)Лемма. Если для некоторого плана x задачи (39) – (41)
, (46)
то
(47) Доказательство проведем по индукции. Сначала докажем, что
(47¢)По определению
(48)Так как ранг матрицы
равен m, то 
где 
– число элементов множества 
. Из определения чисел 
получаем
(49) 
(50)Из (48), (49), (50) и (46) имеем
Лемма доказана при р=1.
Теперь допустим, что лемма верна при 
, и докажем ее при 
:
Лемма доказана.
Пользуясь леммой, докажем две теоремы.
Теорема 1. Если каждый оптимальный план задачи (39) – (42) содержит не менее (m+2) положительных компонент, то алгоритм Данцига не будет конечным.
Доказательство. Допустим, что на s-й итерации алгоритма Данцига получится искомый оптимальный план
. Рассмотрим числа 
(51)Все они целые и среди них должно быть (n-m) нулей – это небазисные переменные
. Кроме того, по условию среди чисел 
, должно быть по крайней мере (m+2) положительных числа, т.е. не больше чем (n-m-2) нулей.По определению чисел
отсюда следует, что 
а так как
должно быть целым, то 
(52)Но по определению чисел
(53)Из (52) получаем
(54)и по лемме
(55)Из (52), (53) и (55) следует, что среди чисел (51) по крайней мере [1+(m+1)+s] = [m+2+s] положительных, а следовательно, не больше чем [n+s – (m+2+s)] = (n-m-2) нулей. Но выше было отмечено, что среди чисел (51) должно быть (n-m) нулей. Получилось противоречие. Теорема 1 доказана.
Следствие (из теоремы 1). Для того чтобы алгоритм Данцига был конечным, необходимо, чтобы искомый оптимальный план лежал на ребре многогранного множества (40) – (41) (предполагается, что задача (39) – (41) невырожденная).
Хотя это условие и является весьма жестким, ему удовлетворяют, например, все (невырожденные) задачи следующего вида.
Максимизировать
(56)при условиях
(57) 
(58) 
(59) 
– целое, 
(60)А это важный класс задач.
Однако приведенное в следствии необходимое условие конечности алгоритма Данцига не является достаточным. Действительно, имеет место следующая
Теорема 2. Если для некоторого оптимального плана x' задачи (39) – (42) и некоторого плана x» задачи (39) – (41) имеют место неравенства
(61)
и
(62)то алгоритм Данцига не будет конечным.
Доказательство. Допустим, что алгоритм Данцига конечен. Тогда из (61) следует, что точка x» была отсечена на некоторой (скажем, р-й) итерации, так что
(63)Но из (62) и леммы получим
(64)Сравнивая (63) и (64), получаем противоречие. Теорема 2 доказана.
Итак, упрощенный алгоритм Данцига будет конечным лишь в весьма редких случаях.
7. Некоторые выводы
Попробуем охарактеризовать поведение алгоритмов метода отсечения при решении задач целочисленного линейного программирования. В качестве меры продолжительности вычислений могут рассматриваться количество симплексных итераций I и количество правильных отсечений (дополнительных линейных ограничений) D.
Для первого алгоритма Гомори и различных его обобщений I и D также тесно связаны между собой (как показывает эксперимент, в большинстве случаев решение отдельной задачи (£, С) требует сравнительно небольшого количества симплексных итераций).
Переходим к изложению отдельных свойств алгоритмов метода отсечения.
Числа I и D имеют (в среднем) тенденцию к возрастанию с увеличением числа переменных и ограничений, ростом порядка коэффициентов задачи и увеличением заполненности матрицы
.Это явление кажется естественным, но опыт показывает, что в дискретном программировании «естественное» и «правдоподобное» не всегда оказывается правильным. Точнее говоря, опыт, накопленный на задачах ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ, нельзя механически переносить на задачи ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.
Прежде всего, обращает на себя внимание «нерегулярность», «непредсказуемость» поведения алгоритмов метода отсечения. Для ряда задач оптимальное решение не удавалось получить после многих тысяч итераций, в то время как другие задачи решались за несколько десятков итераций.
Не удается установить непосредственную связь между размерами задач (т.е. числом ограничений m и переменных n) и числом итераций: неудачи были зафиксированы даже для небольших задач (m≤10, n≤10), а успехи – для задач достаточно большого размера (m = 215, n = 2600). Возможно, впрочем, что попытка установления подобной связи – это неправомерное перенесение результатов ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ в область ЦЕЛОЧИСЛЕННОГО ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ.