ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ имени академика С.П. КОРОЛЕВА»

Б.А. Титов

ОСНОВЫ ТЕОРИИ ТРАНСПОРТНЫХ ПОТОКОВ

Учебное пособие

Самара ‑ 2009

УДК 629.7

Титов Б.А. основы теории транспортных потоков: Учебное пособие. / Самар. гос. аэрокосм. ун-т. Самара, 2009. с.

ISBN

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

Пособие предназначено для студентов специальности 190701 – «Организация перевозок и управление на транспорте (воздушный транспорт)» очной и заочной форм обучения. Пособие подготовлено на кафедре организации и управления перевозками на транспорте.

Табл. Ил. Библиогр. назв.

Печатается по решению редакционно-издательского совета Самарского государственного аэрокосмического университета имени академика С.П. Королёва.

Рецензент:

доктор технических наук, профессор С.А. Ишков,

эксперт Центра сертификации эксплуатантов «Приволжский аэрорегистр» Илларионов А.А.

ISBN

© Б.А. Титов, 2009

© Самарский государственный аэрокосмический университет имени академика С.П. Королёва, 2009

СОДЕРЖАНИЕ

1.	Потоки в транспортных сетях		4
	1.1.	Графы и сети	4
	1.2.	Структуры данных для представления графов ……………..	9
	1.3.	Поток по дуге и техническая оснащенность дуги ………….	13
	1.4.	Условия непрерывности потока в сети ……………………...	16
	1.5.	Основная транспортная задача ………………………………	19
	1.6.	Многопродуктовые потоки …………………………………..	20
2.	Описание системы перевозок на транспортных системах ……...		22
	2.1.	Транспортная инфраструктура ………………………………	22
	2.2.	Потребность в перевозках ……………………………………	22
	2.3.	Равновесие в транспортной сети …………………………….	24
	2.4.	Принцип Вардропа ……………………………………………	24
	2.5.	Задача распределения перевозок …………………………….	26
	2.6.	Определение дескриптивных и нормативных систем перевозок ………………………………………………………	27
	2.7.	Дескриптивное и нормативное распределение потоков в сети …………………………………………………………..	28
	2.8.	Парадокс Брайеса ……………………………………………..	28
	2.9.	Уменьшение различия между дескриптивным и нормативным распределением потоков в сети ……………..	31
3.	Задача оптимизации транспортной сети …………..……….……...		33
	3.1.	Оптимальное планирование транспортной сети ……………	33
	3.2.	Искомые переменные …...……………………………………	34
	3.3.	Целевая функция ……………………………….…………….	38
	3.4.	Система ограничений ..………………………………………	40
4.	Методы решения задачи оптимизации транспортной сети ……...		40
	4.1.	Постановка задач оптимизации транспортной сети ..………	41
	4.2.	Методы математического программирования ...……………	42
	4.3.	Метод ветвей и границ ……………………………………….	45
	4.4.	Эвристические методы ……………………………………….	45
	4.5.	Метод отбора наиболее перспективных проектов ………….	49
	4.6.	Примеры сетевых задач, сводящихся к задачам линейного программирования ……………………………………………	51
	4.7.	Общая постановка классической транспортной задачи ……	55
	4.8.	Пример графического решения транспортной задачи, сводящейся к задаче линейного программирования ……….	56
Список использованных источников …………………………………			58

1. Потоки в транспортных сетях

1.1. Графы и сети

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

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

Ребро связывает между собой две вершины. При работе с графами часто возникает вопрос, как проложить путь из рёбер (или дуг) от одной вершины графа к другой? Поэтому в дальнейшем целесообразно говорить о движении по ребру. Это означает, что имеет место переход из вершины А графа в другую вершину В, связанную с ней ребром АВ. (При этом ребро графа, связывающее две вершины, для краткости обозначается парой этих вершин АВ, Рисунок 1).

Рисунок 1 – Простейший граф: две вершины А и В, соединённые дугой АВ

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

