Решение задачи оптимизации городской транспортной сети в MS Excel

Лабораторная работа №2.

«Решение задачи оптимизации городской транспортной сети в MS Excel»

Задание на лабораторную работу

Создать и оптимизировать в Microsoft Excel табличную модель задачи оптимизации городской транспортной сети.

Номер варианта	Номера вершин
8	1 – 8, 12, 13, 14, 15

Порядок выполнения работы:

1. Ознакомиться с теоретическим введением и примером выполнения задания в Microsoft Excel.
2. Получить индивидуальное задание у преподавателя.
3. Построить математическую модель данной задачи.
4. С помощью программы MS Excel создать новую рабочую книгу.
5. На рабочем листе MS Excel создать табличную модель данной задачи, т.е. таблицы исходных данных и результатов решения. В рабочий лист также должны быть занесены расчетные формулы, связывающие переменные модели.
6. Оптимизировать модель, т.е. построить минимальное покрывающее дерево исходного графа, используя средство Поиск решения.
7. Проанализировать полученное решение и сделать выводы.

Теоретическое введение

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

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

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

Рассмотрим алгоритм (последовательность действий) ее решения:

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

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

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

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

Дадим математическую постановку задачи о минимальном покрывающем дереве в графе.

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

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

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

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

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

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

Найти минимум целевой функции

(4)

при ограничениях

(5)

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

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

Исходные данные

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

Рис. 6. Граф транспортных связей микрорайонов города

Таблица 2

Матрица смежности исходного графа

	v1	v2	v3	v4	v5	v6	v7	v8	v9	v10	v11	v12	v13	v14	v15	v16	v17	v18	v19	v20	v21	v22	v23	v24	v25	v26	v27	v28	v29	v30	v31	v32	v33
v1	0	1,0
v2		0	1,5	0,9
v3			0		0,7	0,8
v4				0	1,1							1,7
v5					0		0,9
v6						0		1,2
v7							0	0,8							0,9
v8								0
v9									0	1,6
v10										0	1,5
v11											0	1,4
v12												0	0,9	1,6	2,1
v13													0	1,5										1,1
v14														0	1,4	1,2											1,5
v15															0	0,9	1,4
v16																0	1,4
v17																	0	1,4													1,0
v18																		0	1,5
v19																			0
v20																				0			0,8
v21																					0	0,3
v22																						0	1,8			1,5
v23																							0	1,6	1,3
v24																								0	0,7		1,5
v25																									0	1,3
v26																										0
v27																											0	0,5		1,8
v28																												0	0,8
v29																													0
v30																														0	1,2
v31																															0	1,5	2,0
v32																																0
v33																																	0

Примечание: Матрица смежности является симметричной, т.е. расстояния между пунктами в прямом и обратном направлении равны. Знак «» означает отсутствие прямой связи между пунктами.

Решение

Матрица смежности для нашего случая имеет вид:

	v1	v2	v3	v4	v5	v6	v7	v8	v12	v13	v14	v15
v1	0	1,0
v2		0	1,5	0,9
v3			0		0,7	0,8
v4				0	1,1				1,7
v5					0		0,9
v6						0		1,2
v7							0	0,8				0,9
v8								0
v12									0	0,9	1,6	2,1
v13										0	1,5
v14											0	1,4
v15												0

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

(3)

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

Для решения данной задачи с помощью программы MS Excel создадим новую книгу и изменим имя ее первого листа на Покрывающее дерево. Для решения поставленной задачи выполним следующие подготовительные действия.

1. Внесем необходимые надписи в ячейки A1:F1, A11 (рис. 7). Следует отметить, что конкретное содержание этих надписей не оказывает влияние на решение рассматриваемой задачи.
2. В ячейки A2:A15 введем индексы начальных вершин, а в ячейки B2:B15 – индексы конечных вершин всех имеющихся ребер исходного графа.
3. В ячейки C2:C15 введем значения коэффициентов целевой функции (1).
4. В ячейку F2 введем формулу: =СУММПРОИЗВ(C2:C15; D2:D15), которая представляет собой целевую функцию (3).
5. В ячейки E2:E15 введем значение левых частей первых двенадцати ограничений системы ограничений (4) (см. рис. 7).
6. В ячейку D16 введем формулу: =СУММ(D2:D14), которая представляет собой левую часть тринадцатого ограничения в системе (4).

Внешний вид рабочего листа MS Excel с исходными данными решения задачи о минимальном покрывающем дереве в графе имеет вид, представленный на рис. 7.

Рис. 7. Исходные данные для решения задачи о минимальном

покрывающем дереве в графе

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

После появления диалогового окна Поиск решения следует выполнить следующие действия:

1. В поле с именем Установить целевую ячейку: ввести абсолютный адрес ячейки $F$2.
2. Для группы Равной: выбрать вариант поиска решения – минимальному значению.
3. В поле с именем Изменяя ячейки: ввести абсолютный адрес ячеек $D$2:$D$15.
4. Задать ограничения рассматриваемой задачи, как показано на рис. 8.

Рис. 8. Переменные и параметры поиска решения

1. В окне дополнительных параметров поиска решения выбрать отметки Линейная модель и Неотрицательные значения.

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

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

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

Найденному оптимальному решению соответствует значение целевой функции:

На рис. 10 представлено минимальное покрывающее дерево графа.

Рис. 10. Минимальное покрывающее дерево исходного графа

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

Решение задачи оптимизации городской транспортной сети в MS Excel