Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 36
Текст из файла (страница 36)
(Имеется перевод: Ху Т. Целочисленное программирование и потоки н сетях. — Мл Мнр, 1974.) :32. Ни Т. С., ТЬе Мах!пиип СарвсИу Кои1е РгоЫет, Орегайопз йезеагсЬ, 9, 898 — 900 (1961) . 33. ЛасоЬв %. %., ТЬе Са(егег РгоЫет, !уаоа! йезеагсА 1.оу!з(!сз Оаш!ег!у, 1, 154 — 165 (1954). .84. К!е!п М., А Ргипа1 МеИсой Сов( Р1очсз, Мападетеп! Яс!енсе, 14 (3), 205— 220 (1967).
35. КИп2тап Ъ., Мар)ег А., $1и(к Л., ХЕТОЕХ вЂ” А Рго8гат 1ог бепегаИп8 ).аг2е Зса!е (Оп) СарасИа1ей Авз18птеп1, Тгапврог1аИоп апй М!и!пиип Сов1 Р1осч Хе!чгог1с РгоЫепва, Мапауетеп! Зссепсе, 20 (5), 814 — 822 (1974). 36. К!еИспап О. Н., герог1ей Ьу Н. РгапЬ, 1. Рг!всЬ !пс Хе!игогЬ Апа1ув(з, ЯссепЩ!с Атейсап, 223, 94 — 103 (ли!у 1970). 37. КИп8тап О.
Н., НиИк Л., Яо!ч)пй СопЫга)пей бепегаИкей Ме(могЬ РгоЬ1етв, КевеагсЬ Корок( ССЯ 257, Сеп1ег 1ог СуЬегпеИс З!ий!ез, ТЬе (!п)чегвИу о1 Техав а1 АизИп, 1976, 38. Кооргаапв Т. С., ОрИпнпп !)ИИкаИоп о1 Иге Тгапзрог1аИоп Зув(есп, РгосеесИп8в о1 1Ье 1п1егпаИопа! $1аИвИса! Соп(егепсез, %азЫп81оп, 11. С., 1947. 39. КиЬп Н. %., ТЬе Нип8аг(ап МеИсой 1ог !Ье Авв!Яптеп( РгоЫет, Асаиа! йезеагсд Воумйсз Оааггейу, 2, 83 — 97 (1955). 40.
).ам!ег Е. 1., А Зо!чаЫе Саве о! 1Ье Тгаче!!п8 Зв!евтап РгоЫет, Ма!1сетаВса! Ртоутатт!пу, 1, 267 — 269 (1971). 41. )лИ)е л. 11. С., ес а1., Ап А!догИЬт 1ог 1Ье ТгачеИпд Яа!еыпап РгоЫет, Орегас!опв йезеагсА 11 (5), 972 — 989 (1963). 42. 1г! М., Хе!мог1с Р!очс, Тгапврог1а1юп апй ЗсЬейиИп8, Асайепйс Ргевз, 1пс„ Хеис Уотс, 1969. 43.
М!п1е1са Е. Т., ЯЫег О. К., А Мо(е оп ап А18еЬга 1ог 1Ье К Вез( Кои1ев !п а Хе!чсогЬ, Хоигпа! о! 1Ле ПИА, 11, 145 — 149 (1973). 44. РоИас1с М., ТЬе Махипшп СарасИу Кои!а 1Ьгои2Ь а Хе(чсогЬ, Орега(!опз йевеагсЬ, 8, 733 — 736 (1960). 45. Ковз О. Т., Зо!апй К. М., А ВгапсЬ апй Воипй А18оНЬЬт 1ог Исе ОепегаИ- кей Авв10пгпеп1 РгоЫет, МаИсета!!са! Ргоугатт!пу, 8, 91 — 104 (1975).
46. ЯаИгиап К. О., Во!оЫсу б. К., Ки1ЬЬег8 У. б., Неиг!зИс Сов( ОрИт(каИоп о! !Ье Рейега! Те)раЬ Хе1ягогЬ, Ха1юпа1 Вигеаи о1 $1апйагйв ТесЬп(са1 Хо1е 787, 1973. 47. ЯЫег О. А., 11егаИче Ме(Ьойз 1ог Эе(егт!и!п8 !Ье К ЯЬог(ез1 РаИт 1и а Ме!исог1с, Ме(тотув, 6, 205 — 230 (1976). 48. ЯЫег О. А., СотрЫаИопа1 Ехрепепсе чг(Ис ап А18огИЬт (ог Р(псИп8 Иге К ЗЬог1ез1 РвИсв 1п а Хе!чгогЬ, Юошпа( о) йевеагсА, Майопа! Вагеаа о( Ясапйшйв, 788, 139 — 165 (Ли!у — Яер(етЬег 1974). 49. Зту!Ье %. К., ЛоЬпвоп 1...
1п1гойисИоп 1о )лпеаг Рго0тапнп(п8 вс(Иг АррИ- са1юпв, РгепИсе-НаИ, 1пс., Епа!емоой СИИв, М. Л., 1966. 150. %88атз Т. А., %ЬИе О. Р., А Мо(е оп Уеп'в А18оПИип !ог Р!нй!пд Иге Ьеп81Ь о1 АИ $Ьог1ез1 Ра!Ьз 1п !ч-Майе Моппе8а1%е ОЬИапсе Ме(счогйз, Дете минированные лозони в сетях Тоигла( о! Ие АззосгаЕол о) Сотри)!лИ Маей!пегц, 20 (3), 389 — 390 (Юп1)) 1973).
51. Че(по(1 А. Р., Лг., Традпег Н. М., Ор1ппа! Сарас11у Бс!геди!!пп 1, ОрегаЕолв. Лезеагсй,!О, 518 — 522 (!962). 52. Уздене М., Тйеоге1!са! ЕШс(епсу апд РагВа! Ецшча!епсе о1 М!п!пппп Соей Р!очг А!2оП(птз: А Вад ХеЬчог!г РгоЫет 1ог Сле $1тр!ех Ме()год, Орега1топв Кевеагсй Сеп(ег, Бп!чегвВу о1 СаИогп!а а1 Вег1ге!еу, ОКС 72-7, МагсЬ 1972. 53. Еайп С. Т., ОгарЬ-Т!геоге11са! Ме(!года !ог Ре1ес1!па апд РевсПЫпд без!а!й С!пв1егв, !ЕЕЕ Тгалзасйолз ол Сотрисегвг С-20 (1), 68 — 86 (Лаппагу".
1971). 54. Еап0ад1! %т А ВасЫоп0!п2 Моде! апд а Мп1Н-есЬе1оп Моде! о1 а Рупаппс Есопопйс 1.о1 5!хе РгодпсВоп Ьув1егп — А' Хе1игог!с АрргоасВн Мала5р тел( Яс!елее, 15, 506 — 527 (1969). Глава 3 АЛГОРИТМ ДЕФЕКТА. ОБОБЩЕННЫЙ АНАЛИЗ ,ДЕТЕРМИНИРОВАННЫХ СЕТЕЙ С ОГРАНИЧЕННОЙ ПРОПУСКНОЙ СПОСОБНОСТЬЮ Несомненно существует лучший способ сделать зто, н если нскать достаточно долго, то мы обязательно найдем его.
ггз высказываний исследователя 'После изучения большого числа различных алгоритмов, описанных в гл. 2, читателю может показаться, что для решения ;рассмотренных выше задач нет более эффективных методов. Однако в области системного анализа и оптимизации дело об° стоит таким образом, что в результате разработки более эф,фективных алгоритмов могут возникнуть усовершенствованные подходы к решению задач. В теории сетевого анализа значи.тельное место занимает алгоритм дефекта. Он является наибо.лее общим алгоритмом на детерминированных сетях с ограниченной пропускной способностью и имеет широкую область .применения. Поэтому несмотря на то что иногда он уступает по эффективности некоторым специальным алгоритмам, ему .уделяют особое внимание.
Описание алгоритма дефекта разбито на три части. В пертвой части дано теоретическое обоснование алгоритма и описана его работа на одном простом примере. Во второй части показана многогранность области его применения и описаны процедуры построения сети для большого числа классических сетегвых задач. В третьей части формулируются и решаются некоторые практические задачи. ЧАСТЬ Ь ОПТИМИЗАЦИЯ ПОТОКА, ОСНОВАННАЯ НА ПРИМЕНЕНИИ АЛГОРИТМА ДЕФЕКТА. ОПИСАНИЕ ТЕОРИИ Основная цель первой части состоит в описании теоретической основы алгоритма дефекта, который был разработан для юптимизации на сетях с ограниченной пропускной способностью.
.Алгоритм дефекта основан на теории двойственности линейного шрограммирования и условиях дополняющей нежесткости. Фор- 225 Алгоритм дефекта мальная схема работы алгоритма описана в общих чертах, однако помимо нее даются логическое обоснование метода и описание ряда решающих правил поиска решения задачи.
Затем весь алгоритм описывается в виде пяти основных шагов, выполнение которых осуществляется с помощью табличных решающих правил. В заключение, для того чтобы проиллюстрировать применение алгоритма дефекта при решении потоковых задач с сетями с ограниченной пропускной способностью, рассмотрен и решен вручную модельный пример. 3.1. ОСНОВНЫЕ ПОНЯТИЯ Перед тем как перейти к описанию алгоритма, определим основные понятия, используемые в данном разделе. Некоторые определения были даны выше, однако для наглядности изложения мы вновь остановимся на них.
1. Узел †э основной элемент сетевой диаграммы. Обычно он служит для обозначения физического объекта, являющегося начальным или конечным пунктом (например, пред~приятие, магазин, источник рабочей силы и т. д.). Узел, который порождает Я 4 Рис. 3.1. Ориентированная Рис. 3.2. Главный источник и главный сток. сеть.
поток (например, склад в некоторых задачах), называется источниколг. Узел, который поглощает поток (например, предприятие-заказчик), называется стоком. Множество узлов сети будем обозначать через В(. 2. Дугами, илн ветвями, называются линии, соединяющие различные узлы сети. Дуга является ориентированной, если поток по ней может протекать только в одном заданном направлении. Множество дуг сети будем обозначать через 8. 3.
Сеть — это связное множество дуг и узлов. Обычно она используется для описания физического процесса, в котором единицы потока движутся из источника (нли источников) в сток (или стоки). На рис. 3.1 изображена сеть, в которой узел 1 является источником, а узел 4 — стоком. Сеть может содержать несколько источников и стоков. На рис.
3.2 изображена сеть, в которой узлы 2 и 3 являются источниками, а узлы 3 и 15-1654 Глава 3 6 — стоками. К этой сети с помощью пунктирных дуг добавлены узлы 1 и 7, называемые главным источником и главным стоком соответственно. 4. Если поток по дуге может принимать только определенные значения, например если заданы верхняя и (или) нижняя границы потока, то говорят, что дуга имеет ограниченную пропускную способность. 5. При описании алгоритма удобно воспользоваться понятиями прямой и обратной дуги. Если направление движения ло Рис. З.З. Замкнутые сети. дуге совпадает с ее ориентацией, то дуга называется прямой. Если направление движения по дуге противоположно ее ориентации, то дуга называется обратной.
6. Сеть, содержащая дуги с ограниченной пропускной способностью, называется сетью с ограниченной пропускной способностью. 7. Циркуляцией называется поток по дугам сети, для которого в каждом узле выполняется условие сохранения, т. е. суммарный поток, входящий в узел, равен суммарному потоку, выходящему из узла. Для работы алгоритма дефекта требуется существование циркуляции; поэтому исходная сеть, как правило, соответствующим образом модифицируется. Так, для сетей, изображенных на рис.
3.1 и 3.2, необходимо ввести дополнительную дугу, чтобы соединить сток с источником. Эта дуга называется возвратной (рис. 3.3). Способы построения возвратной дуги зависят от вида сети. Подробно о них будет рассказано во второй части 'настоящей главы. 8. Для сети с ограниченной пропускной способностью всегда заданы верхние и нижние границы (которые могут быть равными нулю или бесконечности) потоков по всем дугам. Величина потока по каждой дуге должна быть заключена между верхним и нижним пределами, и это ограничение, как и все остальные, не должно нарушаться. В настоящей главе будут использованы следующие обозначения: )» — поток по дуге (1, /), Ь» — нижняя пропускная способность дуги (1, 1), У» — верхцяя пропускная Ллгоритм дефекта способность дуги (1, /), сп — стоимость прохождения единицы потока нз узла 1 в узел ].
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