В ориентированном графе, или орграфе, рёбра представляют собой упорядоченные пары вершин: первая вершина – это начало ребра; а вторая – его конец. Начало и конец ребра в ориентированном графе также могут совпадать.

Пример.

Автомагистраль или воздушная линия с двусторонним движением транспортных средств описывается не ориентированным графом или ориентированным графом с двумя дугами, имеющими разное указанное направление движения (Рисунок 2).

Рисунок 2 – Графовые модели двустороннего движения между вершинами А и В

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

Графически графы могут быть изображены двояко:

‑ вершины кружками с номером вершины, а ребра – отрезками прямых или кривых;

‑ вершины точками с указанием номера вершины рядом с точкой, а рёбра – отрезками прямых или кривых.

Далее дадим графическое изображение и аналитическое описание не ориентированного и ориентированного графов (Рисунки 3, 4).

Рисунок 3 – Неориентированный граф и его аналитическое описание

Рисунок 4 – Орграф и его аналитическое описание

Отметим особенности аналитического описания графов и орграфов.

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

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

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

Полный граф – это граф, в котором каждая вершина соединена со всеми остальными.

Число ребер в полном графе без петель с N вершинами равно .

В полном ориентированном графе разрешается переход из любой вершины в любую другую.

Поскольку в графе переход по ребру разрешается в обоих направлениях, а переход по ребру в орграфе – только в одном, то в полном орграфе в два раза больше ребер, то есть их число равно (Рисунок 5).

Рисунок 5 – а) Полный граф; N = 3; число рёбер равно 3;

б) Полный орграф; N = 3; число рёбер равно 6.

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

Подграф графа или орграфа состоит из некоторого подмножества вершин и некоторого подмножества ребер .

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

Пусть в графе или орграфе ‑ это последовательность ребер, по которым можно поочередно проходить.

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

С формальной точки зрения, путь из вершины в вершину – это последовательность ребер графа , , …, .

При этом требуется, чтобы любая вершина встречалась на таком пути не более чем один раз. У всякого пути есть длина – число ребер в нем (Рисунок 6).

Рисунок 6 – Путь в графе. В данном случае имеет место два пути из вершины А в вершину В, определяемых суммой длин дуг:

для пути – ;

для пути – .

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

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

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

Например, рассмотрим пару вершин С и D в ориентированном графе на рисунке 6. Припишем ребру СD некий вес и в результате получим триплет

.

При проходе по ориентированному графу вес ребра считается ценой этого прохода.

Пример.

Стоимость перевозки по заданному сегменту (ребру) воздушной линии;

стоимость проезда по заданному отрезку платной автомагистрали и т.п.

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

Стоимость пути по взвешенному графу равна сумме весов всех ребер пути.

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

Кратчайший путь во взвешенном графе – это путь с минимальным весом, даже если число ребер в пути можно и уменьшить (Рисунок 7).

Рисунок 7 – Кратчайший путь во взвешенном графе: Р₁=24усл.ед., Р₂=36усл.ед.

Введем следующие обозначения для длины пути Р на графе.

Обозначим через – длину пути из вершины А в вершину В.

Тогда

,

где .

Длина кратчайшего пути на графе принимает обозначение

.

Здесь – множество альтернативных путей из А в В.

Далее введем определение сети.

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

Граф или орграф, в котором вершины и ребра имеют некоторые количественные характеристики, называются сетью.

И, наконец, дадим определение связного графа и цикла на графе.

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

Граф или орграф называется связным, если всякую пару узлов можно соединить, по крайней мере, одним путем.

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

Цикл на графе – это путь, который начинается и кончается в одной и той же вершине (Рисунок 8).

Рисунок 8 – Граф с циклами

В ациклическом графе или орграфе циклы отсутствуют.

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

Связный ациклический граф называется деревом (Рисунок 9).

Рисунок 9 – Ациклический граф – дерево