Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 69
Текст из файла (страница 69)
Пусть Е = (Е' (у)) — любая точка, координаты Е (у) которой — целые и О < т' (у) < г (у). Такой вектор имеет ) т) ) компонент и каждая компонента может принимать любое из значений О, 1,..., т' (у). Следовательно, имеется не более Ц (1 + г (д)) различных возможных векторов Ф, у которых еЕч 19а. Асимптотический АлГОРитм 395 8' (у) (1(а). если точка 1 — неприводимая, то сумма Х Р(а) д=д(2') ееч даст различные групповые злементы для разных Ф . Однако имеется только ) С ) различных групповых элементов, и, следовательно,неравенство (9) справедливо. (Заметим, что граница, полученная для г (д), справедлива и для хк.) ° Слвдствив '19.1. Ееяи Ф = (г(л)) — неприеодильая точка г1ногогранника Р (6, Ч, Лг), то ч~, 8(д)(Р— 1.
геч (10а) Доказьтгшьство, Если произведение нескольких целых положительных переменных фиксировано, то максимальное значение суммы этих целочисленных переменных достигается, когда все переменные (кроме одной) равны единице. По теореме 19.6 И (1+2(у))(! а! =Р. геч Поэтому наибольшее значение суммы Х 8(л) достигается при геч е(д) = 0 для всех л Ф а. Полагая е (у) = 0 для всех я ~ Ь, имеем (1+О) ° °...
(1+2(Ь)).... (1+О)(!6)=Р, т. е. 1 + г (й) ( Р, или г (й) Р— 1. Тогда, очевидно, для всех ~, а1=2(д), где Уг=(7'~~(а1)=у), 19 ге Поскольку е* (д) = шш с,', Хг — — о ! 7 (а1) = д), Югег то имеем я Д с,*ау~~,~~ с'(д)$(Я, 1=1 ггч ~~ г(д) =(О+... +ю®+... +О)(Р— 1 геч и утвер1кдение (10а) доказано. ° Установим связь мея1ду решением Ф задачи (7) и решением х задачи (2а). Рассмотрим л2обое допустимое решение хн задачи (5) и допустимое решение $ задачи (7), такие, что ДЯС ГЛ, <в. ЛИНЕИНОЕ И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ или (10б) сйххм ) с'1. Пусть 1в — оптимальное решение задачи (7), а хй — решение задачи (5), полученное из Ф' согласно (8б).
Тогда сйхй = с'1' (11) и в силу (10б) х~~ — оптимальное решение задачи (5). Поскольку 1ь — оптимальное решение задачи (7), для произвольпого хз< получаем сйхк ) с*1) с" 1'. (12) Обозначим значение целевой функции задачи (2в) через з,(Ь), а ф <Ь через з<(Ь). Тогда з,(Ь) = зь (Ь) — с~хи. (18) Поскольку хй — оптимальное решение задачи (5), то из соотношений (11), (12) и (13) следует с,В 'Ь вЂ” сйх)<=с„В Ь вЂ” с'1')зь(Ь) — сяхп —— зг(Ь).
(14) Следовательно, если хй — такое; что х~в =В '(Ь вЂ” Мхй))0, то из соотношения (14) закл<очаем, что (х7<, х~) — оптимальное решение (2в). Этот результат можно сформулировать в виде теоремы. Теовемл 19.7. Коли 1е — оптимальное решение задачи (7), то соотпветствующее ему решение х* =- (В ' (Ь вЂ” Ххй), хй) является оптил<альным решением задачи (2з) при условии, что В '(Ь вЂ” Ххй))0. Исследуем теперь, в каких случаях хв = В <Ь вЂ” В 1Ххп )О. < Мы знаем, что ха=В <Ь является решением задачи линейного программирования.
Вектор В 'Ь неотрицателен, если Ь принадлежит конусу, порожденному столбцами из В. Обозначим этот конус череа Кв. Если Ь вЂ” Ххп также прииадлея<ит конусу Кв, то . В 1(Ъ вЂ” Ххп) ) О. Геометрически, если точка Ь расположена достаточно далеко от любой граничной точки конуса Кв и если длина вектора Ххп достаточно мала, то разность Ь вЂ” Мхи таки<е лежит внутри конуса Кв.
Если через Кв (<1) обозначим подмножество точек конуса Кв, удаленных в евклидовой метрике не меньше чем па <1 от любой граничной точки конуса Кв, то Кв = Кв (О) 19.2. Асимптотичеокий АлГОРитм 397 н нз условия Ь Е Кв (а), (( 11хн (( ( сг следует, что В '(Ь вЂ” Ъ(хн) ) О.-Рассмотрим длины небазнсных вектор-столбцов аг (7 = 1, ..., и). Наибольшую нз них обозначим через 1 аах т. Е. 1 ах = ШаХ (Ч~",ааа1)112. ТОГДа 7=1, ..., а а а ПХХНИ=!! ~ агаг!!((шах Х Хг=(пах Х г(у)((мах(Р— 1). 1=1 7=1 геч Следующая теорема дает достаточное условие неотрицательности хе. ТеОРемА 19.8.
Если Ъ Е Кв (1ааах (Р— 1)), где Р = ) аех В (, то (хав, хна) — оптимальное целочисленное решение задачи (26), где хо = — В 1(Ь вЂ” Ъ(хна), хй соответствует 1а согласно (86), а 1а— оптимальное решение задачи (7). Изобразим конус Ко. На рис. 19. 2 (а) имееется полоса точек, которые удалены не более чем на д от граничных точек конуса Ке. Заметим, что данная точка Ь может принадлежать полосе, тогда как ХЬ, при Х.~)1 может лежать вне ее. Можно указать и другое достаточное условие, аналогичное теореме 19.8.
Пусть 11 — максимальный элемент в 1-й строке матрицы В 1Х. Построем вектор-столбец 1 = [11,..., 11,..., 1м). Тогда, если В 'Ь вЂ” (Р— 1) ! ) О, оптимальное решение 1» задачи (7) соответствует оптимальному решению задачи целочисленного программирования (2а).
Пусть дана задача целочисленного программирования (2а). Рассмотрим матрицу А и вектор с как фиксированные, а правую часть — как вектор, который может принимать одно из значений Ь", Ьх, ..., Ъ". Для любой заданной правой части Ь' существует оптимальный базис В' соответствующей задачи линейного программирования. Можно разбить т-мерное пространство точек, удовлетворяющих ограничениям, на несколько конусов, соответствующих различным оптимальным базисам В'. Это показано на рис.
19.2 (6). Если базис В является оптимальным для правой части Ь, а Ь вЂ” другая правая часть, для которой В 'Ь > О, то В— оптимальный базис и для Ь'. Теорема 19.8 показывает, что конус Кв имеет полосу фиксированпой ширины' 1,аах (~ де$ В ) — 1).
Если Ь и Ь вЂ” точки, не принадлежащие полосе, то оптимальное решение задачи (2а) находится по оптимальному решепиюзадачи (7). Пусть оптимальное решение задачи (2а) при правых частях Ь и Ь есть ха (Ь) и х" (Ь) соответственно. Тогда х*(Ь) =(хе'(Ь), хнаа(Ь))=(В 'Ь, 0)+( — В 111хй(Ь), ха (Ь)), х'(Ь') =- (хав(Ь'), хй(Ь')) =(В 'Ь', 0) +-( — В хай(Ь'), ха (Ь')).
393 ГЛ. 19. ЛИНЕЙНОь И ЦЕЛОЧИСЛЕННОЕ ПРОГРАММИРОВАНИЕ Заметим, что мы разбили решение на две части. Первая часть соответствуег решению задачи линейного программирования, вторая часть представляет собой поправку, необходимую для того, чтобы сделать хв целочисленным.
Следует подчеркнуть, что хя получается .иа оптимального решения 1э задачи (7), которое является оптимальной вершиной многогранника Р (6, ц, бэ). Вместе с оптимальным бааисом В определены также С и Ч. Но 1' одинаково для двух правых частей, если они отображаются в один (б) Р и с.
19.2. и тот же элемент я,. Поэтому, если две правые части Ь и Ь отличаются на целочисленную комбинацию столбцов из В, то их образы при отображении ~ = фВ ' одинаковы и вторые части в соотношениях (15) одинаковы. Разность между хэ (Ь) и х* (Ь') тогда равна В т (Ь вЂ” Ь'). Так как существует в точности ) 6 ) возможных элементов группы 6 для оптимального базиса В, то существует ! 6 ) возможных элементов яю и в (15) может быть не более ! С ) различных вторых частей.
Можно вычислить вторую часть соотношения (15) для каждого д, с С. Если это сделано, то решение задачи целочисленного программирования получено для всех правых частей Ь, принадлежащих Кз(И), где с) = 1~,„(Р— 1). Заметим, что в оптимальном решении задачи целочисленного программирования (хвхя) часть хя* является периодической относительно столбцов.
!».з. Лсимптотическии алгоритм ззз оптимального базиса В соответствующей задачи линейного программирования '). Кагкдое Ь, для которого соответствующая задача линейного программирования имеет решение, прннадлеягит некоторому конусу Кв. Этот конус может быть, например, одним из конусов, изображенных на рис. 19.2 (б). Это означает, что Ь можно выразить посредством столбцов из В, т. е. Ъ = ~Лги„где Л; )О. Точка Ь может принадлежать, либо не принадлежать конусу Кв (1шах (Р— 1)). Но если Л! м О для всех (, то ЙЬ при достаточно большом )с будет принадлежать конусу Кв ()юех (Р— 1)).
На рис. 19.2(а) показан случай й = 2. Это означает, что задача целочисленного программирования с ограничением Ах = есЬ может быть репгена при достаточно большом Ь, если решение соответствующей задачи линейного программирования не вырождепо. Поэтому настоящий параграф называется «асимптотический алгоритм». Заметим, что ширина полосы Ы = !шах(Р— 1) обычно дает слишком жесткие достаточные условия.
Пусть Ь принадлегкит допустимой области '). Тогда из соотношения (9) получаем 11 (1+ ! (й'))(Р'). лев Из соотношения (8б) для небазисных компонент задачи (2а) следует (16) Когда Р = ) г)еФ В ) = 1 (матрица 'А унимодулярна), ив соотношения (16) получаем, что х! = О для всех 1. В этом случае е) = = 1„,х (Р— 1) = О и оптимальное целочисленное решение совпадает с решением задачи линейного программирования, которое имеет не больше чем т ненулевых компонент. Поскольку Р возрастает начиная с 1, то полоса уже не будет нри этом иметь нулевой ширины, а оптимальное решение будет, вообще говоря, отли- !) Имеется в виду, что хне является периодической функцией от вектора Ь вЂ” правой части задачи хе (Ь.р Ч~~ Л!Ь!) =х'". (Ь), где Х! — целые, В= 3=! =(Ье, Ьт, ..., Ьие).— Прим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
