Сетевые модели. Тема10_Сетевые модели_net_lec. Тема 10 Сетевые модели

• Название: Тема 10 Сетевые модели
• Анкор: Сетевые модели
• Дата: 28.04.2021
• Размер: 1.35 Mb.
• Имя файла: Тема10_Сетевые модели_net_lec.pdf
• Тип: Анализ; #199664
• страница: 1 из 4

Тема 10 Сетевые модели
Введение
Сетевые модели могут строиться: в терминах событий: вершины- события, дуги - взаимосвязь событий; в терминах работ: вершины- работы, дуги - взаимосвязь работ; в терминах работ и событий: вершины - события результата работ (начало либо завершение), дуги - сами работы.
С помощью сетевых моделей можно решить множество задач. Рассмотрим следующие конкрет- ные примеры.
1. Проектирование газопровода, соединяющего буровые скважины в Мексиканском заливе с нахо- дящейся на берегу приемной станцией. Следует выбрать проект, в котором строительство газопровода имеет минимальную стоимость.
2. Определение кратчайшего пути между двумя городами, проходящего по существующей сети шос- сейных дорог.
3. Определение максимальной пропускной способности (в тоннах/год) трубопровода для транспор- тировки угольной пульпы с шахт Вайоминга на тепловые электростанции в Хьюстоне. (Уголь под напором воды поступает в специально спроектированный трубопровод и перегоняется с шахт в пункты назначения.)
4. Определение наиболее экономичной (имеющей минимальную стоимость) схемы транспорти- ровки нефти из пунктов нефтедобычи на перерабатывающие заводы и далее в центры распределения.
Сырую нефть и нефтепродукты можно транспортировать на танкерах, грузовиках или по нефтепроводу.
Помимо условий, определяющих верхний предел для добычи нефти и нижний предел для удовлетворе- ния спроса на нее, необходимо принимать во внимание ограничения мощности нефтеперерабатываю- щих заводов и пропускных способностей соответствующих транспортных коммуникаций.
Анализ указанных примеров показывает, что оптимизационные задачи на сети можно описать следую- щими четырьмя типами моделей:
1) минимизации сети;
2) нахождения кратчайшего маршрута;
3) определения максимального потока;
4) минимизации стоимости потока в сети с ограниченными пропускными способностями коммуникаций.
Рассмотренные примеры связаны с определением расстояний и материальных потоков. Однако во многих приложениях переменные могут представлять величины иной природы, как, например, потоки запасов или денег.
Перечисленные выше сетевые задачи можно сформулировать и решить как задачи линейного программирования. Однако специальная структура этих задач позволяет разработать более эффектив- ные алгоритмы, которые в большинстве случаев основываются на теории линейного программирова- ния.
Модель определения потока минимальной стоимости в сети с ограниченными пропускными спо- собностями имеет широкий круг практических приложений. Задачу о кратчайшем пути и задачу о мак- симальном потоке можно рассматривать как частные случаи транспортной задачи с ограниченными пропускными способностями. Однако метод решения задачи с ограниченными пропускными способно- стями неудобен, т.к. включает большой объѐм вычислительных процедур.
Необходимо подчеркнуть, что принцип оптимальности является основой поэтапного решения задачи, однако он не содержит информации о способах решения подзадач, возникающих на данном эта- пе. В связи с этим принцип оптимальности иногда рассматривается как слишком общий для того, что- бы быть полезным в практических исследованиях.
1. Определение кратчайшего маршрута для сети без циклов
Наиболее просто решается задача определения пути для сети без циклов, т.е. не имеющей путей возврата. Пусть сеть упорядочена, так что номера пунктов предшественников всегда меньше номеров

