Элементы транспортной системы и ее параметры

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

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

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

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

Вершины обозначаются номерами или индексами i, j. Дуга обозначается номерами вершин, которые она соединяет, например (i,j) или просто ij. Каждая дуга имеет оценку pij, которая определяет длину дуги (расстояние между вершинами) или затраты на движение по дуге. Когда затраты при движении по дуге в одном направление отличаются от затрат при движении в другом направлении, то оценка дуги записывается в виде дроби.

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

Маршрут – это последовательность прохождения вершин транспортной сети при движении от начальной вершины (пункта отправления) до конечной вершины (пункта назначения). Обозначается маршрут путем перечисления номеров вершин, т.е. Si1,in[i1,i2,…in].

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

Предшествующая вершина – вершина, которая в маршруте предшествует заданной вершине. Обозначается как λi, где λ – номер вершины, предшествующей вершине i в маршруте. Для начальной вершины маршрута λi=0.

Потенциал вершины – это сумма оценок дуг, входящих в маршрут движения от начальной вершины до данной. Обозначается как pi. Потенциал конечной вершины маршрута равен длине (оценке) всего маршрута.

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)