Хозяйственно-питьевой водопровод соединяет источник I со стоком S. Имеется несколько путей, по которым можно доставлять воду из источника в сток. Вершины сети соответствуют пересечениям труб, а ребра и дуги – участкам труб между пересечениями. На сети указаны пропускные способности труб, т.е. максимальное количество воды в м3, которое можно пропустить по трубам за 1 ч. Также сформирован начальный поток с мощностью Z0 (м3/ч). Какой поток воды максимальной мощности можно пропустить по данному трубопроводу?
Требуется:
посчитать мощность начального потока воды;
построить на сети поток воды максимальной мощности, направленный из источника I к стоку S;
указать «узкое место» сети и найти его пропускную способность;
провести анализ результатов решения.

Часть выполненной работы

Присваиваем вершине 2 метку (1+), так как u12 прямая дуга и x12 < d12 (4<9). Присваиваем вершине 4 метку (1+), так как u14 прямая дуга и x14 < d14 (3<6). Вершине 3 нельзя присвоить метку, т.к. x13= d13=2.
Просматриваем соседние непомеченные вершины радом с вершиной 2. Это вершина 5. Присваиваем 5 метку (2+), так как u25 прямая дуга и x25 < d25 (2<6).
Просматриваем соседние непомеченные вершины рядом с вершиной 4. Это вершина 6. Присваиваем вершине 6 метку (3+), так как x46 < d46 (1<9).
Рассмотрим вершину 5. Непомеченная вершина рядом с 5 – это вершина 6 (сток). Ставим метку (4+) вершине 6, так как u56 прямая дуга и x56 < d56 (8<9).
Получается путь от I до S:
Р2: 1-2-5-6
Выписываем множество прямых и обратных дуг.
Р+={u12; u25; u56} прямые дуги. Обратные дуги в увеличивающий путь не входят.
ɛ1=min(dij – xij)=min{(d12 – x12); (d25 – x25); (d56 – x56)}=min{9-4; 6-2; 9-8}=1.
Так как обратных дуг нет, то ɛ2 не рассматриваем.
Вдоль дуг увеличивающего пути изменяем поток на ɛ1 = 1 и получаем новый поток z2=z1+ɛ=8+1=9 (м3/ч):
х12=4+1=5
х25=2+1=3
х56=8+1=9
Остальные остаются без изменений, т…
   
4.21
Anka3107
Педагог. Занимаюсь научной деятельностью. Имею опыт в написании курсовых, дипломных, контрольных, тестовых работ, рефератов, статей, докладов, сочинений, эссе, ответов на билеты к экзаменам. Пишу стихи.