Потоки в сетях. Примеры практических задач, определение потока, разрезы.
Рассмотрим некоторые примеры практических задач.
Пример:
1) Пусть имеется сеть трубопроводов, соединяющих пункт А (скажем, нефтепромысел) с пунктом В (скажем, нефтеперерабатывающим заводом). Трубопроводы могут соединяться и разветвляться в промежуточных пунктах. Количество нефти, которое может быть перекачено по каждому отрезку трубопровода в единицу времени, также не безгранично и определяется такими факторами, как диаметр трубы, мощность нагнетающего насоса и т. д. (обычно это называют «пропускной способностью» или «максимальным расходом» трубопровода). Сколько нефти можно прокачать через такую сеть в единицу времени?
2) Пусть имеется система машин для производства готовых изделий из сырья, и последовательность технологических операций может быть различной (то есть операции могут выполняться на разном оборудовании или в разной последовательности), но все допустимые варианты заранее строго определены. Максимальная производительность каждой единицы оборудования, естественно, также заранее известна и постоянна. Какова максимально возможная производительность всей системы в целом и как нужно организовать производство для достижения максимальной производительности?
Определения:
Пусть G(V, Е) – сеть, сетью называется граф, имеющий вершины. S и t – соответственно источник и сток сети. Дуги сети нагружены неотрицательными вещественными числами Е Þ R+ . Если u и v – вершины, то число с(u, v) – называется пропускной способностью дуги (u, v).
При решении будем полагать, что C(2,1)= C(1,2).
Максимальное количество Xij вещества, которое может пропустить в единицу времени ребро между вершиной (i,j) называют его пропускной способностью.
В общем случае Xij ≠Xji. Пропускные способности рёбер сети можно задать квадратной матрицей n-го порядка, где n – число вершин сети. В теории потоков предполагается, что Xii=0. И поэтому главная диагональ матрицы состоит из нулей.
||Cij|| =
| 1 2 3 4 5 6 1 0 6 1 0 0 0 2 6 0 2 0 3 0 3 1 2 0 3 0 0 4 0 0 3 0 1 2 5 0 3 0 1 0 5 6 0 0 0 2 5 0 |
Сформируем начальный поток j0, состоящий из суммы потоков по
следующим путям, и найдем пропускные способности путей:
m1 = (1, 3, 4, 6), j( m1 ) = 1;
m2 = (1, 2, 3, 4, 6), j( m2 ) = 2;
m3 = (1, 2, 5, 6), j( m3 ) = 3.
Т.e. пропускная способность потока j0 равна:
j0 = j( m1 )+ j( m2 )+ j( m3 ) = 6
Величина потока каждого ребра выглядят так :
j(e13) = 1;
j(e12) = 4;
j(e23) = 1;
j(e34) = 2;
j(e46) = 2;
j(e25) = 3;
j(e56) = 3.
Составим теперь матрицу построенного потока ( M2 ) c эле- ментами j(eij):
1 2 3 4 5 6
1 0 4 1 0 0 0
2 -4 0 1 0 3 0
3 -1 -1 0 2 0 0
4 0 0 -2 0 0 2
5 0 -3 0 0 0 3
6 0 0 0 -2 -3 0
Далее строим матрицу М3 = М1 - М2 = { C(eij) - j(eij) }:
1 2 3 4 5 6
1 0 2 0 0 0 0
2 10 0 1 0 0 0
3 2 3 0 1 0 0
4 0 0 5 0 1 0
5 0 6 0 1 0 2
6 0 0 0 4 8 0
В соответствии с данным алгоритмом составляем максимальный поток:
1)Построим начальный поток.
2)Составляем по ненасыщенному пути А={1,2,3,4,5,6},где 1ºI и
6ºS,в сответствии с п.2 алгоритма построения по теореме Форда-Фалкерсона,сток попал в количество ребер по ненасыщенному пути.
3)Выделим путь из истока в сток состоящий из ненасыщенных ребер m4=(1,2,3,4,5,6).
Потом высчитываем Сij-Xij:C12-X12=6-4=2, C23-X23=2-1=1,
C34-X34=3-2=1,∆45=1,∆56=2.
Min(Cij-Xij)=1,увеличиваем на единицу построенный поток и возвращаемся к п.2 j(m4)=1.
П.2 строим множество по ненасыщенным ребрам А={1,2}
Построим разрез min пропускной способности. Этот разрез будет иметь вид (A\B)=1+2+3=6.
Построим разрез транспортной сети. Он будет пересекать дуги, начало которых принадлежит множеству А,а конец мно-жеству В.
Считаем пропускную способность разреза:
R(A\B)=1+2+3=6.
Таким образом, согласно теореме Форда- Фалкерсона построен
Максимальный поток, равный минимальной пропускной способности pазреза сети.
Дата добавления: 2021-07-22; просмотров: 352;