20.7. ХАРАКТЕРЫ II НЕРАВЕНСТВА |
447 |
тить, что столбцы В - 1 с операцией сложения по модулю 1 порож дают группу G, в то время как дробные части строк В - 1 , исполь
зованные для определения | г, порождают изоморфную группу характеров.
Рассмотрим, как для данной задачи строятся отсекающие пло скости из граней многогранника Р (Я , g0), где Я — циклическая
группа порядка D — | det В |. Для данной задачи целочисленного программирования найдем оптимальный базис В соответствующей задачи линейного программирования. Базис В определяет группу
G. Если | — характер, отображающий G в циклическую группу Я порядка D с элементами n/D (mod 1), то отсекающие плоскости для нашей задачи целочисленного программирования можно полу
чить из граней многогранника Р (Я , hQ).
Пусть (у, уо) — грань многогранника Р (Я , h0), где Я — циклическая группа порядка D. Для фиксированного характера | группы G определяем
Если t (g) задает путь в Я (G, Yg) от 0 до g0, т. е.
|
2 |
g-t(g)=go, |
|
|
то |
gen |
|
|
|
|
|
|
|
|
|
|
2 i(g )t(g )= l(g o ). |
|
|
Другими словами, |
отображение £ |
переводит |
путь в Н (G, у 0 |
в путь Н (Н,у). Длины двух путей одинаковы и равны |
|
|
2 |
Y [1(£)И (£)- |
|
|
|
g£ G |
|
|
|
|
По предположению (у, у0) — грань |
многогранника Р |
(Я, h0). |
Тогда компоненты у удовлетворяют неравенству |
у (h^ -|- |
у (fe2) |
У (hi + h2) или |
|
|
|
|
|
2 |
y [l(g)]t(g)>y\l(go)]- |
|
(3> |
Таким образом, (3) является неравенством, которое должно удовле творяться при любом t (g) из Р (G, go). Следовательно, (3) может быть использовано как отсекающая плоскость. Меняя характер
можно получить D — 1 неравенств из каждой грани Р (Я, h0).
Заметим, |
что |
в |
(3) не предполагается £ (g0) = h0. |
Как частный случай этого подхода рассмотрим грань много |
гранника |
Р |
(Я, |
hD_i) с компонентами у (hs) = s/D и у0 = |
= (Я — 1)/D. |
Тогда семейство полученных неравейств в точности |
4 4 8 ГЛ. 20. ГРАНИ ЦЕЛОЧИСЛЕННОГО МНОГОГРАННИКА
•совпадает с семейством отсекающих плоскостей, порожденных циклическим алгоритмом целочисленного программирования. В общем случае эти неравенства не являются гранями многогран ника Р (G, ц, go), хотя гранями они могут быть.
Рассмотрим численный пример (30) из § 19.2. Задачу в матрич ной форме можно записать так:
“ 1 - 2 |
- 1 |
|
- 1 |
0 |
0 |
2 |
1 |
0 |
3 - 4 |
|
4 |
|
z |
|
|
|
Xi |
|
|
0 |
х2 |
- О- |
|
0 |
|
1 |
х 3 |
41 |
|
0 |
(4) |
|
xk |
47 |
0 |
1 |
|
Хц
хч
Оптимальный базис состоит из первых трех столбцов, и мы имеем
|
|
|
|
|
|
|
|
|
z |
|
|
|
|
|
|
|
|
|
|
|
Xi |
|
|
|
" 1 |
0 |
0 |
2 1 / 6 |
5 |
2 |
1 1 / 6 |
4/ 6“ |
х2 |
1063/ G |
|
|
Х 3 |
|
|
0 |
1 |
0 |
2 |
3 |
1 |
4/6 |
2 / 6 |
43 |
(5) |
|
Xl |
|
0 |
0 |
1 |
3/6 |
2 |
1 |
3/6 |
0 |
_ 203/6_ |
|
хъ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Xq |
|
|
|
|
|
|
|
|
|
|
|
Х -1 |
|
|
|
Оптимальный базис имеет определитель, |
равный 6. |
|
|
Каждая строка г из (5) задает характер, |
который отображает G |
|
в циклическую группу порядка 6. |
Характеры £i, | 2 и 5з исполь |
|
зуют только |
дробные части |
элементов из |
(5), |
выписанные ниже |
с опущенным общим знаменателем:
|
Z |
Xi |
X2 |
Хз |
X4 |
хь |
Хв |
х7 |
Пр.ч. |
Si |
0 |
0 |
0 |
3 |
0 |
0 |
5 |
4 |
3 |
|
0 |
0 |
0 |
0 |
0 |
0 |
4 |
2 |
0 |
ь |
0 |
0 |
0 |
3 |
0 |
0 |
3 |
0 |
3 |
Поскольку правая часть состоит из 3, 0, 3, обращаемся к прило жению D для граней многогранника Р (G6, 3) (или используем
20.7. ХАРАКТЕРЫ И НЕРАВЕНСТВА |
449 |
§ 20.4, § 20.5). Грани приведены ниже:
|
|
7i |
7г |
Уз |
74 |
75 |
7о |
Грань |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
Грань 2 |
2 |
1 |
3 |
2 |
1 |
3 |
Грань |
3 |
1 |
2 |
3 |
2 |
1 |
3 |
Грань 4 |
1 |
2 |
3 |
1 |
2 |
3 |
Из первой строки (6) видно, что х3 соответствует у3, хв соот ветствует у5, а х7 соответствует у4. Таким образом, характер задает неравенства (по граням (7)):
по грани 1: 1х3 + 1хв+ 0х7^ 1;
по грани 2: Зж3 + l#e + 2х7 |
^ 3;(8) |
по грани 3: Зх3 -f- 1хв+ 2х7^ 3;
по грани 4: Зх3 -{- 2хв+ 1х7^ 3.
Характер | а не порождает ни одного неравенства, поскольку
правой частью является 0. Из §з мы видим, что х3 соответствует 7з> а хъ соответствует у 3. Таким образом, из (7) получаем нера венства:
1х3 + |
1ж6 > |
1; |
|
Зх3 + |
Зх3 ^ |
3; |
(9) |
Зх3 |
+ |
Зхв ^ |
3; |
Зх3 |
+ |
Зх6 ^ |
3. |
|
Заметим, что в процессе получения неравенств нет необходи мости знать, какой элемент группы какому базисному столбцу соответствует. Мы используем £г непосредственно. Исключая дублирующие неравенства из (8) и (9), получаем
Зх3 -)- Зхв |
|
|
3, |
|
Зх3 |
-f- х3 -f- |
2х7 |
^ |
3, |
(10) |
З;г3 |
-{—2хв |
х7 |
|
3. |
|
Если бы мы воспользовались циклическим целочисленным алгоритмом, то получили бы следующее множество неравенств, более слабое, чем (10):
З:г3 |
-{- 5х3 -}- 4х7 3, |
Зх3 |
+ Зхв |
3. |
ПРИЛОЖЕНИЕ А
НОРМАЛЬНАЯ ФОРМА СМИТА (ХУ [112|)
В этом приложении рассматривается преобразование полно стью целочисленной квадратной матрицы в нормальную форму Смита
■“в! |
О “ |
е2 |
J |
. |
_ 0 |
гт_ |
где ег делит ег+1 (t = 1, . . |
т — 1). |
Мы рассматриваем приведение матрицы к нормальной форме |
Смита как задачу нахождения нового множества базисных и еди
ничных векторов. (Поскольку |
все |
|
вычисления |
производятся |
по модулю D, будем предполагать, что элементы матрицы при |
нимают значения, заключенные |
между 0 |
и D — 1.) |
|
где |
Пусть b4, b2, . • |
bm — множество базисных |
векторов в Rm, |
|
Ь; = [ b i j , b 2j , . . - , b m j]. |
|
|
|
Тогда |
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
bjf — 2 |
ь i ./Сi |
, |
|
|
|
|
|
|
i= 1 |
|
|
|
|
|
где |
а — вектор-столбец, |
у которого |
i-я |
компонента |
равна 1, |
а |
остальные компоненты — нули. |
Выберем новое |
множество |
базисных векторов bj, |
b', |
. . ., Ь„ и новое |
множество |
единичных |
векторов el, такое, что |
|
|
|
|
|
|
|
|
bj = |
eje] |
для |
7 = |
1, |
|
|
|
|
т. е. каждое b] равно ej, умноженному на скаляр в новой коорди натной системе:
|
1
|
1
|
81 |
о
|
|
|
0 |
Ь2 -- |
1 • **»Ьт = |
5 |
|
О -
|
1
|
о
|
|
1
|
1
|
Кроме того, ег делит ег+1 (i = 1, . . ., т).
НОРМАЛЬНАЯ ФОРМА СМИТА |
451 |
Для данной матрицы [ЬгД требуемое преобразование дости гается: (1) перестановкой столбцов или строк; (2) сложением (или вычитанием) одного столбца с (или из) другим столбцом или одной строки с (или из) другой строкой. Операции со столбцами форми руют новый базис Ь), У = 1, . . т, с помощью целочисленных комбинаций векторов старого базиса Ь,-, а операции со строками формируют новые единичные векторы е) с помощью целочислен ной комбинации векторов е7.
Опишем сначала стандартную процедуру приведения полно стью целочисленной квадратной матрицы к нормальной форме Смита.
Ш а г 1. Перестановкой столбцов и строк добьемся, чтобы Ъц был наименьшим по абсолютной величине среди ненулевых
элементов матрицы. |
Перейдем к шагу 2. |
|
|
|
|
|
|
Ш а г |
2. Если |
|
Ъц делит |
biS, / |
= 2, . . ., |
т, |
перейдем к ша |
гу 3. |
Если Ъц не делит Ь1;- для некоторого ] = |
к, |
то |
|
|
|
|
|
blk = пЬц + q, |
|
|
|
|
|
|
где |
п — целое |
число и |
0 < |
q < |
Ъц. |
|
|
|
|
|
|
Положим К |
= |
bh — nhi |
и b) = |
Ь,- для / ф к. Эту операцию |
осуществляем, |
вычитая п раз 1-й столбец из к-vo столбца. В ре |
зультате получим b'lh = q, где q < |
Ъц. Перейдем к шагу 1. |
Ш а г |
3. Если Ьц делит bH(i |
= |
2, |
. . ., |
тп), перейдем к шагу 4. |
Если Ьп не |
делит Ьп для некоторого |
i = |
k, |
то |
|
|
|
|
|
|
|
bhi |
= |
nbi |
+ |
q, |
|
|
|
|
|
|
где п — целое число и 0 < |
q < |
bn . |
|
|
|
|
|
|
|
Положим е[ = |
ei -f- neh и |
е) = |
ег для |
i ф |
1. |
Эту операцию |
осуществляем, |
вычитая п раз 1-ю |
строку из к-й строки. Чтобы |
убедиться |
в этом, |
рассмотрим вектор-столбец |
Ь7-: |
или |
|
by = |
b^ei + b2je2+ |
■• • + |
bkjek+ |
• • • + |
bmjem, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
или |
by= Ьц (е4 —пей) + |
Ьце2+ • • • + bhjeh + |
• • • + |
bmje'm, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ь; =r M |
l + |
Ьце2+ . . . + |
(bhj —пЪц) e'u+ |
. . . + |
bmje'm. |
Перейдем к шагу |
1. |
|
|
|
|
|
|
|
|
|
|
|
Ш аг 4. Поскольку положительное Ъп делит Ьц (У = 2, . . . , т )
иЬц (г = 2, . . ., т), предположим, что Ъц = П)Ъц, а Ъц = щЪц.
Положим bj = bj —П]Ъц Ь) = Ь4 |
(т. е. вычтем |
из у-го столбца nj |
раз 1-й столбец), |
|
|
е4 = в) + п2е2 -f ще3+ |
. .. + птет\ е\ = |
е*, 1Ф 1, |
