Итераций

3. Ищем квазипуть (квазипутем будем называть такую последовательность ребер и дуг, что если убрать ориентацию с дуг, то получится цепь. Т.е. при движении вдоль квазипути некоторые дуги могут быть пройдены в направлении, противоположном их ориентации), поток вдоль которого можно увеличить. Этот квазипуть можно взять со схемы построения множества . На этой схеме найдем последовательность s до t. Квазипуть, проходящий через вершины этой последовательности и будет искомым:

(s,1),(1,2),(2,3),(3,5),(5,7),(7,t).

Для этого пути a =1.

4. Увеличиваем потоки по коммуникациям этого квазипути на a и выполняем пункт 2 и т.д.

Решение рассматриваемого примера представлено на рисунках 10-13.

Рис.12. План перевозок после пятой итерации

При построении множества убеждаемся в том, что вершина t , значит план не оптимальный.

Вдоль квазипути (s,1),(1,4),(4,3),(3,5), (5,7), (7,t) поток можно увеличить на a =1 (рис.3.5.5)

Вдоль квазипути (s,2),(2,4),(4,7),(7,t) a =2, вдоль квазипути (s,3),((3,5),(5,7),(7,t) a =1 (см. рис.11).

Вдоль квазипути (s,1),(1,4),(4,2),(2,3)(3,5), (5,7),(7,t) a =2. Новый поток показан на рисунке 12. Заметим, что ребро (4,2) мы проходим в обратном направлении, поэтому поток x₂₄ мы уменьшаем на 2.

Вдоль квазипути (s,1),(1,4),(4,2),(2,3),(3,5), (5,7),(7,t) a =5, см. рис.13.

Напомним, что черта в углу прямоугольника, изображающего вершину, означает, что эта вершина попала в множество . Мы видим, что после последней итерации ={s,1,2,4} и ={3,5,6,7,t}. Пропускная способность разреза равна 2+2+1+1+8=14. Поток такой величины мы и получили на рисунке 13.

Рис.13. Оптимальный план перевозок