Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

294 ГЛ. 13. ЦИКЛИЧЕСКИЙ АЛГОРИТМ

([а0] обозначает наибольшее целое, не превосходящее а0). Из урав­ нения (1) получим отсечение Гомори

В исходной таблице все коэффициенты ац — целые, а любая переменная х (базисная или нет) представлена в виде целочислен­ ной комбинации исходных небазисных переменных. Это означает, что правая часть уравнения (1 ) также должна быть представима

в виде целочисленной комбинации исходных небазисных пере­ менных Xj.

Пусть

где п0 = ?ij = 0 (mod 1 ), т. е. правая часть равенства (3) есть

целочисленная форма относительно исходных небазисных пере­ менных.

В 2-й таблице х = [а„] + /о- Из уравнений (1) и (3) получаем

Уравнение (4) определяет гиперплоскость, проходящую через оптимальную вершину выпуклого множества в пространстве Xj. Мы утверждаем, что между гиперплоскостью (4) и гиперплоско­ стью

нет целочисленных точек. Действительно, если бы такая точка

в положение (5), при этом все допустимые целочисленные точки

xt = 1 0 — 3£t — 2 х 2 > 0 и хъ = И — хх — 4 ^ 2 ^ 0 .

Тогда х4 + 1х5 = 87 — Юа^ — 30^2 ^ 0 или Xi + Ъх2 ^ 8,7.

Откуда получаем отсечение Гомори

Xi + Зх2 ^ 8 .

296 ГЛ. 13. ЦИКЛИЧЕСКИЙ АЛГОРИТМ

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

вой и в этом случае.

На рис. 13.2 показано, что отсечение 23= 0 , использован­ ное в примере 1 , является не­

равенством с целыми коэффи­ циентами при исходных неба­ зисных переменных.

Заметим, что для получения новой производящей строки могут быть использованы цело­ численные комбинации уравне­ ний вида (1 ); скажем, сумма

одного уравнения, умноженного на 5, и другого, умнояаднного на (—7). В таком случае левая часть производящей строки может и не быть неотрицательной. Однако если внимательно проследить, как было получено отсечение (9) в § 13.1 из уравнения (4), то выяснится, что для левой части урав­ нения (4) требовалась только целочисленность. Процесс алге­ браического сложения соотношения 0 = Xj (mod 1 ) соответствует

алгебраическому сложению строк таблицы с единичной строкой

13.4. Свойства дополнительных неравенств (Гомори и Баумоль [87])

В этом параграфе будут приведены некоторые свойства допол­ нительных неравенств. Во-первых, будет показано, что дополни­ тельное неравенство вида

где х\ — текущие небазисные переменные, становится неравен­ ством с целочисленными коэффициентами, если его выразить через исходные небазисные переменные. Чтобы понять это утвер­ ждение, предположим, что рассматриваемое неравенство (1 )

является первым дополнительным неравенством, а производящая строка имеет вид

задачи (1) в § 13.1. Каждую переменную х1. можно выразить через

~'E.an+j. ;£;• Таким образом, х1 в уравнении (2) будут выражены.

г

через исходные небазисные переменные.

Поскольку любая переменная выражается через исходные небазисные единственным образом, уравнение (2 ) должно приво­

диться к виду уравнений (1) в § 13.1, т. е. либо

П

х*. ■ х и либо xi = arHi, о— 2 an+i,jXj. i=i

В обоих случаях правая часть содержит только целочисленные

Первая скобка содержит только целые коэффициенты, поскольку [а*], [а]\ — целые части от а\ и а] соответственно. Вторая скобка, как только что было показано, также должна быть целочисленной комбинацией исходных переменных. Поэтому новое неравенство st ^ 0 содержит лишь целочисленные коэффициенты, если его выразить через исходные переменные. Показав справедливость утверждения для первого дополнительного неравенства, мы можем повторить доказательство и для второго, считая первое частью исходной задачи и т. д.

Таким образом, доказано, что дополнительные ограничения Гомори представляют собой целочисленные комбинации исходных небазисных переменных. Исследуя выражение (1) более подробно^ можно сделать еще ряд заключений. Рассмотрим первое дополни­ тельное ограничение Гомори в виде (1). Разобьем множество

переменных х\ на два подмножества J и / . К J отнесем те х), которые являются исходными небазисными переменными, а к / — х], являющиеся исходными базисными переменными. Выразив;

Все члены в левой части неравенства (5) положительны, кроме —/ го, где 0 < /;о < 1. Следовательно, левая часть неравенства (5)- строго больше, чем (—1). Кроме того, выше было доказано, чтонеравенство (4) содержит только целочисленные коэффициенты,.

а в левой части неравенства (5) нет переменных, т. е. левая часть есть целое число. Таким образом, левая часть неравенства (5) есть неотрицательное целое число.

Рассмотрев правую часть неравенства (5), можно увидеть, что коэффициенты при переменных представляют собой либо

Рассмотрим особый случай, когда все коэффициенты исходной таблицы неотрицательны. В этом случае 2 fi)aik — неотрицатель-

3EJ

ное число, и, более того, (поскольку было доказано, что все коэф­

Поскольку левая часть этого неравенства представляет собой коэффициент при некоторой переменной xh, она должна быть

целым числом. Поэтому выражение 2 fuajk — fa есть неотрица­ тельное целое, т. е. 0, 1, 2 . . . . Проведенные рассуждения отно­ сились к первому дополнительному неравенству, однако это неравенство можно рассматривать как часть исходной задачи и тогда применить доказательство ко второму дополнительному неравенству и т. д.