последующих пунктов. Для упрощения анализа упорядоченная сеть разбивается на ряд последователь- ных этапов.
Введем следующие обозначения: d
ij
– расстояние на сети между смежными узлами i и j. u
j
– кратчайшее расстояние между узлами 1 и j, u
1
=0.
Общая формула для вычисления u
j имеет вид: u
j
=
min i
{u j
+d ij
}
(кратчайшее расстояние до предыдущего узла i плюс расстояние между текущим узлом j и предыдущим узлом i).
Из этой формулы следует, что кратчайшее расстояние u
j до узла j можно вычислить лишь после того, как определено кратчайшее расстояние до каждого предыдущего узла i, соединенного дугой с уз- лом j.
Минимальное расстояние между начальным и конечным узлами находится в конце прямого хода вычислений. Оптимальный маршрут определяется при обратном проходе с использованием условия u
i
=
u j
-d ij
Заметим также, что полученное решение дает кратчайшее расстояние между узлом 1 и любым из других узлов сети.
Представленный тип вычислений интересен тем, что он имеет рекурсивный характер. Вычис- ления выполняются с использованием информации обо всех кратчайших расстояниях до непосред-
ственно предшествующего узла.
Рекурсивные вычисления представляют собой основу вычислительной схемы динамического программирования.
Рассмотрим алгоритм на примере сети, представленной на рис.1.1. Предварительно сеть упоря- дочена и разбита на последовательность этапов, определяющих ход вычислений.
Этап
1
Этап
2
Этап
3
Этап
4
Этап
5
U
2
=2 5
U
5
=7 11 6
2 8
10
U
4
=7
U
7
=13
U
1
=0 4
7 9
3 1
U
3
=4
U
6
=5
Рис. 1.1
Узел 1 представляет начальную точку (исходный пункт), а узел 7- конечную точку (пункт назна- чения). Заметим, что сеть не имеет циклов, поскольку нет ни одной цепи, связывающей узел с самим
2 4
1 3
6 7
5

собой. Для узла 1 можно вычислить лишь u
2
и u
3.
(Заметим, что, хотя узел 4 соединен узлом 1 дугой, со- ответствующее значение u
4
вычислить нельзя, пока не будут определены u
2
и u
3
).
Процедура завершается, когда получено значение u
7
Вычислительная схема состоит из следующих этапов:
Этап 1: u
1
=0.
Этап 2: u
2
= u
1
+d
12
=0+2=2).
u
3
= u
1
+d
13
=0+4=4.
Этап 3: u
4
= min {u
1
+d
14
, u
1
+d
24
, u
1
+d
34
} = min {0+10, 2+11, 4+3 } =7.
Этап 4: u
5
= min {u
2
+d
25
, u
4
+d
45
}= min {2+5, 7+8 } =7. u
6
= min {u
3
+d
36
, u
4
+d
46
}= min {4+1, 7+7 }=5.
Этап 5: u
7
= min { u
5
+d
57
, u
6
+d
67
} = min {7+6, 5+9 } =13.
Минимальное расстояние между узлами 1 и 7 равно 13, а соответствующий маршрут-
1 2
5 7, который находится на обратном проходе с использованием условия : u
i
=
u j
-d ij
Заметим также, что полученное решение дает кратчайшее расстояние между узлом 1 и любым из других узлов сети.
Вычисления выполняются с использованием информации обо всех кратчайших расстояниях до
непосредственно предшествующего узла. Например, в узле 5 величина u
5
вычисляется по кратчайшим расстояниям между узлом 1 и узлами 2 и 4, т.е. u
2
и u
4
. Заметим, что не обязательно знать конкретный маршрут, дающий кратчайшее расстояние между узлами 1 и 4. Величина u
4 включает всю информацию, необходимую для узла 4. Именно такая информация позволяет использовать рекурсивные вычисления.
Все вычисления можно провести непосредственно на сети (рис. 1.1).
Для решения таких задач используется теория графов и алгоритмы, разработанные на основе теории графов.
2. Теоретические основы теории графов
2.1. Основные определения графа.
В настоящее время теория графов привлекает все большее внимание специалистов самых разных областей науки и техники, являясь эффективным аппаратом формализации современных инженерных задач, связанных с дискретными объектами. Такие задачи возникают при проектировании интегральных схем и схем управления, при исследовании автоматов и логических цепей, системном анализе, автома- тизированном управлении производством, в теории расписаний и дискретной оптимизации.
Родившись при решении головоломок и занимательных задач (задача о кенигсбергских мостах, о шахматном коне, о ферзях, «кругосветное путешествие» и т.п.), теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов в различных областях знаний. Она явля- ется очень наглядной для анализа путей и маршрутов.
Чтобы составить наглядное представление о графе, достаточно вообразить некоторое множество точек плоскости или пространства (вершины) и множество отрезков прямых или кривых линий (ребра или дуги), соединяющих все или некоторые из этих точек. Если в паре вершин x i и x j
указанно направ- ление связи, то соединяющий их отрезок называется дугой, если же ориентация не указана, - ребром.
Если в графе все ребра являются дугами, то он называется ориентированным (орграфом), если ни одно не является дугой, - то неориентированным. Иногда рассматривают смешанные графы, состоя- щие из дуг и ребер.
Путем в орграфе называется последовательность дуг, в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь, проходящий через все вершины, и притом только по одному ра- зу, называется гамельтоновым. Путь, содержащий все дуги графа и притом только по одному разу, называется эйлеровым. Конечный путь, у которого начальная вершина совпадает с конечной, называет- ся контуром.
В неориентированном графе последовательность ребер, в которой каждые два соседних ребра смежны, называется цепью, а конечный путь, у которого начальная и конечная вершины совпадают, - циклом.

