Методы анализа сетей. Филлипс. Гарсиа-Диас (1981) (1186150), страница 3
Текст из файла (страница 3)
Сетевой анализ не является дисциплиной, принадлежащей какой-то одной области науки или отрасли производства. Основное достоинство сетевого подхода заключается в том, что ои может быть успешно применен к решению практически лю- 12 Глава 1 бой задачи, когда исследователь обладает необходимыми знаниями и способностью точно построить сетевую модель.
Преимущества использования сетевых моделей можно сформулировать следующим образом: 1. Сетевые модели могут точно описать многие, реально существующие системы. 2. Для людей, не занимающихся научной работой, сетевые модели являются, вероятно, более понятными, чем любые другие модели, используемые в исследовании операций. По-видимому, это следует из того, что «лучше один раз увидеть, чем сто раз услышать». Руководителю предпрвятия, наверное, легче понять сетевую диайрамму, чем абстрактные формулы. Кроме того, связанные, как правило, с .конкретными прикладными задачами сетевые модели являются несложными для работников, не имеющих специального математического образования.
3. Сетевые алгоритмы позволяют находить наиболее эффективные решенная при изучении некоторых больших систем. 4. По сравнению с другими методами оптимизации сетевые алгоритмы нередко позволяют, решать задачи со значительно ббльшим числом переменных и ограничений. Это становится возможным благодаря тому, что при использовании методов сетевого анализа часто удается ограничиться изучением лишь части рассматриваемой системы.
!.!. ОПРЕДЕЛЕНИЯ И ОБОЗНАЧЕНИЯ Сеть состоит из множества узлов и множества дуг, соединяющих их. Узлы иногда называют вершинами иии точками, а дуги — ребрами, звеньями, линиями или ветвями. Сеть может быть представлена в виде 6=()Ч, А), где !Ч вЂ” множество узлов сети 6, А — множество дуг сети 6. Примерами узлов сети могут быть пересечения автострад, электростанции, телефонные узлы, железнодорожные парки, аэропорты, водохранилища, вычислительные машины, точно определенные во времени события, или попросту «километровые столбы» проекта. Вообще узлом может быть точка, являющаяся источником или стоком некоторого потока, а также точка, в которой величина этого потока изменяется.
Поэтому узел можно рассматривать как точку ветвления в сети. Примерами дуг могут быть дороги, линии электропередачи, телефонные лиями, авиалинии, водные магистрали или обобщенные каналы, через которые протекает некоторый поток. Иногда дуги не имеют физического смысла, а используются для того, чтобы направить поток через узлы в нужной логической последовательности илн чтобы выполнялись определенные отношения предшествования. Введение Обычно узлам приписываются номера, чтобы, различать их или иметь возможность ими оперировать в процессе анализа. Очевидно, что нумерацию узлов можно осуществлять произвольным образом'>.
Однако исследования могут упроститься, если их занумеровать в определенном порядке. Говорят, что дуга, соединяющая узлы 1 и 1, направлена от 1 к 1, если единица потока, посылаемого от узла 1' к узлу 1' по этой дуге, уве- 6» — -От Рис. 1.1. Графическое изображение дуг и узлов. и — неориентированная дуга; б — приентнреванная дуга; а — биприентирпваииая дуга. личивает текущую величину потока в данной дуге, а единица потока противоположного направления уменьшает эту величи- ну. Дуги сети могут быть неориентированными, ориентирован- ными и бнориентированными. Неориентироеанной называется дуга, не имеющая определенного направления, ориентирован- ной — дуга, имеющая од'*"'""'"""' " ' Π— Г е у ориентированной — дуга, имеющая два направления.
а б При графическом Рис. 1.2. Замена биориентированной дуги ПрсдетаВЛЕНИИ СЕТИ УЗЛЫ двумя противоположно направленными думы обозначаем кружка- а — бнернентиреванная дуга; б — эквивалентное мн, дуги — отрезками пряпредставление. мой, а направления дуг указываем стрелками. Парой (1,1) мы обозначаем ориентированную дугу, направлен- ную от узла 1 к узлу 1. На рис. 1.1 изображены неориентирован- иая, ориентированная и биориентированная дуги соответственно. При решении большинства практических задач нет необхо- димости делать различие между неориентированными и био- риентированными дугами.
Кроме того, очевидно, что биориен- тированную дугу, соединяющую два произвольных узла 1 и /, можно заменить двумя ориентированными дугами 1'й 1) и (), Е) 1рнс. 1.2). Как отмечалойь выше, дуги сети можно рассматривать как каналы, по кото~ым протекает поток некоторого обобщенного 'э Интересное исключение из этого правила можно получить при анализе систем МКП и ПЕРТ. Как показано в гл. 4, нумерацию узлов лучше производить последовательно в возрастающем порядке. 14 Глава ! продукта.
Чистая величина этого продукта в заданном узле равна разности величн~н потока, втекающего в узел, и потока, вытекающего из него. Если эта разность положительна, то узел называется источником, а если отрицательна — стоком или конечным узлом сети. Сеть может содержать более одного стока или источника. Для удобства мы часто будем называть источником каждый узел, из которого поток только вытекает, а стоком — каждый узел, в который поток только втекает.
Напри мер, в сети, изображенной на рис. 1.3, узлы 1 и 2 являются источниками, а узлы 6 и 7 — стоказ ми. При описании некоторых алгоритмов предполагается, что сеть содержит только один источник и один сток. Такую сеть можно построить, вводя главный источник и главный сток и затем соединяя фиктивными дугами главный источник со всеми источниками, а глав- 4 ный сток — со всеми стоками. При сведении практических задач к потоковым задачам нередко бывает полезно разбить сеть на составные части исходя из направления потока. В связи с этим следует ввести часто используемое в теории сетей понятие, связанное с соединением двух узлов 1 и ! последовательностью дуг Е=(аь ам...,аь).
Целью из угла ! в узел ! называется последовательность дуг и узлов, в которой конечный узел каждой дуги является начальным узлом следующей (исключая первый и последний узлы последовательности). Следовательно, каждая дуга в такой последовательности ориентирована по направлению от узла ! к узлу 1. Путь отличается от цепи лишь тем, что в ием одна или несколько дуг могут быть направлены не к узлу 1, а к узлу й Это означает, что в отличие от цепи в пути не все дуги имеют одинаковое направление. Согласно этим определениям, цепь не может содержать биориентированную дугу, но может содержать неориентнрованную дугу. Обычно цепи и пути различают лишь при изучении потоков в ориентированных дугах; в данной книге мы также будем придерживаться этого соглашения.
В сети, изображенной на рис. 1.3, последовательность дуг (1, 3), (3, 5), (5, 3), (3, 6) образует цепь, а последовательность дуг (2, 4), (3, 4), (3, 6)— путь. Сеть называется неориентированной, если ни одна из ее дуг не имеет ориентации. В неориентированной сети понятия цепи и пути являются взаимозаменяемыми и соответствуют последовательности дуг, соединяющих два произвольных узла, Ваедеиив аб Циклом называется конечный путь, начальный и конечный узлы которого совпадают. На рнс. 1.3 последовательность дуг (4, 7), (4, 5), (5, 7) образует цикл. В частности, циклами являются контуры.
Контуром называется конечная цепь, начальный н конечный узлы которой совпадают. Очевидно, что циклы Рис. 1.4. циклические и ациклические сети, а — сеть, содержащая контуры; б — сеть, не содержащая контуров; е — ацнканчесная сеть. являются замкнутыми путями, а контуры — замкнутыми цепями.
Петля образуется одним узлом и одной дугой и поэтому является как контуром, так и циклом. В сети, изображенной на,рис. 1.3, последовательность дуг (3, 4), (4, 5), (5, 3) образует контур. Вырожденный цикл, или петлю, иногда называют одноступенчатым циклом, поскольку он содержит только одну дугу. Дуга (4, 4) сети, изображенной на 1рнс. 1.3, образует петлю. Говорят, что сеть является бесконтурной, если она не содержит контуров. Иными словами, сеть, содержащая только ориентированные дуги, называется басконтурной, если ее дуги не образуют контуров.
Такие сети обладают рядом специальных свойств, которые используются цри решении некотопых практических задач, связанных с поиском кратчайших и максимальных путин. На этих свойствах основаны алгоритмы 16 Глава 1 в системах МКП и ПЕРТ. На рис. 1.4, а, б изображены сеть, имеющая контуры, и бесконтурная сеть соответственно. Сеть, изображенная на .рис. 1.4, в, является аииклической, т. е. не содержит циклов. Сеть называется связной, если для любых двух различных узлов существует по крайней мере один соединяющий их путь или цепь. Частным случаем связных ориентированных и неориентированных сетей являются деревья.
Напомним, что множество всех узлов и дуг задается в виде 6= (й), А). Подмножество множества 6 определим как 6= (Й, А). Дерево определяется как связное подмножество 6, не содержащее циклов. Следовательно, для любых двух узлов дерева существует единственный путь, соединяющий их. В сети, содержащей и узлов, подграф из й узлов (й(п) является деревом, если выполнены любые два из следующих условий: 1. Подграф является связным. 2. Подграф не имеет циклов. 3. Число дуг в подграфе равно й — !.
Остовным деревом'> называется дерево, содержащее все узлы сети. Следовательно, если сеть содержит п узлов, то дерево с а узлами и~ и — 1 дугой является остовным. Если для указания некоторых естественных ограничений, накладываемых на дуги сети, сопоставить последним числае1, соответствующие, например, расстоянию, стоимости или другим аддитввным величинам, то мы сможет ввести понятие кратчайшего (илн максимального) остова.
Вес дерева определяется как сумма весов его дуг. Кратчайшим (максимальным) остовом называется дерево с минимальным (максимальным) весом. Деревья и остовы определяются как для ориентированных, так и для неориентированных сетей. Однако для сетей, содержащих только ориентированные дуги, следует ввести понятие древовндности. Древовидность можно представить себе как дерево, все дуги которого ориентированные.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
