В сети присутствуют
потоков различных продуктов; есть
источников и
стоков. При этом должно выполняется соотношение
, где
,
- соответственно нижняя и верхняя
пропускные способности сети для дуги, инцедентной вершинам
и
,
- величина
-го потока по этой дуге. Требуется
максимизировать величины всех потоков, то есть рассматривается многокритериальная задача сетевой оптимизации.
Принцип построения алгоритма:
Рассматривается 1-й поток и для него полностью решается оптимизационная задача;
Верхняя пропускная способность каждой дуги уменьшается на величину найденного потока;
Решается задача для 2-го потока;
Если решение для 2-го потока найти не удается, то изменяется маршрут для 1-го потока;
И так далее для остальных потоков.