Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 70
Текст из файла (страница 70)
ред. з) Имеется в виду, что х~~ (Ь) ) О.— Прим. ред. з) Заметим, что зто соотношение справедливо в случае, если точке т(Л) неприводима. Но не любое оптинальпое решение задачи (7) является непрпводимой точкой. Следующее ниже утверждение о границе числа ненулевых компонент оптимального решения задачи (2а) также справедливо, если соотеетствующан точка г(л) — непрнводима.— Прим. верее. 4ео Гл. !9.:!инвйное и цкло~!ислвннок ЦРОГРАммироэлнив чаться от регпепия соответствующей задачи линейного программирования.
Если Ь принадлея<ит допустимой области, то оптимальное реп!ение имеет не больше чем т + р ненулевых компо~ент. Чтобы получить верхпюю границу для р, предполоя!им, что х~я имеет р ненулевых компонент или что хт ) 1 для р небазисных компонент.
Тогда из соотношения (9) получаем В)Ц (1+ х!) ) 2Р, или р ~= 1оа э)7. Итак, в случае )7 = 1 оптимальное решение задачи линейного программирования оказывается автоматически целочисленным. При возрастании 77 решение задачи целочисленного программирования начинает постепенно удаляться от решения соответствующей задачи линейного программирования, однако при этом число ненулевых небазисных переменных всегда не болыце !ол, 77. Начав ре!Цать аадачу целочисленного программирования (2а), возьмем оптимальный базис В соответству!ошей задачи линейного программирования. Применив отобран<ение рВ ' к ограничениям задачи (2а), преобразуем их в одно отношение сравнения (6). Если мы решим задачу групповой минимизации (7), то сможем получить хя' нз соотношения (8б) и хв из соотношения хй = = В-т (Ь вЂ” Хх ). Если хр, ) О, то (х!!, х*;ч) — оптимальное целочисленное решение исходной задачи целочисленного программирования (2а).
Обсудим теперь детально решение задачи групповой минимизации (7). Задача (7) во многом похожа на задачу о рюкзаке, только вместо отно!пения сравнения в последней имеется единственное ограничение типа неравенства. Для любого Я ~ ц и элемента Ь Е б! определим функцию !р(Я, Ь)==ш(п ~ с*(д)С(д) аез при условии ,~„1(д) д.=-1!, (17) зев 1(д)) 0 (полые). Если Я вЂ” пустое множество О, то положим !р (О, Ь) = оо. Если Ь вЂ” нулевой элемент группы, то !р (Я, О) = О. Для любого другого Я и Ь групповой элемент л' Е 5 либо используется по меньшей мере один раа при подсчете !р (Я, Ь), либо не используется вовсе. В первом случае т(я') ) 1 н !р(Я, Ь) = с* (л') + !р (Я, Ь вЂ” д'), (18) а во втором г (д') = 0 и ф (Я, Ь) = !р (Я вЂ” у', Ь).
(19) 12.2. ЛСНМПТОТИчгКСБИИ ЛЛГОРНТМ 401 Следовательно, объединяя (18) и (19), получаем рекуррентное соотношение "Р(о Ь)==ш1пй(о — 4"', Ь), с'(д')+Ф(Я, Ь вЂ” д')). (20) з' Это рекуррентпое соотношение позволяет вычислить гр(Я, Ь) для всех Я ~ т) и каждого Ь б С. Чтобы упростить вычисления, будем решать численные примеры, используя только переменные х1. В гл. 20 мы изучим грани многогранника Р (С, г), до) и обсудим их в терминах 1-пространства.
Пусть фе (у) == 1П1П 2,' СЧХ1 1 — 1 при условии ф,(у) =-пцп (ф, 1(у), ф (у — а,) ' с,'). (21) Это рекуррснтное соотношение позволяет вычислить ф,(у) для всех гч 1(г(п', и у, начиная с гр,(0).— 0 и 1Ро(у) = -:и со, при условии, что вся группа порождается а,г). Коли а, порождает всю группу, то для .побого у выло нгяется у =--га„1(г(н', и моя1но образовать разность у — а„требус21ук1 в (21). ° Рассмотрим численный пример (см. (6)): максимизировать 2 =. — 1хз — ЗХ1 при условии хе+ хь = — 2, 4хч +х, =- — 5, 2хь 1 Х2 (целые) (!=1, ..., 5). — Зхз— — хз— (22) — Зхз— хз )О 1) то есть когда группа (а) — циклическая; случай когда (а) ие является циклической, рассматривается датее.— Прим.
ред. 26 т.' хт ~з агх, .=- у (шоб 1), 1.— 1 хг --- 0 (шог) 1), хт)0 (1=-1, ..., 2). Иными словами, 1р, (у) — оптимальное значение в случае, когда только первые г столбцов ат могут участвовать в образовании столбца у. Прн подсчете ф„(у) либо а, не используется, либо используется по меньшей мере один раз. Отсюда получаем рекуррентное соотпопюнне, аналогичное соотношению (20): 403 Гл. !з. линейнОе и целочислкнное пРОГРАммиРОВАние Решая задачу линейного программирования, получасы оптималь- ный базис — 3 — 1 1 — 1 — 4 0 — 3 — 2 0 с (г(е1В(=10. Применяя преобразование 0 Вг= Π— Й 3 11 1 1О 10 н ограничениям задачи (22), получасы максимизировать г=- -(1'О) х!-(ГО) х.-(10) при условии 0 ха+ 1 х! Р 0 ХА-Р 11 Го Го Х1>0, 1= — 1, ..., 5.
Сггсдоватсльпо, ыы стремимся минимизировать (Г) ~!+(ГО) х! при условии (23) (шо!1 1). хг> Так как ф(0)=0, то по (21) получаем: грг(сг!) =с*,, Ф!(2сс!)=2с!, ..., !р!(9сг!) =9с,* .10 7 ГО 3 10 о ГО 1 х!. Р 10 0 Го 8 1О 8 ГО 3 Го О, х,)0. 4 Го 1 Го 18 ГО 8 1о 43 10 1е.г. гсимптотичкския ллгогнтм 403 и для как:дого гсс, (г=), ..., 27 — 1) получаолг г«,=1«г(шод1). Напрнмор, «г = — 7ссг (снос) 1), 2«, =— 4«г(тес(1) и т. д. Чтобы воспользоваться соотношением г)з (у) = ш1п (фг (у) фг (у — «г) + сг) ~ (24) надо знать фг (у — «г).
Кдинственное фг (у), которое известно к настоящему моменту, это фг(0) =О. Следовательно, мы начинаем с фг(«г)=шш(фс(«г), фг(«г — «г)+с,")= = ш(п(ф(3«с), фг(0)+с,") ') =- ~21 О, 111 11 116 ' + 1О) 16 Вычислив фг(«г), получаем фг(2«г) = пйп (фг (2«г) фг(2«г — «г).)-сг*) = = ш1п (юг (6«г), фг («г) + сг) =' 42 11 11 22 =ш" (ГО 16+ Ге) = Гс Этот процесс можно продолжать до тех пор, пока пе будет вычислено фг((2) — 1)«г).
Чтобы восстановить значения зм образующие текущее ф, (у), необходимо помнить индекс 1, указывающий последнюю переменную, получившую зпачопио единица: — ( 1(з — 1, у), если ф,,(у)(ф,(у — «,) —,' с,', 1(~, у)=4 ' ' ' '' (26) г, если ф г (у) >~ ф, (у — «,] + с,*. Вычисления сведены в табл. 19.1, где ф (у) выписаны для всех 1 е ' г е ' 2 и у Е (а). Заметим, что в строке фг (у) мы производим вычисления слева направо, а в строке фг (у) сначала вычисляется элемент в третьем столбце, а затем — в шестом столбце.
Заметим, что после того, как последние две строки вычислены, первые две строки мегино отбросить. Это сэкономит большой объем памяти вычислительной машины. Преимущество этого алгоритма состоит в том, что, построив один раз таблицу, аналогичную табл. 19.1, можно решать задачу целочисленного программирования (22) с любым вектором правой части Ь. Например, если правая часть равпа [ — 6, — 7, — 8), то ~- — -1=- à — -~хск 18 13 7) 63 -3 73 Го Го' Г61=)Го Го' Гс) — 3«гь— к 9«,(ш с)$). г) Ведь аг ш Заг (шей 1).— Прим.
ред. 26е 404 Гл. 10.:!инеяное н целочнслГннОе ИРОГРАммиРОВАМНГ таблица 1г!,! нулевой столбец ! ! третий столбец ! шастай етолбоц Это означает, что х,—. О, хв =-3 и Оптимальным решением является хе=3~ ха =4, х,=4, хс=О, хе ==3. Рассатотрим теперь случай, когда а, имеет порядок с(, который делит Р (с)чь В). Б этом случае с!и,=-О и не все элементы группы (а) оудут получены. Пусть у — элемент, пе полученный при вычисленная. ТогДа !)!е(У нс известно.
)!РеДполояеим, пРоДеаРительно, что тр,'(у)=-!р„!(у). Тогда мы получим !р,(у) как предварительное значонио !р„(у); !Р,'(У вЂ” '; га,)=:нйн(!Р;(У+гав — а,) Рс,', тР, !(У+га,)) (2(!) (г =.1, ..., с!). После с! шагов йк,.-О, так что мы получим ф,(у',.с)а,)! которое может отличаться от !Р, с(у). Используом это, чтобы вычислить 19.2. АСИМПТОТИЧЕСКИЙ АЛГОРИТМ 405 иоследоватольпо ф,'(у--' га,) при разных г'). Как только одпо из значений ф,"(у ';-га,) совпадает с соответству!ощип значением ф,'(у+та,), вычисления прекращаются. Эта ироцедура повторяется для (0(д) — 1 начальных точен у, чтобы получить все ф.
(у), у'с (а). Мы покажем, что (1) вычисления закончатся после д шагов, где д(д(2д; (2) значения ф,"(у -(- га,) равны в точности значениям ф. (у+ а.) Доклзатвльство. Полагая, что ф,(у)=фе 1(у), можно только оценить ф(у) сверху. Возможны два случая. 1. ф,(у+га,)=!р.,(у+га.) для некоторого г, 1(г(д, тогда ф'(у+и.)=Ф(у+да.)') (д>д) ), и далее ф;(у-:;дае)=фе(у+да,) (д=-1, ..., г). 2.
ЕСЛИ ф,(у-'.Га.)арфе!(у-(-Га,) дЛя ВСЕХ Г=-1, ..., д, Ета влечет за собой для всех г ф, (у+ га,) = з)1, (у 1- га, — ае) — , 'с,*. Но фе (у) = ф, (у. р да,) =- ф, (у. (. (д — 1) а,) + с', = =- ф, (у+ (д — 2) а,) + 2с„* = =... =. ф,(у)-; дс,*. Если с,*чьО, получается противоречие.
Если с',=О, то иредположим, что у — влемопт, который пе мо!нет быть получен с использованием только а,. Пусть у, ( га,= у, где е — ! у,— ~ а х и 1(г(д. з —.!' !) !! ри этом предполагается, что ф", (у! —.ф,' (у+ йа ). — Прим. перев. 2) Для увазапиого г справедливо ф,'(у-',.га„) =ф,(у —,га,); поэтому для . посаедующих значений г правая часть (20! превращаотся в выраи!ение для ф,(у+та,). При доказательстве утверждения 'о ф'; имеется в виду, что де(УЛ Еае)=ю(1! (ф'„'(У-! (З вЂ” ()а,)-, 'ез,фе 1(У.Г Чае)). 4ОЕ гл. нь линвинок и пзлочислвннок пгогглммиговэнив Тогда, поскольку с,'=О, то Ф-~(у~) =Ф(у~+гмз), или ф, (у).=~р, (у) для некоторого у, в группе, или ф,, (у-,'- га) = =ф,(у-,'-ги,) для некоторого 1(г <д, а это приводит к первому случаю.
Определим элемент группы, который является образом данного небазисного столбца при отображеяии фВ '. Это можно сделать двумя способами. При первом способе мы хотим получить группу (А)/(В), приводя В к нормальной форме Смита. Известно, что существуют певырожденные унимодулярные матрицы Р и ф, такие, что РВС( = Я, где Я вЂ” нормальная форма Смита. Матрицы Р и ~ соответствуют операциям над строками и столбцами.
Если группа 6 является .прямой суммой Й циклических групп, то нормальной формой Смита будет 1. 0 е, где е,.с,: .. еэ = 1/. Заметим, что операции над строками действуют над В и Х, а операции пад столбцами действуют только над В. Итак, когда В приводится к Я, Х переходит в РХ. Факторгруппа (А)/(В) получается вычитанием столбцов Я из РХ. . Итак, первые т — й компонент каждого небазисного столбца будут равны О по модулю 1, а /-я компопента (1) т — й) может принимать одно из следующих значений: О, 1, ..., с; +„— 1 (тооз; е„). Так мы находим образ каждого небазисного вектор-столбца. Второй способ состоит в нахождении группы (В ')/(1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
