Введение в прикладную комбинаторику, Кофман А. (984071), страница 44
Текст из файла (страница 44)
(59.8) с=! ~ г=! Эта формула легко переносится на и слагаемых: В. (5)- Х Х(,— г ! ( и и и-! з = гпах ~Я Л(г — ~ В(Р ~.' А( — ~а В(, ..., А(,, (59.! !) или ( а а-! 0„(5) = гпах Я Л( — ~ В(1. !~а~а г ! " г ! г( (59.12) Полагая а-! га=,~~ А! ~ В( г' (59.13) имеем В„(5) = гпах (59.14) !:а а< и Обозначим теперь первоначальный порядок обработки изделий через 5,: 5! = (Р(,, Рг,, Р(,, ..., Р; ,, Р(, Р( ,, Р( ,, ..., Р; ), (59.15) а через 5 — порядок, в котором переставлены местами Р! и й гй+! 5~=(Р(, Р(, Р(; Р(,, Р(„, Р(„Р(„, Р(„). (59.1б) Значения (.а н (,, полученные, исходя из порядков 5, и 5, и! а! совпадают для всех а, кроме, быть может, а=(г и а=(»+ 1.
1) Имеем В„(5,) = 0„(5,), гпах(1!й! (.Д !) шах (В»!! (»й!!) (59.17) если (59.18) 2) Если шах((.а»', (.'й! !) ~ шах((!»", 1,!й! !), (59.19) то один из двух порядков 5„ 5» предпочтительнее, Порядок 5„ в котором Р( , следует за Р(,, предпочтительнее 5м в котором Р(„, предшествует Р;й, если и шах ((.'й", Ейа'+!!) = (й-! й-! шах ! ~п' А, + А(, — ~', В(, г=! йй! й ! А( — ~ Вг — В( г ! г й+!/' (59.22) „((и! (п~ ) С ((!йг (!й!,) (59.20) Так как ( й й-! йй! й тахК»', г.»й!)=шах~~ Л;,— ~~'„Вг,, 2, Л( — ~ч'„В, (59.21) г=! г=! г г=! г=! то мы можем записать й-! й+! ~ В! — ~~'.! А! + шах(1.йи 1йй!!)=гпах( — А,, В )— й ! ' т=! = — пип(А!... В! ) (59.23) н й-! й+! ~ В! — ~с,'й А! + шах(1'й', 1й.!й!)=шах( — А!„, — В )— й ! " г пип(А!В!й)(5924) Соотношение (59.20) перепишется тогда так: — пип(А!й+и В!й! < — пип(А!, В! ) (59.2б) или ш!п(Аьи В!,,) < пип(Л!,, В;,). (59.26) Таким образом, порядок Я! предпочтительнее Вй, если пип(Ай, В!,) < ш!п(А,„, В! ).
(59 27) Рассмотрим теперь порядок 5 =(Рйи Рй,, Рй,, ..., Рйй, РВ, Р! ). (59,28) Не следует изменять порядок В', если для любой пары соседних индексов имеем пип(А!, В!,)~(ш!п(Ай, В! ). (59. 29) Это выполняется, если А! меньше или рави В А В этом случае (59.29) равносильно пип(Л!„, В! )(пз!п(Айи ВВ). (59.30) Отсюда следует, что если в матрице !!тп!! есть А!й, не превосходящее всех других Ап и Вуп то порядок обработки должен начинаться Р! ! такое А,„может равняться нескольким другим А!, или В!!, но (по (59.30)) это не препятствует выбору А! в качестве начального элемента.
Соотношение (59.29) выполняется также, если ВВ меньше нли равно Абп Вби А!,. В этом случае оно равносильно т!п (Айи В!,) ( пип(А!, В! ). (59.31) Следовательно, если в матрице !!тп!! есть В!и не превосходящее всех других А! и Впи то порядок обработки должел заканчиваться Р!,, такое Вб может равняться нескольким другим А! илн Вби но (по (59.31)) это не препятствует выбору Вй в качестве конечного элемента. Тем самым мы показали, что, устанавливая по алгоритму Джонсона порядок прохождения изделий, мы действительно минимизируем время простоя станка Мь Случай трех станков.
Алгоритм Джонсона применим и вэтом случае, если 4п!пА!) гпахВР !' 1, 2, ..., и, (59,32) или пппС!) гпахВР 1=1, 2, ..., и, (59.33) где С! — — тм Нахождение оптимального порядка производится с помощью сумм А;+ В, и В;+ Сь Пример. Пусть в матрице (59.34) даны числа ты, теи тм, ти + теь тм + тал» / = 1, 2,..., 5: (59.34) Выполнено условие гп!п (А!) п4ах (В!), г ! (59.35) так как гп!п А, = 6 и гпах В, = 6. Следовательно, можно Рае 393. использовать алгоритм Джонсона. В качестве оптимального порядка получают одну из двух последовательностей (Р4, Рм Рз» Ро Рз) или (Р4» Рм Р„Рм Рз), (59.36) для каждой из которых время простоя равно 35. Рис. 393 иллюстрирует полученный результат.
360 УПРАЖНЕНИЯ 69А. Указать оптимальный порядок обработки изделий, используя алгоритм Джонсона, для следующих матриц 1]тп11: а) а) 59В. То же для следующих матриц (г) и (д), применяя алгоритм Джонсона, приспособленный к случаю трех станков. 4] й 60. Оптимизация потока в сети Транспортная сеть. Пусть 0 = (Е, Г) = (Е,11) — конечный граф без петель, для которого выполняются условия: 1) (31Хо ен Е) Г Хо = Я (60. 1) 2) (:-(1Хп ~ Е) ГХм = 3, (60.2) 3) каждой его дуге приписано значение с (и) ) О, и ~ О. (60.3) Такой граф называют транспортной сетью.
Х, называют вкодолг сети, Хп — выходол, а с(и) — пропускной способностью дуги и. На рис. 394 изображен граф, являющийся транспортной сетью. Поток в транспортной сети. Функцию <р(и), определенную на множестве 11, называют потоком в транспортной сети, если: 1) (7и ~ 11) ср (и) ) О, (60.4) 2) ()))Х) чь Хо и ~ Х„) са ср(и) = 2'„)р(и), (60.5) п»н я» и+ л, л 361 Ряс 39ь дуг, заход»ших в А. Например, для сети на рис.
395, если взять А=(Х„Хм Х, Х,), (60.8) то Юл = ((Хм Хз), (Хп Хк) (Хз Хк) (Хг Хк), (Хь Хк)(Хм Хк), (Хз, Хк), (Хк, Хм)) (60.9) — разрез. Пропускная способность разреза. Число с(лкл)= ~ с(и) (60.10) и~с л называют пропускной способностью разреза 1)л. Например, для сети на рис. 395 с(()л)=8+ 2+ 5+ 6+ 9+ 5+ 8+8 51. (60.1!) Так как каждая частипа вешества, движушаяся по сети от Хз к Х„, пройдет по крайней мере однажды по какой-нибудь дуге из П., то, каковы бы ни были поток фх и разрез Ю всегда фх (~с(Пл). (60.12) збк где 1)л,— множество дуг, заходящих в Хи ()хк — множество дуг, исходяших из Х„ 3) (Уи ен Т.У) ф (и) < с (и), (60.6) Поток уподобляется количеству вешества, протекающему по дуге. В силу (60.5) имеем к — Х вЬ) к ~г = Х ю~ )) >(т, ф„„) (ккЛ и«О+ ий и хо ли Разрез.
Для подмножества А ~ Е такого, что хк ~ А, а хиенА, разрезом сети 6=(Е, 1)) называют множество 11л 90 лк Насыщенные дуги. Дугу и ен () называют насыи1енной, если ~р(и) = с(и). (60.! 3) Задача о максимальном потоке. Требуется определить такую функцию ~р(и), вен ь1, что ~рх принимает максимальное значение. Для решения этой задачи нам понадобятся три теоремы.
Для простоты записи положим (60.14) Теорем а 1. Пусть и=(Х„Х„,, ..., Хун Х,) — путь, соединяющий вход Хь с выходом Хн. Если все дуги этого пути / х ! / к т Рис. 393. ненасыщенные, то можно увеличить ~р, не нарушая соотношения (60.5) . Действительно, рассмотрим разности Ь(и) = с (и) — ~р(и) > 0 (60.15) и выберем среди них наименьшую Ь*. Увеличивая на Ь' поток в каждой дуге (что не нарушает соотношений (60.4) — (60.6)), приходим к потоку ~р + Ь*.
Пример (рис. 396 и 397). Рассмотрим путь и (Хь,А,В, С,В, Хн) в транспортной сети на рис. 395. Пропускные способности дуг обозначены цифрами в скобках, а пропускные способности потока — цифрами вне скобок. Очевидно, что этот путь не содержит насыщенной дуги. Имеем Ь(Хы А)=5 — 3=2, Ь(А, В)=8 — 5=3, Ь(В, В) 7 — 6 1, Ь(В, С)=9 — 2=7, Ь(С, Хн) =6 — 3=3, т. е. Ь'=Ь(В, 0) =1. (60.16) Итак, поток на каждой дуге этого пути и, следовательно, поток ~р можно увеличить на единицу.
363 Пусть й=(Х, Хй, у!,, „Х!, Х„) — цепь, соединяющая вход Ло с выходом Хн. Предположим, что она не является путем. Если ориентация дуги и совпадает с направлением прохождения цепи, то будем обозначать ее через и, е противном случае — через и. Положим м > б (и) = с (и) — ф (и), ф'= вв ф (и), + ь (60.17) (60.18) Следовательно, поток ф можно увеличить на 1. Потоки на дугах й таковы: — э ф'(Ль, Н)=2+1=3, ф'(А, Н)=1 — ! = О, ф' (А, У) = 3 + 1 = 4, ф' (У, К) = 4 .+ 1 = 5, ф'(Е К)=9 — ! =8, ф'(Р, Е)=3 — ! =2, (60.
22) ф'(УУ, )7)=5+1=6, ф'Я, Хн)=4+! =5. Поток ф' увеличить нельзя, так как е" = О. Полный поток. Поток ф транспортной сети назовем полным, если любой путь, соединяющий Хь с Хн, содержит по крайней мере одну насыщенную дугу. Иначе говоря, нельзя увеличить ф, рассматривая только пути; хотя это иногда можно сделать, рассматривая цепи, соединяющие Хо с Хн. 364 б'= в!пб(и), (60.19) И е" = ппп(ф*, б"). (60.20) Теор ем а П.
Если е* ) О, то, увеличивая на е' поток на каждой дуге и и уменьшая на е* поток на каждой дуге и цепи т, мы увеличим поток ф также на е'. Цепь, для которой е* = О, называют насыщеннои. П р и м е р (рис. 398 и 399). Рассмотрим цепь й = (Хь, УУ, А, У, К, Е, О, )с, Хн) транспортной сети на рис. 398.
Имеем б(Хо Н)=4 — 2=2 ф(А Н)=1 б(А У)=11 — 3=8 б(У, К)=8 — 4=4, ф(Е К)=9, ф(0, Е)=3, (60.21) б(УУ, !к)=7 — 5=2, б(Я, Хн)=6 — 4=2, + -Ъ. ф*=в!пф(и)=1, б'=пппб(и)=2, в!п[ф*, 5*1=1. Т е о р е м а П1, Если не существует цепи 6 от Хь до Хн с е* > О, то поток гь нельзя больше увеличить, т. е. он максимальный. Действительно, исключая из транспортной сети все дуги, для которых 6(и) = 0 или ~р(и) = О, получаем по крайней мере два несвязных подграфа (в противном случае существовала бы ненасыщенная цепь, соединяющая Х, с Хн).
Множество вершин того из них, среди вершин которого содержится Хн, обозначим через А. Очевидно, что А определяет разрез бь и Ф» хи Ф(и) — 2л р(и) = хи с(и)+О=с(1) ). (60,23) иап ь~п и~о Отсюда и из того, что общее количество вещества, входящего в А, не превосходит с(1)ь), заключаем, что все дуги и ец бх насьпценные, т. е. ~р' — максимальный поток. йн Из теорем 1, 11 и П1 вытекает следующая основная теорема. Т е о р е м а 1Ч (теорема Форда — Фалкерсона).
Для заданной транспортной сети максимальное значение потока равно минимальной пропускной способности разреза, т. е. гпах Ф» = ппп с (1) ь). л ~ хь в л, х„~ л Алгоритм Форда — Фалкерсона (43]. На этих теоремах основан следующий алгоритм для отыскания максимального потока в заданной транспортной сети. Этот алгоритм применим к любой транспортной сети.
Для иллюстрации же наших рассуждений, мы ограничимся случаем антисимметрического графа на рис. 400. 1) Отыскание какого-нибудь потока Строим некоторый поток ~, удовлетворяющий (60.4) — (60.6) (за гр можно принять и нулевой). На рис. 401 изображен поток ~р для сети на рис. 400. 2) Отыскание полного потока. Если поток ~р не полный, то в сети существует путь от Хь к Хн, все дуги которого не насыщены. Отыскиваем такой путь (в частичном графе, образованном ненасыщенными дугами).
Увеличивая поток через дуги этого пути до насыщения по крайней мере одной из них, получаем новый поток гр'. Если гь' — не полный поток, то операция повторяется. Таким образом, поток ~р, не являющийся полным, всегда может быть увеличен до полного.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
