Нахождение кратчайших путей

Орграф G(X, A) называется взвешенным, если каждой дуге (x,y) поставлено в соответствие некоторое действительное число l(x, y) - вес дуги (x, y). Весом маршрута x₁,x₂, …,x_n, x_n+1 называется число l= . Взвешенным расстоянием (w- расстоянием) между вершинами x и y называется минимальный из весов (x, y) – маршрутов. (x, y) – маршрут, вес которого равен расстоянию , называется кратчайшим (x, y) – маршрутом во взвешенном графе G.

Алгоритм Форда-Беллмана позволяет определить кратчайшее расстояние от фиксированной вершины графа G, называемой источником, до всех других вершин этого графа.

Задаётся строка D⁽¹⁾=(d₁⁽¹⁾, d₂⁽¹⁾,..., d_n⁽¹⁾), полагая d_i⁽¹⁾=0, d_j⁽¹⁾=w_ij, i≠j. В этой строке d_j⁽¹⁾ (i≠j) есть вес w_ij дуги (x_i, x_j), если (x_i, x_j) существует, и d_j⁽¹⁾=∞, если дуга (x_i, x_j) отсутствует в G. Далее определяется строка D⁽²⁾=(d₁⁽²⁾, d₂⁽²⁾,..., d_n⁽²⁾), полагая d_j⁽²⁾=min{ d_j⁽¹⁾, d_k⁽¹⁾ + w_kj}_{k=1,..., n}. При этом d_j⁽²⁾ - минимальный из весов (x_i, x_j) – маршрутов, состоящих не более, чем из двух дуг.

Продолжая процесс, на шаге s определяется строка D^(s)=(d₁^(s), d₂^(s),..., d_n^(s)), полагая d_j^(s)=min{ d_j^(s-1), d_k^(s-1) + w_kj}_{k=1,..., n}. Искомая строка w-расстояний получается при s=n – 1: d_j^(n-1) = . Работа алгоритма завершается на шаге k, если D^(k) = D^(k+1).

Задача. Найти кратчайшие расстояния от вершины 1 до всех других вершин в орграфе G с матрицей весов W:

.

Решение

Выберем в качестве источника вершину 1. Тогда D⁽¹⁾=(0, 1, ∞, ∞, 3), D⁽²⁾=(0, 1, 4, 4, 3), D⁽³⁾=(0, 1, 4, 4, -1), D⁽⁴⁾=(0, 1, 4, 3, -1). Таким образом, , , , , .

Варианты задачи №10

Взвешенный орграф G задан матрицей весов W. Найти минимальный и максимальный путь из вершины 1 в вершину 6.

Вариант1 Вариант 2

Вариант 3 Вариант 4

Вариант 5 Вариант 6

Вариант 7 Вариант 8

Вариант 9 Вариант 10

Вариант 11 Вариант 12

Вариант 13 Вариант 14

Вариант 15 Вариант 16

Вариант 17 Вариант 18

Вариант 19 Вариант 20

Вариант 21 Вариант 22

Вариант 23 Вариант 24

Вариант 25 Вариант 26

Вариант 27 Вариант 28

Вариант 29 Вариант 30

6 Сетевое планирование

Основные понятия и формулы

Одно из применений теории графов – сетевое планирование, которое применяют, например, для организации и составления календарных планов реализации больших комплексов работ.

После определения работ и связей между ними строится ориентированный граф, который называется сетевым графом (на производстве его обычно называют сетевым графиком). Сетевой граф не может содержать циклов.

Если сетевой граф содержит несколько начальных вершин (в которые не входит ни одна дуга), то можно добавить еще одну вершину и соединить ее дугами со всеми начальными вершинами: граф будет иметь одну начальную вершину. Совершенно аналогично вводится конечная вершина, из которой не выходит ни одна дуга.

Вершины графа называют работами. Временем наступления работы считают время, когда завершено выполнение всех работ, предшествующих данной.

Раннее начало t_i каждой работы будем определять так:

1) для начальной работы t₁=0;

2) раннее начало любой работы определяется как максимум ранних из начал предшествующих работ вместе с их длительностями: t_i=max(t_ki+d_ki), где t_ki – ранние начала работ, предшествующих i-той, d_ki – длительности этих работ.

Продолжительность Т всей разработки равна сумме раннего начала конечной работы и её длительности:

.

Продолжительность разработки равна длине критического пути.

Для определения состава критического пути необходимо найти вспомогательные величины: ранние начала работ в обратном графе (отношение предшествования в прямом графе превратится в отношение следования в обратном графе и наоборот).

Раннее начало t_i каждой работы обратного графа определим совершенно аналогично, как и для прямого графа, начиная с работы N n:

t_n=0, t_i=max (t_ki +d_ki).

Аналогично определяется продолжительность разработки Т:

.

Ясно, что продолжительность разработки и в том, и в другом случае должна быть одинакова.

Длина m_i максимального из всех путей, проходящих через i-тую работу вычисляется по формуле:

m_i = t_i + t_i +d_i.

