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

1

ВВЕДЕНИЕ

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

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

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

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

2

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

Цель работы

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

Задание

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

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

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

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

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

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

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

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

4

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

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

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

5

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

Таблица 2

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). Получаем

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

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

10

Оформление работы. Выполненную работу оформить на листах бумаги формата А4. Выполнение каждого задания является новым пунктом отчета. Схему минимизированной сети вычертить на листе миллиметровой бумаги формата А3 и подшить к отчету.

Практическое занятие № 3 ЗАДАЧА О НАХОЖДЕНИИ НАИБОЛЕЕ НАДЕЖНОГО

МАРШРУТА

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

Задание

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

2.Рассчитать кратчайший маршрут между указанными вершинами.

3.Сравнить протяженности найденных маршрутов и вероятности беспрепятственного проезда по ним.

Исходные данные: “базовый” ГТС; вероятности беспрепятственного проезда по всем дугам графа.

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

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

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

11

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

вероятность не быть остановленной полицией будет дополнительной вероятностью к pii , т.е. Pii = 1− pii . Соответственно, полная вероятность

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

Pst = P1• P2 • ... • Pk ,

где s - источник (исходный пункт), t - сток (пункт назначения), k - количество участков сети.

Тогда

lg Pst = lgP1+ lg P2 + ...+ lg Pk .

Алгебраически максимизация Pst эквивалентна максимизации lg Pst и, следовательно, максимизации суммы логарифмов вероятностей для отдельных участков маршрута. Поскольку lg Pj ≤ 0, максимизация суммы lg Pj эквивалентна минимизации суммы -lg Pj . Задача о

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

Пример. Воспользуемся приведенным алгоритмом для расчета наиболее надежного маршрута из вершины 1 в вершину 9 для ГТС, изображенного на рис. 1.

В табл. 3 приведены вероятности для участков сети и их логариф-