Многопродуктовые потоки

В предыдущем разделе мы познакомились с постановками сетевых задач, в которых было много пунктов производства и много пунктов потребления. Причем поток мог быть послан из любого произвольного пункта отправления в любой произвольный пункт назначения.

Если требуется, чтобы поток из определенных пунктов отправления должен быть послан в определенные пункты назначения, то мы получаем новый класс задач – задачи о многопродуктовых потоках.

Особый случай многопродуктовых потоков – когда каждый поток идет только из одного определенного пункта отправления только в один определенный пункт назначения.

Для общего потока из узла А в узел В используем обозначение и введем следующее определение.

Определение.

Упорядоченная пара узлов А, В, состоящая из пункта отправления А и пункта назначения В называется транспортной связью.

Множество всех транспортных связей на сети будем обозначать через S.

Отметим, что транспортная связь АВ только тогда имеет смысл, когда в сети существует путь, связывающий А и В.

С учетом введенного определения условия непрерывности потоков в сети приобретают вид:

Здесь – поток на дуге ij, который порождается транспортной связью АВ. Эта величина называется транспортной корреспонденцией (пассажирской или грузовой).

В случае многопродуктовых потоков справедливо также требование, чтобы потоки были неотрицательными:

.

В ряде случаев условие непрерывности потока в сети удобнее выразить через понятие пути. Обозначим – поток на дуге ij, порожденный транспортной связью АВ и использующий путь р из А в В.

Тогда условия непрерывности потоков в сети можно представить в виде

.

Кроме того, сюда следует добавить условия неотрицательности потоков

.

Полученные выше соотношения образуют технические соотношения транспортной сети и называются характеристиками транспортной обеспеченности.