Логистика человеко-машинных систем. Чертыковцев В.К. - 28 стр.

UptoLike

ВУЗ: 

СамГУПС | Самара

Составители: 

Рубрика: 

29
принимающая целочисленные положительные значения, представляет собой поток данной
транспортной сети, если
ϕ
(и) = с(и) (2.10)
∑
−∈Uu
ϕ
(и) -
∑
+∈Uu
ϕ
(и) = 0 (х?х
0 ,
х ? z) (2.11)
Первое условие означает, что поток дуги не может превышать ее пропускную способность.
Второе уcловие, утверждает, что суммарный поток входящих в вершину дуг равен суммарному
потоку выходящих дуг (за исключением точек входа и выхода). Иногда последнее соотношение
называется условием сохранения потока, так как оно утверждает, что в любой промежуточной
вершине сети поток не создается и не исчезает.
Очевидно, что транспортные сети типа сети автомобильных дорог или железнодорожных
путей, сети линий связи (телеграфных или телефонных) удовлетворяют условиям, накладываемым
на транспортную сеть в теории потоков, и обладают потоком. Введем понятие суммарного потока
на конечных дугах Ф сети, отличное от понятия потока
на дуге
ϕ
(и), которое рассматривалось
ранее. Сумма потоков, исходящих из начальной вершины (истока) х
0
(рис. 2.7), равна сумме
потоков, входящих в конечную вершину (сток) z, т. е.
∑
−∈Uu
ϕ
(и) =
∑
+∈Uu
ϕ
(и) = Ф (2.12)
Соотношения определяют функцию
ϕ
(и), называемую потоком в сети (X, Т) с суммарным
потоком на конечных дугах Ф, который ставит в соответствие каждой дуге сети определенное
целочисленное и положительное число
ϕ
(и
i
) (i = 1, 2, ..., п)., где п — число дуг.
Перейдем к определению понятия величины разреза сети [50]. Допустим, что множество всех
вершин данной сети разбито на два взаимно дополнительных подмножества Р и С
х
(Р), причем
первое подмножество содержит вход сети х
0
∈
Р, а второе — выход сети z ∈ С
х
(Р), т. е. все
вершины сети, которые не вошли в подмножество Р, должны содержатьcя в подмножестве С
х
(Р)
рис. 2.8.
Сумма двух подмножеств Р и С
Х
(Р) составляет множество всех вершин сети.
В этом случае говорят, что к сети приложен разрез или в сети произведен разрез. Множество
дуг (х
i
, х
ј
), где х
i∈
Р, х
ј
∈ С
х
(Р), называется разрезом. Сумма пропускных способностей дуг разреза
называется величиной разреза и обозначается Г.
х
х
х
х
x
n
x
n
x
n-1
x
n
z
Р и с.2.8. Поток сети
Если взять карту автомобильных дорог или железнодорожных путей и с помощью ножниц
разрезать ее на две части так, чтобы разрез не попал на узлы (вершины), то получатся два взаимно
дополнительных множества населенных пунктов (вершин).
В общем случае величина потока на конечных дугах никогда не превышает
величину разреза:
Ф ≤ Г. (2.13)
Здесь использовано условие, согласно которому значение потока на дуге не превышает ее
пропускную способность, т. е.

Страницы