Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 67
Текст из файла (страница 67)
19. линейнОе и целочисленное НРОГРАмьн1РОВАние Леммл 19.1. Фактор-модуль (А)l )гег фВ ! и группа(а) изоморфнм !). Эта лемма в более общем виде формулируется так: пусть !' — гомоморфивм модулей (А) и (А'). Тогда ядро !' обрадует нормальный подмодуль (Н) модуля (А) и отображение (А)l(Н) -+- (А'), определенное соотношением ~е (а, + Н) = = )'(а!), является игоморфизмом между (А)!(Н) и (А') 1). Докдзятвльство. Пусть х — произвольный элемент ядра ~, т. е. ~ (х) = О', где О' — нейтральный или нулевой элемент (Ае). Пусть а! — произвольный элемент из (А).
Тогда 1 ( — а! + х + а1) = ! ( — а!) + ) (х) + 7 (а!) = ! ( — а!) + О' + + ~ (а!) = — — р'(а1) + ~ (а!) = О'. Это означает, что — а, + х + а, принадлежит Н или — а1 + Н + а! содержится в Н. Меняя местами а! и — а! в рассуждении, мы можем йоказать, что ае + + х — а! также принадлежит Н, или что а! + Н вЂ” а, содержится в Н. Заменяя х на а, + Н вЂ” а„получаем, что — а, + + (а1 + Н вЂ” а1) + а1 содержится в — а, + Н + а, илн что Н содержится в — а! +Н+ а1. Следовательно, Н = — а, + Н+ + а1 для любого элемента а! ~ (А) и, значит, Н вЂ” нормальный подмодуль модуля (А).
Для доказательства второго утверждения предположим, что а, и а, принадлежат одному смежному классу по Н. Так как Н— подмодуль, то — а1 + а, также принадлежит Н и / ( — а, + а,) = = О'. Используя этот факт, получаем / (аг) = ~ (а1 — а, + а ) = р (а1) + 1( — а, + а ) = = ) (ае) + О' = ~(ае).
Следовательно, ~е отображает все элементы любого смежного класса (А) по Н и один элемент иэ (А'), т. е. если а, + Н = = а„+ Н, то Г(а,) = /(а,). Положим ~ = фВ-!. ° Леммя 19.2. )1ег фВ-! = (В). Дон АЗАтельство. и и ~~ ЛтатЕ)сег фВ 1:=,*> ф(В '(Д Л;а;)) =О<::. и ~: В '(~ Л!а!) = р()А — некоторый целочислеияый вектор):: е=! и ее и срге ~~', Л!а! =-В)А= ~~' )А!Ь!':=ь ~ Лен! Е(В). ° 1-1 1=1 !) Здесь и далее под модулем псдрагумееается аддитивнвя абелевн группа бег операторов, которую можно рассматривать яак модуль над кольдом целмх чисел.— Прил. ред.
е) Дояааательстес леммы 19Д содержится пс существу в теореме о гомомсрфигмях групп. См., например Ван-дер-Варден Б. Л., Современная алгебра, ОГИЗ, М., 1947.— Прим. иерее. !9.!. ввкдгяик Твогвттл 19.2. (А),'(В) ви (о!). Изучим структуру фактор-модуля (Е)/(В). Так как (Х)— множество т-мерпык векторов, то единичные векторы е;(!=1,'..., т) О ~ — ь-я компонента служат базисом для (Х), а также, конечпе, и для (В), где Ь!= У Ьые! () =1, ..., т). !=1 Следовательно, матрица В Ь„...Ь о!! Ьа! оев ь е, е„, Ь,ц 6,„ выражает каждый вектор Ь! через векторы ен Эта теорема непосредственно следует из лемм 19.1 и 19.2.
Как отмечалось ранее, В является базисом в В, так что каждый вектор можно выразить через векторы из В, если допустимы действительные коэффициенты. Если бы линейные комбинации векторов из В с целочисленными коэффициентами содержали все векторы из А, то фактор-модуль (А)/(В) состоял бы только иа нейтрального элемента О + (В) и модуль (я) также содержал бы только один элемент нуль. Следовательно, порядок модуля (а) в некотором смысле является мерой невовмохсности получения векторов А с помощью целочисленных линейных комбинаций векторов ив В. 394 ГЛ.
1У, ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Изменяя базисные векторы Ь1 и единичные векторы е/, мы можем сделать в1атрицу диагональной Ь; Ь;...Ь,'„ Е1 =В', с, е' Рту где е, является делителем е1+, (1 = 1,..., т — 1). (Процесс приведения матрицы к нормальной форме Смита детально описан в приложении А). Поскольку этот процесс не изменяет величины определителя, Р = [ 1[еу В [ = [ 1[еу В' [ = ет е, ... е„, и Ь; = = е1е1 ([ = 1, ..., т). Так как система е1(1 = 1,..., т) является базисом для (Х), то (Х)=ге,' Е ге,'9 ... цУхе' (г — любые целые), (2) а так как Ь1 (1=1, ..., лу) является базисом для (В), то (В)=хЬ; йУ хЬ; Ю Щ хЬ~,=хе1е1' Щ хехе,'1ТУ ...
еУ хз е'. (3) Из (2) и (3) следует (Х)/(В) = (хе,' Щ хе,' Щ ... Все' )/(хе,е,' Щ хехе,' Щ ... Щ хе„,е) хм зи (хеД/(хе,е ) Щ (хе,)/(хер,) 3 ... Д+ (хе,„)/(хе е„) ги зи (х)/(хе,') 9 (х)/(хеу) Ю ... 9 (х)/(хе,'). Заметим, что Ь,'=е;е1, поэтому в группе хе,'/хе;е,' не более чем е1 элементов, а именно О, е,', 2е,', ..., (е; — 1) е,', и следовательно„ порядок этой циклической группы равен ео Итак, (Х)/(В) — прямая сумма т циклических групп, порядок 1-й циклической группы равен е1 (1 =- 1, ..., т), где е1 делит е1+1.
Поэтому порядок группы (Х)/(В) равен е, еу. 'ет— Пусть [(Х): (А)[ — индекс подгруппы (А) в группе (Х), а [(А): (В)) — индекс подгруппы (В) в (А). Тогда Р = [(Х): (В)[ = [(Х): (А)[ [(А): (В)), так как (А):у (В). Это означает, что [(А): (В)[ всегда делит Р. Если бы матрица А содержала единичную подматрицу размерности эх Х т, то (Х) = (А) и [(Х): (А)[ = 1, так что Р = [(А): (В)[ = [(а)[.
Так как группа (и) изоморфна (А)/(В), мы получаем следующую теорему. !г.ь ВВедение Теогемл 19.3. Для любой целочисленной матрицы А, ее подматрицы В и а = В 'А суихествуют положительные целые числа ех (1 = 1,..., т), такие, что ех делит ех»» (1 = 1,..., т — 1) ех ... ° егх = Р = ( деС В ~, и (и) ивоморфна модулю — Ю вЂ” Ю ° Ю— гхх гых или же одному иг его подмодулей. Порядок (а) никогда не превышает Р и всегда делит Р. Если А содержит единичную подматрицу, то (А)/(В) меет порядок Р.
Ранее было показано, что строки (Д, ~ы..., ~ ) образуют абелеву группу с операцией сложения по модулю 1 и, кроме того, что зта абелева группа есть прямая сумма нескольких циклических групп, имеющих порядок ех (1 = — 1, ..., т), причем е, ° е, ... е = Р. Рассхютрим строку дробей Эта строка является элементом одной из циклических групп. Коли числа р~.() =- О, 1, ..., и) и Р пе имеют общих множителей, то строка имеет порядок .0 и, следовательно, порождает всю группу. Иными словами группа является циклической.
Ксли числа рх (! =- О, 1,..., и) и Р имеют общий множитель с, то строка имеет порядок Р(с. Таким образом, порядок строки Г; равен общему анаменателю сокращенных дробей рРР (С = О, 1,..., и). Мы показали, что (а) изоморфпа прямой сумме. циклических групп, имеющих порядок е;. Теогемл 19.4. Пусть (т Х и)-матрица А содержит единичную подматрицу К, а матрица В диагонолигирована так, опо„Ь; = е;е; (1 = 1,..., т).
Тогда (сх) = (фВ '(е,')) Ю (фВ '(е,'О су ... Ю (фВ '(е' )). Доказлтельстао. Пусть фВ '(е,).=Ь,. Покажем, что Ь, имеет порядок е,. Так как (а)вм(А)~(В), то паимеяьщим положительным кратным е,', которое будет обращаться в куль отображением фВ ', является е,е,' =-Ь,. Поэтому фВ '(ехе',) = ехфВ '.е, = е,Ь, =-О и Ьх имеет порядок е,. Подобные рассуждения можно провести и для фВ '(е,')) (х=-1, ..., т). Таким образом, (сх) =- (фВ '(е,')) ® б» (фВ '(е,'„)) = (Ьх) Е (Ь,) Е ... щ (Ь ). ° 25 т,хт 388 Гл. 12.
линейнОе и целочисленное НРОГРАммиРОВА1Н1е Пример. Пусть — 120100 2 0 0 0 1 0 1 — 2 2 0 0 1 0 — 2 О 2 0 0 1 — 2 2 В'= (4) 4 8 Если мы воспользуемся е,' = — е, + ез+ 2е, е,'= ез з — Ь2, е,'= Е2 то матрица В диагонализируется 0 0 В' = Тогда 0 0 ~ ез= 0 0 0 2 0 1 0 е',= е =— 1 О 0 1 0 0 2 В-1 В' Вз 0 0 4 8 4 8 0 0 0 0 0 0 0 4 8 0 0 0 Следовательно, 0 2 8 ~. 2! так: 0 0 2 0 0 4 Ь;=Ь„ Ь;= Ь„ Ь;= 2Ь1 0 4 8 — 0 0 0 3! 2 8 0 387 19.9. АСИМПТОТИЧЕСКИЙ АЛГОРИТМ 19.2. Асимптотический алгоритм (Гомори (84), Щ, )86)) Рассмотрим вадачу целочисленного программирования максимизировать с'х' при условии А х' ( Ь, (1) х' ) О (целые), где А' — целочисленная (т х и) матрица, Ь вЂ” целочисленный л9-мерный вектор, с' — целочисленный п-мерный вектор. ' Задачу целочисленного программирования можно записать и в другой форме максимизировать при условии Ах = Ь, (2а) х ) О (целые), максимизировать свхв + скхи при условии Вхв+ Мхи = Ь, х в, х к Ъ О (целые).
(2б) Выражая хв через хи: хв = В 'Ь вЂ” В 1Ххи, получим следую- щую задачу: максимизировать свВ-'Ь вЂ” (свВ 1Р( — с, ) х, при условии хз + В 111х, = В-1Ь, (2в) хз, хи ) О (целые). Если в задаче (2в) отбросить требование целочисленности переменных хв и хи, и если  — оптимальный базис получившейся где А — целочисленная (и )Г (пт + п))-матрица, с — целочисленный (т + и)-мерный вектор, а х — (вт + п)-мерный вектор, который включает дополнительные переменные, введенные для преобразования неравенств задачи ($) в уравнения задачи (2а). Для простоты предположим, что А содержит единичную (т Х лт)- матрицу.
Представляя А в виде (В, Я), можно записать (2а) в следующем виде." 333 ГЛ. 19. ЛИНЕИНОЕ И ЦЕЛОЧ11СЛЕН1ГОЕ ПРОГРАММИРОВАНИЕ задачи линейного программирования, то ее оптимальным реше- нием является хв = В 'Ь, хк =О, причем свВ 1Р( — сн ~ О. Если В-1Ь вЂ” целочисленный вектор, то хв = В 1Ь, х99 = 0 является также оптимальным решением задачи целочисленного программирования (2в). Если В 'Ь— нецелочислонный вектор, необходимо увеличить хя от нуля до некоторого неотрицательного целочисленного вектора, такого, что хв =- В-'Ь вЂ” В 1%х; . »0 (целЫе).
Возникает два вопроса: 1) когда В 1Ь вЂ” В-'Хх„з О? 2) когда В 1Ь вЂ” В 1Ххи — целочисленный вектор? Рассмотрим сначала второй вопрос. Пусть В 1М есть матрица (а1, аз,..., ал), а В 1Ь вЂ” вектор (19. Тогда второй вопрос можно сформулировать как задачу нахождеяия таких хгл что Ха)х1 = рз(шоб 1) '), хтю0(шо1)1),, х;~0 ()=1 ..., п).
, азх, =— ()с(шой1), х1 ал 0(шо1) 1), х )О (у'= 1, и) (4) Заметим, что (4) моягно было бы получить, применяя отображение у =- фВ 1 к ограничениям задачи (2б). Так как в (2в) ск = свВ 1Х вЂ” ск )~ О, мы стремимся увеличивать хк как моя но меньше. Таким образом, если отброшено требование хв ~) О, задача целочисленного программирования примет вид 1) Перемеппымн в (3) являются компоненты хл — псбазпспые относительно оптимального базиса В непрерывной (пецелочпсленной) задачи (2в). Здесь и далее, очеввдпо для удобства, автор отождествляет переменные х„ с переменными зо ..., Ел задача (1).
— Прим. ред. Так как целые части компонент вектора ан умноженные на целое число х;, равны нулю по модулю 1, интерес представляют лишь дробные части компонент векторов ау и Рз. Пусть ф (а1) = а~ и ф (Раз) = Рпз. Тогда (3) эквивалентно 19.2. АСИМПТОТИЧВСКИИ АЛГОРИТМ максимизировать свВ 1Ь вЂ” с1атхн при условии ~а1хт = — Ре(шос) 1), (5) ()=1, ...,и) 1) Точйео говоря, сушестаует оптимальное решение вадачи (2б), являющееся вершиной многогранника Р.— Прим. иерее. з) Имеется ввиду выпуклый конус с вершиной и = (хв, хк) =. (В-1Ь, О), образованный решениями системы Вхз + (тхи = Ь,хк > 0 в х-пространстве размерности и+ т.
Конус с вершиной в точке Р, — это такое множество О, что если Р, б О н Л г О, то (Ро+ Л (Р1 — Ро)) с О.— Прим. ред. хтжО(шод1), х,.- 0 1 С каждой задачей целочисленного программирования (2б) сопоставим соответствующую ей задачу линейного программирования, получаемую отбрасыванием требования целочислекпости х. Допустимые решения задачи линейного программирования, соответствующей (26), образуют выпуклый с многогранник, который будем обозначать Р'. Выпуклую 'оболочку всех целочисленных точек, принадлежащих Р', обозначим через Р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
