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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 169

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

 

20.6. ГРА Н И

М Н О ГО ГРА Н Н И КО В ГОМ ОМ ОРФ НЫ Х ГРУ П П

443

Поскольку каждый автоморфизм будет отображать 0 в 0 , то

л ю ­

бой автоморфизм будет

переводить грань Р (G, 0) в другую грань

Р (G, 0). Если рассмотрим

автоморфизмы, порождаемые умноже­

нием

элементов группы

соответственно на 2, 3, 4, 5 и 6 , то полу­

чим

из (2) следующие

грани для Р (G7, 0):

 

 

 

4д -j-

i2 —(— 5t3 -j- 2Д -f- 6^5

3ig ^

7,

 

 

5^1 -j-

3^2“I-

^3“Ь

6 ^ 4

4^5 -)- 2te

7,

 

 

2^ -p

4£2 -j-

-f-

^4

-}- 3^5 -j- 5te

7,

 

 

3 fi -I-

6 if2 -E

2 < 3

Ы ,

4“ ^5 "b

4^g

7,

 

 

6 tj -f-

5<2 -f- At3-j- 3i4

-(-2^5 -|-

ifg ^

7.

 

20.6.Грани многогранников гомоморфных групп

Вэтом параграфе будет описан способ получения грани много­ гранника Р (G, go) из известной грани многогранника Р (Н , h0) при заданном гомоморфизме G в Н. Точная формулировка утвер­ ждения содержится в теореме 2 0 .1 1 .

Теорема 20.11.

Пусть

ф' —

гомоморфизм G

в

Н с ядром К

и So $ К. Если (у',

у0) —

грань

многогранника

Р

(Н, ф'#0), то

{у, у0) является гранью многогранника Р (G , g0)

при у (g), равном

у' (ф'^). ( М ы полагаем у' (0) = 0, так что у (g) = 0 для всех g £

€К . )

Доказательство приводится в работе [8 6 ]. Проиллюстрируем теорему двумя примерами. Предположим, что t\ ^ 1 является

гранью многогранника Р (G2, 1). И н ы м и словами, (у' (0), у' (1); То) = (0, 1; 1) является гранью многогранника Р (G2, Т). Рас­

смотрим гомоморфизм ф',

отображающий

Ge в G 2, с ядром К =

= {0, S%, g^}. Поскольку ф ' ^ 5 =

.1, м ы получим грань многогран­

ника Р (Go, gs):

 

 

 

t± -f- 0-t2

1 *^3

~T— 0 -^4 —[—

1 •£5 ^ 1 .

Аналогично можно рассмотреть гомоморфизм ф', отображающий

G e в G 3,с ядром {0, g3}. Если у_(1) =

1, у (2) =

2, у0 = 2 является

гранью многогранника Р (G3, 2), то

 

 

ti -|- 2 ^ 2 + 0 -f3

Д -[- 2 ^ ^

2

является гранью многогранника Р

(Ge, g5), поскольку ф ' ^ 5 = 2.

Справедлива следующая теорема, обратная к теореме 20.11.

Теорема 20.12. Пусть (у, у0) — нетривиальная грань много­ гранника Р (G, go)- Если у (g) = 0 для некоторого g ф 0 6 G, то

444

ГЛ. 20. ГРАНИ ЦЕЛОЧИСЛЕННОГО МНОГОГРАННИКА

существует группа Я, гомоморфизм ф' и грань (у', у0) многогран­ ника Р (Я, h0), такие, что Я = ф Я и у (g) = у' (ф'|/) (h0 = ф'Ы-

Доказательство этой и следующей теоремы приведено в работе [8 6 ]. Прежде чем сформулировать следующую теорему, введем

термин специальная грань многогранника Р (Я, 0), где Я — цикли­ ческая группа. Под специальной гранью м ы подразумеваем либо

грань

Т (^р) = т ^ Г ’ Т о = 1 , I Н I

либо одну из граней, полученных из нее с помощью автоморфиз­

ма. В теореме 20.11 и теореме 20.12 м ы

имеем дело с g0 Q К. Сле­

дующая

теорема

позволяет

получить

грань

 

многогранника

Р (G , g0), где g0 принадлежит

ядру К.

 

 

 

 

 

 

 

 

Т е о р е м а

20.13. Пусть ( у ь 1) —

грань многогранника Р (Я ,go),

« (Ya, !) — специальная грань многогранника

Р

(Я,

0), где Я •—

циклическая

группа порядка большего, чем

два. Если ф' — •гомо­

морфизм, отображающий G

в Я,

где

g0 6

К,

то

неравенство

(у, 1 ), определенное соотношениями

 

 

 

 

 

 

 

 

 

 

 

У (g) =

Yi (g),

g 6

К,

 

 

 

 

 

 

 

 

У {g) =

У2 (Ф'£), g € К,

 

 

 

 

 

является гранью многогранника Р (G , g0).

 

 

 

 

 

 

 

 

 

 

Таблица 20.5

 

 

 

 

 

 

 

 

 

 

 

 

п.i =

0 n i—A

щ =

2

 

 

 

 

 

 

 

 

а 2 =

0

0

1 /3

2 /3

 

 

 

 

 

 

 

 

 

« 2 =

1

1 /2

1/3

2 / 3

 

 

 

 

 

 

 

 

 

п2 — 2

1

1/3

2 / 3

 

 

 

 

 

 

Например, рассмотрим группу пар целых чисел \щ, щ\

с опе­

рацией сложения по модулю [3,3], и

пусть

g0 =

[0,2].

Легко

видеть,

что

отображение ф': [wlt

п2]

 

[геь

0 ] —

гомоморфизм.

Ядро К

является подгруппой элементов вида [0, п2]. Из приложе­

ния D _известно,

что (V2, 1; 1) является

гранью

многогранника

Р (G 3, 2), a

(V3, 2/3; 1) —

специальной

гранью

многогранника

Р (G3, 0). Тогда у [пь п2], заданное табл. 20.5, образует грань многогранника Р (G3,3, [0,2]).

20.7. ХАРАКТЕРЫ И НЕРАВЕНСТВА

445

20.7. Характеры и неравенства

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

Ш а г 1. Использовать симплекс-метод для нахождения опти­ мального базиса В соответствующей задачи линейного програм­ мирования. Пусть матрица коэффициентов А = [В, N], Тогда симплексные вычисления должны преобразовать матрицу А

в[I, B _1N].

Ша г 2. Найти фактор-группу {1}/{В} или {B_1N }/{I} для базиса В, полученного на шаге 1, затем для небазисных векторов а7- и правой части Ь найти соответствующие элементы группы G.

Ша г 3. Найти неравенство, определяющее грань многогран­ ника Р (G, g0), и вычеркнуть в нем переменные, соответствующие групповым элементам, не принадлежащим ц. Получившееся неравенство будет определять грань многогранника Р (G, ц, g0) или отсекающую плоскость для нашей задачи.

На шаге 2 и 3 мы должны знать группу G, в то время как в циклическом целочисленном алгоритме [79] отсекающие пло­ скости получаются непосредственно после шага 1 без проверки групповой структуры. В этом параграфе мы покажем, как полу­ чать отсекающие плоскости, не зная соответствия между небазис­

ными столбцами и

групповыми

 

элементами.

Сначала

выясним

соотношения между

различными

группами:

 

 

 

{В, N} — U {I,

B-‘N>

 

 

 

 

1 “

 

 

kz

 

 

 

 

 

 

 

 

 

{В, N}/{B} —

 

{I,

B_1N}/{!},

 

( 1)

где В -1 переводит

{В,

N} в {I,

В ХХ}, Zcj отображает

{В, Щ

в фактор-группу {В, IV}/{В}, /г2

отображает {I,

B _1N} в фактор­

группу {I, B _1N }/{I}.

Легко

 

убедиться,

что {В,

N}/{B}

и {I, B _1N }/{I} — изоморфны.

Изоморфизм между фактор-груп­

пами обозначается через В-1. Здесь необходимо подчеркнуть, что соответствие между групповым элементом g и небазисным столб­ цом aj определяется только дробными частями В _1а7-. Порядок группы G равен | (let В |, который в свою очередь равен произве­ дению последовательности ведущих элементов.

446

ГЛ. 20. ГРАНИ ЦЕЛОЧИСЛЕННОГО МНОГОГРАННИКА

Введем новый термин характер группы или групповой харак­ тер. Характер группы есть такое отображение Е, что

Е (gi + gi) = Е Ы + E ( g t ) , (Ei + li) g = El (g) + E2 (g)-

Обычно понятие «характер группы» означает отображение, кото­ рое переводит групповые элементы в единичную окружность в комплексной плоскости, так что

l ( g i ) = e iQi, 1 Ы = «Шг, !(gi + g 2 )= ei<ei+62\

и т. д. Таким образом, группа порядка D отображается в корни степени D из единицы в комплексной плоскости. Ясно, что харак­ теры сами образуют группу, называемую группой характеровт и группа характеров изоморфна исходной группе G. В нашем слу­ чае мы будем иметь дело с аддитивной группой дробей n/D (mod 1) (п — целые) или аддитивной группой целых чисел п (mod D). Таким образом, мы будем понимать под характером группы G отображение, которое переводит G в n!D (mod 1) или в целые числа п (mod D). Пусть п — любое целое число, a GD — цикли­ ческая группа порядка D. Определим ф (nID) как элемент gp группы Gd , где n/D = p/D (mod 1). В гл. 19 было показано, что любой элемент из В - 1 имеет вид п/D, где п — целое. Отсюда непо­

средственно следует, что любая целочисленная комбинация эле­ ментов из В - 1 также имеет вид п/D. Рассмотрим скалярное про­ изведение строки гi (из В - 1 ) и целочисленного вектор-столбца с.

Скаляр (гг-с) имеет вид п/D, и мы можем отобразить его в gpr где n/D = pID (mod 1). При фиксированной строке гг можно рас­ сматривать это как отображение целочисленного столбца с в груп­

повой элемент

g d G.

| г (g), где g 6 G, полагая

 

Определим

функцию

 

 

Е; (g) =

Ф ( гг с), где й^с -» g.

(2)

Это означает, что для любого вектор-столбца с, который отображается в g посредством кх из (1), функция Ei (g) задается соотно­ шением (2). Сначала покажем справедливость записи Ег (g) и дока­ жем, что E; (g) является функцией от g и не зависит от выбора вектор-столбца с.

Пусть с и с' — два вектор-столбца, таких, что й^с = й^с' = g.

Тогда *! (с — с') = 0 € G и Й^В"1 (с - с') = 0 6 {I, B -1N}/{I>.

Это означает, что В - 1 (с — с') должно быть полностью целочис­

ленным

вектором

или

г; (с — с') = О (mod 1). Следовательно,

ф (гj• с)

=

ф (гг с')

для

любого с', такого, что й^с' = g. Можно

проверить,

что Ei (gi +

g2) = Ei (&) + Е; ( g s ) и что

Ei — харак­

тер группы. Если

| г — характер, то целочисленная

комбинация

 

т

 

 

 

 

£г, Е = 2 игЕь также является характером группы. Легко заме- i=i

Смотрите также файлы