2.4.1. ТРАНСПОРТНЫЕ ПОТОКИ

По своему назначению транспорт делится на две основные группы [16]:

транспорт общего пользования;

внутрипроизводственный транспорт.

К транспорту общего пользования относится группа транспорта, которая удовлетворяет все общественные потребности в перевозке населения и грузов.

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

В задачах управления транспортными потоками широкое распространение получили логистические модели в виде графов [25]. В графовых моделях используются концепции топологических геометрий и пространств. Из класса графовых моделей будем рассматривать только потоковые модели, называемые транспортными сетями [25].

Под транспортной сетью понимается плоский граф рис. 2.7, в котором отсутствуют петли. Граф без петель называется сетью, если каждой дуге и отнесено целое число с(и) = 0, называемое пропускной способностью.

х;

х1

х0

хз

z

Р и с. 2.7. Транспортная сеть

Этот граф обладает следующими свойствами:

существует одна и только одна вершина хо, из которой дуги выходят, но ни одна дуга не входит. Эта вершина называется входом или истоком сети;

существует одна и только одна вершина графа z, в которую входят дуги, но ни одна дуга не выходит. Эта вершина называется выходом или стоком сети.

Для сетей вводят понятие потока. Пусть U- — множество дуг, входящих в вершину х„ a U — множество дуг, выходящих из вершины xt. Функция р (и), определенная на множестве дуг сети и

принимающая целочисленные положительные значения, представляет собой поток данной транспортной сети, если

(р(и) = с (и) (2.10)

2 (р(и) -2 ф(и) = 0 (X?X0X ? z) (2.11)

ueU - ueU+

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

Второе условие, утверждает, что суммарный поток входящих в вершину дуг равен суммарному потоку выходящих дуг (за исключением точек входа и выхода).

Очевидно, что транспортные сети типа сети автомобильных дорог или железнодорожных путей, сети линий связи (телеграфных или телефонных) удовлетворяют условиям, накладываемым на транспортную сеть в теории потоков, и обладают потоком. Введем понятие суммарного потока на конечных дугах Ф сети, отличное от понятия потока на дуге (р(и), которое рассматривалось ранее. Сумма потоков, исходящих из начальной вершины (истока) х0 (рис. 2.7), равна сумме потоков, входящих в конечную вершину (сток) z, т. е.

2 (Р(и) = 2 <Р(и) = Ф (2.12)

ueU - ueU +

Соотношения определяют функцию (р(и), называемую потоком в сети (X, Т) с суммарным потоком на конечных дугах Ф, который ставит в соответствие каждой дуге сети определенное целочисленное и положительное число (р(и) (i = 1, 2, ..., п)., где п — число дуг.

Перейдем к определению понятия величины разреза сети [50]. Допустим, что множество всех вершин данной сети разбито на два взаимно дополнительных подмножества Р и СХ(Р), причем первое подмножество содержит вход сети х0 е Р, а второе — выход сети z е Сх (Р), т. е. все вершины сети, которые не вошли в подмножество Р, должны содержаться в подмножестве Сх (Р) рис. 2.8.

Сумма двух подмножеств Р и СХ (Р) составляет множество всех вершин сети.

В этом случае говорят, что к сети приложен разрез или в сети произведен разрез. Множество дуг (xi, Xj), где xi е Р, Xj е СХ(Р), называется разрезом. Сумма пропускных способностей дуг разреза называется величиной разреза и обозначается Г.

хп

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

В общем случае величина потока на конечных дугах никогда не превышает величину разреза:

Ф < Г. (2.13)

Здесь использовано условие, согласно которому значение потока на дуге не превышает ее пропускную способность, т. е.

(2.14)

Ф(ХЬХ]) - y(Xj,Xi)< фьХ])

Это соотношение представляет собой другую запись условия. Дело в том, что каждую дугу (например, железнодорожный путь, соединяющий два населенных пункта) можно представить двумя дугами, имеющими разное направление (два направления движения поездов) и два значения потока в прямом и обратном направлениях, или одной дугой, поток которой равен алгебраической сумме потоков прямой и обратной дуг.