В различных приложениях теории графов дугам (ребрам) графов, моделирующим реальные про- цессы, обычно сопоставляют какие-либо числовые характеристики. Например, если дугами изобража- ются транспортные магистрали, то числовой характеристикой дуги может быть пропускная способность соответствующей магистрали и т. д. В подобных случаях говорят, что дугам графа приписаны опреде- ленные веса, а сам граф с весами на дугах называют взвешенным.
Граф часто обозначают символом G (V,E), G от английского Graph, V от Vertices – вершины, E от
Edges – ребра. Взвешенные графы также называют сетями, их часто обозначают N (V,E,W), где N от английского Network – сеть, а W от Weight – вес.
Циклом называется цепь из V в V.
Часто в задачах встречается следующая конструкция - есть дома и дороги, их соединяющие; у каждой дороги есть длина. В терминах же теории графов, дома называются "вершинами", дороги - "ре- брами" или "дугами", а длина дороги "весом ребра" или "весом дуги". Таким образом фраза 'Найти ми- нимальный вес пути между вершинами s и k в графе' может быть переведена так: 'Есть дома и дороги их соединяющие. Также заданы длины дорог. Найти кратчайшую длину пути от города s до города k, если двигаться можно только по дорогам.
2.2. Задача о кратчайшем пути.
Задача о кратчайшем пути состоит в нахождении связанных между собой дорог на транспортной сети, которые в совокупности имеют минимальную длину от исходного пункта до пункта назначения.
Пусть дан граф G = (V,Е) дугам которого приписаны веса (стоимости), задаваемые матрицей С =
[c i,j
] . Задача о кратчайшем пути состоит в нахождении самого короткого пути от заданной начальной вершины s V до заданной конечной вершины t V, при условии, что такой путь существует, т.е. при условии, что t принадлежит множеству, достижимому из вершины s. Элементы c i,j матрицы весов С мо- гут быть положительными, отрицательными или нулями, что в большей степени и определяет выбор алгоритма. Единственное ограничение состоит в том, чтобы в G не было циклов с отрицательным сум- марным весом.
Существует ряд алгоритмов решающих задачу нахождения оптимального варианта пути между заданными узлами:
Волновой алгоритм
Позволяет найти один или все возможные пути между двумя заданными вершинами графа (орграфа), количество промежуточных вершин в которых минимально.
Алгоритм Дейкстры
Позволяет найти один или все возможные пути минимальной суммарной длины между двумя задан- ными вершинам взвешенного графа(орграфа) с неотрицательными весами ребер (дуг).
Алгоритм Форда
Позволяет найти один или все возможные пути минимальной суммарной длины между двумя заданны- ми вершинами взвешенного графа (орграфа) с произвольными весами ребер (дуг).
Алгоритм Флойда
Используется, если надо найти кратчайшие пути между всеми парами вершин взвешенного графа (ор- графа) с произвольными весами ребер (дуг).
Алгоритм Форда - Беллмана
Для случая, когда не существует замкнутых маршрутов, для которых сумма цен отрицательна. Найти в этом случае маршрут с наименьшей стоимостью.

