И.А. Кузнецов Сетевые модели. Методические указания к практическим занятиям

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУЗБАССКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра автомобильных перевозок

СЕТЕВЫЕ МОДЕЛИ

Методические указания к практическим занятиям по курсу “Теоретические основы организации и функционирования

транспортных систем” для студентов направления 552100 “Эксплуатация транспортных средств”

Составители И. А. Кузнецов А. В. Косолапов А.Ю. Тюрин

Рассмотрены и утверждены на заседании кафедры Протокол № 28 от 16.05.2000

Рекомендованы к печати методической комиссией направления 552100 Протокол № 7 от 16.05.2000

Электронная копия хранится в библиотеке главного корпуса КузГТУ

Кемерово 2000

1

ВВЕДЕНИЕ

Вметодических указаниях приводится описание практических занятий по курсу “Теоретические основы организации и функционирования транспортных систем” для студентов, обучающихся по специальности 240100.03 “Организация перевозок и управление на транспорте (автомобильном)”.

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

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

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

2

Практическое занятие № 1 РЕДУКЦИЯ ГРАФА ТРАНСПОРТНОЙ СЕТИ

Цель работы

Изучение алгоритма редукции графа транспортной сети (ГТС) для получения практических навыков решения задач сокращения размерности информационных массивов представления модели региона.

Задание

1. Построить орграф для каждой “загруженной” вершины “базового” ГТС на основе результатов расчета строки матрицы кратчайших путей проезда.

2.Построить подграф сети, представляющий собой совокупность орграфов, найденных на 1-м этапе.

3.Произвести минимизацию количества вершин подграфа за счет исключения “транзитных” вершин.

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

Методические указания к проведению работы

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

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

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

3

Пример редукции ГТС.

Исходная сеть представлена на рис. 1.

Рис. 1. Базовый ГТС

“Загруженными” в данном случае являются вершины 1, 5 и 9. Рассчитаем строку матрицы кратчайших расстояний и путей про-

езда для вершины 1:

Графически кратчайшие пути проезда от вершины 1 к вершинам 5 и 9 можно изобразить следующим образом:

4

Для вершин 5 и 9 подсеть будет выглядеть следующим образом:

Рис. 3. Орграф для вершин 5 и 9

В итоге выделенный подграф (ГТС после редукции) таков:

5

Кодировка транспортной подсети:

Таблица 2

	Номер	Номера вершин, имеющих
		прямые связи (в скобках -
	вершины
		протяженность связей)
	1	2 (4), 6 (2)
	2	5 (2)
	3	-
	4	-
	5	6 (3), 8 (3)
	6	1 (2), 7 (2)
	7	8 (4)
	8	5 (3), 9 (2)
	9	8 (2)
	10	-
	11	-

6

Оформление работы

Выполненную работу оформить на листах бумаги формата А4. Выполнение каждого задания является новым пунктом отчета. Вначале привести расчетную формулу с расшифровкой всех входящих в нее переменных, затем - подстановка в формулу числовых значений переменных и результаты расчета. Схемы ГТС чертят на листе миллиметровки формата А3 и подшивают к отчету: 1-й лист - “базовый” ГТС, 2-й - орграфы для каждой загруженной вершины, 3-й - подграф после минимизации количества вершин.

Практическое занятие № 2 МИНИМИЗАЦИЯ СЕТИ

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

Задание

1. Произвести минимизацию “базового” ГТС с помощью описанного алгоритма.

2.Изобразить минимизированную сеть графически.

3.Вычислить абсолютное и относительное сокращение суммарной длины дуг ГТС.

Исходные данные: “базовый” ГТС.

Методические указания

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

В любой сети минимальное дерево-остов можно определить с помощью следующего итеративного процесса. Начать с любого узла и соединить его с ближайшим узлом сети. Соединенные два узла образуют теперь связное множество, а оставшиеся - несвязное множество. Да-

7

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

Пример.

Решим задачу минимизации сети для ГТС, который изображен на рис. 1. Связное множество вершин будем обозначать С, несвязное множество - С.

Начнем счет от вершины 2. В соответствии с приведенным алгоритмом на начальном этапе имеем

С = {2}; С = {1, 3, 4, 5, 6, 7, 8, 9, 10, 11}.

Шаг 1. Ближайшая ко 2-й вершина из несвязного множества - вершина 5. Связываем ее со второй. Имеем

С = {2, 5}; С = {1, 3, 4, 6, 7, 8, 9, 10, 11}

Шаг 2. На втором шаге имеем четыре вершины в несвязном множестве, одинаково удаленных от вершин связного множества. Это вершины 3, 6, 7 и 8. После присоединения вершины 3 ситуация принципиально не меняется (минимальное расстояние до несвязанной вершины остается равным 3). Присоединяем вершину 8. Имеем

С = {2, 3, 5, 8}; С = {1, 4, 6, 7, 9, 10, 11}.

8

Шаг 3. Ближайшими вершинами из несвязного множества являются вершины 9 и 10 (расстояние до каждой из них - 2). Присоединяем их.

С = {2, 3, 5, 8, 9, 10}; С = {1, 4, 6, 7, 11}.

Шаг 4. Кратчайшей связью между вершинами двух множеств является связь (10 - 7) (длина - 3). Присоединяем вершину 7. Имеем

С = {2, 3, 5, 7, 8, 9, 10}; С = {1, 4, 6, 11}.

Шаг 5. Аналогично шагу 4 присоединяем вершину 6 (связь 7 - 6, длина - 2) и 1 (связь 6 - 1, длина - 2). Получаем

	9
С = {1, 2, 3, 5, 6, 7, 8, 9,	10}; С = {4, 11}.
Шаг 6. На этом шаге присоединяем оставшиеся вершины - 11
(связь 1 - 11) и 4 (связь 3 - 4)	(рис. 9).
С = {1, 2, 3, 4, 5, 6, 7, 8,	9, 10, 11}; С =

Полученная сеть имеет суммарную весовую оценку дуг, равную 29. Суммарная весовая оценка дуг “базового” графа составляет 63. Сокращение составляет 54 %.

Замечание. На шаге 2 было возможно альтернативное подключение вершины 6 вместо вершины 8. Однако связь (5 - 6) является ориентированной. В этом случае дальнейшее присоединение вершин выполнялось бы от вершины 6 (т.к. кратчайшими связями между связным и несвязным множествами были бы связи (6 - 7) и (6 - 1)), однако образовалось бы подмножество вершин { 1, 6, 7} , не связанных с остальными (т.к. связи в направлении (6 - 5) нет). Для устранения этого явления в обязательном порядке необходимо было бы предусмотреть соединение образовавшегося подмножества с остальным связным множеством (в данном примере это рационально было бы сделать по связи (7 - 5)). Суммарная длина дуг минимизированной сети в этом случае составила бы 32. Различие объясняется только наличием ориентированной дуги. На неориентированном графе алгоритм всегда дает один и тот же результат независимо от выбора альтернативных соединений.