Файл: И.А. Кузнецов Сетевые модели. Методические указания к практическим занятиям.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 10.06.2024
Просмотров: 41
Скачиваний: 0
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. При этом изменения потока допускаются только в тех дугах, для которых
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 |