На странице представлен фрагмент
Реши любую задачу с помощью нейросети.
Хозяйственно-питьевой водопровод соединяет источник I со стоком S. Имеется несколько путей, по которым можно доставлять воду из источника в сток. Вершины сети соответствуют пересечениям труб, а ребра и дуги – участкам труб между пересечениями. На сети указаны пропускные способности труб, т.е. максимальное количество воды в м3, которое можно пропустить по трубам за 1 ч. Также сформирован начальный поток с мощностью Z0 (м3/ч). Какой поток воды максимальной мощности можно пропустить по данному трубопроводу?
Требуется:
посчитать мощность начального потока воды;
построить на сети поток воды максимальной мощности, направленный из источника I к стоку S;
указать «узкое место» сети и найти его пропускную способность;
провести анализ результатов решения.
Часть выполненной работы
Просматриваем соседние непомеченные вершины радом с вершиной 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
Остальные остаются без изменений, т…
Купить уже готовую работу
Так же вы можете купить уже выполненные похожие работы. Для удобства покупки работы размещены на независимой бирже. Подробнее об условиях покупки тут.
