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

ГЛАВА 19

О СООТНОШЕНИИ МЕЖДУ ЛИНЕЙНЫМ И ЦЕЛОЧИСЛЕННЫМ ПРОГРАММИРОВАНИЕМ Ц

19Л. Введение (Гомори [84], Кортанек и Ярослав [133])

В § 13Л для получения отсечения (9) мы использовали урав­ нение (4). При построении отсечения мы требовали, чтобы левая часть уравнения (4) была целой (необязательно неотрицательной), а переменные в правой части уравнения — целыми и неотрица­ тельными. Следовательно, в качестве производящей строки можно использовать любую целочисленную комбинацию уравнений, подобных (4), и отсечение Гомори можно получить из нее. Так ■как существует бесконечно много целочисленных комбинаций, то из данной таблицы можно получить бесконечно много произво­ дящих строк. Казалось бы, можно добавить сколь угодно много отсечений. Тем не менее будет показано, что имеет смысл добав­ лять только конечное число отсечений. Любое другое отсечение, полученное из таблицы, является следствием одного из них.

Используем вектор-строку R* = (r0, rt, . . ., гп) для обозна­ чения производящей строки, вектор-строку F £ — (/0, Д, . . ., / п)

если Rг и R; отличаются на вектор с целочисленными компонен­ тами. Далее, пусть Rt и R2 — любые две производящие строки

и п — произвольное целое число. Тогда

ф (Ri + Иг) = ф (Hi) + ф(R2) — Ft -f- F2

и

ф(rcRi) = пф (Rj) = »Ft.

Д Многие из результатов гл. 19 и 20 являются перефразировкой или непосредственным изложением статьи Гомори [86]. Читателю обязательно придется обращаться к подлиннику, так как многие теоремы и доказатель­ ства здесь не приводятся. Автор благодарит Американское издательство Elsevier и корпорацию IBM за разрешение использовать в работе эти мате­ риалы.

380 ГЛ. 19. ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ

откуда

Уравнение (1) можно рассматривать как систему уравнений, где неизвестными являются компоненты вектора а;. По правилу Кра­ мера каждая компонента вектора есть отношение двух опреде­ лителей, причем знаменателем является определитель матрицы В0. Пусть | det В0 | = D. Тогда D равно абсолютной величине

ведущего элемента, а каждая компонента вектора а* имеет вид h/D, где h — целое. Рассмотрим соотношение между исходной матрицей А0 и текущей матрицей А*. Имеем

АоВ^В; 1 . . . B l i i - A ,

или

А0 = A;B;_iB(_2 . . . В0 = А*В.

Так как det В = det B(_i det Вг_2 . . . det В0, то каждый эле­

мент матрицы А( имеет вид hID, где D теперь обозначает абсолют­ ную величину произведения последовательно получающихся веду­ щих элементов, и h — целое.

Если в циклическом алгоритме сохранять все отсечения Гомори, число строк будет возрастать. Отсечения Гомори являются полностью целочисленными неравенствами, если они выражены через исходные небазисные переменные. Таким образом, их мож­ но представить как часть исходной полностью целочисленной матрицы.А0, а приведенные выше рассуждения можно использо­ вать для доказательства следующей теоремы.

Т еорема 19.1. Каждый элемент таблицы, используемой е цик­ лическом алгоритме, имеет вид h/D, где h — целое, a D — произ­ ведение ведущих элементов последовательно получаемых при пере­ ходе от исходной таблицы к данной.

Мы умножали полностью целочисленную матрицу А на обрат­ ную матрицу В- 1 и затем брали дробные части вектор-строк АВ-1.

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

тор-строк ф (АВ-1). Тем не менее результаты, полученные в одной формулировке, останутся справедливыми также и в другой.

Рассмотрим вектор-столбцы с т компонентами. Эти векторстолбцы с обычной операцией сложения образуют абелеву группу. Через R обозначим пг-мерные векторы с действительными ком­ понентами, а через Z соответственно /?г-мерные векторы с целыми компонентами. Пусть т — абелева группа действительных

m-мерных векторов *). Ясно, что {Z} является подгруппой {Я}ичто любой m-мерный вектор с действительными компонентами при­ надлежит {R}, а любой m-мерный вектор с. целочисленными ком­

порожденную вектор-столбцами из А. Любой вектор, который

П

2

5=1 (А ). Если матрица А содержит единичную матрицу размерности

т X т, то {А} = {Z}; в общем случае {А} будет подгруппой группы {Z}.

Предположим, что ранг матрицы А равен т, и что подматрица В = [Ьь . . ., bm] матрицы А также имеет ранг т. Мы можем аналогично рассмотреть абелеву группу {В}, порожденную вектор-

столбцами В. Таким образом, элементы группы {В} имеют вид

т

2 Hjhj, где rij — целые. Так как А и В имеют одинаковый ранг,

5 = 1

то любой вектор-столбец aj из А можно представить как линейную комбинацию векторов Ьг (i = 1 , . . ., т) с действительными, но

не обязательно целыми коэффициентами. Таким образом, в общем

R==R-|-Z, a = a -|-Z a).

Тогда {а} —абелева группа, порожденная ■дробными частями вектор-столбцов из а с операцией сложения по модулю 1 .

Итак, используя В-1, отобразим группу {А} в {а} и, далее,

посредством ф отобразим {а} в {а}. Символически это запишется так:

{А) ———> {а} —— {а}.

Легко проверить, что произведение отображений фВ-1, кото­ рое переводит {А} в {а }, является гомоморфизмом.21

1)Имеются в виду группы относительно операции обычного алгебраи­ ческого сложения векторов.— Прим. ред.

2)В соотношении a = а + Z под Z понимается целочисленная матрица соответствующей размерности.— Прим, перев.