Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 63
Текст из файла (страница 63)
5.3). Коэффициент выигрыша этого цикла равен 2 и поэтому д/(д — 1) =2.. Рассматривая узел 4 как выпускающий и используя (5.9), вычисляем значение 1/4.' Глава а Значения Уз и Уз могут быть вычислены с помощью (5 8г): Уз= (Уз+сзз)/А4з= (80 — 8)/4=18, Уз= (Уз+сев)/Азу= = (18 — 2)/2=8. Узлам 3, 2 и 4 цикла, изображенного на рис.5.3, приписываются новые пометки (4, 18), (3, 8) и (2, 80) соответственно.
Поскольку узел 4 является стоком, то увеличение потока осуществляется с минимальными затратами в том случае, если этот узел выбрать в качестве выпускающего узла. При этом может быть получен ,ь поток, стоимость единицы которого равна 80. Как н ~Ъ на итерации 1, максимальный поток, который может быть получен в выпускаю- 3 сз4 4 щем узле, зависит от дугоАзз= 4 вых множителей и верхних границ потоков по дугам.
Рис. 5.3. Подсеть. Однако максимальный поток в цикле определяется коэффициентом выигрыша цикла. Величина максимального потока, порождаемого циклом в выпускающем узле, вычисляется следующим образом 1161: Рь ~ ппп 1/„П аг (5.10г) Дуга Ь (гь П а, Гь (С)) гз м=з (4, 3) 1 1/2 2 1 (3, 2) 2 2 1/2. (2, 4) 3 4 1/4 1 где й — номер выпускающего узла, я — коэффициент выигрыша цикла, и †чис дуг в цикле, (/з — верхняя граница потока по й-й дуге цикла, аз — множитель й-й дуги.
Предполагается, что дуги цикла занумерованы так же, как это было сделано при рассмотрении формулы (5.9). Отметим, что правая часть равенства (5.10г) равна правой части равенства (5.10а), умноженной на функцию от коэффициента выигрыша цикла. В следующей таблице приводятся результаты вычислений, проведенных на итерации 2. )1авеее вовроем Из (5.10г) следует, что Ге=1/2 пип11, 1, 11 =1/2, Следовательно, максимальный поток в выпускающем узле равен 1/2. Для определения нужных поправок потоков по дугам в случае, когда существует генерирующий цикл, нельзя воспользоваться обычными последовательными процедурами обратного поиска.
Однако в этом случае может быть использована следующая формула 1161: /ь = гв ~, 1 ~ П а,. (5.! Од) Применяя к дугам цикла, изображенного на рис. 5.3, формулу (5.10д) при т=3, Рв=1/2 и й/!(й — 1) =2, получаем следующие поправки: е 1[а, Л 14,3) . 1 2 !/2 13, 2) 2 112 2 12, 4) 3 1,'4 4 Поправки потоков по дугам, не указанным в приведенной выше таблице, равны нулю. Новая величина потока по дуге равна сумме величины, вычисленной на итерации 1, и поправки, соответствующей потоку по дуге в маргинальной сети, т. е. Р, 1') =/ (')+0=12+0=12, /„!') =/„(')+О= 0+0= О, Приращение потока равно 1/2 и после выполнения итерации 2 Р=1, Р=12.
Стоимость получения единицы потока равна 32 (итерация 1) +80 1/2=72. Остановимся на обобщении полученных выше результатов. Пусть /„11-о — поток по дуге' (1, /) исходной сети на итерации 1 — 1. Пусть /п1') — величина потока по дуге (1, /) маргинальной сети, построенной на /-й итерации. И наконец, пусть /))п) — ве- Глава 5 личина потока по зеркальной дуге (1, () маргинальной сети, построенной на 1-й итерации. Если на итерации ! — 1 дуга (1, 1) не насыщена, то ее входной поток может быть увеличен на величину выходного потока узла ! маргинальной сети итерации 1, т. е.
Пометка (О, О) узла 1 не изменяется, т. е. Р! О. Результаты выполнения процедуры расстановки пометок приведены в следующей таблице. Дуга, входящая узел у в узел 1 го Ао в) ро )'~ пометка 3 (1, 3) 20 1,/2 О 4 (3,4) 2 1!4 40 2 (4, 2) — 48 4 168 1 (2,!) — б 3 30 3 (2,3) ! !/2 30 40 168 30 8 64 40 (1, 40) 1 68 (3, 148) зо (4, зо) о (о, 0) Ни один цикл не найден, и каждому узлу приписана пометка.
;Цепь минимальной стоимости задается последовательностью (т) — г 0-!)+Г (() (5.11а) С другой стороны, если поток по дуге (1, 1) исходной сети положительный, то он может быть уменьшен на величину выходного потока зеркальной дуги Ц, !) маргинальной сети итерации 1, т. е. Г!.") = 7!)()-2) — Г)!()))А!). (5.11б) Отслеживая величины 1!1(з) потоков по дугам, можно показать, что новая величина потока в стоке равна 1, а стоимость потока равна 72. Дуги (1, 2) и (2, 4) теперь стали насыщенными и поэтому могут быть исключены. Зеркальные дуги (2, 1) и (4, 2) включаются в маргинальную сеть для того, чтобы определить способ возможного уменьшения потоков. Итерация 3.
888 Новые вопросы дуг (1,3), (3, 4). Максимальный поток в стоке может быть вы- числен с помощью формулы (5.10а), для применения которой необходимы величины, содержащиеся в следующей таблице. Дуга Ю О . ь и, П о, г, О,З) 11,41 2 1б 1/8 2 2 1/4 1/2 Узлу 4 должна быть приписана пометка (О, оо). Поскольку аугментальная цепь потока не может быть построена, то теку- 28 — 1854 Из (5.10а) следует, что Р)=пни[2, 1/21 = 1/2. Выполняя процедуру обратного поиска так, как зто показано на итерации 1, получаем следующие поправки: Я" = (1/2)/(1/4) =2, /и") = =2/(1/2) =4, /))1') =/е)1))=0.
Измененные потоки по дугам исходной сети могут быть вычислены с помощью соотношений (5.11а) и (5.116): /,з~'~ = /)в'и — /в)'~~/А,в = 12 — 0 = 12, )в)=/ и)+/ )е)=0+4=4, (з) / м)+/ <е) О+2 2 Кроме того, поскольку /е)1')=/е41')=О, то /ее)е)=/евм)=0, /е«') =/ееы) =4. СЛЕдОВатЕЛЬНО, УВЕЛИЧЕНИЕ ПОтОКа ВНОВЬ СОСтаВ- лает 1/2 единиц, общий поток равен Р=1)/з и Р=16. Стоимость получения этого потока равна 32 (итерация 1) +40 (итерация 2) +(1/2) 168=156. Дуги (1, 2), (2, 4) и (3, 4) исключаются, а зеркальные дуги (4, 3) и (3, 1) включаются для того, чтобы определить способ возможного уменьшения потоков по соответствующим исходным дугам.
Итерация 4 Глава Б щее решение является оптимальным. Как видно из приводимого ниже рисунка, в узел 1 входит 16 единиц потока, а из узла 4 выходит 1'/в единиц потока. Соответствующая минимальная стоимость равна !2.2+4 20+4 12+2 2=156, что также следует из результатов, полученных на итерации 3. гб ад О. 3Аключение Алгоритмы, описанные в части 1, были даны с той целью, чтобы показать сложность обобщенных сетевых задач и сообщить читателю основные сведения, необходимые для решения других классов задач.
Процедура расстановки пометок, хотя и носит общий характер, при численной реализации становится громоздкой и относительно неэффективной для больших систем. В своей работе Йенсен и Барнес 1171 обобщают основные понятия, рассмотренные в равд. 5.5 — 5.9, и предлагают подход, заслуживающий особого внимания с вычислительной точки зрения. Кроме того, ими разработан высокоэффективный алгоритм, основанный на теории двойственности в линейном программировании, позволяющий решать задачи большой размерности с линейной, строго выпуклой илн строго вогнутой целевой функцией.
Для более глубокого изучения сетевого анализа мы рекомендуем обратиться к этой работе. Хотя в данном разделе не проводилось исследование поглощающих циклов, оно может быть проведено аналогично исследованию генерирующих циклов. Однако в задачах о максимальном потоке поглощающие циклы не представляют особого интереса и при разработке алгоритмов их можно ие рассматривать. ЧАСТЬ П. СТОХАСТИЧЕСКИЕ СЕТИ. ГРАФИЧЕСКИЙ МЕТОД ОЦЕНКИ И ПЕРЕСМОТРА ПЛАНОВ (ГЕРТ) До сих пор мы рассматривали лишь те системы, которые описываются детерминированными сетями. Для полного выполнения типичной сети проекта необходимо выполнение всех Новые вопросы дуг'1.
Из этого условия следует, что в такую модель не могут быть включены операции с обратной связью, поскольку они представляются петлями, существование которых в свою очередь означает, что конечный узел операции должен быть выполнен раньше ее начального узла. В области детерминированных сетей наиболее полно были изучены две модели.
В первой нз них, модели критического пути, время выполнения каждой дуги фиксированно. Во второй, модели ПЕРТ, для каждой дуги существует несколько возможных времен ее выполнения. При моделировании работы промышленных комплексов нередко наиболее гибкими и полезными оказываются сетевые модели со стохастической структурой. Стохастическую сеть определим как сеть, которая может быть выполнена только при выполнении некоторого подмножества дуг; при этом время выполнения каждой дуги (операции) выбирается в соответствии с вероятностным распределением. В стохастических сетях для выполнения узла не является необходимым выполнение всех дуг, входящих в него. Поэтому в таких моделях допускается существование циклов и петель, 5.11.
СЕТЕВОЕ ПРЕДСТАВЛЕНИЕ Узлы стохастической сети могут быть интерпретированы как состояния системы, а дуги — как переходы из одного состояния в другое. Такие переходы можно рассматривать как выполнение обобщенных операций, характеризуемых плотностью распределения, или функцией массы, и вероятностью выполнения. Каждый внутренний узел стохастической сети выполняет две функции, одна из которых касается входа в узел, а другая— выхода.
Обычно эти функции называют входной и выходной. 1. Входная функция. Она определяет условие, при котором узел может быть выполнен. 2. Выходная функции Она определяет совокупность условий, связанных с результатом выполнения узла. Другими словами, с помощью выходной функции указывается, должны ли выполняться все операции, которым данный узел непосредственно предшествует, или только одна из них. Отметим, что начальный узел сети выполняет только выходную функцию, в то время как конечный узел — только входную. Существуют три типа входных функций. 5.!1.1. ВХОДНЫЕ ФУНКЦИИ Тип 1.
Узел выполняется, если выполнены все дуги, входящие в него. о Под выполнением дуг и узлов сети понимается выполнение соответствующих операций. — Прим. перев. Глава 5 Тип 2. Узел выполняется, если выполнена любая дуга, входящая в него. Тип 3. Узел выполняется, если выполнена любая дуга, входящая в него, при условии, что в заданный момент времени может выполняться только одна дуга. 5.11.2. ВЫХОДНЫЕ ФУНКПИИ Тип 1. Все дуги, выходящие из узла, выполняются, если этот узел выполнен. Данная функция называется детерминированной выходной функцией.
Тип 2. Ровно одна дуга, выходящая из узла, выполняется, если узел выполнен. Выбор такой дуги может быть описан с помощью вероятности. Поэтому эта функция называется вероятностной. в т В настоящем разделе мы рас- смотрим два типа узлов: а) узлы в д~~р~~~~ро~~~вив видов.
в оо с третьим типом входной функроятлоотнив выход. ции и детерминированной выход- ной функцией и б) узлы с третьим типом входной функции и вероятностной выходной функцией. Сети, содержащие только эти два типа узлов, называются ГЕРТ-сетями. Для ГЕРТ-узлов используются обозначения, приведенные на рис. 5.4 ~34, 351. Исправление Продажа в розницу Поступление нв линию сборки Сдача в метвллолок Рве. 5.5. Пример ГЕРТ-сети.
Покажем, как можно воспользоваться этими обозначениями при рассмотрении простой системы контроля качества продукции (рис. 5.5). В результате выполнения операции проверки система определяет, какие детали следует сдать в металлолом, какие исправить, а какие отправить на линию сборки. После исправления детали могут быть проданы в розницу, сданы в металлолом или отправлены непосредственно на линию сборки. Новые вопросы 5.12. ОСНОВНЫЕ ПРОЦЕДУРЫ СИСТЕМЫ ГЕРТ Рассмотрим сеть 6= (я(, А), содержащую только ГЕРТ-узлы, которые образуют множество Х. Пусть время выполнения ОПЕрацй)ва(1, 1) ЕСтъ СЛуЧайНая ВЕЛИЧИНа у(!.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
