Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 51
Текст из файла (страница 51)
е, решение, соответствующее паросочетанию. Наше доказательство будет консчруктивным. Мы просто покажем, что прямо-двойственный метод нз гл. 5 приводит к целочисленному решению, а мы знаем, что ои приводит к оптимуму. Однако более ннчересно то, что применение прямо-двойственного метода к описанной выше задаче ЛП приведет нас к эффек~ивному алгоритму для общей задачи о паросочетании. Задача Д, двойственная к задаче ЛП с ограничениями (!!.!), (1!.2) и (11.3), имеет вид шах Х а, + ~р зеу„ с г ее прн условиях а+а + Х ух<се ь 1езе у„<о для всех 1, 1(п, ~11.4) для всех А( йг, (11.5) где а соответствуют ограничениям из (11.!), а у — ограничениям из (! 1.3). Прямо-двойственный алгоритм будет решать задачу о взвешенном паросочетании следующим образом.
Начинаем с допустимого двойственного решения у„=О для всех й и аз — — !!2 ппп;(см), Затем производим несколько итераций, во время которых решаем ограниченную прямую (ОП) задачу и соответственно изменяем двойственные переменные. ОП, как обычно, будет зависеть от множества допусгпимьех переменных в двойственной задаче, описываемой условиями (1!.4) и (!!.5).
Множеством допустимых переменных будет мно- учшпывая ограничения (11.1) и (!! .2), а гпакжг новый класс ограничений (по одному для каждого подмножества Зь) х;,+у„= з„, у ) О для й=1, 2, ..., )у. (!1,3) ( ! е /езе !д,3. Задача о о»оеа/«пном пароеочетанни «ао жество л'=л',1!л'», где л',— множество допустимых ребер, т.
е. тех ребер, для которых в (11.4) имеет место равенство, а о'» — множество допустимых нечетных множеств, т, е, гех множеств 5», для которых у„=О. Пусть 7» обозначает множество всех нечетных множеств, не входящих в л'ы Тогда задача ОП имеет вид ш(п $ = Х хо+2 Х х",„ /=/ ' «=/ при условиях х ц + х ) 1 /=/ Х х//+ у»+хл+е=з»~ / /«3» (11.6) (11.7) х/л.-о О и [о/, ой/ ~ х/л = 0 (1 1.8) (1 !.9) (нз-за множителя 2 в функции стоимости некоторые у в задаче, двойственной к ОП, могут равняться 2). Следовательно, задача, двойственная к ОП (ДОП), имеет вид л и шах Х а,+ Х з,у„ » / при условиях а/+ал+ Х у»<0, [о,, ол]Е./„(11,10) /, /ез« у»(0, 5»Е'7» (11.1!) а,. (1 для всех /, у (2 для всех й, где а соответствуют ограничениям из (1!.6) и у — ограничениям из (11.7).
Остальной материал параграфа будет посвящен установлению того факта, что двойственные переменные а/ и ун на протяжении всего прямо-двойственного алгоритма таковы, что задачи ОП и ДОП «комбннаторны» по своей природе и, следовательно, всегда дают целочисленные решения задачи ОП. Поскольку окончательное решение задачи ОП является решением для (11.1), (11.2) и (11.3), то этим теорема !!.2 будет доказана. Допустим на время, что текущие значения переменных а и у из задачи Д и оптимальное решение хп соответствующей задачи ОП таковы, что выполняется Предположение.
а) Переменные хы принимают значения 0 или 1 и образуют паросочетание в графе (У, о',). б) Если 5»Е,7» (т. е. у < 0), то граф (У, о',), ограниченный на множество 5„содержит а„ребер паросочетания. (Отсюда вытекает, что множество 5„является полным, т. е. Х х,. = в»,) ! /«вв Гл, 11. Взвешенное паросочетание в) Если 5ы 5„б7ь и 5,П5„~*8, то либо 5,с-5,, либо 5 с- 5, При этом предположении можно забыть об ограничениях (11.7) в задаче ОП, задаваемой ограничениями (11,6), (11.7), (11.8) и (11.9), поскольку если у =О, то у„может быть положительным, и, следовательно, его можно бесплатно использовать для заполнения разрыва между ~ х, и з„; с другой стороны, если Ь1чв„ у„<0 (т.
е. 5„ЕУь), то, согласно п. б) нашего предположения, нет такого разрыва, который бы нужно было заполнять. Таким образом, можно взять х"„'~,=0 для я 1, ..., Ж, что мы и будем делать в дальнейшем. Определим теперь допусти,чый граф 6г, соответствующий /, и 1ь. Граф6 получается из графа (У, /,) послгстягиваниявсгхнечетных множеств, содержащихся в Ть.
Например, если и=!2 и 1, и 1ь таковы, как показано на рис. 11.4(а), то 6г будет иметь вид, приведенный на рис. 1!.4(б), Заметим, что и. в) нашего предположения нужен для того, чтобы граф 6 был корректно определенным. Далее, назовем паросочетание в графе (У, 1,) правильным, если все нечетные множества из )ь являются полными Например, на рис. 11.4(а) показано максимальное правильное паросочетанне в графе (У, 1,). Заметим, что оно не является максимальным паросочетанием в графе (У, l,). Лемма 11.2, В графе 6в существует паросочгтаниг с д свободными вершинами тогда и только тогда, когда в графе (У, 1,) существует правильное паросочгтаниг с д свободными вершинами.
Доказательство. Читатель может проследить соответствие на рнс. !1.4. Имея правильное паросочетание в графе (У, 1,), можно перейти к паросочетанию в 6з, просто стягивая максимальные не. четные множества из Хгл при этом число свободных вершин не изменяется, поскольку исходное паросочетание было правильным. Для доказательства обратного утверждения достаточно превратить паросочетаяие в 6х в правильное паросочетание в графе (У, У„), расширяя нече|ные множества и заполняя их подходящим образом ребрами паросочетання, Расширенное нечетное множество будет содержать свободную вершину в том и только в том случае, если оно само являлось свободной вершиной в 6 . С) Одно нз следствий этой леммы состоит в том, что можно найти максимальное по мощности правильное паросочетание в графе (У, /,), находя максимальное по мощности паросочетание в 6,. Это очень важно ввиду следующего утверждения.
Утверждение. 6птимальног решение (х~1) задачи ОП является максимальным правильны.ч паросочгтанигм в графе (У, 1,). 1дд. Задача а ввввшвннам нарааачвтанаи 26! Согласно (11.6), значение указанного в утверждении оптимума равно в н Х.;= Х 1 — Х.„, 1=! /=! !, >' что совпадает с числом г( свободных вершин в максимальном правильном паросочетании в графе ()г, а',).
Мы докажем наше утверждеОч ив ас! вс 1 !' !с ! да 1(и!,ив,ис), (ас>а,.с .вс,а!в), (св,ив'ач)1 (а) [ и!, О . Ос, Ос. и!сс ) ! а7 вв ° сн 1 и!! ас б~ (б) Рис. 11нп ние, приведя решение задачиДОП, на котором достигается та же стоимость с). Предположим, что мы нашли максимальное паросочетанив в графе бг с помощью алгоритма из предыдущей главы. Это озна- Гл. !!. Взвешенное порооочепчание О = (ам, ааь ц„, пы а цв п4 а1о) =(;....,,), 1а= ((ц1 по ° па па пм)) ° Ч',=(1п„п„, а,)), искомое решение задачи ЛОП: 1, если и!ЕО, — 1, если а с1, 0 в противном случае; Определим теперь — 2, если Я,ЕЧ'а, 2, если ~~ 6Ч'ь 0 в противном случае.
Легко понять, что эти значения удовлетворяют условию (11.11), поскольку Ч',о-,Го. Неравенство (11.1О) также выполняется, так как если Ьа а!)Е,)„то (11.10) может нарушаться, только если аь а!~О. Но эта означает, что а; и и! принадлежат одной и той же псевдовершине (ани не могут принадлежать различным внешним псевдовершинам, так как тогда эти две псевдовершины образовывали бы цветок), и, следовательно, в неравенстве (11.10) имеется слагаемое у„=- — 2, что приводит к справедливости этага неравенслва. чает, что нам ие удалось обнаружить увеличивающий путь в текущем графе б„полученном из бо стягиванием нескольких цветков. Множество вершин графа 6, состоит из псевдовершин.
Псевдовершины могут быть следующих типов: 1) вершина множества 2) максимальное нечетное множество (о', 3) несколько вершин из Р и максимальных нечетных множеств из Гы слитых в наибольший относительна включения цветок (т. е. цветок, не содержащийся ни в каком другом цветке) графа 6,. Псевдовершина графа бо мажет быть либо внешней (достижимой из свободной вершины по чередующемуся пути четной длины), либо внутренней (напарником внешней псевдовершины), либо ни той, ни другой.
Следовательно, множество )г разбивается на множества О внешних вершин (вершин, входящих во внешние псевдовершины), ! (вершин, содержащихся во внутренних псевдовершинах) и множество остальных вершин. Аналогично, вершины графа б„не являющиеся вершинами множества )!, разбиваются на множества Ч"а (максимальные нечетные множества, соответствующие внешним псевдовершииам илн цветкам), Ч", (максимальные нечетные множества, соответствующие внутренним псевдовершинам) и множество остальных вершин. В примере на рис. 11.4(б) 6,=6, 1!.З. Задача о взвешенном паросочетанпн Стоимость указанного решения равна (О! — (1! — 2 Х 5„+2 ~Р 5„.
5ЕЕ Чеп 5ЕВ Ч?С (11.12) с;1 — ач — а1 и — тв те а;+ св1+ Х уе Ь 1н5В где минимум берется по всем таким величинам, у которых знаменатель положителен. Первый знаменатель может быть положительным в двух случаях: 1) по пфО, но лежат в разных псевдовершинах графа 6,; в этом случае знаменатель равен 2; 2) п;ЕО, п1ЕУ вЂ” 1 — О. Тогда а,+из+ ~чР ~ух — — 1.
К 1е5в Теперь можно заметить, что (11.!2) — это число внешних псевдовершин в 6, минус число внутренних псевдовершин; это в свою очередь совпадает с числом свободных вершин в 6„которое по лемме 11.2 равно числу свободных вершин в максимальном правильном паросочетании в графе (У, з',), Это в точности совпадает с указанной в утверждении оптимальной стоимостью задачи ОП, Таким образом, оптимальность установлена и утверждение доказана Следовательно, все решения задачи ОП будут максимальными правильными паросочетаниями. Это справедливо также для последней итерации, после которой оптимальное решение задачи ОП совпадает с оптимальным решением задачи ЛП, задаваемой ограничениями (1!.!), (!1,2) и (11.3). Остается доказать наше предположение, которое мы очень давно приняли.
Это довольно легко сделать индукцней по числу итераций. Оно, очевидно, выполняется на первой итерации, поскольку первоначально все у и хы равны нулю, А приведенные выше рассуждения доказывают, что если наше предположение выполняется в начале некоторой итерации, оно также выполняется в начале следующей итерации. Это следует из того, что в Ув могут добавляться только цветки допустимого графа, а цветки, очевидно, являются полными. Кроме того, нечетные множества, которые уже содержались в зь, остаются полными, так как максимальное паросочетание в ОП всегда является правильным паросочетанием.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
