Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 71
Текст из файла (страница 71)
Так как первая часть асимптотического целочисленного алгоритма предполагает решение задачи целочисиенного программирования как задачи линейного программирования, то В 'А = (1, В 'Х) при окончании сиьшлексных вычислений. Если взять дробные части В 'Х, то они представляют собой элементы группы с операцией сложения по модулю 1 (если каждый элемент В ~Х записывается как л/ь/, то мы можем рассматривать лишь числители Й, но с операцией сложения по модулю й).
Обозначим матрицу, 12.2. АСИМПТОТИЧЕСКИЙ АЛГОРИТМ 407 обратную к 8, через Я ', тогда О) Й)~ (О Отсзода следует, что существуют незырожденные унимодулярные матрицы О " и Р з, такие, что 44 зВ 'Р ' = Я з, где зс з соответствует операциям над строками, а Р ' — операциям над столбцами. При втором способе нахождения образов небазисных столбцов мы начинаем с [В з, В зХ).
Затем, применяя О ' и Р ", получаем (О- В-'Р-', 4)- В- й)) = (З-', О- В- Р(). Если взять дробную часть О зВ зг(, то элементы первых пз — й строк будут равны О, а 1-е компоненты (1) и, — й) столбцов матрицы 44 зВ зХ будут принимать одно из следующих значений: 1 2 21„~,+А — 1 0— Ф з Ю-т+д Е1 ~М ' ' 21-~е1-А Так мы находим образ каждого пебазисного столбца. Рассмотрим численный пример: максимизировать 1 г = х1 + 2хз + Зхз + хг+ х, + —, хз при условии х, + 4хз+ 2хз+ хз+ хе = 41, 4х1+ Зхз+ хз — 4хе — хз + х; = 47, хз)О (целые) (7=1, ..., 7).
(27) ~3 — 4 ' с (ое1В(=6: сеВ '= (2, 1) В'= Оптимальным базисом задачи линейного программирования, соответствующей задаче (27), является 403 ГЛ. !Е. ЛИНЕЙНОГ И ЦГЛОЧИС;111ННОК ПРОГ)'АМЬП!РОВАНИЕ Вычислим [свВ !Х вЂ” сл): /11 з1=1б ' Следовательно, целевая функция 1п1пс,*-х, в задаче [7) прнпимаот вид пппз=- !-[2116!)х! '-[30!6)хз ', [1/6)хе+[1116!)хе+[3''6)х!. [23) Существуют два пути получениге отноп!ения сравнения атхтги с=: [)о[я!Ой 1). Выпи!лом матрицу [В. М, Ь, 1] задачи [27), где единичная матрица справа служит только длн проверкит): 3 — 441 — 1 0 147 О 1 Пусть Ь; = Ь1, Ь; — — Ъ, + Ь,. Получаем 3 — 14 1 — 1 0 147 0 1 Пусть Ь," = Ь,+ЗЬ;, Ъ; ==Ь;. Получаем 6 2 1 4 1 1 0 41 (('1 О) 0 — 1 4 1 — 1 0 1 47 1~0 1) Пусть е,'=е„е,'=- — 2е!+ез, т. е.
добавим дважды 2-юстроку к 1-й строке, и пусть Ь,.=- — Ь",. Тогда получаем 6 0 9 6 — 1 1 2 135 1 2 Теперь мы имеем базис В' в диагональной форме н все 16! векторы а! ладо взять по пюй [ ) . Папримср, ! ) —= [1! 4 = — (, ) !втой[ )) . Следовательно, мы должны решить [29) !) При такой форме записи преобразования иад единичной матркцей соответствуют преобразованиям пад строками из А в процессе приведения В к нормальной форме Смята. — Прим.
рад. ю.. аспмптотнчкскпи ллгоеитм 409 Заметим для проверки Итак, мы доля ны решить задачу целочисленного программирования (28), (29). Заметим, что операции над строками соответствуют изменению базиса в пространстве всех вектор-столбцов, а операции пад столбцами соответствуют изменонтпо в базисе, порожденном целочисленными комбинациями столбцов из В. Другой путь сестоит в том, что мы начинаем с оптимальной таблицы задачи линейного программирования. В конце сямплекспых вычислений получаем В'Х Вгй с 1 0( 2 3 2!6 4!6 2,~6( 43 0 1(316 2 3,~6 3 6 0 (123~6~ 3(6 0 3 — 4 4 1 — 1 0 1 47 После вычитания целых частей и отбрасывания 6 в знаменателе таблица принимает вид (слева добавлена единичная матрица) 10002120 Пусть е,'=.—.е~ н е,'=- — е, ! ею т.
е. добави» строну 2 и строке 1. Получаем 01303303 Заметим, что все числа берутся по модулю 6. Пусть е," = = — Зе,' '-, е,' и с, "= е,', т. е. добавим 3 раза 1-ю строку ко 2-й строко. Получаем 34000000 Заметим, что группа (В '),11) имеет ранг 1, следовательно, вторая строка состоит из нулей. Так как преобразования кад 410 Гл. 1з.
линеинОН и пелочислепное пРОГРАммиРОВАние строками зада1отся матрицей ') (' '1 то при проверке получаем ') 3 4 3 4 3 О О О а1 —— =, аз= "=Г 'П'1-Г1 "-Г Т)-П -(1 И=(Л '-(' 'Н-(') и мы снова приходим к (29). Следовательно, элементы группы имеют вид (') (') ( ) (') (') (~) сзз а1 сзт а1 аз Относительными стоимостями векторов а) являются с,*=21, сз — — 30, с,*=1, се=11, се=3. Мы хотим минимизировать ~~ стх) ()'=1, 3, 5, 6, 7) при условии (29) (') -(')" (')"-(')"-(')"-(')(- (')1 Воспользуемся рокуррентпым соотношением ~,(У) =Шзн(еув 1(У), ЗРв(У вЂ” а,)+С',).
Начинаем с а„поскольку его стоимость равна 1, т. е. наименьшая, а порядок равен 6: р,(о) =О зр1(аз) = е)11(яз) =шгп(оо, ер1(О)+1) = 1, з)11(2а,) =зр1(81)=ш(п(осе ер1(Аз)+1)=2, 1) См. сноску на стр. 408.— Прим. ред. ') Наементы всех фигурирующих здесь матриц взяты по щое) 6.— Прим. иерее. «9.2, Асимптотический ллгогитм ф«(Заз)= ф«(ЮГз)= «пш(оо, ф«(дз) )-1) =-3 ф«(4аз) = ф«(лг) = ш«п (оо, ф«(дз) + 1) = 4, ф«(5«'«5) ф«(л!) = п«(п (оо, ф«(«,'2) —, 1) = 5. Затеи мы начинаем с а„, так как ого стоимость равна 3, т.
о. «ааименыпая из оставшихся: фг(аз)=фг(52)=Ш)п(ф«(52), фг(0)+3) =ппп(«, 3) =3, фг (2а,) = фг (45) = Шш (ф«(лз), ф, (42) + 3) = Ш1п (2, 3, 3) = 2, фг(Заз)= фг(0) =ппп(ф,(0), «)«г(55) — ', 3)=ппп(0, 2+3)=0. Поскольку порядок а, или дг равен 3 и делит 6, мы должны взять некоторую другу«о начальную точку, чтобы получить ф,'(д) для всех л.
Начнег«с л«: ф2 (а1) = ф«(б«) = 5 з(72 (ь«+ Дг) = фг (45) = ш1п (ф«(05), 'фз(вз+ ьг) = фз (ьз) = ш(п (ф«(55) ф2 (Ь5+ вг) = фз (5«) = Ш«п (ф« (к«), ф,'(д«)+3) =ппп(3, 5+3)=3, фз(дз)+3)=шш(1, 3+3)=1, «рз'(дз)+3)=шш(5, 1+3)=4. Заметил«, что фз'(дз) не использует дг. Вычисляем фг" (д«); оно не совпадаот с фг'(д«), которое равно 5. Поэтому ф",(д«+дг) — ф (дз)=шш(фь(яз) ф (у«)+3)=ппп(3, 4+3)=3. Заметиз«тепеРь, что ф,"(дз)=фз(дз) и вычислении заканчиваютсЯ. В следу«огцей таблице приведены результаты вычислений"): 55 5« 4Ъ Уз 55 Юз 0 5 3 3 2 1 0 4 3 3 2 1 аг «57 аз с«5 «55 Для любого д« ~(уз, д„..., дз) получаем равенство фз(д)=-фг(д) обусловлоп~ое относительно высокими стоимостями а«, а, и аз, Так как =Д] з) Последняя строка здесь заполняется аналогично строкам «в табл.
193; т. е. в соответствии с (25), с той разницей, что вместо номеров «указываются соответствующие векторы ап — Прим. перев. и совпаДает с л„з«ы Должны использовать аз по меньшей меРе один раз. Делая обратное построение, получаем л5=3, а все 442 ГЛ. ГЬ ЛИНЕЙНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ другие пебазисные переменные равны О, х =В '(Ь вЂ” Мхи)= 4 2 6 6 4 2 6 6 — О Следовательно, оптимальным целочисленным решением является х, = 42, х, = 49, х, =- 3, з =- 2х, + х, †', хз + Зх, + х; при условии 2хз + хз + 4х„ + 2хз + хз = 4( (30) Зх~ — 4х, + 4хз + х~ — ха+ х7 = 47, хз ) )О (целые) (7 =- 4, ..., 7). Заметим, что зта задача почти такая же, как (27).
Оптимальным базисом соответствующей задачи линейного программирования является а остальные переменные равны О. При решении задачи грушювой минимизации полезно рассмотреть граф П (С, ц, с). Граф имеет ( С ) вершин, по одной вершине Х (д) для каждого д Е С. Если д' е т~, то существует ориентированная дуга из Х (д) к Х (д + д'). Стоимость этой направленной дуги равна с (д'). На рис. $9.3 изображен граф Н (С, т1, с) для случая, когда С вЂ” циклическая группа порядка 6, Ч= — (А ум Чз).с=( е 'з Пскоторые дуги, соответствующие дз, не изображены. Задачу групповой минимизации (7) можно интерпретировать как задачу нахождения пути минимальной стоимости или кратчайшего пути от О к Л' (д,) в графе П (С, т1, с).
Рассмотрим численный пример: Р и с. 19.2. максимизировать 19.7. лсимптОтичгскпй л71ГОРитм а оптимальной таблицей соответствующей задачи линейного программирования является табл. 19.2. Таблица 72.2 1 х1 хт хх х1 ха ха хт константы Таблица 7У,3 если 7(Ь)=-О; если ) (Ь) =д1," если 1(Ь) =да; если 1(Ь).— -уа; если ) (Ь) = да; если 1 (Ь) = д,. ! 00000, 00010, ( ) хм = хх, ха, хл, х„х, =- Лспо, что 7 (аа) = 1 (аа) =- О, поскольку все компоненты векторов а, п а; целочисленные. Вычисления, подоб17Ьте проведеппым для задачи (27), дадут 1 (аз) = Ь'3 7 (аа) = В1 И т (ат) = Зт Таким образом, можно построить граф, показанный па рис. 19.3.
Результат вычисления кратчайшего пути даст табл, 19.3. Решеппем задачи целочисленного программировапия является (хв, хх) с хв = В 'Ь вЂ” В 1)71х77. Мы показали, что рептеиие состоит из двух частей и что вторая часть является периодической поправкой. Из соответствия 11 = — ха, 2а = хт получаем яериодические поправки для всех возможных Ь.
Таким образом, 444 ГЛ. Ш. ЛГП1ЕИНОЕ И ПЕЛОЧИС:1ЕПНОЕ ПРОГРАММИРОВАНИЕ $Р.З. А р* рр Р 111 зацин (Ху [112)) ° ° ° ° ° ° ° ° ° ° ° ° В этом параграфе мы рассмотрим алгоритм решения задачи групповой минимизации: минимизировать Х с*(а) 4(а) асс-О при условии д С(д)=4", (1) ЮЕО-О Ю (д) )О (цельре). Р я с.
19.4. Очевидно, что задача (1) охватывает случай д й д с С',О. Действительно, для элемента д' ~ 1) можно взять в качестве его стоимости с* (д') сколь угодно болыпое число, так что 4' в опти- Заметим, что решения задачи (30), полученные с использованием этих периодических поправок, являются оптимальнымм целочисленными тогда и только тогда, когда хв = В 'Ъ вЂ” В гй(хя Ъ О. В пастоя1цем случае ~ [41, 47! = дю так что хн = (О, 0,,0, 1, 1). Используя значения для В 'Ь н В 111 нз онтимальпой таблицьв задачи линейного программирования, получаем [~рзр~~ [3 р| [ 0 1 [20] ' Так как компоненты хв неотрицатсльны, решение (х„х„хю х„х„хю х1) = (42, 20, О, О, О, 1, 1) является оптимальным решением.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
