КОМПЛЕКСНОЕ ЗАДАНИЕ по УЯП-ІМЗ
Задача о распределении потоков в многополюсной транспортной сети
Часть 1. Метод Форда-Фалкерсона
1. Вычисление теоретического предела полного потока в симметричной сети
а) теоретические пределы потоков в отдельных полюсах сети:
полюс 1: F1=6+7+1=14
полюс 2: F2=1+11+2=14
полюс 3: F3=3+13+4=20
полюс 4: F4=5+9+4=18
Теоретический предел полного потока в симметричной сети:
F?lim=0.5·(14+14+20+18)=33
2. Вычисление полного потока в симметричной сети эмпирическим методом
Остаточная сеть после удаления полностью использованных ребер и несвязных узлов
Матрица потоков в симметричной сети
Эмпирический полный поток в симметричной сети:
F?=14+13+5=32
Вывод:
? значение полного потока сети должно быть, по крайней мере, не меньше чем найденное эмпирическое значение 32;
? найденное эмпирическое значение полного потока сети (32) близко к теоретическому пределу полного потока (33), т. е. может быть принято в качестве приближенного фактического значения с ошибкой 1.
3. Решение задачи о максимальном потоке между полюсами сети методом Форда-Фалкерсона для симметричной сети:
а) запустить приложение MaxFlow-2000;
б) сформировать структуру сети в соответствии с вариантом задания;
в) используя приложение MaxFlow-2000 рассчитать матрицу максимально возможных потоков для каждой пары полюсов;
г) построить минимальные сечения для каждой из 6 пар узлов;
д) распределим потоки для пары узлов с максимально возможным потоком (пара исток «3» ? сток «4» , максимальный поток = 15) и определим максимальный поток сети в первом приближении.
Как видим, суммарный поток в первом приближении равен 15+3+5=23, т. е значительно меньше теоретического предела 33. Поэтому следует продолжить поиск вариантов решения задачи о наилучшем распределении потоков по критерию максимального полного потока сети.
4. Провести расчеты по п.3-д для оставшихся пяти пар полюсов, каждый раз выбирая очередную пару с максимальным потоком. Поскольку в нашем случае, все оставшиеся пары имеют максимальный поток 14, то рассмотрим пары полюсов в очередности:
1>2; 1>3; 1>4; 2>3; 2>4.
Все промежуточные результаты при вести в отчете (по аналогии с п.3-д).
Результаты этих расчетов сведем в таблицу
Из данной таблицы определить максимально возможный полный поток сети и построить соответствующее распределение потоков (для симметричной сети).
5. Для заданной матрицы генерации внешних потоков и заданной сети найти максимальный полный поток сети. Для этого:
а) используя приложение MaxFlow-2000 построить матрицу максимальных потоков B для каждой пары полюсов и сравнить ее с матрицей генераторов внешних потоков A. В результате сравнения построить матрицу C; каждый элемент результирующей матрицы C принимается равным меньшему из двух однотипных элементов в матрицах A и B.
Например, A(1,2) =25, B(1,2) =14. Отсюда C(1,2)=14.
б) Для матрицы возможных потоков C найти максимальный поток в симметричной транспортной сети. Построить соответствующее распределение потоков по ветвям сети. Результаты привести в отчете.
После выполнения комплексного практического защитить результат у преподавателя и получить зачет по первой части практического задания.
Варианты комплексного практического задания –часть1 (1 вариант ? для 2-х студентов)
Часть 2. Метод уравнений Кирхгофа
Рассмотрим симметричную кольцевую транспортную сеть, в которой заданы симметричные в обоих направлениях проводимости ветвей 
, 
, 
(т. е. дуплексные каналы связи). Пусть также задана симметричная матрица генерации внешних (транзитных) потоков F. Поскольку все элементы матрицы симметричны относительно главной диагонали, то все процессы в прямом направлении одинаковы с процессами в обратном направлении. Для простоты в матрице показаны элементы одной половины (выше диагонали).
Примем следующее условие относительно способа распределения потоков.
Для каждого потока из полюса истока (S) в полюс стока (D) будем выбирать по два альтернативных пути в противоположных направлениях кольцевой сети. Например, поток F12 из узла S=1 (исток) в узел D=2 (сток) представим как сумму двух потоков:
F12 = 
+
,
где 
? часть потока F12 , которая идет по часовой стрелке напрямую от узла 1 к узлу 2; 
? часть потока F12 , которая идет против часовой стрелки от узла 1 к узлу 2 транзитом через узел 3. Нетрудно видеть, что в каждой из трех ветвей 
, 
, 
должны протекать по три составляющих потоков, а именно:
а) через ветвь 
? потоки по часовой стрелке 
(зеленый) и 
(красный), а также против часовой стрелки поток 
(синий);
б) через ветвь 
? потоки по часовой стрелке 
(синий) и 
(красный), а также против часовой стрелки поток 
(синий); 
, 
(по часовой стрелке) и поток 
(против часовой стрелки);
в) через ветвь 
? потоки против часовой стрелки 
(красный), 
(синий), 
(зеленый).
.
Произведем виртуализацию сети. Для этого разделим каждый из трех каналов 
, 
, 
на три виртуальных канала соответственно для трех различных потоков в каждой ветви сети:
(1)
Составим уравнения баланса потоков:
(2)
Установим соответствие каналов и потоков:
канал 
: 
>
>
>
канал 
: 
>
>
>
канал 
: 
>
>
>
В уравнениях (1) и (2) общее число неизвестных составляет 15 (9 проводимостей виртуальных каналов и 6 виртуальных потоков). Правые части тих уравнений считаются известными заданными величинами. Из этих шести уравнений несложно методом подстановки исключить 6 неизвестных, после чего число неизвестных станет равным 9. Дл их нахождения необходимо составить по правилам Кирхгофа 9 уравнений для баланса потоков в узлах и напряжений в контурах. В качестве информационного напряжения выберем безразмерную величину, равную отношению виртуального потока к проводимости его виртуального канала.
Например, информационное напряжение в канале 
равно 
.
Согласно второму закону Кирхгофа, в параллельных ветвях каждого канала напряжение должно быть одинаковым. Отсюда запишем три двойных уравнения (каждое из которых фактически представляет собой два уравнения):
канал 
: 
=
=
канал 
: 
=
=
(3)
канал 
: 
=
=
Система (3) содержит 6 уравнений. Еще три уравнения получим для описания баланса напряжений согласно второму закону Кирхофа для каждой пары параллельных потоков, которые порождаются генераторами потоков
=
+
; 
=
+
; 
=
+
.
(4)
Далее выполнить подстановку шести переменных из первых шести уравнений в систему из 9 уравнений. В результате получим систему из 9 нелинейных уравнений с 9 неизвестными, из которых три переменных являются виртуальными потоками и шесть переменных ? виртуальными проводимостями (выполнить самостоятельно).
Решение полученной системы нелинейных уравнений является нетривиальной задачей и требует применения специальных численных методов.
Варианты комплексного практического задания –часть2 (1 вариант ? для 2-х студентов)
Задание:
1. Построить систему из 9 уравнений для описания распределения виртуальных каналов и виртуальных потоков, исходя из заданного варианта (1 вариант для 2-х студентов).
2. Защитить результат у преподавателя и получить зачет по второй части практического задания.
