Задача сводится к задаче линейного программирования.
Пользуюсь обозначениями из недавно вышедшей статьи
http://rts-md.com/index.php/jornalRTS/article/view/25/18.
Там же есть ссылки, на работы, которые могут быть полезными.
Пусть
- соответственно множество всех маршрутов, множество маршрутов из
в
, множество маршрутов, проходящих по дуге
;
– интенсивность потока на маршруте
- поток (функция распределения потоков, система потоков, или вектор-поток, или вектор интенсивностей потоков – как угодно) в сети;
- множество допустимых потоков (ограничено линейными неравенствами).
Задача формулируется в виде:
,
где
– стоимость потока (линейный функционал).
Другой вариант задания системы потоков
посмотрите в книге Шварца (см. ссылку выше).