Алгоритм нахождения максимального потока в сети
Алгоритм определения возможности насыщения сети распределения товаром направлен на определение объемов поставок товара в звенья распределительной системы при учете возможностей дальнейшего продвижения товара по звеньям сети и пропускной способности этих звеньев. Расчет проводится на основе следующего алгоритма.
- 1. Установить значения отметок всех вершин орграфа, за исключением а, равными «—».
- 2. Установить резерв вершины а равным <*>.
- 3. Включить а в S: S = {а}.
- 4. Если S — пустое множество, идти к 28, иначе — к шагу 5.
- 5. Если S не является пустым множеством, выбрать элемент множества S, имеющий максимальный приоритет в матрице предпочтений.
- 6. Обозначить выбранный элемент v.
- 7. Удалить выбранный элемент из множества S.
- 8. Если у v есть неотмеченные последующие вершины, идти к шагу 9, иначе — к шагу 17.
- 9. Выбрать последующую v неотмеченную вершину, имеющую максимальный приоритет в матрице предпочтений.
- 10. Обозначить выбранную вершину w.
- 11. Если/((v,w)) < c((v,w)), идти к шагу 12, иначе — к шагу 16.
- 12. Рассчитать резерв вершины w: Rw = min {c((v,w)) — .A(v,w));
Rv}.
- 13. Обозначить предшествующую w вершину.
- 14. Если w Ф z, идти к шагу 15, иначе — к шагу 25.
- 15. Добавить w в S.
- 16. Все последующие v неотмеченные вершины рассмотрены? Если да, идти к 17, иначе — к шагу 9.
- 17. Если у вершины v есть неотмеченные предшествующие вершины, идти к 18, иначе — к шагу 4.
- 18. Выбрать предшествующую v неотмеченную и ранее не просмотренную вершину, имеющую максимальный приоритет в матрице предпочтений.
- 19. Обозначить выбранную вершину w.
- 20. Если/((v,w)) > 0 идти к шагу 21, иначе — к шагу 24.
- 21. Рассчитать резерв вершины w: Rw = min {/((v,w)); Rv}.
- 22. Обозначить предшествующую w вершину.
- 23. Добавить w в S.
- 24. Все предшествующие v неотмеченные вершины рассмотрены? Если да, идти к 4, иначе — к шагу 18.
- 25. Используя отметки предшествующих вершин, построить цепь от z к а.
- 26. Для построенной цепи от z к а увеличить величину потока каждого ребра, ориентированного по направлению от а к z, на резерв вершины z и уменьшить величину потока каждого ребра, ориентированного по направлению от z к а, на резерв вершины z-
- 27. Идти к шагу 1.
- 28. Конец.
Блок-схема алгоритма представлена на рис. 13.5.
Рис. 13.5. Блок-схема алгоритма метода максимального потока
Рис. 13.5 (окончание)
