1.3. Определение максимального потока направленного графа

С каждым ребром (e) связывается пропускная (провозная) способность - неотрицательное число (c_e) рассчитываемое в соответствии с Методикой N 266 и Инструкцией N 545/р, на соответствующий рассматриваемый период с учетом пассажирского движения.

Величина потока, передаваемого по ребру (e), называется его мощностью - f(e). Поток (f) должен обладать следующими свойствами:

величина потока через ребро не может превышать его пропускную (провозную) способность: то есть должно выполняться условие 0 <= f(e) <= c_e;

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

, [1.1]

где

- сумма значений потока по всем ребрам, входящим в узел, груз. поездов/сутки (млн т/год);

- сумма значений потока по всем ребрам, выходящим из узла, груз. поездов/сутки (млн т/год).

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

Основная алгоритмическая задача для потоковой сети (расчетных железнодорожных магистралей и подходов к портам, представленных в виде направленного графа) найти поток максимально возможной величины.

Для определения максимально возможной величины потока направленного графа производится построение потоков по ребрам графа начинается с ближайших станций его зарождения к станциям его погашения.

Суммарной пропускной или провозной способностью направленного графа является сумма потоков, которые могут быть переданы по насыщенным ребрам, расположенным между станциями входа (зарождения) и выхода (погашения) потоков, с учетом возможностей пропуска дополнительного местного потока по ненасыщенным ребрам. При этом насыщенным называется ребро, на котором поток достигает его пропускной (провозной) способности, т.е. выполняется условие f(e) = c_e.

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

Алгоритм определения максимального потока направленного графа или характерного сечения приведен ниже:

1. На сформированной модели графа построить некоторый поток (f_п) от источника к стоку с учетом приоритетности пропуска.

2. Осуществить учет пропущенного потока (f_п) на ребрах графа, с определением оставшегося после пропуска потока резерва пропускной способности (c_рез, груз. поездов/сутки (млн т/год):

c_рез = c_е - f_п, [1.2]

при этом необходимо соблюдать следующие условия:

для ребер графа, по которым проследовал поток (f_п) при выполнении равенства: c_рез = 0, ребра считаются насыщенным и дальнейший пропуск потока по ним невозможен;

при дальнейшем построении потоков на графе от источников к стокам обеспечить насыщение одного из ребер графа.

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

4. Рассмотреть ненасыщенные ребра графа на предмет возможности пропуска дополнительного потока от источников, расположенных в границах железнодорожных магистралей.

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

При выполнении пункта 2 представленного алгоритма образуется новое насыщенное ребро (участок с исчерпанной пропускной способностью), а т.к. число ребер графа конечно, то пункты 3 и 4 представленного алгоритма могут быть выполнены лишь конечное число раз, поэтому указанный алгоритм обязательно построит максимальный поток за конечное число шагов.

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

Для расчета целевых показателей федерального проекта и мониторинга их достижения расчет выполняется исходя из следующих условий:

величины пропускной и провозной способностей по ребрам графа (f(e) соответствуют периоду начала реализации федерального проекта и этапам ввода в эксплуатацию объектов;

параметр провозной способности в млн тонн за год определяется на основании пропускных способностей участков на начало соответствующего года и их увеличения с учетом планов ввода в эксплуатацию объектов инфраструктуры в течение года (расчетное средневзвешенное значение по итогам года);

величины потоков по ребрам графа (f(e) должны соответствовать периоду максимальной мощности инвестиционного проекта.

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

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

Характерными сечениями для ежегодного мониторинга значений суммарных пропускных и провозных способностей Байкало-Амурской и Транссибирской магистралей, при соответствующей конфигурации участков магистралей, по результатам решения задачи определения максимального потока в сети, являются участки Новый Ургал - Комсомольск-Сортировочный и Известковая - Волочаевка I.

Для Восточного полигона сумма потоков , пропущенных по характерному сечению, будет являться максимальным потоком направленного графа или пропускной (провозной) способностью железнодорожных магистралей (Гхс_i, млн т):

, [1.3]

где

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

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

Значения провозных способностей по участкам, составляющим характерное сечение, определяются в соответствии с пунктом 1.4 Приложения к Методике.