Нахождение максимального потока в транспортной сети алгоритмом Форда-Фалкерсона.

⇐ ПредыдущаяСтр 8 из 8

Рассмотрим задачу поиска максимального потока в транспортной сети с 10 вершинами (вершина 1 - исток, вершина 10 -сток), матрица пропускных способностей дуг Q имеет вид:

i\j

Строим последовательность вершин из истока:

1, 2, 4, 3, 2, 5, 7, 4, 6, 3, 5, 10.

Схема построения последовательности:

из истока 1 по ненасыщенным дугам есть пути в вершины 2, 4, 3.

Первая не рассмотренная вершина 2 связана с вершинами 6 и 7 (по ненасыщенным дугам). Следующая не рассмотренная вершина 4 связана с вершиной 6. Следующая не рассмотренная вершина 3 не порождает ни одной новой вершины.

Вершина 5 не соединена ни с одной новой вершины. Из вершины 5 существует ненасыщенная дуга, ведущая в сток (вершина 10).

Получили существование маршрута по ненасыщенным ребрам из истока в сток:

1 - 2 -5 - 10, максимальная величина груза, который можно перевезти по этому маршруту равно 2.

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

Из вершины 1 в вершину 2 пропускная способность станет равна 4-2=2, в обратном направлении из вершины 2 в вершину 1 пропускная способность увеличится 0+2=2.

Из вершины 2 в вершину 5 пропускная способность станет равна 2-2=0, в обратном направлении из вершины 5 в вершину 2 пропускная способность увеличится 0+2=2.

Из вершины 5 в вершину 10 пропускная способность станет равна 3-2=1, в обратном направлении из вершины 10 в вершину 5 пропускная способность увеличится 0+2=2.

Строим новую последовательность вершин из истока:

1, 2, 4, 3, 2, 7, 4, 6, 3, 7, 10.

Получили существование маршрута по ненасыщенным ребрам из истока в сток:

1 - 2 -7 - 10, максимальная величина груза, который можно перевезти по этому маршруту равно 2.

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

Из вершины 1 в вершину 2 пропускная способность станет равна 2-2=0, в обратном направлении из вершины 2 в вершину 1 пропускная способность увеличится 2+2=4.

Из вершины 2 в вершину 7 пропускная способность станет равна 2-2=0, в обратном направлении из вершины 7 в вершину 2 пропускная способность увеличится 0+2=2.

Из вершины 7 в вершину 10 пропускная способность станет равна 4-2=2, в обратном направлении из вершины 10 в вершину пропускная способность увеличится 0+2=2.

Строим новую последовательность вершин из истока:

1, 4, 3, 4, 6, 7, 3, 6, 9, 7, 10.

Получили существование маршрута по ненасыщенным ребрам из истока в сток:

1 - 4 -7 - 10, максимальная величина груза, который можно перевезти по этому маршруту равно 2.

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

Из вершины 1 в вершину 4 пропускная способность станет равна 3-2=1, в обратном направлении из вершины 4 в вершину 1 пропускная способность увеличится 0+2=2.

Из вершины 4 в вершину 7 пропускная способность станет равна 3-2=1, в обратном направлении из вершины 7 в вершину пропускная способность увеличится 0+2=2.

Из вершины 7 в вершину 10 пропускная способность станет равна 2-2=0 в обратном направлении из вершины 10 в вершину пропускная способность увеличится 2+2=4.

Строим новую последовательность вершин из истока:

1, 4, 3, 4, 7, 6, 3, 7, 6, 9, 9, 10.

Получили существование маршрута по ненасыщенным ребрам из истока в сток:

1 - 4 - 6 - 9 - 10, максимальная величина груза, который можно перевезти по этому маршруту равна 1.

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

Из вершины 1 в вершину 4 пропускная способность станет равна 1-1=0, в обратном направлении из вершины 4 в вершину 1 пропускная способность увеличится 2+1=3.

Из вершины 4 в вершину 6 пропускная способность станет равна 3-1=2, в обратном направлении из вершины 6 в вершину 4 пропускная способность увеличится 0+1=1.

Из вершины 6 в вершину 9 пропускная способность станет равна 2-1=1 в обратном направлении из вершины 9 в вершину 6 пропускная способность увеличится 0+1=1.

