И.А. Кузнецов Сетевые модели. Методические указания к практическим занятиям

20

p(y)- p(x) = a(x,y).

(12)

С учетом приведенных соображений, формальное описание алгоритма поиска потока минимальной стоимости таково.

Шаг 1. (Задание начальных условий). Принять значение f (x, y) в

каждой дуге (x, y) равным 0. Кроме того, положить р(х)=0 для всех

вершин х.

Шаг 2. (Выявление дуг, в которых допускается изменение пото-

ка). Сформировать множество I, включив в него дуги (x, y) , для которых p(y)- p(x) = a(x,y) и f(x, y) < c(x, y) .

Сформировать множество R, включив в него дуги (x, y) , для кото-

рых:

p(y)- p(x) = a(x,y) и 0 < f (x, y) .

Сформировать множество N, включив в него дуги (x, y) , не во-

шедшие ни в I, ни в R.

На следующих этапах выполнения алгоритма изменения потока будут допускаться только в дугах, принадлежащих I или R. Следовательно, потоки могут изменяться в тех дугах, для которых выполняется соотношение (7).

Шаг 3. (Изменение потока). Применить алгоритм поиска максимального потока к исходной сети при найденном на шаге 2 распределении ее дуг по множествам I, R и N. Выполнение данного алгоритма заканчивается либо тогда, когда оказывается, что из s в t уже передано v единиц потока, либо тогда, когда окажется, что при текущем разбиении дуг на множества I, R и N полученный поток максимален. В первом случае закончить выполнение процедуры алгоритма: полученный поток заданной суммарной величины v и является потоком минимальной стоимости. Во втором случае проверить, не является ли полученный поток максимальным в исходном графе (путем исследования разреза, определяемого по окончании процедуры окрашивания в соответствии с алгоритмом поиска увеличивающей цепи - рассматриваемый поток является максимальным только в том случае, когда исследуемый разрез является насыщенным). Если это так, закончить выполнение алгоритма: найденный поток является в исходном графе максимальным из s в t и имеет при этом минимальную общую стоимость прохождения по соответствующей сети. В противном случае перейти к шагу 4.

21

Шаг 4. (Изменение вершинных чисел). Исходной информацией для выполнения данного шага являются результаты окрашивания вершин в алгоритме поиска увеличивающей цепи.

Увеличить на +1 вершинные числа р(х) для всех неокрашенных вершин (при этом обязательно увеличится р(t), поскольку вершина t является неокрашенной; если бы вершина t была окрашена, была бы найдена увеличивающая цепь). Затем вернуться к шагу 2.

Пример. Найдем поток минимальной стоимости на ГТС, изображенном на рис. 1. Требуется переслать 100 единиц потока из вершины 11 (источника) в вершину 9 (сток). Цифры возле дуг будут обозначать стоимость пересылки единицы потока по каждой дуге. Пропускные способности дуг приведены в табл. 4.

На первом шаге пытаемся отыскать цепь, по которой возможно переслать максимальное количество единиц потока, однако из возможных альтернативных вариантов выбираем цепь наименьшей стоимости. Этим условиям удовлетворяет цепь 11 - 1 - 6 - 7 - 8 - 9. По ней возможно переслать 50 единиц, при этом стоимость прохождения единицы потока по цепи составит 17 (альтернативная цепь - 11 - 1 - 6 - 7 - 10 - 9, однако стоимость прохождения по ней единицы потока равна 19; все остальные цепи в данном графе имеют меньшую пропускную способность). Дуги (1 - 6) и (8 - 9) переходят во множество N. Остается переслать 50 единиц потока.

	Таблица 4
Дуга ГТС (i - j)	Пропускная способность, ед.
1 - 2	50
1 - 6	50
1 - 11	100
2 - 3	30
2 - 5	30
3 - 4	30
3 - 8	75
4 - 8	90
4 - 9	60
5 - 6	65
5 - 7	70
5 - 8	40

	22
6 - 7		60
7 - 8		70
7 - 10		85
8 - 9		50
8 - 10		50
9 - 10		70

2-й шаг. По тому же принципу отыскиваем следующую цепь. Это цепь 11 - 1 - 2 - 5 - 8 - 10 - 9 (пропускная способность - 30 единиц, стоимость пересылки одной единицы - 22). Дуга (2 - 5) переходит во множество N. Остается переслать 20 единиц потока.

3-й шаг. Ищем вторую увеличивающую цепь. Ею оказывается цепь 11 - 1 - 2 - 3 - 4 - 9. По ней возможно переслать оставшиеся 20 единиц потока. Стоимость пересылки одной единицы по этой цепи - 23.

Общая стоимость пересылки потока по сети составляет Р=17• 50+30• 22+20• 23=1970 (стоимостных единиц).

Поток минимальной стоимости изображен на рис. 11. Величины потока (суммарные) в каждой дуге указаны курсивом. Цифры в скобках - резервы пропускных способностей дуг.

Следует заметить, что применение данного алгоритма невозможно, когда на потоки в дугах накладываются ограничения снизу, или когда стоимости, приписанные дугам, отрицательны.

23

СПИСОК РЕКОМЕНДУЕМОЙ ЛИТЕРАТУРЫ

1. Вагнер Г. Основы исследования операций. - М.: Мир, 1972. - Т.

1. - 336 с.

2.Кристофидес Н. Теория графов. Алгоритмический подход. - M.:

Мир, 1978. - 432 с.

3.Майника Э. Алгоритмы оптимизации на сетях и графах. - М.: Мир, 1981.

4.Оре О. Теория графов. - М.: Мир, 1975.

5.Таха Х. Введение в исследование операций. В 2-х кн. - М.: Мир,

1985. - Кн. 1. - 479 с.; Кн. 2. - 496 с.

6.Форд Л.Р. Потоки в сетях/ Л.Р. Форд, Д.Р. Фалкерсон - М.: Мир,

1966. - 276 с.

7.Ху Т. Целочисленное программирование и потоки в сетях. -М.:

Мир, 1974. - 419 с.

24

СОДЕРЖАНИЕ

Введение .......……………………………………………………....... 1 1. Практическое занятие № 1. Редукция графа

транспортной сети …………………………...…………..…....... 2

2.Практическое занятие № 2. Минимизация сети .………........... 6

3.Практическое занятие № 3. Задача о нахождении

наиболее надежного маршрута ………………………............. 10 4. Практическое занятие № 4. Задача о максимальном

потоке ..…….……………………………………………........... 13 5. Практическое занятие № 5. Задача о потоке

минимальной стоимости ...……………………………............ 18

Список рекомендуемой литературы ........…..………………......... 24

25

Составители Игорь Алексеевич Кузнецов

Андрей Валентинович Косолапов Алексей Юрьевич Тюрин

СЕТЕВЫЕ МОДЕЛИ

Методические указания к практическим занятиям по курсу “Теоретические основы организации и функционирования транспортных систем” для студентов направления 552100 “Эксплуатация транспортных средств”

Редактор Е. Л. Наркевич

ЛР № 020313 от 23.12.96

Подписано в печать 05.06.2000. Формат 60×84/16. Уч.-изд. л. 1,5. Бумага офсетная.

Отпечатано на ризографе. Тираж 100 экз. Заказ

Кузбасский государственный технический университет. 650026, Кемерово, ул. Весенняя, 28.

Типография Кузбасского государственного технического университета. 650099, Кемерово, ул. Д. Бедного, 4а.