Алгоритм Йена
Позволяет находить k-кратчайшие пути без циклов последовательно
Алгоритм Флойда-Уоршелла
Представляетпоследовательность операции над матрицей, в которой хранятся расстояния из одного го- рода в другой
Алгоритм Шимбелла
Находит по матрице кратчайшие расстояния между всеми парами вершин.
Можно дать много практических интерпретаций задачи о кратчайших путях.
Например, вершины могут соответствовать городам, а каждая дуга – некоторому пути, длина ко- торого представлена весом дуги. Мы ищем затем кратчайшие пути между городами.
Вес дуги также может соответствовать стоимости (или времени) передачи информации между вершинами. В таком случае мы ищем самый дешевый (или самый скорый) путь передачи информации.
Ещѐ одну ситуацию мы получаем, когда вес дуги ,x j
> равен вероятности p(x i
,x j
) безаварийной работы канала передачи информации. Если предположить, что аварии каналов не зависят друг от друга, то вероятность исправности пути передачи информации равна произведению вероятностей составляю- щих его дуг. Задачу нахождения наиболее надѐжного пути легко можно свести к задаче о кратчайшем пути.
Наиболее простой случай задачи о кратчайших путях - если все цены равны 0 или бесконечны.
Другими словами, мы интересуемся возможностью попасть из i в j, но за ценой не постоим. В других терминах: мы имеем ориентированный граф и нас интересуют вершины, доступные из данной.
Сейчас нас интересует такая задача: не просто перечислить все вершины, доступные из данной, но перечислить их в определенном порядке. Два популярных случая - поиск в ширину и в глубину.
Поиск в ширину:
Надо перечислить все вершины ориентированного графа, доступные из данной, в порядке увели- чения длины пути от нее.
Начиная с произвольной вершины приписываем ей номер 0. Каждой вершине из окружения при- писываем номер 1, и т. д. Если исходный граф связен, т. е. существует путь между любыми двумя вер- шинами, то поиск в ширину занумерует все его вершины. Таким образом можно найти кратчайшую цепь и множество всех вершин, достижимых из заданной.
Поиск в глубину:
Рассматривая поиск в глубину, удобно представлять себе ориентированный граф как образ дерева. Бо- лее точно, пусть есть ориентированный граф, одна из вершин которого выделена. Будем полагать, что все вершины доступны из выделенной по ориентированным путям. Построим дерево, которое можно было бы назвать "универсальным накрытием" нашего графа. Его корнем будет выделенная вершина графа. Из корня выходят те же стрелки, что и в графе - их концы будут сыновьями корня. Из них в дере- ве выходят те же стрелки, что и в графе и так далее. Разница между графом и деревом в том, что пути в графе, ведущие в одну и ту же вершину, в дереве "расклеены". В других терминах: вершина дерева - это путь в графе, выходящий из корня. Ее сыновья - это пути, продолженные на одно ребро. Заметим, что дерево бесконечно, если в графе есть ориентированные циклы. Имеется естественное отображение де- рева в граф (вершин в вершины). При этом каждая вершина графа имеет столько прообразов, сколько путей в нее ведет. Поэтому обход дерева (посещение его вершин в том или ином порядке) одновремен- но является и обходом графа - только каждая вершина посещается многократно. Будем предполагать, что для каждой вершины графа выходящие из нее ребра упорядочены (например, пронумерованы). Тем самым для каждой вершины дерева выходящие из нее ребра также упорядочены. Будем обходить дере- во так: сначала корень, а потом поддеревья (в порядке ведущих в них ребер). Если выкинуть из этого обхода повторные посещения уже посещенных вершин, то получится то, что называется "поиск в глу- бину".

