Курсовая работа: Решение транспортной задачи

Для каждой обратной дуги:

Величина, на которую можно увеличить поток. Находим минимальное значение на всех этих дугах.

Шаг 4

Наращивание потока в сети. Корректируем поток на дугах в соответствии последнего пути в инкрементальном графе.

На этих дугах, поток изменяется по правилам:

Для прямых дуг:

Для обратных дуг:

Алгоритм завершается, если заданная величина потока достигнута.

Переход к шагу 1.

5. Решение индивидуального задания по шагам

Рис. 2. Нулевой поток.

Рис.3. Инкрементальный граф

Рис. 4. Увеличения потока в сети

Рис.5. Инкрементальный граф

Рис. 6. Увеличение потока в сети