Задание на лабораторную работу - Задача оптимизации городской транспортной сети
Создать и оптимизировать в Microsoft Excel табличную модель задачи оптимизации городской транспортной сети.
Табл. 1
Номер варианта |
Номера вершин |
8 |
1 - 8, 12, 13, 14, 15 |
- 2. Порядок выполнения работы 1. Ознакомиться с теоретическим введением и примером выполнения задания в Microsoft Excel. 2. Получить индивидуальное задание у преподавателя. 3. Построить математическую модель данной задачи. 4. С помощью программы MS Excel создать новую рабочую книгу. 5. На рабочем листе MS Excel создать табличную модель данной задачи, т. е. таблицы исходных данных и результатов решения. В рабочий лист также должны быть занесены расчетные формулы, связывающие переменные модели. 6. Оптимизировать модель, т. е. построить минимальное покрывающее дерево исходного графа, используя средство Поиск решения. 7. Проанализировать полученное решение и сделать выводы. 3. Теоретическое введение
Периодическое открытие новых автобусных маршрутов, связанное с формированием пассажиропотоков в новых жилых и промышленных районах, оказывает существенное влияние на функционирование действующей маршрутной системы автобусного транспорта города. В связи с этим возникает периодическая необходимость уточнения, совершенствования и оптимизации всей маршрутной системы города в целом. Оптимизация маршрутной системы осуществляется с помощью экономико-математических методов планирования, при этом используются два основных методических подхода.
В одном из них рассматривают маршрутную систему в совокупности с наличным парком автобусов и установленными нормативами скорости движения по участкам маршрута. В результате выявляются общие затраты времени пассажиров на поездки и их систематическое сокращение принимается в качестве основного критерия.
При втором подходе маршрутную систему автобусного транспорта города рассматривают как взаимоувязанную конфигурацию прямых транспортных связей между взаимодействующими (тяготеющими) конечными и основными промежуточными пунктами массового передвижения пассажиров на всей территории города. При этом основным критерием является минимум пересадочности. Поскольку маршрутная система базируется на транспортной сети, ее совершенствуют путем выбора лучшего варианта при равных условиях обеспеченности подвижным составом. Таким образом, второй методический подход является более рациональным, отвечающим цели и постановке задачи.
Рассмотрим алгоритм (последовательность действий) ее решения:
- ? на плане города с границами районов отмечают важнейшие узлы (площади) массового формирования пассажиропотоков; осуществляют ранжирование пассажирообразующих узлов (пунктов) по ожидаемым трудовым и культурно-бытовым поездкам и выявляется их примерный объем (спрос на перевозки); ? определяют первоочередные кратчайшие транспортные связи (маршруты) по перевозке пассажиров в часы пик (к местам приложения труда), а также связи районов с железнодорожными (речным, морским, автомобильным) вокзалами, рынками, станциями метрополитена и др.; ? территорию городских районов разбивают на микрорайоны и устанавливают первоочередные конечные пункты автобусных маршрутов. Выявляют первоочередность прямых транспортных связей между отдельными конечными пунктами, как для трудовых, так и культурно-бытовых поездок; ? устанавливают наиболее важные промежуточные узлы большой сменяемости пассажиров между конечными пунктами основных автобусных маршрутов, производят выбор и обоснование наиболее рациональных вариантов ожидаемой трассы маршрута; ? определяют примерное ожидаемое распределение пассажиропотока по промежуточным узловым пунктам автобусных маршрутов. Составляют примерную матрицу ожидаемых корреспонденций пассажиров между конечными и промежуточными пунктами автобусных маршрутов во времени суток. Выявляют наиболее рациональную маршрутную систему автобусного транспорта города, имеющую наибольшую прямолинейность маршрутов и минимальный коэффициент пересадочности.
Конфигурация автобусных линий на плане города образует автобусную транспортную сеть города. Автобусная транспортная сеть со всеми пролегающими по ней городскими автобусными маршрутами представляет собой маршрутную систему.
Оптимальная, с точки зрения затрат времени пассажиров на передвижение, маршрутная система должна быть проложена по кратчайшей транспортной сети. Задача нахождения кратчайшей транспортной сети сводится к задаче о минимальном покрывающем дереве в графе.
Содержательная постановка задачи заключается в следующем. Необходимо разработать проект транспортной сети, которая должна соединить конечное число микрорайонов в некотором городе. Из экономических соображений требуется, чтобы общая стоимость реализации проекта (общая протяженность сети) была минимальной, при этом должно быть выполнено обязательное условие - из любого микрорайона по данной транспортной сети можно было бы попасть в любой другой микрорайон города.
Дадим математическую постановку задачи о минимальном покрывающем дереве в графе.
Рассмотрим неориентированный связный граф: , в котором - конечное множество вершин, - конечное множество ребер, - весовая функция ребер. Для математической постановки задачи удобно обозначить отдельные значения весовой функции ребер через: , где ребро соответствует паре вершин. Согласно содержательной постановке рассматриваемой задачи отдельные значения: могут интерпретироваться как затраты времени пассажиров на передвижение по участку исходного графа.
Стоимость любого подмножества ребер в графе равна сумме весов ребер, входящих в это подмножество. Требуется определить такое подмножество ребер, которое образует покрывающее или остовное дерево в графе и обладает минимальной стоимостью.
Для формальной записи условий задачи о минимальном покрывающем дереве в графе в виде модели булева программирования следует воспользоваться двумя условиями покрывающего дерева в графе:
- 1. Каждая из вершин исходного графа должна иметь хотя бы одно инцидентное ей ребро, входящее в минимальное покрывающее дерево. В противном случае такие вершины в искомом дереве окажутся изолированными, и, следовательно, дерево не будет являться покрывающим. 2. Общее количество ребер в минимальном покрывающем дереве должно быть в точности равно, где - общее количество вершин исходного графа. Действительно, если некоторое дерево содержит меньше ребер, то оно не будет покрывающим, если же дерево содержит более ребер, то оно будет содержать цикл.
Введем в рассмотрение булевых переменных, которые для удобства обозначаются через и интерпретируются следующим образом. Переменная, если ребро, которому соответствует пара вершин, входит в искомое покрывающее дерево минимальной стоимости, и, в противном случае, т. е. если ребро не входит в оптимальное покрывающее дерево. Заметим, что количество рассматриваемых булевых переменных конечно и равно, где - количество ребер исходного графа.
Тогда математическая постановка задачи о минимальном покрывающем дереве в графе может быть сформулирована следующим образом.
Найти минимум целевой функции:
(1)
При ограничениях:
(2)
Первые три ограничения в системе ограничений (2) требуют выполнения первого из отмеченных ранее свойств, т. е. в искомом покрывающем дереве не должно быть изолированных вершин. Четвертое ограничение в (2) требует выполнения второго из отмеченных ранее свойств, т. е. искомое покрывающее дерево должно содержать ровно ребер. Наконец, последнее ограничение в (5) требует, чтобы переменные принимали только булевы значения.
Примечание: В исходном графе рассматриваемой задачи не должно быть висячих вершин. Для того чтобы минимальное покрывающее дерево было связным и не имело циклов необходимо указать в качестве ограничений для ребер, связывающих эти вершины, значения.
Похожие статьи
-
Введение - Моделирование крупномасштабной транспортной сети предфрактальными графами
Транспорт - важный стратегический комплекс, в значительной степени определяющий мощь экономики страны и обеспечивающий нужды общества в перемещении людей...
-
В зависимости от содержания задачи может быть два случая: когда ребра графа G единичной длины; когда ребра графа произвольной длины. Для каждого из этих...
-
Транспортные задачи, имеющие некоторые усложнения в постановке - Экономико-математические методы
Транспортная задача с избытком запасов: Для отыскания оптимального плана вводят фиктивный (n+1)-й пункт назначения Bn+1 с потребностью bn+1 и полагают...
-
Выводы, Литература - Моделирование крупномасштабной транспортной сети предфрактальными графами
В качестве модели карты дорог предлагается использовать предфрактальные графы, которые естественным образом отражают структуру связей при рассмотрении...
-
Для заданного региона обслуживания с помощью технологии ГИС предоставляется карта автомобильных дорог, на которой указаны пункты, соответствующие...
-
Определим понятие предфрактального графа индуктивно. Обозначим через - конечный связный n-вершинный граф с множеством вершин и множеством ребер, который...
-
Пример транспортной задачи линейного программирования - Оптимальное программирование
Транспортная задача -- математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из...
-
Экономические задачи, сводящиеся к транспортной модели Транспортная модель используется для составления наиболее экономичного плана перевозок одного вида...
-
Вводим дополнительные ограничения в модель: А) продукция типа 1 выпускается только в том случае, если разрешен выпуск хотя бы одного типа продукции: 2 и...
-
Моделирование транспортной сети большой размерности с помощью предфрактальных графов позволяет строить эффективные алгоритмы благодаря свойству...
-
В основе модели крупномасштабной транспортной сети лежит принцип иерархической организации территорий (в нисходящем направлении). Рассмотрим карту сети...
-
Математическая модель транспортной задачи: F = ??cIjXIj, (1) При условиях: ?xIj = aI, i = 1,2,..., m, (2) ?xIj = bJ, j = 1,2,..., n, (3)...
-
Развитие методов многокритериальной оптимизации сложных систем обусловлено необходимостью повышения эффективности их функционирования на основе обобщения...
-
ПОСТАНОВКА ЗАДАЧИ - Задача коммивояжера
Пусть имеется п городов. Расстояния между любой парой городов (i, j) известны и составляют dij, где i=1, m; j=1, n; i?j. Если прямого маршрута...
-
Минимальное остовное дерево в связанном взвешенном неориентированном графе-это остовное дерево данного графа, в котором сумма весов, входящих в него...
-
Задача поиска маршрутов в графе (путей в орграфе)
Задача поиска маршрутов в графе (путей в орграфе) Алгоритм Тэрри поиска маршрута в связном графе, соединяющем вершины и. Правила. 1) Идя по произвольному...
-
С помощью специальных генетических алгоритмов (NSGA, NPGA, MOGA) была решена задача многокритериальной оптимизации инвестиционного портфеля. Каждый из...
-
Метод дифференциальных рент для решения транспортной задачи - Формирование оптимального штата фирмы
Для решения транспортных задач используется несколько методов. Рассмотрим решение с помощью метода дифференциальных рент. При нахождении решения...
-
Транспортная задача - Экономико-математические методы
Методы линейного программирования, являются хорошим инструментом для решения ряда проблем распределения ресурсов. Применение пакетов прикладных программ...
-
Поток в транспортной сети - Нахождение максимального потока в графе
Функция, определенная на множестве X дуг транспортной сети D и принимающая целочисленные значения, называется допустимым потоком (или просто потоком) в...
-
В современных условиях повышается самостоятельность предприятий в принятии и реализации управленческих решений, их экономическая и юридическая...
-
Задачи, решаемые на основе нейронных сетей - Прогнозирующие системы
В литературе [33, 41, 43] встречается значительное число признаков, которыми должна обладать задача, чтобы применение НС было оправдано и НС могла бы ее...
-
В разделе 1 курсовой работы требуется: Определить количество закупаемого заданным филиалом фирмы сырья у каждого АО, (xj), максимизируя прибыль филиала....
-
Расчет верхней и нижней границы надежности схемы методом минимальных путей и сечений Как видно из схемы, она не является последовательно-параллельной,...
-
Решение транспортной задачи методом потенциалов - Математическая модель решения транспортной задачи
Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями...
-
Задача маршрутизации реализуется набором алгоритмов, каждый из которых осуществляет решение задачи коммивояжера. Коммивояжер (распространитель товаров)...
-
Постановка задачи За сельскохозяйственной артелью "Горизонт" закреплено 3 890 га сельскохозяйственных угодий, в том числе 3406 га пашни, 389 га сенокосов...
-
Экономические задачи, сводящиеся к транспортным моделям - Экономико-математические методы
Алгоритмы и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с...
-
Для примера рассмотрим вытекающую из общей постановки (3),(4) двухкритериальную () многоэтапную динамическую задачу, с целевыми функциями дохода и потерь...
-
Это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты (эффективность) возрастают или...
-
Постановка задачи - Методика решения задачи целочисленного программирования
Сформулировать по заданному 24-хзначному числу модель целочисленного программирования вида: Где все параметры модели должны быть определены из следующих...
-
Задача кластеризации может быть сведена к задаче раскраски вершин графа. Для этого строится граф несовместимости. Вершинам графа соответствуют...
-
ВВЕДЕНИЕ - Задача коммивояжера
Данная работа посвящена теме "Задача о коммивояжере". Задача коммивояжера заключается в определении такой последовательности объезда городов, которая...
-
Введение, Основные положения - Эволюционные процедуры решения комбинаторных задач на графах
Среди набора комбинаторно-логических задач на графах важное место занимает проблема определения паросочетаний, раскраски графа, выделения в графе...
-
Наличие особых ситуаций на террайне зависит от характеристик его сложности. Ниже приведена возможная классификационная схема характеристик сложности...
-
В работе рассматривается задача нахождения маршрутов развоза товаров на объекты заданного региона, возникающая у компаний, желающих сократить...
-
В настоящее время Российская Федерация входит в состав ВТО, в связи с чем, для устойчивого развития, для надежности, для стойкости [1, 2] появляется...
-
Задача кластеризации реализуется набором методов (алгоритмов), каждый из которых осуществляет разбиения региона на компактные зоны обслуживания. Аппарат...
-
Оптимизация инвестиционного портфеля (ИП) [Дубровин и др., 2008], [Мищенко и др., 2002], [Серов, 2000] является одной из важных экономических задач,...
-
На основании вышеприведенных обозначений сформулируем математическую модель задачи оптимизации графиков занятости работников с многосменной организацией...
Задание на лабораторную работу - Задача оптимизации городской транспортной сети