Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 26
Текст из файла (страница 26)
В отличие от алгоритма ЦИКЛ алгоритм '!ОСТРОЙКА не порождае« допустимого пот «ка величины о, до тех пор, пока не осганопигся, поэтому мы будем называть его алгоритмом, недопустимо«м относительно задачи, Пример 7.2. Если начать с нулевого погока и сети, пр" веденной на рис. 7.3, го путем из з в ! наименьшей стоимости будет путь ргосебнге ДОСТРОЙКА Ьей«п мвп1е нотон ! < чь «1о Ьея!и нвйтв в и' кратчайший путь Р вз .. в 1; увеличить поток вдоль Р твк, чтобы либо велнчннв потока сгвлв равной н„, либо Р перестзл быть увеличн««в~ошим путем наименьшей стонмостн еп«! епб Рнс.
7.7. Алгоритм ДОСТРОЙКА длв задачи о потоке минимальной стовмостн. !м Ь, !), и увеличение потока вдоль этого пути приводит к потоку величины 1 и стоимости 3 Путем нанменыпей стоимости из ь в ! и получаемой сети приращения Аг будет путь (ь, а, !), который при. водит к гому же оптимальному потоку величины 2 и стоимости 12, что н алгоритм ЦИКЛ в примере 7.!. Д 7А Явный прямо-двойственный алгоритм для задачи Хичкока.
Алгоритм АЛЬФАБЕТА Рассмогрим геперь одну очень известиу,о «а«1«чу, являю'цуюся частным случаем задачи о потоке минимальной стоимости. Первоначально она была сформулирована около 1911 г несколькимн ис. следователям««, в частности Хичкоком 1Н«1, и носи« его имя. Постановка этой «адачи связана со следующей ситуацией Имеются т пунктов отправления некогорого говара, на каждом из которых хранится запас в и, единиц «овара, « =1,, т, н а пункгов назначения, в каждый из которых гребуегся доставить Ь«единиц товара, !'=1, ..., п Кроме гого, известна стоимосгь с„перевозки единицы товара из пункта отправления «' в пункг назначения !.
Спрашивается, как удовлетворить все потребности при минимальной стоимости перевозок Эту задачу можно следующим образом сформулировать в виде задачи ЛП. Гл. 7. Задача о потока минимальной стоимости 148 Определение 7.4. Пусть даны т, лба+, запасы а;ЕР'((=1, ... ..., т) в пунктах отправления, потребности Ьос)с' (1=1, ..., л) в пунктах назначения и сц6Р' (ь' =-1, ..., т и /=1, ..., п).
Индивидуальной задачей Хичкока называется следующая задача ЛП с пере- менными пп'п ~с,/;, и ь и 2'ч Рь/=по с= 11 ' ' ' ш (П) ~'., );т=Ьт, 1=1, ..., и, с=! ~с, )О, (7,4) (7.5) где ~~;, а;=~~;, Ь|. Заметим, что можно было бы сформулировать эту задачу с не- равенствами (7,6) (7.7) выражающими тот факт, что в нашем распоряжении имеются запасы а; и необходимо покрыть потребности Ьь Однако равенства в (7.4) и (7.5) не приводят к потере общности, поскольку всегда можно ввести фиктивный (и+!)-й пункт назначения с потребностью Ь„„= ~л а; — ~ Ьу (7.8) и стоимостями сы „,,— — О, с'=1, ..., т, Этот дополнительный пункт назначения, согласно (7.8), потребляет все излишние запасы (которые предполагаются неотрицательными) бесплатно (Заметим, что справедливость такого перехода опирается на предположение сы- с).
См. задачу 3.) В том случае, когда все а, и Ьз равны 1, задача Хичкока называется задачей о назначениях, которая еще появится позднее в этой книге. В действительности, когда мы применяем прямо-двойствен. ный алгоритм к задаче Хичкока, мы поворачиваем историю вспять, поскольку «венгерский метод» Куна (Кп! для задачи о назначениях был предшественником общего прямо-двойственного алгоритма. Наш план состоит в том, чтобы комбинаториализовать стоимость в задаче Хичкока и исследовать явно двойственную задачу Д вместо того, чтобы обойти ее, как было сделано в предыдущем параграфе Сопоставляя переменные а, и ~~ соответственно равенствам (7.4) 7М.
Задача Хичкока 149 и (7.5), получим двойственную задачу )И о шах н! = ~а а,а, + ~ Ь,()„ !=! ач+р -.с,. для всех != 1, ..., т; ) =1, ..., п, (Д) Можно сразу же выписать исходное допустимое решение для этой двойственной задачи а .—.О, шш (с,,).
(7.9) !а! о Далее, определим допусти.иос лиооксспч!!а Ы индексов переменных в ограниченной прямой задаче как множество пар (с, 1), для которых в Д имеет место равенство Б=-((с, )): !х!-1-р; — --с;,). Тогда ограниченная прямая задача ОП определяется следующим образом: пп'и в = „«~ х';, !=! ~ 70+ х'! = ао !'=- 1, ..., т, ! ~ч)!7+ хт!-! =б7 / = 1 " ОП) х",)О, !=1, ..., т+и, )!7 Р. "О, (!, 1') 6 Ы, )ч~ — — О, (с, 1)~Ы, где через х',, !=1, ..., т+и, обозначены искусственные пере- менныее. Стоимость в ОП можно записать в виде (7.10) Таким образом, минимизация Е эквивалентна максимизации сум- марного потока по допустимым дугам.
Можно переписать ОП без искусственных переменных, но с ограничениями в виде неравенств шах н, по!о ~З ~)» ( аь ! = 1, ..., т, ! ~~п); (Ь!, )=1, ..., и, (ОП') 74 )~0, (!, 1') ~!,У, ~,=0, (, ))б 1,). 150 Гт 7. Задача о потоке минимальной стоимости шеи иый ункт нвчения Обобщены пункт отправлен Рнс. 7.В Задача о чвкснмляьноч потоке, зквнвтингиля огртптенной прямой зввлче Хнч. кока Бесконечные пропускньн способпосгн дуг соогвегсзнутт допустимым нндексвм в двойст. венной задаче.
в том и только в том сл>чае, если (г, ()ЕП. Этим обеспечивается то, что переменная );, можез бить болине О только тогда, когда пара индексов (г, !) допустима. В прямо-двойственном алгоритме двойственное допустимое ре. шение и, (> улучшается с помощью оптимального решения, скажем се, р, задачи, двойственной к ограниченной прямой задаче. В гл. 6 мы видели, что при завершении алгоритма Форда — Фалкерсона множество помеченных вершин определяет оптимальный зФразрез и, следовательно, также оптимальное решение. Для обсуждения применения алгоритма пометок к задаче Хичкока нам потребуется специальный термин. Определение 7.5.
При достижении оптимальности после приме. пения алгоритма пометок к задаче ОП будем говорить, что мы пришли к отсутствию лрорьюи. При огсутсчвии прорыва положим (* = 'г: пункт отправления г помечен), (7.! !) й*=((: пункт назначения ( помечен), Теперь можно записап оптимальное решение задачи, двойственной к ограниченной прямой задаче. Последняя задача представляет собой задачу о максимальном потоке, приведенную на рис. 7.8. В ней добавлены обобщенный пункт отправления в и обобщенный пункч назначения г', из з в каждый из гп пунктов отправления проведена дуга с пропускной способностью а; и из каждого из л п>нктов назначения проведена дуга в ( с пропускной способностью Ьм Из пункта отправления к пункту назначения проведена дуга (г', () с бесконечной пропускной способностью 7.4.
Задача Хичкока гз! (7.12) Доказательство Можно показать, что а, 'р допустнмь) в ДОП и что их стоимость оптимальна для ОП. Детали доказательства оставляем читателю (см. задачу 4). () Если при отсутствии прорыва $=-0, то мы достигли оптимального решения нашей исходной задачи с величиной потока )г = э а)= й„() )г. Ое)/ г ) Если $' »О, то напомним, что в прямо-двойственном алгоритме возможны 2 случая. Случай l; ег)+р) 0 для всех (г, 1)т!l.
Случай 2; ай !-~3))0 для некоторой пары (г, 1)е!Б. В случае 1 получаем, что прямая задача была недопустимой, и, следовательно, этот случай невозможен, поскольку сформулированная нами задача П всегда имеет допустимое решение. Таким образом, имеет место случай 2, и можно вычислить О,= ппп [ ' ' 1 = гп(п [ ' ~1. (7.13) ), Па.ч-е > е, г+йl гч)",, ф г / в, ))6).) сумма ее)+!)) может быть причем тогда она равна 2, ибо в противном случае 1 двойственное решение и Пос.леднее равенство следует из того, что больше 0 только тогда, когда 1С Р и Щ и в этом случае автоматически (1, ()Ц13, должно было быть помеченным.
Новое можно получить по формулам а, +О, для я) — О) длг) 1': — О, для 1(! +О, аля ) Е 1*, 1ч 1Е", г 4.1" (7. 14) При этом оказывается, что никакая дуга, на которой имеется поток, не может стать недопустимой, так же как никакой базисный столбец не может стать недопустимым в общем прямо-двойственном алгоритме (см. задачу 5). Это дает возможность продолжать расста- Лемма 7.!. Ори отсутствии прорыва в решении задачи ОП' оп- тимальное реи)ение задачи, двойственной к ОП, дается равенствами аз= 1, 1Е 1", а;= — 1, 1ч 1*, (1, =- — 1, Я7= Гл.?.
Задача а потоке мпнимольнод стоимости новку пометок в алгоритме Форда — Фалкерсона начиная с потока, который был оптимальным при последнем отсутствии прорыва. Этим алгоритм полностью определяется, и окончательно мы приходим к максимальному потоку величины ~~а;=~,Ь,. На рис. 7.9 прн- ргоседнге АЛЬФЛБЕТЛ Ьея1п выбрать и, (), допустимые н В; зчЫ!е поток не максимален до Ьей(п решить задачу о максимальном потоке ОП, используя только допустимые дуги; найти множества помеченных строк и столбцов при отсутствии прорыва, скажем 1" и зч; вычислить О, и пересчитать и, 1) (сошшепг см. (7. И) и 17.14)) епд епд Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
