Т. Ху - Целочисленное программирование и потоки в сетях (1984) (1162191), страница 75
Текст из файла (страница 75)
Поскольку мы ограничиваемся у, ) 0 при обсукдении неравенства в теореме 20Л, остается еще возможность 70 = О. Вернемся теперь к случаю у, = О. гь.>. ввкдкник 499 Доклзлткльство. Предположим, что (у, 0) является гранью многогранника Р (С, >), яь).
Поскольку зта гнперплоскость есть 1п' — 1)-меркое надпространство и порождена элементами 1 й Т, то опа должка содержать п' — 1 линейно независимых точек 1 ~ Т Для каждого из этих векторов 1' (>:=. 1,..., и' — 1) справедливо' у1' =- О, где 1> =- (Р (д>), >> (д,),..., Р (д )1 Так как у (д) ) О, а(д) ) 0 и ,'~„у (я) й (д) —.= О, то либо у (я) ) 0 влечет г (е) = О, либо г (е) ) О влечет у (д) = О. Это справодливо для каждого из векторов О. Если Р (л) = 0 при всех > (> =- 1,... , и' — 1) лля более чем ол>ого элемента д, то зто будет противоречить тому, что п' — 1 векторов О имеют ранг и' — 1, Но если у вектора С = (Г(д>), г (дг),..., Г(д„с)1 все кое>понг>ть> положительны, то, для того чтобы ~ у (я) > (я) =- = О, у (л) должно быть равно 0 для всех к с >1.
Таким образом, кроме случая у (я) .= 0 для всех д й т) единственной возможностью является у (Ь) ) 0 и у (д) =- 0 для всех д с Ч, я М й. Это дает у(>>) 1(й)-~с ~ у (л) С (д) —. 0 или у (й) 1 (й) =. О. Отсюда следует, ееж гюь что 1(й) = 0 — грань, упоминаемая в теореме. Мы показали, что условие 1(й) ) 0 дает единственно возможные грани с правыми частями у, = О. Легко установить, когда зто условие действительно дает грани.
Тно»кмл 20.3. Условие 1(й) ) 0 определяет грань м>ьогогронника Р (6, >), яг) тогда и только тогда, когда элемент д„лежит в подгруппе Сч ы порожденной элементами т) — й. Если д„~ ~ С„'ь, то грань задается условием 1 (й) ) р ) О. Здесь р— наименьшее положительное целое число, определяющее смежный класс рй + 6„>„в котором лежит лв. Доклзлткльство.
Если ль ~) С„' ь, то не существует решения группового соотношения Х 1(д) Д=-Дг веч с ~(й)--.0. Следователы>о, 1(Ь) )О нс является гранью. Если д,с 6>»„то имеем представление 8(е).д фю 0(~(е) <-з(л). (8) ееч — ь Н вектпру 1, удовлетворяющему соотношению (8), можно добавить и' — 1 егдиничных векторов э (л) и (д) для каждого я с ц — Ь, чтобы образовать п' — 1 независимых решений с > (Ь) =- О. Следовательно, 1(Ь) ) 0 является гранью. Если яв >г 6;, ь» поскольку С;, ь разбивает 6 па смежные классы, если Р (С, Ч, йо) не пуст, то лг принадлежит одному ГЛ.
20. ГРАНИ ПКЛОЧИСЛРННОГО МНОГОГРАННИКА из сме2кных классов. Эти смежные классы имеют вид рй + 6„' ь, и мы можем выбрать для каждого смежного класса наимепыпее возможное р. Это дает одно решение 1(й) = р уравнения и мы можем получить и' — 1 других решений простым добавлением единичных векторов и (д), у Г т) — й.
Поскольку не существует выражения для ус при 1(Ь) ( р, неравенство 1(а) ) р выполняется для всех 1 ~ Т. ° В гл. 19;мы ввели граф Н (6, т), с), где с — дуговые стоимости, и стремились найти кратчайтний путь от 0 до ус. Сейчас мы 7% 7(УО Р к с. 20.1. построим граф Н(6, т), у), где у — длины дуг графа. Кратчайший путь от 0 до уь является решением задачи групповой минимизации (3) с общей длиной у (д) 1(д) = у,.
Если у (д) выбрано так, что имеется и' линейно независимых кратчайших путей от 0 до ль, то (у, у,) является гранью многогранника Р (6, Ч, лс). Граф Н(6, ц, ус) для циклической группы из 4 элементов О, ды д„дз и т) = (уы дз) показан на рис. 20.1. Любой из стандартных алгоритмов поиска кратчайшей цепи или алгоритм $19.3 можно использовать для нахождения кратчайшей цепи от 0 до уь или для нахождения кратчайших цепей от 0 до всех вершин Хв, у Е 6. Если кратчайшая цепь Р* от 0 до уь содержит 1(у) дуг, соответствующих д, то имеем решение 1 = = (1(у)) (д ч 2)) задачи групповой минимизации с целевой функцией Х у (д) 1(д). Очевидно, каждое решение определяет много Вез различных кратчайших цепей, различающихся лишь порядком дуг.
Как мы упоминали в гл. 10, любой подпуть кратчайшего пути должен сам быть кратчайгпим путем. Этот факт, конечно, справедлив в графе Н (6, 2), у) и мы сформулируем его в виде леммы. Лкммь 20.1. Нуеть Рь — кратчайший путь от 0 до и 1 — соответствующее ему решение. Нели 1 — любой неотрицательный целочисленный вектор, такой, что р (д) < 1(у), гол. Вввленг!в 434 и 2' Р(д)д=й, то любой пдть, начинающийсЯ в Хв и кончаю»ее щийся в Л +ь, соответствующий решению Р (д), является кратчайшим путем от Ме к Мвьь ° Доклзлтвльство. Поскольку- Р (д) (~ Г (у), то путь, соответствующий [у (д)], есть подпуть кратчайшего пути, соответствующего [1(д)1.
Если существует путь от Л'» к Л' ч.,„соответствующий [1" (д)], который короче, чем [у (д)], то путь, соответствующий [1" (д) + г (д) — Р (д)1, доли»ен быть путем от 0 до дэ с более коротким расстоянием, чем [1(д)1. Получили противоречие. ° Когда мы рассматриваем грани многогранника Р (6, т), у»), которые могут быть записаны как ~ у (у) 1(у) ~ )уо или (т 7»). веч удобно рассуждать в терминах графа Н(6, т), у).
Представим у (к) как длину дуги, соответствующей д. Используя это, мы можем охарактеризовать грань Р(6, з), у») в графе Н(6, т) у)- Лвммя 20.2. Если (у, ув), уг)0, является гранью многогранника Р(6, т), уг) и д~Ч, то существует кратчайшйй путь от Ух к Уе„такой, что 1(у)'- О. Отсюда следует, что существует кратчайший путь от Л~-„к Л»ю проходящий через Л». (Существует много кратчайших путей от Л~й к Л'е,. В лемме утверждается, что каждая вершина Хв, д ~ »), должна припадлея ать по меньшей мере одному из кратчайших путей.) Доклзяткльство, Поскольку (у, у,) — грань, такая, что у, ) ) О, существует и' линейно независимых векторов 1', для которых у[г = — ув.
Для всех других 1, удовлетворяющих соотношению ~Я 1(у) у = Аг, имеем у1 ) уо. Итак, каждый нз векторов 1' веч представляет собой кратчайший путь от 0 до у,. Если все [г($ =' 1,..., и') имеют г» (у) = 0 для некоторого д, то 1~ не будут иметь ранга и'. Следовательно, по меньшей мере одно [г имеет 1» (д) >1. ° Тгогвмл 20.4. Если (у, уг), у, » О, является гранью, то у (у) — длина кратчайшего пути от 0 до уо. Доказяткльство. По лемме 20.2 существует кратчайший путь отО до у»с г(д) ) 1.
Пусть 1 — решение, соответствующее кратчайшему пути из 0 к уо, 'и пусть и (д) вектор 1' из леммы 20.1. Тогда этот путь, состоящий из одной дуги (соответствующей и (д)), является подпутем кратчайшего пути 1; следовательно, и (д) само должно быть кратчайшим путем. Длина этого пути, состоящего из одной дуги, равна у (д). Г;!. 20. ГРАНИ ЦКЛОЧИСЛКННОГО МИОГОГРЛННИКЛ или 7 ]и (з!)] + 7 (1 — и (д!)] = 7о, 7 (е!) + 7 (во) = 70.
или 20.2. Вычисление грани В этом параграфе мы опишем вычисления, необходимые для полУченин коэффициентов пеРавенства ~ 7(Я) Г(а) - 70, котоРое определяет грань многогранника е- ( 6, ги яо). Как и в гл. 19, мы Определим для любого Я с: !) и:побого Ь б б функцию ф, (Ь) = пип ~ 7 (д) г (я) при условии Х б ~(й)=-Ь. (1) есв Тогда з]1,(Ь) удовлетворяет рекуррентному соотношению з]1,(Ь) ==гп(О((0, е(Ь), (Р,(Ь вЂ” а) 1-7(е)). (2) В начале вычислений все 7 (д) неизвестны.
Воспользуемся рекуррептным алгоритмом, чтобы найти 7(д) для всех д ~ т). Как и прежде, определим зро(я) =.(О) 1-=7о и ф,(0).=0. Предположим, что мы:шаем 7 (д) для всех д ~ Я. Тогда следующие три шага дадут 7(г) лля дб() и ябЯ. (1) Найдем значения то для которых (р((до — т!я)(1. Если таких значений нет, положим 7(а)=.0 и перейдем к пахожле. пню 7 (а), где д(] Я () а.
Если существуют значения т;(1=1, ..., д), для которых з](о(до — т!а)(1, то полагаем 7 (я) =- шах (1 — зре (до — т!я)],(т!. ! Слкдствик 20.1. Если д! и до оба принадлежат Ч и я = я! + + до, та 7(б) (7(а!) + 792). Доклзлткльство. Ре!пение ! (я!) — 1 и ! (до) = 1 обеспечивает путь к я длины 7 (б!) Рс 7 (до). Но 7 (д) — длина кратчайшего пути к д. Следовательно, 7 (а) 7 (д!) + 7 (ао). Слвдствнв 20.2. Если я! и до оба принадлежат ц и а! + ко =- = — ' Ио !Ио 7 (К!) + 7 (Фе) = 7о. Докхзлтвльство.
По лемме 20.2. существуез кратчайший путь от 0 к ао, такой, что Г(д!) О. Пусть таким решеинвм будет 1. Тогда ~ (я!) = 1 — подпуть кратчай!Него пути от 0 к «о. Если б! -! Ло = во то йо =- бо — д!. Но мы знаем, что 7'1 = 7о 20.2. ВЫ"!ИГ;!ГНПК ГРАНИ (2) Используем это значение у (я) вместо с у (я), я с Я, для вычисления ф ..— (Й) прп всех !! с 6 аналогично тому, как это делалось в гл. 19.
Когда Я = !), переходим к шагу (3); в противном случае возвращаемся к шагу (1), прн этом число элементов множества о возрастает на 1. (3) Когда у (я) найдены для всех д с т), неравенство ~~ у (д) ! (д) ) 1 определит грань многогранника Р (С, !), еО). Чтобы доказать, что зги вычисления приводят к цели, надо показать, что они дадут и' линейно независимых кратчайших путей в графе Н (б, т), у ). Пе теряя общности, можно считать, что зсе у (д) = О для д с Я и мы хотим вычислить у (я). Предположим, что у (д) —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
