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

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

Задача 6.1.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(2)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(3)	R(4)	R(3)
R(3)	R(4)	R(3)	R(2)
J(1)	J(2)	J(3)	J(4)

Задача 6.2.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(2)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(4)	R(4)	R(3)
R(3)	R(3)	R(3)	R(2)
J(1)	J(2)	J(3)	J(4)

Задача 6.3.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(2)	R(1)	R(1)
R(3)	R(1)	R(2)	R(4)
R(1)	R(3)	R(4)	R(2)
R(4)	R(4)	R(3)	R(3)
J(1)	J(2)	J(3)	J(4)

Задача 6.4.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(2)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(3)	R(4)	R(3)
R(3)	R(4)	R(3)	R(2)
J(1)	J(2)	J(3)	J(4)

Задача 6.5.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(4)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(3)	R(4)	R(3)
R(3)	R(2)	R(3)	R(2)
J(1)	J(2)	J(3)	J(4)

.

Задача 6.6.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(2)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(3)	R(4)	R(3)
R(3)	R(4)	R(3)	R(2)
J(1)	J(2)	J(3)	J(4)

Задача 6.7.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(2)	R(1)	R(2)
R(4)	R(1)	R(2)	R(4)
R(3)	R(3)	R(4)	R(3)
R(1)	R(4)	R(3)	R(1)
J(1)	J(2)	J(3)	J(4)

Задача 6.8.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(2)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(4)	R(4)	R(2)
R(3)	R(3)	R(3)	R(3)
J(1)	J(2)	J(3)	J(4)

Задача 6.9.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(2)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(3)	R(4)	R(3)
R(3)	R(4)	R(3)	R(2)
J(1)	J(2)	J(3)	J(4)

Задача 6.10.

Матрица производительностей.

J(i)/R(i)	R(1)	R(2)	R(3)	R(4)
J(1)
J(2)
J(3)
J(4)

Матрица предпочтений.

R(2)	R(4)	R(1)	R(1)
R(4)	R(1)	R(2)	R(4)
R(1)	R(3)	R(4)	R(3)
R(3)	R(2)	R(3)	R(2)
J(1)	J(2)	J(3)	J(4)

Рассмотрим задачу поиска максимального потока в транспортной сети с 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.

Из вершины 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.

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

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

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

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

Дата добавления: 2017-02-01