Отыскание кратчайшего пути имеет естественную интерпретацию в терминах матриц. Пусть
A - матрица цен одной авиакомпании, а B - матрица цен другой. (Мы считаем, что диагональные эле- менты матриц равны 0.) Пусть мы хотим лететь с одной пересадкой, причем сначала самолетом компа- нии A, а затем - компании B. Сколько нам придется заплатить, чтобы попасть из города i в город j?
Можно доказать, что эта матрица вычисляется по обычной формуле для произведения матриц, только вместо суммы надо брать минимум, а вместо умножения - сумму.
Обычное (не модифицированное) умножение матриц тоже может оказаться полезным, только матрицы должны быть другие. Пусть есть не все рейсы, а только некоторые, a[i,j] равно 1, если рейс есть, и 0, если рейса нет. Возведем матрицу a (обычным образом) в степень k и посмотрим на ее i-j-ый элемент. Он равен числу различных способов попасть из i в j за k рейсов.
Случай, когда есть не все рейсы, можно свести к исходному, введя фиктивные рейсы с бесконеч- но большой (или достаточно большой) стоимостью.
3. Нахождение кратчайшего пути в сети с циклами
3.1. Схема алгоритма Дейкстры:
Для решения данной задачи рассмотрим алгоритм Дейкстры, как классический пример нахож- дения кратчайшего пути в сети с циклами.
Граф может быть как ориентированным, так и нет. Требуется найти самый короткий простой путь для двух выделенных вершин графа.
Для нахождения пути каждой веpшине будем пpиписывать следующую инфоpмацию:
1. длину кpатчайшего пути от начальной веpшины до данной веpшины;
2. пpизнак, говоpящий о том, что
- мы не были в данной вершине;
- длину пути до этой вершины можно уменьшить;
- длину пути до этой вершины уменьшить нельзя;
3. Ссылку на метку предыдущей вершины в пути.
Нахождение пути проводится в три этапа:
на первом этапе создается начальная разметка; на втором этапе разметка изменяется; а на последнем этапе по разметке восстанавливается путь.
Разметка вершин делается так:
1.
Для всех вершин, кроме начальной, устанавливаем равным бесконечности признак того, что мы здесь еще не были; оставляем неопределенными длину пути и ссылку на предыдущую вер- шину.
2.
Для начальной вершины длину пути устанавливаем равной нулю, признак того, что длину пути уменьшить нельзя, номер предыдущей вершины оставляем неопределенным.
До тех поp, пока можно уменьшить длину до конечной точки пути, делаем следующее:
1. уменьшаем длины путей до веpшин
Для этого смотpим, к каким веpшинам ведут pебpа от веpшины, пpизнак котоpой был установлен в значение 'длину пути уменьшить нельзя' последним.
Для каждой из этих веpшин выясняем, что меньше: длина пути, пpиписанная веpшине pанее или длина пути полученного пpи добавлении pебpа. Пpи необходимости коppектиpуем длину пути до веpшины и номеp пpедыдущей веpшины в пути.
2. из всех веpшин, пpизнак котоpых говоpит о возможности уменьшения длины пути, выбиpаем веpшину, длина пути до котоpой минимальна. Говоpим, что длину пути до этой веpшины уменьшить нельзя.
3.Hаконец, мы найдем длину неуменьшаемого пути до конечной вершины.
Теперь осталось восстановить сам путь. Так как мы в каждой вершине запоминали, откуда мы при- шли, то это делается просто: узнаем из какой вершины мы пришли в конечную, затем узнаем, из ка-

кой вершины мы пришли в вершину перед конечной и так далее, пока не окажемся в начальной вершине.