Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 78
Текст из файла (страница 78)
Гран~,многогранников гомоморфных групп В атом параграфе будет описан способ получения грани многогранника Р (С, уз) из известной грани многогранника Р (Й, Ьз) при заданном гомоморфизме С в Й. Точная формулировка утверждения содержится в теореме 20 11. Твоокмл 20.11. Пусть зу' — гомоззорфиггз С в Й с ядром К и уз б К. Если (у', 70) — грань многогранника Р (Й, ф'уз), то (у, 70) является гранью многогранника Р (С, дз) при у (у), равном 7' (з)з'д). (Мы полагаем у' (0) = О, так что у (д).= 0 для всех д Г с К) Доказательство приводится в работе (86]. Проиллюстрнруелз теорему двумя примерами. Предположим, что ~1) 1 является гранью многогранника Р (Сз, 1). Иными словами, (у (0), 7' (1); 7,) = (О, 1; 1) является гранью многогранника Р (С„1). Рассмотрим гоиоморфизм з)з', отображающий Сз в С„с ядром К = =- (О, д„У4).
ПосколькУ ф'Уз = 1, мы полУчим гРань многогРапника Р (Сг Аз): ~1 + 0 ~з + 1 ° 80 + 0 11 + 1 зз ) 1. Аналогично можно рассмотреть гомоморфизм ф', отображающий Сев Сз, с ядром (О, дз). Если у (1) = 1, у (2) = 2, 70 = 2 является гранью многогранника Р (Сз, 2), то 81 + 2гз + О. сз !- с, + 2сз ) 2 является гранью многогранника Р (Св, дз), поскольку ф'уз — — 2. Справедлива следующая теорема, обратная к теореме 20.11. Твоовмл 20.12. Пусть (у, 70) — нетривиальная грань многогранника Р (С, дз). Если у (у) = 0 для некоторого у Ф 0 с С, то 444 ггь 20. ГРАшх нглочислгнного многогглнникА существует группа П, гомоморуьизм ф' и грань (у', уг) многогранника Р (П, Ьг), такие, что Й = ф 6 и .у (у) = у' (ф д) (йь = ф дь). Доказательство этой и следующей теоремы приведено в работе [86].
Нреи4де чем сформулировать следующую теорему, введем термин специальная грань многогранника Р (П, 0), где Й вЂ” циклическая группа. Нод специальной гранью мы подразумеваем либо грань либо одну из граней, полученных из пее с помощью автоморфиэма. В теореме 20. И и теореме 20.12 мы имеем дело с дг й К.
Следующая теорема позволяет получить грань многогранника Р (6, д,), где дь принадлежит ядру К. Твогвмл 20.13. Пусть (у4. 1) — грань многогранника Р (П, уг), а (уг, 1) — специальная грань многогранника Р (П, 0), где Й— циклическая группа порядка большего, чем два. Если ~р' — гомоморфизм, отображающий 6 в Н, где уь ~ К, то неравенсгпво ( у, 1), он р еде лен кое сост ношениям и у(у) =71(к) г с К у(у) =- у (Ф'у) у1 К является гранью многогранника Р (6, уг). Таблица 2а.з Например, рассмотрим группу пар целых чисел [пм п,] с операцией ело"кения по модулю [3,3], и пусть уг = [0,2]. Легко видеть, что отображение ф'.
[п„п,] -+. [п„О] — гомоморфизм. Ядро К является подгруппой элементов вида -[О, пг]. Из приложения 0 известно, что (Чг, 1; 1) является гранью многогранника Р (Сз 2), а (ч)г, г!г; 1) — специальной гранью многогранника Р(Сг 0). Тогда у [п,, пг], заданное табл. 20.5, образует грань многогранника Р (Сг,г, [0„2]).
445 20.7. хАРАкткгы и нкглвкнствл 20.7. Характеры п неравенства В предыдущих параграфах приведены методы получения граней многогранника Р (С, л,), пе использующие теоремы 20.1. Если мы хотим применить зти методы для получения неравенств или отсекающих плоскостей в циклическом целочисленном алгоритме, то необходимо проделать следу4ощие шаги. Ш а г 1.
Использовать симплекс-метод для нахождения оптимального базиса В соответствующей задачи линейного программирования. Пусть матрица коэффициентов А = [В, М]. Тогда симплекспые вычисления должны преобразовать матрицу А в(1, В '%. Ш а г 2, Найти фактор-групну (1)1(В) или (В 'Х)/(1) для базиса В, полученного на шаге 1, затем для пебазисных векторов а; и правой части Ь найти соответствующие элементы группы С. Ш а г 3. Найти неравенство, определяющее грань мпогогранпика Р (С, яэ), и вычеркнуть в нем переменные, соответстзукпцие групповым элементам, пе принадлежащим т!. Получившееся неравенство будет определять грань многогранника Р (С, т!, 4О) или отсекающую плоскость для нашей задачи.
На шаге 2 и 3 мы должны знать группу С, в то время как в циклическом целочисленном алгоритме (79! отсекающие плоскости получаются непосредственно после шага 1 без проверки групповой структуры. В этом параграфе мы покажем, как получать отсекающие плоскости, ие зная соответствия ме4кду небазисными столбцами и групповыми элементами. Сначала выясним соотношении между различными группами: (В, и!) — (1, В 'г() 1, 1„ (В, ХЯВ) к (1, В 'ЩГ(1), где В ' переводит (В, Х) в (1, В 'Х), Л, отображает (В, Х) в фактор-группу (В, Х),'(В), й, отображает (1, В-'Х) в фактор- группу (1. В 'Х)'(1).
Легко убедиться, что (В, г!)'(В) и (1, В 'г() '(!) — изоморфпы. Изоморфизи между фактор-груп- наин обозначается через В '. Здесь необходимо подчеркнуть, что соответствие мел ду групповым элементом д и небазиспым столбцом а; определяется только дробными частями В 'а;, Порядок группы С равен ! ~!е! гт !, который в сво1о очередь равен произведению последовательности ведущих элементов. 446 Гл. 20. ГРАни целОчисленнОГО мнОГОГРАнникА Введем новый термин характер группы или групповой характер,.
Характер групйы есть такое отображение с, что $ (у1 + у ) =- $ (у1) + $ (ул), (6 + $г) у = Ь (у) + $ (у). Обычно понятие «характер группы» означает отображение, которое переводит групповые элементы в единичную окружность в колшлексной плоскости, так что $ (д ) 0101 с (уг) = — е'0» с (у, + уг) = еаз'+ап и т. д. Таким образом, группа порядка Р отображается в корни степени Р из единицы в комплексной плоскости.
Ясно, что характеры сани образуют группу, называемую группой характеров, и группа характеров изоморфна исходной группе С. В нашем случае мы будслл иметь дело с адднтивной группой дробей иЮ (пшб 1) (и — целые) или аддитивной группой целых чисел и (лвой Р). Таким образом, мы будем понимать под характером группьл С отображение, которое переводит С в иЮ (шод 1) или в целые числа п (шоб Р).
Пусть п — любое целое число, а Со — циклическая группа порядка Р. Определим р (и!Р) как элемент уп группы Со, где иЮ = р Р (шоб 1). В гл. 19 было показано, что любой элемент из В ' имеет вид тР, где и — целое. Отсюда непосредственно следует, что любая целочисленная комбинация элементов из В ' также имеет вид пЮ. Рассмотрим скалярное произведение строки г; (иэ В ') и целочисленного вектор-столбца с. Скаляр (г; с) имеет внд иЮ, и мы можем отобразить его в уп, где п(Р = рЮ (шоб 1). При фиксированной строке г; мо'кпо рассматривать зто как отображение целочисленного столбца с в групповой элемент д с С. Определим функцию э; (у), где у с С, налагая $; (у) = ф (г, с), где )г,с -» у. (2) Это означает, что для любого вектор-столбца с, который отображается в д посредством и, из (1), функция 6; (д) задается соотношением (2). Сначала покажем справедливость записи 1; (у) и докажем, что $; (у) является функцией от' д и не зависит от выбора вектор-столбца с.
)1усть с и с' — два вектор-столбца, таких, что )г,с = )в~с' = у. Тогда )г~ (с — с') =- О с С н )г»В '(с — с') = О Р (1, В л)ч)/(1). Это означает, что В ' (с — с') должно быть полностью целочисленным вектором или г; (с — с') — = О (шод 1). Следовательно, р (г;. С) =- 9 (г; с') для любого с', такого, что й,с' = у. Можно пРовеРить, что с; (У~ + Ул) = $~ (д,) -)- $; (Ул) и что 6; — хаРактер группьь Если $; — характер, то целочисленная комбинация ы зо с =- Х пДО также является характером группы. '1егко заме- ~ —.! 20.7.хАРАктЕРы И НЕРАВЕНСТВА 447 тить, что столбцы В > с операцией сложения по модулю 1 порождают группу С, в то время как дробные части строк В ', использованные для определения $>, порождают изоморфную группу характеров.
Рассмотрим, как для данной задачи строятся отсекающие плоскости из граней многогранника Р (Й, у»), где Й вЂ” циклическая группа порядка Р = ( >(е4 В ). Для данной задачи целочисленного программирования найдем оптимальный базис В соответствук>щей задачи линейного программирования. Базис В определяет группу С. Если $ — характер, отобража>ощий С в циклическую группу Й порядка Н с элементами п>А> (то>1 1), то отсека>ощие плоскости для нашей задачи целочисленного программирования можно получить из граней многогранника Р (Й, Ь,).
Пусть (у, у,) — грань многогранника Р (Й, Ьа), где Й— циклическая группа порядка Н. Для фиксированного характера з группы С определяем Уз(У) = У В(У)!. Если > (д) задает путь в Н (С, уз) от О до у», т. о. 1 д 2(д)=аю аеч то Х $(а) г(а) = $(уа). зео Другими словами, отобракепие $ переводит путь в Н(С, уз~ в путь Н(Й, у). Длины двух путей одинаковы и равны Х уй(у)) 2(а) аеп По предположению (у, у,) — грань многогранника Р (Н, Ь,). Тогда компоненты у удовлетворя>от неравенству у (Ь,) + у (Ь ) ) )у(Ь>+ Ь) или Х уй(а))2(а))уй(М. зео Таким образом, (3) является неравенством,' которое должно удовлетворяться при л>обои 8 (д) из Р (С, Ре).
Следовательно, (3) может быть использовано как отсекающая плоскость. Меняя характер $, можно получить и — 1 неравенств из каждой грани Р (Й, )г,). Заметим, что в (3) не предполагается $ (уо) = Ьм Как частный случай этого подхода рассмотрим грань многогранника Р (П, Ьо >) с компонентами у (Ь>) = зЮ и уе =- =- (Н вЂ” 1)Ю. Тогда семейство полученных неравенств в точности 448 Гл. 20. ГРАни цклОчислвнноГО мнОГОГРА!гиикА совпадает с семейством отсекавщих плоскостей, порожденных циклическим алгоритмом целочисленного программирования. В общем случае эти неравенства не являются гранями многогранпика Р (6, )), 4,"2), хотя гранями они могут быть. Рассмотрим численный пример (30) из 3 19.2.
Задачу в матричной форме можно записать так: х, Х2 0 41 47 ° (4) Х) Оптималыпай базис состоит из первых трех столбцов, и мы имеем хг Хз Оптимальный базис имеет определитель, равный 6. Каждая строка г из (5) задает характер, который отображает С в циклическу)о группу порядка 6. Характеры $» $2 и $з использук)т только дробные части злемонтов из (5), выписанные ниже с опущенным общим знаменателем: х) 22 хг 22 хз хе хз ~ ПР 2! О (6) 0 0 0 3 0 О 3 0 0 О 0 0 0 4 0 0 О 3 О 0 3 51 Е2 53 Поскольку правая часть состоит из 3, О, 3, обращаемся к приложению В для граней многогранника Р (62, 3) (или испо,тьзуем 1 — 2 — 1 — 1 — 3 — 1 0 О 0 0 2 1 4 2 1 0 0 3 — 4 4 1 — 1 0 1 1 0 0 21~6 5 2 11,6 4,'6 0 1 0 2 3 1 4,'6 2,)6 0 0 1 3!'6 2 1 3;6 0 1063)з 43 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
