Рассмотренную задачу для моделей реальных систем не всегда возможно решать без автоматизации вычислений. Методы теории графов позволяют для решения задач использовать ЭВМ. Однако при этом необходимо пред- ставить граф в памяти компьютера. Для этого используются различные фор- мы, основой которых являются матрицы смежности и инциденций.
Матрица смежности представляет собой таблицу, в которой номера столбцов и строк означают номера вершин графа. На пересечении строк и столбцов ставится 1, если вершины соединены ребром в графе (в противном случае ставится 0).
В матрице инциденций номера строк – номера вершин, а номера столбцов – номера ребер (дуг). На пересечении ставится 1, если ребро и вершина инци- дентны (т. е. ребро соединено с данной вершиной). Для графа на рис. 6 мат- рицы смежности и инциденций показаны ниже. В общем случае матрица ин- циденций необязательно квадратная.
Рис. 6. Пример графа
|
В данном примере граф G (X, V) является неориентированным. Если при- своить ориентацию ребрам графа (в этом случае ребра называются дугами), то матрицы смежности и инциденций будут другими. Это объясняется тем, что в ориентированном графе связь между вершинами существует только в одном направлении (применительно к транспортной сети можно сказать, что движение объектов по дугам сети возможно только в направлении стрелки). Так, в приведенном примере матрица смежности графа G (X, V) является симметричной относительно главной оси. При присвоении ребрам ориента- ции эта симметрия нарушается. Например, если между вершинами x 1 и х 3 провести вместо ребра дугу от x 1 к х 3, то в матрице на пересечении 3-й строки и 1-го столбца вместо 1 будет 0. В матрице инциденций для ориентированно- го графа необходимо некоторым образом указать направление ребра (т. е. ду- ги). Это можно сделать, приписывая единице знаки «+» (если дуга входит в данную вершину) или «–» (если дуга выходит из данной вершины).
МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ВЫПОЛНЕНИЮ КУРСОВОЙ РАБОТЫПО ТЕМЕ «ОПТИМИЗАЦИЯ ПОТОКА В ТРАНСПОРТНОЙ СЕТИ»
Цели курсовой работы – систематизировать знания по моделированию и оптимизации процессов УВД, приобрести умения оценивать количественные характеристики воздушного движения и определять допустимые значения характеристик процессов организации, планирования и управления воздуш- ным движением.
Требования к содержанию
Курсовая работа должна включать:
– титульный лист;
– пояснительную записку.
Пояснительная записка к курсовой работе должна содержать:
1. Общую характеристику задачи оптимизации потока в транспортной сети. В данной части необходимо дать определение транспортной сети и по- тока ВС в сети, общую характеристику задачи оптимизации, пояснить на примере задачи планирования потока в транспортной сети понятие критерия оптимизации и ограничений.
2. Исходные данные. В данном разделе необходимо привести, исходя из варианта курсовой работы, данные матрицы смежности сети, начальную ве- личину потока, а затем нарисовать исходную сеть.
Примечание. Варианты заданий к курсовой работе разрабатываются и вы-
даются преподавателем.
3. Разработку примера транспортной сети. В этом пункте необходимо дать физическую интерпретацию вершинам и дугам транспортной сети, за- данной в варианте. Пример должен содержать рисунок транспортной сети с пояснением того смысла, который присваивается вершинам, дугам, величине потока и пропускной способности дуг. Необходимо проиллюстрировать не- формальный смысл задачи транспортной сети на данном примере, т. е. ука- зать, что будет означать оптимизация потока в данном примере, какой смысл
имеет критерий оптимизации и ограничения. Это может быть, в частности, оптимизация потока воздушного движения в некотором районе воздушного пространства. В соответствии с этим дается интерпретация элементам задачи.
4. Решение. В процессе решения необходимо в соответствии с алгоритмом найти максимальный допустимый поток в сети, заданной исходными данными.
При решении необходимо перейти от задачи, сформулированной в при- мере, к формальной сети, заданной обычной совокупностью вершин { X } и дуг { U }. При этом отражаются все шаги алгоритма поиска решения. Для каждого цикла работы алгоритма:
– рисуется исходная сеть с распределенным потоком;
– рисуется полученный орграф приращений для данного потока;
– отмечается путь на орграфе, который будет рассматриваться при поис-
ке приращения потока;
– рисуется цепь на сети, по которой это приращение потока будет пущено;
– записывается величина приращения и новый полученный поток;
– последним циклом работы алгоритма является расчет общего потенци- ала сети – максимальный поток ВС, который может быть обслужен транс- портной сетью в соответствии с установленным регламентом.
5. Заключение (вывод и рекомендации). В заключении необходимо дать ха- рактеристику процессов на каждом этапе функционирования системы ОВД, за основу которой принимается модель полученной сети воздушных трасс. В за- ключении также формулируются выводы, которые должны содержать реко- мендации по совершенствованию данной транспортной сети.
6. Список использованной литературы. Список использованной литера- туры оформляется в соответствии с требованиями ГОСТ 7.1–2003 «Библио- графическая запись. Библиографическое описание. Общие требования и пра- вила составления».
Пример. Крыжановский, Г. А. Введение в прикладную теорию УВД /
Г. А. Крыжановский. – М.: Машиностроение, 1984. – 364 с.
Требования к оформлению
Пояснительная записка выполняется на листах формата А4 в рукописном или печатном виде через 1,5–2 интервала между строками. Текст пишется на одной стороне листа, листы нумеруются.
Объем работы зависит от количества циклов в работе, а количество цик-
лов – от количества всех возможных путей в графе, построенному по матрице.
Все рисунки должны иметь подписи. Каждому шагу работы и, соответ-
ственно, каждому рисунку должно сопутствовать пояснение действий.
Каждый цикл работы алгоритма следует начинать с новой страницы, под-
писывая номер шага алгоритма.
Рекомендуемая литература
1. Теория графов и сетей при моделировании процессов УВД: учеб. посо-
бие / сост. В. А. Карнаухов. – Ульяновск: УВАУ ГА(И), 2009. − 63 с.
2. Нефедов, В. Н. Алгоритмический подход к решению задач теории гра-
фов и сетей: учеб. пособие / В. Н. Нефедов. – М.: МАИ, 1990. – 120 с.
3. Емеличев, В. А. Лекции по теории графов / В. А. Емеличев, О. И. Мель-
никова. – М.: Наука, 1990. – 384 с.
4. Основы теории УВД. В 2 ч. Ч. 1 / сост. И. Н. Глухих. – Ульяновск:
УВАУ ГА, 1998. – 29 с.