Из вершины 9 в вершину 10 пропускная способность станет равна 2-1=1 в обратном направлении из вершины 10 в вершину 9 пропускная способность увеличится 0+1=1.

Строим новую последовательность вершин из истока:

1, 3, 3, 6, 6, 4, 7, 9, 4, 7, 2, 9, 10.

Получили существование маршрута по ненасыщенным ребрам из истока в сток:

1 - 3 - 6 - 9 - 10, максимальная величина груза, который можно перевезти по этому маршруту равна 1.

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

Из вершины 1 в вершину 3 пропускная способность станет равна 1-1=0, в обратном направлении из вершины 3 в вершину 1 пропускная способность увеличится 0+1=1.

Из вершины 3 в вершину 6 пропускная способность станет равна 2-1=1, в обратном направлении из вершины 6 в вершину 3 пропускная способность увеличится 0+1=1.

Строим новую последовательность вершин:

Из вершины 1 нет маршрута по ненасыщенным ребрам в сток, т.е. по теореме Форда-Фалкерсона найденный поток максимален.

Решение задачи определяется матрицей X:



-4
-1
-3
	-2
		-1	-1
	-2		-2

					-2
				-2		-4	-2

Величина максимального потока равна

F(X’)=8.

Найти максимальный поток в транспортной сети.

Задача 8.1.

i\j

Задача 8.2.

i\j

Задача 8.3.

i\j

Задача 8.4.

i\j

Задача 8.5.

i\j

Задача 8.6.

i\j

Задача 8.7.

i\j

Задача 8.8.

i\j

Задача 8.9.

i\j

Задача 8.10.

i\j

Расчет временных характеристик сетевых моделей.

Пусть i - номер работы, t(i) - длительность выполнения работы i, i=1, 2, 3, 4, 5, 6, 7. Обозначим через K(i) - множество работ, непосредственно предшествующих работе с номером i (условие, определяемое технологическими трбованиями на порядок выполнения работ). Требуется определить минимально возможное время, за которое можно выполнить все работы.

i	t(i)	K(i)
		O
		O
		{1, 2}
		{3}
		{3}
		{4}
		{5, 6}

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

К таким характеристикам относятся:

t(rn, i) - время самого раннего начала выполнения работы с номером i,

t(rk, i) - время самого раннего окончания выполнения работы с номером i,

t(pn, i) - время самого позднего начала выполнения работы с номером i,

t(pk, i) - время самого позднего окончания выполнения работы с номером i,

r(i) - резерв времени работы с номером i, т.е.. время, на которое не в ущерб времени общего окончания выполнения всех работ, можно задерживать выполнение работы с номером (i),

T(k) - время выполнения всех работ изделия.

Величина T(k) называется длиной критического пути, а критическим путём называют путь, соединяющий некоторую начальную работу - не имеющую предшествующих работ, и некоторую конечную работу - не имеющую последующих, т.е. от неё зависящих работ, суммарное время выполнения всех работ которого максимально.

Для расчета временных характеристик воспользуемся следующими рекуррентными соотношениями:

t(rn, i) = 0, если K(i) - пустое множество.

t(rk, i) = t(rn, i) + t(i),

t(rn, i)= max t(rk, j), где максимум берется по всем работам j из множества K(i).

t(pk, i) = t(rk, i), если работа i не имеет последующих,

t(pn, i) = t(pk, i) - t(i),

t(pk, i) = min t(pn, j), где минимум берется по тем работам j, которые принадлежат множеству K(i), т.е. по тем работам, от которых зависит работа с номером i.

r(i) = t(pn, i) - t(rn, i) = t(pk, i) - t(rk, i).

Работы критического пути это те работы, резервы времени которых нулевые.

Найденные временные характеристики приведем в таблице:

i	t(i)	K(i)	t(rn, i)	t(rk, i)	t(pn, i)	t(pk, i)	r(i)
		O
		O					0’
		{1, 2}					0’
		{3}					0’
		{3}
		{4}					0’
		{5, 6}					0’

Работы критического пути (2, 3, 4, 6, 7).

Длина критического пути T(k)=19.

Работа1, t(1)=3		Работа5, t(5)=3
	Работа3’ t(3)=2			Работа7’, t(7)=2
Работа2’, t(2)=5		Работа4’, t(4)=4	Работа6’, t(6)=6

⇐ Предыдущая 1 2 3 4 5 6 78