Полный запас времени z_i данной работы определяется по формуле:

z_i = T - m_i.

Это величина, на которую можно увеличить длительность работы, чтобы длина критического пути не увеличилась.

Для работ, лежащих на критическом пути, z_i=0.

С целью упрощения расчетов и для наглядности каждая вершина графа представляется в виде круга, который разбивается на четыре сектора

Рисунок 8 - Представление вершины графа

(рисунок 8): в верхнем секторе проставляется номер работы, в левом - раннее время наступления работы ti., в правом – продолжительность работы di, в нижнем – полный запас времени zi.

Примеры

Пример. При анализе проекта разработки выяснилось, что она состоит из восьми работ, пронумеруем их от 1 до 8, продолжительность которых, соответственно, равны 5, 6, 10, 5, 9, 6, 4 и 7 неделям. Причем, работы 2, 3 и 4 могут выполняться после окончания работы № 1; работы 3, 4 не могут выполняться раннее выполнения работы №2; работа №5 может начаться только после выполнения работ №2 и 3; работа №6 выполняется только после выполнения работы №4; работа №7 может выполняться после окончания работ №3 и 5; выполнение работ №8 может начаться лишь после выполнения работ №5 и 7. Найти продолжительность выполнения разработки и критический путь ее выполнения.

Решение

Построим сетевой граф, используя исходные данные:

Вычислим временные характеристики графа:

t₁=0;

t₂=0+5=5 (к работе 2 ведет только один путь 1- 2);

К работе 3 ведут два пути 1: 1 – 3----- t₃=0+5=5;

2: 1 – 2 – 3-----t₃=5+6+11.

max t₃=11. Следовательно, t₃=11: выполнение работы №3 может начаться лишь через 11 недель.

Раннее время каждой из остальных работ определится совершенно аналогично. Полученные результаты сведем в таблицу 9.

Таблица 9 - Расчет раннего времени наступления работы

Продолжительность разработки Т = 34 + 7 = 41.

Построим обратный граф для вычисления временных характеристик t_i:

Вычислим временные характеристики обратного графа:

t₈=0; t₇=7; t₅=11,...

Полученные результаты сведем в таблицу 10.

Таблица 10 - Расчет раннего времени наступления работ в обратном графе

Номер работы
Номера последую-щих работ	5,7	3,5,6		2,3	1,2	1,2		-
di

Продолжительность разработки Т = 36 + 5 =41.

Для определения величин m_i и z_i составим таблицу 11.

Таблица 11 - Расчет полного запаса времени

Номер работы
di
ti
mi
zi

Из таблицы 11 видно, что запаса времени нет (z_i=0) у работ 1, 2, 3, 5, 7, 8. Таким образом, критическим является путь

1—2---3---5---7---8.

На этом планирование выполнения работ заканчивается, и начинается процесс управления выполнением разработки.

Варианты задачи №11

Таблица 12 – Варианты задачи №11

Продолжение таблицы 11

Продолжение таблицы 11

ЛИТЕРАТУРА

1. Горбатов, В.А. Основы дискретной математики. – М.: Высшая школа,1986.

2. Нефедов, В.Н. Курс дискретной математики: учебное пособие/ В.Н. Нефедов, В.А. Осипова. – М.: Изд-во МАИ, 1992.

3. Новиков, Ф.А. Дискретная математика для программистов. – СПб.: Питер, 2001.

4. Романовский, И.В. Дискретный анализ. – 2-е изд. – СПб.: Невский диалект, 2000.

5. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов. – Изд. 4-е/И.А. Лавров, Л.Л. Максимова. – М.: ФИЗМАТЛИТ, 2001.

6. Кофман, А. Введение в прикладную комбинаторику. – М.: Наука, 1975.

7. Новиков, Л.С. Введение в математическую логику. – М.: Наука, 1973.

8. Гиндикин, С.Г. Алгебра логики в примерах и задачах. – М.: Наука, 1972.

9. Оре, О. Теория графов. – М.: Наука, 1980.

10. Оре, О. Графы и их применение. –М.: Мир, 1965.

11. Судоплатов, С.В. Элементы дискретной математики: учебное пособие/ С.В. Судоплатов, Е.В. Овчинникова. – М.: ИНФРА-М, Новосибирск: Изд-во НГТУ, 2002.

12. Гаврилов, Г.П. Сборник задач по дискретной математике/ Г.П. Гаврилов, А.А. Сапоженко. – М.: Наука, 1977.

СОДЕРЖАНИЕ

Редактор

Подписано в печать 01.01.01. Формат 60х84 1/16

Отпечатано на ксероксе. Усл.п.л.1.39. Уч.-изд.л. 1,20

Бесплатно. Тираж 50 экз. Рег. № -д

Алтайский государственный технический университет им. И.И.Ползунова, Барнаул, пр. Ленина, 46

Отпечатано на ксероксе Бийского технологического института АлтГТУ им. И.И.Ползунова, г. Бийск, ул. Трофимова, 29

Поиск по сайту: