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

10

Оформление работы. Выполненную работу оформить на листах бумаги формата А4. Выполнение каждого задания является новым пунктом отчета. Схему минимизированной сети вычертить на листе миллиметровой бумаги формата А3 и подшить к отчету.

Практическое занятие № 3 ЗАДАЧА О НАХОЖДЕНИИ НАИБОЛЕЕ НАДЕЖНОГО

МАРШРУТА

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

Задание

1.Рассчитать наиболее “надежный” маршрут между двумя заданными вершинами, используя предлагаемый алгоритм.

2.Рассчитать кратчайший маршрут между указанными вершинами.

3.Сравнить протяженности найденных маршрутов и вероятности беспрепятственного проезда по ним.

Исходные данные: “базовый” ГТС; вероятности беспрепятственного проезда по всем дугам графа.

Методические указания.

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

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

11

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

вероятность не быть остановленной полицией будет дополнительной вероятностью к pii , т.е. Pii = 1− pii . Соответственно, полная вероятность

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

Pst = P1• P2 • ... • Pk ,

где s - источник (исходный пункт), t - сток (пункт назначения), k - количество участков сети.

Тогда

lg Pst = lgP1+ lg P2 + ...+ lg Pk .

Алгебраически максимизация Pst эквивалентна максимизации lg Pst и, следовательно, максимизации суммы логарифмов вероятностей для отдельных участков маршрута. Поскольку lg Pj ≤ 0, максимизация суммы lg Pj эквивалентна минимизации суммы -lg Pj . Задача о

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

Пример. Воспользуемся приведенным алгоритмом для расчета наиболее надежного маршрута из вершины 1 в вершину 9 для ГТС, изображенного на рис. 1.

В табл. 3 приведены вероятности для участков сети и их логариф-

мы.				Таблица 3
	Участок сети (ij)	Pij	lg Pij	-lg Pij
	1 - 2	0,74	-0,130768	0,130768
	1 - 6	0,56	-0,251812	0,251812
	1 - 11	1,0	0,0	0,0
	2 - 3	0,68	-0,167491	0,167491
	2 - 5	0,69	-0,161151	0,161151
	3 - 4	0,55	-0,259637	0,259637

12

3 - 8	0,75	-0,124939	0,124939
4 - 8	0,81	-0,091515	0,091515
4 - 9	0,51	-0,292430	0,292430
5 - 6	0,9	-0,045757	0,045757
5 - 7	0,85	-0,070581	0,070581
5 - 8	0,8	-0,096910	0,096910
6 - 7	0,93	-0,031517	0,031517
7 - 8	0,6	-0,221847	0,221847
7 - 10	0,7	-0,154902	0,154902
8 - 9	0,61	-0,214670	0,214670
8 - 10	0,74	-0,130768	0,130768
9 - 10	0,88	-0,055517	0,055517

Расчет показывает, что наиболее выгодным с точки зрения возможности беспрепятственного проезда является путь 1 - 6 - 7 - 10 - 9. Полная вероятность беспрепятственного проезда по нему составляет 0,56• 0,93• 0,7• 0,88=0,3208. Длина этого пути составляет 12 км. Кратчайшим же является путь 1 - 2 - 5 - 8 - 9 (длина - 11 км), однако вероятность беспрепятственного проезда по нему равна

0,74• 0,69• 0,8• 0,61=0,2492.

Практическое занятие № 4 ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

Цель работы

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

Задание

1. Для заданной модели транспортной сети с указанными величинами пропускных способностей дуг отыскать цепь, поток по которой будет максимальным.

13

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

Исходные данные: ГТС с указанными величинами пропускных способностей дуг.

Методические указания

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

Через f (x, y) будем обозначать количество единиц потока, прошедших по дуге (x, y) . Для любого потока из s в t количество единиц,

выходящих из любой вершины x (x ≠ s, x ≠				t) , должно быть равно коли-
честву единиц, входящих в эту вершину, т.е.
∑	f ( x, y) −	∑	f( y, x) = 0	(x ≠ s, x ≠ t),	(1)
y	X	y	X

где Х - множество всех вершин рассматриваемого графа. Кроме того,

количество единиц потока, проходящего по каждой дуге		(x, y) , не
должно превышать пропускной способности этой дуги:
0 ≤ f (x, y) ≤ c( x, y)	( x, y) А ,	(2)

где А - множество всех дуг рассматриваемого графа.

Наконец, суммарное число единиц потока, выходящих из источника, должно быть равно суммарному числу единиц потока, входящих в сток. Если указанное число обозначить через v, то это условие можно

представить следующим образом:
∑	f ( x, y) −	∑	f( y, s)	= ν,	(3)
y	X	y	X
∑	f ( y,t) −	∑	f( t, y)	= ν.	(4)
y	X	y	X
Любой поток из s в t должен удовлетворять всем условиям (1) -
(4). И наоборот, если может быть найден набор величин					f (x, y) при

(x, y) А , для которого выполняются эти четыре условия, то такой на-

бор представляет собой поток из источника s в сток t.

Задача о максимальном потоке состоит в поиске потока, удовлетворяющего условиям (1) - (4), для которого величина v максимальна.

14

Задача о максимальном потоке является задачей линейного программирования и может быть решена симплексным методом. Однако существует более простой алгоритм решения этой задачи - так называемый алгоритм Форда - Фалкерсона.

Основная идея этого алгоритма состоит в следующем. Выбирается некоторый начальный поток из s в t и с помощью алгоритма поиска увеличивающей цепи выполняется поиск увеличивающей цепи. Если он оказывается успешным, то поток вдоль найденной цепи увеличивается до максимально возможного значения. Затем выполняется поиск новой увеличивающей цепи и т.д. Если на каком-то этапе этой процедуры увеличивающую цепь найти не удается, выполнение алгоритма заканчивается: найденный поток является максимальным.

Поиск увеличивающей цепи. Применительно к графам, вообще говоря, поток задает способ пересылки некоторых объектов из одной вершины в другую. Вершина, из которой начинается перемещение объектов, называется источником и обычно обозначается через s. Вершина, в которой заканчивается перемещение объектов, называется стоком и обычно обозначается через t. Объекты, которые перемещаются из источника в сток, называются единицами потока (или просто единицами).

Если количество единиц потока, которое может проходить по дуге (x, y) , ограничено, то говорят, что дуга (x, y) имеет ограниченную пропускную способность. Максимальную величину пропускной способности будем обозначать через c(x, y) . Кроме того, через a(x, y) будем обозначать стоимость перемещения единицы потока по дуге (x, y) .

Предположим, что имеется граф, в котором некоторое количество единиц потока проходит от источника к стоку и известен маршрут движения каждой единицы. Назовем количество единиц, проходящих по дуге (x, y) , потоком в данной дуге и обозначим эту величину через

f (x, y) . Очевидно, 0 ≤ f (x, y) ≤ c( x, y) . Дуги графа можно отнести к трем

различным категориям:

1) дуги, в которых поток не может не увеличиваться, не уменьшаться (множество таких дуг обозначим через N);

2) дуги, в которых поток может увеличиваться (множество таких дуг обозначим через I)

3) дуги, в которых поток может уменьшаться (множество таких дуг обозначим через R).

Множеству N, например, должны принадлежать дуги, имеющие нулевую пропускную способность или значительную стоимость прохо-

15

ждения потока. Дуги, в которых поток меньше пропускной способности, должны принадлежать множеству I. Наконец, дуги, в которых уже проходит некоторый поток, должны принадлежать множеству R. Дуги из множества I называются увеличивающими, дуги из множества R - уменьшающими. Очевидно, любая дуга графа принадлежит одному из трех множеств - N, I или R. Возможна также принадлежность дуг одновременно множествам I и R (это имеет место в случае, когда по дуге протекает некоторый поток, который можно увеличивать или уменьшать).

Обозначим через i(x, y) максимальную величину, на которую может быть увеличен поток в дуге. Очевидно, что i(x, y) = c( x, y) - f( x, y) .

Предположим, что мы хотим переслать дополнительное количество единиц потока из источника в сток. Задача будет решена (если она вообще имеет решение), если удастся найти путь Р, целиком состоящий из увеличивающих дуг. Максимальное увеличение потока в этом случае составит

min	{ i(x, y) }.	(5)
(x,y)	P

Каждая цепь из s в t, по которой могут быть посланы дополнительные единицы потока, называется увеличивающей цепью. Нахождение увеличивающей цепи осуществляется с помощью описываемого ниже алгоритма, основная идея которого заключается в построении растущего из вершины s дерева, составленного из окрашенных дуг, по которому могут посылаться дополнительные единицы потока.

Шаг 1. Определить состав множеств N, I и R. Дуги множества N из дальнейшего рассмотрения исключить (поскольку в них поток увеличиваться не может).

Шаг 2. Окрашивать дуги и вершины в соответствии с приведенными ниже правилами до тех пор, пока либо не будет окрашена вершина t, либо окраска новых вершин станет невозможной.

Правила окрашивания вершины у и дуги (x, y) при уже окрашенной вершине х:

а) если (x, y) I , то окрашивают вершину у и дугу (x, y) ; б) если (x, y) R , то окрашивают вершину у и дугу (y, x) ;

в) в противном случае окрашивание вершины у и дуги (x, y) не

производится.

В случае окрашивания вершины t действие алгоритма прекращается: в сети находится единственная увеличивающая цепь. В противном

16

случае, когда вершина t не окрашена, а окрасить новые вершины и дуги уже невозможно, в сети отсутствуют увеличивающие цепи из s в t.

Формальное описание алгоритма выглядит следующим образом. Шаг 1. Выбрать любой начальный поток из вершины s (источник)

в вершину t (сток), т.е. любой набор величин f (x, y) , удовлетворяющий соотношениям (1) - (4). Если ни один из начальных потоков из s в t неизвестен, задать начальный поток, положив для всех (x, y) f( x, y) = 0 .

Шаг 2. Сформировать множества дуг I и R согласно правилам, приведенным в алгоритме поиска увеличивающей цепи.

Шаг 3. На множествах I и R, сформированных на предыдущем шаге, применить к исходному графу алгоритм поиска увеличивающей цепи. Если при этом увеличивающую цепь найти не удастся, закончить процедуру алгоритма: найденный поток является максимальным. В противном случае осуществить максимально возможное увеличение потока вдоль найденной увеличивающей цепи. Затем вернуться к шагу

2.

Пример. Решим задачу о максимальном потоке для ГТС, изображенного на рис. 1. Источником является вершина 11, стоком - вершина 9. Будем считать, что цифры возле дуг - их пропускные способности c(x, y) . Общее количество единиц потока, которое необходимо переслать, v=7 (т.к. пересылка большего количества из вершины 11 невозможна).

На первом шаге попытаемся найти цепь, дающую возможность переслать максимальное количество единиц потока. Такой цепью будет цепь 11 - 1 - 2 - 3 - 4 - 9, по ней возможно переслать 3 единицы потока. После этого дуги (2 - 3) и (3 - 4) попадают во множество N (их пропускные способности исчерпаны). Остается переслать 4 единицы потока.

2-й шаг. Ищем по тому же принципу увеличивающую цепь. Это цепь 11 - 1 - 6 - 7 - 10 - 9, по ней можно переслать 2 единицы потока. Во множество N переходят дуги (1 - 6) и (6 - 7). Остается переслать 2 единицы потока.

3-й шаг. Ищем новую увеличивающую цепь. Единственный возможный вариант - цепь 11 - 1 - 2 - 5 - 8 - 9, по ней возможно переслать 1 единицу потока (т.к. 3 единицы уже пересылаются по первой цепи, а с(1,2)=4). После этого дуга (1 - 2) также переходит во множество N, и выполнение алгоритма заканчивается (из вершины 1 больше нельзя выслать ни одной единицы потока).

17

Вывод: максимальный поток в данной сети равен 6 единицам. Графически он показан на рис. 10. На сети оставлены только дуги, по которым проходит поток; первая цифра показывает суммарную величину потока в дуге; цифры в скобках - резервы пропускной способности дуг.

Рис. 10. Максимальный поток в сети

Оформление работы. Работу оформить на стандартных листах формата А4. На листах миллиметровки того же формата вычертить пошаговые схемы нахождения максимального потока в сети.

Практическое занятие № 5 ЗАДАЧА О ПОТОКЕ МИНИМАЛЬНОЙ СТОИМОСТИ

Цель работы

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

18

Задание: на заданной модели сети отыскать поток минимальной стоимости.

Исходные данные: ГТС с указанными пропускными способностями дуг и величинами стоимости пересылки единицы потока по каждой дуге.

Методические указания

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

Обозначим a(x, y) - стоимость прохождения единицы потока по дуге (x, y) . Сначала будем полагать, что каждая из величин a(x, y) является целочисленной. Через f (x, y) обозначим количество единиц потока, проходящих по дуге (x, y) f( x, y) ≥ 0 . Через v обозначим количество

единиц потока, которое нужно переслать из источника в сток.

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

найти

min	∑ a(x, y) f (x, y)
	x,y

при ограничениях

	∑ [ f (s, y) −	f ( y, s)]=	v,
	y
∑	[f (x,y)− f (y,x)]= 0		(x	≠ s,x ≠ t),
y
	∑ [ f (t, y) − f ( y,t)]= − v,
	y
0 ≤ f(x, y) ≤ c(x, y)		для всех		x, y.

(6)

(7)

(8)

(9)

(10)

Сумма, входящая в основное соотношение, представляет собой общую стоимость потока. Уравнение (2) показывает, что чистый суммарный поток из источника s должен быть равен v. Уравнение (3) показывает, что чистый поток из любой вершины х, не совпадающей ни с источником s, ни со стоком t, должен быть равен 0. Уравнение (4) показывает, что чистый поток из стока t должен быть равен –v. Наконец, условие (5) описывает требование, согласно которому поток в каждой дуге должен иметь величину, находящуюся в интервале от 0 до значения пропускной способности дуги.

19

Задача о потоке минимальной стоимости является задачей линейного программирования.

Основное соотношение можно заменить следующим:

max p−

		(11)
∑ a(x, y) f (x, y) .
x,y

Здесь р - достаточно большое число (большее максимальной стоимости прохождения единицы потока из источника в сток). Очевидно, что любой поток, дающий максимум соотношения (6), одновременно будет обеспечивать минимум основного соотношения.

Алгоритм поиска потока минимальной стоимости выполняет следующие действия. Вначале из s в t пересылается как можно больше единиц потока, полная стоимость прохождения по сети каждой из которых равна 0. Затем из s в t пересылается как можно больше единиц потока, полная стоимость прохождения по сети каждой из которых равна 1. Далее процедура продолжается аналогичным образом, при этом полная стоимость прохождения по сети единицы потока каждый раз увеличивается на единицу. Работа алгоритма заканчивается либо тогда, когда через сеть удается пропустить заданное число v единиц потока, либо когда ни одной дополнительной единицы потока по сети пропустить нельзя (в зависимости от того, какое из этих событий произойдет раньше). Иначе говоря, данный алгоритм многократно решает задачу, выраженную соотношениями (2) - (6), сначала для р=0, затем р=1, р=2 и т.д.

Если же в результате работы алгоритма через сеть было пропущено максимально возможное количество единиц потока, имеющих общую стоимость прохождения через сеть (р-1) или меньшую, возникает необходимость отыскать возможность пересылки дополнительных единиц потока. В соответствии с алгоритмом поиска потока минимальной стоимости это реализуется путем выявления увеличивающей цепи, стоимость прохождения по которой единицы потока составляет величину р. Рассматриваемый алгоритм должен найти такую увеличивающую цепь, в которой сумма стоимостей для прямых дуг за вычетом стоимостей обратных дуг равна р. Этот поиск осуществляется путем приписывания каждой вершине х целого числа p(x). Эти числа выби-

раются так, что р(s)=0, р(t)=р и 0≤ р(х)≤ р для всех вершин х, отличных от s и t. При этом изменения потока допускаются только в тех дугах, для которых